1 This is Info file gmp.info, produced by Makeinfo-1.64 from the input
5 * gmp: (gmp.info). GNU Multiple Precision Arithmetic Library.
8 This file documents GNU MP, a library for arbitrary-precision
11 Copyright (C) 1991, 1993, 1994, 1995, 1996 Free Software Foundation,
14 Permission is granted to make and distribute verbatim copies of this
15 manual provided the copyright notice and this permission notice are
16 preserved on all copies.
18 Permission is granted to copy and distribute modified versions of
19 this manual under the conditions for verbatim copying, provided that
20 the entire resulting derived work is distributed under the terms of a
21 permission notice identical to this one.
23 Permission is granted to copy and distribute translations of this
24 manual into another language, under the above conditions for modified
25 versions, except that this permission notice may be stated in a
26 translation approved by the Foundation.
29 File: gmp.info, Node: Top, Next: Copying, Prev: (dir), Up: (dir)
34 This manual documents how to install and use the GNU multiple
35 precision arithmetic library, version 2.0.2.
39 * Copying:: GMP Copying Conditions (LGPL).
40 * Introduction to MP:: Brief introduction to GNU MP.
41 * Installing MP:: How to configure and compile the MP library.
42 * MP Basics:: What every MP user should now.
43 * Reporting Bugs:: How to usefully report bugs.
44 * Integer Functions:: Functions for arithmetic on signed integers.
45 * Rational Number Functions:: Functions for arithmetic on rational numbers.
46 * Floating-point Functions:: Functions for arithmetic on floats.
47 * Low-level Functions:: Fast functions for natural numbers.
48 * BSD Compatible Functions:: All functions found in BSD MP.
49 * Custom Allocation:: How to customize the internal allocation.
57 File: gmp.info, Node: Copying, Next: Introduction to MP, Prev: Top, Up: Top
59 GNU MP Copying Conditions
60 *************************
62 This library is "free"; this means that everyone is free to use it
63 and free to redistribute it on a free basis. The library is not in the
64 public domain; it is copyrighted and there are restrictions on its
65 distribution, but these restrictions are designed to permit everything
66 that a good cooperating citizen would want to do. What is not allowed
67 is to try to prevent others from further sharing any version of this
68 library that they might get from you.
70 Specifically, we want to make sure that you have the right to give
71 away copies of the library, that you receive source code or else can
72 get it if you want it, that you can change this library or use pieces
73 of it in new free programs, and that you know you can do these things.
75 To make sure that everyone has such rights, we have to forbid you to
76 deprive anyone else of these rights. For example, if you distribute
77 copies of the GNU MP library, you must give the recipients all the
78 rights that you have. You must make sure that they, too, receive or
79 can get the source code. And you must tell them their rights.
81 Also, for our own protection, we must make certain that everyone
82 finds out that there is no warranty for the GNU MP library. If it is
83 modified by someone else and passed on, we want their recipients to
84 know that what they have is not what we distributed, so that any
85 problems introduced by others will not reflect on our reputation.
87 The precise conditions of the license for the GNU MP library are
88 found in the Library General Public License that accompany the source
92 File: gmp.info, Node: Introduction to MP, Next: Installing MP, Prev: Copying, Up: Top
94 Introduction to GNU MP
95 **********************
97 GNU MP is a portable library written in C for arbitrary precision
98 arithmetic on integers, rational numbers, and floating-point numbers.
99 It aims to provide the fastest possible arithmetic for all applications
100 that need higher precision than is directly supported by the basic C
103 Many applications use just a few hundred bits of precision; but some
104 applications may need thousands or even millions of bits. MP is
105 designed to give good performance for both, by choosing algorithms
106 based on the sizes of the operands, and by carefully keeping the
107 overhead at a minimum.
109 The speed of MP is achieved by using fullwords as the basic
110 arithmetic type, by using sophisticated algorithms, by including
111 carefully optimized assembly code for the most common inner loops for
112 many different CPUs, and by a general emphasis on speed (as opposed to
113 simplicity or elegance).
115 There is carefully optimized assembly code for these CPUs: DEC
116 Alpha, Amd 29000, HPPA 1.0 and 1.1, Intel Pentium and generic x86,
117 Intel i960, Motorola MC68000, MC68020, MC88100, and MC88110,
118 Motorola/IBM PowerPC, National NS32000, IBM POWER, MIPS R3000, R4000,
119 SPARCv7, SuperSPARC, generic SPARCv8, and DEC VAX. Some optimizations
120 also for ARM, Clipper, IBM ROMP (RT), and Pyramid AP/XP.
122 This version of MP is released under a more liberal license than
123 previous versions. It is now permitted to link MP to non-free
124 programs, as long as MP source code is provided when distributing the
127 How to use this Manual
128 ======================
130 Everyone should read *Note MP Basics::. If you need to install the
131 library yourself, you need to read *Note Installing MP::, too.
133 The rest of the manual can be used for later reference, although it
134 is probably a good idea to glance through it.
137 File: gmp.info, Node: Installing MP, Next: MP Basics, Prev: Introduction to MP, Up: Top
142 To build MP, you first have to configure it for your CPU and
143 operating system. You need a C compiler, preferably GCC, but any
144 reasonable compiler should work. And you need a standard Unix `make'
145 program, plus some other standard Unix utility programs.
147 (If you're on an MS-DOS machine, your can build MP using `make.bat'.
148 It requires that djgpp is installed. It does not require
149 configuration, nor is `make' needed; `make.bat' both configures and
152 Here are the steps needed to install the library on Unix systems:
154 1. In most cases, `./configure --target=cpu-vendor-os', should work
155 both for native and cross-compilation. If you get error messages,
156 your machine might not be supported.
158 If you want to compile in a separate object directory, cd to that
159 directory, and prefix the configure command with the path to the
160 MP source directory. Not all `make' programs have the necessary
161 features to support this. In particular, SunOS and Slowaris
162 `make' have bugs that makes them unable to build from a separate
163 object directory. Use GNU `make' instead.
165 In addition to the standard cpu-vendor-os tuples, MP recognizes
166 sparc8 and supersparc as valid CPU names. Specifying these CPU
167 names for relevant systems will improve performance significantly.
169 In general, if you want a library that runs as fast as possible,
170 you should make sure you configure MP for the exact CPU type your
173 If you have `gcc' in your `PATH', it will be used by default. To
174 override this, pass `-with-gcc=no' to `configure'.
178 This will compile MP, and create a library archive file `libgmp.a'
179 in the working directory.
183 This will make sure MP was built correctly. If you get error
184 messages, please report this to `bug-gmp@prep.ai.mit.edu'. (*Note
185 Reporting Bugs::, for information on what to include in useful bug
190 This will copy the file `gmp.h' and `libgmp.a', as well as the info
191 files, to `/usr/local' (or if you passed the `--prefix' option to
192 `configure', to the directory given as argument to `--prefix').
194 If you wish to build and install the BSD MP compatible functions, use
195 `make libmp.a' and `make install-bsdmp'.
197 There are some other useful make targets:
201 Create a DVI version of the manual, in `gmp.dvi' and a set of info
202 files, in `gmp.info', `gmp.info-1', `gmp.info-2', etc.
206 Create a Postscript version of the manual, in `gmp.ps'.
210 Create a HTML version of the manual, in `gmp.html'.
214 Delete all object files and archive files, but not the
219 Delete all files not included in the distribution.
223 Delete all files copied by `make install'.
228 GCC 2.7.2 (as well as 2.6.3) for the RS/6000 and PowerPC can not be
229 used to compile MP, due to a bug in GCC. If you want to use GCC for
230 these machines, you need to apply the patch below to GCC, or use a
231 later version of the compiler.
233 If you are on a Sequent Symmetry, use the GNU assembler instead of
234 the system's assembler, since the latter has serious bugs.
236 The system compiler on NeXT is a massacred and old gcc, even if the
237 compiler calls itself `cc'. This compiler cannot be used to build MP.
238 You need to get a real gcc, and install that before you compile MP.
239 (NeXT might have fixed this in newer releases of their system.)
241 The system C compiler under SunOS 4 has a bug that makes it
242 miscompile mpq/get_d.c. This will make `make check' fail.
244 Please report other problems to `bug-gmp@prep.ai.mit.edu'. *Note
247 Patch to apply to GCC 2.6.3 and 2.7.2:
249 *** config/rs6000/rs6000.md Sun Feb 11 08:22:11 1996
250 --- config/rs6000/rs6000.md.new Sun Feb 18 03:33:37 1996
253 (set (match_operand:SI 0 "gpc_reg_operand" "=r")
254 (not:SI (match_dup 1)))]
257 [(set_attr "type" "compare")])
261 (set (match_operand:SI 0 "gpc_reg_operand" "=r")
262 (not:SI (match_dup 1)))]
265 [(set_attr "type" "compare")])
270 File: gmp.info, Node: MP Basics, Next: Reporting Bugs, Prev: Installing MP, Up: Top
275 All declarations needed to use MP are collected in the include file
276 `gmp.h'. It is designed to work with both C and C++ compilers.
278 Nomenclature and Types
279 ======================
281 In this manual, "integer" usually means a multiple precision integer, as
282 defined by the MP library. The C data type for such integers is
283 `mpz_t'. Here are some examples of how to declare such integers:
287 struct foo { mpz_t x, y; };
291 "Rational number" means a multiple precision fraction. The C data type
292 for these fractions is `mpq_t'. For example:
296 "Floating point number" or "Float" for short, is an arbitrary precision
297 mantissa with an limited precision exponent. The C data type for such
300 A "limb" means the part of a multi-precision number that fits in a
301 single word. (We chose this word because a limb of the human body is
302 analogous to a digit, only larger, and containing several digits.)
303 Normally a limb contains 32 or 64 bits. The C data type for a limb is
309 There are six classes of functions in the MP library:
311 1. Functions for signed integer arithmetic, with names beginning with
312 `mpz_'. The associated type is `mpz_t'. There are about 100
313 functions in this class.
315 2. Functions for rational number arithmetic, with names beginning with
316 `mpq_'. The associated type is `mpq_t'. There are about 20
317 functions in this class, but the functions in the previous class
318 can be used for performing arithmetic on the numerator and
319 denominator separately.
321 3. Functions for floating-point arithmetic, with names beginning with
322 `mpf_'. The associated type is `mpf_t'. There are about 50
323 functions is this class.
325 4. Functions compatible with Berkeley MP, such as `itom', `madd', and
326 `mult'. The associated type is `MINT'.
328 5. Fast low-level functions that operate on natural numbers. These
329 are used by the functions in the preceding groups, and you can
330 also call them directly from very time-critical user programs.
331 These functions' names begin with `mpn_'. There are about 30
332 (hard-to-use) functions in this class.
334 The associated type is array of `mp_limb_t'.
336 6. Miscellaneous functions. Functions for setting up custom
339 MP Variable Conventions
340 =======================
342 As a general rule, all MP functions expect output arguments before
343 input arguments. This notation is based on an analogy with the
344 assignment operator. (The BSD MP compatibility functions disobey this
345 rule, having the output argument(s) last.)
347 MP allows you to use the same variable for both input and output in
348 the same expression. For example, the main function for integer
349 multiplication, `mpz_mul', can be used like this: `mpz_mul (x, x, x)'.
350 This computes the square of X and puts the result back in X.
352 Before you can assign to an MP variable, you need to initialize it
353 by calling one of the special initialization functions. When you're
354 done with a variable, you need to clear it out, using one of the
355 functions for that purpose. Which function to use depends on the type
356 of variable. See the chapters on integer functions, rational number
357 functions, and floating-point functions for details.
359 A variable should only be initialized once, or at least cleared out
360 between each initialization. After a variable has been initialized, it
361 may be assigned to any number of times.
363 For efficiency reasons, avoid to initialize and clear out a variable
364 in loops. Instead, initialize it before entering the loop, and clear
365 it out after the loop has exited.
367 You don't need to be concerned about allocating additional space for
368 MP variables. All functions in MP automatically allocate additional
369 space when a variable does not already have enough space. They do not,
370 however, reduce the space when a smaller number is stored in the
371 object. Most of the time, this policy is best, since it avoids
372 frequent re-allocation.
374 Useful Macros and Constants
375 ===========================
377 - Global Constant: const int mp_bits_per_limb
378 The number of bits per limb.
380 - Macro: __GNU_MP_VERSION
381 - Macro: __GNU_MP_VERSION_MINOR
382 The major and minor MP version, respectively, as integers.
384 Compatibility with Version 1.x
385 ==============================
387 This version of MP is upward compatible with previous versions of
388 MP, with a few exceptions.
390 1. Integer division functions round the result differently. The old
391 functions (`mpz_div', `mpz_divmod', `mpz_mdiv', `mpz_mdivmod',
392 etc) now all use floor rounding (i.e., they round the quotient to
393 -infinity). There are a lot of new functions for integer
394 division, giving the user better control over the rounding.
396 2. The function `mpz_mod' now compute the true *mod* function.
398 3. The functions `mpz_powm' and `mpz_powm_ui' now use *mod* for
401 4. The assignment functions for rational numbers do no longer
402 canonicalize their results. In the case a non-canonical result
403 could arise from an assignment, the user need to insert an
404 explicit call to `mpq_canonicalize'. This change was made for
407 5. Output generated by `mpz_out_raw' in this release cannot be read
408 by `mpz_inp_raw' in previous releases. This change was made for
409 making the file format truly portable between machines with
410 different word sizes.
412 6. Several `mpn' functions have changed. But they were intentionally
413 undocumented in previous releases.
415 7. The functions `mpz_cmp_ui', `mpz_cmp_si', and `mpq_cmp_ui' are now
416 implementated as macros, and thereby sometimes evaluate their
417 arguments multiple times.
419 8. The functions `mpz_pow_ui' and `mpz_ui_pow_ui' now yield 1 for
420 0^0. (In version 1, they yielded 0.)
423 Getting the Latest Version of MP
424 ================================
426 The latest version of the MP library is available by anonymous ftp
427 from from `prep.ai.mit.edu'. The file name is
428 `/pub/gnu/gmp-M.N.tar.gz'. Many sites around the world mirror `prep';
429 please use a mirror site near you.
432 File: gmp.info, Node: Reporting Bugs, Next: Integer Functions, Prev: MP Basics, Up: Top
437 If you think you have found a bug in the MP library, please
438 investigate it and report it. We have made this library available to
439 you, and it is not to ask too much from you, to ask you to report the
442 There are a few things you should think about when you put your bug
445 You have to send us a test case that makes it possible for us to
446 reproduce the bug. Include instructions on how to run the test case.
448 You also have to explain what is wrong; if you get a crash, or if
449 the results printed are incorrect and in that case, in what way.
451 It is not uncommon that an observed problem is actually due to a bug
452 in the compiler used when building MP; the MP code tends to explore
453 interesting corners in compilers. Therefore, please include compiler
454 version information in your bug report. This can be extracted using
455 `what `which cc`', or, if you're using gcc, `gcc -v'. Also, include
456 the output from `uname -a'.
458 If your bug report is good, we will do our best to help you to get a
459 corrected version of the library; if the bug report is poor, we won't
460 do anything about it (aside of chiding you to send better bug reports).
462 Send your bug report to: `bug-gmp@prep.ai.mit.edu'.
464 If you think something in this manual is unclear, or downright
465 incorrect, or if the language needs to be improved, please send a note
469 File: gmp.info, Node: Integer Functions, Next: Rational Number Functions, Prev: Reporting Bugs, Up: Top
474 This chapter describes the MP functions for performing integer
475 arithmetic. These functions start with the prefix `mpz_'.
477 Arbitrary precision integers are stored in objects of type `mpz_t'.
481 * Initializing Integers::
482 * Assigning Integers::
483 * Simultaneous Integer Init & Assign::
484 * Converting Integers::
485 * Integer Arithmetic::
486 * Comparison Functions::
487 * Integer Logic and Bit Fiddling::
489 * Miscellaneous Integer Functions::
492 File: gmp.info, Node: Initializing Integers, Next: Assigning Integers, Up: Integer Functions
494 Initialization and Assignment Functions
495 =======================================
497 The functions for integer arithmetic assume that all integer objects
498 are initialized. You do that by calling the function `mpz_init'.
500 - Function: void mpz_init (mpz_t INTEGER)
501 Initialize INTEGER with limb space and set the initial numeric
502 value to 0. Each variable should normally only be initialized
503 once, or at least cleared out (using `mpz_clear') between each
506 Here is an example of using `mpz_init':
512 mpz_add (integ, ...);
514 mpz_sub (integ, ...);
516 /* Unless the program is about to exit, do ... */
520 As you can see, you can store new values any number of times, once an
521 object is initialized.
523 - Function: void mpz_clear (mpz_t INTEGER)
524 Free the limb space occupied by INTEGER. Make sure to call this
525 function for all `mpz_t' variables when you are done with them.
527 - Function: void * _mpz_realloc (mpz_t INTEGER, mp_size_t NEW_ALLOC)
528 Change the limb space allocation to NEW_ALLOC limbs. This
529 function is not normally called from user code, but it can be used
530 to give memory back to the heap, or to increase the space of a
531 variable to avoid repeated automatic re-allocation.
533 - Function: void mpz_array_init (mpz_t INTEGER_ARRAY[], size_t
534 ARRAY_SIZE, mp_size_t FIXED_NUM_BITS)
535 Allocate *fixed* limb space for all ARRAY_SIZE integers in
536 INTEGER_ARRAY. The fixed allocation for each integer in the array
537 is enough to store FIXED_NUM_BITS. If the fixed space will be
538 insufficient for storing the result of a subsequent calculation,
539 the result is unpredictable.
541 This function is useful for decreasing the working set for some
542 algorithms that use large integer arrays.
544 There is no way to de-allocate the storage allocated by this
545 function. Don't call `mpz_clear'!
548 File: gmp.info, Node: Assigning Integers, Next: Simultaneous Integer Init & Assign, Prev: Initializing Integers, Up: Integer Functions
553 These functions assign new values to already initialized integers
554 (*note Initializing Integers::.).
556 - Function: void mpz_set (mpz_t ROP, mpz_t OP)
557 - Function: void mpz_set_ui (mpz_t ROP, unsigned long int OP)
558 - Function: void mpz_set_si (mpz_t ROP, signed long int OP)
559 - Function: void mpz_set_d (mpz_t ROP, double OP)
560 - Function: void mpz_set_q (mpz_t ROP, mpq_t OP)
561 - Function: void mpz_set_f (mpz_t ROP, mpf_t OP)
562 Set the value of ROP from OP.
564 - Function: int mpz_set_str (mpz_t ROP, char *STR, int BASE)
565 Set the value of ROP from STR, a '\0'-terminated C string in base
566 BASE. White space is allowed in the string, and is simply
567 ignored. The base may vary from 2 to 36. If BASE is 0, the
568 actual base is determined from the leading characters: if the
569 first two characters are `0x' or `0X', hexadecimal is assumed,
570 otherwise if the first character is `0', octal is assumed,
571 otherwise decimal is assumed.
573 This function returns 0 if the entire string up to the '\0' is a
574 valid number in base BASE. Otherwise it returns -1.
577 File: gmp.info, Node: Simultaneous Integer Init & Assign, Next: Converting Integers, Prev: Assigning Integers, Up: Integer Functions
579 Combined Initialization and Assignment Functions
580 ------------------------------------------------
582 For convenience, MP provides a parallel series of initialize-and-set
583 functions which initialize the output and then store the value there.
584 These functions' names have the form `mpz_init_set...'
586 Here is an example of using one:
590 mpz_init_set_str (pie, "3141592653589793238462643383279502884", 10);
597 Once the integer has been initialized by any of the `mpz_init_set...'
598 functions, it can be used as the source or destination operand for the
599 ordinary integer functions. Don't use an initialize-and-set function
600 on a variable already initialized!
602 - Function: void mpz_init_set (mpz_t ROP, mpz_t OP)
603 - Function: void mpz_init_set_ui (mpz_t ROP, unsigned long int OP)
604 - Function: void mpz_init_set_si (mpz_t ROP, signed long int OP)
605 - Function: void mpz_init_set_d (mpz_t ROP, double OP)
606 Initialize ROP with limb space and set the initial numeric value
609 - Function: int mpz_init_set_str (mpz_t ROP, char *STR, int BASE)
610 Initialize ROP and set its value like `mpz_set_str' (see its
611 documentation above for details).
613 If the string is a correct base BASE number, the function returns
614 0; if an error occurs it returns -1. ROP is initialized even if
615 an error occurs. (I.e., you have to call `mpz_clear' for it.)
618 File: gmp.info, Node: Converting Integers, Next: Integer Arithmetic, Prev: Simultaneous Integer Init & Assign, Up: Integer Functions
623 This section describes functions for converting arbitrary precision
624 integers to standard C types. Functions for converting *to* arbitrary
625 precision integers are described in *Note Assigning Integers:: and
626 *Note I/O of Integers::.
628 - Function: unsigned long int mpz_get_ui (mpz_t OP)
629 Return the least significant part from OP. This function combined
631 `mpz_tdiv_q_2exp(..., OP, CHAR_BIT*sizeof(unsigned long int))' can
632 be used to extract the limbs of an integer.
634 - Function: signed long int mpz_get_si (mpz_t OP)
635 If OP fits into a `signed long int' return the value of OP.
636 Otherwise return the least significant part of OP, with the same
639 If OP is too large to fit in a `signed long int', the returned
640 result is probably not very useful.
642 - Function: double mpz_get_d (mpz_t OP)
643 Convert OP to a double.
645 - Function: char * mpz_get_str (char *STR, int BASE, mpz_t OP)
646 Convert OP to a string of digits in base BASE. The base may vary
649 If STR is NULL, space for the result string is allocated using the
650 default allocation function, and a pointer to the string is
653 If STR is not NULL, it should point to a block of storage enough
654 large for the result. To find out the right amount of space to
655 provide for STR, use `mpz_sizeinbase (OP, BASE) + 2'. The two
656 extra bytes are for a possible minus sign, and for the terminating
660 File: gmp.info, Node: Integer Arithmetic, Next: Comparison Functions, Prev: Converting Integers, Up: Integer Functions
665 - Function: void mpz_add (mpz_t ROP, mpz_t OP1, mpz_t OP2)
666 - Function: void mpz_add_ui (mpz_t ROP, mpz_t OP1, unsigned long int
668 Set ROP to OP1 + OP2.
670 - Function: void mpz_sub (mpz_t ROP, mpz_t OP1, mpz_t OP2)
671 - Function: void mpz_sub_ui (mpz_t ROP, mpz_t OP1, unsigned long int
673 Set ROP to OP1 - OP2.
675 - Function: void mpz_mul (mpz_t ROP, mpz_t OP1, mpz_t OP2)
676 - Function: void mpz_mul_ui (mpz_t ROP, mpz_t OP1, unsigned long int
678 Set ROP to OP1 times OP2.
680 - Function: void mpz_mul_2exp (mpz_t ROP, mpz_t OP1, unsigned long int
682 Set ROP to OP1 times 2 raised to OP2. This operation can also be
683 defined as a left shift, OP2 steps.
685 - Function: void mpz_neg (mpz_t ROP, mpz_t OP)
688 - Function: void mpz_abs (mpz_t ROP, mpz_t OP)
689 Set ROP to the absolute value of OP.
691 - Function: void mpz_fac_ui (mpz_t ROP, unsigned long int OP)
692 Set ROP to OP!, the factorial of OP.
697 Division is undefined if the divisor is zero, and passing a zero
698 divisor to the divide or modulo functions, as well passing a zero mod
699 argument to the `mpz_powm' and `mpz_powm_ui' functions, will make these
700 functions intentionally divide by zero. This gives the user the
701 possibility to handle arithmetic exceptions in these functions in the
702 same manner as other arithmetic exceptions.
704 There are three main groups of division functions:
705 * Functions that truncate the quotient towards 0. The names of these
706 functions start with `mpz_tdiv'. The `t' in the name is short for
709 * Functions that round the quotient towards -infinity. The names of
710 these routines start with `mpz_fdiv'. The `f' in the name is
713 * Functions that round the quotient towards +infinity. The names of
714 these routines start with `mpz_cdiv'. The `c' in the name is
717 For each rounding mode, there are a couple of variants. Here `q'
718 means that the quotient is computed, while `r' means that the remainder
719 is computed. Functions that compute both the quotient and remainder
720 have `qr' in the name.
722 - Function: void mpz_tdiv_q (mpz_t ROP, mpz_t OP1, mpz_t OP2)
723 - Function: void mpz_tdiv_q_ui (mpz_t ROP, mpz_t OP1, unsigned long
725 Set ROP to [OP1/OP2]. The quotient is truncated towards 0.
727 - Function: void mpz_tdiv_r (mpz_t ROP, mpz_t OP1, mpz_t OP2)
728 - Function: void mpz_tdiv_r_ui (mpz_t ROP, mpz_t OP1, unsigned long
730 Set ROP to (OP1 - [OP1/OP2] * OP2). Unless the remainder is zero,
731 it has the same sign as the dividend.
733 - Function: void mpz_tdiv_qr (mpz_t ROP1, mpz_t ROP2, mpz_t OP1, mpz_t
735 - Function: void mpz_tdiv_qr_ui (mpz_t ROP1, mpz_t ROP2, mpz_t OP1,
736 unsigned long int OP2)
737 Divide OP1 by OP2 and put the quotient in ROP1 and the remainder
738 in ROP2. The quotient is rounded towards 0. Unless the remainder
739 is zero, it has the same sign as the dividend.
741 If ROP1 and ROP2 are the same variable, the results are undefined.
743 - Function: void mpz_fdiv_q (mpz_t ROP1, mpz_t OP1, mpz_t OP2)
744 - Function: void mpz_fdiv_q_ui (mpz_t ROP, mpz_t OP1, unsigned long
746 Set ROP to OP1/OP2. The quotient is rounded towards -infinity.
748 - Function: void mpz_fdiv_r (mpz_t ROP, mpz_t OP1, mpz_t OP2)
749 - Function: unsigned long int mpz_fdiv_r_ui (mpz_t ROP, mpz_t OP1,
750 unsigned long int OP2)
751 Divide OP1 by OP2 and put the remainder in ROP. Unless the
752 remainder is zero, it has the same sign as the divisor.
754 For `mpz_fdiv_r_ui' the remainder is small enough to fit in an
755 `unsigned long int', and is therefore returned.
757 - Function: void mpz_fdiv_qr (mpz_t ROP1, mpz_t ROP2, mpz_t OP1, mpz_t
759 - Function: unsigned long int mpz_fdiv_qr_ui (mpz_t ROP1, mpz_t ROP2,
760 mpz_t OP1, unsigned long int OP2)
761 Divide OP1 by OP2 and put the quotient in ROP1 and the remainder
762 in ROP2. The quotient is rounded towards -infinity. Unless the
763 remainder is zero, it has the same sign as the divisor.
765 For `mpz_fdiv_qr_ui' the remainder is small enough to fit in an
766 `unsigned long int', and is therefore returned.
768 If ROP1 and ROP2 are the same variable, the results are undefined.
770 - Function: unsigned long int mpz_fdiv_ui (mpz_t OP1, unsigned long
772 This function is similar to `mpz_fdiv_r_ui', but the remainder is
773 only returned; it is not stored anywhere.
775 - Function: void mpz_cdiv_q (mpz_t ROP1, mpz_t OP1, mpz_t OP2)
776 - Function: void mpz_cdiv_q_ui (mpz_t ROP, mpz_t OP1, unsigned long
778 Set ROP to OP1/OP2. The quotient is rounded towards +infinity.
780 - Function: void mpz_cdiv_r (mpz_t ROP, mpz_t OP1, mpz_t OP2)
781 - Function: unsigned long int mpz_cdiv_r_ui (mpz_t ROP, mpz_t OP1,
782 unsigned long int OP2)
783 Divide OP1 by OP2 and put the remainder in ROP. Unless the
784 remainder is zero, it has the opposite sign as the divisor.
786 For `mpz_cdiv_r_ui' the negated remainder is small enough to fit
787 in an `unsigned long int', and it is therefore returned.
789 - Function: void mpz_cdiv_qr (mpz_t ROP1, mpz_t ROP2, mpz_t OP1, mpz_t
791 - Function: unsigned long int mpz_cdiv_qr_ui (mpz_t ROP1, mpz_t ROP2,
792 mpz_t OP1, unsigned long int OP2)
793 Divide OP1 by OP2 and put the quotient in ROP1 and the remainder
794 in ROP2. The quotient is rounded towards +infinity. Unless the
795 remainder is zero, it has the opposite sign as the divisor.
797 For `mpz_cdiv_qr_ui' the negated remainder is small enough to fit
798 in an `unsigned long int', and it is therefore returned.
800 If ROP1 and ROP2 are the same variable, the results are undefined.
802 - Function: unsigned long int mpz_cdiv_ui (mpz_t OP1, unsigned long
804 Return the negated remainder, similar to `mpz_cdiv_r_ui'. (The
805 difference is that this function doesn't store the remainder
808 - Function: void mpz_mod (mpz_t ROP, mpz_t OP1, mpz_t OP2)
809 - Function: unsigned long int mpz_mod_ui (mpz_t ROP, mpz_t OP1,
810 unsigned long int OP2)
811 Set ROP to OP1 `mod' OP2. The sign of the divisor is ignored, and
812 the result is always non-negative.
814 For `mpz_mod_ui' the remainder is small enough to fit in an
815 `unsigned long int', and is therefore returned.
817 - Function: void mpz_divexact (mpz_t ROP, mpz_t OP1, mpz_t OP2)
818 Set ROP to OP1/OP2. This function produces correct results only
819 when it is known in advance that OP2 divides OP1.
821 Since mpz_divexact is much faster than any of the other routines
822 that produce the quotient (*note References::. Jebelean), it is
823 the best choice for instances in which exact division is known to
824 occur, such as reducing a rational to lowest terms.
826 - Function: void mpz_tdiv_q_2exp (mpz_t ROP, mpz_t OP1, unsigned long
828 Set ROP to OP1 divided by 2 raised to OP2. The quotient is
831 - Function: void mpz_tdiv_r_2exp (mpz_t ROP, mpz_t OP1, unsigned long
833 Divide OP1 by (2 raised to OP2) and put the remainder in ROP.
834 Unless it is zero, ROP will have the same sign as OP1.
836 - Function: void mpz_fdiv_q_2exp (mpz_t ROP, mpz_t OP1, unsigned long
838 Set ROP to OP1 divided by 2 raised to OP2. The quotient is
839 rounded towards -infinity.
841 - Function: void mpz_fdiv_r_2exp (mpz_t ROP, mpz_t OP1, unsigned long
843 Divide OP1 by (2 raised to OP2) and put the remainder in ROP. The
844 sign of ROP will always be positive.
846 This operation can also be defined as masking of the OP2 least
849 Exponentialization Functions
850 ----------------------------
852 - Function: void mpz_powm (mpz_t ROP, mpz_t BASE, mpz_t EXP, mpz_t MOD)
853 - Function: void mpz_powm_ui (mpz_t ROP, mpz_t BASE, unsigned long int
855 Set ROP to (BASE raised to EXP) `mod' MOD. If EXP is negative,
856 the result is undefined.
858 - Function: void mpz_pow_ui (mpz_t ROP, mpz_t BASE, unsigned long int
860 - Function: void mpz_ui_pow_ui (mpz_t ROP, unsigned long int BASE,
861 unsigned long int EXP)
862 Set ROP to BASE raised to EXP. The case of 0^0 yields 1.
864 Square Root Functions
865 ---------------------
867 - Function: void mpz_sqrt (mpz_t ROP, mpz_t OP)
868 Set ROP to the truncated integer part of the square root of OP.
870 - Function: void mpz_sqrtrem (mpz_t ROP1, mpz_t ROP2, mpz_t OP)
871 Set ROP1 to the truncated integer part of the square root of OP,
872 like `mpz_sqrt'. Set ROP2 to OP-ROP1*ROP1, (i.e., zero if OP is a
875 If ROP1 and ROP2 are the same variable, the results are undefined.
877 - Function: int mpz_perfect_square_p (mpz_t OP)
878 Return non-zero if OP is a perfect square, i.e., if the square
879 root of OP is an integer. Return zero otherwise.
881 Number Theoretic Functions
882 --------------------------
884 - Function: int mpz_probab_prime_p (mpz_t OP, int REPS)
885 If this function returns 0, OP is definitely not prime. If it
886 returns 1, then OP is `probably' prime. The probability of a
887 false positive is (1/4)**REPS. A reasonable value of reps is 25.
889 An implementation of the probabilistic primality test found in
890 Seminumerical Algorithms (*note References::. Knuth).
892 - Function: void mpz_gcd (mpz_t ROP, mpz_t OP1, mpz_t OP2)
893 Set ROP to the greatest common divisor of OP1 and OP2.
895 - Function: unsigned long int mpz_gcd_ui (mpz_t ROP, mpz_t OP1,
896 unsigned long int OP2)
897 Compute the greatest common divisor of OP1 and OP2. If ROP is not
898 NULL, store the result there.
900 If the result is small enough to fit in an `unsigned long int', it
901 is returned. If the result does not fit, 0 is returned, and the
902 result is equal to the argument OP1. Note that the result will
903 always fit if OP2 is non-zero.
905 - Function: void mpz_gcdext (mpz_t G, mpz_t S, mpz_t T, mpz_t A, mpz_t
907 Compute G, S, and T, such that AS + BT = G = `gcd' (A, B). If T is
908 NULL, that argument is not computed.
910 - Function: int mpz_invert (mpz_t ROP, mpz_t OP1, mpz_t OP2)
911 Compute the inverse of OP1 modulo OP2 and put the result in ROP.
912 Return non-zero if an inverse exist, zero otherwise. When the
913 function returns zero, do not assume anything about the value in
916 - Function: int mpz_jacobi (mpz_t OP1, mpz_t OP2)
917 - Function: int mpz_legendre (mpz_t OP1, mpz_t OP2)
918 Compute the Jacobi and Legendre symbols, respectively.
921 File: gmp.info, Node: Comparison Functions, Next: Integer Logic and Bit Fiddling, Prev: Integer Arithmetic, Up: Integer Functions
926 - Function: int mpz_cmp (mpz_t OP1, mpz_t OP2)
927 Compare OP1 and OP2. Return a positive value if OP1 > OP2, zero
928 if OP1 = OP2, and a negative value if OP1 < OP2.
930 - Macro: int mpz_cmp_ui (mpz_t OP1, unsigned long int OP2)
931 - Macro: int mpz_cmp_si (mpz_t OP1, signed long int OP2)
932 Compare OP1 and OP2. Return a positive value if OP1 > OP2, zero
933 if OP1 = OP2, and a negative value if OP1 < OP2.
935 These functions are actually implemented as macros. They evaluate
936 their arguments multiple times.
938 - Macro: int mpz_sgn (mpz_t OP)
939 Return +1 if OP > 0, 0 if OP = 0, and -1 if OP < 0.
941 This function is actually implemented as a macro. It evaluates its
942 arguments multiple times.
945 File: gmp.info, Node: Integer Logic and Bit Fiddling, Next: I/O of Integers, Prev: Comparison Functions, Up: Integer Functions
947 Logical and Bit Manipulation Functions
948 ======================================
950 These functions behave as if two's complement arithmetic were used
951 (although sign-magnitude is used by the actual implementation).
953 - Function: void mpz_and (mpz_t ROP, mpz_t OP1, mpz_t OP2)
954 Set ROP to OP1 logical-and OP2.
956 - Function: void mpz_ior (mpz_t ROP, mpz_t OP1, mpz_t OP2)
957 Set ROP to OP1 inclusive-or OP2.
959 - Function: void mpz_com (mpz_t ROP, mpz_t OP)
960 Set ROP to the one's complement of OP.
962 - Function: unsigned long int mpz_popcount (mpz_t OP)
963 For non-negative numbers, return the population count of OP. For
964 negative numbers, return the largest possible value (MAX_ULONG).
966 - Function: unsigned long int mpz_hamdist (mpz_t OP1, mpz_t OP2)
967 If OP1 and OP2 are both non-negative, return the hamming distance
968 between the two operands. Otherwise, return the largest possible
971 It is possible to extend this function to return a useful value
972 when the operands are both negative, but the current
973 implementation returns MAX_ULONG in this case. *Do not depend on
974 this behavior, since it will change in future versions of the
977 - Function: unsigned long int mpz_scan0 (mpz_t OP, unsigned long int
979 Scan OP, starting with bit STARTING_BIT, towards more significant
980 bits, until the first clear bit is found. Return the index of the
983 - Function: unsigned long int mpz_scan1 (mpz_t OP, unsigned long int
985 Scan OP, starting with bit STARTING_BIT, towards more significant
986 bits, until the first set bit is found. Return the index of the
989 - Function: void mpz_setbit (mpz_t ROP, unsigned long int BIT_INDEX)
990 Set bit BIT_INDEX in OP1.
992 - Function: void mpz_clrbit (mpz_t ROP, unsigned long int BIT_INDEX)
993 Clear bit BIT_INDEX in OP1.
996 File: gmp.info, Node: I/O of Integers, Next: Miscellaneous Integer Functions, Prev: Integer Logic and Bit Fiddling, Up: Integer Functions
998 Input and Output Functions
999 ==========================
1001 Functions that perform input from a stdio stream, and functions that
1002 output to a stdio stream. Passing a NULL pointer for a STREAM argument
1003 to any of these functions will make them read from `stdin' and write to
1004 `stdout', respectively.
1006 When using any of these functions, it is a good idea to include
1007 `stdio.h' before `gmp.h', since that will allow `gmp.h' to define
1008 prototypes for these functions.
1010 - Function: size_t mpz_out_str (FILE *STREAM, int BASE, mpz_t OP)
1011 Output OP on stdio stream STREAM, as a string of digits in base
1012 BASE. The base may vary from 2 to 36.
1014 Return the number of bytes written, or if an error occurred,
1017 - Function: size_t mpz_inp_str (mpz_t ROP, FILE *STREAM, int BASE)
1018 Input a possibly white-space preceded string in base BASE from
1019 stdio stream STREAM, and put the read integer in ROP. The base
1020 may vary from 2 to 36. If BASE is 0, the actual base is
1021 determined from the leading characters: if the first two
1022 characters are `0x' or `0X', hexadecimal is assumed, otherwise if
1023 the first character is `0', octal is assumed, otherwise decimal is
1026 Return the number of bytes read, or if an error occurred, return 0.
1028 - Function: size_t mpz_out_raw (FILE *STREAM, mpz_t OP)
1029 Output OP on stdio stream STREAM, in raw binary format. The
1030 integer is written in a portable format, with 4 bytes of size
1031 information, and that many bytes of limbs. Both the size and the
1032 limbs are written in decreasing significance order (i.e., in
1035 The output can be read with `mpz_inp_raw'.
1037 Return the number of bytes written, or if an error occurred,
1040 The output of this can not be read by `mpz_inp_raw' from GMP 1,
1041 because of changes necessary for compatibility between 32-bit and
1044 - Function: size_t mpz_inp_raw (mpz_t ROP, FILE *STREAM)
1045 Input from stdio stream STREAM in the format written by
1046 `mpz_out_raw', and put the result in ROP. Return the number of
1047 bytes read, or if an error occurred, return 0.
1049 This routine can read the output from `mpz_out_raw' also from GMP
1050 1, in spite of changes necessary for compatibility between 32-bit
1051 and 64-bit machines.
1054 File: gmp.info, Node: Miscellaneous Integer Functions, Prev: I/O of Integers, Up: Integer Functions
1056 Miscellaneous Functions
1057 =======================
1059 - Function: void mpz_random (mpz_t ROP, mp_size_t MAX_SIZE)
1060 Generate a random integer of at most MAX_SIZE limbs. The generated
1061 random number doesn't satisfy any particular requirements of
1062 randomness. Negative random numbers are generated when MAX_SIZE
1065 - Function: void mpz_random2 (mpz_t ROP, mp_size_t MAX_SIZE)
1066 Generate a random integer of at most MAX_SIZE limbs, with long
1067 strings of zeros and ones in the binary representation. Useful
1068 for testing functions and algorithms, since this kind of random
1069 numbers have proven to be more likely to trigger corner-case bugs.
1070 Negative random numbers are generated when MAX_SIZE is negative.
1072 - Function: size_t mpz_size (mpz_t OP)
1073 Return the size of OP measured in number of limbs. If OP is zero,
1074 the returned value will be zero.
1076 *This function is obsolete. It will disappear from future MP
1079 - Function: size_t mpz_sizeinbase (mpz_t OP, int BASE)
1080 Return the size of OP measured in number of digits in base BASE.
1081 The base may vary from 2 to 36. The returned value will be exact
1082 or 1 too big. If BASE is a power of 2, the returned value will
1085 This function is useful in order to allocate the right amount of
1086 space before converting OP to a string. The right amount of
1087 allocation is normally two more than the value returned by
1088 `mpz_sizeinbase' (one extra for a minus sign and one for the
1092 File: gmp.info, Node: Rational Number Functions, Next: Floating-point Functions, Prev: Integer Functions, Up: Top
1094 Rational Number Functions
1095 *************************
1097 This chapter describes the MP functions for performing arithmetic on
1098 rational numbers. These functions start with the prefix `mpq_'.
1100 Rational numbers are stored in objects of type `mpq_t'.
1102 All rational arithmetic functions assume operands have a canonical
1103 form, and canonicalize their result. The canonical from means that the
1104 denominator and the numerator have no common factors, and that the
1105 denominator is positive. Zero has the unique representation 0/1.
1107 Pure assignment functions do not canonicalize the assigned variable.
1108 It is the responsibility of the user to canonicalize the assigned
1109 variable before any arithmetic operations are performed on that
1110 variable. *Note that this is an incompatible change from version 1 of
1113 - Function: void mpq_canonicalize (mpq_t OP)
1114 Remove any factors that are common to the numerator and
1115 denominator of OP, and make the denominator positive.
1119 * Initializing Rationals::
1120 * Assigning Rationals::
1121 * Simultaneous Integer Init & Assign::
1122 * Comparing Rationals::
1123 * Applying Integer Functions::
1124 * Miscellaneous Rational Functions::
1127 File: gmp.info, Node: Initializing Rationals, Next: Assigning Rationals, Prev: Rational Number Functions, Up: Rational Number Functions
1129 Initialization and Assignment Functions
1130 =======================================
1132 - Function: void mpq_init (mpq_t DEST_RATIONAL)
1133 Initialize DEST_RATIONAL and set it to 0/1. Each variable should
1134 normally only be initialized once, or at least cleared out (using
1135 the function `mpq_clear') between each initialization.
1137 - Function: void mpq_clear (mpq_t RATIONAL_NUMBER)
1138 Free the space occupied by RATIONAL_NUMBER. Make sure to call this
1139 function for all `mpq_t' variables when you are done with them.
1141 - Function: void mpq_set (mpq_t ROP, mpq_t OP)
1142 - Function: void mpq_set_z (mpq_t ROP, mpz_t OP)
1145 - Function: void mpq_set_ui (mpq_t ROP, unsigned long int OP1,
1146 unsigned long int OP2)
1147 - Function: void mpq_set_si (mpq_t ROP, signed long int OP1, unsigned
1149 Set the value of ROP to OP1/OP2. Note that if OP1 and OP2 have
1150 common factors, ROP has to be passed to `mpq_canonicalize' before
1151 any operations are performed on ROP.
1154 File: gmp.info, Node: Assigning Rationals, Next: Comparing Rationals, Prev: Initializing Rationals, Up: Rational Number Functions
1156 Arithmetic Functions
1157 ====================
1159 - Function: void mpq_add (mpq_t SUM, mpq_t ADDEND1, mpq_t ADDEND2)
1160 Set SUM to ADDEND1 + ADDEND2.
1162 - Function: void mpq_sub (mpq_t DIFFERENCE, mpq_t MINUEND, mpq_t
1164 Set DIFFERENCE to MINUEND - SUBTRAHEND.
1166 - Function: void mpq_mul (mpq_t PRODUCT, mpq_t MULTIPLIER, mpq_t
1168 Set PRODUCT to MULTIPLIER times MULTIPLICAND.
1170 - Function: void mpq_div (mpq_t QUOTIENT, mpq_t DIVIDEND, mpq_t
1172 Set QUOTIENT to DIVIDEND/DIVISOR.
1174 - Function: void mpq_neg (mpq_t NEGATED_OPERAND, mpq_t OPERAND)
1175 Set NEGATED_OPERAND to -OPERAND.
1177 - Function: void mpq_inv (mpq_t INVERTED_NUMBER, mpq_t NUMBER)
1178 Set INVERTED_NUMBER to 1/NUMBER. If the new denominator is zero,
1179 this routine will divide by zero.
1182 File: gmp.info, Node: Comparing Rationals, Next: Applying Integer Functions, Prev: Assigning Rationals, Up: Rational Number Functions
1184 Comparison Functions
1185 ====================
1187 - Function: int mpq_cmp (mpq_t OP1, mpq_t OP2)
1188 Compare OP1 and OP2. Return a positive value if OP1 > OP2, zero
1189 if OP1 = OP2, and a negative value if OP1 < OP2.
1191 To determine if two rationals are equal, `mpq_equal' is faster than
1194 - Macro: int mpq_cmp_ui (mpq_t OP1, unsigned long int NUM2, unsigned
1196 Compare OP1 and NUM2/DEN2. Return a positive value if OP1 >
1197 NUM2/DEN2, zero if OP1 = NUM2/DEN2, and a negative value if OP1 <
1200 This routine allows that NUM2 and DEN2 have common factors.
1202 This function is actually implemented as a macro. It evaluates its
1203 arguments multiple times.
1205 - Macro: int mpq_sgn (mpq_t OP)
1206 Return +1 if OP > 0, 0 if OP = 0, and -1 if OP < 0.
1208 This function is actually implemented as a macro. It evaluates its
1209 arguments multiple times.
1211 - Function: int mpq_equal (mpq_t OP1, mpq_t OP2)
1212 Return non-zero if OP1 and OP2 are equal, zero if they are
1213 non-equal. Although `mpq_cmp' can be used for the same purpose,
1214 this function is much faster.
1217 File: gmp.info, Node: Applying Integer Functions, Next: Miscellaneous Rational Functions, Prev: Comparing Rationals, Up: Rational Number Functions
1219 Applying Integer Functions to Rationals
1220 =======================================
1222 The set of `mpq' functions is quite small. In particular, there are
1223 no functions for either input or output. But there are two macros that
1224 allow us to apply any `mpz' function on the numerator or denominator of
1225 a rational number. If these macros are used to assign to the rational
1226 number, `mpq_canonicalize' normally need to be called afterwards.
1228 - Macro: mpz_t mpq_numref (mpq_t OP)
1229 - Macro: mpz_t mpq_denref (mpq_t OP)
1230 Return a reference to the numerator and denominator of OP,
1231 respectively. The `mpz' functions can be used on the result of
1235 File: gmp.info, Node: Miscellaneous Rational Functions, Prev: Applying Integer Functions, Up: Rational Number Functions
1237 Miscellaneous Functions
1238 =======================
1240 - Function: double mpq_get_d (mpq_t OP)
1241 Convert OP to a double.
1243 These functions assign between either the numerator or denominator
1244 of a rational, and an integer. Instead of using these functions, it is
1245 preferable to use the more general mechanisms `mpq_numref' and
1246 `mpq_denref', together with `mpz_set'.
1248 - Function: void mpq_set_num (mpq_t RATIONAL, mpz_t NUMERATOR)
1249 Copy NUMERATOR to the numerator of RATIONAL. When this risks to
1250 make the numerator and denominator of RATIONAL have common
1251 factors, you have to pass RATIONAL to `mpq_canonicalize' before
1252 any operations are performed on RATIONAL.
1254 This function is equivalent to `mpz_set (mpq_numref (RATIONAL),
1257 - Function: void mpq_set_den (mpq_t RATIONAL, mpz_t DENOMINATOR)
1258 Copy DENOMINATOR to the denominator of RATIONAL. When this risks
1259 to make the numerator and denominator of RATIONAL have common
1260 factors, or if the denominator might be negative, you have to pass
1261 RATIONAL to `mpq_canonicalize' before any operations are performed
1264 *In version 1 of the library, negative denominators were handled by
1265 copying the sign to the numerator. That is no longer done.*
1267 This function is equivalent to `mpz_set (mpq_denref (RATIONAL),
1270 - Function: void mpq_get_num (mpz_t NUMERATOR, mpq_t RATIONAL)
1271 Copy the numerator of RATIONAL to the integer NUMERATOR, to
1272 prepare for integer operations on the numerator.
1274 This function is equivalent to `mpz_set (NUMERATOR, mpq_numref
1277 - Function: void mpq_get_den (mpz_t DENOMINATOR, mpq_t RATIONAL)
1278 Copy the denominator of RATIONAL to the integer DENOMINATOR, to
1279 prepare for integer operations on the denominator.
1281 This function is equivalent to `mpz_set (DENOMINATOR, mpq_denref