1 \input texinfo @c -*-texinfo-*-
9 @comment %**end of header
14 * gmp: (gmp). GNU Multiple Precision Arithmetic Library.
25 @c Note: the edition number is listed in *three* places; please update
26 @c all three. Also, update the month and year where appropriate.
28 @c ==> Update edition number for settitle and subtitle, and in the
29 @c ==> following paragraph; update date, too.
33 This file documents GNU MP, a library for arbitrary-precision arithmetic.
35 Copyright (C) 1991, 1993, 1994, 1995, 1996 Free Software Foundation, Inc.
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.
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).
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.
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
61 @c use the new format for titles
64 @subtitle The GNU Multiple Precision Arithmetic Library
65 @subtitle Edition 2.0.2
68 @author by Torbj@"orn Granlund, TMG Datakonsult
70 @c Include the Distribution inside the titlepage so
71 @c that headings are turned off.
76 \global\baselineskip=13pt
80 @vskip 0pt plus 1filll
81 Copyright @copyright{} 1991, 1993, 1994, 1995, 1996 Free Software Foundation, Inc.
85 Published by the Free Software Foundation @*
86 59 Temple Place - Suite 330 @*
87 Boston, MA 02111-1307, USA @*
89 Permission is granted to make and distribute verbatim copies of
90 this manual provided the copyright notice and this permission notice
91 are preserved on all copies.
93 Permission is granted to copy and distribute modified versions of this
94 manual under the conditions for verbatim copying, provided that the entire
95 resulting derived work is distributed under the terms of a permission
96 notice identical to this one.
98 Permission is granted to copy and distribute translations of this manual
99 into another language, under the above conditions for modified versions,
100 except that this permission notice may be stated in a translation approved
106 @node Top, Copying, (dir), (dir)
110 This manual documents how to install and use the GNU multiple precision
111 arithmetic library, version 2.0.2.
116 * Copying:: GMP Copying Conditions (LGPL).
117 * Introduction to MP:: Brief introduction to GNU MP.
118 * Installing MP:: How to configure and compile the MP library.
119 * MP Basics:: What every MP user should now.
120 * Reporting Bugs:: How to usefully report bugs.
121 * Integer Functions:: Functions for arithmetic on signed integers.
122 * Rational Number Functions:: Functions for arithmetic on rational numbers.
123 * Floating-point Functions:: Functions for arithmetic on floats.
124 * Low-level Functions:: Fast functions for natural numbers.
125 * BSD Compatible Functions:: All functions found in BSD MP.
126 * Custom Allocation:: How to customize the internal allocation.
134 @node Copying, Introduction to MP, Top, Top
135 @comment node-name, next, previous, up
136 @unnumbered GNU MP Copying Conditions
137 @cindex Copying conditions
138 @cindex Conditions for copying GNU MP
140 This library is @dfn{free}; this means that everyone is free to use it and
141 free to redistribute it on a free basis. The library is not in the public
142 domain; it is copyrighted and there are restrictions on its distribution, but
143 these restrictions are designed to permit everything that a good cooperating
144 citizen would want to do. What is not allowed is to try to prevent others
145 from further sharing any version of this library that they might get from
148 Specifically, we want to make sure that you have the right to give away copies
149 of the library, that you receive source code or else can get it if you want
150 it, that you can change this library or use pieces of it in new free programs,
151 and that you know you can do these things.@refill
153 To make sure that everyone has such rights, we have to forbid you to deprive
154 anyone else of these rights. For example, if you distribute copies of the GNU
155 MP library, you must give the recipients all the rights that you have. You
156 must make sure that they, too, receive or can get the source code. And you
157 must tell them their rights.@refill
159 Also, for our own protection, we must make certain that everyone finds out
160 that there is no warranty for the GNU MP library. If it is modified by
161 someone else and passed on, we want their recipients to know that what they
162 have is not what we distributed, so that any problems introduced by others
163 will not reflect on our reputation.@refill
165 The precise conditions of the license for the GNU MP library are found in the
166 Library General Public License that accompany the source code.@refill
168 @node Introduction to MP, Installing MP, Copying, Top
169 @comment node-name, next, previous, up
170 @chapter Introduction to GNU MP
173 GNU MP is a portable library written in C for arbitrary precision arithmetic
174 on integers, rational numbers, and floating-point numbers. It aims to provide
175 the fastest possible arithmetic for all applications that need higher
176 precision than is directly supported by the basic C types.
178 Many applications use just a few hundred bits of precision; but some
179 applications may need thousands or even millions of bits. MP is designed to
180 give good performance for both, by choosing algorithms based on the sizes of
181 the operands, and by carefully keeping the overhead at a minimum.
183 The speed of MP is achieved by using fullwords as the basic arithmetic type,
184 by using sophisticated algorithms, by including carefully optimized assembly
185 code for the most common inner loops for many different CPUs, and by a general
186 emphasis on speed (as opposed to simplicity or elegance).
188 There is carefully optimized assembly code for these CPUs: DEC Alpha, Amd
189 29000, HPPA 1.0 and 1.1, Intel Pentium and generic x86, Intel i960, Motorola
190 MC68000, MC68020, MC88100, and MC88110, Motorola/IBM PowerPC, National
191 NS32000, IBM POWER, MIPS R3000, R4000, SPARCv7, SuperSPARC, generic SPARCv8,
192 and DEC VAX. Some optimizations also for ARM, Clipper, IBM ROMP (RT), and
195 This version of MP is released under a more liberal license than previous
196 versions. It is now permitted to link MP to non-free programs, as long as MP
197 source code is provided when distributing the non-free program.
200 @section How to use this Manual
202 Everyone should read @ref{MP Basics}. If you need to install the library
203 yourself, you need to read @ref{Installing MP}, too.
205 The rest of the manual can be used for later reference, although it is
206 probably a good idea to glance through it.
209 @node Installing MP, MP Basics, Introduction to MP, Top
210 @comment node-name, next, previous, up
211 @chapter Installing MP
214 To build MP, you first have to configure it for your CPU and operating system.
215 You need a C compiler, preferably GCC, but any reasonable compiler should
216 work. And you need a standard Unix @samp{make} program, plus some other
217 standard Unix utility programs.
219 (If you're on an MS-DOS machine, your can build MP using @file{make.bat}. It
220 requires that djgpp is installed. It does not require configuration, nor is
221 @samp{make} needed; @file{make.bat} both configures and builds the library.)
223 Here are the steps needed to install the library on Unix systems:
227 In most cases, @samp{./configure --target=cpu-vendor-os}, should work both for
228 native and cross-compilation. If you get error messages, your machine might
231 If you want to compile in a separate object directory, cd to that directory,
232 and prefix the configure command with the path to the MP source directory.
233 Not all @samp{make} programs have the necessary features to support this. In
234 particular, SunOS and Slowaris @samp{make} have bugs that makes them unable to
235 build from a separate object directory. Use GNU @samp{make} instead.
237 In addition to the standard cpu-vendor-os tuples, MP recognizes sparc8 and
238 supersparc as valid CPU names. Specifying these CPU names for relevant
239 systems will improve performance significantly.
241 In general, if you want a library that runs as fast as possible, you should
242 make sure you configure MP for the exact CPU type your system uses.
244 If you have @code{gcc} in your @code{PATH}, it will be used by default. To
245 override this, pass @samp{-with-gcc=no} to @file{configure}.
250 This will compile MP, and create a library archive file @file{libgmp.a} in the
256 This will make sure MP was built correctly. If you get error messages, please
257 report this to @samp{bug-gmp@@prep.ai.mit.edu}. (@xref{Reporting Bugs}, for
258 information on what to include in useful bug reports.)
263 This will copy the file @file{gmp.h} and @file{libgmp.a}, as well as the info
264 files, to @file{/usr/local} (or if you passed the @samp{--prefix} option to
265 @file{configure}, to the directory given as argument to @samp{--prefix}).
269 If you wish to build and install the BSD MP compatible functions, use
270 @samp{make libmp.a} and @samp{make install-bsdmp}.
272 There are some other useful make targets:
278 Create a DVI version of the manual, in @file{gmp.dvi} and a set of info files,
279 in @file{gmp.info}, @file{gmp.info-1}, @file{gmp.info-2}, etc.
284 Create a Postscript version of the manual, in @file{gmp.ps}.
289 Create a HTML version of the manual, in @file{gmp.html}.
294 Delete all object files and archive files, but not the configuration files.
299 Delete all files not included in the distribution.
304 Delete all files copied by @samp{make install}.
308 @section Known Build Problems
310 GCC 2.7.2 (as well as 2.6.3) for the RS/6000 and PowerPC can not be used to
311 compile MP, due to a bug in GCC. If you want to use GCC for these machines,
312 you need to apply the patch below to GCC, or use a later version of the
315 If you are on a Sequent Symmetry, use the GNU assembler instead of the
316 system's assembler, since the latter has serious bugs.
318 The system compiler on NeXT is a massacred and old gcc, even if the compiler
319 calls itself @file{cc}. This compiler cannot be used to build MP. You need
320 to get a real gcc, and install that before you compile MP. (NeXT might have
321 fixed this in newer releases of their system.)
323 The system C compiler under SunOS 4 has a bug that makes it miscompile
324 mpq/get_d.c. This will make @samp{make check} fail.
326 Please report other problems to @samp{bug-gmp@@prep.ai.mit.edu}.
327 @xref{Reporting Bugs}.
330 Patch to apply to GCC 2.6.3 and 2.7.2:
333 *** config/rs6000/rs6000.md Sun Feb 11 08:22:11 1996
334 --- config/rs6000/rs6000.md.new Sun Feb 18 03:33:37 1996
337 (set (match_operand:SI 0 "gpc_reg_operand" "=r")
338 (not:SI (match_dup 1)))]
341 [(set_attr "type" "compare")])
345 (set (match_operand:SI 0 "gpc_reg_operand" "=r")
346 (not:SI (match_dup 1)))]
349 [(set_attr "type" "compare")])
354 @node MP Basics, Reporting Bugs, Installing MP, Top
355 @comment node-name, next, previous, up
360 All declarations needed to use MP are collected in the include file
361 @file{gmp.h}. It is designed to work with both C and C++ compilers.
364 @section Nomenclature and Types
369 In this manual, @dfn{integer} usually means a multiple precision integer, as
370 defined by the MP library. The C data type for such integers is @code{mpz_t}.
371 Here are some examples of how to declare such integers:
376 struct foo @{ mpz_t x, y; @};
381 @cindex Rational number
384 @dfn{Rational number} means a multiple precision fraction. The C data type
385 for these fractions is @code{mpq_t}. For example:
391 @cindex Floating-point number
394 @dfn{Floating point number} or @dfn{Float} for short, is an arbitrary precision
395 mantissa with an limited precision exponent. The C data type for such objects
399 @tindex @code{mp_limb_t}
401 A @dfn{limb} means the part of a multi-precision number that fits in a single
402 word. (We chose this word because a limb of the human body is analogous to a
403 digit, only larger, and containing several digits.) Normally a limb contains
404 32 or 64 bits. The C data type for a limb is @code{mp_limb_t}.
407 @section Function Classes
409 There are six classes of functions in the MP library:
413 Functions for signed integer arithmetic, with names beginning with
414 @code{mpz_}. The associated type is @code{mpz_t}. There are about 100
415 functions in this class.
418 Functions for rational number arithmetic, with names beginning with
419 @code{mpq_}. The associated type is @code{mpq_t}. There are about 20
420 functions in this class, but the functions in the previous class can be used
421 for performing arithmetic on the numerator and denominator separately.
424 Functions for floating-point arithmetic, with names beginning with
425 @code{mpf_}. The associated type is @code{mpf_t}. There are about 50
426 functions is this class.
429 Functions compatible with Berkeley MP, such as @code{itom}, @code{madd}, and
430 @code{mult}. The associated type is @code{MINT}.
433 Fast low-level functions that operate on natural numbers. These are used by
434 the functions in the preceding groups, and you can also call them directly
435 from very time-critical user programs. These functions' names begin with
436 @code{mpn_}. There are about 30 (hard-to-use) functions in this class.
438 The associated type is array of @code{mp_limb_t}.
441 Miscellaneous functions. Functions for setting up custom allocation.
445 @section MP Variable Conventions
447 As a general rule, all MP functions expect output arguments before input
448 arguments. This notation is based on an analogy with the assignment operator.
449 (The BSD MP compatibility functions disobey this rule, having the output
452 MP allows you to use the same variable for both input and output in the same
453 expression. For example, the main function for integer multiplication,
454 @code{mpz_mul}, can be used like this: @code{mpz_mul (x, x, x)}. This
455 computes the square of @var{x} and puts the result back in @var{x}.
457 Before you can assign to an MP variable, you need to initialize it by calling
458 one of the special initialization functions. When you're done with a
459 variable, you need to clear it out, using one of the functions for that
460 purpose. Which function to use depends on the type of variable. See the
461 chapters on integer functions, rational number functions, and floating-point
462 functions for details.
464 A variable should only be initialized once, or at least cleared out between
465 each initialization. After a variable has been initialized, it may be
466 assigned to any number of times.
468 For efficiency reasons, avoid to initialize and clear out a variable in loops.
469 Instead, initialize it before entering the loop, and clear it out after the
472 You don't need to be concerned about allocating additional space for MP
473 variables. All functions in MP automatically allocate additional space when a
474 variable does not already have enough space. They do not, however, reduce the
475 space when a smaller number is stored in the object. Most of the time, this
476 policy is best, since it avoids frequent re-allocation.
479 @section Useful Macros and Constants
481 @deftypevr {Global Constant} {const int} mp_bits_per_limb
482 The number of bits per limb.
485 @defmac __GNU_MP_VERSION
486 @defmacx __GNU_MP_VERSION_MINOR
487 The major and minor MP version, respectively, as integers.
490 @section Compatibility with Version 1.x
492 This version of MP is upward compatible with previous versions of MP, with a
496 @item Integer division functions round the result differently. The old
497 functions (@code{mpz_div}, @code{mpz_divmod}, @code{mpz_mdiv},
498 @code{mpz_mdivmod}, etc) now all use floor rounding (i.e., they round the
499 quotient to @minus{}infinity). There are a lot of new functions for integer
500 division, giving the user better control over the rounding.
502 @item The function @code{mpz_mod} now compute the true @strong{mod} function.
504 @item The functions @code{mpz_powm} and @code{mpz_powm_ui} now use
505 @strong{mod} for reduction.
507 @item The assignment functions for rational numbers do no longer canonicalize
508 their results. In the case a non-canonical result could arise from an
509 assignment, the user need to insert an explicit call to
510 @code{mpq_canonicalize}. This change was made for efficiency.
512 @item Output generated by @code{mpz_out_raw} in this release cannot be read
513 by @code{mpz_inp_raw} in previous releases. This change was made for making
514 the file format truly portable between machines with different word sizes.
516 @item Several @code{mpn} functions have changed. But they were intentionally
517 undocumented in previous releases.
519 @item The functions @code{mpz_cmp_ui}, @code{mpz_cmp_si}, and @code{mpq_cmp_ui}
520 are now implementated as macros, and thereby sometimes evaluate their
521 arguments multiple times.
523 @item The functions @code{mpz_pow_ui} and @code{mpz_ui_pow_ui} now yield 1
524 for 0^0. (In version 1, they yielded 0.)
529 @section Getting the Latest Version of MP
531 The latest version of the MP library is available by anonymous ftp from
532 from @samp{prep.ai.mit.edu}. The file name is
533 @file{/pub/gnu/gmp-M.N.tar.gz}. Many sites around the world mirror
534 @samp{prep}; please use a mirror site near you.
536 @node Reporting Bugs, Integer Functions, MP Basics, Top
537 @comment node-name, next, previous, up
538 @chapter Reporting Bugs
539 @cindex Reporting bugs
541 If you think you have found a bug in the MP library, please investigate it and
542 report it. We have made this library available to you, and it is not to ask
543 too much from you, to ask you to report the bugs that you find.
545 There are a few things you should think about when you put your bug report
548 You have to send us a test case that makes it possible for us to reproduce the
549 bug. Include instructions on how to run the test case.
551 You also have to explain what is wrong; if you get a crash, or if the results
552 printed are incorrect and in that case, in what way.
554 It is not uncommon that an observed problem is actually due to a bug in the
555 compiler used when building MP; the MP code tends to explore interesting
556 corners in compilers. Therefore, please include compiler version information
557 in your bug report. This can be extracted using @samp{what `which cc`}, or,
558 if you're using gcc, @samp{gcc -v}. Also, include the output from @samp{uname
561 If your bug report is good, we will do our best to help you to get a corrected
562 version of the library; if the bug report is poor, we won't do anything about
563 it (aside of chiding you to send better bug reports).
565 Send your bug report to: @samp{bug-gmp@@prep.ai.mit.edu}.
567 If you think something in this manual is unclear, or downright incorrect, or if
568 the language needs to be improved, please send a note to the same address.
571 @node Integer Functions, Rational Number Functions, Reporting Bugs, Top
572 @comment node-name, next, previous, up
573 @chapter Integer Functions
574 @cindex Integer functions
576 This chapter describes the MP functions for performing integer arithmetic.
577 These functions start with the prefix @code{mpz_}.
579 Arbitrary precision integers are stored in objects of type @code{mpz_t}.
582 * Initializing Integers::
583 * Assigning Integers::
584 * Simultaneous Integer Init & Assign::
585 * Converting Integers::
586 * Integer Arithmetic::
587 * Comparison Functions::
588 * Integer Logic and Bit Fiddling::
590 * Miscellaneous Integer Functions::
593 @node Initializing Integers, Assigning Integers, , Integer Functions
594 @comment node-name, next, previous, up
595 @section Initialization and Assignment Functions
597 The functions for integer arithmetic assume that all integer objects are
598 initialized. You do that by calling the function @code{mpz_init}.
600 @deftypefun void mpz_init (mpz_t @var{integer})
601 Initialize @var{integer} with limb space and set the initial numeric value to
602 0. Each variable should normally only be initialized once, or at least cleared
603 out (using @code{mpz_clear}) between each initialization.
606 Here is an example of using @code{mpz_init}:
613 mpz_add (integ, @dots{});
615 mpz_sub (integ, @dots{});
617 /* Unless the program is about to exit, do ... */
623 As you can see, you can store new values any number of times, once an
624 object is initialized.
626 @deftypefun void mpz_clear (mpz_t @var{integer})
627 Free the limb space occupied by @var{integer}. Make sure to call this
628 function for all @code{mpz_t} variables when you are done with them.
631 @deftypefun {void *} _mpz_realloc (mpz_t @var{integer}, mp_size_t @var{new_alloc})
632 Change the limb space allocation to @var{new_alloc} limbs. This function is
633 not normally called from user code, but it can be used to give memory back to
634 the heap, or to increase the space of a variable to avoid repeated automatic
638 @deftypefun void mpz_array_init (mpz_t @var{integer_array}[], size_t @var{array_size}, mp_size_t @var{fixed_num_bits})
639 Allocate @strong{fixed} limb space for all @var{array_size} integers in
640 @var{integer_array}. The fixed allocation for each integer in the array is
641 enough to store @var{fixed_num_bits}. If the fixed space will be insufficient
642 for storing the result of a subsequent calculation, the result is
645 This function is useful for decreasing the working set for some algorithms
646 that use large integer arrays.
648 There is no way to de-allocate the storage allocated by this function.
649 Don't call @code{mpz_clear}!
653 @node Assigning Integers, Simultaneous Integer Init & Assign, Initializing Integers, Integer Functions
654 @comment node-name, next, previous, up
655 @subsection Assignment Functions
656 @cindex Integer assignment functions
658 These functions assign new values to already initialized integers
659 (@pxref{Initializing Integers}).
661 @deftypefun void mpz_set (mpz_t @var{rop}, mpz_t @var{op})
662 @deftypefunx void mpz_set_ui (mpz_t @var{rop}, unsigned long int @var{op})
663 @deftypefunx void mpz_set_si (mpz_t @var{rop}, signed long int @var{op})
664 @deftypefunx void mpz_set_d (mpz_t @var{rop}, double @var{op})
665 @deftypefunx void mpz_set_q (mpz_t @var{rop}, mpq_t @var{op})
666 @deftypefunx void mpz_set_f (mpz_t @var{rop}, mpf_t @var{op})
667 Set the value of @var{rop} from @var{op}.
670 @deftypefun int mpz_set_str (mpz_t @var{rop}, char *@var{str}, int @var{base})
671 Set the value of @var{rop} from @var{str}, a '\0'-terminated C string in base
672 @var{base}. White space is allowed in the string, and is simply ignored. The
673 base may vary from 2 to 36. If @var{base} is 0, the actual base is determined
674 from the leading characters: if the first two characters are `0x' or `0X',
675 hexadecimal is assumed, otherwise if the first character is `0', octal is
676 assumed, otherwise decimal is assumed.
678 This function returns 0 if the entire string up to the '\0' is a valid
679 number in base @var{base}. Otherwise it returns @minus{}1.
683 @node Simultaneous Integer Init & Assign, Converting Integers, Assigning Integers, Integer Functions
684 @comment node-name, next, previous, up
685 @subsection Combined Initialization and Assignment Functions
686 @cindex Initialization and assignment functions
688 For convenience, MP provides a parallel series of initialize-and-set functions
689 which initialize the output and then store the value there. These functions'
690 names have the form @code{mpz_init_set@dots{}}
692 Here is an example of using one:
697 mpz_init_set_str (pie, "3141592653589793238462643383279502884", 10);
699 mpz_sub (pie, @dots{});
706 Once the integer has been initialized by any of the @code{mpz_init_set@dots{}}
707 functions, it can be used as the source or destination operand for the ordinary
708 integer functions. Don't use an initialize-and-set function on a variable
711 @deftypefun void mpz_init_set (mpz_t @var{rop}, mpz_t @var{op})
712 @deftypefunx void mpz_init_set_ui (mpz_t @var{rop}, unsigned long int @var{op})
713 @deftypefunx void mpz_init_set_si (mpz_t @var{rop}, signed long int @var{op})
714 @deftypefunx void mpz_init_set_d (mpz_t @var{rop}, double @var{op})
715 Initialize @var{rop} with limb space and set the initial numeric value from
719 @deftypefun int mpz_init_set_str (mpz_t @var{rop}, char *@var{str}, int @var{base})
720 Initialize @var{rop} and set its value like @code{mpz_set_str} (see its
721 documentation above for details).
723 If the string is a correct base @var{base} number, the function returns 0;
724 if an error occurs it returns @minus{}1. @var{rop} is initialized even if
725 an error occurs. (I.e., you have to call @code{mpz_clear} for it.)
729 @node Converting Integers, Integer Arithmetic, Simultaneous Integer Init & Assign, Integer Functions
730 @comment node-name, next, previous, up
731 @section Conversion Functions
732 @cindex Integer conversion functions
733 @cindex Conversion functions
735 This section describes functions for converting arbitrary precision integers
736 to standard C types. Functions for converting @emph{to} arbitrary
737 precision integers are described in @ref{Assigning Integers} and @ref{I/O of
740 @deftypefun {unsigned long int} mpz_get_ui (mpz_t @var{op})
741 Return the least significant part from @var{op}. This function combined
742 with @* @code{mpz_tdiv_q_2exp(@dots{}, @var{op}, CHAR_BIT*sizeof(unsigned
743 long int))} can be used to extract the limbs of an integer.
746 @deftypefun {signed long int} mpz_get_si (mpz_t @var{op})
747 If @var{op} fits into a @code{signed long int} return the value of @var{op}.
748 Otherwise return the least significant part of @var{op}, with the same sign
751 If @var{op} is too large to fit in a @code{signed long int}, the returned
752 result is probably not very useful. @c To find out if the value will fit, use
753 @c the function @code{mpz_fits_si}.
756 @deftypefun double mpz_get_d (mpz_t @var{op})
757 Convert @var{op} to a double.
760 @deftypefun {char *} mpz_get_str (char *@var{str}, int @var{base}, mpz_t @var{op})
761 Convert @var{op} to a string of digits in base @var{base}. The base may vary
764 If @var{str} is NULL, space for the result string is allocated using the
765 default allocation function, and a pointer to the string is returned.
767 If @var{str} is not NULL, it should point to a block of storage enough large
768 for the result. To find out the right amount of space to provide for
769 @var{str}, use @code{mpz_sizeinbase (@var{op}, @var{base}) + 2}. The two
770 extra bytes are for a possible minus sign, and for the terminating null
775 @node Integer Arithmetic, Comparison Functions, Converting Integers, Integer Functions
776 @comment node-name, next, previous, up
777 @section Arithmetic Functions
778 @cindex Integer arithmetic functions
779 @cindex Arithmetic functions
781 @deftypefun void mpz_add (mpz_t @var{rop}, mpz_t @var{op1}, mpz_t @var{op2})
782 @deftypefunx void mpz_add_ui (mpz_t @var{rop}, mpz_t @var{op1}, unsigned long int @var{op2})
784 Set @var{rop} to @var{op1} + @var{op2}.
788 Set @var{rop} to $@var{op1} + @var{op2}$.
793 @deftypefun void mpz_sub (mpz_t @var{rop}, mpz_t @var{op1}, mpz_t @var{op2})
794 @deftypefunx void mpz_sub_ui (mpz_t @var{rop}, mpz_t @var{op1}, unsigned long int @var{op2})
795 Set @var{rop} to @var{op1} @minus{} @var{op2}.
798 @deftypefun void mpz_mul (mpz_t @var{rop}, mpz_t @var{op1}, mpz_t @var{op2})
799 @deftypefunx void mpz_mul_ui (mpz_t @var{rop}, mpz_t @var{op1}, unsigned long int @var{op2})
801 Set @var{rop} to @var{op1} times @var{op2}.
805 Set @var{rop} to $@var{op1} \times @var{op2}$.
810 @deftypefun void mpz_mul_2exp (mpz_t @var{rop}, mpz_t @var{op1}, unsigned long int @var{op2})
812 Set @var{rop} to @var{op1} times 2 raised to @var{op2}. This operation can
813 also be defined as a left shift, @var{op2} steps.
817 Set @var{rop} to $@var{op1} \times 2^{op2}$. This operation can also be
818 defined as a left shift, @var{op2} steps.
823 @deftypefun void mpz_neg (mpz_t @var{rop}, mpz_t @var{op})
824 Set @var{rop} to @minus{}@var{op}.
827 @deftypefun void mpz_abs (mpz_t @var{rop}, mpz_t @var{op})
828 Set @var{rop} to the absolute value of @var{op}.
831 @deftypefun void mpz_fac_ui (mpz_t @var{rop}, unsigned long int @var{op})
832 Set @var{rop} to @var{op}!, the factorial of @var{op}.
835 @subsection Division functions
837 Division is undefined if the divisor is zero, and passing a zero divisor to
838 the divide or modulo functions, as well passing a zero mod argument to the
839 @code{mpz_powm} and @code{mpz_powm_ui} functions, will make these functions
840 intentionally divide by zero. This gives the user the possibility to handle
841 arithmetic exceptions in these functions in the same manner as other
842 arithmetic exceptions.
844 There are three main groups of division functions:
847 Functions that truncate the quotient towards 0. The names of these
848 functions start with @code{mpz_tdiv}. The @samp{t} in the name is short for
851 Functions that round the quotient towards @minus{}infinity. The names of
852 these routines start with @code{mpz_fdiv}. The @samp{f} in the name is
853 short for @samp{floor}.
855 Functions that round the quotient towards +infinity. The names of
856 these routines start with @code{mpz_cdiv}. The @samp{c} in the name is
857 short for @samp{ceil}.
860 For each rounding mode, there are a couple of variants. Here @samp{q} means
861 that the quotient is computed, while @samp{r} means that the remainder is
862 computed. Functions that compute both the quotient and remainder have
863 @samp{qr} in the name.
865 @deftypefun void mpz_tdiv_q (mpz_t @var{rop}, mpz_t @var{op1}, mpz_t @var{op2})
866 @deftypefunx void mpz_tdiv_q_ui (mpz_t @var{rop}, mpz_t @var{op1}, unsigned long int @var{op2})
867 Set @var{rop} to [@var{op1}/@var{op2}]. The quotient is truncated towards
871 @deftypefun void mpz_tdiv_r (mpz_t @var{rop}, mpz_t @var{op1}, mpz_t @var{op2})
872 @deftypefunx void mpz_tdiv_r_ui (mpz_t @var{rop}, mpz_t @var{op1}, unsigned long int @var{op2})
873 Set @var{rop} to (@var{op1} - [@var{op1}/@var{op2}] * @var{op2}).
874 Unless the remainder is zero, it has the same sign as the dividend.
877 @deftypefun void mpz_tdiv_qr (mpz_t @var{rop1}, mpz_t @var{rop2}, mpz_t @var{op1}, mpz_t @var{op2})
878 @deftypefunx void mpz_tdiv_qr_ui (mpz_t @var{rop1}, mpz_t @var{rop2}, mpz_t @var{op1}, unsigned long int @var{op2})
879 Divide @var{op1} by @var{op2} and put the quotient in @var{rop1} and the
880 remainder in @var{rop2}. The quotient is rounded towards 0. Unless the
881 remainder is zero, it has the same sign as the dividend.
883 If @var{rop1} and @var{rop2} are the same variable, the results are
887 @deftypefun void mpz_fdiv_q (mpz_t @var{rop1}, mpz_t @var{op1}, mpz_t @var{op2})
888 @deftypefunx void mpz_fdiv_q_ui (mpz_t @var{rop}, mpz_t @var{op1}, unsigned long int @var{op2})
890 Set @var{rop} to @var{op1}/@var{op2}. The quotient is rounded towards
895 Set @var{rop} to $\lfloor@var{op1}/@var{op2}\rfloor$. (I.e., round
896 the quotient towards $-\infty$.)
901 @deftypefun void mpz_fdiv_r (mpz_t @var{rop}, mpz_t @var{op1}, mpz_t @var{op2})
902 @deftypefunx {unsigned long int} mpz_fdiv_r_ui (mpz_t @var{rop}, mpz_t @var{op1}, unsigned long int @var{op2})
903 Divide @var{op1} by @var{op2} and put the remainder in @var{rop}. Unless
904 the remainder is zero, it has the same sign as the divisor.
906 For @code{mpz_fdiv_r_ui} the remainder is small enough to fit in an
907 @code{unsigned long int}, and is therefore returned.
910 @deftypefun void mpz_fdiv_qr (mpz_t @var{rop1}, mpz_t @var{rop2}, mpz_t @var{op1}, mpz_t @var{op2})
911 @deftypefunx {unsigned long int} mpz_fdiv_qr_ui (mpz_t @var{rop1}, mpz_t @var{rop2}, mpz_t @var{op1}, unsigned long int @var{op2})
912 Divide @var{op1} by @var{op2} and put the quotient in @var{rop1} and the
913 remainder in @var{rop2}. The quotient is rounded towards @minus{}infinity.
914 Unless the remainder is zero, it has the same sign as the divisor.
916 For @code{mpz_fdiv_qr_ui} the remainder is small enough to fit in an
917 @code{unsigned long int}, and is therefore returned.
919 If @var{rop1} and @var{rop2} are the same variable, the results are
923 @deftypefun {unsigned long int} mpz_fdiv_ui (mpz_t @var{op1}, unsigned long int @var{op2})
924 This function is similar to @code{mpz_fdiv_r_ui}, but the remainder is only
925 returned; it is not stored anywhere.
928 @deftypefun void mpz_cdiv_q (mpz_t @var{rop1}, mpz_t @var{op1}, mpz_t @var{op2})
929 @deftypefunx void mpz_cdiv_q_ui (mpz_t @var{rop}, mpz_t @var{op1}, unsigned long int @var{op2})
931 Set @var{rop} to @var{op1}/@var{op2}. The quotient is rounded towards
936 Set @var{rop} to $\lceil@var{op1}/@var{op2}\rceil$. (I.e., round the
937 quotient towards $+\infty$.)
942 @deftypefun void mpz_cdiv_r (mpz_t @var{rop}, mpz_t @var{op1}, mpz_t @var{op2})
943 @deftypefunx {unsigned long int} mpz_cdiv_r_ui (mpz_t @var{rop}, mpz_t @var{op1}, unsigned long int @var{op2})
944 Divide @var{op1} by @var{op2} and put the remainder in @var{rop}. Unless
945 the remainder is zero, it has the opposite sign as the divisor.
947 For @code{mpz_cdiv_r_ui} the negated remainder is small enough to fit in an
948 @code{unsigned long int}, and it is therefore returned.
951 @deftypefun void mpz_cdiv_qr (mpz_t @var{rop1}, mpz_t @var{rop2}, mpz_t @var{op1}, mpz_t @var{op2})
952 @deftypefunx {unsigned long int} mpz_cdiv_qr_ui (mpz_t @var{rop1}, mpz_t @var{rop2}, mpz_t @var{op1}, unsigned long int @var{op2})
953 Divide @var{op1} by @var{op2} and put the quotient in @var{rop1} and the
954 remainder in @var{rop2}. The quotient is rounded towards +infinity. Unless
955 the remainder is zero, it has the opposite sign as the divisor.
957 For @code{mpz_cdiv_qr_ui} the negated remainder is small enough to fit in an
958 @code{unsigned long int}, and it is therefore returned.
960 If @var{rop1} and @var{rop2} are the same variable, the results are
964 @deftypefun {unsigned long int} mpz_cdiv_ui (mpz_t @var{op1}, unsigned long int @var{op2})
965 Return the negated remainder, similar to @code{mpz_cdiv_r_ui}. (The
966 difference is that this function doesn't store the remainder anywhere.)
969 @deftypefun void mpz_mod (mpz_t @var{rop}, mpz_t @var{op1}, mpz_t @var{op2})
970 @deftypefunx {unsigned long int} mpz_mod_ui (mpz_t @var{rop}, mpz_t @var{op1}, unsigned long int @var{op2})
971 Set @var{rop} to @var{op1} @code{mod} @var{op2}. The sign of the divisor is
972 ignored, and the result is always non-negative.
974 For @code{mpz_mod_ui} the remainder is small enough to fit in an
975 @code{unsigned long int}, and is therefore returned.
978 @deftypefun void mpz_divexact (mpz_t @var{rop}, mpz_t @var{op1}, mpz_t @var{op2})
979 Set @var{rop} to @var{op1}/@var{op2}. This function produces correct
980 results only when it is known in advance that @var{op2} divides
983 Since mpz_divexact is much faster than any of the other routines that produce
984 the quotient (@pxref{References} Jebelean), it is the best choice for
985 instances in which exact division is known to occur, such as reducing a
986 rational to lowest terms.
989 @deftypefun void mpz_tdiv_q_2exp (mpz_t @var{rop}, mpz_t @var{op1}, unsigned long int @var{op2})
991 Set @var{rop} to @var{op1} divided by 2 raised to @var{op2}. The quotient is
996 Set @var{rop} to $@var{op1}/2^{op2}$. The quotient is rounded towards 0.
1001 @deftypefun void mpz_tdiv_r_2exp (mpz_t @var{rop}, mpz_t @var{op1}, unsigned long int @var{op2})
1003 Divide @var{op1} by (2 raised to @var{op2}) and put the remainder in
1004 @var{rop}. Unless it is zero, @var{rop} will have the same sign as @var{op1}.
1008 Divide @var{op1} by $2^{op2}$ and put the remainder in @var{rop}. Unless it is
1009 zero, @var{rop} will have the same sign as @var{op1}.
1014 @deftypefun void mpz_fdiv_q_2exp (mpz_t @var{rop}, mpz_t @var{op1}, unsigned long int @var{op2})
1016 Set @var{rop} to @var{op1} divided by 2 raised to @var{op2}. The quotient is
1017 rounded towards @minus{}infinity.
1021 Set @var{rop} to $\lfloor@var{op1}/2^{op2}\rfloor$. The quotient is rounded
1027 @deftypefun void mpz_fdiv_r_2exp (mpz_t @var{rop}, mpz_t @var{op1}, unsigned long int @var{op2})
1029 Divide @var{op1} by (2 raised to @var{op2}) and put the remainder in
1030 @var{rop}. The sign of @var{rop} will always be positive.
1034 Divide @var{op1} by $2^{op2}$ and put the remainder in @var{rop}. The sign of
1035 @var{rop} will always be positive.
1039 This operation can also be defined as masking of the @var{op2} least
1043 @subsection Exponentialization Functions
1045 @deftypefun void mpz_powm (mpz_t @var{rop}, mpz_t @var{base}, mpz_t @var{exp}, mpz_t @var{mod})
1046 @deftypefunx void mpz_powm_ui (mpz_t @var{rop}, mpz_t @var{base}, unsigned long int @var{exp}, mpz_t @var{mod})
1047 Set @var{rop} to (@var{base} raised to @var{exp}) @code{mod} @var{mod}. If
1048 @var{exp} is negative, the result is undefined.
1051 @deftypefun void mpz_pow_ui (mpz_t @var{rop}, mpz_t @var{base}, unsigned long int @var{exp})
1052 @deftypefunx void mpz_ui_pow_ui (mpz_t @var{rop}, unsigned long int @var{base}, unsigned long int @var{exp})
1053 Set @var{rop} to @var{base} raised to @var{exp}.
1055 The case of 0^0 yields 1.
1059 The case of $0^0$ yields 1.
1064 @subsection Square Root Functions
1066 @deftypefun void mpz_sqrt (mpz_t @var{rop}, mpz_t @var{op})
1068 Set @var{rop} to the truncated integer part of the square root of
1073 Set @var{rop} to $\lfloor\sqrt{@var{op}}\rfloor$, the truncated integer
1074 part of the square root of @var{op}.
1079 @deftypefun void mpz_sqrtrem (mpz_t @var{rop1}, mpz_t @var{rop2}, mpz_t @var{op})
1081 Set @var{rop1} to the truncated integer part of the square root of @var{op},
1082 like @code{mpz_sqrt}. Set @var{rop2} to
1083 @var{op}@minus{}@var{rop1}*@var{rop1},
1087 Set @var{rop1} to $\lfloor\sqrt{@var{op}}\rfloor$, like @code{mpz_sqrt}.
1088 Set @var{rop2} to $(@var{op} - @var{rop1}^2)$,
1091 (i.e., zero if @var{op} is a perfect square).
1093 If @var{rop1} and @var{rop2} are the same variable, the results are
1097 @deftypefun int mpz_perfect_square_p (mpz_t @var{op})
1098 Return non-zero if @var{op} is a perfect square, i.e., if the square root of
1099 @var{op} is an integer. Return zero otherwise.
1102 @subsection Number Theoretic Functions
1104 @deftypefun int mpz_probab_prime_p (mpz_t @var{op}, int @var{reps})
1106 If this function returns 0, @var{op} is definitely not prime. If it returns
1107 1, then @var{op} is `probably' prime. The probability of a false positive is
1112 If this function returns 0, @var{op} is definitely not prime. If it returns
1113 1, then @var{op} is `probably' prime. The probability of a false positive is
1117 A reasonable value of reps is 25.
1119 An implementation of the probabilistic primality test found in Seminumerical
1120 Algorithms (@pxref{References} Knuth).
1123 @deftypefun void mpz_gcd (mpz_t @var{rop}, mpz_t @var{op1}, mpz_t @var{op2})
1124 Set @var{rop} to the greatest common divisor of @var{op1} and @var{op2}.
1127 @deftypefun {unsigned long int} mpz_gcd_ui (mpz_t @var{rop}, mpz_t @var{op1}, unsigned long int @var{op2})
1128 Compute the greatest common divisor of @var{op1} and @var{op2}. If
1129 @var{rop} is not NULL, store the result there.
1131 If the result is small enough to fit in an @code{unsigned long int}, it is
1132 returned. If the result does not fit, 0 is returned, and the result is equal
1133 to the argument @var{op1}. Note that the result will always fit if @var{op2}
1137 @deftypefun void mpz_gcdext (mpz_t @var{g}, mpz_t @var{s}, mpz_t @var{t}, mpz_t @var{a}, mpz_t @var{b})
1138 Compute @var{g}, @var{s}, and @var{t}, such that @var{a}@var{s} +
1139 @var{b}@var{t} = @var{g} = @code{gcd} (@var{a}, @var{b}). If @var{t} is
1140 NULL, that argument is not computed.
1143 @deftypefun int mpz_invert (mpz_t @var{rop}, mpz_t @var{op1}, mpz_t @var{op2})
1144 Compute the inverse of @var{op1} modulo @var{op2} and put the result in
1145 @var{rop}. Return non-zero if an inverse exist, zero otherwise. When the
1146 function returns zero, do not assume anything about the value in @var{rop}.
1149 @deftypefun int mpz_jacobi (mpz_t @var{op1}, mpz_t @var{op2})
1150 @deftypefunx int mpz_legendre (mpz_t @var{op1}, mpz_t @var{op2})
1151 Compute the Jacobi and Legendre symbols, respectively.
1155 @node Comparison Functions, Integer Logic and Bit Fiddling, Integer Arithmetic, Integer Functions
1156 @comment node-name, next, previous, up
1157 @section Comparison Functions
1159 @deftypefun int mpz_cmp (mpz_t @var{op1}, mpz_t @var{op2})
1161 Compare @var{op1} and @var{op2}. Return a positive value if @var{op1} >
1162 @var{op2}, zero if @var{op1} = @var{op2}, and a negative value if @var{op1} <
1167 Compare @var{op1} and @var{op2}. Return a positive value if $@var{op1} >
1168 @var{op2}$, zero if $@var{op1} = @var{op2}$, and a negative value if $@var{op1}
1174 @deftypefn Macro int mpz_cmp_ui (mpz_t @var{op1}, unsigned long int @var{op2})
1175 @deftypefnx Macro int mpz_cmp_si (mpz_t @var{op1}, signed long int @var{op2})
1177 Compare @var{op1} and @var{op2}. Return a positive value if @var{op1} >
1178 @var{op2}, zero if @var{op1} = @var{op2}, and a negative value if @var{op1} <
1183 Compare @var{op1} and @var{op2}. Return a positive value if $@var{op1} >
1184 @var{op2}$, zero if $@var{op1} = @var{op2}$, and a negative value if $@var{op1}
1189 These functions are actually implemented as macros. They evaluate their
1190 arguments multiple times.
1193 @deftypefn Macro int mpz_sgn (mpz_t @var{op})
1195 Return +1 if @var{op} > 0, 0 if @var{op} = 0, and @minus{}1 if @var{op} < 0.
1199 Return $+1$ if $@var{op} > 0$, 0 if $@var{op} = 0$, and $-1$ if $@var{op} < 0$.
1203 This function is actually implemented as a macro. It evaluates its
1204 arguments multiple times.
1207 @node Integer Logic and Bit Fiddling, I/O of Integers, Comparison Functions, Integer Functions
1208 @comment node-name, next, previous, up
1209 @section Logical and Bit Manipulation Functions
1210 @cindex Logical functions
1211 @cindex Bit manipulation functions
1213 These functions behave as if two's complement arithmetic were used (although
1214 sign-magnitude is used by the actual implementation).
1216 @deftypefun void mpz_and (mpz_t @var{rop}, mpz_t @var{op1}, mpz_t @var{op2})
1217 Set @var{rop} to @var{op1} logical-and @var{op2}.
1220 @deftypefun void mpz_ior (mpz_t @var{rop}, mpz_t @var{op1}, mpz_t @var{op2})
1221 Set @var{rop} to @var{op1} inclusive-or @var{op2}.
1224 @c @deftypefun void mpz_xor (mpz_t @var{rop}, mpz_t @var{op1}, mpz_t @var{op2})
1225 @c Set @var{rop} to @var{op1} exclusive-or @var{op2}.
1228 @deftypefun void mpz_com (mpz_t @var{rop}, mpz_t @var{op})
1229 Set @var{rop} to the one's complement of @var{op}.
1232 @deftypefun {unsigned long int} mpz_popcount (mpz_t @var{op})
1233 For non-negative numbers, return the population count of @var{op}. For
1234 negative numbers, return the largest possible value (@var{MAX_ULONG}).
1237 @deftypefun {unsigned long int} mpz_hamdist (mpz_t @var{op1}, mpz_t @var{op2})
1238 If @var{op1} and @var{op2} are both non-negative, return the hamming distance
1239 between the two operands. Otherwise, return the largest possible value
1242 It is possible to extend this function to return a useful value when the
1243 operands are both negative, but the current implementation returns
1244 @var{MAX_ULONG} in this case. @strong{Do not depend on this behavior, since
1245 it will change in future versions of the library.}
1248 @deftypefun {unsigned long int} mpz_scan0 (mpz_t @var{op}, unsigned long int @var{starting_bit})
1249 Scan @var{op}, starting with bit @var{starting_bit}, towards more significant
1250 bits, until the first clear bit is found. Return the index of the found bit.
1253 @deftypefun {unsigned long int} mpz_scan1 (mpz_t @var{op}, unsigned long int @var{starting_bit})
1254 Scan @var{op}, starting with bit @var{starting_bit}, towards more significant
1255 bits, until the first set bit is found. Return the index of the found bit.
1258 @deftypefun void mpz_setbit (mpz_t @var{rop}, unsigned long int @var{bit_index})
1259 Set bit @var{bit_index} in @var{op1}.
1262 @deftypefun void mpz_clrbit (mpz_t @var{rop}, unsigned long int @var{bit_index})
1263 Clear bit @var{bit_index} in @var{op1}.
1266 @node I/O of Integers, Miscellaneous Integer Functions, Integer Logic and Bit Fiddling, Integer Functions
1267 @comment node-name, next, previous, up
1268 @section Input and Output Functions
1269 @cindex Integer input and output functions
1270 @cindex Input functions
1271 @cindex Output functions
1272 @cindex I/O functions
1274 Functions that perform input from a stdio stream, and functions that output to
1275 a stdio stream. Passing a NULL pointer for a @var{stream} argument to any of
1276 these functions will make them read from @code{stdin} and write to
1277 @code{stdout}, respectively.
1279 When using any of these functions, it is a good idea to include @file{stdio.h}
1280 before @file{gmp.h}, since that will allow @file{gmp.h} to define prototypes
1281 for these functions.
1283 @deftypefun size_t mpz_out_str (FILE *@var{stream}, int @var{base}, mpz_t @var{op})
1284 Output @var{op} on stdio stream @var{stream}, as a string of digits in base
1285 @var{base}. The base may vary from 2 to 36.
1287 Return the number of bytes written, or if an error occurred, return 0.
1290 @deftypefun size_t mpz_inp_str (mpz_t @var{rop}, FILE *@var{stream}, int @var{base})
1291 Input a possibly white-space preceded string in base @var{base} from stdio
1292 stream @var{stream}, and put the read integer in @var{rop}. The base may vary
1293 from 2 to 36. If @var{base} is 0, the actual base is determined from the
1294 leading characters: if the first two characters are `0x' or `0X', hexadecimal
1295 is assumed, otherwise if the first character is `0', octal is assumed,
1296 otherwise decimal is assumed.
1298 Return the number of bytes read, or if an error occurred, return 0.
1301 @deftypefun size_t mpz_out_raw (FILE *@var{stream}, mpz_t @var{op})
1302 Output @var{op} on stdio stream @var{stream}, in raw binary format. The
1303 integer is written in a portable format, with 4 bytes of size information, and
1304 that many bytes of limbs. Both the size and the limbs are written in
1305 decreasing significance order (i.e., in big-endian).
1307 The output can be read with @code{mpz_inp_raw}.
1309 Return the number of bytes written, or if an error occurred, return 0.
1311 The output of this can not be read by @code{mpz_inp_raw} from GMP 1, because
1312 of changes necessary for compatibility between 32-bit and 64-bit machines.
1315 @deftypefun size_t mpz_inp_raw (mpz_t @var{rop}, FILE *@var{stream})
1316 Input from stdio stream @var{stream} in the format written by
1317 @code{mpz_out_raw}, and put the result in @var{rop}. Return the number of
1318 bytes read, or if an error occurred, return 0.
1320 This routine can read the output from @code{mpz_out_raw} also from GMP 1, in
1321 spite of changes necessary for compatibility between 32-bit and 64-bit
1327 @node Miscellaneous Integer Functions,, I/O of Integers, Integer Functions
1328 @comment node-name, next, previous, up
1329 @section Miscellaneous Functions
1330 @cindex Miscellaneous integer functions
1332 @deftypefun void mpz_random (mpz_t @var{rop}, mp_size_t @var{max_size})
1333 Generate a random integer of at most @var{max_size} limbs. The generated
1334 random number doesn't satisfy any particular requirements of randomness.
1335 Negative random numbers are generated when @var{max_size} is negative.
1338 @deftypefun void mpz_random2 (mpz_t @var{rop}, mp_size_t @var{max_size})
1339 Generate a random integer of at most @var{max_size} limbs, with long strings
1340 of zeros and ones in the binary representation. Useful for testing functions
1341 and algorithms, since this kind of random numbers have proven to be more
1342 likely to trigger corner-case bugs. Negative random numbers are generated
1343 when @var{max_size} is negative.
1346 @deftypefun size_t mpz_size (mpz_t @var{op})
1347 Return the size of @var{op} measured in number of limbs. If @var{op} is zero,
1348 the returned value will be zero.
1349 @c (@xref{Nomenclature}, for an explanation of the concept @dfn{limb}.)
1351 @strong{This function is obsolete. It will disappear from future MP
1355 @deftypefun size_t mpz_sizeinbase (mpz_t @var{op}, int @var{base})
1356 Return the size of @var{op} measured in number of digits in base @var{base}.
1357 The base may vary from 2 to 36. The returned value will be exact or 1 too
1358 big. If @var{base} is a power of 2, the returned value will always be exact.
1360 This function is useful in order to allocate the right amount of space before
1361 converting @var{op} to a string. The right amount of allocation is normally
1362 two more than the value returned by @code{mpz_sizeinbase} (one extra for a
1363 minus sign and one for the terminating '\0').
1367 @node Rational Number Functions, Floating-point Functions, Integer Functions, Top
1368 @comment node-name, next, previous, up
1369 @chapter Rational Number Functions
1370 @cindex Rational number functions
1372 This chapter describes the MP functions for performing arithmetic on rational
1373 numbers. These functions start with the prefix @code{mpq_}.
1375 Rational numbers are stored in objects of type @code{mpq_t}.
1377 All rational arithmetic functions assume operands have a canonical form, and
1378 canonicalize their result. The canonical from means that the denominator and
1379 the numerator have no common factors, and that the denominator is positive.
1380 Zero has the unique representation 0/1.
1382 Pure assignment functions do not canonicalize the assigned variable. It is
1383 the responsibility of the user to canonicalize the assigned variable before
1384 any arithmetic operations are performed on that variable. @strong{Note that
1385 this is an incompatible change from version 1 of the library.}
1387 @deftypefun void mpq_canonicalize (mpq_t @var{op})
1388 Remove any factors that are common to the numerator and denominator of
1389 @var{op}, and make the denominator positive.
1393 * Initializing Rationals::
1394 * Assigning Rationals::
1395 * Simultaneous Integer Init & Assign::
1396 * Comparing Rationals::
1397 * Applying Integer Functions::
1398 * Miscellaneous Rational Functions::
1401 @node Initializing Rationals, Assigning Rationals, Rational Number Functions, Rational Number Functions
1402 @comment node-name, next, previous, up
1403 @section Initialization and Assignment Functions
1405 @deftypefun void mpq_init (mpq_t @var{dest_rational})
1406 Initialize @var{dest_rational} and set it to 0/1. Each variable should
1407 normally only be initialized once, or at least cleared out (using the function
1408 @code{mpq_clear}) between each initialization.
1411 @deftypefun void mpq_clear (mpq_t @var{rational_number})
1412 Free the space occupied by @var{rational_number}. Make sure to call this
1413 function for all @code{mpq_t} variables when you are done with them.
1416 @deftypefun void mpq_set (mpq_t @var{rop}, mpq_t @var{op})
1417 @deftypefunx void mpq_set_z (mpq_t @var{rop}, mpz_t @var{op})
1418 Assign @var{rop} from @var{op}.
1421 @deftypefun void mpq_set_ui (mpq_t @var{rop}, unsigned long int @var{op1}, unsigned long int @var{op2})
1422 @deftypefunx void mpq_set_si (mpq_t @var{rop}, signed long int @var{op1}, unsigned long int @var{op2})
1423 Set the value of @var{rop} to @var{op1}/@var{op2}. Note that if @var{op1} and
1424 @var{op2} have common factors, @var{rop} has to be passed to
1425 @code{mpq_canonicalize} before any operations are performed on @var{rop}.
1428 @node Assigning Rationals, Comparing Rationals, Initializing Rationals, Rational Number Functions
1429 @comment node-name, next, previous, up
1430 @section Arithmetic Functions
1432 @deftypefun void mpq_add (mpq_t @var{sum}, mpq_t @var{addend1}, mpq_t @var{addend2})
1433 Set @var{sum} to @var{addend1} + @var{addend2}.
1436 @deftypefun void mpq_sub (mpq_t @var{difference}, mpq_t @var{minuend}, mpq_t @var{subtrahend})
1437 Set @var{difference} to @var{minuend} @minus{} @var{subtrahend}.
1440 @deftypefun void mpq_mul (mpq_t @var{product}, mpq_t @var{multiplier}, mpq_t @var{multiplicand})
1442 Set @var{product} to @var{multiplier} times @var{multiplicand}.
1446 Set @var{product} to $@var{multiplier} \times @var{multiplicand}$.
1451 @deftypefun void mpq_div (mpq_t @var{quotient}, mpq_t @var{dividend}, mpq_t @var{divisor})
1452 Set @var{quotient} to @var{dividend}/@var{divisor}.
1455 @deftypefun void mpq_neg (mpq_t @var{negated_operand}, mpq_t @var{operand})
1456 Set @var{negated_operand} to @minus{}@var{operand}.
1459 @deftypefun void mpq_inv (mpq_t @var{inverted_number}, mpq_t @var{number})
1460 Set @var{inverted_number} to 1/@var{number}. If the new denominator is
1461 zero, this routine will divide by zero.
1464 @node Comparing Rationals, Applying Integer Functions, Assigning Rationals, Rational Number Functions
1465 @comment node-name, next, previous, up
1466 @section Comparison Functions
1468 @deftypefun int mpq_cmp (mpq_t @var{op1}, mpq_t @var{op2})
1470 Compare @var{op1} and @var{op2}. Return a positive value if @var{op1} >
1471 @var{op2}, zero if @var{op1} = @var{op2}, and a negative value if @var{op1} <
1476 Compare @var{op1} and @var{op2}. Return a positive value if $@var{op1} >
1477 @var{op2}$, zero if $@var{op1} = @var{op2}$, and a negative value if $@var{op1}
1482 To determine if two rationals are equal, @code{mpq_equal} is faster than
1486 @deftypefn Macro int mpq_cmp_ui (mpq_t @var{op1}, unsigned long int @var{num2}, unsigned long int @var{den2})
1488 Compare @var{op1} and @var{num2}/@var{den2}. Return a positive value if
1489 @var{op1} > @var{num2}/@var{den2}, zero if @var{op1} = @var{num2}/@var{den2},
1490 and a negative value if @var{op1} < @var{num2}/@var{den2}.
1494 Compare @var{op1} and @var{num2}/@var{den2}. Return a positive value if
1495 $@var{op1} > @var{num2}/@var{den2}$, zero if $@var{op1} =
1496 @var{num2}/@var{den2}$, and a negative value if $@var{op1} <
1497 @var{num2}/@var{den2}$.
1501 This routine allows that @var{num2} and @var{den2} have common factors.
1503 This function is actually implemented as a macro. It evaluates its
1504 arguments multiple times.
1507 @deftypefn Macro int mpq_sgn (mpq_t @var{op})
1509 Return +1 if @var{op} > 0, 0 if @var{op} = 0, and @minus{}1 if @var{op} < 0.
1513 Return $+1$ if $@var{op} > 0$, 0 if $@var{op} = 0$, and $-1$ if $@var{op} < 0$.
1517 This function is actually implemented as a macro. It evaluates its
1518 arguments multiple times.
1521 @deftypefun int mpq_equal (mpq_t @var{op1}, mpq_t @var{op2})
1522 Return non-zero if @var{op1} and @var{op2} are equal, zero if they are
1523 non-equal. Although @code{mpq_cmp} can be used for the same purpose, this
1524 function is much faster.
1527 @node Applying Integer Functions, Miscellaneous Rational Functions, Comparing Rationals, Rational Number Functions
1528 @comment node-name, next, previous, up
1529 @section Applying Integer Functions to Rationals
1531 The set of @code{mpq} functions is quite small. In particular, there are no
1532 functions for either input or output. But there are two macros that allow us
1533 to apply any @code{mpz} function on the numerator or denominator of a rational
1534 number. If these macros are used to assign to the rational number,
1535 @code{mpq_canonicalize} normally need to be called afterwards.
1537 @deftypefn Macro mpz_t mpq_numref (mpq_t @var{op})
1538 @deftypefnx Macro mpz_t mpq_denref (mpq_t @var{op})
1539 Return a reference to the numerator and denominator of @var{op}, respectively.
1540 The @code{mpz} functions can be used on the result of these macros.
1544 @node Miscellaneous Rational Functions, , Applying Integer Functions, Rational Number Functions
1545 @comment node-name, next, previous, up
1546 @section Miscellaneous Functions
1548 @deftypefun double mpq_get_d (mpq_t @var{op})
1549 Convert @var{op} to a double.
1552 These functions assign between either the numerator or denominator of a
1553 rational, and an integer. Instead of using these functions, it is preferable
1554 to use the more general mechanisms @code{mpq_numref} and @code{mpq_denref},
1555 together with @code{mpz_set}.
1557 @deftypefun void mpq_set_num (mpq_t @var{rational}, mpz_t @var{numerator})
1558 Copy @var{numerator} to the numerator of @var{rational}. When this risks to
1559 make the numerator and denominator of @var{rational} have common factors, you
1560 have to pass @var{rational} to @code{mpq_canonicalize} before any operations
1561 are performed on @var{rational}.
1563 This function is equivalent to
1564 @code{mpz_set (mpq_numref (@var{rational}), @var{numerator})}.
1567 @deftypefun void mpq_set_den (mpq_t @var{rational}, mpz_t @var{denominator})
1568 Copy @var{denominator} to the denominator of @var{rational}. When this risks
1569 to make the numerator and denominator of @var{rational} have common factors,
1570 or if the denominator might be negative, you have to pass @var{rational} to
1571 @code{mpq_canonicalize} before any operations are performed on @var{rational}.
1573 @strong{In version 1 of the library, negative denominators were handled by
1574 copying the sign to the numerator. That is no longer done.}
1576 This function is equivalent to
1577 @code{mpz_set (mpq_denref (@var{rational}), @var{denominators})}.
1580 @deftypefun void mpq_get_num (mpz_t @var{numerator}, mpq_t @var{rational})
1581 Copy the numerator of @var{rational} to the integer @var{numerator}, to
1582 prepare for integer operations on the numerator.
1584 This function is equivalent to
1585 @code{mpz_set (@var{numerator}, mpq_numref (@var{rational}))}.
1588 @deftypefun void mpq_get_den (mpz_t @var{denominator}, mpq_t @var{rational})
1589 Copy the denominator of @var{rational} to the integer @var{denominator}, to
1590 prepare for integer operations on the denominator.
1592 This function is equivalent to
1593 @code{mpz_set (@var{denominator}, mpq_denref (@var{rational}))}.
1597 @node Floating-point Functions, Low-level Functions, Rational Number Functions, Top
1598 @comment node-name, next, previous, up
1599 @chapter Floating-point Functions
1600 @cindex Floating-point functions
1601 @cindex Float functions
1603 This is a description of the @emph{preliminary} interface for floating-point
1604 arithmetic in GNU MP 2.
1606 The floating-point functions expect arguments of type @code{mpf_t}.
1608 The MP floating-point functions have an interface that is similar to the MP
1609 integer functions. The function prefix for floating-point operations is
1612 There is one significant characteristic of floating-point numbers that has
1613 motivated a difference between this function class and other MP function
1614 classes: the inherent inexactness of floating point arithmetic. The user has
1615 to specify the precision of each variable. A computation that assigns a
1616 variable will take place with the precision of the assigned variable; the
1617 precision of variables used as input is ignored.
1619 @cindex User-defined precision
1620 The precision of a calculation is defined as follows: Compute the requested
1621 operation exactly (with ``infinite precision''), and truncate the result to
1622 the destination variable precision. Even if the user has asked for a very
1623 high precision, MP will not calculate with superfluous digits. For example,
1624 if two low-precision numbers of nearly equal magnitude are added, the
1625 precision of the result will be limited to what is required to represent the
1628 The MP floating-point functions are @emph{not} intended as a smooth extension
1629 to the IEEE P754 arithmetic. Specifically, the results obtained on one
1630 computer often differs from the results obtained on a computer with a
1631 different word size.
1634 * Initializing Floats::
1635 * Assigning Floats::
1636 * Simultaneous Float Init & Assign::
1637 * Converting Floats::
1638 * Float Arithmetic::
1639 * Float Comparison::
1641 * Miscellaneous Float Functions::
1644 @node Initializing Floats, Assigning Floats, , Floating-point Functions
1645 @comment node-name, next, previous, up
1646 @section Initialization and Assignment Functions
1648 @deftypefun void mpf_set_default_prec (unsigned long int @var{prec})
1649 Set the default precision to be @strong{at least} @var{prec} bits. All
1650 subsequent calls to @code{mpf_init} will use this precision, but previously
1651 initialized variables are unaffected.
1654 An @code{mpf_t} object must be initialized before storing the first value in
1655 it. The functions @code{mpf_init} and @code{mpf_init2} are used for that
1658 @deftypefun void mpf_init (mpf_t @var{x})
1659 Initialize @var{x} to 0. Normally, a variable should be initialized once only
1660 or at least be cleared, using @code{mpf_clear}, between initializations. The
1661 precision of @var{x} is undefined unless a default precision has already been
1662 established by a call to @code{mpf_set_default_prec}.
1665 @deftypefun void mpf_init2 (mpf_t @var{x}, unsigned long int @var{prec})
1666 Initialize @var{x} to 0 and set its precision to be @strong{at least}
1667 @var{prec} bits. Normally, a variable should be initialized once only or at
1668 least be cleared, using @code{mpf_clear}, between initializations.
1671 @deftypefun void mpf_clear (mpf_t @var{x})
1672 Free the space occupied by @var{x}. Make sure to call this function for all
1673 @code{mpf_t} variables when you are done with them.
1677 Here is an example on how to initialize floating-point variables:
1681 mpf_init (x); /* use default precision */
1682 mpf_init2 (y, 256); /* precision @emph{at least} 256 bits */
1684 /* Unless the program is about to exit, do ... */
1690 The following three functions are useful for changing the precision during a
1691 calculation. A typical use would be for adjusting the precision gradually in
1692 iterative algorithms like Newton-Raphson, making the computation precision
1693 closely match the actual accurate part of the numbers.
1695 @deftypefun void mpf_set_prec (mpf_t @var{rop}, unsigned long int @var{prec})
1696 Set the precision of @var{rop} to be @strong{at least} @var{prec} bits.
1697 Since changing the precision involves calls to @code{realloc}, this routine
1698 should not be called in a tight loop.
1701 @deftypefun {unsigned long int} mpf_get_prec (mpf_t @var{op})
1702 Return the precision actually used for assignments of @var{op}.
1705 @deftypefun void mpf_set_prec_raw (mpf_t @var{rop}, unsigned long int @var{prec})
1706 Set the precision of @var{rop} to be @strong{at least} @var{prec} bits. This
1707 is a low-level function that does not change the allocation. The @var{prec}
1708 argument must not be larger that the precision previously returned by
1709 @code{mpf_get_prec}. It is crucial that the precision of @var{rop} is
1710 ultimately reset to exactly the value returned by @code{mpf_get_prec}.
1714 @node Assigning Floats, Simultaneous Float Init & Assign, Initializing Floats, Floating-point Functions
1715 @comment node-name, next, previous, up
1716 @subsection Assignment Functions
1717 @cindex Float assignment functions
1719 These functions assign new values to already initialized floats
1720 (@pxref{Initializing Floats}).
1722 @deftypefun void mpf_set (mpf_t @var{rop}, mpf_t @var{op})
1723 @deftypefunx void mpf_set_ui (mpf_t @var{rop}, unsigned long int @var{op})
1724 @deftypefunx void mpf_set_si (mpf_t @var{rop}, signed long int @var{op})
1725 @deftypefunx void mpf_set_d (mpf_t @var{rop}, double @var{op})
1726 @deftypefunx void mpf_set_z (mpf_t @var{rop}, mpz_t @var{op})
1727 @deftypefunx void mpf_set_q (mpf_t @var{rop}, mpq_t @var{op})
1728 Set the value of @var{rop} from @var{op}.
1731 @deftypefun int mpf_set_str (mpf_t @var{rop}, char *@var{str}, int @var{base})
1732 Set the value of @var{rop} from the string in @var{str}. The string is of the
1733 form @samp{M@@N} or, if the base is 10 or less, alternatively @samp{MeN}.
1734 @samp{M} is the mantissa and @samp{N} is the exponent. The mantissa is always
1735 in the specified base. The exponent is either in the specified base or, if
1736 @var{base} is negative, in decimal.
1738 The argument @var{base} may be in the ranges 2 to 36, or @minus{}36 to
1739 @minus{}2. Negative values are used to specify that the exponent is in
1742 Unlike the corresponding @code{mpz} function, the base will not be determined
1743 from the leading characters of the string if @var{base} is 0. This is so that
1744 numbers like @samp{0.23} are not interpreted as octal.
1746 White space is allowed in the string, and is simply ignored.
1748 This function returns 0 if the entire string up to the '\0' is a valid number
1749 in base @var{base}. Otherwise it returns @minus{}1.
1753 @node Simultaneous Float Init & Assign, Converting Floats, Assigning Floats, Floating-point Functions
1754 @comment node-name, next, previous, up
1755 @subsection Combined Initialization and Assignment Functions
1756 @cindex Initialization and assignment functions
1758 For convenience, MP provides a parallel series of initialize-and-set functions
1759 which initialize the output and then store the value there. These functions'
1760 names have the form @code{mpf_init_set@dots{}}
1762 Once the float has been initialized by any of the @code{mpf_init_set@dots{}}
1763 functions, it can be used as the source or destination operand for the ordinary
1764 float functions. Don't use an initialize-and-set function on a variable
1765 already initialized!
1767 @deftypefun void mpf_init_set (mpf_t @var{rop}, mpf_t @var{op})
1768 @deftypefunx void mpf_init_set_ui (mpf_t @var{rop}, unsigned long int @var{op})
1769 @deftypefunx void mpf_init_set_si (mpf_t @var{rop}, signed long int @var{op})
1770 @deftypefunx void mpf_init_set_d (mpf_t @var{rop}, double @var{op})
1771 Initialize @var{rop} and set its value from @var{op}.
1773 The precision of @var{rop} will be taken from the active default precision, as
1774 set by @code{mpf_set_default_prec}.
1777 @deftypefun int mpf_init_set_str (mpf_t @var{rop}, char *@var{str}, int @var{base})
1778 Initialize @var{rop} and set its value from the string in @var{str}. See
1779 @code{mpf_set_str} above for details on the assignment operation.
1781 Note that @var{rop} is initialized even if an error occurs. (I.e., you have to
1782 call @code{mpf_clear} for it.)
1784 The precision of @var{rop} will be taken from the active default precision, as
1785 set by @code{mpf_set_default_prec}.
1789 @node Converting Floats, Float Arithmetic, Simultaneous Float Init & Assign, Floating-point Functions
1790 @comment node-name, next, previous, up
1791 @section Conversion Functions
1792 @cindex Conversion functions
1794 @deftypefun double mpf_get_d (mpf_t @var{op})
1795 Convert @var{op} to a double.
1798 @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})
1799 Convert @var{op} to a string of digits in base @var{base}. The base may vary
1800 from 2 to 36. Generate at most @var{n_digits} significant digits, or if
1801 @var{n_digits} is 0, the maximum number of digits accurately representable by
1804 If @var{str} is NULL, space for the mantissa is allocated using the default
1805 allocation function, and a pointer to the string is returned.
1807 If @var{str} is not NULL, it should point to a block of storage enough large
1808 for the mantissa, i.e., @var{n_digits} + 2. The two extra bytes are for a
1809 possible minus sign, and for the terminating null character.
1811 The exponent is written through the pointer @var{expptr}.
1813 If @var{n_digits} is 0, the maximum number of digits meaningfully achievable
1814 from the precision of @var{op} will be generated. Note that the space
1815 requirements for @var{str} in this case will be impossible for the user to
1816 predetermine. Therefore, you need to pass NULL for the string argument
1817 whenever @var{n_digits} is 0.
1819 The generated string is a fraction, with an implicit radix point immediately
1820 to the left of the first digit. For example, the number 3.1416 would be
1821 returned as "31416" in the string and 1 written at @var{expptr}.
1825 @node Float Arithmetic, Float Comparison, Converting Floats, Floating-point Functions
1826 @comment node-name, next, previous, up
1827 @section Arithmetic Functions
1828 @cindex Float arithmetic functions
1829 @cindex Arithmetic functions
1831 @deftypefun void mpf_add (mpf_t @var{rop}, mpf_t @var{op1}, mpf_t @var{op2})
1832 @deftypefunx void mpf_add_ui (mpf_t @var{rop}, mpf_t @var{op1}, unsigned long int @var{op2})
1834 Set @var{rop} to @var{op1} + @var{op2}.
1838 Set @var{rop} to $@var{op1} + @var{op2}$.
1843 @deftypefun void mpf_sub (mpf_t @var{rop}, mpf_t @var{op1}, mpf_t @var{op2})
1844 @deftypefunx void mpf_ui_sub (mpf_t @var{rop}, unsigned long int @var{op1}, mpf_t @var{op2})
1845 @deftypefunx void mpf_sub_ui (mpf_t @var{rop}, mpf_t @var{op1}, unsigned long int @var{op2})
1846 Set @var{rop} to @var{op1} @minus{} @var{op2}.
1849 @deftypefun void mpf_mul (mpf_t @var{rop}, mpf_t @var{op1}, mpf_t @var{op2})
1850 @deftypefunx void mpf_mul_ui (mpf_t @var{rop}, mpf_t @var{op1}, unsigned long int @var{op2})
1852 Set @var{rop} to @var{op1} times @var{op2}.
1856 Set @var{rop} to $@var{op1} \times @var{op2}$.
1861 Division is undefined if the divisor is zero, and passing a zero divisor to
1862 the divide functions will make these functions intentionally divide by zero.
1863 This gives the user the possibility to handle arithmetic exceptions in these
1864 functions in the same manner as other arithmetic exceptions.
1866 @deftypefun void mpf_div (mpf_t @var{rop}, mpf_t @var{op1}, mpf_t @var{op2})
1867 @deftypefunx void mpf_ui_div (mpf_t @var{rop}, unsigned long int @var{op1}, mpf_t @var{op2})
1868 @deftypefunx void mpf_div_ui (mpf_t @var{rop}, mpf_t @var{op1}, unsigned long int @var{op2})
1869 Set @var{rop} to @var{op1}/@var{op2}.
1872 @deftypefun void mpf_sqrt (mpf_t @var{rop}, mpf_t @var{op})
1873 @deftypefunx void mpf_sqrt_ui (mpf_t @var{rop}, unsigned long int @var{op})
1875 Set @var{rop} to the square root of @var{op}.
1879 Set @var{rop} to $\sqrt{@var{op}}$.
1884 @c @deftypefun void mpf_pow_ui (mpf_t @var{rop}, mpf_t @var{op1}, unsigned long int @var{op2})
1885 @c Set @var{rop} to @var{op1} raised to @var{op2}.
1888 @deftypefun void mpf_neg (mpf_t @var{rop}, mpf_t @var{op})
1889 Set @var{rop} to @minus{}@var{op}.
1892 @deftypefun void mpf_abs (mpf_t @var{rop}, mpf_t @var{op})
1893 Set @var{rop} to the absolute value of @var{op}.
1896 @deftypefun void mpf_mul_2exp (mpf_t @var{rop}, mpf_t @var{op1}, unsigned long int @var{op2})
1898 Set @var{rop} to @var{op1} times 2 raised to @var{op2}.
1902 Set @var{rop} to $@var{op1} \times 2^{op2}$.
1907 @deftypefun void mpf_div_2exp (mpf_t @var{rop}, mpf_t @var{op1}, unsigned long int @var{op2})
1909 Set @var{rop} to @var{op1} divided by 2 raised to @var{op2}.
1913 Set @var{rop} to $@var{op1}/2^{op2}$.
1918 @node Float Comparison, I/O of Floats, Float Arithmetic, Floating-point Functions
1919 @comment node-name, next, previous, up
1920 @section Comparison Functions
1921 @cindex Float comparisons functions
1922 @cindex Comparison functions
1924 @deftypefun int mpf_cmp (mpf_t @var{op1}, mpf_t @var{op2})
1925 @deftypefunx int mpf_cmp_ui (mpf_t @var{op1}, unsigned long int @var{op2})
1926 @deftypefunx int mpf_cmp_si (mpf_t @var{op1}, signed long int @var{op2})
1928 Compare @var{op1} and @var{op2}. Return a positive value if @var{op1} >
1929 @var{op2}, zero if @var{op1} = @var{op2}, and a negative value if @var{op1} <
1934 Compare @var{op1} and @var{op2}. Return a positive value if $@var{op1} >
1935 @var{op2}$, zero if $@var{op1} = @var{op2}$, and a negative value if $@var{op1}
1941 @deftypefun int mpf_eq (mpf_t @var{op1}, mpf_t @var{op2}, unsigned long int op3)
1942 Return non-zero if the first @var{op3} bits of @var{op1} and @var{op2} are
1943 equal, zero otherwise. I.e., test of @var{op1} and @var{op2} are
1944 approximately equal.
1947 @deftypefun void mpf_reldiff (mpf_t @var{rop}, mpf_t @var{op1}, mpf_t @var{op2})
1948 Compute the relative difference between @var{op1} and @var{op2} and store the
1949 result in @var{rop}.
1952 @deftypefn Macro int mpf_sgn (mpf_t @var{op})
1954 Return +1 if @var{op} > 0, 0 if @var{op} = 0, and @minus{}1 if @var{op} < 0.
1958 Return $+1$ if $@var{op} > 0$, 0 if $@var{op} = 0$, and $-1$ if $@var{op} < 0$.
1962 This function is actually implemented as a macro. It evaluates its
1963 arguments multiple times.
1966 @node I/O of Floats, Miscellaneous Float Functions, Float Comparison, Floating-point Functions
1967 @comment node-name, next, previous, up
1968 @section Input and Output Functions
1969 @cindex Float input and output functions
1970 @cindex Input functions
1971 @cindex Output functions
1972 @cindex I/O functions
1974 Functions that perform input from a stdio stream, and functions that output to
1975 a stdio stream. Passing a NULL pointer for a @var{stream} argument to any of
1976 these functions will make them read from @code{stdin} and write to
1977 @code{stdout}, respectively.
1979 When using any of these functions, it is a good idea to include @file{stdio.h}
1980 before @file{gmp.h}, since that will allow @file{gmp.h} to define prototypes
1981 for these functions.
1983 @deftypefun size_t mpf_out_str (FILE *@var{stream}, int @var{base}, size_t @var{n_digits}, mpf_t @var{op})
1984 Output @var{op} on stdio stream @var{stream}, as a string of digits in
1985 base @var{base}. The base may vary from 2 to 36. Print at most
1986 @var{n_digits} significant digits, or if @var{n_digits} is 0, the maximum
1987 number of digits accurately representable by @var{op}.
1989 In addition to the significant digits, a leading @samp{0.} and a
1990 trailing exponent, in the form @samp{eNNN}, are printed. If @var{base}
1991 is greater than 10, @samp{@@} will be used instead of @samp{e} as
1994 Return the number of bytes written, or if an error occurred, return 0.
1997 @deftypefun size_t mpf_inp_str (mpf_t @var{rop}, FILE *@var{stream}, int @var{base})
1998 Input a string in base @var{base} from stdio stream @var{stream}, and put the
1999 read float in @var{rop}. The string is of the form @samp{M@@N} or, if the
2000 base is 10 or less, alternatively @samp{MeN}. @samp{M} is the mantissa and
2001 @samp{N} is the exponent. The mantissa is always in the specified base. The
2002 exponent is either in the specified base or, if @var{base} is negative, in
2005 The argument @var{base} may be in the ranges 2 to 36, or @minus{}36 to
2006 @minus{}2. Negative values are used to specify that the exponent is in
2009 Unlike the corresponding @code{mpz} function, the base will not be determined
2010 from the leading characters of the string if @var{base} is 0. This is so that
2011 numbers like @samp{0.23} are not interpreted as octal.
2013 Return the number of bytes read, or if an error occurred, return 0.
2016 @c @deftypefun void mpf_out_raw (FILE *@var{stream}, mpf_t @var{float})
2017 @c Output @var{float} on stdio stream @var{stream}, in raw binary
2018 @c format. The float is written in a portable format, with 4 bytes of
2019 @c size information, and that many bytes of limbs. Both the size and the
2020 @c limbs are written in decreasing significance order.
2023 @c @deftypefun void mpf_inp_raw (mpf_t @var{float}, FILE *@var{stream})
2024 @c Input from stdio stream @var{stream} in the format written by
2025 @c @code{mpf_out_raw}, and put the result in @var{float}.
2029 @node Miscellaneous Float Functions, , I/O of Floats, Floating-point Functions
2030 @comment node-name, next, previous, up
2031 @section Miscellaneous Functions
2032 @cindex Miscellaneous float functions
2034 @deftypefun void mpf_random2 (mpf_t @var{rop}, mp_size_t @var{max_size}, mp_exp_t @var{max_exp})
2035 Generate a random float of at most @var{max_size} limbs, with long strings of
2036 zeros and ones in the binary representation. The exponent of the number is in
2037 the interval @minus{}@var{exp} to @var{exp}. This function is useful for
2038 testing functions and algorithms, since this kind of random numbers have
2039 proven to be more likely to trigger corner-case bugs. Negative random numbers
2040 are generated when @var{max_size} is negative.
2043 @c @deftypefun size_t mpf_size (mpf_t @var{op})
2044 @c Return the size of @var{op} measured in number of limbs. If @var{op} is
2045 @c zero, the returned value will be zero. (@xref{Nomenclature}, for an
2046 @c explanation of the concept @dfn{limb}.)
2048 @c @strong{This function is obsolete. It will disappear from future MP
2052 @node Low-level Functions, BSD Compatible Functions, Floating-point Functions, Top
2053 @comment node-name, next, previous, up
2054 @chapter Low-level Functions
2055 @cindex Low-level functions
2057 This chapter describes low-level MP functions, used to implement the high-level
2058 MP functions, but also intended for time-critical user code.
2060 These functions start with the prefix @code{mpn_}.
2062 @c 1. Some of these function clobber input operands.
2065 The @code{mpn} functions are designed to be as fast as possible, @strong{not}
2066 to provide a coherent calling interface. The different functions have somewhat
2067 similar interfaces, but there are variations that make them hard to use. These
2068 functions do as little as possible apart from the real multiple precision
2069 computation, so that no time is spent on things that not all callers need.
2071 A source operand is specified by a pointer to the least significant limb and a
2072 limb count. A destination operand is specified by just a pointer. It is the
2073 responsibility of the caller to ensure that the destination has enough space
2074 for storing the result.
2076 With this way of specifying operands, it is possible to perform computations
2077 on subranges of an argument, and store the result into a subrange of a
2080 A common requirement for all functions is that each source area needs at least
2081 one limb. No size argument may be zero.
2083 The @code{mpn} functions is the base for the implementation of the @code{mpz_},
2084 @code{mpf_}, and @code{mpq_} functions.
2086 This example adds the number beginning at @var{src1_ptr} and the number
2087 beginning at @var{src2_ptr} and writes the sum at @var{dest_ptr}. All areas
2088 have @var{size} limbs.
2091 cy = mpn_add_n (dest_ptr, src1_ptr, src2_ptr, size)
2095 In the notation used here, a source operand is identified by the pointer to
2096 the least significant limb, and the limb count in braces. For example,
2097 @{s1_ptr, s1_size@}.
2099 @deftypefun mp_limb_t mpn_add_n (mp_limb_t * @var{dest_ptr}, const mp_limb_t * @var{src1_ptr}, const mp_limb_t * @var{src2_ptr}, mp_size_t @var{size})
2100 Add @{@var{src1_ptr}, @var{size}@} and @{@var{src2_ptr}, @var{size}@}, and
2101 write the @var{size} least significant limbs of the result to @var{dest_ptr}.
2102 Return carry, either 0 or 1.
2104 This is the lowest-level function for addition. It is the preferred function
2105 for addition, since it is written in assembly for most targets. For addition
2106 of a variable to itself (i.e., @var{src1_ptr} equals @var{src2_ptr}, use
2107 @code{mpn_lshift} with a count of 1 for optimal speed.
2110 @deftypefun mp_limb_t mpn_add_1 (mp_limb_t * @var{dest_ptr}, const mp_limb_t * @var{src1_ptr}, mp_size_t @var{size}, mp_limb_t @var{src2_limb})
2111 Add @{@var{src1_ptr}, @var{size}@} and @var{src2_limb}, and write the
2112 @var{size} least significant limbs of the result to @var{dest_ptr}. Return
2113 carry, either 0 or 1.
2116 @deftypefun mp_limb_t mpn_add (mp_limb_t * @var{dest_ptr}, const mp_limb_t * @var{src1_ptr}, mp_size_t @var{src1_size}, const mp_limb_t * @var{src2_ptr}, mp_size_t @var{src2_size})
2117 Add @{@var{src1_ptr}, @var{src1_size}@} and @{@var{src2_ptr},
2118 @var{src2_size}@}, and write the @var{src1_size} least significant limbs of
2119 the result to @var{dest_ptr}. Return carry, either 0 or 1.
2121 This function requires that @var{src1_size} is greater than or equal to
2125 @deftypefun mp_limb_t mpn_sub_n (mp_limb_t * @var{dest_ptr}, const mp_limb_t * @var{src1_ptr}, const mp_limb_t * @var{src2_ptr}, mp_size_t @var{size})
2126 Subtract @{@var{src2_ptr}, @var{src2_size}@} from @{@var{src1_ptr},
2127 @var{size}@}, and write the @var{size} least significant limbs of the result
2128 to @var{dest_ptr}. Return borrow, either 0 or 1.
2130 This is the lowest-level function for subtraction. It is the preferred
2131 function for subtraction, since it is written in assembly for most targets.
2134 @deftypefun mp_limb_t mpn_sub_1 (mp_limb_t * @var{dest_ptr}, const mp_limb_t * @var{src1_ptr}, mp_size_t @var{size}, mp_limb_t @var{src2_limb})
2135 Subtract @var{src2_limb} from @{@var{src1_ptr}, @var{size}@}, and write the
2136 @var{size} least significant limbs of the result to @var{dest_ptr}. Return
2137 borrow, either 0 or 1.
2140 @deftypefun mp_limb_t mpn_sub (mp_limb_t * @var{dest_ptr}, const mp_limb_t * @var{src1_ptr}, mp_size_t @var{src1_size}, const mp_limb_t * @var{src2_ptr}, mp_size_t @var{src2_size})
2141 Subtract @{@var{src2_ptr}, @var{src2_size}@} from @{@var{src1_ptr},
2142 @var{src1_size}@}, and write the @var{src1_size} least significant limbs of
2143 the result to @var{dest_ptr}. Return borrow, either 0 or 1.
2145 This function requires that @var{src1_size} is greater than or equal to
2149 @deftypefun void mpn_mul_n (mp_limb_t * @var{dest_ptr}, const mp_limb_t * @var{src1_ptr}, const mp_limb_t * @var{src2_ptr}, mp_size_t @var{size})
2150 Multiply @{@var{src1_ptr}, @var{size}@} and @{@var{src2_ptr}, @var{size}@},
2151 and write the @strong{entire} result to @var{dest_ptr}.
2153 The destination has to have space for 2@var{size} limbs, even if the
2154 significant result might be one limb smaller.
2157 @deftypefun mp_limb_t mpn_mul_1 (mp_limb_t * @var{dest_ptr}, const mp_limb_t * @var{src1_ptr}, mp_size_t @var{size}, mp_limb_t @var{src2_limb})
2158 Multiply @{@var{src1_ptr}, @var{size}@} and @var{src2_limb}, and write the
2159 @var{size} least significant limbs of the product to @var{dest_ptr}. Return
2160 the most significant limb of the product.
2162 This is a low-level function that is a building block for general
2163 multiplication as well as other operations in MP. It is written in assembly
2166 Don't call this function if @var{src2_limb} is a power of 2; use
2167 @code{mpn_lshift} with a count equal to the logarithm of @var{src2_limb}
2168 instead, for optimal speed.
2171 @deftypefun mp_limb_t mpn_addmul_1 (mp_limb_t * @var{dest_ptr}, const mp_limb_t * @var{src1_ptr}, mp_size_t @var{size}, mp_limb_t @var{src2_limb})
2172 Multiply @{@var{src1_ptr}, @var{size}@} and @var{src2_limb}, and add the
2173 @var{size} least significant limbs of the product to @{@var{dest_ptr},
2174 @var{size}@} and write the result to @var{dest_ptr} @var{dest_ptr}. Return
2175 the most significant limb of the product, plus carry-out from the addition.
2177 This is a low-level function that is a building block for general
2178 multiplication as well as other operations in MP. It is written in assembly
2182 @deftypefun mp_limb_t mpn_submul_1 (mp_limb_t * @var{dest_ptr}, const mp_limb_t * @var{src1_ptr}, mp_size_t @var{size}, mp_limb_t @var{src2_limb})
2183 Multiply @{@var{src1_ptr}, @var{size}@} and @var{src2_limb}, and subtract the
2184 @var{size} least significant limbs of the product from @{@var{dest_ptr},
2185 @var{size}@} and write the result to @var{dest_ptr}. Return the most
2186 significant limb of the product, minus borrow-out from the subtraction.
2188 This is a low-level function that is a building block for general
2189 multiplication and division as well as other operations in MP. It is written
2190 in assembly for most targets.
2193 @deftypefun mp_limb_t mpn_mul (mp_limb_t * @var{dest_ptr}, const mp_limb_t * @var{src1_ptr}, mp_size_t @var{src1_size}, const mp_limb_t * @var{src2_ptr}, mp_size_t @var{src2_size})
2194 Multiply @{@var{src1_ptr}, @var{src1_size}@} and @{@var{src2_ptr},
2195 @var{src2_size}@}, and write the result to @var{dest_ptr}. Return the most
2196 significant limb of the result.
2198 The destination has to have space for @var{src1_size} + @var{src1_size}
2199 limbs, even if the result might be one limb smaller.
2201 This function requires that @var{src1_size} is greater than or equal to
2202 @var{src2_size}. The destination must be distinct from either input operands.
2205 @deftypefun mp_size_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})
2206 Divide @{@var{rs2p}, @var{rs2size}@} by @{@var{s3p}, @var{s3size}@}, and
2207 write the quotient at @var{r1p}, with the exception of the most significant
2208 limb, which is returned. The remainder replaces the dividend at @var{rs2p}.
2210 In addition to an integer quotient, @var{xsize} fraction limbs are developed,
2211 and stored after the integral limbs. For most usages, @var{xsize} will be
2214 It is required that @var{rs2size} is greater than or equal to @var{s3size}.
2215 It is required that the most significant bit of the divisor is set.
2217 If the quotient is not needed, pass @var{rs2p} + @var{s3size} as @var{r1p}.
2218 Aside from that special case, no overlap between arguments is permitted.
2220 Return the most significant limb of the quotient, either 0 or 1.
2222 The area at @var{r1p} needs to be @var{rs2size} @minus{} @var{s3size} +
2223 @var{xsize} limbs large.
2226 @deftypefun mp_limb_t mpn_divrem_1 (mp_limb_t * @var{r1p}, mp_size_t @var{xsize}, mp_limb_t * @var{s2p}, mp_size_t @var{s2size}, mp_limb_t @var{s3limb})
2227 Divide @{@var{s2p}, @var{s2size}@} by @var{s3limb}, and write the quotient
2228 at @var{r1p}. Return the remainder.
2230 In addition to an integer quotient, @var{xsize} fraction limbs are developed,
2231 and stored after the integral limbs. For most usages, @var{xsize} will be
2234 The areas at @var{r1p} and @var{s2p} have to be identical or completely
2235 separate, not partially overlapping.
2238 @deftypefun mp_size_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})
2239 @strong{This interface is obsolete. It will disappear from future releases.
2240 Use @code{mpn_divrem} in its stead.}
2243 @deftypefun mp_limb_t mpn_divmod_1 (mp_limb_t * @var{r1p}, mp_limb_t * @var{s2p}, mp_size_t @var{s2size}, mp_limb_t @var{s3limb})
2244 @strong{This interface is obsolete. It will disappear from future releases.
2245 Use @code{mpn_divrem_1} in its stead.}
2248 @deftypefun mp_limb_t mpn_mod_1 (mp_limb_t * @var{s1p}, mp_size_t @var{s1size}, mp_limb_t @var{s2limb})
2249 Divide @{@var{s1p}, @var{s1size}@} by @var{s2limb}, and return the remainder.
2252 @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})
2253 @strong{This interface is obsolete. It will disappear from future releases.
2254 Use @code{mpn_mod_1} in its stead.}
2257 @deftypefun mp_limb_t mpn_bdivmod (mp_limb_t * @var{dest_ptr}, 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})
2258 The function puts the low [@var{d}/@var{BITS_PER_MP_LIMB}] limbs of
2260 @{@var{s1p}, @var{s1size}@}/@{@var{s2p}, @var{s2size}@}
2263 and returns the high @var{d} mod @var{BITS_PER_MP_LIMB} bits of @var{q}.
2265 @{@var{s1p}, @var{s1size}@} - @var{q} * @{@var{s2p}, @var{s2size}@}
2266 mod 2^(@var{s1size}*@var{BITS_PER_MP_LIMB})
2267 is placed at @var{s1p}.
2268 Since the low [@var{d}/@var{BITS_PER_MP_LIMB}] limbs of
2269 this difference are zero, it is possible to overwrite the low limbs at
2270 @var{s1p} with this difference,
2271 provided @var{dest_ptr} <= @var{s1p}.
2273 This function requires that @var{s1size} * @var{BITS_PER_MP_LIMB} >= @var{D},
2274 and that @{@var{s2p}, @var{s2size}@} is odd.
2276 @strong{This interface is preliminary. It might change incompatibly in
2280 @deftypefun mp_limb_t mpn_lshift (mp_limb_t * @var{dest_ptr}, const mp_limb_t * @var{src_ptr}, mp_size_t @var{src_size}, unsigned long int @var{count})
2281 Shift @{@var{src_ptr}, @var{src_size}@} @var{count} bits to the left, and
2282 write the @var{src_size} least significant limbs of the result to
2283 @var{dest_ptr}. @var{count} might be in the range 1 to n @minus{} 1, on an
2284 n-bit machine. The bits shifted out to the left are returned.
2286 Overlapping of the destination space and the source space is allowed in this
2287 function, provided @var{dest_ptr} >= @var{src_ptr}.
2289 This function is written in assembly for most targets.
2292 @deftypefun mp_limp_t mpn_rshift (mp_limb_t * @var{dest_ptr}, const mp_limb_t * @var{src_ptr}, mp_size_t @var{src_size}, unsigned long int @var{count})
2293 Shift @{@var{src_ptr}, @var{src_size}@} @var{count} bits to the right, and
2294 write the @var{src_size} most significant limbs of the result to
2295 @var{dest_ptr}. @var{count} might be in the range 1 to n @minus{} 1, on an
2296 n-bit machine. The bits shifted out to the right are returned.
2298 Overlapping of the destination space and the source space is allowed in this
2299 function, provided @var{dest_ptr} <= @var{src_ptr}.
2301 This function is written in assembly for most targets.
2304 @deftypefun int mpn_cmp (const mp_limb_t * @var{src1_ptr}, const mp_limb_t * @var{src2_ptr}, mp_size_t @var{size})
2305 Compare @{@var{src1_ptr}, @var{size}@} and @{@var{src2_ptr}, @var{size}@} and
2306 return a positive value if src1 > src2, 0 of they are equal, and a negative
2307 value if src1 < src2.
2310 @deftypefun mp_size_t mpn_gcd (mp_limb_t * @var{dest_ptr}, mp_limb_t * @var{src1_ptr}, mp_size_t @var{src1_size}, mp_limb_t * @var{src2_ptr}, mp_size_t @var{src2_size})
2311 Puts at @var{dest_ptr} the greatest common divisor of @{@var{src1_ptr},
2312 @var{src1_size}@} and @{@var{src2_ptr}, @var{src2_size}@}; both source
2313 operands are destroyed by the operation. The size in limbs of the greatest
2314 common divisor is returned.
2316 @{@var{src1_ptr}, @var{src1_size}@} must be odd, and @{@var{src2_ptr},
2317 @var{src2_size}@} must have at least as many bits as @{@var{src1_ptr},
2320 @strong{This interface is preliminary. It might change incompatibly in
2324 @deftypefun mp_limb_t mpn_gcd_1 (const mp_limb_t * @var{src1_ptr}, mp_size_t @var{src1_size}, mp_limb_t @var{src2_limb})
2325 Return the greatest common divisor of @{@var{src1_ptr}, @var{src1_size}@}
2326 and @var{src2_limb}, where @var{src2_limb} (as well as @var{src1_size})
2327 must be different from 0.
2330 @deftypefun mp_size_t mpn_gcdext (mp_limb_t * @var{r1p}, mp_limb_t * @var{r2p}, mp_limb_t * @var{s1p}, mp_size_t @var{s1size}, mp_limb_t * @var{s2p}, mp_size_t @var{s2size})
2331 Puts at @var{r1p} the greatest common divisor of @{@var{s1p}, @var{s1size}@}
2332 and @{@var{s2p}, @var{s2size}@}. The first cofactor is written at
2333 @var{r2p}. Both source operands are destroyed by the operation. The size
2334 in limbs of the greatest common divisor is returned.
2336 @strong{This interface is preliminary. It might change incompatibly in
2340 @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})
2341 Compute the square root of @{@var{sp}, @var{size}@} and put the result at
2342 @var{r1p}. Write the remainder at @var{r2p}, unless @var{r2p} is NULL.
2344 Return the size of the remainder, whether @var{r2p} was NULL or non-NULL.
2345 Iff the operand was a perfect square, the return value will be 0.
2347 The areas at @var{r1p} and @var{sp} have to be distinct. The areas at
2348 @var{r2p} and @var{sp} have to be identical or completely separate, not
2349 partially overlapping.
2352 The area at @var{r1p} needs to have space for ceil(@var{size}/2) limbs.
2356 The area at @var{r1p} needs to have space for $\lceil@var{size}/2\rceil$ limbs.
2359 The area at @var{r2p} needs to be @var{size} limbs large.
2361 @strong{This interface is preliminary. It might change incompatibly in
2365 @deftypefun mp_size_t mpn_get_str (unsigned char *@var{str}, int @var{base}, mp_limb_t * @var{s1p}, mp_size_t @var{s1size})
2366 Convert @{@var{s1p}, @var{s1size}@} to a raw unsigned char array in base
2367 @var{base}. The string is not in ASCII; to convert it to printable format,
2368 add the ASCII codes for @samp{0} or @samp{A}, depending on the base and
2369 range. There may be leading zeros in the string.
2371 The area at @var{s1p} is clobbered.
2373 Return the number of characters in @var{str}.
2375 The area at @var{str} has to have space for the largest possible number
2376 represented by a @var{s1size} long limb array, plus one extra character.
2379 @deftypefun mp_size_t mpn_set_str (mp_limb_t * @var{r1p}, const char *@var{str}, size_t {strsize}, int @var{base})
2380 Convert the raw unsigned char array at @var{str} of length @var{strsize} to
2381 a limb array @{@var{s1p}, @var{s1size}@}. The base of @var{str} is
2384 Return the number of limbs stored in @var{r1p}.
2387 @deftypefun {unsigned long int} mpn_scan0 (const mp_limb_t * @var{s1p}, unsigned long int @var{bit})
2388 Scan @var{s1p} from bit position @var{bit} for the next clear bit.
2390 It is required that there be a clear bit within the area at @var{s1p} at or
2391 beyond bit position @var{bit}, so that the function has something to return.
2393 @strong{This interface is preliminary. It might change incompatibly in
2397 @deftypefun {unsigned long int} mpn_scan1 (const mp_limb_t * @var{s1p}, unsigned long int @var{bit})
2398 Scan @var{s1p} from bit position @var{bit} for the next set bit.
2400 It is required that there be a set bit within the area at @var{s1p} at or
2401 beyond bit position @var{bit}, so that the function has something to return.
2403 @strong{This interface is preliminary. It might change incompatibly in
2407 @deftypefun void mpn_random2 (mp_limb_t * @var{r1p}, mp_size_t @var{r1size})
2408 Generate a random number of length @var{r1size} with long strings of zeros
2409 and ones in the binary representation, and store it at @var{r1p}.
2411 The generated random numbers are intended for testing the correctness of the
2412 implementation of the @code{mpn} routines.
2415 @deftypefun {unsigned long int} mpn_popcount (const mp_limb_t * @var{s1p}, unsigned long int @var{size})
2416 Count the number of set bits in @{@var{s1p}, @var{size}@}.
2419 @deftypefun {unsigned long int} mpn_hamdist (const mp_limb_t * @var{s1p}, const mp_limb_t * @var{s2p}, unsigned long int @var{size})
2420 Compute the hamming distance between @{@var{s1p}, @var{size}@} and
2421 @{@var{s2p}, @var{size}@}.
2424 @deftypefun int mpn_perfect_square_p (const mp_limb_t * @var{s1p}, mp_size_t @var{size})
2425 Return non-zero iff @{@var{s1p}, @var{size}@} is a perfect square.
2429 @node BSD Compatible Functions, Custom Allocation, Low-level Functions, Top
2430 @comment node-name, next, previous, up
2431 @chapter Berkeley MP Compatible Functions
2432 @cindex BSD MP compatible functions
2434 These functions are intended to be fully compatible with the Berkeley MP
2435 library which is available on many BSD derived U*ix systems.
2437 The original Berkeley MP library has a usage restriction: you cannot use the
2438 same variable as both source and destination in a single function call. The
2439 compatible functions in GNU MP do not share this restriction---inputs and
2440 outputs may overlap.
2442 It is not recommended that new programs are written using these functions.
2443 Apart from the incomplete set of functions, the interface for initializing
2444 @code{MINT} objects is more error prone, and the @code{pow} function collides
2445 with @code{pow} in @file{libm.a}.
2448 Include the header @file{mp.h} to get the definition of the necessary types
2449 and functions. If you are on a BSD derived system, make sure to include GNU
2450 @file{mp.h} if you are going to link the GNU @file{libmp.a} to you program.
2451 This means that you probably need to give the -I<dir> option to the compiler,
2452 where <dir> is the directory where you have GNU @file{mp.h}.
2454 @deftypefun {MINT *} itom (signed short int @var{initial_value})
2455 Allocate an integer consisting of a @code{MINT} object and dynamic limb space.
2456 Initialize the integer to @var{initial_value}. Return a pointer to the
2460 @deftypefun {MINT *} xtom (char *@var{initial_value})
2461 Allocate an integer consisting of a @code{MINT} object and dynamic limb space.
2462 Initialize the integer from @var{initial_value}, a hexadecimal, '\0'-terminate
2463 C string. Return a pointer to the @code{MINT} object.
2466 @deftypefun void move (MINT *@var{src}, MINT *@var{dest})
2467 Set @var{dest} to @var{src} by copying. Both variables must be previously
2471 @deftypefun void madd (MINT *@var{src_1}, MINT *@var{src_2}, MINT *@var{destination})
2472 Add @var{src_1} and @var{src_2} and put the sum in @var{destination}.
2475 @deftypefun void msub (MINT *@var{src_1}, MINT *@var{src_2}, MINT *@var{destination})
2476 Subtract @var{src_2} from @var{src_1} and put the difference in
2480 @deftypefun void mult (MINT *@var{src_1}, MINT *@var{src_2}, MINT *@var{destination})
2481 Multiply @var{src_1} and @var{src_2} and put the product in
2485 @deftypefun void mdiv (MINT *@var{dividend}, MINT *@var{divisor}, MINT *@var{quotient}, MINT *@var{remainder})
2486 @deftypefunx void sdiv (MINT *@var{dividend}, signed short int @var{divisor}, MINT *@var{quotient}, signed short int *@var{remainder})
2487 Set @var{quotient} to @var{dividend}/@var{divisor}, and @var{remainder} to
2488 @var{dividend} mod @var{divisor}. The quotient is rounded towards zero; the
2489 remainder has the same sign as the dividend unless it is zero.
2491 Some implementations of these functions work differently---or not at all---for
2495 @deftypefun void msqrt (MINT *@var{operand}, MINT *@var{root}, MINT *@var{remainder})
2497 Set @var{root} to the truncated integer part of the square root of
2498 @var{operand}. Set @var{remainder} to
2499 @var{operand}@minus{}@var{root}*@var{root},
2503 Set @var{root} to $\lfloor\sqrt{@var{operand}}\rfloor$, like
2504 @code{mpz_sqrt}. Set @var{remainder} to $(operand - root^2)$,
2507 (i.e., zero if @var{operand} is a perfect square).
2509 If @var{root} and @var{remainder} are the same variable, the results are
2513 @deftypefun void pow (MINT *@var{base}, MINT *@var{exp}, MINT *@var{mod}, MINT *@var{dest})
2514 Set @var{dest} to (@var{base} raised to @var{exp}) modulo @var{mod}.
2517 @deftypefun void rpow (MINT *@var{base}, signed short int @var{exp}, MINT *@var{dest})
2518 Set @var{dest} to @var{base} raised to @var{exp}.
2521 @deftypefun void gcd (MINT *@var{operand1}, MINT *@var{operand2}, MINT *@var{res})
2522 Set @var{res} to the greatest common divisor of @var{operand1} and
2526 @deftypefun int mcmp (MINT *@var{operand1}, MINT *@var{operand2})
2527 Compare @var{operand1} and @var{operand2}. Return a positive value if
2528 @var{operand1} > @var{operand2}, zero if @var{operand1} =
2529 @var{operand2}, and a negative value if @var{operand1} < @var{operand2}.
2532 @deftypefun void min (MINT *@var{dest})
2533 Input a decimal string from @code{stdin}, and put the read integer in
2534 @var{dest}. SPC and TAB are allowed in the number string, and are ignored.
2537 @deftypefun void mout (MINT *@var{src})
2538 Output @var{src} to @code{stdout}, as a decimal string. Also output a newline.
2541 @deftypefun {char *} mtox (MINT *@var{operand})
2542 Convert @var{operand} to a hexadecimal string, and return a pointer to the
2543 string. The returned string is allocated using the default memory allocation
2544 function, @code{malloc} by default.
2547 @deftypefun void mfree (MINT *@var{operand})
2548 De-allocate, the space used by @var{operand}. @strong{This function should
2549 only be passed a value returned by @code{itom} or @code{xtom}.}
2552 @node Custom Allocation, Contributors, BSD Compatible Functions, Top
2553 @comment node-name, next, previous, up
2554 @chapter Custom Allocation
2556 By default, the MP functions use @code{malloc}, @code{realloc}, and
2557 @code{free} for memory allocation. If @code{malloc} or @code{realloc} fails,
2558 the MP library terminates execution after printing a fatal error message to
2561 For some applications, you may wish to allocate memory in other ways, or you
2562 may not want to have a fatal error when there is no more memory available. To
2563 accomplish this, you can specify alternative memory allocation functions.
2565 @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))
2566 Replace the current allocation functions from the arguments. If an argument
2567 is NULL, the corresponding default function is retained.
2569 @strong{Make sure to call this function in such a way that there are no active
2570 MP objects that were allocated using the previously active allocation
2571 function! Usually, that means that you have to call this function before any
2575 The functions you supply should fit the following declarations:
2577 @deftypefun {void *} allocate_function (size_t @var{alloc_size})
2578 This function should return a pointer to newly allocated space with at least
2579 @var{alloc_size} storage units.
2582 @deftypefun {void *} reallocate_function (void *@var{ptr}, size_t @var{old_size}, size_t @var{new_size})
2583 This function should return a pointer to newly allocated space of at least
2584 @var{new_size} storage units, after copying at least the first @var{old_size}
2585 storage units from @var{ptr}. It should also de-allocate the space at
2588 You can assume that the space at @var{ptr} was formerly returned from
2589 @code{allocate_function} or @code{reallocate_function}, for a request for
2590 @var{old_size} storage units.
2593 @deftypefun void deallocate_function (void *@var{ptr}, size_t @var{size})
2594 De-allocate the space pointed to by @var{ptr}.
2596 You can assume that the space at @var{ptr} was formerly returned from
2597 @code{allocate_function} or @code{reallocate_function}, for a request for
2598 @var{size} storage units.
2601 (A @dfn{storage unit} is the unit in which the @code{sizeof} operator returns
2602 the size of an object, normally an 8 bit byte.)
2605 @node Contributors, References, Custom Allocation, Top
2606 @comment node-name, next, previous, up
2607 @unnumbered Contributors
2609 I would like to thank Gunnar Sjoedin and Hans Riesel for their help with
2610 mathematical problems, Richard Stallman for his help with design issues and
2611 for revising the first version of this manual, Brian Beuning and Doug Lea for
2612 their testing of early versions of the library.
2614 John Amanatides of York University in Canada contributed the function
2615 @code{mpz_probab_prime_p}.
2617 Paul Zimmermann of Inria sparked the development of GMP 2, with his
2618 comparisons between bignum packages.
2620 Ken Weber (Kent State University, Universidade Federal do Rio Grande do Sul)
2621 contributed @code{mpz_gcd}, @code{mpz_divexact}, @code{mpn_gcd}, and
2622 @code{mpn_bdivmod}, partially supported by CNPq (Brazil) grant 301314194-2.
2624 Per Bothner of Cygnus Support helped to set up MP to use Cygnus' configure.
2625 He has also made valuable suggestions and tested numerous intermediary
2628 Joachim Hollman was involved in the design of the @code{mpf} interface, and in
2629 the @code{mpz} design revisions for version 2.
2631 Bennet Yee contributed the functions @code{mpz_jacobi} and
2632 @code{mpz_legendre}.
2634 Andreas Schwab contributed the files @file{mpn/m68k/lshift.S} and
2635 @file{mpn/m68k/rshift.S}.
2637 The development of floating point functions of GNU MP 2, were supported in
2638 part by the ESPRIT-BRA (Basic Research Activities) 6846 project POSSO
2639 (POlynomial System SOlving).
2641 GNU MP 2 was finished and released by TMG Datakonsult, Sodermannagatan 5, 116
2642 23 STOCKHOLM, SWEDEN, in cooperation with the IDA Center for Computing
2646 @node References, , Contributors, Top
2647 @comment node-name, next, previous, up
2648 @unnumbered References
2653 Donald E. Knuth, "The Art of Computer Programming", vol 2,
2654 "Seminumerical Algorithms", 2nd edition, Addison-Wesley, 1981.
2657 John D. Lipson, "Elements of Algebra and Algebraic Computing",
2658 The Benjamin Cummings Publishing Company Inc, 1981.
2661 Richard M. Stallman, "Using and Porting GCC", Free Software Foundation,
2665 Peter L. Montgomery, "Modular Multiplication Without Trial Division", in
2666 Mathematics of Computation, volume 44, number 170, April 1985.
2669 Torbjorn Granlund and Peter L. Montgomery, "Division by Invariant
2670 Integers using Multiplication", in Proceedings of the SIGPLAN
2671 PLDI'94 Conference, June 1994.
2675 "An algorithm for exact division",
2676 Journal of Symbolic Computation,
2677 v. 15, 1993, pp. 169-180.
2680 Kenneth Weber, "The accelerated integer GCD algorithm",
2681 ACM Transactions on Mathematical Software,
2682 v. 21 (March), 1995, pp. 111-122.
2685 @node Concept Index, , , Top
2686 @comment node-name, next, previous, up
2687 @unnumbered Concept Index
2690 @node Function Index, , , Top
2691 @comment node-name, next, previous, up
2692 @unnumbered Function and Type Index