Annotation of OpenXM_contrib/gmp/gmp.texi, Revision 1.1.1.2
1.1 maekawa 1: \input texinfo @c -*-texinfo-*-
2: @c %**start of header
3: @setfilename gmp.info
1.1.1.2 ! maekawa 4: @include version.texi
! 5: @settitle GNU MP @value{VERSION}
1.1 maekawa 6: @synindex tp fn
7: @iftex
8: @afourpaper
9: @end iftex
10: @comment %**end of header
11:
1.1.1.2 ! maekawa 12: @dircategory GNU libraries
! 13: @direntry
! 14: * gmp: (gmp). GNU Multiple Precision Arithmetic Library.
! 15: @end direntry
1.1 maekawa 16:
17: @c smallbook
18:
19: @iftex
20: @finalout
21: @end iftex
22:
1.1.1.2 ! maekawa 23: @c Texinfo version 4 or up will be needed to process this into .info files.
! 24: @c
! 25: @c The edition number is in three places and the month/year in one, all
! 26: @c taken from version.texi. version.texi is created when you configure with
! 27: @c --enable-maintainer-mode, and is included in a distribution made with
! 28: @c "make dist".
1.1 maekawa 29:
30:
1.1.1.2 ! maekawa 31: @ifnottex
1.1 maekawa 32: This file documents GNU MP, a library for arbitrary-precision arithmetic.
33:
1.1.1.2 ! maekawa 34: Copyright (C) 1991, 1993, 1994, 1995, 1996, 1997, 1998, 1999, 2000 Free
! 35: Software Foundation, Inc.
1.1 maekawa 36:
37: Permission is granted to make and distribute verbatim copies of
38: this manual provided the copyright notice and this permission notice
39: are preserved on all copies.
40:
41: @ignore
42: Permission is granted to process this file through TeX and print the
43: results, provided the printed document carries copying permission
44: notice identical to this one except for the removal of this paragraph
45: (this paragraph not being relevant to the printed manual).
46: @end ignore
1.1.1.2 ! maekawa 47:
1.1 maekawa 48: Permission is granted to copy and distribute modified versions of this
49: manual under the conditions for verbatim copying, provided that the entire
50: resulting derived work is distributed under the terms of a permission
51: notice identical to this one.
52:
53: Permission is granted to copy and distribute translations of this manual
54: into another language, under the above conditions for modified versions,
55: except that this permission notice may be stated in a translation approved
56: by the Foundation.
1.1.1.2 ! maekawa 57: @end ifnottex
1.1 maekawa 58:
59: @setchapternewpage on
60: @titlepage
61: @c use the new format for titles
62:
63: @title GNU MP
64: @subtitle The GNU Multiple Precision Arithmetic Library
1.1.1.2 ! maekawa 65: @subtitle Edition @value{EDITION}
! 66: @subtitle @value{UPDATED}
1.1 maekawa 67:
1.1.1.2 ! maekawa 68: @author by Torbj@"orn Granlund, Swox AB
! 69: @email{tege@@swox.com}
1.1 maekawa 70:
71: @c Include the Distribution inside the titlepage so
72: @c that headings are turned off.
73:
74: @tex
75: \global\parindent=0pt
76: \global\parskip=8pt
77: \global\baselineskip=13pt
78: @end tex
79:
80: @page
81: @vskip 0pt plus 1filll
1.1.1.2 ! maekawa 82: Copyright @copyright{} 1991, 1993, 1994, 1995, 1996, 1997, 1998, 1999, 2000
! 83: Free Software Foundation, Inc.
1.1 maekawa 84:
85: @sp 2
86:
87: Published by the Free Software Foundation @*
88: 59 Temple Place - Suite 330 @*
89: Boston, MA 02111-1307, USA @*
90:
91: Permission is granted to make and distribute verbatim copies of
92: this manual provided the copyright notice and this permission notice
93: are preserved on all copies.
94:
95: Permission is granted to copy and distribute modified versions of this
96: manual under the conditions for verbatim copying, provided that the entire
97: resulting derived work is distributed under the terms of a permission
98: notice identical to this one.
99:
100: Permission is granted to copy and distribute translations of this manual
101: into another language, under the above conditions for modified versions,
102: except that this permission notice may be stated in a translation approved
103: by the Foundation.
104: @end titlepage
105: @headings double
106:
1.1.1.2 ! maekawa 107: @ifnottex
1.1 maekawa 108: @node Top, Copying, (dir), (dir)
109:
110: @top GNU MP
111:
112: This manual documents how to install and use the GNU multiple precision
1.1.1.2 ! maekawa 113: arithmetic library, version @value{VERSION}.
1.1 maekawa 114:
1.1.1.2 ! maekawa 115: @end ifnottex
1.1 maekawa 116:
117: @menu
1.1.1.2 ! maekawa 118: * Copying:: GMP Copying Conditions (LGPL).
! 119: * Introduction to GMP:: Brief introduction to GNU MP.
! 120: * Installing GMP:: How to configure and compile the GMP library.
! 121: * GMP Basics:: What every GMP user should now.
! 122: * Reporting Bugs:: How to usefully report bugs.
! 123: * Integer Functions:: Functions for arithmetic on signed integers.
! 124: * Rational Number Functions:: Functions for arithmetic on rational numbers.
! 125: * Floating-point Functions:: Functions for arithmetic on floats.
! 126: * Low-level Functions:: Fast functions for natural numbers.
! 127: * Random Number Functions:: Functions for generating random numbers.
! 128: * BSD Compatible Functions:: All functions found in BSD MP.
! 129: * Custom Allocation:: How to customize the internal allocation.
1.1 maekawa 130:
1.1.1.2 ! maekawa 131: * Contributors:: Who brings your this library?
! 132: * References:: Some useful papers and books to read.
1.1 maekawa 133: * Concept Index::
134: * Function Index::
135: @end menu
136:
1.1.1.2 ! maekawa 137: @node Copying, Introduction to GMP, Top, Top
1.1 maekawa 138: @comment node-name, next, previous, up
139: @unnumbered GNU MP Copying Conditions
140: @cindex Copying conditions
141: @cindex Conditions for copying GNU MP
142:
143: This library is @dfn{free}; this means that everyone is free to use it and
144: free to redistribute it on a free basis. The library is not in the public
145: domain; it is copyrighted and there are restrictions on its distribution, but
146: these restrictions are designed to permit everything that a good cooperating
147: citizen would want to do. What is not allowed is to try to prevent others
148: from further sharing any version of this library that they might get from
149: you.@refill
150:
151: Specifically, we want to make sure that you have the right to give away copies
152: of the library, that you receive source code or else can get it if you want
153: it, that you can change this library or use pieces of it in new free programs,
154: and that you know you can do these things.@refill
155:
156: To make sure that everyone has such rights, we have to forbid you to deprive
157: anyone else of these rights. For example, if you distribute copies of the GNU
158: MP library, you must give the recipients all the rights that you have. You
159: must make sure that they, too, receive or can get the source code. And you
160: must tell them their rights.@refill
161:
162: Also, for our own protection, we must make certain that everyone finds out
163: that there is no warranty for the GNU MP library. If it is modified by
164: someone else and passed on, we want their recipients to know that what they
165: have is not what we distributed, so that any problems introduced by others
166: will not reflect on our reputation.@refill
167:
168: The precise conditions of the license for the GNU MP library are found in the
169: Library General Public License that accompany the source code.@refill
170:
1.1.1.2 ! maekawa 171:
! 172: @node Introduction to GMP, Installing GMP, Copying, Top
1.1 maekawa 173: @comment node-name, next, previous, up
174: @chapter Introduction to GNU MP
1.1.1.2 ! maekawa 175: @cindex Introduction
1.1 maekawa 176:
177: GNU MP is a portable library written in C for arbitrary precision arithmetic
178: on integers, rational numbers, and floating-point numbers. It aims to provide
179: the fastest possible arithmetic for all applications that need higher
180: precision than is directly supported by the basic C types.
181:
182: Many applications use just a few hundred bits of precision; but some
1.1.1.2 ! maekawa 183: applications may need thousands or even millions of bits. GMP is designed to
1.1 maekawa 184: give good performance for both, by choosing algorithms based on the sizes of
185: the operands, and by carefully keeping the overhead at a minimum.
186:
1.1.1.2 ! maekawa 187: The speed of GMP is achieved by using fullwords as the basic arithmetic type,
1.1 maekawa 188: by using sophisticated algorithms, by including carefully optimized assembly
189: code for the most common inner loops for many different CPUs, and by a general
190: emphasis on speed (as opposed to simplicity or elegance).
191:
1.1.1.2 ! maekawa 192: There is carefully optimized assembly code for these CPUs:
! 193: @cindex CPUs supported
! 194: ARM,
! 195: DEC Alpha 21064, 21164, and 21264,
! 196: AMD 29000,
! 197: AMD K6 and Athlon,
! 198: Hitachi SuperH and SH-2,
! 199: HPPA 1.0, 1.1 and 2.0,
! 200: Intel Pentium, Pentium Pro/Pentium II, generic x86,
! 201: Intel i960,
! 202: Motorola MC68000, MC68020, MC88100, and MC88110,
! 203: Motorola/IBM PowerPC 32 and 64,
! 204: National NS32000,
! 205: IBM POWER,
! 206: MIPS R3000, R4000,
! 207: SPARCv7, SuperSPARC, generic SPARCv8, UltraSPARC,
! 208: DEC VAX,
! 209: and Zilog Z8000.
! 210: Some optimizations also for Clipper, IBM ROMP (RT), and Pyramid AP/XP.
! 211:
! 212: @cindex Mailing list
! 213: There is a mailing list for GMP users. To join it, send a mail to
! 214: @email{gmp-request@@swox.com} with the word @samp{subscribe} in the message
! 215: @strong{body} (not in the subject line).
! 216:
! 217: @cindex Home page
! 218: @cindex Web page
! 219: For up-to-date information on GMP, please see the GMP Home Pages at
! 220: @uref{http://www.swox.com/gmp/}.
1.1 maekawa 221:
222:
223: @section How to use this Manual
1.1.1.2 ! maekawa 224: @cindex About this manual
1.1 maekawa 225:
1.1.1.2 ! maekawa 226: Everyone should read @ref{GMP Basics}. If you need to install the library
! 227: yourself, you need to read @ref{Installing GMP}, too.
1.1 maekawa 228:
229: The rest of the manual can be used for later reference, although it is
230: probably a good idea to glance through it.
231:
232:
1.1.1.2 ! maekawa 233: @node Installing GMP, GMP Basics, Introduction to GMP, Top
1.1 maekawa 234: @comment node-name, next, previous, up
1.1.1.2 ! maekawa 235: @chapter Installing GMP
! 236: @cindex Installing GMP
! 237: @cindex Configuring GMP
1.1 maekawa 238:
1.1.1.2 ! maekawa 239: @noindent
! 240: GMP has an autoconf/automake/libtool based configuration system. On a
! 241: Unix-like system a basic build can be done with
1.1 maekawa 242:
1.1.1.2 ! maekawa 243: @example
! 244: ./configure
! 245: make
! 246: @end example
1.1 maekawa 247:
1.1.1.2 ! maekawa 248: @noindent
! 249: Some self-tests can be run with
1.1 maekawa 250:
1.1.1.2 ! maekawa 251: @example
! 252: make check
! 253: @end example
1.1 maekawa 254:
1.1.1.2 ! maekawa 255: @noindent
! 256: And you can install (under @file{/usr/local} by default) with
1.1 maekawa 257:
1.1.1.2 ! maekawa 258: @example
! 259: make install
! 260: @end example
1.1 maekawa 261:
1.1.1.2 ! maekawa 262: @noindent
! 263: If you experience problems, please report them to @email{bug-gmp@@gnu.org}.
! 264: (@xref{Reporting Bugs}, for information on what to include in useful bug
! 265: reports.)
1.1 maekawa 266:
1.1.1.2 ! maekawa 267: @menu
! 268: * Build Options::
! 269: * ABI and ISA::
! 270: * Notes for Package Builds::
! 271: * Notes for Particular Systems::
! 272: * Known Build Problems::
! 273: @end menu
1.1 maekawa 274:
275:
1.1.1.2 ! maekawa 276: @node Build Options, ABI and ISA, Installing GMP, Installing GMP
! 277: @section Build Options
! 278: @cindex Build options
1.1 maekawa 279:
1.1.1.2 ! maekawa 280: @noindent
! 281: All the usual autoconf configure options are available, run @samp{./configure
! 282: --help} for a summary.
1.1 maekawa 283:
1.1.1.2 ! maekawa 284: @table @asis
! 285: @item Non-Unix Systems
1.1 maekawa 286:
1.1.1.2 ! maekawa 287: @samp{configure} needs various Unix-like tools installed. On an MS-DOS system
! 288: cygwin or djgpp should work. It might be possible to build without the help
! 289: of @samp{configure}, certainly all the code is there, but unfortunately you'll
! 290: be on your own.
! 291:
! 292: @item Object Directory
! 293:
! 294: To compile in a separate object directory, @command{cd} to that directory, and
! 295: prefix the configure command with the path to the GMP source directory. For
! 296: example @samp{../src/gmp/configure}. Not all @samp{make} programs have the
! 297: necessary features (@code{VPATH}) to support this. In particular, SunOS and
! 298: Slowaris @command{make} have bugs that make them unable to build from a
! 299: separate object directory. Use GNU @command{make} instead.
! 300:
! 301: @item @option{--disable-shared}, @option{--disable-static}
! 302:
! 303: By default both shared and static libraries are built (where possible), but
! 304: one or other can be disabled. Shared libraries are very slightly slower,
! 305: having a small cost on each function call, but result in smaller executables
! 306: and permit code sharing between separate running processes.
! 307:
! 308: @item @option{--target=CPU-VENDOR-OS}
! 309:
! 310: The build target can be specified in the usual way, for either native or cross
! 311: compilation.
! 312:
! 313: If @option{--target} isn't given, @samp{./configure} builds for the host
! 314: system as determined by @samp{./config.guess}. On some systems this can't
! 315: distinguish between different CPUs in a family, and you should check the
! 316: guess. Running @samp{./config.guess} on the target system will also show the
! 317: relevant @samp{VENDOR-OS}, if you don't already know what it should be.
1.1 maekawa 318:
1.1.1.2 ! maekawa 319: In general, if you want a library that runs as fast as possible, you should
! 320: configure GMP for the exact CPU type your system uses. However, this may mean
! 321: the binaries won't run on older members of the family, and might run slower on
! 322: other members, older or newer. The best idea is always to build GMP for the
! 323: exact machine type you intend to run it on.
! 324:
! 325: The following CPU targets have specific assembly code support. See
! 326: @file{configure.in} for which @file{mpn} subdirectories get used by each.
1.1 maekawa 327:
328: @itemize @bullet
329:
1.1.1.2 ! maekawa 330: @c Keep this formatting, it's easy to read and it can be grepped to
! 331: @c automatically test that targets listed get through ./config.sub
1.1 maekawa 332:
333: @item
1.1.1.2 ! maekawa 334: Alpha:
! 335: @samp{alpha},
! 336: @samp{alphaev5},
! 337: @samp{alphaev6}
! 338:
! 339: @item
! 340: Hitachi:
! 341: @samp{sh},
! 342: @samp{sh2}
! 343:
! 344: @item
! 345: HPPA:
! 346: @samp{hppa1.0},
! 347: @samp{hppa1.1},
! 348: @samp{hppa2.0},
! 349: @samp{hppa2.0w}
! 350:
! 351: @item
! 352: MIPS:
! 353: @samp{mips},
! 354: @samp{mips3},
! 355:
! 356: @item
! 357: Motorola:
! 358: @samp{m68000},
! 359: @samp{m68k},
! 360: @samp{m88k},
! 361: @samp{m88110}
! 362:
! 363: @item
! 364: POWER:
! 365: @samp{power1},
! 366: @samp{power2},
! 367: @samp{power2sc},
! 368: @samp{powerpc},
! 369: @samp{powerpc64}
! 370:
! 371: @item
! 372: SPARC:
! 373: @samp{sparc},
! 374: @samp{sparcv8},
! 375: @samp{microsparc},
! 376: @samp{supersparc},
! 377: @samp{sparcv9},
! 378: @samp{ultrasparc},
! 379: @samp{sparc64}
! 380:
! 381: @item
! 382: 80x86 family:
! 383: @samp{i386},
! 384: @samp{i486},
! 385: @samp{i586},
! 386: @samp{pentium},
! 387: @samp{pentiummmx},
! 388: @samp{pentiumpro},
! 389: @samp{pentium2},
! 390: @samp{pentium3},
! 391: @samp{k6},
! 392: @samp{k62},
! 393: @samp{k63},
! 394: @samp{athlon}
! 395:
! 396: @item
! 397: Other:
! 398: @samp{a29k},
! 399: @samp{arm},
! 400: @samp{clipper},
! 401: @samp{i960},
! 402: @samp{ns32k},
! 403: @samp{pyramid},
! 404: @samp{vax},
! 405: @samp{z8k}
! 406: @end itemize
1.1 maekawa 407:
1.1.1.2 ! maekawa 408: CPUs not listed use generic C code. If some of the assembly code causes
! 409: problems, the generic C code can be selected with CPU @samp{none}.
1.1 maekawa 410:
1.1.1.2 ! maekawa 411: @item @option{CC}, @option{CFLAGS}
1.1 maekawa 412:
1.1.1.2 ! maekawa 413: The C compiler used is chosen from among some likely candidates, with GCC
! 414: normally preferred if it's present. The usual @samp{CC=whatever} can be
! 415: passed to @samp{./configure} to choose something different.
! 416:
! 417: For some configurations specific compiler flags are set based on the target
! 418: CPU and compiler, for others @samp{CFLAGS="-whatever"} can be used to
! 419: set the best flags.
! 420:
! 421: If @samp{CC} is set then @samp{CFLAGS} must also be set. This applies even if
! 422: @samp{CC} is merely one of the choices GMP would make itself. This may change
! 423: in a future release.
! 424:
! 425: @item @option{--disable-alloca}
! 426: @cindex Stack overflow segfaults
! 427: @cindex @code{alloca}
! 428:
! 429: By default, GMP allocates temporary workspace using @code{alloca} if that
! 430: function is available, or @code{malloc} if not. If you're working with large
! 431: numbers and @code{alloca} overflows the available stack space, you can build
! 432: with @option{--disable-alloca} to use @code{malloc} instead. @code{malloc}
! 433: will probably be slightly slower than @code{alloca}.
! 434:
! 435: When not using @code{alloca}, it's actually the allocation function
! 436: selected with @code{mp_set_memory_functions} that's used, this being
! 437: @code{malloc} by default. @xref{Custom Allocation}.
! 438:
! 439: Depending on your system, the only indication of stack overflow might be a
! 440: segmentation violation. It might be possible to increase available stack
! 441: space with @command{limit}, @command{ulimit} or @code{setrlimit}, or under
! 442: DJGPP with @command{stubedit} or @code{_stklen}.
! 443:
! 444: @item @option{--enable-fft}
! 445:
! 446: By default multiplications are done using Karatsuba and 3-way Toom-Cook
! 447: algorithms, but a Fermat FFT can be enabled, for use on large to very large
! 448: operands. Currently the FFT is recommended only for knowledgeable users who
! 449: check the algorithm thresholds for their CPU.
! 450:
! 451: @item @option{--enable-mpbsd}
! 452:
! 453: The Berkeley MP compatibility library (@file{libmp.a}) and header file
! 454: (@file{mp.h}) are built and installed only if @option{--enable-mpbsd} is used.
! 455: @xref{BSD Compatible Functions}.
! 456:
! 457: @item @option{MPN_PATH}
! 458:
! 459: Various assembler versions of mpn subroutines are provided, and, for a given
! 460: CPU target, a search is made though a path to choose a version of each. For
! 461: example @samp{sparcv8} has path @samp{"sparc32/v8 sparc32 generic"}, which
! 462: means it looks first for v8 code, falls back on plain sparc32, and finally
! 463: falls back on generic C. Knowledgeable users with special requirements can
! 464: specify a path with @samp{MPN_PATH="dir list"}. This will normally be
! 465: unnecessary because all sensible paths should be available under one or other
! 466: CPU target.
! 467:
! 468: @item Demonstration Programs
! 469: @cindex Demonstration programs
! 470: @cindex Example programs
! 471:
! 472: The @file{demos} subdirectory has some sample programs using GMP. These
! 473: aren't built or installed, but there's a @file{Makefile} with rules for them.
! 474: For instance, @samp{make pexpr} and then @samp{./pexpr 68^975+10}.
! 475:
! 476: @item Documentation
! 477:
! 478: The document you're now reading is @file{gmp.texi}. The usual automake
! 479: targets are available to make @file{gmp.ps} and/or @file{gmp.dvi}. Some
! 480: supplementary notes can be found in the @file{doc} subdirectory.
! 481: @end table
1.1 maekawa 482:
483:
1.1.1.2 ! maekawa 484: @need 2000
! 485: @node ABI and ISA, Notes for Package Builds, Build Options, Installing GMP
! 486: @section ABI and ISA
! 487: @cindex ABI
! 488: @cindex ISA
! 489:
! 490: ABI (Application Binary Interface) refers to the calling conventions between
! 491: functions, meaning what registers are used and what sizes the various C data
! 492: types are. ISA (Instruction Set Architecture) refers to the instructions and
! 493: registers a CPU has available.
! 494:
! 495: Some 64-bit ISA CPUs have both a 64-bit ABI and a 32-bit ABI defined, the
! 496: latter for compatibility with older CPUs in the family. GMP chooses the best
! 497: ABI available for a given target system, and this generally gives
! 498: significantly greater speed.
! 499:
! 500: The burden is on application programs and cooperating libraries to ensure they
! 501: match the ABI chosen by GMP. Fortunately this presents a difficulty only on a
! 502: few systems, and if you have one of them then the performance gains are enough
! 503: to make it worth the trouble.
! 504:
! 505: Some of what's described in this section may change in future releases of GMP.
! 506:
! 507: @table @asis
! 508: @need 1000
! 509: @item HPPA 2.0
! 510:
! 511: CPU target @samp{hppa2.0} uses the hppa2.0n 32-bit ABI, but either a 32-bit or
! 512: 64-bit limb.
! 513:
! 514: A 64-bit limb is available on HP-UX 10 or up when using @command{c89}. No
! 515: @command{gcc} support is planned for 64-bit operations in this ABI.
! 516: Applications must be compiled with the same options as GMP, which means
1.1 maekawa 517:
1.1.1.2 ! maekawa 518: @example
! 519: c89 +DA2.0 +e -D_LONG_LONG_LIMB
! 520: @end example
1.1 maekawa 521:
1.1.1.2 ! maekawa 522: A 32-bit limb is used in other cases, and no special compiler options are
! 523: needed.
1.1 maekawa 524:
1.1.1.2 ! maekawa 525: CPU target @samp{hppa2.0w} uses the hppa2.0w 64-bit ABI, which is available on
! 526: HP-UX 11 or up when using @command{c89}. @command{gcc} support for this is in
! 527: progress. Applications must be compiled for the same ABI, which means
1.1 maekawa 528:
1.1.1.2 ! maekawa 529: @example
! 530: c89 +DD64
! 531: @end example
1.1 maekawa 532:
1.1.1.2 ! maekawa 533: @need 1000
! 534: @item MIPS 3 and 4 under IRIX 6
1.1 maekawa 535:
1.1.1.2 ! maekawa 536: Targets @samp{mips*-*-irix6*} use the n32 ABI and a 64-bit limb. Applications
! 537: must be compiled for the same ABI, which means either
1.1 maekawa 538:
1.1.1.2 ! maekawa 539: @example
! 540: gcc -mabi=n32
! 541: cc -n32
! 542: @end example
1.1 maekawa 543:
1.1.1.2 ! maekawa 544: @need 1000
! 545: @item PowerPC 64
1.1 maekawa 546:
1.1.1.2 ! maekawa 547: CPU target @samp{powerpc64} uses either the 32-bit ABI or the AIX 64-bit ABI.
! 548: The latter is used on targets @samp{powerpc64-*-aix*} and applications must be
! 549: compiled using either
1.1 maekawa 550:
1.1.1.2 ! maekawa 551: @example
! 552: gcc -maix64
! 553: xlc -q64
! 554: @end example
1.1 maekawa 555:
1.1.1.2 ! maekawa 556: On other systems the 32-bit ABI is used, but with 64-bit limbs provided by
! 557: @code{long long} in @command{gcc}. Applications must be compiled using
1.1 maekawa 558:
1.1.1.2 ! maekawa 559: @example
! 560: gcc -D_LONG_LONG_LIMB
! 561: @end example
! 562:
! 563: @need 1000
! 564: @item Sparc V9
1.1 maekawa 565:
1.1.1.2 ! maekawa 566: On a sparc v9 CPU, either the v8plus 32-bit ABI or v9 64-bit ABI is used.
! 567: Targets @samp{ultrasparc*-*-solaris2.[7-9]}, @samp{sparcv9-*-solaris2.[7-9]}
! 568: and @samp{sparc64-*-linux*} use the v9 ABI, if the compiler supports it.
! 569: Other targets use the v8plus ABI (but with as much of the v9 ISA as possible
! 570: in the circumstances). Note that Solaris prior to 2.7 doesn't save all
! 571: registers properly, and hence uses the v8plus ABI.
! 572:
! 573: For the v8plus ABI, applications can be compiled with either
1.1 maekawa 574:
575: @example
1.1.1.2 ! maekawa 576: gcc -mv8plus
! 577: cc -xarch=v8plus
1.1 maekawa 578: @end example
579:
1.1.1.2 ! maekawa 580: For the v9 ABI, applications must be compiled with either
1.1 maekawa 581:
1.1.1.2 ! maekawa 582: @example
! 583: gcc -m64 -mptr64 -Wa,-xarch=v9 -mcpu=v9
! 584: cc -xarch=v9
! 585: @end example
! 586:
! 587: Don't be confused by the names of these options, they're called @samp{arch}
! 588: but they effectively control the ABI.
! 589: @end table
! 590:
! 591:
! 592: @need 2000
! 593: @node Notes for Package Builds, Notes for Particular Systems, ABI and ISA, Installing GMP
! 594: @section Notes for Package Builds
! 595: @cindex Build notes for binary packaging
! 596: @cindex Packaged builds
! 597:
! 598: GMP should present no great difficulties for packaging in a binary
! 599: distribution.
! 600:
! 601: @cindex Libtool versioning
! 602: Libtool is used to build the library and @samp{-version-info} is set
! 603: appropriately, having started from @samp{3:0:0} in GMP 3.0. The GMP 3 series
! 604: will be upwardly binary compatible in each release, but may be adding
! 605: additional function interfaces. On systems where libtool versioning is not
! 606: fully checked by the loader, an auxiliary mechanism may be needed to express
! 607: that a dynamic linked application depends on a new enough minor version of
! 608: GMP.
! 609:
! 610: When building a package for a CPU family, care should be taken to use
! 611: @samp{--target} to choose the least common denominator among the CPUs which
! 612: might use the package. For example this might necessitate @samp{i386} for
! 613: x86s, or plain @samp{sparc} (meaning V7) for SPARCs.
! 614:
! 615: Users who care about speed will want GMP built for their exact CPU type, to
! 616: make use of the available optimizations. Providing a way to suitably rebuild
! 617: a package may be useful. This could be as simple as making it possible for a
! 618: user to omit @samp{--target} in a build so @samp{./config.guess} will detect
! 619: the CPU. But a way to manually specify a @samp{--target} will be wanted for
! 620: systems where @samp{./config.guess} is inexact.
! 621:
! 622:
! 623: @need 2000
! 624: @node Notes for Particular Systems, Known Build Problems, Notes for Package Builds, Installing GMP
! 625: @section Notes for Particular Systems
! 626: @cindex Build notes for particular systems
! 627: @table @asis
! 628:
! 629: @c This section is more or less meant for notes about performance or about
! 630: @c build problems that have been worked around but might leave a user
! 631: @c scratching their head. Fun with different ABIs on a system belongs in the
! 632: @c above section.
! 633:
! 634: @item AIX 4.3
! 635:
! 636: Targets @samp{*-*-aix4.[3-9]*} have shared libraries disabled since they seem
! 637: to fail on AIX 4.3.
! 638:
! 639: @item OpenBSD 2.6
! 640:
! 641: @command{m4} in this release of OpenBSD has a bug in @code{eval} that makes it
! 642: unsuitable for @file{.asm} file processing. @samp{./configure} will detect
! 643: the problem and either abort or choose another m4 in the @env{PATH}. The bug
! 644: is fixed in OpenBSD 2.7, so either upgrade or use GNU m4.
! 645:
! 646: @item Sparc V8
! 647:
! 648: Using CPU target @samp{sparcv8} or @samp{supersparc} on relevant systems will
! 649: give a significant performance increase over the V7 code.
! 650:
! 651: @item SunOS 4
! 652:
! 653: @command{/usr/bin/m4} lacks various features needed to process @file{.asm}
! 654: files, and instead @samp{./configure} will automatically use
! 655: @command{/usr/5bin/m4}, which we believe is always available (if not then use
! 656: GNU m4).
! 657:
! 658: @item x86 Pentium and PentiumPro
! 659:
! 660: The Intel Pentium P5 code is good for its intended P5, but quite slow when run
! 661: on Intel P6 class chips (PPro, P-II, P-III)@. @samp{i386} is a better choice
! 662: if you're making binaries that must run on both.
! 663:
! 664: @item x86 MMX and old GAS
! 665:
! 666: Old versions of GAS don't support MMX instructions, in particular version
! 667: 1.92.3 that comes with FreeBSD 2.2.8 doesn't (and unfortunately there's no
! 668: newer assembler for that system).
! 669:
! 670: If the target CPU has MMX code but the assembler doesn't support it, a warning
! 671: is given and non-MMX code is used instead. This will be an inferior build,
! 672: since the MMX code that's present is there because it's faster than the
! 673: corresponding plain integer code.
! 674:
! 675: @item x86 GCC 2.95.2 @samp{-march=pentiumpro}
! 676:
! 677: GCC 2.95.2 miscompiles @file{mpz/powm.c} when @samp{-march=pentiumpro} is
! 678: used, so that option is omitted from the @env{CFLAGS} chosen for relevant
! 679: CPUs. The problem is believed to be fixed in GCC 2.96.
! 680: @end table
! 681:
! 682:
! 683: @need 2000
! 684: @node Known Build Problems, , Notes for Particular Systems, Installing GMP
! 685: @section Known Build Problems
! 686: @cindex Build problems known
! 687:
! 688: @c This section is more or less meant for known build problems that are not
! 689: @c otherwise worked around and require some sort of manual intervention.
! 690:
! 691: You might find more up-to-date information at @uref{http://www.swox.com/gmp/}.
! 692:
! 693: @table @asis
! 694:
! 695: @item Generic C on a 64-bit system
! 696:
! 697: When making a generic C build using @samp{--target=none} on a 64-bit system
! 698: (meaning where @code{unsigned long} is 64 bits), @code{BITS_PER_MP_LIMB},
! 699: @code{BITS_PER_LONGINT} and @code{BYTES_PER_MP_LIMB} in
! 700: @file{mpn/generic/gmp-mparam.h} need to be changed to 64 and 8. This will
! 701: hopefully be automated in a future version of GMP.
! 702:
! 703: @item NeXT prior to 3.3
! 704:
! 705: The system compiler on old versions of NeXT was a massacred and old GCC, even
! 706: if it called itself @file{cc}. This compiler cannot be used to build GMP, you
! 707: need to get a real GCC, and install that before you compile GMP. (NeXT may
! 708: have fixed this in release 3.3 of their system.)
! 709:
! 710: @item POWER and PowerPC
! 711:
! 712: Bugs in GCC 2.7.2 (and 2.6.3) mean it can't be used to compile GMP on POWER or
! 713: PowerPC. If you want to use GCC for these machines, get GCC 2.7.2.1 (or
! 714: later).
! 715:
! 716: @item Sequent Symmetry
! 717:
! 718: Use the GNU assembler instead of the system assembler, since the latter has
! 719: serious bugs.
! 720:
! 721: @item Stripped Libraries
! 722: @cindex Stripped libraries
! 723:
! 724: GNU binutils @samp{strip} should not be used on the static libraries
! 725: @file{libgmp.a} and @file{libmp.a}, neither directly nor via @samp{make
! 726: install-strip}. It can be used on the shared libraries @file{libgmp.so} and
! 727: @file{libmp.so} though.
! 728:
! 729: Currently (binutils 2.10.0), @samp{strip} extracts archives into a single
! 730: directory, but GMP contains multiple object files of the same name (eg. three
! 731: versions of @file{init.o}), and they overwrite each other, leaving only the
! 732: one that happens to be last.
! 733:
! 734: If stripped static libraries are wanted, the suggested workaround is to build
! 735: normally, strip the separate object files, and do another @samp{make all} to
! 736: rebuild. Alternately @samp{CFLAGS} with @samp{-g} omitted can always be used
! 737: if it's just debugging which is unwanted.
! 738:
! 739: @item SunOS 4 Native Tools
! 740:
! 741: The setting for @code{GSYM_PREFIX} in @file{config.m4} may be incorrectly
! 742: determined when using the native @command{grep}, leading at link-time to
! 743: undefined symbols like @code{___gmpn_add_n}. To fix this, after running
! 744: @samp{./configure}, change the relevant line in @file{config.m4} to
! 745: @samp{define(<GSYM_PREFIX>, <_>)}.
! 746:
! 747: The @command{ranlib} command will need to be run manually when building a
! 748: static library with the native @command{ar}. After @samp{make}, run
! 749: @samp{ranlib .libs/libgmp.a}, and when using @option{--enable-mpbsd} run
! 750: @samp{ranlib .libs/libmp.a} too.
! 751:
! 752: @item VAX running Ultrix
! 753:
! 754: You need to build and install the GNU assembler before you compile GMP. The VAX
! 755: assembly in GMP uses an instruction (@code{jsobgtr}) that cannot be assembled by
! 756: the Ultrix assembler.
! 757: @end table
! 758:
! 759:
! 760:
! 761: @node GMP Basics, Reporting Bugs, Installing GMP, Top
! 762: @comment node-name, next, previous, up
! 763: @chapter GMP Basics
! 764: @cindex Basics
1.1 maekawa 765:
766: @cindex @file{gmp.h}
1.1.1.2 ! maekawa 767: All declarations needed to use GMP are collected in the include file
1.1 maekawa 768: @file{gmp.h}. It is designed to work with both C and C++ compilers.
769:
1.1.1.2 ! maekawa 770: @strong{Using functions, macros, data types, etc.@: not documented in this
! 771: manual is strongly discouraged. If you do so your application is guaranteed
! 772: to be incompatible with future versions of GMP.}
! 773:
! 774: @menu
! 775: * Nomenclature and Types:: Which data types are there?
! 776: * Function Classes:: How the functions are organized.
! 777: * GMP Variable Conventions:: Some rules and hints about variables.
! 778: * GMP and Reentrancy:: What about reentrancy?
! 779: * Useful Macros and Constants:: Convenient helpers.
! 780: * Compatibility with older versions:: Compatibility issues.
! 781: * Getting the Latest Version of GMP:: How to get the software.
! 782: @end menu
1.1 maekawa 783:
1.1.1.2 ! maekawa 784: @node Nomenclature and Types, Function Classes, GMP Basics, GMP Basics
1.1 maekawa 785: @section Nomenclature and Types
1.1.1.2 ! maekawa 786: @cindex Nomenclature
! 787: @cindex Types
1.1 maekawa 788:
789: @cindex Integer
790: @tindex @code{mpz_t}
791: @noindent
792: In this manual, @dfn{integer} usually means a multiple precision integer, as
1.1.1.2 ! maekawa 793: defined by the GMP library. The C data type for such integers is @code{mpz_t}.
1.1 maekawa 794: Here are some examples of how to declare such integers:
795:
796: @example
797: mpz_t sum;
798:
799: struct foo @{ mpz_t x, y; @};
800:
801: mpz_t vec[20];
802: @end example
803:
804: @cindex Rational number
805: @tindex @code{mpq_t}
806: @noindent
807: @dfn{Rational number} means a multiple precision fraction. The C data type
808: for these fractions is @code{mpq_t}. For example:
809:
810: @example
811: mpq_t quotient;
812: @end example
813:
814: @cindex Floating-point number
815: @tindex @code{mpf_t}
816: @noindent
817: @dfn{Floating point number} or @dfn{Float} for short, is an arbitrary precision
1.1.1.2 ! maekawa 818: mantissa with a limited precision exponent. The C data type for such objects
1.1 maekawa 819: is @code{mpf_t}.
820:
821: @cindex Limb
822: @tindex @code{mp_limb_t}
823: @noindent
824: A @dfn{limb} means the part of a multi-precision number that fits in a single
825: word. (We chose this word because a limb of the human body is analogous to a
826: digit, only larger, and containing several digits.) Normally a limb contains
827: 32 or 64 bits. The C data type for a limb is @code{mp_limb_t}.
828:
829:
1.1.1.2 ! maekawa 830: @node Function Classes, GMP Variable Conventions, Nomenclature and Types, GMP Basics
1.1 maekawa 831: @section Function Classes
1.1.1.2 ! maekawa 832: @cindex Function classes
1.1 maekawa 833:
1.1.1.2 ! maekawa 834: There are six classes of functions in the GMP library:
1.1 maekawa 835:
836: @enumerate
837: @item
838: Functions for signed integer arithmetic, with names beginning with
839: @code{mpz_}. The associated type is @code{mpz_t}. There are about 100
840: functions in this class.
841:
842: @item
843: Functions for rational number arithmetic, with names beginning with
844: @code{mpq_}. The associated type is @code{mpq_t}. There are about 20
845: functions in this class, but the functions in the previous class can be used
846: for performing arithmetic on the numerator and denominator separately.
847:
848: @item
849: Functions for floating-point arithmetic, with names beginning with
850: @code{mpf_}. The associated type is @code{mpf_t}. There are about 50
851: functions is this class.
852:
853: @item
1.1.1.2 ! maekawa 854: Functions compatible with Berkeley GMP, such as @code{itom}, @code{madd}, and
1.1 maekawa 855: @code{mult}. The associated type is @code{MINT}.
856:
857: @item
858: Fast low-level functions that operate on natural numbers. These are used by
859: the functions in the preceding groups, and you can also call them directly
860: from very time-critical user programs. These functions' names begin with
861: @code{mpn_}. There are about 30 (hard-to-use) functions in this class.
862:
863: The associated type is array of @code{mp_limb_t}.
864:
865: @item
1.1.1.2 ! maekawa 866: Miscellaneous functions. Functions for setting up custom allocation and
! 867: functions for generating random numbers.
1.1 maekawa 868: @end enumerate
869:
870:
1.1.1.2 ! maekawa 871: @node GMP Variable Conventions, GMP and Reentrancy, Function Classes, GMP Basics
! 872: @section GMP Variable Conventions
! 873: @cindex Variable conventions
! 874: @cindex Parameter conventions
! 875: @cindex Conventions for variables
1.1 maekawa 876:
1.1.1.2 ! maekawa 877: As a general rule, all GMP functions expect output arguments before input
1.1 maekawa 878: arguments. This notation is based on an analogy with the assignment operator.
879: (The BSD MP compatibility functions disobey this rule, having the output
880: argument(s) last.)
881:
1.1.1.2 ! maekawa 882: GMP lets you use the same variable for both input and output in one call. For
! 883: example, the main function for integer multiplication, @code{mpz_mul}, can be
! 884: used to square @code{x} and put the result back in @code{x} with
! 885:
! 886: @example
! 887: mpz_mul (x, x, x);
! 888: @end example
1.1 maekawa 889:
1.1.1.2 ! maekawa 890: Before you can assign to a GMP variable, you need to initialize it by calling
1.1 maekawa 891: one of the special initialization functions. When you're done with a
892: variable, you need to clear it out, using one of the functions for that
893: purpose. Which function to use depends on the type of variable. See the
894: chapters on integer functions, rational number functions, and floating-point
895: functions for details.
896:
897: A variable should only be initialized once, or at least cleared out between
898: each initialization. After a variable has been initialized, it may be
899: assigned to any number of times.
900:
1.1.1.2 ! maekawa 901: For efficiency reasons, avoid initializing and clearing out a GMP variable in
! 902: a loop. Instead, initialize it before entering the loop, and clear it out
! 903: after the loop has exited.
! 904:
! 905: GMP variables are small, containing only a couple of sizes, and pointers to
! 906: allocated data. Once you have initialized a GMP variable, you don't need to
! 907: worry about space allocation. All functions in GMP automatically allocate
! 908: additional space when a variable does not already have enough. They do not,
! 909: however, reduce the space when a smaller value is stored. Most of the time
! 910: this policy is best, since it avoids frequent re-allocation.
! 911:
! 912: When a variable of type @code{mpz_t} is used as a function parameter, it's
! 913: effectively a call-by-reference, meaning anything the function does to it will
! 914: be be done to the original in the caller. When a function is going to return
! 915: an @code{mpz_t} result, it should provide a separate parameter or parameters
! 916: that it sets, like the GMP library functions do. A @code{return} of an
! 917: @code{mpz_t} doesn't return the object, only a pointer to it, and this is
! 918: almost certainly not what you want. All this applies to @code{mpq_t} and
! 919: @code{mpf_t} too.
! 920:
! 921: Here's an example function accepting an @code{mpz_t} parameter, doing a
! 922: certain calculation, and returning a result.
! 923:
! 924: @example
! 925: void
! 926: myfunction (mpz_t result, mpz_t param, unsigned long n)
! 927: @{
! 928: unsigned long i;
! 929:
! 930: mpz_mul_ui (result, param, n);
! 931: for (i = 1; i < n; i++)
! 932: mpz_add_ui (result, result, i*7);
! 933: @}
! 934:
! 935: int
! 936: main (void)
! 937: @{
! 938: mpz_t r, n;
! 939: mpz_init (r);
! 940: mpz_init_set_str (n, "123456", 0);
! 941:
! 942: myfunction (r, n, 20L);
! 943: mpz_out_str (stdout, 10, r); printf ("\n");
! 944:
! 945: return 0;
! 946: @}
! 947: @end example
! 948:
! 949: This example will work if @code{result} and @code{param} are the same
! 950: variable, just like the library functions. But sometimes this is tricky to
! 951: arrange, and an application might not want to bother for its own subroutines.
! 952:
! 953: @code{mpz_t} is actually implemented as a one-element array of a certain
! 954: structure type. This is why using it to declare a variable gives an object
! 955: with the fields GMP needs, but then using it as a parameter passes a pointer
! 956: to the object. Note that the actual contents of an @code{mpz_t} are for
! 957: internal use only and you should not access them directly if you want your
! 958: code to be compatible with future GMP releases.
! 959:
! 960:
! 961: @node GMP and Reentrancy, Useful Macros and Constants, GMP Variable Conventions, GMP Basics
! 962: @section GMP and Reentrancy
! 963: @cindex Reentrancy
! 964: @cindex Thread safety
! 965: @cindex Multi-threading
! 966:
! 967: The GMP code is reentrant and thread-safe, with some exceptions:
! 968:
! 969: @itemize @bullet
! 970: @item
! 971: The function @code{mpf_set_default_prec} saves the selected precision in
! 972: a global variable.
! 973:
! 974: @item
! 975: The function @code{mp_set_memory_functions} uses several global
! 976: variables for storing the selected memory allocation functions.
! 977:
! 978: @item
! 979: If the memory allocation functions set by a call to
! 980: @code{mp_set_memory_functions} (or @code{malloc} and friends by default) are
! 981: not reentrant, GMP will not be reentrant either.
! 982:
! 983: @item
! 984: The old random number functions (@code{mpz_random}, etc) use a random number
! 985: generator from the C library, usually @code{mrand48} or @code{random}. These
! 986: routines are not reentrant, since they rely on global state.
! 987: (However the newer random number functions that accept a
! 988: @code{gmp_randstate_t} parameter are reentrant.)
! 989: @end itemize
1.1 maekawa 990:
991:
1.1.1.2 ! maekawa 992: @need 2000
! 993: @node Useful Macros and Constants, Compatibility with older versions, GMP and Reentrancy, GMP Basics
1.1 maekawa 994: @section Useful Macros and Constants
1.1.1.2 ! maekawa 995: @cindex Useful macros and constants
! 996: @cindex Constants
1.1 maekawa 997:
998: @deftypevr {Global Constant} {const int} mp_bits_per_limb
1.1.1.2 ! maekawa 999: @cindex Bits per limb
! 1000: @cindex Limb size
1.1 maekawa 1001: The number of bits per limb.
1002: @end deftypevr
1003:
1004: @defmac __GNU_MP_VERSION
1005: @defmacx __GNU_MP_VERSION_MINOR
1.1.1.2 ! maekawa 1006: @defmacx __GNU_MP_VERSION_PATCHLEVEL
! 1007: @cindex Version number
! 1008: @cindex GMP version number
! 1009: The major and minor GMP version, and patch level, respectively, as integers.
! 1010: For GMP i.j, these numbers will be i, j, and 0, respectively.
! 1011: For GMP i.j.k, these numbers will be i, j, and k, respectively.
1.1 maekawa 1012: @end defmac
1013:
1014:
1.1.1.2 ! maekawa 1015: @node Compatibility with older versions, Getting the Latest Version of GMP, Useful Macros and Constants, GMP Basics
! 1016: @section Compatibility with older versions
! 1017: @cindex Compatibility with older versions
! 1018: @cindex Upward compatibility
! 1019:
! 1020: This version of GMP is upwardly binary compatible with versions 3.0 and 3.0.1,
! 1021: and upwardly compatible at the source level with versions 2.0, 2.0.1, and
! 1022: 2.0.2, with the following exceptions.
1.1 maekawa 1023:
1.1.1.2 ! maekawa 1024: @itemize @bullet
! 1025: @item
! 1026: @code{mpn_gcd} had its source arguments swapped as of GMP 3.0 for consistency
! 1027: with other @code{mpn} functions.
1.1 maekawa 1028:
1.1.1.2 ! maekawa 1029: @item
! 1030: @code{mpf_get_prec} counted precision slightly differently in GMP 3.0 and
! 1031: 3.0.1, but in 3.1 has reverted to the 2.0.x style.
1.1 maekawa 1032:
1.1.1.2 ! maekawa 1033: @end itemize
1.1 maekawa 1034:
1.1.1.2 ! maekawa 1035: There are a number of compatibility issues between GMP 1 and GMP 2 that of
! 1036: course also apply when porting applications from GMP 1 to GMP 3. Please
! 1037: see the GMP 2 manual for details.
! 1038:
! 1039: @c @enumerate
! 1040: @c @item Integer division functions round the result differently. The obsolete
! 1041: @c functions (@code{mpz_div}, @code{mpz_divmod}, @code{mpz_mdiv},
! 1042: @c @code{mpz_mdivmod}, etc) now all use floor rounding (i.e., they round the
! 1043: @c quotient towards
! 1044: @c @ifinfo
! 1045: @c @minus{}infinity).
! 1046: @c @end ifinfo
! 1047: @c @iftex
! 1048: @c @tex
! 1049: @c $-\infty$).
! 1050: @c @end tex
! 1051: @c @end iftex
! 1052: @c There are a lot of functions for integer division, giving the user better
! 1053: @c control over the rounding.
! 1054:
! 1055: @c @item The function @code{mpz_mod} now compute the true @strong{mod} function.
! 1056:
! 1057: @c @item The functions @code{mpz_powm} and @code{mpz_powm_ui} now use
! 1058: @c @strong{mod} for reduction.
! 1059:
! 1060: @c @item The assignment functions for rational numbers do no longer canonicalize
! 1061: @c their results. In the case a non-canonical result could arise from an
! 1062: @c assignment, the user need to insert an explicit call to
! 1063: @c @code{mpq_canonicalize}. This change was made for efficiency.
! 1064:
! 1065: @c @item Output generated by @code{mpz_out_raw} in this release cannot be read
! 1066: @c by @code{mpz_inp_raw} in previous releases. This change was made for making
! 1067: @c the file format truly portable between machines with different word sizes.
! 1068:
! 1069: @c @item Several @code{mpn} functions have changed. But they were intentionally
! 1070: @c undocumented in previous releases.
! 1071:
! 1072: @c @item The functions @code{mpz_cmp_ui}, @code{mpz_cmp_si}, and @code{mpq_cmp_ui}
! 1073: @c are now implemented as macros, and thereby sometimes evaluate their
! 1074: @c arguments multiple times.
! 1075:
! 1076: @c @item The functions @code{mpz_pow_ui} and @code{mpz_ui_pow_ui} now yield 1
! 1077: @c for 0^0. (In version 1, they yielded 0.)
! 1078:
! 1079: @c @end enumerate
! 1080:
! 1081:
! 1082: @node Getting the Latest Version of GMP, , Compatibility with older versions, GMP Basics
! 1083: @section Getting the Latest Version of GMP
! 1084: @cindex Latest version of GMP
! 1085: @cindex Anonymous FTP of latest version
! 1086: @cindex FTP of latest version
! 1087:
! 1088: The latest version of the GMP library is available at
! 1089: @uref{ftp://ftp.gnu.org/pub/gnu/gmp}. Many sites around the world mirror
! 1090: @samp{ftp.gnu.org}; please use a mirror site near you, see
! 1091: @uref{http://www.gnu.org/order/ftp.html}.
1.1 maekawa 1092:
1093:
1.1.1.2 ! maekawa 1094: @node Reporting Bugs, Integer Functions, GMP Basics, Top
1.1 maekawa 1095: @comment node-name, next, previous, up
1096: @chapter Reporting Bugs
1097: @cindex Reporting bugs
1.1.1.2 ! maekawa 1098: @cindex Bug reporting
! 1099:
! 1100: If you think you have found a bug in the GMP library, please investigate it
! 1101: and report it. We have made this library available to you, and it is not too
! 1102: much to ask you to report the bugs you find. Before you report a bug, you may
! 1103: want to check @uref{http://www.swox.com/gmp/} for patches for this release.
! 1104:
! 1105: Please include the following in any report,
! 1106:
! 1107: @itemize @bullet
! 1108: @item
! 1109: The GMP version number, and if pre-packaged or patched then say so.
! 1110:
! 1111: @item
! 1112: A test program that makes it possible for us to reproduce the bug. Include
! 1113: instructions on how to run the program.
1.1 maekawa 1114:
1.1.1.2 ! maekawa 1115: @item
! 1116: A description of what is wrong. If the results are incorrect, in what way.
! 1117: If you get a crash, say so.
! 1118:
! 1119: @item
! 1120: If you get a crash, include a stack backtrace from the debugger if it's
! 1121: informative (@samp{where} in @command{gdb}, or @samp{$C} in @command{adb}).
! 1122:
! 1123: @item
! 1124: @strong{Please do not send core dumps, executables or @command{strace}s.}
! 1125:
! 1126: @item
! 1127: The configuration options you used when building GMP, if any.
! 1128:
! 1129: @item
! 1130: The name of the compiler and its version. For @command{gcc}, get the version
! 1131: with @samp{gcc -v}, otherwise perhaps @samp{what `which cc`}, or similar.
! 1132:
! 1133: @item
! 1134: The output from running @samp{uname -a}.
1.1 maekawa 1135:
1.1.1.2 ! maekawa 1136: @item
! 1137: The output from running @samp{./config.guess}.
1.1 maekawa 1138:
1.1.1.2 ! maekawa 1139: @item
! 1140: If the bug is related to @samp{configure}, then the contents of
! 1141: @file{config.log}.
1.1 maekawa 1142:
1.1.1.2 ! maekawa 1143: @item
! 1144: If the bug is related to an @file{asm} file not assembling, then the contents
! 1145: of @file{config.m4}.
! 1146: @end itemize
1.1 maekawa 1147:
1148: It is not uncommon that an observed problem is actually due to a bug in the
1.1.1.2 ! maekawa 1149: compiler; the GMP code tends to explore interesting corners in compilers.
1.1 maekawa 1150:
1.1.1.2 ! maekawa 1151: If your bug report is good, we will do our best to help you get a corrected
1.1 maekawa 1152: version of the library; if the bug report is poor, we won't do anything about
1.1.1.2 ! maekawa 1153: it (except maybe ask you to send a better report).
1.1 maekawa 1154:
1.1.1.2 ! maekawa 1155: Send your report to: @email{bug-gmp@@gnu.org}.
1.1 maekawa 1156:
1157: If you think something in this manual is unclear, or downright incorrect, or if
1158: the language needs to be improved, please send a note to the same address.
1159:
1160:
1161: @node Integer Functions, Rational Number Functions, Reporting Bugs, Top
1162: @comment node-name, next, previous, up
1163: @chapter Integer Functions
1164: @cindex Integer functions
1165:
1.1.1.2 ! maekawa 1166: This chapter describes the GMP functions for performing integer arithmetic.
1.1 maekawa 1167: These functions start with the prefix @code{mpz_}.
1168:
1.1.1.2 ! maekawa 1169: GMP integers are stored in objects of type @code{mpz_t}.
1.1 maekawa 1170:
1171: @menu
1.1.1.2 ! maekawa 1172: * Initializing Integers::
! 1173: * Assigning Integers::
! 1174: * Simultaneous Integer Init & Assign::
! 1175: * Converting Integers::
! 1176: * Integer Arithmetic::
! 1177: * Integer Division::
! 1178: * Integer Exponentiation::
! 1179: * Integer Roots::
! 1180: * Number Theoretic Functions::
! 1181: * Integer Comparisons::
! 1182: * Integer Logic and Bit Fiddling::
! 1183: * I/O of Integers::
! 1184: * Integer Random Numbers::
! 1185: * Miscellaneous Integer Functions::
1.1 maekawa 1186: @end menu
1187:
1.1.1.2 ! maekawa 1188: @node Initializing Integers, Assigning Integers, Integer Functions, Integer Functions
1.1 maekawa 1189: @comment node-name, next, previous, up
1.1.1.2 ! maekawa 1190: @section Initialization Functions
! 1191: @cindex Integer initialization functions
! 1192: @cindex Initialization functions
1.1 maekawa 1193:
1194: The functions for integer arithmetic assume that all integer objects are
1195: initialized. You do that by calling the function @code{mpz_init}.
1196:
1197: @deftypefun void mpz_init (mpz_t @var{integer})
1198: Initialize @var{integer} with limb space and set the initial numeric value to
1199: 0. Each variable should normally only be initialized once, or at least cleared
1200: out (using @code{mpz_clear}) between each initialization.
1201: @end deftypefun
1202:
1203: Here is an example of using @code{mpz_init}:
1204:
1205: @example
1206: @{
1207: mpz_t integ;
1208: mpz_init (integ);
1209: @dots{}
1210: mpz_add (integ, @dots{});
1211: @dots{}
1212: mpz_sub (integ, @dots{});
1213:
1214: /* Unless the program is about to exit, do ... */
1215: mpz_clear (integ);
1216: @}
1217: @end example
1218:
1219: @noindent
1220: As you can see, you can store new values any number of times, once an
1221: object is initialized.
1222:
1223: @deftypefun void mpz_clear (mpz_t @var{integer})
1224: Free the limb space occupied by @var{integer}. Make sure to call this
1225: function for all @code{mpz_t} variables when you are done with them.
1226: @end deftypefun
1227:
1228: @deftypefun {void *} _mpz_realloc (mpz_t @var{integer}, mp_size_t @var{new_alloc})
1229: Change the limb space allocation to @var{new_alloc} limbs. This function is
1230: not normally called from user code, but it can be used to give memory back to
1231: the heap, or to increase the space of a variable to avoid repeated automatic
1232: re-allocation.
1233: @end deftypefun
1234:
1235: @deftypefun void mpz_array_init (mpz_t @var{integer_array}[], size_t @var{array_size}, mp_size_t @var{fixed_num_bits})
1236: Allocate @strong{fixed} limb space for all @var{array_size} integers in
1237: @var{integer_array}. The fixed allocation for each integer in the array is
1238: enough to store @var{fixed_num_bits}. If the fixed space will be insufficient
1239: for storing the result of a subsequent calculation, the result is
1240: unpredictable.
1241:
1242: This function is useful for decreasing the working set for some algorithms
1243: that use large integer arrays.
1244:
1245: There is no way to de-allocate the storage allocated by this function.
1246: Don't call @code{mpz_clear}!
1247: @end deftypefun
1248:
1249:
1250: @node Assigning Integers, Simultaneous Integer Init & Assign, Initializing Integers, Integer Functions
1251: @comment node-name, next, previous, up
1.1.1.2 ! maekawa 1252: @section Assignment Functions
1.1 maekawa 1253: @cindex Integer assignment functions
1.1.1.2 ! maekawa 1254: @cindex Assignment functions
1.1 maekawa 1255:
1256: These functions assign new values to already initialized integers
1257: (@pxref{Initializing Integers}).
1258:
1259: @deftypefun void mpz_set (mpz_t @var{rop}, mpz_t @var{op})
1260: @deftypefunx void mpz_set_ui (mpz_t @var{rop}, unsigned long int @var{op})
1261: @deftypefunx void mpz_set_si (mpz_t @var{rop}, signed long int @var{op})
1262: @deftypefunx void mpz_set_d (mpz_t @var{rop}, double @var{op})
1263: @deftypefunx void mpz_set_q (mpz_t @var{rop}, mpq_t @var{op})
1264: @deftypefunx void mpz_set_f (mpz_t @var{rop}, mpf_t @var{op})
1265: Set the value of @var{rop} from @var{op}.
1266: @end deftypefun
1267:
1268: @deftypefun int mpz_set_str (mpz_t @var{rop}, char *@var{str}, int @var{base})
1269: Set the value of @var{rop} from @var{str}, a '\0'-terminated C string in base
1270: @var{base}. White space is allowed in the string, and is simply ignored. The
1271: base may vary from 2 to 36. If @var{base} is 0, the actual base is determined
1272: from the leading characters: if the first two characters are `0x' or `0X',
1273: hexadecimal is assumed, otherwise if the first character is `0', octal is
1274: assumed, otherwise decimal is assumed.
1275:
1276: This function returns 0 if the entire string up to the '\0' is a valid
1277: number in base @var{base}. Otherwise it returns @minus{}1.
1.1.1.2 ! maekawa 1278:
! 1279: [It turns out that it is not entirely true that this function ignores
! 1280: white-space. It does ignore it between digits, but not after a minus sign
! 1281: or within or after "0x". We are considering changing the definition of
! 1282: this function, making it fail when there is any white-space in the input,
! 1283: since that makes a lot of sense. Please tell us your opinion about this
! 1284: change. Do you really want it to accept "3 14" as meaning 314 as it does
! 1285: now?]
! 1286: @end deftypefun
! 1287:
! 1288: @deftypefun void mpz_swap (mpz_t @var{rop1}, mpz_t @var{rop2})
! 1289: Swap the values @var{rop1} and @var{rop2} efficiently.
1.1 maekawa 1290: @end deftypefun
1291:
1292:
1293: @node Simultaneous Integer Init & Assign, Converting Integers, Assigning Integers, Integer Functions
1294: @comment node-name, next, previous, up
1.1.1.2 ! maekawa 1295: @section Combined Initialization and Assignment Functions
1.1 maekawa 1296: @cindex Initialization and assignment functions
1.1.1.2 ! maekawa 1297: @cindex Integer init and assign
1.1 maekawa 1298:
1.1.1.2 ! maekawa 1299: For convenience, GMP provides a parallel series of initialize-and-set functions
1.1 maekawa 1300: which initialize the output and then store the value there. These functions'
1301: names have the form @code{mpz_init_set@dots{}}
1302:
1303: Here is an example of using one:
1304:
1305: @example
1306: @{
1307: mpz_t pie;
1308: mpz_init_set_str (pie, "3141592653589793238462643383279502884", 10);
1309: @dots{}
1310: mpz_sub (pie, @dots{});
1311: @dots{}
1312: mpz_clear (pie);
1313: @}
1314: @end example
1315:
1316: @noindent
1317: Once the integer has been initialized by any of the @code{mpz_init_set@dots{}}
1318: functions, it can be used as the source or destination operand for the ordinary
1319: integer functions. Don't use an initialize-and-set function on a variable
1320: already initialized!
1321:
1322: @deftypefun void mpz_init_set (mpz_t @var{rop}, mpz_t @var{op})
1323: @deftypefunx void mpz_init_set_ui (mpz_t @var{rop}, unsigned long int @var{op})
1324: @deftypefunx void mpz_init_set_si (mpz_t @var{rop}, signed long int @var{op})
1325: @deftypefunx void mpz_init_set_d (mpz_t @var{rop}, double @var{op})
1326: Initialize @var{rop} with limb space and set the initial numeric value from
1327: @var{op}.
1328: @end deftypefun
1329:
1330: @deftypefun int mpz_init_set_str (mpz_t @var{rop}, char *@var{str}, int @var{base})
1331: Initialize @var{rop} and set its value like @code{mpz_set_str} (see its
1332: documentation above for details).
1333:
1334: If the string is a correct base @var{base} number, the function returns 0;
1335: if an error occurs it returns @minus{}1. @var{rop} is initialized even if
1336: an error occurs. (I.e., you have to call @code{mpz_clear} for it.)
1337: @end deftypefun
1338:
1339:
1.1.1.2 ! maekawa 1340: @node Converting Integers, Integer Arithmetic, Simultaneous Integer Init & Assign, Integer Functions
1.1 maekawa 1341: @comment node-name, next, previous, up
1342: @section Conversion Functions
1343: @cindex Integer conversion functions
1344: @cindex Conversion functions
1345:
1.1.1.2 ! maekawa 1346: This section describes functions for converting GMP integers to standard C
! 1347: types. Functions for converting @emph{to} GMP integers are described in
! 1348: @ref{Assigning Integers} and @ref{I/O of Integers}.
! 1349:
! 1350: @deftypefun mp_limb_t mpz_getlimbn (mpz_t @var{op}, mp_size_t @var{n})
! 1351: Return limb #@var{n} from @var{op}. This function allows for very efficient
! 1352: decomposition of a number in its limbs.
! 1353:
! 1354: The function @code{mpz_size} can be used to determine the useful range for
! 1355: @var{n}.
! 1356: @end deftypefun
1.1 maekawa 1357:
1358: @deftypefun {unsigned long int} mpz_get_ui (mpz_t @var{op})
1.1.1.2 ! maekawa 1359: Return the least significant part from @var{op}. This function combined with
! 1360: @* @code{mpz_tdiv_q_2exp(@dots{}, @var{op}, CHAR_BIT*sizeof(unsigned long
! 1361: int))} can be used to decompose an integer into unsigned longs.
1.1 maekawa 1362: @end deftypefun
1363:
1364: @deftypefun {signed long int} mpz_get_si (mpz_t @var{op})
1365: If @var{op} fits into a @code{signed long int} return the value of @var{op}.
1366: Otherwise return the least significant part of @var{op}, with the same sign
1367: as @var{op}.
1368:
1369: If @var{op} is too large to fit in a @code{signed long int}, the returned
1.1.1.2 ! maekawa 1370: result is probably not very useful. To find out if the value will fit, use
! 1371: the function @code{mpz_fits_slong_p}.
1.1 maekawa 1372: @end deftypefun
1373:
1374: @deftypefun double mpz_get_d (mpz_t @var{op})
1375: Convert @var{op} to a double.
1376: @end deftypefun
1377:
1378: @deftypefun {char *} mpz_get_str (char *@var{str}, int @var{base}, mpz_t @var{op})
1379: Convert @var{op} to a string of digits in base @var{base}. The base may vary
1380: from 2 to 36.
1381:
1.1.1.2 ! maekawa 1382: If @var{str} is @code{NULL}, space for the result string is allocated using the
! 1383: default allocation function.
1.1 maekawa 1384:
1.1.1.2 ! maekawa 1385: If @var{str} is not @code{NULL}, it should point to a block of storage enough large
1.1 maekawa 1386: for the result. To find out the right amount of space to provide for
1387: @var{str}, use @code{mpz_sizeinbase (@var{op}, @var{base}) + 2}. The two
1388: extra bytes are for a possible minus sign, and for the terminating null
1389: character.
1.1.1.2 ! maekawa 1390:
! 1391: A pointer to the result string is returned. This pointer will will either
! 1392: equal @var{str}, or if that is @code{NULL}, will point to the allocated storage.
1.1 maekawa 1393: @end deftypefun
1394:
1395:
1.1.1.2 ! maekawa 1396: @need 2000
! 1397: @node Integer Arithmetic, Integer Division, Converting Integers, Integer Functions
1.1 maekawa 1398: @comment node-name, next, previous, up
1399: @section Arithmetic Functions
1400: @cindex Integer arithmetic functions
1401: @cindex Arithmetic functions
1402:
1403: @deftypefun void mpz_add (mpz_t @var{rop}, mpz_t @var{op1}, mpz_t @var{op2})
1404: @deftypefunx void mpz_add_ui (mpz_t @var{rop}, mpz_t @var{op1}, unsigned long int @var{op2})
1.1.1.2 ! maekawa 1405: @ifnottex
1.1 maekawa 1406: Set @var{rop} to @var{op1} + @var{op2}.
1.1.1.2 ! maekawa 1407: @end ifnottex
1.1 maekawa 1408: @tex
1409: Set @var{rop} to $@var{op1} + @var{op2}$.
1410: @end tex
1411: @end deftypefun
1412:
1413: @deftypefun void mpz_sub (mpz_t @var{rop}, mpz_t @var{op1}, mpz_t @var{op2})
1414: @deftypefunx void mpz_sub_ui (mpz_t @var{rop}, mpz_t @var{op1}, unsigned long int @var{op2})
1415: Set @var{rop} to @var{op1} @minus{} @var{op2}.
1416: @end deftypefun
1417:
1418: @deftypefun void mpz_mul (mpz_t @var{rop}, mpz_t @var{op1}, mpz_t @var{op2})
1.1.1.2 ! maekawa 1419: @deftypefunx void mpz_mul_si (mpz_t @var{rop}, mpz_t @var{op1}, long int @var{op2})
1.1 maekawa 1420: @deftypefunx void mpz_mul_ui (mpz_t @var{rop}, mpz_t @var{op1}, unsigned long int @var{op2})
1.1.1.2 ! maekawa 1421: @ifnottex
1.1 maekawa 1422: Set @var{rop} to @var{op1} times @var{op2}.
1.1.1.2 ! maekawa 1423: @end ifnottex
1.1 maekawa 1424: @tex
1425: Set @var{rop} to $@var{op1} \times @var{op2}$.
1426: @end tex
1.1.1.2 ! maekawa 1427: @end deftypefun
! 1428:
! 1429: @deftypefun void mpz_addmul_ui (mpz_t @var{rop}, mpz_t @var{op1}, unsigned long int @var{op2})
! 1430: @ifnottex
! 1431: Add @var{op1} times @var{op2} to @var{rop}.
! 1432: @end ifnottex
! 1433: @tex
! 1434: Set @var{rop} to $@var{rop} + @var{op1} \times @var{op2}$.
! 1435: @end tex
1.1 maekawa 1436: @end deftypefun
1437:
1438: @deftypefun void mpz_mul_2exp (mpz_t @var{rop}, mpz_t @var{op1}, unsigned long int @var{op2})
1.1.1.2 ! maekawa 1439: @cindex Bit shift left
! 1440: @ifnottex
1.1 maekawa 1441: Set @var{rop} to @var{op1} times 2 raised to @var{op2}. This operation can
1442: also be defined as a left shift, @var{op2} steps.
1.1.1.2 ! maekawa 1443: @end ifnottex
1.1 maekawa 1444: @tex
1445: Set @var{rop} to $@var{op1} \times 2^{op2}$. This operation can also be
1446: defined as a left shift, @var{op2} steps.
1447: @end tex
1448: @end deftypefun
1449:
1450: @deftypefun void mpz_neg (mpz_t @var{rop}, mpz_t @var{op})
1451: Set @var{rop} to @minus{}@var{op}.
1452: @end deftypefun
1453:
1454: @deftypefun void mpz_abs (mpz_t @var{rop}, mpz_t @var{op})
1455: Set @var{rop} to the absolute value of @var{op}.
1456: @end deftypefun
1457:
1458:
1.1.1.2 ! maekawa 1459: @need 2000
! 1460: @node Integer Division, Integer Exponentiation, Integer Arithmetic, Integer Functions
! 1461: @section Division Functions
! 1462: @cindex Integer division functions
! 1463: @cindex Division functions
1.1 maekawa 1464:
1.1.1.2 ! maekawa 1465: Division is undefined if the divisor is zero, and passing a zero divisor to the
! 1466: divide or modulo functions, as well passing a zero mod argument to the
1.1 maekawa 1467: @code{mpz_powm} and @code{mpz_powm_ui} functions, will make these functions
1.1.1.2 ! maekawa 1468: intentionally divide by zero. This lets the user handle arithmetic exceptions
! 1469: in these functions in the same manner as other arithmetic exceptions.
1.1 maekawa 1470:
1471: There are three main groups of division functions:
1472: @itemize @bullet
1473: @item
1.1.1.2 ! maekawa 1474: Functions that truncate the quotient towards 0. The names of these functions
! 1475: start with @code{mpz_tdiv}. The @samp{t} in the name is short for
1.1 maekawa 1476: @samp{truncate}.
1477: @item
1.1.1.2 ! maekawa 1478: Functions that round the quotient towards
! 1479: @ifnottex
! 1480: @minus{}infinity).
! 1481: @end ifnottex
! 1482: @tex
! 1483: $-\infty$
! 1484: @end tex
! 1485: The names of these routines start with @code{mpz_fdiv}. The @samp{f} in the
! 1486: name is short for @samp{floor}.
! 1487: @item
! 1488: Functions that round the quotient towards
! 1489: @ifnottex
! 1490: +infinity.
! 1491: @end ifnottex
! 1492: @tex
! 1493: $+\infty$
! 1494: @end tex
! 1495: The names of these routines start with @code{mpz_cdiv}. The @samp{c} in the
! 1496: name is short for @samp{ceil}.
1.1 maekawa 1497: @end itemize
1498:
1499: For each rounding mode, there are a couple of variants. Here @samp{q} means
1500: that the quotient is computed, while @samp{r} means that the remainder is
1501: computed. Functions that compute both the quotient and remainder have
1502: @samp{qr} in the name.
1503:
1.1.1.2 ! maekawa 1504: @deftypefun void mpz_tdiv_q (mpz_t @var{q}, mpz_t @var{n}, mpz_t @var{d})
! 1505: @deftypefunx {unsigned long int} mpz_tdiv_q_ui (mpz_t @var{q}, mpz_t @var{n}, unsigned long int @var{d})
! 1506: Set @var{q} to [@var{n}/@var{d}], truncated towards 0.
! 1507:
! 1508: The function @code{mpz_tdiv_q_ui} returns the absolute value of the true
! 1509: remainder.
1.1 maekawa 1510: @end deftypefun
1511:
1.1.1.2 ! maekawa 1512: @deftypefun void mpz_tdiv_r (mpz_t @var{r}, mpz_t @var{n}, mpz_t @var{d})
! 1513: @deftypefunx {unsigned long int} mpz_tdiv_r_ui (mpz_t @var{r}, mpz_t @var{n}, unsigned long int @var{d})
! 1514: @ifnottex
! 1515: Set @var{r} to (@var{n} - [@var{n}/@var{d}] * @var{d}), where the quotient is
! 1516: truncated towards 0. Unless @var{r} becomes zero, it will get the same sign as
! 1517: @var{n}.
! 1518: @end ifnottex
! 1519: @tex
! 1520: Set @var{r} to $(@var{n} - [@var{n}/@var{d}] \times @var{d})$, where the
! 1521: quotient is truncated towards 0. Unless @var{r} becomes zero, it will get the
! 1522: same sign as @var{n}.
! 1523: @end tex
! 1524:
! 1525: The function @code{mpz_tdiv_r_ui} returns the absolute value of the remainder.
1.1 maekawa 1526: @end deftypefun
1527:
1.1.1.2 ! maekawa 1528: @deftypefun void mpz_tdiv_qr (mpz_t @var{q}, mpz_t @var{r}, mpz_t @var{n}, mpz_t @var{d})
! 1529: @deftypefunx {unsigned long int} mpz_tdiv_qr_ui (mpz_t @var{q}, mpz_t @var{r}, mpz_t @var{n}, unsigned long int @var{d})
! 1530: @ifnottex
! 1531: Set @var{q} to [@var{n}/@var{d}], truncated towards 0. Set @var{r} to (@var{n}
! 1532: - [@var{n}/@var{d}] * @var{d}). Unless @var{r} becomes zero, it will get the
! 1533: same sign as @var{n}. If @var{q} and @var{r} are the same variable, the
! 1534: results are undefined.
! 1535: @end ifnottex
! 1536: @tex
! 1537: Set @var{q} to [@var{n}/@var{d}], truncated towards 0. Set @var{r} to $(@var{n}
! 1538: - [@var{n}/@var{d}] \times @var{d})$. Unless @var{r} becomes zero, it will get the
! 1539: same sign as @var{n}. If @var{q} and @var{r} are the same variable, the
! 1540: results are undefined.
! 1541: @end tex
1.1 maekawa 1542:
1.1.1.2 ! maekawa 1543: The function @code{mpz_tdiv_qr_ui} returns the absolute value of the remainder.
1.1 maekawa 1544: @end deftypefun
1545:
1.1.1.2 ! maekawa 1546: @deftypefun {unsigned long int} mpz_tdiv_ui (mpz_t @var{n}, unsigned long int @var{d})
! 1547: Like @code{mpz_tdiv_r_ui}, but the remainder is not stored anywhere; its
! 1548: absolute value is just returned.
! 1549: @end deftypefun
! 1550:
! 1551: @deftypefun void mpz_fdiv_q (mpz_t @var{q}, mpz_t @var{n}, mpz_t @var{d})
! 1552: @deftypefunx {unsigned long int} mpz_fdiv_q_ui (mpz_t @var{q}, mpz_t @var{n}, unsigned long int @var{d})
! 1553: @ifnottex
! 1554: Set @var{q} to @var{n}/@var{d}, rounded towards @minus{}infinity.
! 1555: @end ifnottex
1.1 maekawa 1556: @tex
1.1.1.2 ! maekawa 1557: Set @var{q} to $\lfloor@var{n}/@var{d}\rfloor$.
1.1 maekawa 1558: @end tex
1.1.1.2 ! maekawa 1559:
! 1560: The function @code{mpz_fdiv_q_ui} returns the remainder.
1.1 maekawa 1561: @end deftypefun
1562:
1.1.1.2 ! maekawa 1563: @deftypefun void mpz_fdiv_r (mpz_t @var{r}, mpz_t @var{n}, mpz_t @var{d})
! 1564: @deftypefunx {unsigned long int} mpz_fdiv_r_ui (mpz_t @var{r}, mpz_t @var{n}, unsigned long int @var{d})
! 1565: @ifnottex
! 1566: Set @var{r} to (@var{n} - @var{n}/@var{d} * @var{d}), where the quotient is
! 1567: rounded towards @minus{}infinity. Unless @var{r} becomes zero, it will get the
! 1568: same sign as @var{d}.
! 1569: @end ifnottex
! 1570: @tex
! 1571: Set @var{r} to $(@var{n} - \lfloor@var{n}/@var{d}\rfloor \times @var{d})$.
! 1572: Unless @var{r} becomes zero, it will get the same sign as @var{d}.
! 1573: @end tex
1.1 maekawa 1574:
1.1.1.2 ! maekawa 1575: The function @code{mpz_fdiv_r_ui} returns the remainder.
! 1576: @end deftypefun
1.1 maekawa 1577:
1.1.1.2 ! maekawa 1578: @deftypefun void mpz_fdiv_qr (mpz_t @var{q}, mpz_t @var{r}, mpz_t @var{n}, mpz_t @var{d})
! 1579: @deftypefunx {unsigned long int} mpz_fdiv_qr_ui (mpz_t @var{q}, mpz_t @var{r}, mpz_t @var{n}, unsigned long int @var{d})
! 1580: @ifnottex
! 1581: Set @var{q} to @var{n}/@var{d}, rounded towards @minus{}infinity. Set @var{r}
! 1582: to (@var{n} - @var{n}/@var{d} * @var{d}). Unless @var{r} becomes zero, it
! 1583: will get the same sign as @var{d}. If @var{q} and @var{r} are the same
! 1584: variable, the results are undefined.
! 1585: @end ifnottex
! 1586: @tex
! 1587: Set @var{q} to $\lfloor@var{n}/@var{d}\rfloor$. Set @var{r} to $(@var{n} -
! 1588: \lfloor@var{n}/@var{d}\rfloor \times @var{d})$. Unless @var{r} becomes zero,
! 1589: it will get the same sign as @var{d}. If @var{q} and @var{r} are the same
! 1590: variable, the results are undefined.
! 1591: @end tex
! 1592:
! 1593: The function @code{mpz_fdiv_qr_ui} returns the remainder.
1.1 maekawa 1594: @end deftypefun
1595:
1.1.1.2 ! maekawa 1596: @deftypefun {unsigned long int} mpz_fdiv_ui (mpz_t @var{n}, unsigned long int @var{d})
! 1597: Like @code{mpz_fdiv_r_ui}, but the remainder is not stored anywhere; it is just
! 1598: returned.
1.1 maekawa 1599: @end deftypefun
1600:
1.1.1.2 ! maekawa 1601: @deftypefun void mpz_cdiv_q (mpz_t @var{q}, mpz_t @var{n}, mpz_t @var{d})
! 1602: @deftypefunx {unsigned long int} mpz_cdiv_q_ui (mpz_t @var{q}, mpz_t @var{n}, unsigned long int @var{d})
! 1603: @ifnottex
! 1604: Set @var{q} to @var{n}/@var{d}, rounded towards +infinity.
! 1605: @end ifnottex
1.1 maekawa 1606: @tex
1.1.1.2 ! maekawa 1607: Set @var{q} to $\lceil@var{n}/@var{d}\rceil$.
1.1 maekawa 1608: @end tex
1.1.1.2 ! maekawa 1609:
! 1610: The function @code{mpz_cdiv_q_ui} returns the negated remainder.
1.1 maekawa 1611: @end deftypefun
1612:
1.1.1.2 ! maekawa 1613: @deftypefun void mpz_cdiv_r (mpz_t @var{r}, mpz_t @var{n}, mpz_t @var{d})
! 1614: @deftypefunx {unsigned long int} mpz_cdiv_r_ui (mpz_t @var{r}, mpz_t @var{n}, unsigned long int @var{d})
! 1615: @ifnottex
! 1616: Set @var{r} to (@var{n} - @var{n}/@var{d} * @var{d}), where the quotient is
! 1617: rounded towards +infinity. Unless @var{r} becomes zero, it will get the
! 1618: opposite sign as @var{d}.
! 1619: @end ifnottex
! 1620: @tex
! 1621: Set @var{r} to $(@var{n} - \lceil@var{n}/@var{d}\rceil \times @var{d})$. Unless
! 1622: @var{r} becomes zero, it will get the opposite sign as @var{d}.
! 1623: @end tex
1.1 maekawa 1624:
1.1.1.2 ! maekawa 1625: The function @code{mpz_cdiv_r_ui} returns the negated remainder.
! 1626: @end deftypefun
1.1 maekawa 1627:
1.1.1.2 ! maekawa 1628: @deftypefun void mpz_cdiv_qr (mpz_t @var{q}, mpz_t @var{r}, mpz_t @var{n}, mpz_t @var{d})
! 1629: @deftypefunx {unsigned long int} mpz_cdiv_qr_ui (mpz_t @var{q}, mpz_t @var{r}, mpz_t @var{n}, unsigned long int @var{d})
! 1630: @ifnottex
! 1631: Set @var{q} to @var{n}/@var{d}, rounded towards +infinity. Set @var{r}
! 1632: to (@var{n} - @var{n}/@var{d} * @var{d}). Unless @var{r} becomes zero, it
! 1633: will get the opposite sign as @var{d}. If @var{q} and @var{r} are the same
! 1634: variable, the results are undefined.
! 1635: @end ifnottex
! 1636: @tex
! 1637: Set @var{q} to $\lceil@var{n}/@var{d}\rceil$. Set @var{r} to $(@var{n} -
! 1638: \lceil@var{n}/@var{d}\rceil \times @var{d})$. Unless @var{r} becomes zero, it will
! 1639: get the opposite sign as @var{d}. If @var{q} and @var{r} are the same
! 1640: variable, the results are undefined.
! 1641: @end tex
! 1642:
! 1643: The function @code{mpz_cdiv_qr_ui} returns the negated remainder.
1.1 maekawa 1644: @end deftypefun
1645:
1.1.1.2 ! maekawa 1646: @deftypefun {unsigned long int} mpz_cdiv_ui (mpz_t @var{n}, unsigned long int @var{d})
! 1647: Like @code{mpz_tdiv_r_ui}, but the remainder is not stored anywhere; its
! 1648: negated value is just returned.
1.1 maekawa 1649: @end deftypefun
1650:
1.1.1.2 ! maekawa 1651: @deftypefun void mpz_mod (mpz_t @var{r}, mpz_t @var{n}, mpz_t @var{d})
! 1652: @deftypefunx {unsigned long int} mpz_mod_ui (mpz_t @var{r}, mpz_t @var{n}, unsigned long int @var{d})
! 1653: Set @var{r} to @var{n} @code{mod} @var{d}. The sign of the divisor is ignored;
! 1654: the result is always non-negative.
1.1 maekawa 1655:
1.1.1.2 ! maekawa 1656: The function @code{mpz_mod_ui} returns the remainder.
1.1 maekawa 1657: @end deftypefun
1658:
1.1.1.2 ! maekawa 1659: @deftypefun void mpz_divexact (mpz_t @var{q}, mpz_t @var{n}, mpz_t @var{d})
! 1660: @cindex Exact division functions
! 1661: Set @var{q} to @var{n}/@var{d}. This function produces correct results only
! 1662: when it is known in advance that @var{d} divides @var{n}.
1.1 maekawa 1663:
1664: Since mpz_divexact is much faster than any of the other routines that produce
1.1.1.2 ! maekawa 1665: the quotient (@pxref{References} Jebelean), it is the best choice for instances
! 1666: in which exact division is known to occur, such as reducing a rational to
! 1667: lowest terms.
1.1 maekawa 1668: @end deftypefun
1669:
1.1.1.2 ! maekawa 1670: @deftypefun void mpz_tdiv_q_2exp (mpz_t @var{q}, mpz_t @var{n}, unsigned long int @var{d})
! 1671: @cindex Bit shift right
! 1672: @ifnottex
! 1673: Set @var{q} to @var{n} divided by 2 raised to @var{d}. The quotient is truncated
! 1674: towards 0.
! 1675: @end ifnottex
1.1 maekawa 1676: @tex
1.1.1.2 ! maekawa 1677: Set @var{q} to $[{n}/2^{d}]$, truncated towards 0.
1.1 maekawa 1678: @end tex
1679: @end deftypefun
1680:
1.1.1.2 ! maekawa 1681: @deftypefun void mpz_tdiv_r_2exp (mpz_t @var{r}, mpz_t @var{n}, unsigned long int @var{d})
! 1682: @ifnottex
! 1683: Divide @var{n} by (2 raised to @var{d}), rounding the quotient towards 0, and
! 1684: put the remainder in @var{r}.
! 1685: @end ifnottex
1.1 maekawa 1686: @tex
1.1.1.2 ! maekawa 1687: Set @var{r} to $n - [n / 2^{d}] \times 2^{d}$, where [ ] indicates rounding towards
! 1688: 0.
1.1 maekawa 1689: @end tex
1.1.1.2 ! maekawa 1690: Unless it is zero, @var{r} will have the same sign as @var{n}.
1.1 maekawa 1691: @end deftypefun
1692:
1.1.1.2 ! maekawa 1693: @deftypefun void mpz_fdiv_q_2exp (mpz_t @var{q}, mpz_t @var{n}, unsigned long int @var{d})
! 1694: @ifnottex
! 1695: Set @var{q} to @var{n} divided by 2 raised to @var{d}, rounded towards
! 1696: @minus{}infinity.
! 1697: @end ifnottex
1.1 maekawa 1698: @tex
1.1.1.2 ! maekawa 1699: Set @var{q} to $\lfloor{n}/2^{d}\rfloor$.
1.1 maekawa 1700: @end tex
1.1.1.2 ! maekawa 1701: This operation can also be defined as arithmetic right shift @var{d} bit
! 1702: positions.
1.1 maekawa 1703: @end deftypefun
1704:
1.1.1.2 ! maekawa 1705: @deftypefun void mpz_fdiv_r_2exp (mpz_t @var{r}, mpz_t @var{n}, unsigned long int @var{d})
! 1706: @ifnottex
! 1707: Divide @var{n} by (2 raised to @var{d}), rounding the quotient towards
! 1708: @minus{}infinity, and put the remainder in @var{r}.
! 1709: @end ifnottex
1.1 maekawa 1710: @tex
1.1.1.2 ! maekawa 1711: Set @var{r} to $n - \lfloor{n}/2^{d}\rfloor \times 2^{d}$.
1.1 maekawa 1712: @end tex
1.1.1.2 ! maekawa 1713: The sign of @var{r} will always be positive.
! 1714: This operation can also be defined as masking of the @var{d} least significant
! 1715: bits.
1.1 maekawa 1716: @end deftypefun
1717:
1.1.1.2 ! maekawa 1718:
! 1719: @need 2000
! 1720: @node Integer Exponentiation, Integer Roots, Integer Division, Integer Functions
! 1721: @section Exponentiation Functions
! 1722: @cindex Integer exponentiation functions
! 1723: @cindex Exponentiation functions
1.1 maekawa 1724:
1725: @deftypefun void mpz_powm (mpz_t @var{rop}, mpz_t @var{base}, mpz_t @var{exp}, mpz_t @var{mod})
1726: @deftypefunx void mpz_powm_ui (mpz_t @var{rop}, mpz_t @var{base}, unsigned long int @var{exp}, mpz_t @var{mod})
1.1.1.2 ! maekawa 1727: @ifnottex
1.1 maekawa 1728: Set @var{rop} to (@var{base} raised to @var{exp}) @code{mod} @var{mod}. If
1729: @var{exp} is negative, the result is undefined.
1.1.1.2 ! maekawa 1730: @end ifnottex
! 1731: @tex
! 1732: Set @var{rop} to $base^{exp} \bmod mod$. If
! 1733: @var{exp} is negative, the result is undefined.
! 1734: @end tex
! 1735:
1.1 maekawa 1736: @end deftypefun
1737:
1738: @deftypefun void mpz_pow_ui (mpz_t @var{rop}, mpz_t @var{base}, unsigned long int @var{exp})
1739: @deftypefunx void mpz_ui_pow_ui (mpz_t @var{rop}, unsigned long int @var{base}, unsigned long int @var{exp})
1.1.1.2 ! maekawa 1740: @ifnottex
! 1741: Set @var{rop} to @var{base} raised to @var{exp}. The case of 0^0 yields 1.
! 1742: @end ifnottex
1.1 maekawa 1743: @tex
1.1.1.2 ! maekawa 1744: Set @var{rop} to $base^{exp}$. The case of $0^0$ yields 1.
1.1 maekawa 1745: @end tex
1746: @end deftypefun
1747:
1.1.1.2 ! maekawa 1748:
! 1749: @need 2000
! 1750: @node Integer Roots, Number Theoretic Functions, Integer Exponentiation, Integer Functions
! 1751: @section Root Extraction Functions
! 1752: @cindex Integer root functions
! 1753: @cindex Root extraction functions
! 1754:
! 1755: @deftypefun int mpz_root (mpz_t @var{rop}, mpz_t @var{op}, unsigned long int @var{n})
! 1756: @ifnottex
! 1757: Set @var{rop} to the truncated integer part of the @var{n}th root of @var{op}.
! 1758: @end ifnottex
! 1759: @tex
! 1760: Set @var{rop} to $\lfloor\root n \of {op}\rfloor$, the truncated integer
! 1761: part of the @var{n}th root of @var{op}.
! 1762: @end tex
! 1763: Return non-zero if the computation was exact, i.e., if @var{op} is
! 1764: @var{rop} to the @var{n}th power.
! 1765: @end deftypefun
1.1 maekawa 1766:
1767: @deftypefun void mpz_sqrt (mpz_t @var{rop}, mpz_t @var{op})
1.1.1.2 ! maekawa 1768: @ifnottex
! 1769: Set @var{rop} to the truncated integer part of the square root of @var{op}.
! 1770: @end ifnottex
1.1 maekawa 1771: @tex
1.1.1.2 ! maekawa 1772: Set @var{rop} to $\lfloor\sqrt{@var{op}}\rfloor$, the truncated integer part of
! 1773: the square root of @var{op}.
1.1 maekawa 1774: @end tex
1775: @end deftypefun
1776:
1777: @deftypefun void mpz_sqrtrem (mpz_t @var{rop1}, mpz_t @var{rop2}, mpz_t @var{op})
1.1.1.2 ! maekawa 1778: @ifnottex
1.1 maekawa 1779: Set @var{rop1} to the truncated integer part of the square root of @var{op},
1780: like @code{mpz_sqrt}. Set @var{rop2} to
1781: @var{op}@minus{}@var{rop1}*@var{rop1},
1.1.1.2 ! maekawa 1782: @end ifnottex
1.1 maekawa 1783: @tex
1784: Set @var{rop1} to $\lfloor\sqrt{@var{op}}\rfloor$, like @code{mpz_sqrt}.
1785: Set @var{rop2} to $(@var{op} - @var{rop1}^2)$,
1786: @end tex
1787: (i.e., zero if @var{op} is a perfect square).
1788:
1789: If @var{rop1} and @var{rop2} are the same variable, the results are
1790: undefined.
1791: @end deftypefun
1792:
1.1.1.2 ! maekawa 1793: @deftypefun int mpz_perfect_power_p (mpz_t @var{op})
! 1794: @ifnottex
! 1795: Return non-zero if @var{op} is a perfect power, i.e., if there exist integers
! 1796: @var{a} and @var{b}, with @var{b} > 1, such that @var{op} equals a raised to
! 1797: b. Return zero otherwise.
! 1798: @end ifnottex
! 1799: @tex
! 1800: Return non-zero if @var{op} is a perfect power, i.e., if there exist integers
! 1801: $a$ and $b$, with $b>1$, such that $@var{op}=a^b$. Return zero otherwise.
! 1802: @end tex
! 1803: @end deftypefun
! 1804:
1.1 maekawa 1805: @deftypefun int mpz_perfect_square_p (mpz_t @var{op})
1806: Return non-zero if @var{op} is a perfect square, i.e., if the square root of
1807: @var{op} is an integer. Return zero otherwise.
1808: @end deftypefun
1809:
1810:
1.1.1.2 ! maekawa 1811: @need 2000
! 1812: @node Number Theoretic Functions, Integer Comparisons, Integer Roots, Integer Functions
! 1813: @section Number Theoretic Functions
! 1814: @cindex Number theoretic functions
! 1815:
! 1816: @deftypefun int mpz_probab_prime_p (mpz_t @var{n}, int @var{reps})
! 1817: @cindex Prime testing functions
! 1818: If this function returns 0, @var{n} is definitely not prime. If it
! 1819: returns 1, then @var{n} is `probably' prime. If it returns 2, then
! 1820: @var{n} is surely prime. Reasonable values of reps vary from 5 to 10; a
! 1821: higher value lowers the probability for a non-prime to pass as a
! 1822: `probable' prime.
1.1 maekawa 1823:
1.1.1.2 ! maekawa 1824: The function uses Miller-Rabin's probabilistic test.
1.1 maekawa 1825: @end deftypefun
1826:
1.1.1.2 ! maekawa 1827: @deftypefun int mpz_nextprime (mpz_t @var{rop}, mpz_t @var{op})
! 1828: Set @var{rop} to the next prime greater than @var{op}.
! 1829:
! 1830: This function uses a probabilistic algorithm to identify primes, but for for
! 1831: practical purposes it's adequate, since the chance of a composite passing will
! 1832: be extremely small.
! 1833: @end deftypefun
! 1834:
! 1835: @c mpz_prime_p not implemented as of gmp 3.0.
! 1836:
! 1837: @c @deftypefun int mpz_prime_p (mpz_t @var{n})
! 1838: @c Return non-zero if @var{n} is prime and zero if @var{n} is a non-prime.
! 1839: @c This function is far slower than @code{mpz_probab_prime_p}, but then it
! 1840: @c never returns non-zero for composite numbers.
! 1841:
! 1842: @c (For practical purposes, using @code{mpz_probab_prime_p} is adequate.
! 1843: @c The likelihood of a programming error or hardware malfunction is orders
! 1844: @c of magnitudes greater than the likelihood for a composite to pass as a
! 1845: @c prime, if the @var{reps} argument is in the suggested range.)
! 1846: @c @end deftypefun
! 1847:
1.1 maekawa 1848: @deftypefun void mpz_gcd (mpz_t @var{rop}, mpz_t @var{op1}, mpz_t @var{op2})
1.1.1.2 ! maekawa 1849: @cindex Greatest common divisor functions
1.1 maekawa 1850: Set @var{rop} to the greatest common divisor of @var{op1} and @var{op2}.
1.1.1.2 ! maekawa 1851: The result is always positive even if either of or both input operands
! 1852: are negative.
1.1 maekawa 1853: @end deftypefun
1854:
1855: @deftypefun {unsigned long int} mpz_gcd_ui (mpz_t @var{rop}, mpz_t @var{op1}, unsigned long int @var{op2})
1856: Compute the greatest common divisor of @var{op1} and @var{op2}. If
1.1.1.2 ! maekawa 1857: @var{rop} is not @code{NULL}, store the result there.
1.1 maekawa 1858:
1859: If the result is small enough to fit in an @code{unsigned long int}, it is
1860: returned. If the result does not fit, 0 is returned, and the result is equal
1861: to the argument @var{op1}. Note that the result will always fit if @var{op2}
1862: is non-zero.
1863: @end deftypefun
1864:
1865: @deftypefun void mpz_gcdext (mpz_t @var{g}, mpz_t @var{s}, mpz_t @var{t}, mpz_t @var{a}, mpz_t @var{b})
1.1.1.2 ! maekawa 1866: @cindex Extended GCD
1.1 maekawa 1867: Compute @var{g}, @var{s}, and @var{t}, such that @var{a}@var{s} +
1.1.1.2 ! maekawa 1868: @var{b}@var{t} = @var{g} = @code{gcd}(@var{a}, @var{b}). If @var{t} is
! 1869: @code{NULL}, that argument is not computed.
! 1870: @end deftypefun
! 1871:
! 1872: @deftypefun void mpz_lcm (mpz_t @var{rop}, mpz_t @var{op1}, mpz_t @var{op2})
! 1873: @cindex Least common multiple functions
! 1874: Set @var{rop} to the least common multiple of @var{op1} and @var{op2}.
1.1 maekawa 1875: @end deftypefun
1876:
1877: @deftypefun int mpz_invert (mpz_t @var{rop}, mpz_t @var{op1}, mpz_t @var{op2})
1.1.1.2 ! maekawa 1878: @cindex Modular inverse functions
1.1 maekawa 1879: Compute the inverse of @var{op1} modulo @var{op2} and put the result in
1.1.1.2 ! maekawa 1880: @var{rop}. Return non-zero if an inverse exists, zero otherwise. When the
! 1881: function returns zero, @var{rop} is undefined.
1.1 maekawa 1882: @end deftypefun
1883:
1884: @deftypefun int mpz_jacobi (mpz_t @var{op1}, mpz_t @var{op2})
1885: @deftypefunx int mpz_legendre (mpz_t @var{op1}, mpz_t @var{op2})
1.1.1.2 ! maekawa 1886: @cindex Jabobi symbol functions
! 1887: Compute the Jacobi and Legendre symbols, respectively. @var{op2} should be
! 1888: odd and must be positive.
! 1889: @end deftypefun
! 1890:
! 1891: @deftypefun int mpz_si_kronecker (long @var{a}, mpz_t @var{b});
! 1892: @deftypefunx int mpz_ui_kronecker (unsigned long @var{a}, mpz_t @var{b});
! 1893: @deftypefunx int mpz_kronecker_si (mpz_t @var{a}, long @var{b});
! 1894: @deftypefunx int mpz_kronecker_ui (mpz_t @var{a}, unsigned long @var{b});
! 1895: @cindex Kronecker symbol functions
! 1896: @tex
! 1897: Calculate the value of the Kronecker/Jacobi symbol $\left(a \over b\right)$,
! 1898: with the Kronecker extension $\left(a \over 2\right) = \left(2 \over a\right)$
! 1899: when $a$ odd, or $\left(a \over 2\right) = 0$ when $a$ even.
! 1900: @end tex
! 1901: @ifnottex
! 1902: Calculate the value of the Kronecker/Jacobi symbol (@var{a}/@var{b}), with the
! 1903: Kronecker extension (a/2)=(2/a) when a odd, or (a/2)=0 when a even.
! 1904: @end ifnottex
! 1905: All values of @var{a} and @var{b} give a well-defined result. See Henri
! 1906: Cohen, section 1.4.2, for more information (@pxref{References}). See also the
! 1907: example program @file{demos/qcn.c} which uses @code{mpz_kronecker_ui}.
! 1908: @end deftypefun
! 1909:
! 1910: @deftypefun {unsigned long int} mpz_remove (mpz_t @var{rop}, mpz_t @var{op}, mpz_t @var{f})
! 1911: Remove all occurrences of the factor @var{f} from @var{op} and store the
! 1912: result in @var{rop}. Return the multiplicity of @var{f} in @var{op}.
1.1 maekawa 1913: @end deftypefun
1914:
1.1.1.2 ! maekawa 1915: @deftypefun void mpz_fac_ui (mpz_t @var{rop}, unsigned long int @var{op})
! 1916: @cindex Factorial functions
! 1917: Set @var{rop} to @var{op}!, the factorial of @var{op}.
! 1918: @end deftypefun
! 1919:
! 1920: @deftypefun void mpz_bin_ui (mpz_t @var{rop}, mpz_t @var{n}, unsigned long int @var{k})
! 1921: @deftypefunx void mpz_bin_uiui (mpz_t @var{rop}, unsigned long int @var{n}, @w{unsigned long int @var{k}})
! 1922: @cindex Binomial coefficient functions
! 1923: Compute the binomial coefficient
! 1924: @ifnottex
! 1925: @var{n} over @var{k}
! 1926: @end ifnottex
! 1927: @tex
! 1928: $\left({n}\atop{k}\right)$
! 1929: @end tex
! 1930: and store the result in @var{rop}. Negative values of @var{n} are supported
! 1931: by @code{mpz_bin_ui}, using the identity
! 1932: @ifnottex
! 1933: bin(-n,k) = (-1)^k * bin(n+k-1,k)
! 1934: @end ifnottex
! 1935: @tex
! 1936: $\left({-n}\atop{k}\right) = (-1)^k \left({n+k-1}\atop{k}\right)$
! 1937: @end tex
! 1938: (see Knuth volume 1 section 1.2.6 part G).
! 1939: @end deftypefun
! 1940:
! 1941: @deftypefun void mpz_fib_ui (mpz_t @var{rop}, unsigned long int @var{n})
! 1942: @cindex Fibonacci sequence functions
! 1943: Compute the @var{n}th Fibonacci number and store the result in @var{rop}.
! 1944: @end deftypefun
! 1945:
! 1946:
! 1947: @node Integer Comparisons, Integer Logic and Bit Fiddling, Number Theoretic Functions, Integer Functions
1.1 maekawa 1948: @comment node-name, next, previous, up
1949: @section Comparison Functions
1.1.1.2 ! maekawa 1950: @cindex Integer comparison functions
! 1951: @cindex Comparison functions
1.1 maekawa 1952:
1953: @deftypefun int mpz_cmp (mpz_t @var{op1}, mpz_t @var{op2})
1.1.1.2 ! maekawa 1954: @ifnottex
1.1 maekawa 1955: Compare @var{op1} and @var{op2}. Return a positive value if @var{op1} >
1956: @var{op2}, zero if @var{op1} = @var{op2}, and a negative value if @var{op1} <
1957: @var{op2}.
1.1.1.2 ! maekawa 1958: @end ifnottex
1.1 maekawa 1959: @tex
1960: Compare @var{op1} and @var{op2}. Return a positive value if $@var{op1} >
1961: @var{op2}$, zero if $@var{op1} = @var{op2}$, and a negative value if $@var{op1}
1962: < @var{op2}$.
1963: @end tex
1964: @end deftypefun
1965:
1966: @deftypefn Macro int mpz_cmp_ui (mpz_t @var{op1}, unsigned long int @var{op2})
1967: @deftypefnx Macro int mpz_cmp_si (mpz_t @var{op1}, signed long int @var{op2})
1.1.1.2 ! maekawa 1968: @ifnottex
1.1 maekawa 1969: Compare @var{op1} and @var{op2}. Return a positive value if @var{op1} >
1970: @var{op2}, zero if @var{op1} = @var{op2}, and a negative value if @var{op1} <
1971: @var{op2}.
1.1.1.2 ! maekawa 1972: @end ifnottex
1.1 maekawa 1973: @tex
1974: Compare @var{op1} and @var{op2}. Return a positive value if $@var{op1} >
1975: @var{op2}$, zero if $@var{op1} = @var{op2}$, and a negative value if $@var{op1}
1976: < @var{op2}$.
1977: @end tex
1978:
1979: These functions are actually implemented as macros. They evaluate their
1980: arguments multiple times.
1981: @end deftypefn
1982:
1.1.1.2 ! maekawa 1983:
! 1984: @deftypefun int mpz_cmpabs (mpz_t @var{op1}, mpz_t @var{op2})
! 1985: @deftypefunx int mpz_cmpabs_ui (mpz_t @var{op1}, unsigned long int @var{op2})
! 1986: @ifnottex
! 1987: Compare the absolute values of @var{op1} and @var{op2}. Return a positive
! 1988: value if @var{op1} > @var{op2}, zero if @var{op1} = @var{op2}, and a negative
! 1989: value if @var{op1} < @var{op2}.
! 1990: @end ifnottex
! 1991: @tex
! 1992: Compare the absolute values of @var{op1} and @var{op2}. Return a positive
! 1993: value if $|@var{op1}| > |@var{op2}|$, zero if $|@var{op1}| = |@var{op2}|$, and a
! 1994: negative value if $|@var{op1}| < |@var{op2}|$.
! 1995: @end tex
! 1996: @end deftypefun
! 1997:
1.1 maekawa 1998: @deftypefn Macro int mpz_sgn (mpz_t @var{op})
1.1.1.2 ! maekawa 1999: @ifnottex
1.1 maekawa 2000: Return +1 if @var{op} > 0, 0 if @var{op} = 0, and @minus{}1 if @var{op} < 0.
1.1.1.2 ! maekawa 2001: @end ifnottex
1.1 maekawa 2002: @tex
2003: Return $+1$ if $@var{op} > 0$, 0 if $@var{op} = 0$, and $-1$ if $@var{op} < 0$.
2004: @end tex
2005:
2006: This function is actually implemented as a macro. It evaluates its
2007: arguments multiple times.
2008: @end deftypefn
2009:
1.1.1.2 ! maekawa 2010: @node Integer Logic and Bit Fiddling, I/O of Integers, Integer Comparisons, Integer Functions
1.1 maekawa 2011: @comment node-name, next, previous, up
2012: @section Logical and Bit Manipulation Functions
2013: @cindex Logical functions
2014: @cindex Bit manipulation functions
1.1.1.2 ! maekawa 2015: @cindex Integer bit manipulation functions
1.1 maekawa 2016:
2017: These functions behave as if two's complement arithmetic were used (although
2018: sign-magnitude is used by the actual implementation).
2019:
2020: @deftypefun void mpz_and (mpz_t @var{rop}, mpz_t @var{op1}, mpz_t @var{op2})
2021: Set @var{rop} to @var{op1} logical-and @var{op2}.
2022: @end deftypefun
2023:
2024: @deftypefun void mpz_ior (mpz_t @var{rop}, mpz_t @var{op1}, mpz_t @var{op2})
2025: Set @var{rop} to @var{op1} inclusive-or @var{op2}.
2026: @end deftypefun
2027:
1.1.1.2 ! maekawa 2028: @deftypefun void mpz_xor (mpz_t @var{rop}, mpz_t @var{op1}, mpz_t @var{op2})
! 2029: Set @var{rop} to @var{op1} exclusive-or @var{op2}.
! 2030: @end deftypefun
1.1 maekawa 2031:
2032: @deftypefun void mpz_com (mpz_t @var{rop}, mpz_t @var{op})
2033: Set @var{rop} to the one's complement of @var{op}.
2034: @end deftypefun
2035:
2036: @deftypefun {unsigned long int} mpz_popcount (mpz_t @var{op})
2037: For non-negative numbers, return the population count of @var{op}. For
2038: negative numbers, return the largest possible value (@var{MAX_ULONG}).
2039: @end deftypefun
2040:
2041: @deftypefun {unsigned long int} mpz_hamdist (mpz_t @var{op1}, mpz_t @var{op2})
2042: If @var{op1} and @var{op2} are both non-negative, return the hamming distance
2043: between the two operands. Otherwise, return the largest possible value
2044: (@var{MAX_ULONG}).
2045:
2046: It is possible to extend this function to return a useful value when the
2047: operands are both negative, but the current implementation returns
2048: @var{MAX_ULONG} in this case. @strong{Do not depend on this behavior, since
1.1.1.2 ! maekawa 2049: it will change in a future release.}
1.1 maekawa 2050: @end deftypefun
2051:
2052: @deftypefun {unsigned long int} mpz_scan0 (mpz_t @var{op}, unsigned long int @var{starting_bit})
2053: Scan @var{op}, starting with bit @var{starting_bit}, towards more significant
2054: bits, until the first clear bit is found. Return the index of the found bit.
2055: @end deftypefun
2056:
2057: @deftypefun {unsigned long int} mpz_scan1 (mpz_t @var{op}, unsigned long int @var{starting_bit})
2058: Scan @var{op}, starting with bit @var{starting_bit}, towards more significant
2059: bits, until the first set bit is found. Return the index of the found bit.
2060: @end deftypefun
2061:
2062: @deftypefun void mpz_setbit (mpz_t @var{rop}, unsigned long int @var{bit_index})
1.1.1.2 ! maekawa 2063: Set bit @var{bit_index} in @var{rop}.
1.1 maekawa 2064: @end deftypefun
2065:
2066: @deftypefun void mpz_clrbit (mpz_t @var{rop}, unsigned long int @var{bit_index})
1.1.1.2 ! maekawa 2067: Clear bit @var{bit_index} in @var{rop}.
1.1 maekawa 2068: @end deftypefun
2069:
1.1.1.2 ! maekawa 2070: @deftypefun int mpz_tstbit (mpz_t @var{op}, unsigned long int @var{bit_index})
! 2071: Check bit @var{bit_index} in @var{op} and return 0 or 1 accordingly.
! 2072: @end deftypefun
! 2073:
! 2074: @node I/O of Integers, Integer Random Numbers, Integer Logic and Bit Fiddling, Integer Functions
1.1 maekawa 2075: @comment node-name, next, previous, up
2076: @section Input and Output Functions
2077: @cindex Integer input and output functions
2078: @cindex Input functions
2079: @cindex Output functions
2080: @cindex I/O functions
2081:
2082: Functions that perform input from a stdio stream, and functions that output to
1.1.1.2 ! maekawa 2083: a stdio stream. Passing a @code{NULL} pointer for a @var{stream} argument to any of
1.1 maekawa 2084: these functions will make them read from @code{stdin} and write to
2085: @code{stdout}, respectively.
2086:
2087: When using any of these functions, it is a good idea to include @file{stdio.h}
2088: before @file{gmp.h}, since that will allow @file{gmp.h} to define prototypes
2089: for these functions.
2090:
2091: @deftypefun size_t mpz_out_str (FILE *@var{stream}, int @var{base}, mpz_t @var{op})
2092: Output @var{op} on stdio stream @var{stream}, as a string of digits in base
2093: @var{base}. The base may vary from 2 to 36.
2094:
2095: Return the number of bytes written, or if an error occurred, return 0.
2096: @end deftypefun
2097:
2098: @deftypefun size_t mpz_inp_str (mpz_t @var{rop}, FILE *@var{stream}, int @var{base})
2099: Input a possibly white-space preceded string in base @var{base} from stdio
2100: stream @var{stream}, and put the read integer in @var{rop}. The base may vary
2101: from 2 to 36. If @var{base} is 0, the actual base is determined from the
2102: leading characters: if the first two characters are `0x' or `0X', hexadecimal
2103: is assumed, otherwise if the first character is `0', octal is assumed,
2104: otherwise decimal is assumed.
2105:
2106: Return the number of bytes read, or if an error occurred, return 0.
2107: @end deftypefun
2108:
2109: @deftypefun size_t mpz_out_raw (FILE *@var{stream}, mpz_t @var{op})
2110: Output @var{op} on stdio stream @var{stream}, in raw binary format. The
2111: integer is written in a portable format, with 4 bytes of size information, and
2112: that many bytes of limbs. Both the size and the limbs are written in
2113: decreasing significance order (i.e., in big-endian).
2114:
2115: The output can be read with @code{mpz_inp_raw}.
2116:
2117: Return the number of bytes written, or if an error occurred, return 0.
2118:
2119: The output of this can not be read by @code{mpz_inp_raw} from GMP 1, because
2120: of changes necessary for compatibility between 32-bit and 64-bit machines.
2121: @end deftypefun
2122:
2123: @deftypefun size_t mpz_inp_raw (mpz_t @var{rop}, FILE *@var{stream})
2124: Input from stdio stream @var{stream} in the format written by
2125: @code{mpz_out_raw}, and put the result in @var{rop}. Return the number of
2126: bytes read, or if an error occurred, return 0.
2127:
2128: This routine can read the output from @code{mpz_out_raw} also from GMP 1, in
2129: spite of changes necessary for compatibility between 32-bit and 64-bit
2130: machines.
2131: @end deftypefun
2132:
2133:
2134: @need 2000
1.1.1.2 ! maekawa 2135: @node Integer Random Numbers, Miscellaneous Integer Functions, I/O of Integers, Integer Functions
1.1 maekawa 2136: @comment node-name, next, previous, up
1.1.1.2 ! maekawa 2137: @section Random Number Functions
! 2138: @cindex Integer random number functions
! 2139: @cindex Random number functions
! 2140:
! 2141: The random number functions of GMP come in two groups; older function
! 2142: that rely on a global state, and newer functions that accept a state
! 2143: parameter that is read and modified. Please see the @ref{Random Number
! 2144: Functions} for more information on how to use and not to use random
! 2145: number functions.
! 2146:
! 2147: @deftypefun void mpz_urandomb (mpz_t @var{rop}, gmp_randstate_t @var{state},
! 2148: unsigned long int @var{n})
! 2149: Generate a uniformly distributed random integer in the range
! 2150: @ifnottex
! 2151: 0 to 2^@var{n} @minus{} 1,
! 2152: @end ifnottex
! 2153: @tex
! 2154: 0 to $2^n-1$,
! 2155: @end tex
! 2156: inclusive.
! 2157:
! 2158: The variable @var{state} must be initialized by calling one of the
! 2159: @code{gmp_randinit} functions (@ref{Random State Initialization}) before
! 2160: invoking this function.
! 2161: @end deftypefun
! 2162:
! 2163: @deftypefun void mpz_urandomm (mpz_t @var{rop}, gmp_randstate_t @var{state},
! 2164: mpz_t @var{n})
! 2165: Generate a uniform random integer in the range 0 to
! 2166: @ifnottex
! 2167: @var{n} @minus{} 1, inclusive.
! 2168: @end ifnottex
! 2169: @tex
! 2170: $n-1$, inclusive.
! 2171: @end tex
! 2172:
! 2173: The variable @var{state} must be initialized by calling one of the
! 2174: @code{gmp_randinit} functions (@ref{Random State Initialization})
! 2175: before invoking this function.
! 2176: @end deftypefun
! 2177:
! 2178: @deftypefun void mpz_rrandomb (mpz_t @var{rop}, gmp_randstate_t @var{state}, unsigned long int @var{n})
! 2179: Generate a random integer with long strings of zeros and ones in the
! 2180: binary representation. Useful for testing functions and algorithms,
! 2181: since this kind of random numbers have proven to be more likely to
! 2182: trigger corner-case bugs. The random number will be in the range
! 2183: @ifnottex
! 2184: 0 to 2^@var{n} @minus{} 1,
! 2185: @end ifnottex
! 2186: @tex
! 2187: 0 to $2^n-1$,
! 2188: @end tex
! 2189: inclusive.
! 2190:
! 2191: The variable @var{state} must be initialized by calling one of the
! 2192: @code{gmp_randinit} functions (@ref{Random State Initialization})
! 2193: before invoking this function.
! 2194: @end deftypefun
1.1 maekawa 2195:
2196: @deftypefun void mpz_random (mpz_t @var{rop}, mp_size_t @var{max_size})
2197: Generate a random integer of at most @var{max_size} limbs. The generated
2198: random number doesn't satisfy any particular requirements of randomness.
2199: Negative random numbers are generated when @var{max_size} is negative.
1.1.1.2 ! maekawa 2200:
! 2201: This function is obsolete. Use @code{mpz_urandomb} or
! 2202: @code{mpz_urandomm} instead.
1.1 maekawa 2203: @end deftypefun
2204:
2205: @deftypefun void mpz_random2 (mpz_t @var{rop}, mp_size_t @var{max_size})
2206: Generate a random integer of at most @var{max_size} limbs, with long strings
2207: of zeros and ones in the binary representation. Useful for testing functions
2208: and algorithms, since this kind of random numbers have proven to be more
2209: likely to trigger corner-case bugs. Negative random numbers are generated
2210: when @var{max_size} is negative.
1.1.1.2 ! maekawa 2211:
! 2212: This function is obsolete. Use @code{mpz_rrandomb} instead.
1.1 maekawa 2213: @end deftypefun
2214:
1.1.1.2 ! maekawa 2215:
! 2216: @need 2000
! 2217: @node Miscellaneous Integer Functions, , Integer Random Numbers, Integer Functions
! 2218: @comment node-name, next, previous, up
! 2219: @section Miscellaneous Functions
! 2220: @cindex Miscellaneous integer functions
! 2221: @cindex Integer miscellaneous functions
! 2222:
! 2223: @deftypefun int mpz_fits_ulong_p (mpz_t @var{op})
! 2224: @deftypefunx int mpz_fits_slong_p (mpz_t @var{op})
! 2225: @deftypefunx int mpz_fits_uint_p (mpz_t @var{op})
! 2226: @deftypefunx int mpz_fits_sint_p (mpz_t @var{op})
! 2227: @deftypefunx int mpz_fits_ushort_p (mpz_t @var{op})
! 2228: @deftypefunx int mpz_fits_sshort_p (mpz_t @var{op})
! 2229: Return non-zero iff the value of @var{op} fits in an @code{unsigned long int},
! 2230: @code{signed long int}, @code{unsigned int}, @code{signed int}, @code{unsigned
! 2231: short int}, or @code{signed short int}, respectively. Otherwise, return zero.
! 2232: @end deftypefun
! 2233:
! 2234: @deftypefn Macro int mpz_odd_p (mpz_t @var{op})
! 2235: @deftypefnx Macro int mpz_even_p (mpz_t @var{op})
! 2236: Determine whether @var{op} is odd or even, respectively. Return non-zero if
! 2237: yes, zero if no. These macros evaluate their arguments more than once.
! 2238: @end deftypefn
! 2239:
1.1 maekawa 2240: @deftypefun size_t mpz_size (mpz_t @var{op})
2241: Return the size of @var{op} measured in number of limbs. If @var{op} is zero,
2242: the returned value will be zero.
2243: @c (@xref{Nomenclature}, for an explanation of the concept @dfn{limb}.)
2244: @end deftypefun
2245:
2246: @deftypefun size_t mpz_sizeinbase (mpz_t @var{op}, int @var{base})
2247: Return the size of @var{op} measured in number of digits in base @var{base}.
2248: The base may vary from 2 to 36. The returned value will be exact or 1 too
2249: big. If @var{base} is a power of 2, the returned value will always be exact.
2250:
2251: This function is useful in order to allocate the right amount of space before
2252: converting @var{op} to a string. The right amount of allocation is normally
2253: two more than the value returned by @code{mpz_sizeinbase} (one extra for a
2254: minus sign and one for the terminating '\0').
2255: @end deftypefun
2256:
2257:
2258: @node Rational Number Functions, Floating-point Functions, Integer Functions, Top
2259: @comment node-name, next, previous, up
2260: @chapter Rational Number Functions
2261: @cindex Rational number functions
2262:
1.1.1.2 ! maekawa 2263: This chapter describes the GMP functions for performing arithmetic on rational
1.1 maekawa 2264: numbers. These functions start with the prefix @code{mpq_}.
2265:
2266: Rational numbers are stored in objects of type @code{mpq_t}.
2267:
2268: All rational arithmetic functions assume operands have a canonical form, and
2269: canonicalize their result. The canonical from means that the denominator and
2270: the numerator have no common factors, and that the denominator is positive.
2271: Zero has the unique representation 0/1.
2272:
2273: Pure assignment functions do not canonicalize the assigned variable. It is
2274: the responsibility of the user to canonicalize the assigned variable before
2275: any arithmetic operations are performed on that variable. @strong{Note that
2276: this is an incompatible change from version 1 of the library.}
2277:
2278: @deftypefun void mpq_canonicalize (mpq_t @var{op})
2279: Remove any factors that are common to the numerator and denominator of
2280: @var{op}, and make the denominator positive.
2281: @end deftypefun
2282:
2283: @menu
1.1.1.2 ! maekawa 2284: * Initializing Rationals::
! 2285: * Rational Arithmetic::
! 2286: * Comparing Rationals::
! 2287: * Applying Integer Functions::
! 2288: * I/O of Rationals::
! 2289: * Miscellaneous Rational Functions::
1.1 maekawa 2290: @end menu
2291:
1.1.1.2 ! maekawa 2292: @node Initializing Rationals, Rational Arithmetic, Rational Number Functions, Rational Number Functions
1.1 maekawa 2293: @comment node-name, next, previous, up
2294: @section Initialization and Assignment Functions
1.1.1.2 ! maekawa 2295: @cindex Initialization and assignment functions
! 2296: @cindex Rational init and assign
1.1 maekawa 2297:
2298: @deftypefun void mpq_init (mpq_t @var{dest_rational})
2299: Initialize @var{dest_rational} and set it to 0/1. Each variable should
2300: normally only be initialized once, or at least cleared out (using the function
2301: @code{mpq_clear}) between each initialization.
2302: @end deftypefun
2303:
2304: @deftypefun void mpq_clear (mpq_t @var{rational_number})
2305: Free the space occupied by @var{rational_number}. Make sure to call this
2306: function for all @code{mpq_t} variables when you are done with them.
2307: @end deftypefun
2308:
2309: @deftypefun void mpq_set (mpq_t @var{rop}, mpq_t @var{op})
2310: @deftypefunx void mpq_set_z (mpq_t @var{rop}, mpz_t @var{op})
2311: Assign @var{rop} from @var{op}.
2312: @end deftypefun
2313:
2314: @deftypefun void mpq_set_ui (mpq_t @var{rop}, unsigned long int @var{op1}, unsigned long int @var{op2})
2315: @deftypefunx void mpq_set_si (mpq_t @var{rop}, signed long int @var{op1}, unsigned long int @var{op2})
2316: Set the value of @var{rop} to @var{op1}/@var{op2}. Note that if @var{op1} and
2317: @var{op2} have common factors, @var{rop} has to be passed to
2318: @code{mpq_canonicalize} before any operations are performed on @var{rop}.
2319: @end deftypefun
2320:
1.1.1.2 ! maekawa 2321: @deftypefun void mpq_swap (mpq_t @var{rop1}, mpq_t @var{rop2})
! 2322: Swap the values @var{rop1} and @var{rop2} efficiently.
! 2323: @end deftypefun
! 2324:
! 2325:
! 2326: @node Rational Arithmetic, Comparing Rationals, Initializing Rationals, Rational Number Functions
1.1 maekawa 2327: @comment node-name, next, previous, up
2328: @section Arithmetic Functions
1.1.1.2 ! maekawa 2329: @cindex Rational arithmetic functions
! 2330: @cindex Arithmetic functions
1.1 maekawa 2331:
2332: @deftypefun void mpq_add (mpq_t @var{sum}, mpq_t @var{addend1}, mpq_t @var{addend2})
2333: Set @var{sum} to @var{addend1} + @var{addend2}.
2334: @end deftypefun
2335:
2336: @deftypefun void mpq_sub (mpq_t @var{difference}, mpq_t @var{minuend}, mpq_t @var{subtrahend})
2337: Set @var{difference} to @var{minuend} @minus{} @var{subtrahend}.
2338: @end deftypefun
2339:
2340: @deftypefun void mpq_mul (mpq_t @var{product}, mpq_t @var{multiplier}, mpq_t @var{multiplicand})
1.1.1.2 ! maekawa 2341: @ifnottex
1.1 maekawa 2342: Set @var{product} to @var{multiplier} times @var{multiplicand}.
1.1.1.2 ! maekawa 2343: @end ifnottex
1.1 maekawa 2344: @tex
2345: Set @var{product} to $@var{multiplier} \times @var{multiplicand}$.
2346: @end tex
2347: @end deftypefun
2348:
2349: @deftypefun void mpq_div (mpq_t @var{quotient}, mpq_t @var{dividend}, mpq_t @var{divisor})
1.1.1.2 ! maekawa 2350: @cindex Division functions
1.1 maekawa 2351: Set @var{quotient} to @var{dividend}/@var{divisor}.
2352: @end deftypefun
2353:
2354: @deftypefun void mpq_neg (mpq_t @var{negated_operand}, mpq_t @var{operand})
2355: Set @var{negated_operand} to @minus{}@var{operand}.
2356: @end deftypefun
2357:
2358: @deftypefun void mpq_inv (mpq_t @var{inverted_number}, mpq_t @var{number})
2359: Set @var{inverted_number} to 1/@var{number}. If the new denominator is
2360: zero, this routine will divide by zero.
2361: @end deftypefun
2362:
1.1.1.2 ! maekawa 2363: @node Comparing Rationals, Applying Integer Functions, Rational Arithmetic, Rational Number Functions
1.1 maekawa 2364: @comment node-name, next, previous, up
2365: @section Comparison Functions
1.1.1.2 ! maekawa 2366: @cindex Rational comparison functions
! 2367: @cindex Comparison functions
1.1 maekawa 2368:
2369: @deftypefun int mpq_cmp (mpq_t @var{op1}, mpq_t @var{op2})
1.1.1.2 ! maekawa 2370: @ifnottex
1.1 maekawa 2371: Compare @var{op1} and @var{op2}. Return a positive value if @var{op1} >
2372: @var{op2}, zero if @var{op1} = @var{op2}, and a negative value if @var{op1} <
2373: @var{op2}.
1.1.1.2 ! maekawa 2374: @end ifnottex
1.1 maekawa 2375: @tex
2376: Compare @var{op1} and @var{op2}. Return a positive value if $@var{op1} >
2377: @var{op2}$, zero if $@var{op1} = @var{op2}$, and a negative value if $@var{op1}
2378: < @var{op2}$.
2379: @end tex
2380:
2381: To determine if two rationals are equal, @code{mpq_equal} is faster than
2382: @code{mpq_cmp}.
2383: @end deftypefun
2384:
2385: @deftypefn Macro int mpq_cmp_ui (mpq_t @var{op1}, unsigned long int @var{num2}, unsigned long int @var{den2})
1.1.1.2 ! maekawa 2386: @ifnottex
1.1 maekawa 2387: Compare @var{op1} and @var{num2}/@var{den2}. Return a positive value if
2388: @var{op1} > @var{num2}/@var{den2}, zero if @var{op1} = @var{num2}/@var{den2},
2389: and a negative value if @var{op1} < @var{num2}/@var{den2}.
1.1.1.2 ! maekawa 2390: @end ifnottex
1.1 maekawa 2391: @tex
2392: Compare @var{op1} and @var{num2}/@var{den2}. Return a positive value if
2393: $@var{op1} > @var{num2}/@var{den2}$, zero if $@var{op1} =
2394: @var{num2}/@var{den2}$, and a negative value if $@var{op1} <
2395: @var{num2}/@var{den2}$.
2396: @end tex
2397:
2398: This routine allows that @var{num2} and @var{den2} have common factors.
2399:
2400: This function is actually implemented as a macro. It evaluates its
2401: arguments multiple times.
2402: @end deftypefn
2403:
2404: @deftypefn Macro int mpq_sgn (mpq_t @var{op})
1.1.1.2 ! maekawa 2405: @ifnottex
1.1 maekawa 2406: Return +1 if @var{op} > 0, 0 if @var{op} = 0, and @minus{}1 if @var{op} < 0.
1.1.1.2 ! maekawa 2407: @end ifnottex
1.1 maekawa 2408: @tex
2409: Return $+1$ if $@var{op} > 0$, 0 if $@var{op} = 0$, and $-1$ if $@var{op} < 0$.
2410: @end tex
2411:
2412: This function is actually implemented as a macro. It evaluates its
2413: arguments multiple times.
2414: @end deftypefn
2415:
2416: @deftypefun int mpq_equal (mpq_t @var{op1}, mpq_t @var{op2})
2417: Return non-zero if @var{op1} and @var{op2} are equal, zero if they are
2418: non-equal. Although @code{mpq_cmp} can be used for the same purpose, this
2419: function is much faster.
2420: @end deftypefun
2421:
1.1.1.2 ! maekawa 2422: @node Applying Integer Functions, I/O of Rationals, Comparing Rationals, Rational Number Functions
1.1 maekawa 2423: @comment node-name, next, previous, up
2424: @section Applying Integer Functions to Rationals
1.1.1.2 ! maekawa 2425: @cindex Rational numerator and denominator
! 2426: @cindex Numerator and denominator
1.1 maekawa 2427:
1.1.1.2 ! maekawa 2428: The set of @code{mpq} functions is quite small. In particular, there are few
1.1 maekawa 2429: functions for either input or output. But there are two macros that allow us
2430: to apply any @code{mpz} function on the numerator or denominator of a rational
2431: number. If these macros are used to assign to the rational number,
2432: @code{mpq_canonicalize} normally need to be called afterwards.
2433:
2434: @deftypefn Macro mpz_t mpq_numref (mpq_t @var{op})
2435: @deftypefnx Macro mpz_t mpq_denref (mpq_t @var{op})
2436: Return a reference to the numerator and denominator of @var{op}, respectively.
2437: The @code{mpz} functions can be used on the result of these macros.
2438: @end deftypefn
2439:
1.1.1.2 ! maekawa 2440:
! 2441: @need 2000
! 2442: @node I/O of Rationals, Miscellaneous Rational Functions, Applying Integer Functions, Rational Number Functions
! 2443: @comment node-name, next, previous, up
! 2444: @section Input and Output Functions
! 2445: @cindex Rational input and output functions
! 2446: @cindex Input functions
! 2447: @cindex Output functions
! 2448: @cindex I/O functions
! 2449:
! 2450: Functions that perform input from a stdio stream, and functions that output to
! 2451: a stdio stream. Passing a @code{NULL} pointer for a @var{stream} argument to
! 2452: any of these functions will make them read from @code{stdin} and write to
! 2453: @code{stdout}, respectively.
! 2454:
! 2455: When using any of these functions, it is a good idea to include @file{stdio.h}
! 2456: before @file{gmp.h}, since that will allow @file{gmp.h} to define prototypes
! 2457: for these functions.
! 2458:
! 2459: @deftypefun size_t mpq_out_str (FILE *@var{stream}, int @var{base}, mpq_t @var{op})
! 2460: Output @var{op} on stdio stream @var{stream}, as a string of digits in base
! 2461: @var{base}. The base may vary from 2 to 36. Output is in the form
! 2462: @samp{num/den} or if the denominator is 1 then just @samp{num}.
! 2463:
! 2464: Return the number of bytes written, or if an error occurred, return 0.
! 2465: @end deftypefun
! 2466:
! 2467:
1.1 maekawa 2468: @need 2000
1.1.1.2 ! maekawa 2469: @node Miscellaneous Rational Functions, , I/O of Rationals, Rational Number Functions
1.1 maekawa 2470: @comment node-name, next, previous, up
2471: @section Miscellaneous Functions
1.1.1.2 ! maekawa 2472: @cindex Rational miscellaneous functions
! 2473: @cindex Miscellaneous rational functions
1.1 maekawa 2474:
2475: @deftypefun double mpq_get_d (mpq_t @var{op})
2476: Convert @var{op} to a double.
2477: @end deftypefun
2478:
1.1.1.2 ! maekawa 2479: @deftypefun double mpq_set_d (mpq_t @var{rop}, double @var{d})
! 2480: Set @var{rop} to the value of d, without rounding.
! 2481: @end deftypefun
! 2482:
1.1 maekawa 2483: These functions assign between either the numerator or denominator of a
2484: rational, and an integer. Instead of using these functions, it is preferable
2485: to use the more general mechanisms @code{mpq_numref} and @code{mpq_denref},
2486: together with @code{mpz_set}.
2487:
2488: @deftypefun void mpq_set_num (mpq_t @var{rational}, mpz_t @var{numerator})
2489: Copy @var{numerator} to the numerator of @var{rational}. When this risks to
2490: make the numerator and denominator of @var{rational} have common factors, you
2491: have to pass @var{rational} to @code{mpq_canonicalize} before any operations
2492: are performed on @var{rational}.
2493:
2494: This function is equivalent to
2495: @code{mpz_set (mpq_numref (@var{rational}), @var{numerator})}.
2496: @end deftypefun
2497:
2498: @deftypefun void mpq_set_den (mpq_t @var{rational}, mpz_t @var{denominator})
2499: Copy @var{denominator} to the denominator of @var{rational}. When this risks
2500: to make the numerator and denominator of @var{rational} have common factors,
2501: or if the denominator might be negative, you have to pass @var{rational} to
2502: @code{mpq_canonicalize} before any operations are performed on @var{rational}.
2503:
2504: @strong{In version 1 of the library, negative denominators were handled by
2505: copying the sign to the numerator. That is no longer done.}
2506:
2507: This function is equivalent to
2508: @code{mpz_set (mpq_denref (@var{rational}), @var{denominators})}.
2509: @end deftypefun
2510:
2511: @deftypefun void mpq_get_num (mpz_t @var{numerator}, mpq_t @var{rational})
2512: Copy the numerator of @var{rational} to the integer @var{numerator}, to
2513: prepare for integer operations on the numerator.
2514:
2515: This function is equivalent to
2516: @code{mpz_set (@var{numerator}, mpq_numref (@var{rational}))}.
2517: @end deftypefun
2518:
2519: @deftypefun void mpq_get_den (mpz_t @var{denominator}, mpq_t @var{rational})
2520: Copy the denominator of @var{rational} to the integer @var{denominator}, to
2521: prepare for integer operations on the denominator.
2522:
2523: This function is equivalent to
2524: @code{mpz_set (@var{denominator}, mpq_denref (@var{rational}))}.
2525: @end deftypefun
2526:
2527:
2528: @node Floating-point Functions, Low-level Functions, Rational Number Functions, Top
2529: @comment node-name, next, previous, up
2530: @chapter Floating-point Functions
2531: @cindex Floating-point functions
2532: @cindex Float functions
2533:
1.1.1.2 ! maekawa 2534: This chapter describes the GMP functions for performing floating point
! 2535: arithmetic. These functions start with the prefix @code{mpf_}.
1.1 maekawa 2536:
1.1.1.2 ! maekawa 2537: GMP floating point numbers are stored in objects of type @code{mpf_t}.
1.1 maekawa 2538:
1.1.1.2 ! maekawa 2539: The GMP floating-point functions have an interface that is similar to the GMP
1.1 maekawa 2540: integer functions. The function prefix for floating-point operations is
2541: @code{mpf_}.
2542:
2543: There is one significant characteristic of floating-point numbers that has
1.1.1.2 ! maekawa 2544: motivated a difference between this function class and other GMP function
1.1 maekawa 2545: classes: the inherent inexactness of floating point arithmetic. The user has
2546: to specify the precision of each variable. A computation that assigns a
2547: variable will take place with the precision of the assigned variable; the
2548: precision of variables used as input is ignored.
2549:
2550: @cindex User-defined precision
1.1.1.2 ! maekawa 2551: @cindex Precision of floats
1.1 maekawa 2552: The precision of a calculation is defined as follows: Compute the requested
2553: operation exactly (with ``infinite precision''), and truncate the result to
2554: the destination variable precision. Even if the user has asked for a very
1.1.1.2 ! maekawa 2555: high precision, GMP will not calculate with superfluous digits. For example,
1.1 maekawa 2556: if two low-precision numbers of nearly equal magnitude are added, the
2557: precision of the result will be limited to what is required to represent the
2558: result accurately.
2559:
1.1.1.2 ! maekawa 2560: The GMP floating-point functions are @emph{not} intended as a smooth extension
1.1 maekawa 2561: to the IEEE P754 arithmetic. Specifically, the results obtained on one
2562: computer often differs from the results obtained on a computer with a
2563: different word size.
2564:
2565: @menu
1.1.1.2 ! maekawa 2566: * Initializing Floats::
! 2567: * Assigning Floats::
! 2568: * Simultaneous Float Init & Assign::
! 2569: * Converting Floats::
! 2570: * Float Arithmetic::
! 2571: * Float Comparison::
! 2572: * I/O of Floats::
! 2573: * Miscellaneous Float Functions::
1.1 maekawa 2574: @end menu
2575:
1.1.1.2 ! maekawa 2576: @node Initializing Floats, Assigning Floats, Floating-point Functions, Floating-point Functions
1.1 maekawa 2577: @comment node-name, next, previous, up
1.1.1.2 ! maekawa 2578: @section Initialization Functions
! 2579: @cindex Float initialization functions
! 2580: @cindex Initialization functions
1.1 maekawa 2581:
2582: @deftypefun void mpf_set_default_prec (unsigned long int @var{prec})
2583: Set the default precision to be @strong{at least} @var{prec} bits. All
2584: subsequent calls to @code{mpf_init} will use this precision, but previously
2585: initialized variables are unaffected.
2586: @end deftypefun
2587:
2588: An @code{mpf_t} object must be initialized before storing the first value in
2589: it. The functions @code{mpf_init} and @code{mpf_init2} are used for that
2590: purpose.
2591:
2592: @deftypefun void mpf_init (mpf_t @var{x})
2593: Initialize @var{x} to 0. Normally, a variable should be initialized once only
2594: or at least be cleared, using @code{mpf_clear}, between initializations. The
2595: precision of @var{x} is undefined unless a default precision has already been
2596: established by a call to @code{mpf_set_default_prec}.
2597: @end deftypefun
2598:
2599: @deftypefun void mpf_init2 (mpf_t @var{x}, unsigned long int @var{prec})
2600: Initialize @var{x} to 0 and set its precision to be @strong{at least}
2601: @var{prec} bits. Normally, a variable should be initialized once only or at
2602: least be cleared, using @code{mpf_clear}, between initializations.
2603: @end deftypefun
2604:
2605: @deftypefun void mpf_clear (mpf_t @var{x})
2606: Free the space occupied by @var{x}. Make sure to call this function for all
2607: @code{mpf_t} variables when you are done with them.
2608: @end deftypefun
2609:
2610: @need 2000
2611: Here is an example on how to initialize floating-point variables:
2612: @example
2613: @{
2614: mpf_t x, y;
2615: mpf_init (x); /* use default precision */
2616: mpf_init2 (y, 256); /* precision @emph{at least} 256 bits */
2617: @dots{}
2618: /* Unless the program is about to exit, do ... */
2619: mpf_clear (x);
2620: mpf_clear (y);
2621: @}
2622: @end example
2623:
2624: The following three functions are useful for changing the precision during a
2625: calculation. A typical use would be for adjusting the precision gradually in
2626: iterative algorithms like Newton-Raphson, making the computation precision
2627: closely match the actual accurate part of the numbers.
2628:
2629: @deftypefun void mpf_set_prec (mpf_t @var{rop}, unsigned long int @var{prec})
2630: Set the precision of @var{rop} to be @strong{at least} @var{prec} bits.
2631: Since changing the precision involves calls to @code{realloc}, this routine
2632: should not be called in a tight loop.
2633: @end deftypefun
2634:
2635: @deftypefun {unsigned long int} mpf_get_prec (mpf_t @var{op})
2636: Return the precision actually used for assignments of @var{op}.
2637: @end deftypefun
2638:
2639: @deftypefun void mpf_set_prec_raw (mpf_t @var{rop}, unsigned long int @var{prec})
2640: Set the precision of @var{rop} to be @strong{at least} @var{prec} bits. This
2641: is a low-level function that does not change the allocation. The @var{prec}
2642: argument must not be larger that the precision previously returned by
2643: @code{mpf_get_prec}. It is crucial that the precision of @var{rop} is
1.1.1.2 ! maekawa 2644: ultimately reset to exactly the value returned by @code{mpf_get_prec} before
! 2645: the first call to @code{mpf_set_prec_raw}.
1.1 maekawa 2646: @end deftypefun
2647:
2648:
1.1.1.2 ! maekawa 2649: @need 2000
1.1 maekawa 2650: @node Assigning Floats, Simultaneous Float Init & Assign, Initializing Floats, Floating-point Functions
2651: @comment node-name, next, previous, up
1.1.1.2 ! maekawa 2652: @section Assignment Functions
1.1 maekawa 2653: @cindex Float assignment functions
1.1.1.2 ! maekawa 2654: @cindex Assignment functions
1.1 maekawa 2655:
2656: These functions assign new values to already initialized floats
2657: (@pxref{Initializing Floats}).
2658:
2659: @deftypefun void mpf_set (mpf_t @var{rop}, mpf_t @var{op})
2660: @deftypefunx void mpf_set_ui (mpf_t @var{rop}, unsigned long int @var{op})
2661: @deftypefunx void mpf_set_si (mpf_t @var{rop}, signed long int @var{op})
2662: @deftypefunx void mpf_set_d (mpf_t @var{rop}, double @var{op})
2663: @deftypefunx void mpf_set_z (mpf_t @var{rop}, mpz_t @var{op})
2664: @deftypefunx void mpf_set_q (mpf_t @var{rop}, mpq_t @var{op})
2665: Set the value of @var{rop} from @var{op}.
2666: @end deftypefun
2667:
2668: @deftypefun int mpf_set_str (mpf_t @var{rop}, char *@var{str}, int @var{base})
2669: Set the value of @var{rop} from the string in @var{str}. The string is of the
2670: form @samp{M@@N} or, if the base is 10 or less, alternatively @samp{MeN}.
2671: @samp{M} is the mantissa and @samp{N} is the exponent. The mantissa is always
2672: in the specified base. The exponent is either in the specified base or, if
2673: @var{base} is negative, in decimal.
2674:
2675: The argument @var{base} may be in the ranges 2 to 36, or @minus{}36 to
2676: @minus{}2. Negative values are used to specify that the exponent is in
2677: decimal.
2678:
2679: Unlike the corresponding @code{mpz} function, the base will not be determined
2680: from the leading characters of the string if @var{base} is 0. This is so that
2681: numbers like @samp{0.23} are not interpreted as octal.
2682:
1.1.1.2 ! maekawa 2683: White space is allowed in the string, and is simply ignored. [This is not
! 2684: really true; white-space is ignored in the beginning of the string and within
! 2685: the mantissa, but not in other places, such as after a minus sign or in the
! 2686: exponent. We are considering changing the definition of this function, making
! 2687: it fail when there is any white-space in the input, since that makes a lot of
! 2688: sense. Please tell us your opinion about this change. Do you really want it
! 2689: to accept "3 14" as meaning 314 as it does now?]
1.1 maekawa 2690:
2691: This function returns 0 if the entire string up to the '\0' is a valid number
2692: in base @var{base}. Otherwise it returns @minus{}1.
2693: @end deftypefun
2694:
1.1.1.2 ! maekawa 2695: @deftypefun void mpf_swap (mpf_t @var{rop1}, mpf_t @var{rop2})
! 2696: Swap the values @var{rop1} and @var{rop2} efficiently.
! 2697: @end deftypefun
! 2698:
1.1 maekawa 2699:
2700: @node Simultaneous Float Init & Assign, Converting Floats, Assigning Floats, Floating-point Functions
2701: @comment node-name, next, previous, up
1.1.1.2 ! maekawa 2702: @section Combined Initialization and Assignment Functions
1.1 maekawa 2703: @cindex Initialization and assignment functions
1.1.1.2 ! maekawa 2704: @cindex Float init and assign functions
1.1 maekawa 2705:
1.1.1.2 ! maekawa 2706: For convenience, GMP provides a parallel series of initialize-and-set functions
1.1 maekawa 2707: which initialize the output and then store the value there. These functions'
2708: names have the form @code{mpf_init_set@dots{}}
2709:
2710: Once the float has been initialized by any of the @code{mpf_init_set@dots{}}
2711: functions, it can be used as the source or destination operand for the ordinary
2712: float functions. Don't use an initialize-and-set function on a variable
2713: already initialized!
2714:
2715: @deftypefun void mpf_init_set (mpf_t @var{rop}, mpf_t @var{op})
2716: @deftypefunx void mpf_init_set_ui (mpf_t @var{rop}, unsigned long int @var{op})
2717: @deftypefunx void mpf_init_set_si (mpf_t @var{rop}, signed long int @var{op})
2718: @deftypefunx void mpf_init_set_d (mpf_t @var{rop}, double @var{op})
2719: Initialize @var{rop} and set its value from @var{op}.
2720:
2721: The precision of @var{rop} will be taken from the active default precision, as
2722: set by @code{mpf_set_default_prec}.
2723: @end deftypefun
2724:
2725: @deftypefun int mpf_init_set_str (mpf_t @var{rop}, char *@var{str}, int @var{base})
2726: Initialize @var{rop} and set its value from the string in @var{str}. See
2727: @code{mpf_set_str} above for details on the assignment operation.
2728:
2729: Note that @var{rop} is initialized even if an error occurs. (I.e., you have to
2730: call @code{mpf_clear} for it.)
2731:
2732: The precision of @var{rop} will be taken from the active default precision, as
2733: set by @code{mpf_set_default_prec}.
2734: @end deftypefun
2735:
2736:
2737: @node Converting Floats, Float Arithmetic, Simultaneous Float Init & Assign, Floating-point Functions
2738: @comment node-name, next, previous, up
2739: @section Conversion Functions
1.1.1.2 ! maekawa 2740: @cindex Float conversion functions
1.1 maekawa 2741: @cindex Conversion functions
2742:
2743: @deftypefun double mpf_get_d (mpf_t @var{op})
2744: Convert @var{op} to a double.
2745: @end deftypefun
2746:
2747: @deftypefun {char *} mpf_get_str (char *@var{str}, mp_exp_t *@var{expptr}, int @var{base}, size_t @var{n_digits}, mpf_t @var{op})
2748: Convert @var{op} to a string of digits in base @var{base}. The base may vary
2749: from 2 to 36. Generate at most @var{n_digits} significant digits, or if
2750: @var{n_digits} is 0, the maximum number of digits accurately representable by
2751: @var{op}.
2752:
1.1.1.2 ! maekawa 2753: If @var{str} is @code{NULL}, space for the mantissa is allocated using the default
! 2754: allocation function.
1.1 maekawa 2755:
1.1.1.2 ! maekawa 2756: If @var{str} is not @code{NULL}, it should point to a block of storage enough large
1.1 maekawa 2757: for the mantissa, i.e., @var{n_digits} + 2. The two extra bytes are for a
2758: possible minus sign, and for the terminating null character.
2759:
2760: The exponent is written through the pointer @var{expptr}.
2761:
2762: If @var{n_digits} is 0, the maximum number of digits meaningfully achievable
2763: from the precision of @var{op} will be generated. Note that the space
2764: requirements for @var{str} in this case will be impossible for the user to
1.1.1.2 ! maekawa 2765: predetermine. Therefore, you need to pass @code{NULL} for the string argument
1.1 maekawa 2766: whenever @var{n_digits} is 0.
2767:
2768: The generated string is a fraction, with an implicit radix point immediately
2769: to the left of the first digit. For example, the number 3.1416 would be
2770: returned as "31416" in the string and 1 written at @var{expptr}.
1.1.1.2 ! maekawa 2771:
! 2772: A pointer to the result string is returned. This pointer will will either
! 2773: equal @var{str}, or if that is @code{NULL}, will point to the allocated storage.
1.1 maekawa 2774: @end deftypefun
2775:
2776:
2777: @node Float Arithmetic, Float Comparison, Converting Floats, Floating-point Functions
2778: @comment node-name, next, previous, up
2779: @section Arithmetic Functions
2780: @cindex Float arithmetic functions
2781: @cindex Arithmetic functions
2782:
2783: @deftypefun void mpf_add (mpf_t @var{rop}, mpf_t @var{op1}, mpf_t @var{op2})
2784: @deftypefunx void mpf_add_ui (mpf_t @var{rop}, mpf_t @var{op1}, unsigned long int @var{op2})
1.1.1.2 ! maekawa 2785: @ifnottex
1.1 maekawa 2786: Set @var{rop} to @var{op1} + @var{op2}.
1.1.1.2 ! maekawa 2787: @end ifnottex
1.1 maekawa 2788: @tex
2789: Set @var{rop} to $@var{op1} + @var{op2}$.
2790: @end tex
2791: @end deftypefun
2792:
2793: @deftypefun void mpf_sub (mpf_t @var{rop}, mpf_t @var{op1}, mpf_t @var{op2})
2794: @deftypefunx void mpf_ui_sub (mpf_t @var{rop}, unsigned long int @var{op1}, mpf_t @var{op2})
2795: @deftypefunx void mpf_sub_ui (mpf_t @var{rop}, mpf_t @var{op1}, unsigned long int @var{op2})
2796: Set @var{rop} to @var{op1} @minus{} @var{op2}.
2797: @end deftypefun
2798:
2799: @deftypefun void mpf_mul (mpf_t @var{rop}, mpf_t @var{op1}, mpf_t @var{op2})
2800: @deftypefunx void mpf_mul_ui (mpf_t @var{rop}, mpf_t @var{op1}, unsigned long int @var{op2})
1.1.1.2 ! maekawa 2801: @ifnottex
1.1 maekawa 2802: Set @var{rop} to @var{op1} times @var{op2}.
1.1.1.2 ! maekawa 2803: @end ifnottex
1.1 maekawa 2804: @tex
2805: Set @var{rop} to $@var{op1} \times @var{op2}$.
2806: @end tex
2807: @end deftypefun
2808:
2809: Division is undefined if the divisor is zero, and passing a zero divisor to
2810: the divide functions will make these functions intentionally divide by zero.
1.1.1.2 ! maekawa 2811: This lets the user handle arithmetic exceptions in these functions in the same
! 2812: manner as other arithmetic exceptions.
1.1 maekawa 2813:
2814: @deftypefun void mpf_div (mpf_t @var{rop}, mpf_t @var{op1}, mpf_t @var{op2})
2815: @deftypefunx void mpf_ui_div (mpf_t @var{rop}, unsigned long int @var{op1}, mpf_t @var{op2})
2816: @deftypefunx void mpf_div_ui (mpf_t @var{rop}, mpf_t @var{op1}, unsigned long int @var{op2})
1.1.1.2 ! maekawa 2817: @cindex Division functions
1.1 maekawa 2818: Set @var{rop} to @var{op1}/@var{op2}.
2819: @end deftypefun
2820:
2821: @deftypefun void mpf_sqrt (mpf_t @var{rop}, mpf_t @var{op})
2822: @deftypefunx void mpf_sqrt_ui (mpf_t @var{rop}, unsigned long int @var{op})
1.1.1.2 ! maekawa 2823: @cindex Root extraction functions
! 2824: @ifnottex
1.1 maekawa 2825: Set @var{rop} to the square root of @var{op}.
1.1.1.2 ! maekawa 2826: @end ifnottex
1.1 maekawa 2827: @tex
2828: Set @var{rop} to $\sqrt{@var{op}}$.
2829: @end tex
2830: @end deftypefun
2831:
1.1.1.2 ! maekawa 2832: @deftypefun void mpf_pow_ui (mpf_t @var{rop}, mpf_t @var{op1}, unsigned long int @var{op2})
! 2833: @cindex Exponentiation functions
! 2834: @ifnottex
! 2835: Set @var{rop} to @var{op1} raised to the power @var{op2}.
! 2836: @end ifnottex
! 2837: @tex
! 2838: Set @var{rop} to $@var{op1}^{op2}$.
! 2839: @end tex
! 2840: @end deftypefun
1.1 maekawa 2841:
2842: @deftypefun void mpf_neg (mpf_t @var{rop}, mpf_t @var{op})
2843: Set @var{rop} to @minus{}@var{op}.
2844: @end deftypefun
2845:
2846: @deftypefun void mpf_abs (mpf_t @var{rop}, mpf_t @var{op})
2847: Set @var{rop} to the absolute value of @var{op}.
2848: @end deftypefun
2849:
2850: @deftypefun void mpf_mul_2exp (mpf_t @var{rop}, mpf_t @var{op1}, unsigned long int @var{op2})
1.1.1.2 ! maekawa 2851: @ifnottex
1.1 maekawa 2852: Set @var{rop} to @var{op1} times 2 raised to @var{op2}.
1.1.1.2 ! maekawa 2853: @end ifnottex
1.1 maekawa 2854: @tex
2855: Set @var{rop} to $@var{op1} \times 2^{op2}$.
2856: @end tex
2857: @end deftypefun
2858:
2859: @deftypefun void mpf_div_2exp (mpf_t @var{rop}, mpf_t @var{op1}, unsigned long int @var{op2})
1.1.1.2 ! maekawa 2860: @ifnottex
1.1 maekawa 2861: Set @var{rop} to @var{op1} divided by 2 raised to @var{op2}.
1.1.1.2 ! maekawa 2862: @end ifnottex
1.1 maekawa 2863: @tex
2864: Set @var{rop} to $@var{op1}/2^{op2}$.
2865: @end tex
2866: @end deftypefun
2867:
2868: @node Float Comparison, I/O of Floats, Float Arithmetic, Floating-point Functions
2869: @comment node-name, next, previous, up
2870: @section Comparison Functions
1.1.1.2 ! maekawa 2871: @cindex Float comparison functions
1.1 maekawa 2872: @cindex Comparison functions
2873:
2874: @deftypefun int mpf_cmp (mpf_t @var{op1}, mpf_t @var{op2})
2875: @deftypefunx int mpf_cmp_ui (mpf_t @var{op1}, unsigned long int @var{op2})
2876: @deftypefunx int mpf_cmp_si (mpf_t @var{op1}, signed long int @var{op2})
1.1.1.2 ! maekawa 2877: @ifnottex
1.1 maekawa 2878: Compare @var{op1} and @var{op2}. Return a positive value if @var{op1} >
2879: @var{op2}, zero if @var{op1} = @var{op2}, and a negative value if @var{op1} <
2880: @var{op2}.
1.1.1.2 ! maekawa 2881: @end ifnottex
1.1 maekawa 2882: @tex
2883: Compare @var{op1} and @var{op2}. Return a positive value if $@var{op1} >
2884: @var{op2}$, zero if $@var{op1} = @var{op2}$, and a negative value if $@var{op1}
2885: < @var{op2}$.
2886: @end tex
2887: @end deftypefun
2888:
2889: @deftypefun int mpf_eq (mpf_t @var{op1}, mpf_t @var{op2}, unsigned long int op3)
2890: Return non-zero if the first @var{op3} bits of @var{op1} and @var{op2} are
2891: equal, zero otherwise. I.e., test of @var{op1} and @var{op2} are
2892: approximately equal.
2893: @end deftypefun
2894:
2895: @deftypefun void mpf_reldiff (mpf_t @var{rop}, mpf_t @var{op1}, mpf_t @var{op2})
2896: Compute the relative difference between @var{op1} and @var{op2} and store the
2897: result in @var{rop}.
2898: @end deftypefun
2899:
2900: @deftypefn Macro int mpf_sgn (mpf_t @var{op})
1.1.1.2 ! maekawa 2901: @ifnottex
1.1 maekawa 2902: Return +1 if @var{op} > 0, 0 if @var{op} = 0, and @minus{}1 if @var{op} < 0.
1.1.1.2 ! maekawa 2903: @end ifnottex
1.1 maekawa 2904: @tex
2905: Return $+1$ if $@var{op} > 0$, 0 if $@var{op} = 0$, and $-1$ if $@var{op} < 0$.
2906: @end tex
2907:
2908: This function is actually implemented as a macro. It evaluates its
2909: arguments multiple times.
2910: @end deftypefn
2911:
2912: @node I/O of Floats, Miscellaneous Float Functions, Float Comparison, Floating-point Functions
2913: @comment node-name, next, previous, up
2914: @section Input and Output Functions
2915: @cindex Float input and output functions
2916: @cindex Input functions
2917: @cindex Output functions
2918: @cindex I/O functions
2919:
2920: Functions that perform input from a stdio stream, and functions that output to
1.1.1.2 ! maekawa 2921: a stdio stream. Passing a @code{NULL} pointer for a @var{stream} argument to any of
1.1 maekawa 2922: these functions will make them read from @code{stdin} and write to
2923: @code{stdout}, respectively.
2924:
2925: When using any of these functions, it is a good idea to include @file{stdio.h}
2926: before @file{gmp.h}, since that will allow @file{gmp.h} to define prototypes
2927: for these functions.
2928:
2929: @deftypefun size_t mpf_out_str (FILE *@var{stream}, int @var{base}, size_t @var{n_digits}, mpf_t @var{op})
2930: Output @var{op} on stdio stream @var{stream}, as a string of digits in
2931: base @var{base}. The base may vary from 2 to 36. Print at most
2932: @var{n_digits} significant digits, or if @var{n_digits} is 0, the maximum
2933: number of digits accurately representable by @var{op}.
2934:
2935: In addition to the significant digits, a leading @samp{0.} and a
2936: trailing exponent, in the form @samp{eNNN}, are printed. If @var{base}
2937: is greater than 10, @samp{@@} will be used instead of @samp{e} as
2938: exponent delimiter.
2939:
2940: Return the number of bytes written, or if an error occurred, return 0.
2941: @end deftypefun
2942:
2943: @deftypefun size_t mpf_inp_str (mpf_t @var{rop}, FILE *@var{stream}, int @var{base})
2944: Input a string in base @var{base} from stdio stream @var{stream}, and put the
2945: read float in @var{rop}. The string is of the form @samp{M@@N} or, if the
2946: base is 10 or less, alternatively @samp{MeN}. @samp{M} is the mantissa and
2947: @samp{N} is the exponent. The mantissa is always in the specified base. The
2948: exponent is either in the specified base or, if @var{base} is negative, in
2949: decimal.
2950:
2951: The argument @var{base} may be in the ranges 2 to 36, or @minus{}36 to
2952: @minus{}2. Negative values are used to specify that the exponent is in
2953: decimal.
2954:
2955: Unlike the corresponding @code{mpz} function, the base will not be determined
2956: from the leading characters of the string if @var{base} is 0. This is so that
2957: numbers like @samp{0.23} are not interpreted as octal.
2958:
2959: Return the number of bytes read, or if an error occurred, return 0.
2960: @end deftypefun
2961:
2962: @c @deftypefun void mpf_out_raw (FILE *@var{stream}, mpf_t @var{float})
2963: @c Output @var{float} on stdio stream @var{stream}, in raw binary
2964: @c format. The float is written in a portable format, with 4 bytes of
2965: @c size information, and that many bytes of limbs. Both the size and the
2966: @c limbs are written in decreasing significance order.
2967: @c @end deftypefun
2968:
2969: @c @deftypefun void mpf_inp_raw (mpf_t @var{float}, FILE *@var{stream})
2970: @c Input from stdio stream @var{stream} in the format written by
2971: @c @code{mpf_out_raw}, and put the result in @var{float}.
2972: @c @end deftypefun
2973:
2974:
1.1.1.2 ! maekawa 2975: @node Miscellaneous Float Functions, , I/O of Floats, Floating-point Functions
1.1 maekawa 2976: @comment node-name, next, previous, up
2977: @section Miscellaneous Functions
2978: @cindex Miscellaneous float functions
1.1.1.2 ! maekawa 2979: @cindex Float miscellaneous functions
! 2980:
! 2981: @deftypefun void mpf_ceil (mpf_t @var{rop}, mpf_t @var{op})
! 2982: @deftypefunx void mpf_floor (mpf_t @var{rop}, mpf_t @var{op})
! 2983: @deftypefunx void mpf_trunc (mpf_t @var{rop}, mpf_t @var{op})
! 2984: Set @var{rop} to @var{op} rounded to an integer. @code{mpf_ceil} rounds to
! 2985: the next higher integer, @code{mpf_floor} to the next lower, and
! 2986: @code{mpf_trunc} to the integer towards zero.
! 2987: @end deftypefun
! 2988:
! 2989: @deftypefun void mpf_urandomb (mpf_t @var{rop}, gmp_randstate_t @var{state}, unsigned long int @var{nbits})
! 2990: Generate a uniformly distributed random float in @var{rop}, such that 0 <=
! 2991: @var{rop} < 1, with @var{nbits} significant bits in the mantissa.
! 2992:
! 2993: The variable @var{state} must be initialized by calling one of the
! 2994: @code{gmp_randinit} functions (@ref{Random State Initialization})
! 2995: before invoking this function.
! 2996: @end deftypefun
1.1 maekawa 2997:
2998: @deftypefun void mpf_random2 (mpf_t @var{rop}, mp_size_t @var{max_size}, mp_exp_t @var{max_exp})
2999: Generate a random float of at most @var{max_size} limbs, with long strings of
3000: zeros and ones in the binary representation. The exponent of the number is in
3001: the interval @minus{}@var{exp} to @var{exp}. This function is useful for
3002: testing functions and algorithms, since this kind of random numbers have
3003: proven to be more likely to trigger corner-case bugs. Negative random numbers
3004: are generated when @var{max_size} is negative.
3005: @end deftypefun
3006:
1.1.1.2 ! maekawa 3007:
! 3008:
1.1 maekawa 3009: @c @deftypefun size_t mpf_size (mpf_t @var{op})
3010: @c Return the size of @var{op} measured in number of limbs. If @var{op} is
3011: @c zero, the returned value will be zero. (@xref{Nomenclature}, for an
3012: @c explanation of the concept @dfn{limb}.)
3013: @c
1.1.1.2 ! maekawa 3014: @c @strong{This function is obsolete. It will disappear from future GMP
1.1 maekawa 3015: @c releases.}
3016: @c @end deftypefun
3017:
1.1.1.2 ! maekawa 3018: @node Low-level Functions, Random Number Functions, Floating-point Functions, Top
1.1 maekawa 3019: @comment node-name, next, previous, up
3020: @chapter Low-level Functions
3021: @cindex Low-level functions
3022:
1.1.1.2 ! maekawa 3023: This chapter describes low-level GMP functions, used to implement the high-level
! 3024: GMP functions, but also intended for time-critical user code.
1.1 maekawa 3025:
3026: These functions start with the prefix @code{mpn_}.
3027:
3028: @c 1. Some of these function clobber input operands.
3029: @c
3030:
3031: The @code{mpn} functions are designed to be as fast as possible, @strong{not}
3032: to provide a coherent calling interface. The different functions have somewhat
3033: similar interfaces, but there are variations that make them hard to use. These
3034: functions do as little as possible apart from the real multiple precision
3035: computation, so that no time is spent on things that not all callers need.
3036:
3037: A source operand is specified by a pointer to the least significant limb and a
3038: limb count. A destination operand is specified by just a pointer. It is the
3039: responsibility of the caller to ensure that the destination has enough space
3040: for storing the result.
3041:
3042: With this way of specifying operands, it is possible to perform computations
3043: on subranges of an argument, and store the result into a subrange of a
3044: destination.
3045:
1.1.1.2 ! maekawa 3046: A common requirement for all functions is that each source area needs at
! 3047: least one limb. No size argument may be zero. Unless otherwise stated,
! 3048: in-place operations are allowed where source and destination are the
! 3049: same, but not where they only partly overlap.
1.1 maekawa 3050:
1.1.1.2 ! maekawa 3051: The @code{mpn} functions are the base for the implementation of the
! 3052: @code{mpz_}, @code{mpf_}, and @code{mpq_} functions.
1.1 maekawa 3053:
1.1.1.2 ! maekawa 3054: This example adds the number beginning at @var{s1p} and the number
! 3055: beginning at @var{s2p} and writes the sum at @var{destp}. All areas
1.1 maekawa 3056: have @var{size} limbs.
3057:
3058: @example
1.1.1.2 ! maekawa 3059: cy = mpn_add_n (destp, s1p, s2p, size)
1.1 maekawa 3060: @end example
3061:
3062: @noindent
3063: In the notation used here, a source operand is identified by the pointer to
3064: the least significant limb, and the limb count in braces. For example,
1.1.1.2 ! maekawa 3065: @{s1p, s1size@}.
1.1 maekawa 3066:
1.1.1.2 ! maekawa 3067: @deftypefun mp_limb_t mpn_add_n (mp_limb_t *@var{rp}, const mp_limb_t *@var{s1p}, const mp_limb_t *@var{s2p}, mp_size_t @var{size})
! 3068: Add @{@var{s1p}, @var{size}@} and @{@var{s2p}, @var{size}@}, and
! 3069: write the @var{size} least significant limbs of the result to @var{rp}.
1.1 maekawa 3070: Return carry, either 0 or 1.
3071:
3072: This is the lowest-level function for addition. It is the preferred function
3073: for addition, since it is written in assembly for most targets. For addition
1.1.1.2 ! maekawa 3074: of a variable to itself (i.e., @var{s1p} equals @var{s2p}, use
1.1 maekawa 3075: @code{mpn_lshift} with a count of 1 for optimal speed.
3076: @end deftypefun
3077:
1.1.1.2 ! maekawa 3078: @deftypefun mp_limb_t mpn_add_1 (mp_limb_t *@var{rp}, const mp_limb_t *@var{s1p}, mp_size_t @var{size}, mp_limb_t @var{s2limb})
! 3079: Add @{@var{s1p}, @var{size}@} and @var{s2limb}, and write the
! 3080: @var{size} least significant limbs of the result to @var{rp}. Return
1.1 maekawa 3081: carry, either 0 or 1.
3082: @end deftypefun
3083:
1.1.1.2 ! maekawa 3084: @deftypefun mp_limb_t mpn_add (mp_limb_t *@var{rp}, const mp_limb_t *@var{s1p}, mp_size_t @var{s1size}, const mp_limb_t *@var{s2p}, mp_size_t @var{s2size})
! 3085: Add @{@var{s1p}, @var{s1size}@} and @{@var{s2p},
! 3086: @var{s2size}@}, and write the @var{s1size} least significant limbs of
! 3087: the result to @var{rp}. Return carry, either 0 or 1.
1.1 maekawa 3088:
1.1.1.2 ! maekawa 3089: This function requires that @var{s1size} is greater than or equal to
! 3090: @var{s2size}.
1.1 maekawa 3091: @end deftypefun
3092:
1.1.1.2 ! maekawa 3093: @deftypefun mp_limb_t mpn_sub_n (mp_limb_t *@var{rp}, const mp_limb_t *@var{s1p}, const mp_limb_t *@var{s2p}, mp_size_t @var{size})
! 3094: Subtract @{@var{s2p}, @var{s2size}@} from @{@var{s1p},
1.1 maekawa 3095: @var{size}@}, and write the @var{size} least significant limbs of the result
1.1.1.2 ! maekawa 3096: to @var{rp}. Return borrow, either 0 or 1.
1.1 maekawa 3097:
3098: This is the lowest-level function for subtraction. It is the preferred
3099: function for subtraction, since it is written in assembly for most targets.
3100: @end deftypefun
3101:
1.1.1.2 ! maekawa 3102: @deftypefun mp_limb_t mpn_sub_1 (mp_limb_t *@var{rp}, const mp_limb_t *@var{s1p}, mp_size_t @var{size}, mp_limb_t @var{s2limb})
! 3103: Subtract @var{s2limb} from @{@var{s1p}, @var{size}@}, and write the
! 3104: @var{size} least significant limbs of the result to @var{rp}. Return
1.1 maekawa 3105: borrow, either 0 or 1.
3106: @end deftypefun
3107:
1.1.1.2 ! maekawa 3108: @deftypefun mp_limb_t mpn_sub (mp_limb_t *@var{rp}, const mp_limb_t *@var{s1p}, mp_size_t @var{s1size}, const mp_limb_t *@var{s2p}, mp_size_t @var{s2size})
! 3109: Subtract @{@var{s2p}, @var{s2size}@} from @{@var{s1p},
! 3110: @var{s1size}@}, and write the @var{s1size} least significant limbs of
! 3111: the result to @var{rp}. Return borrow, either 0 or 1.
1.1 maekawa 3112:
1.1.1.2 ! maekawa 3113: This function requires that @var{s1size} is greater than or equal to
! 3114: @var{s2size}.
1.1 maekawa 3115: @end deftypefun
3116:
1.1.1.2 ! maekawa 3117: @deftypefun void mpn_mul_n (mp_limb_t *@var{rp}, const mp_limb_t *@var{s1p}, const mp_limb_t *@var{s2p}, mp_size_t @var{size})
! 3118: Multiply @{@var{s1p}, @var{size}@} and @{@var{s2p}, @var{size}@},
! 3119: and write the @strong{entire} result to @var{rp}.
1.1 maekawa 3120:
1.1.1.2 ! maekawa 3121: The destination has to have space for 2*@var{size} limbs, even if the
1.1 maekawa 3122: significant result might be one limb smaller.
3123: @end deftypefun
3124:
1.1.1.2 ! maekawa 3125: @deftypefun mp_limb_t mpn_mul_1 (mp_limb_t *@var{rp}, const mp_limb_t *@var{s1p}, mp_size_t @var{size}, mp_limb_t @var{s2limb})
! 3126: Multiply @{@var{s1p}, @var{size}@} and @var{s2limb}, and write the
! 3127: @var{size} least significant limbs of the product to @var{rp}. Return
1.1 maekawa 3128: the most significant limb of the product.
3129:
3130: This is a low-level function that is a building block for general
1.1.1.2 ! maekawa 3131: multiplication as well as other operations in GMP. It is written in assembly
1.1 maekawa 3132: for most targets.
3133:
1.1.1.2 ! maekawa 3134: Don't call this function if @var{s2limb} is a power of 2; use
! 3135: @code{mpn_lshift} with a count equal to the logarithm of @var{s2limb}
1.1 maekawa 3136: instead, for optimal speed.
3137: @end deftypefun
3138:
1.1.1.2 ! maekawa 3139: @deftypefun mp_limb_t mpn_addmul_1 (mp_limb_t *@var{rp}, const mp_limb_t *@var{s1p}, mp_size_t @var{size}, mp_limb_t @var{s2limb})
! 3140: Multiply @{@var{s1p}, @var{size}@} and @var{s2limb}, and add the
! 3141: @var{size} least significant limbs of the product to @{@var{rp},
! 3142: @var{size}@} and write the result to @var{rp}. Return
1.1 maekawa 3143: the most significant limb of the product, plus carry-out from the addition.
3144:
3145: This is a low-level function that is a building block for general
1.1.1.2 ! maekawa 3146: multiplication as well as other operations in GMP. It is written in assembly
1.1 maekawa 3147: for most targets.
3148: @end deftypefun
3149:
1.1.1.2 ! maekawa 3150: @deftypefun mp_limb_t mpn_submul_1 (mp_limb_t *@var{rp}, const mp_limb_t *@var{s1p}, mp_size_t @var{size}, mp_limb_t @var{s2limb})
! 3151: Multiply @{@var{s1p}, @var{size}@} and @var{s2limb}, and subtract the
! 3152: @var{size} least significant limbs of the product from @{@var{rp},
! 3153: @var{size}@} and write the result to @var{rp}. Return the most
1.1 maekawa 3154: significant limb of the product, minus borrow-out from the subtraction.
3155:
3156: This is a low-level function that is a building block for general
1.1.1.2 ! maekawa 3157: multiplication and division as well as other operations in GMP. It is written
1.1 maekawa 3158: in assembly for most targets.
3159: @end deftypefun
3160:
1.1.1.2 ! maekawa 3161: @deftypefun mp_limb_t mpn_mul (mp_limb_t *@var{rp}, const mp_limb_t *@var{s1p}, mp_size_t @var{s1size}, const mp_limb_t *@var{s2p}, mp_size_t @var{s2size})
! 3162: Multiply @{@var{s1p}, @var{s1size}@} and @{@var{s2p},
! 3163: @var{s2size}@}, and write the result to @var{rp}. Return the most
1.1 maekawa 3164: significant limb of the result.
3165:
1.1.1.2 ! maekawa 3166: The destination has to have space for @var{s1size} + @var{s2size}
1.1 maekawa 3167: limbs, even if the result might be one limb smaller.
3168:
1.1.1.2 ! maekawa 3169: This function requires that @var{s1size} is greater than or equal to
! 3170: @var{s2size}. The destination must be distinct from either input operands.
! 3171: @end deftypefun
! 3172:
! 3173: @deftypefun mp_limb_t mpn_tdiv_qr (mp_limb_t *@var{qp}, mp_limb_t *@var{rp}, mp_size_t @var{qxn}, const mp_limb_t *@var{np}, mp_size_t @var{nn}, const mp_limb_t *@var{dp}, mp_size_t @var{dn})
! 3174: Divide @{@var{np}, @var{nn}@} by @{@var{dp}, @var{dn}@}. Write the quotient
! 3175: at @var{qp} and the remainder at @var{rp}.
! 3176:
! 3177: The quotient written at @var{qp} will be @var{nn} @minus{} @var{dn} + 1 limbs.
! 3178: The remainder written at @var{rp} will be @var{dn} limbs.
! 3179:
! 3180: It is required that @var{nn} is greater than or equal to @var{dn}. The
! 3181: @var{qxn} operand must be zero.
! 3182:
! 3183: The quotient is rounded towards 0.
! 3184:
! 3185: No overlap between arguments is permitted.
1.1 maekawa 3186: @end deftypefun
3187:
1.1.1.2 ! maekawa 3188: @deftypefun mp_limb_t mpn_divrem (mp_limb_t *@var{r1p}, mp_size_t @var{xsize}, mp_limb_t *@var{rs2p}, mp_size_t @var{rs2size}, const mp_limb_t *@var{s3p}, mp_size_t @var{s3size})
! 3189: [This function is obsolete. Please call @code{mpn_tdiv_qr} instead for
! 3190: best performance.]
! 3191:
! 3192: Divide @{@var{rs2p}, @var{rs2size}@} by @{@var{s3p}, @var{s3size}@}, and write
! 3193: the quotient at @var{r1p}, with the exception of the most significant limb,
! 3194: which is returned. The remainder replaces the dividend at @var{rs2p}; it will
! 3195: be @var{s3size} limbs long (i.e., as many limbs as the divisor).
1.1 maekawa 3196:
3197: In addition to an integer quotient, @var{xsize} fraction limbs are developed,
3198: and stored after the integral limbs. For most usages, @var{xsize} will be
3199: zero.
3200:
3201: It is required that @var{rs2size} is greater than or equal to @var{s3size}.
3202: It is required that the most significant bit of the divisor is set.
3203:
3204: If the quotient is not needed, pass @var{rs2p} + @var{s3size} as @var{r1p}.
3205: Aside from that special case, no overlap between arguments is permitted.
3206:
3207: Return the most significant limb of the quotient, either 0 or 1.
3208:
3209: The area at @var{r1p} needs to be @var{rs2size} @minus{} @var{s3size} +
3210: @var{xsize} limbs large.
3211: @end deftypefun
3212:
1.1.1.2 ! maekawa 3213: @deftypefn Function mp_limb_t mpn_divrem_1 (mp_limb_t *@var{r1p}, mp_size_t @var{xsize}, @w{mp_limb_t *@var{s2p}}, mp_size_t @var{s2size}, mp_limb_t @var{s3limb})
! 3214: @deftypefnx Macro mp_limb_t mpn_divmod_1 (mp_limb_t *@var{r1p}, mp_limb_t *@var{s2p}, @w{mp_size_t @var{s2size}}, @w{mp_limb_t @var{s3limb}})
1.1 maekawa 3215: Divide @{@var{s2p}, @var{s2size}@} by @var{s3limb}, and write the quotient
3216: at @var{r1p}. Return the remainder.
3217:
1.1.1.2 ! maekawa 3218: The integer quotient is written to @{@var{r1p}+@var{xsize}, @var{s2size}@} and
! 3219: in addition @var{xsize} fraction limbs are developed and written to
! 3220: @{@var{r1p}, @var{xsize}@}. Either or both @var{s2size} and @var{xsize} can
! 3221: be zero. For most usages, @var{xsize} will be zero.
! 3222:
! 3223: @code{mpn_divmod_1} exists for upward source compatibility and is simply a
! 3224: macro calling @code{mpn_divrem_1} with an @var{xsize} of 0.
1.1 maekawa 3225:
3226: The areas at @var{r1p} and @var{s2p} have to be identical or completely
3227: separate, not partially overlapping.
1.1.1.2 ! maekawa 3228: @end deftypefn
1.1 maekawa 3229:
1.1.1.2 ! maekawa 3230: @deftypefun mp_limb_t mpn_divmod (mp_limb_t *@var{r1p}, mp_limb_t *@var{rs2p}, mp_size_t @var{rs2size}, const mp_limb_t *@var{s3p}, mp_size_t @var{s3size})
1.1 maekawa 3231: @strong{This interface is obsolete. It will disappear from future releases.
3232: Use @code{mpn_divrem} in its stead.}
3233: @end deftypefun
3234:
1.1.1.2 ! maekawa 3235: @deftypefn Macro mp_limb_t mpn_divexact_by3 (mp_limb_t *@var{rp}, mp_limb_t *@var{sp}, @w{mp_size_t @var{size}})
! 3236: @deftypefnx Function mp_limb_t mpn_divexact_by3c (mp_limb_t *@var{rp}, mp_limb_t *@var{sp}, @w{mp_size_t @var{size}}, mp_limb_t @var{carry})
! 3237: Divide @{@var{sp}, @var{size}@} by 3, expecting it to divide exactly, and
! 3238: writing the result to @{@var{rp}, @var{size}@}. If 3 divides exactly, the
! 3239: return value is zero and the result is the quotient. If not, the return value
! 3240: is non-zero and the result won't be anything useful.
! 3241:
! 3242: @code{mpn_divexact_by3c} takes an initial carry parameter, which can be the
! 3243: return value from a previous call, so a large calculation can be done piece by
! 3244: piece. @code{mpn_divexact_by3} is simply a macro calling
! 3245: @code{mpn_divexact_by3c} with a 0 carry parameter.
! 3246:
! 3247: These routines use a multiply-by-inverse and will be faster than
! 3248: @code{mpn_divrem_1} on CPUs with fast multiplication but slow division.
! 3249:
! 3250: The source @math{a}, result @math{q}, size @math{n}, initial carry @math{i},
! 3251: and return value @math{c} satisfy
! 3252: @tex
! 3253: $c b^n + a - i = 3q$,
! 3254: @end tex
! 3255: @ifnottex
! 3256: @math{c*b^n + a-i = 3*q},
! 3257: @end ifnottex
! 3258: where @math{b} is the size of a limb
! 3259: @tex
! 3260: ($2^{32}$ or $2^{64}$).
! 3261: @end tex
! 3262: @ifnottex
! 3263: (@math{2^32} or @math{2^64}).
! 3264: @end ifnottex
! 3265: @math{c} is always 0, 1 or 2, and the initial carry must also be 0, 1 or 2
! 3266: (these are both borrows really). When @math{c=0}, clearly @math{q=(a-i)/3}.
! 3267: When
! 3268: @tex
! 3269: $c \neq 0$,
! 3270: the remainder $(a-i) \, mod \, 3$
! 3271: @end tex
! 3272: @ifnottex
! 3273: @math{c!=0}, the remainder @math{(a-i) mod 3}
! 3274: @end ifnottex
! 3275: is given by @math{3-c}, because
! 3276: @tex
! 3277: $b \equiv 1 \, mod \, 3$.
! 3278: @end tex
! 3279: @ifnottex
! 3280: @math{b @equiv{} 1 mod 3}.
! 3281: @end ifnottex
! 3282: @end deftypefn
1.1 maekawa 3283:
1.1.1.2 ! maekawa 3284: @deftypefun mp_limb_t mpn_mod_1 (mp_limb_t *@var{s1p}, mp_size_t @var{s1size}, mp_limb_t @var{s2limb})
1.1 maekawa 3285: Divide @{@var{s1p}, @var{s1size}@} by @var{s2limb}, and return the remainder.
1.1.1.2 ! maekawa 3286: @var{s1size} can be zero.
1.1 maekawa 3287: @end deftypefun
3288:
1.1.1.2 ! maekawa 3289: @deftypefun mp_limb_t mpn_preinv_mod_1 (mp_limb_t *@var{s1p}, mp_size_t @var{s1size}, mp_limb_t @var{s2limb}, mp_limb_t @var{s3limb})
1.1 maekawa 3290: @strong{This interface is obsolete. It will disappear from future releases.
3291: Use @code{mpn_mod_1} in its stead.}
3292: @end deftypefun
3293:
1.1.1.2 ! maekawa 3294: @deftypefun mp_limb_t mpn_bdivmod (mp_limb_t *@var{rp}, mp_limb_t *@var{s1p}, mp_size_t @var{s1size}, const mp_limb_t *@var{s2p}, mp_size_t @var{s2size}, unsigned long int @var{d})
1.1 maekawa 3295: The function puts the low [@var{d}/@var{BITS_PER_MP_LIMB}] limbs of
3296: @var{q} =
3297: @{@var{s1p}, @var{s1size}@}/@{@var{s2p}, @var{s2size}@}
3298: mod 2^@var{d}
1.1.1.2 ! maekawa 3299: at @var{rp},
1.1 maekawa 3300: and returns the high @var{d} mod @var{BITS_PER_MP_LIMB} bits of @var{q}.
3301:
3302: @{@var{s1p}, @var{s1size}@} - @var{q} * @{@var{s2p}, @var{s2size}@}
3303: mod 2^(@var{s1size}*@var{BITS_PER_MP_LIMB})
3304: is placed at @var{s1p}.
3305: Since the low [@var{d}/@var{BITS_PER_MP_LIMB}] limbs of
3306: this difference are zero, it is possible to overwrite the low limbs at
3307: @var{s1p} with this difference,
1.1.1.2 ! maekawa 3308: provided @var{rp} <= @var{s1p}.
1.1 maekawa 3309:
3310: This function requires that @var{s1size} * @var{BITS_PER_MP_LIMB} >= @var{D},
3311: and that @{@var{s2p}, @var{s2size}@} is odd.
3312:
3313: @strong{This interface is preliminary. It might change incompatibly in
3314: future revisions.}
3315: @end deftypefun
3316:
1.1.1.2 ! maekawa 3317: @deftypefun mp_limb_t mpn_lshift (mp_limb_t *@var{rp}, const mp_limb_t *@var{src_ptr}, mp_size_t @var{src_size}, unsigned long int @var{count})
1.1 maekawa 3318: Shift @{@var{src_ptr}, @var{src_size}@} @var{count} bits to the left, and
3319: write the @var{src_size} least significant limbs of the result to
1.1.1.2 ! maekawa 3320: @var{rp}. @var{count} might be in the range 1 to n @minus{} 1, on an
1.1 maekawa 3321: n-bit machine. The bits shifted out to the left are returned.
3322:
3323: Overlapping of the destination space and the source space is allowed in this
1.1.1.2 ! maekawa 3324: function, provided @var{rp} >= @var{src_ptr}.
1.1 maekawa 3325:
3326: This function is written in assembly for most targets.
3327: @end deftypefun
3328:
1.1.1.2 ! maekawa 3329: @deftypefun mp_limp_t mpn_rshift (mp_limb_t *@var{rp}, const mp_limb_t *@var{src_ptr}, mp_size_t @var{src_size}, unsigned long int @var{count})
1.1 maekawa 3330: Shift @{@var{src_ptr}, @var{src_size}@} @var{count} bits to the right, and
3331: write the @var{src_size} most significant limbs of the result to
1.1.1.2 ! maekawa 3332: @var{rp}. @var{count} might be in the range 1 to n @minus{} 1, on an
1.1 maekawa 3333: n-bit machine. The bits shifted out to the right are returned.
3334:
3335: Overlapping of the destination space and the source space is allowed in this
1.1.1.2 ! maekawa 3336: function, provided @var{rp} <= @var{src_ptr}.
1.1 maekawa 3337:
3338: This function is written in assembly for most targets.
3339: @end deftypefun
3340:
1.1.1.2 ! maekawa 3341: @deftypefun int mpn_cmp (const mp_limb_t *@var{s1p}, const mp_limb_t *@var{s2p}, mp_size_t @var{size})
! 3342: Compare @{@var{s1p}, @var{size}@} and @{@var{s2p}, @var{size}@} and
! 3343: return a positive value if s1 > src2, 0 of they are equal, and a negative
! 3344: value if s1 < src2.
1.1 maekawa 3345: @end deftypefun
3346:
1.1.1.2 ! maekawa 3347: @deftypefun mp_size_t mpn_gcd (mp_limb_t *@var{rp}, mp_limb_t *@var{s1p}, mp_size_t @var{s1size}, mp_limb_t *@var{s2p}, mp_size_t @var{s2size})
! 3348: Puts at @var{rp} the greatest common divisor of @{@var{s1p},
! 3349: @var{s1size}@} and @{@var{s2p}, @var{s2size}@}; both source
1.1 maekawa 3350: operands are destroyed by the operation. The size in limbs of the greatest
3351: common divisor is returned.
3352:
1.1.1.2 ! maekawa 3353: @{@var{s1p}, @var{s1size}@} must have at least as many bits as
! 3354: @{@var{s2p}, @var{s2size}@}, and @{@var{s2p}, @var{s2size}@} must be odd.
1.1 maekawa 3355: @end deftypefun
3356:
1.1.1.2 ! maekawa 3357: @deftypefun mp_limb_t mpn_gcd_1 (const mp_limb_t *@var{s1p}, mp_size_t @var{s1size}, mp_limb_t @var{s2limb})
! 3358: Return the greatest common divisor of @{@var{s1p}, @var{s1size}@}
! 3359: and @var{s2limb}, where @var{s2limb} (as well as @var{s1size})
1.1 maekawa 3360: must be different from 0.
3361: @end deftypefun
3362:
1.1.1.2 ! maekawa 3363: @deftypefun mp_size_t mpn_gcdext (mp_limb_t *@var{r1p}, mp_limb_t *@var{r2p}, mp_size_t *@var{r2size}, mp_limb_t *@var{s1p}, mp_size_t @var{s1size}, mp_limb_t *@var{s2p}, mp_size_t @var{s2size})
! 3364: Compute the greatest common divisor of @{@var{s1p}, @var{s1size}@} and
! 3365: @{@var{s2p}, @var{s2size}@}. Store the gcd at @var{r1p} and return its size
! 3366: in limbs. Write the first cofactor at @var{r2p} and store its size in
! 3367: *@var{r2size}. If the cofactor is negative, *@var{r2size} is negative and
! 3368: @var{r2p} is the absolute value of the cofactor.
! 3369:
! 3370: @{@var{s1p}, @var{s1size}@} must be greater than or equal to @{@var{s2p},
! 3371: @var{s2size}@}. Neither operand may equal 0. Both source operands are
! 3372: destroyed, plus one limb past the end of each, ie. @{@var{s1p},
! 3373: @var{s1size}+1@} and @{@var{s2p}, @var{s2size}+1@}.
1.1 maekawa 3374: @end deftypefun
3375:
1.1.1.2 ! maekawa 3376: @deftypefun mp_size_t mpn_sqrtrem (mp_limb_t *@var{r1p}, mp_limb_t *@var{r2p}, const mp_limb_t *@var{sp}, mp_size_t @var{size})
1.1 maekawa 3377: Compute the square root of @{@var{sp}, @var{size}@} and put the result at
1.1.1.2 ! maekawa 3378: @var{r1p}. Write the remainder at @var{r2p}, unless @var{r2p} is @code{NULL}.
1.1 maekawa 3379:
1.1.1.2 ! maekawa 3380: Return the size of the remainder, whether @var{r2p} was @code{NULL} or non-@code{NULL}.
1.1 maekawa 3381: Iff the operand was a perfect square, the return value will be 0.
3382:
3383: The areas at @var{r1p} and @var{sp} have to be distinct. The areas at
3384: @var{r2p} and @var{sp} have to be identical or completely separate, not
3385: partially overlapping.
3386:
1.1.1.2 ! maekawa 3387: @ifnottex
1.1 maekawa 3388: The area at @var{r1p} needs to have space for ceil(@var{size}/2) limbs.
1.1.1.2 ! maekawa 3389: @end ifnottex
1.1 maekawa 3390: @tex
3391: The area at @var{r1p} needs to have space for $\lceil@var{size}/2\rceil$ limbs.
3392: @end tex
3393: The area at @var{r2p} needs to be @var{size} limbs large.
3394: @end deftypefun
3395:
1.1.1.2 ! maekawa 3396: @deftypefun mp_size_t mpn_get_str (unsigned char *@var{str}, int @var{base}, mp_limb_t *@var{s1p}, mp_size_t @var{s1size})
1.1 maekawa 3397: Convert @{@var{s1p}, @var{s1size}@} to a raw unsigned char array in base
3398: @var{base}. The string is not in ASCII; to convert it to printable format,
3399: add the ASCII codes for @samp{0} or @samp{A}, depending on the base and
3400: range. There may be leading zeros in the string.
3401:
3402: The area at @var{s1p} is clobbered.
3403:
3404: Return the number of characters in @var{str}.
3405:
3406: The area at @var{str} has to have space for the largest possible number
3407: represented by a @var{s1size} long limb array, plus one extra character.
3408: @end deftypefun
3409:
1.1.1.2 ! maekawa 3410: @deftypefun mp_size_t mpn_set_str (mp_limb_t *@var{r1p}, const char *@var{str}, size_t @var{strsize}, int @var{base})
1.1 maekawa 3411: Convert the raw unsigned char array at @var{str} of length @var{strsize} to
3412: a limb array @{@var{s1p}, @var{s1size}@}. The base of @var{str} is
3413: @var{base}.
3414:
3415: Return the number of limbs stored in @var{r1p}.
3416: @end deftypefun
3417:
1.1.1.2 ! maekawa 3418: @deftypefun {unsigned long int} mpn_scan0 (const mp_limb_t *@var{s1p}, unsigned long int @var{bit})
1.1 maekawa 3419: Scan @var{s1p} from bit position @var{bit} for the next clear bit.
3420:
3421: It is required that there be a clear bit within the area at @var{s1p} at or
3422: beyond bit position @var{bit}, so that the function has something to return.
3423: @end deftypefun
3424:
1.1.1.2 ! maekawa 3425: @deftypefun {unsigned long int} mpn_scan1 (const mp_limb_t *@var{s1p}, unsigned long int @var{bit})
1.1 maekawa 3426: Scan @var{s1p} from bit position @var{bit} for the next set bit.
3427:
3428: It is required that there be a set bit within the area at @var{s1p} at or
3429: beyond bit position @var{bit}, so that the function has something to return.
3430: @end deftypefun
3431:
1.1.1.2 ! maekawa 3432: @deftypefun void mpn_random (mp_limb_t *@var{r1p}, mp_size_t @var{r1size})
! 3433: @deftypefunx void mpn_random2 (mp_limb_t *@var{r1p}, mp_size_t @var{r1size})
! 3434: Generate a random number of length @var{r1size} and store it at @var{r1p}.
! 3435: The most significant limb is always non-zero. @code{mpn_random} generates
! 3436: uniformly distributed limb data, @code{mpn_random2} generates long strings of
! 3437: zeros and ones in the binary representation.
1.1 maekawa 3438:
1.1.1.2 ! maekawa 3439: @code{mpn_random2} is intended for testing the correctness of the @code{mpn}
! 3440: routines.
1.1 maekawa 3441: @end deftypefun
3442:
1.1.1.2 ! maekawa 3443: @deftypefun {unsigned long int} mpn_popcount (const mp_limb_t *@var{s1p}, unsigned long int @var{size})
1.1 maekawa 3444: Count the number of set bits in @{@var{s1p}, @var{size}@}.
3445: @end deftypefun
3446:
1.1.1.2 ! maekawa 3447: @deftypefun {unsigned long int} mpn_hamdist (const mp_limb_t *@var{s1p}, const mp_limb_t *@var{s2p}, unsigned long int @var{size})
1.1 maekawa 3448: Compute the hamming distance between @{@var{s1p}, @var{size}@} and
3449: @{@var{s2p}, @var{size}@}.
3450: @end deftypefun
3451:
1.1.1.2 ! maekawa 3452: @deftypefun int mpn_perfect_square_p (const mp_limb_t *@var{s1p}, mp_size_t @var{size})
1.1 maekawa 3453: Return non-zero iff @{@var{s1p}, @var{size}@} is a perfect square.
3454: @end deftypefun
3455:
3456:
1.1.1.2 ! maekawa 3457: @node Random Number Functions, BSD Compatible Functions, Low-level Functions, Top
! 3458: @chapter Random Number Functions
! 3459: @cindex Random number functions
! 3460:
! 3461: There are two groups of random number functions in GNU MP; older
! 3462: functions that call C library random number generators, rely on a global
! 3463: state, and aren't very random; and newer functions that don't have these
! 3464: problems. The newer functions are self-contained, they accept a random
! 3465: state parameter that supplants global state, and generate good random
! 3466: numbers.
! 3467:
! 3468: The random state parameter is of the type @code{gmp_randstate_t}. It must be
! 3469: initialized by a call to one of the @code{gmp_randinit} functions (@ref{Random
! 3470: State Initialization}). The initial seed is set using one of the
! 3471: @code{gmp_randseed} functions (@ref{Random State Initialization}).
! 3472:
! 3473: The size of the seed determines the number of different sequences of
! 3474: random numbers that is possible to generate. The ``quality'' of the
! 3475: seed is the randomness of a given seed compared to the previous seed
! 3476: used and affects the randomness of separate number sequences.
! 3477:
! 3478: The algorithm for assigning seed is critical if the generated random numbers
! 3479: are to be used for important applications, such as generating cryptographic
! 3480: keys.
! 3481:
! 3482: The traditional method is to use the current system time for seeding. One has
! 3483: to be careful when using the current time though. If the application seeds the
! 3484: random functions very often, say several times per second, and the resolution
! 3485: of the system clock is comparatively low, like one second, the same sequence of
! 3486: numbers will be generated until the system clock ticks. Furthermore, the
! 3487: current system time is quite easy to guess, so a system depending on any
! 3488: unpredictability of the random number sequence should absolutely not use that
! 3489: as its only source for a seed value.
! 3490:
! 3491: On some systems there is a special device, often called @code{/dev/random},
! 3492: which provides a source of somewhat random numbers more usable as seed.
! 3493:
! 3494: The functions actually generating random functions are documented under
! 3495: ``Miscellaneous Functions'' in their respective function class:
! 3496: @ref{Miscellaneous Integer Functions}, @ref{Miscellaneous Float Functions}.
! 3497:
! 3498: @menu
! 3499: * Random State Initialization:: How to initialize a random state.
! 3500: @end menu
! 3501:
! 3502: @node Random State Initialization, , Random Number Functions, Random Number Functions
! 3503: @section Random State Initialization
! 3504: @cindex Random number state
! 3505:
! 3506: See @ref{Random Number Functions} for a discussion on how to choose the
! 3507: initial seed value passed to these functions.
! 3508:
! 3509: @deftypefun void gmp_randinit (gmp_randstate_t @var{state}, gmp_randalg_t @var{alg}, ...)
! 3510: Initialize random state variable @var{state}.
! 3511:
! 3512: @var{alg} denotes what algorithm to use for random number generation.
! 3513: Use one of
! 3514: @itemize @minus
! 3515: @item GMP_RAND_ALG_LC --- Linear congruential.
! 3516:
! 3517: A fast generator defined by @math{X = (aX + c) mod m}.
! 3518:
! 3519: A third argument @var{size} of type unsigned long int is required. @var{size}
! 3520: is the size of the largest good quality random number to be generated,
! 3521: expressed in number of bits. If the random generation functions are asked for
! 3522: a bigger random number than indicated by this parameter, two or more numbers
! 3523: of @var{size} bits will be generated and concatenated, resulting in a ``bad''
! 3524: random number. This can be used to generate big random numbers relatively
! 3525: cheap if the quality of randomness isn't of great importance.
! 3526:
! 3527: a, c, and m are picked from a table where the modulus (m) is a power of 2 and
! 3528: the multiplier is congruent to 5 (mod 8). The choice is based on the
! 3529: @var{size} parameter. The maximum @var{size} supported by this algorithm is
! 3530: 128. If you need bigger random numbers, use your own scheme and call one of
! 3531: the other @code{gmp_randinit} functions.
! 3532:
! 3533: @ignore
! 3534: @item GMP_RAND_ALG_BBS --- Blum, Blum, and Shub.
! 3535: @end ignore
! 3536: @end itemize
! 3537:
! 3538: If @var{alg} is 0 or GMP_RAND_ALG_DEFAULT, the default algorithm is used. The
! 3539: default algorithm is typically a fast algorithm like the linear congruential
! 3540: and requires a third @var{size} argument (see GMP_RAND_ALG_LC).
! 3541:
! 3542: When you're done with a @var{state} variable, call @code{gmp_randclear}
! 3543: to deallocate any memory allocated by this function.
! 3544:
! 3545: @code{gmp_randinit} may set the following bits in @var{gmp_errno}:
! 3546: @c FIXME: gmp_errno is printed in uppercase. That's wrong.
! 3547: @itemize
! 3548: @item GMP_ERROR_UNSUPPORTED_ARGUMENT --- @var{alg} is unsupported
! 3549: @item GMP_ERROR_INVALID_ARGUMENT --- @var{size} is too big
! 3550: @end itemize
! 3551: @end deftypefun
! 3552:
! 3553:
! 3554: @ignore
! 3555: @deftypefun void gmp_randinit_lc (gmp_randstate_t @var{state}, mpz_t @var{a},
! 3556: unsigned long int @var{c}, mpz_t @var{m})
! 3557:
! 3558: Initialize random state variable @var{state} with given linear congruential
! 3559: scheme.
! 3560:
! 3561: Parameters @var{a}, @var{c}, and @var{m} are the multiplier, adder, and modulus
! 3562: for the linear congruential scheme to use, respectively.
! 3563:
! 3564: When you're done with a @var{state} variable, call @code{gmp_randclear}
! 3565: to deallocate any memory allocated by this function.
! 3566: @end deftypefun
! 3567: @end ignore
! 3568:
! 3569: @deftypefun void gmp_randinit_lc_2exp (gmp_randstate_t @var{state}, mpz_t @var{a},
! 3570: unsigned long int @var{c}, unsigned long int @var{m2exp})
! 3571:
! 3572: Initialize random state variable @var{state} with given linear congruential
! 3573: scheme.
! 3574:
! 3575: Parameters @var{a}, @var{c}, and @var{m2exp} are the multiplier, adder, and
! 3576: modulus for the linear congruential scheme to use, respectively. The modulus
! 3577: is expressed as a power of 2, so that
! 3578: @ifnottex
! 3579: @var{m} = 2^@var{m2exp}.
! 3580: @end ifnottex
! 3581: @tex
! 3582: $m = 2^{m2exp}$.
! 3583: @end tex
! 3584:
! 3585: The least significant bits of a random number generated by the linear
! 3586: congruential algorithm where the modulus is a power of two are not very random.
! 3587: Therefore, the lower half of a random number generated by an LC scheme
! 3588: initialized with this function is discarded. Thus, the size of a random number
! 3589: is @var{m2exp} / 2 (rounded upwards) bits when this function has been used for
! 3590: initializing the random state.
! 3591:
! 3592: When you're done with a @var{state} variable, call @code{gmp_randclear}
! 3593: to deallocate any memory allocated by this function.
! 3594: @end deftypefun
! 3595:
! 3596: @deftypefun void gmp_randseed (gmp_randstate_t @var{state}, mpz_t @var{seed})
! 3597: @deftypefunx void gmp_randseed_ui (gmp_randstate_t @var{state}, unsigned long int @var{seed})
! 3598:
! 3599: Set the initial seed value.
! 3600:
! 3601: Parameter @var{seed} is the initial random seed. The function
! 3602: @code{gmp_randseed_ui} takes the @var{seed} as an unsigned long int rather
! 3603: than as an mpz_t.
! 3604: @end deftypefun
! 3605:
! 3606: @deftypefun void gmp_randclear (gmp_randstate_t @var{state})
! 3607: Free all memory occupied by @var{state}. Make sure to call this
! 3608: function for all @code{gmp_randstate_t} variables when you are done with
! 3609: them.
! 3610: @end deftypefun
! 3611:
! 3612: @node BSD Compatible Functions, Custom Allocation, Random Number Functions, Top
1.1 maekawa 3613: @comment node-name, next, previous, up
3614: @chapter Berkeley MP Compatible Functions
1.1.1.2 ! maekawa 3615: @cindex Berkeley MP compatible functions
1.1 maekawa 3616: @cindex BSD MP compatible functions
3617:
3618: These functions are intended to be fully compatible with the Berkeley MP
1.1.1.2 ! maekawa 3619: library which is available on many BSD derived U*ix systems. The
! 3620: @samp{--enable-mpbsd} option must be used when building GNU MP to make these
! 3621: available (@pxref{Installing GMP}).
1.1 maekawa 3622:
3623: The original Berkeley MP library has a usage restriction: you cannot use the
3624: same variable as both source and destination in a single function call. The
3625: compatible functions in GNU MP do not share this restriction---inputs and
3626: outputs may overlap.
3627:
3628: It is not recommended that new programs are written using these functions.
3629: Apart from the incomplete set of functions, the interface for initializing
3630: @code{MINT} objects is more error prone, and the @code{pow} function collides
3631: with @code{pow} in @file{libm.a}.
3632:
3633: @cindex @file{mp.h}
3634: Include the header @file{mp.h} to get the definition of the necessary types
3635: and functions. If you are on a BSD derived system, make sure to include GNU
1.1.1.2 ! maekawa 3636: @file{mp.h} if you are going to link the GNU @file{libmp.a} to your program.
1.1 maekawa 3637: This means that you probably need to give the -I<dir> option to the compiler,
3638: where <dir> is the directory where you have GNU @file{mp.h}.
3639:
3640: @deftypefun {MINT *} itom (signed short int @var{initial_value})
3641: Allocate an integer consisting of a @code{MINT} object and dynamic limb space.
3642: Initialize the integer to @var{initial_value}. Return a pointer to the
3643: @code{MINT} object.
3644: @end deftypefun
3645:
3646: @deftypefun {MINT *} xtom (char *@var{initial_value})
3647: Allocate an integer consisting of a @code{MINT} object and dynamic limb space.
3648: Initialize the integer from @var{initial_value}, a hexadecimal, '\0'-terminate
3649: C string. Return a pointer to the @code{MINT} object.
3650: @end deftypefun
3651:
3652: @deftypefun void move (MINT *@var{src}, MINT *@var{dest})
3653: Set @var{dest} to @var{src} by copying. Both variables must be previously
3654: initialized.
3655: @end deftypefun
3656:
3657: @deftypefun void madd (MINT *@var{src_1}, MINT *@var{src_2}, MINT *@var{destination})
3658: Add @var{src_1} and @var{src_2} and put the sum in @var{destination}.
3659: @end deftypefun
3660:
3661: @deftypefun void msub (MINT *@var{src_1}, MINT *@var{src_2}, MINT *@var{destination})
3662: Subtract @var{src_2} from @var{src_1} and put the difference in
3663: @var{destination}.
3664: @end deftypefun
3665:
3666: @deftypefun void mult (MINT *@var{src_1}, MINT *@var{src_2}, MINT *@var{destination})
3667: Multiply @var{src_1} and @var{src_2} and put the product in
3668: @var{destination}.
3669: @end deftypefun
3670:
3671: @deftypefun void mdiv (MINT *@var{dividend}, MINT *@var{divisor}, MINT *@var{quotient}, MINT *@var{remainder})
3672: @deftypefunx void sdiv (MINT *@var{dividend}, signed short int @var{divisor}, MINT *@var{quotient}, signed short int *@var{remainder})
3673: Set @var{quotient} to @var{dividend}/@var{divisor}, and @var{remainder} to
3674: @var{dividend} mod @var{divisor}. The quotient is rounded towards zero; the
3675: remainder has the same sign as the dividend unless it is zero.
3676:
3677: Some implementations of these functions work differently---or not at all---for
3678: negative arguments.
3679: @end deftypefun
3680:
3681: @deftypefun void msqrt (MINT *@var{operand}, MINT *@var{root}, MINT *@var{remainder})
1.1.1.2 ! maekawa 3682: @ifnottex
1.1 maekawa 3683: Set @var{root} to the truncated integer part of the square root of
3684: @var{operand}. Set @var{remainder} to
3685: @var{operand}@minus{}@var{root}*@var{root},
1.1.1.2 ! maekawa 3686: @end ifnottex
1.1 maekawa 3687: @tex
3688: Set @var{root} to $\lfloor\sqrt{@var{operand}}\rfloor$, like
3689: @code{mpz_sqrt}. Set @var{remainder} to $(operand - root^2)$,
3690: @end tex
3691: (i.e., zero if @var{operand} is a perfect square).
3692:
3693: If @var{root} and @var{remainder} are the same variable, the results are
3694: undefined.
3695: @end deftypefun
3696:
3697: @deftypefun void pow (MINT *@var{base}, MINT *@var{exp}, MINT *@var{mod}, MINT *@var{dest})
3698: Set @var{dest} to (@var{base} raised to @var{exp}) modulo @var{mod}.
3699: @end deftypefun
3700:
3701: @deftypefun void rpow (MINT *@var{base}, signed short int @var{exp}, MINT *@var{dest})
3702: Set @var{dest} to @var{base} raised to @var{exp}.
3703: @end deftypefun
3704:
3705: @deftypefun void gcd (MINT *@var{operand1}, MINT *@var{operand2}, MINT *@var{res})
3706: Set @var{res} to the greatest common divisor of @var{operand1} and
3707: @var{operand2}.
3708: @end deftypefun
3709:
3710: @deftypefun int mcmp (MINT *@var{operand1}, MINT *@var{operand2})
3711: Compare @var{operand1} and @var{operand2}. Return a positive value if
3712: @var{operand1} > @var{operand2}, zero if @var{operand1} =
3713: @var{operand2}, and a negative value if @var{operand1} < @var{operand2}.
3714: @end deftypefun
3715:
3716: @deftypefun void min (MINT *@var{dest})
3717: Input a decimal string from @code{stdin}, and put the read integer in
3718: @var{dest}. SPC and TAB are allowed in the number string, and are ignored.
3719: @end deftypefun
3720:
3721: @deftypefun void mout (MINT *@var{src})
3722: Output @var{src} to @code{stdout}, as a decimal string. Also output a newline.
3723: @end deftypefun
3724:
3725: @deftypefun {char *} mtox (MINT *@var{operand})
3726: Convert @var{operand} to a hexadecimal string, and return a pointer to the
3727: string. The returned string is allocated using the default memory allocation
3728: function, @code{malloc} by default.
3729: @end deftypefun
3730:
3731: @deftypefun void mfree (MINT *@var{operand})
3732: De-allocate, the space used by @var{operand}. @strong{This function should
3733: only be passed a value returned by @code{itom} or @code{xtom}.}
3734: @end deftypefun
3735:
1.1.1.2 ! maekawa 3736:
1.1 maekawa 3737: @node Custom Allocation, Contributors, BSD Compatible Functions, Top
3738: @comment node-name, next, previous, up
3739: @chapter Custom Allocation
1.1.1.2 ! maekawa 3740: @cindex Custom allocation
! 3741: @cindex Memory allocation
! 3742: @cindex Allocation of memory
! 3743:
! 3744: By default, GMP uses @code{malloc}, @code{realloc} and @code{free} for memory
! 3745: allocation. If @code{malloc} or @code{realloc} fails, GMP prints a message to
! 3746: the standard error output and terminates execution.
! 3747:
! 3748: Some applications might want to allocate memory in other ways, or might not
! 3749: want a fatal error when there is no more memory available. To accomplish
! 3750: this, you can specify alternative memory allocation functions.
1.1 maekawa 3751:
1.1.1.2 ! maekawa 3752: This can be done in the Berkeley compatibility library as well as the main GMP
! 3753: library.
1.1 maekawa 3754:
3755: @deftypefun void mp_set_memory_functions (@* void *(*@var{alloc_func_ptr}) (size_t), @* void *(*@var{realloc_func_ptr}) (void *, size_t, size_t), @* void (*@var{free_func_ptr}) (void *, size_t))
3756: Replace the current allocation functions from the arguments. If an argument
1.1.1.2 ! maekawa 3757: is @code{NULL}, the corresponding default function is retained.
1.1 maekawa 3758:
1.1.1.2 ! maekawa 3759: @strong{Be sure to call this function only when there are no active GMP
! 3760: objects allocated using the previous memory functions! Usually, that means
! 3761: that you have to call this function before any other GMP function.}
1.1 maekawa 3762: @end deftypefun
3763:
3764: The functions you supply should fit the following declarations:
3765:
3766: @deftypefun {void *} allocate_function (size_t @var{alloc_size})
3767: This function should return a pointer to newly allocated space with at least
3768: @var{alloc_size} storage units.
3769: @end deftypefun
3770:
3771: @deftypefun {void *} reallocate_function (void *@var{ptr}, size_t @var{old_size}, size_t @var{new_size})
3772: This function should return a pointer to newly allocated space of at least
3773: @var{new_size} storage units, after copying at least the first @var{old_size}
3774: storage units from @var{ptr}. It should also de-allocate the space at
3775: @var{ptr}.
3776:
3777: You can assume that the space at @var{ptr} was formerly returned from
3778: @code{allocate_function} or @code{reallocate_function}, for a request for
3779: @var{old_size} storage units.
3780: @end deftypefun
3781:
3782: @deftypefun void deallocate_function (void *@var{ptr}, size_t @var{size})
3783: De-allocate the space pointed to by @var{ptr}.
3784:
3785: You can assume that the space at @var{ptr} was formerly returned from
3786: @code{allocate_function} or @code{reallocate_function}, for a request for
3787: @var{size} storage units.
3788: @end deftypefun
3789:
3790: (A @dfn{storage unit} is the unit in which the @code{sizeof} operator returns
3791: the size of an object, normally an 8 bit byte.)
3792:
3793:
3794: @node Contributors, References, Custom Allocation, Top
3795: @comment node-name, next, previous, up
3796: @unnumbered Contributors
1.1.1.2 ! maekawa 3797: @cindex Contributors
! 3798:
! 3799: Torbjorn Granlund wrote the original GMP library and is still developing and
! 3800: maintaining it. Several other individuals and organizations have contributed
! 3801: to GMP in various ways. Here is a list in chronological order:
1.1 maekawa 3802:
1.1.1.2 ! maekawa 3803: Gunnar Sjoedin and Hans Riesel helped with mathematical problems in early
! 3804: versions of the library.
! 3805:
! 3806: Richard Stallman contributed to the interface design and revised the first
! 3807: version of this manual.
! 3808:
! 3809: Brian Beuning and Doug Lea helped with testing of early versions of the
! 3810: library and made creative suggestions.
1.1 maekawa 3811:
3812: John Amanatides of York University in Canada contributed the function
3813: @code{mpz_probab_prime_p}.
3814:
3815: Paul Zimmermann of Inria sparked the development of GMP 2, with his
3816: comparisons between bignum packages.
3817:
3818: Ken Weber (Kent State University, Universidade Federal do Rio Grande do Sul)
3819: contributed @code{mpz_gcd}, @code{mpz_divexact}, @code{mpn_gcd}, and
3820: @code{mpn_bdivmod}, partially supported by CNPq (Brazil) grant 301314194-2.
3821:
1.1.1.2 ! maekawa 3822: Per Bothner of Cygnus Support helped to set up GMP to use Cygnus' configure.
1.1 maekawa 3823: He has also made valuable suggestions and tested numerous intermediary
3824: releases.
3825:
3826: Joachim Hollman was involved in the design of the @code{mpf} interface, and in
3827: the @code{mpz} design revisions for version 2.
3828:
1.1.1.2 ! maekawa 3829: Bennet Yee contributed the functions @code{mpz_jacobi} and @code{mpz_legendre}.
1.1 maekawa 3830:
3831: Andreas Schwab contributed the files @file{mpn/m68k/lshift.S} and
3832: @file{mpn/m68k/rshift.S}.
3833:
1.1.1.2 ! maekawa 3834: The development of floating point functions of GNU MP 2, were supported in part
! 3835: by the ESPRIT-BRA (Basic Research Activities) 6846 project POSSO (POlynomial
! 3836: System SOlving).
! 3837:
! 3838: GNU MP 2 was finished and released by SWOX AB (formerly known as TMG
! 3839: Datakonsult), Swedenborgsgatan 23, SE-118 27 STOCKHOLM, SWEDEN, in
! 3840: cooperation with the IDA Center for Computing Sciences, USA.
1.1 maekawa 3841:
1.1.1.2 ! maekawa 3842: Robert Harley of Inria, France and David Seal of ARM, England, suggested clever
! 3843: improvements for population count.
1.1 maekawa 3844:
1.1.1.2 ! maekawa 3845: Robert Harley also wrote highly optimized Karatsuba and 3-way Toom
! 3846: multiplication functions for GMP 3. He also contributed the ARM assembly
! 3847: code.
1.1 maekawa 3848:
1.1.1.2 ! maekawa 3849: Torsten Ekedahl of the Mathematical department of Stockholm University provided
! 3850: significant inspiration during several phases of the GMP development. His
! 3851: mathematical expertise helped improve several algorithms.
! 3852:
! 3853: Paul Zimmermann wrote the Burnikel-Ziegler division code, the REDC code, the
! 3854: REDC-based mpz_powm code, and the FFT multiply code. The ECMNET project Paul
! 3855: is organizing has been a driving force behind many of the optimization of GMP
! 3856: 3.
! 3857:
! 3858: Linus Nordberg wrote the new configure system based on autoconf and
! 3859: implemented the new random functions.
! 3860:
! 3861: Kent Boortz made the Macintosh port.
! 3862:
! 3863: Kevin Ryde wrote a lot of very high quality x86 code, optimized for most CPU
! 3864: variants. He also made countless other valuable contributions.
! 3865:
! 3866: Steve Root helped write the optimized alpha 21264 assembly code.
! 3867:
! 3868: GNU MP 3.1 was finished and released by Torbjorn Granlund and Kevin Ryde.
! 3869: Torbjorn's work was partially funded by the IDA Center for Computing Sciences,
! 3870: USA.
! 3871:
! 3872: (This list is chronological, not ordered after significance. If you have
! 3873: contributed to GMP but are not listed above, please tell @email{tege@@swox.com}
! 3874: about the omission!)
! 3875:
! 3876: @node References, Concept Index, Contributors, Top
1.1 maekawa 3877: @comment node-name, next, previous, up
3878: @unnumbered References
1.1.1.2 ! maekawa 3879: @cindex References
1.1 maekawa 3880:
3881: @itemize @bullet
3882:
3883: @item
3884: Donald E. Knuth, "The Art of Computer Programming", vol 2,
1.1.1.2 ! maekawa 3885: "Seminumerical Algorithms", 3rd edition, Addison-Wesley, 1988.
1.1 maekawa 3886:
3887: @item
3888: John D. Lipson, "Elements of Algebra and Algebraic Computing",
3889: The Benjamin Cummings Publishing Company Inc, 1981.
3890:
3891: @item
1.1.1.2 ! maekawa 3892: Richard M. Stallman, "Using and Porting GCC", Free Software Foundation, 1999,
! 3893: available online @uref{http://www.gnu.org/software/gcc/onlinedocs/}, and in
! 3894: the GCC package @uref{ftp://ftp.gnu.org/pub/gnu/gcc/}.
1.1 maekawa 3895:
3896: @item
3897: Peter L. Montgomery, "Modular Multiplication Without Trial Division", in
3898: Mathematics of Computation, volume 44, number 170, April 1985.
3899:
3900: @item
3901: Torbjorn Granlund and Peter L. Montgomery, "Division by Invariant
3902: Integers using Multiplication", in Proceedings of the SIGPLAN
1.1.1.2 ! maekawa 3903: PLDI'94 Conference, June 1994. Available online, @*
! 3904: @uref{ftp://ftp.cwi.nl/pub/pmontgom/divcnst.psa4.gz} (and .psl.gz too).
1.1 maekawa 3905:
3906: @item
3907: Tudor Jebelean,
3908: "An algorithm for exact division",
3909: Journal of Symbolic Computation,
3910: v. 15, 1993, pp. 169-180.
1.1.1.2 ! maekawa 3911: Research report version available online @*
! 3912: @uref{ftp://ftp.risc.uni-linz.ac.at/pub/techreports/1992/92-35.ps.gz}
1.1 maekawa 3913:
3914: @item
3915: Kenneth Weber, "The accelerated integer GCD algorithm",
3916: ACM Transactions on Mathematical Software,
3917: v. 21 (March), 1995, pp. 111-122.
1.1.1.2 ! maekawa 3918:
! 3919: @item
! 3920: Christoph Burnikel and Joachim Ziegler, "Fast Recursive Division",
! 3921: Max-Planck-Institut fuer Informatik Research Report MPI-I-98-1-022, @*
! 3922: @uref{http://www.mpi-sb.mpg.de/~ziegler/TechRep.ps.gz}.
! 3923:
! 3924: @item
! 3925: Alfred J. Menezes, Paul C. van Oorschot and Scott A. Vanstone, "Handbook of
! 3926: Applied Cryptography", @uref{http://cacr.math.uwaterloo.ca/hac/}.
! 3927:
! 3928: @item
! 3929: Henri Cohen, "A Course in Computational Algebraic Number Theory", Graduate
! 3930: Texts in Mathematics number 138, Springer-Verlag, 1993. Errata available
! 3931: online @* @uref{http://www.math.u-bordeaux.fr/~cohen}
1.1 maekawa 3932: @end itemize
3933:
1.1.1.2 ! maekawa 3934: @node Concept Index, Function Index, References, Top
1.1 maekawa 3935: @comment node-name, next, previous, up
3936: @unnumbered Concept Index
3937: @printindex cp
3938:
1.1.1.2 ! maekawa 3939: @node Function Index, , Concept Index, Top
1.1 maekawa 3940: @comment node-name, next, previous, up
3941: @unnumbered Function and Type Index
3942: @printindex fn
3943:
3944:
3945: @contents
3946: @bye
1.1.1.2 ! maekawa 3947:
! 3948: @c Local variables:
! 3949: @c fill-column: 78
! 3950: @c End:
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to gmp.texi CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [local] / OpenXM_contrib / gmp