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