diff options
Diffstat (limited to 'contrib/libgmp/gmp.info-1')
| -rw-r--r-- | contrib/libgmp/gmp.info-1 | 1283 |
1 files changed, 1283 insertions, 0 deletions
diff --git a/contrib/libgmp/gmp.info-1 b/contrib/libgmp/gmp.info-1 new file mode 100644 index 0000000..4ea9373 --- /dev/null +++ b/contrib/libgmp/gmp.info-1 @@ -0,0 +1,1283 @@ +This is Info file gmp.info, produced by Makeinfo-1.64 from the input +file gmp.texi. + +START-INFO-DIR-ENTRY +* gmp: (gmp.info). GNU Multiple Precision Arithmetic Library. +END-INFO-DIR-ENTRY + + This file documents GNU MP, a library for arbitrary-precision +arithmetic. + + Copyright (C) 1991, 1993, 1994, 1995, 1996 Free Software Foundation, +Inc. + + Permission is granted to make and distribute verbatim copies of this +manual provided the copyright notice and this permission notice are +preserved on all copies. + + Permission is granted to copy and distribute modified versions of +this manual under the conditions for verbatim copying, provided that +the entire resulting derived work is distributed under the terms of a +permission notice identical to this one. + + Permission is granted to copy and distribute translations of this +manual into another language, under the above conditions for modified +versions, except that this permission notice may be stated in a +translation approved by the Foundation. + + +File: gmp.info, Node: Top, Next: Copying, Prev: (dir), Up: (dir) + +GNU MP +****** + + This manual documents how to install and use the GNU multiple +precision arithmetic library, version 2.0.2. + +* Menu: + +* Copying:: GMP Copying Conditions (LGPL). +* Introduction to MP:: Brief introduction to GNU MP. +* Installing MP:: How to configure and compile the MP library. +* MP Basics:: What every MP user should now. +* Reporting Bugs:: How to usefully report bugs. +* Integer Functions:: Functions for arithmetic on signed integers. +* Rational Number Functions:: Functions for arithmetic on rational numbers. +* Floating-point Functions:: Functions for arithmetic on floats. +* Low-level Functions:: Fast functions for natural numbers. +* BSD Compatible Functions:: All functions found in BSD MP. +* Custom Allocation:: How to customize the internal allocation. + +* Contributors:: +* References:: +* Concept Index:: +* Function Index:: + + +File: gmp.info, Node: Copying, Next: Introduction to MP, Prev: Top, Up: Top + +GNU MP Copying Conditions +************************* + + This library is "free"; this means that everyone is free to use it +and free to redistribute it on a free basis. The library is not in the +public domain; it is copyrighted and there are restrictions on its +distribution, but these restrictions are designed to permit everything +that a good cooperating citizen would want to do. What is not allowed +is to try to prevent others from further sharing any version of this +library that they might get from you. + + Specifically, we want to make sure that you have the right to give +away copies of the library, that you receive source code or else can +get it if you want it, that you can change this library or use pieces +of it in new free programs, and that you know you can do these things. + + To make sure that everyone has such rights, we have to forbid you to +deprive anyone else of these rights. For example, if you distribute +copies of the GNU MP library, you must give the recipients all the +rights that you have. You must make sure that they, too, receive or +can get the source code. And you must tell them their rights. + + Also, for our own protection, we must make certain that everyone +finds out that there is no warranty for the GNU MP library. If it is +modified by someone else and passed on, we want their recipients to +know that what they have is not what we distributed, so that any +problems introduced by others will not reflect on our reputation. + + The precise conditions of the license for the GNU MP library are +found in the Library General Public License that accompany the source +code. + + +File: gmp.info, Node: Introduction to MP, Next: Installing MP, Prev: Copying, Up: Top + +Introduction to GNU MP +********************** + + GNU MP is a portable library written in C for arbitrary precision +arithmetic on integers, rational numbers, and floating-point numbers. +It aims to provide the fastest possible arithmetic for all applications +that need higher precision than is directly supported by the basic C +types. + + Many applications use just a few hundred bits of precision; but some +applications may need thousands or even millions of bits. MP is +designed to give good performance for both, by choosing algorithms +based on the sizes of the operands, and by carefully keeping the +overhead at a minimum. + + The speed of MP is achieved by using fullwords as the basic +arithmetic type, by using sophisticated algorithms, by including +carefully optimized assembly code for the most common inner loops for +many different CPUs, and by a general emphasis on speed (as opposed to +simplicity or elegance). + + There is carefully optimized assembly code for these CPUs: DEC +Alpha, Amd 29000, HPPA 1.0 and 1.1, Intel Pentium and generic x86, +Intel i960, Motorola MC68000, MC68020, MC88100, and MC88110, +Motorola/IBM PowerPC, National NS32000, IBM POWER, MIPS R3000, R4000, +SPARCv7, SuperSPARC, generic SPARCv8, and DEC VAX. Some optimizations +also for ARM, Clipper, IBM ROMP (RT), and Pyramid AP/XP. + + This version of MP is released under a more liberal license than +previous versions. It is now permitted to link MP to non-free +programs, as long as MP source code is provided when distributing the +non-free program. + +How to use this Manual +====================== + + Everyone should read *Note MP Basics::. If you need to install the +library yourself, you need to read *Note Installing MP::, too. + + The rest of the manual can be used for later reference, although it +is probably a good idea to glance through it. + + +File: gmp.info, Node: Installing MP, Next: MP Basics, Prev: Introduction to MP, Up: Top + +Installing MP +************* + + To build MP, you first have to configure it for your CPU and +operating system. You need a C compiler, preferably GCC, but any +reasonable compiler should work. And you need a standard Unix `make' +program, plus some other standard Unix utility programs. + + (If you're on an MS-DOS machine, your can build MP using `make.bat'. +It requires that djgpp is installed. It does not require +configuration, nor is `make' needed; `make.bat' both configures and +builds the library.) + + Here are the steps needed to install the library on Unix systems: + + 1. In most cases, `./configure --target=cpu-vendor-os', should work + both for native and cross-compilation. If you get error messages, + your machine might not be supported. + + If you want to compile in a separate object directory, cd to that + directory, and prefix the configure command with the path to the + MP source directory. Not all `make' programs have the necessary + features to support this. In particular, SunOS and Slowaris + `make' have bugs that makes them unable to build from a separate + object directory. Use GNU `make' instead. + + In addition to the standard cpu-vendor-os tuples, MP recognizes + sparc8 and supersparc as valid CPU names. Specifying these CPU + names for relevant systems will improve performance significantly. + + In general, if you want a library that runs as fast as possible, + you should make sure you configure MP for the exact CPU type your + system uses. + + If you have `gcc' in your `PATH', it will be used by default. To + override this, pass `-with-gcc=no' to `configure'. + + 2. `make' + + This will compile MP, and create a library archive file `libgmp.a' + in the working directory. + + 3. `make check' + + This will make sure MP was built correctly. If you get error + messages, please report this to `bug-gmp@prep.ai.mit.edu'. (*Note + Reporting Bugs::, for information on what to include in useful bug + reports.) + + 4. `make install' + + This will copy the file `gmp.h' and `libgmp.a', as well as the info + files, to `/usr/local' (or if you passed the `--prefix' option to + `configure', to the directory given as argument to `--prefix'). + +If you wish to build and install the BSD MP compatible functions, use +`make libmp.a' and `make install-bsdmp'. + + There are some other useful make targets: + + * `doc' + + Create a DVI version of the manual, in `gmp.dvi' and a set of info + files, in `gmp.info', `gmp.info-1', `gmp.info-2', etc. + + * `ps' + + Create a Postscript version of the manual, in `gmp.ps'. + + * `html' + + Create a HTML version of the manual, in `gmp.html'. + + * `clean' + + Delete all object files and archive files, but not the + configuration files. + + * `distclean' + + Delete all files not included in the distribution. + + * `uninstall' + + Delete all files copied by `make install'. + +Known Build Problems +==================== + + GCC 2.7.2 (as well as 2.6.3) for the RS/6000 and PowerPC can not be +used to compile MP, due to a bug in GCC. If you want to use GCC for +these machines, you need to apply the patch below to GCC, or use a +later version of the compiler. + + If you are on a Sequent Symmetry, use the GNU assembler instead of +the system's assembler, since the latter has serious bugs. + + The system compiler on NeXT is a massacred and old gcc, even if the +compiler calls itself `cc'. This compiler cannot be used to build MP. +You need to get a real gcc, and install that before you compile MP. +(NeXT might have fixed this in newer releases of their system.) + + The system C compiler under SunOS 4 has a bug that makes it +miscompile mpq/get_d.c. This will make `make check' fail. + + Please report other problems to `bug-gmp@prep.ai.mit.edu'. *Note +Reporting Bugs::. + + Patch to apply to GCC 2.6.3 and 2.7.2: + + *** config/rs6000/rs6000.md Sun Feb 11 08:22:11 1996 + --- config/rs6000/rs6000.md.new Sun Feb 18 03:33:37 1996 + *************** + *** 920,926 **** + (set (match_operand:SI 0 "gpc_reg_operand" "=r") + (not:SI (match_dup 1)))] + "" + ! "nor. %0,%2,%1" + [(set_attr "type" "compare")]) + + (define_insn "" + --- 920,926 ---- + (set (match_operand:SI 0 "gpc_reg_operand" "=r") + (not:SI (match_dup 1)))] + "" + ! "nor. %0,%1,%1" + [(set_attr "type" "compare")]) + + (define_insn "" + + +File: gmp.info, Node: MP Basics, Next: Reporting Bugs, Prev: Installing MP, Up: Top + +MP Basics +********* + + All declarations needed to use MP are collected in the include file +`gmp.h'. It is designed to work with both C and C++ compilers. + +Nomenclature and Types +====================== + +In this manual, "integer" usually means a multiple precision integer, as +defined by the MP library. The C data type for such integers is +`mpz_t'. Here are some examples of how to declare such integers: + + mpz_t sum; + + struct foo { mpz_t x, y; }; + + mpz_t vec[20]; + +"Rational number" means a multiple precision fraction. The C data type +for these fractions is `mpq_t'. For example: + + mpq_t quotient; + +"Floating point number" or "Float" for short, is an arbitrary precision +mantissa with an limited precision exponent. The C data type for such +objects is `mpf_t'. + +A "limb" means the part of a multi-precision number that fits in a +single word. (We chose this word because a limb of the human body is +analogous to a digit, only larger, and containing several digits.) +Normally a limb contains 32 or 64 bits. The C data type for a limb is +`mp_limb_t'. + +Function Classes +================ + + There are six classes of functions in the MP library: + + 1. Functions for signed integer arithmetic, with names beginning with + `mpz_'. The associated type is `mpz_t'. There are about 100 + functions in this class. + + 2. Functions for rational number arithmetic, with names beginning with + `mpq_'. The associated type is `mpq_t'. There are about 20 + functions in this class, but the functions in the previous class + can be used for performing arithmetic on the numerator and + denominator separately. + + 3. Functions for floating-point arithmetic, with names beginning with + `mpf_'. The associated type is `mpf_t'. There are about 50 + functions is this class. + + 4. Functions compatible with Berkeley MP, such as `itom', `madd', and + `mult'. The associated type is `MINT'. + + 5. Fast low-level functions that operate on natural numbers. These + are used by the functions in the preceding groups, and you can + also call them directly from very time-critical user programs. + These functions' names begin with `mpn_'. There are about 30 + (hard-to-use) functions in this class. + + The associated type is array of `mp_limb_t'. + + 6. Miscellaneous functions. Functions for setting up custom + allocation. + +MP Variable Conventions +======================= + + As a general rule, all MP functions expect output arguments before +input arguments. This notation is based on an analogy with the +assignment operator. (The BSD MP compatibility functions disobey this +rule, having the output argument(s) last.) + + MP allows you to use the same variable for both input and output in +the same expression. For example, the main function for integer +multiplication, `mpz_mul', can be used like this: `mpz_mul (x, x, x)'. +This computes the square of X and puts the result back in X. + + Before you can assign to an MP variable, you need to initialize it +by calling one of the special initialization functions. When you're +done with a variable, you need to clear it out, using one of the +functions for that purpose. Which function to use depends on the type +of variable. See the chapters on integer functions, rational number +functions, and floating-point functions for details. + + A variable should only be initialized once, or at least cleared out +between each initialization. After a variable has been initialized, it +may be assigned to any number of times. + + For efficiency reasons, avoid to initialize and clear out a variable +in loops. Instead, initialize it before entering the loop, and clear +it out after the loop has exited. + + You don't need to be concerned about allocating additional space for +MP variables. All functions in MP automatically allocate additional +space when a variable does not already have enough space. They do not, +however, reduce the space when a smaller number is stored in the +object. Most of the time, this policy is best, since it avoids +frequent re-allocation. + +Useful Macros and Constants +=========================== + + - Global Constant: const int mp_bits_per_limb + The number of bits per limb. + + - Macro: __GNU_MP_VERSION + - Macro: __GNU_MP_VERSION_MINOR + The major and minor MP version, respectively, as integers. + +Compatibility with Version 1.x +============================== + + This version of MP is upward compatible with previous versions of +MP, with a few exceptions. + + 1. Integer division functions round the result differently. The old + functions (`mpz_div', `mpz_divmod', `mpz_mdiv', `mpz_mdivmod', + etc) now all use floor rounding (i.e., they round the quotient to + -infinity). There are a lot of new functions for integer + division, giving the user better control over the rounding. + + 2. The function `mpz_mod' now compute the true *mod* function. + + 3. The functions `mpz_powm' and `mpz_powm_ui' now use *mod* for + reduction. + + 4. The assignment functions for rational numbers do no longer + canonicalize their results. In the case a non-canonical result + could arise from an assignment, the user need to insert an + explicit call to `mpq_canonicalize'. This change was made for + efficiency. + + 5. Output generated by `mpz_out_raw' in this release cannot be read + by `mpz_inp_raw' in previous releases. This change was made for + making the file format truly portable between machines with + different word sizes. + + 6. Several `mpn' functions have changed. But they were intentionally + undocumented in previous releases. + + 7. The functions `mpz_cmp_ui', `mpz_cmp_si', and `mpq_cmp_ui' are now + implementated as macros, and thereby sometimes evaluate their + arguments multiple times. + + 8. The functions `mpz_pow_ui' and `mpz_ui_pow_ui' now yield 1 for + 0^0. (In version 1, they yielded 0.) + + +Getting the Latest Version of MP +================================ + + The latest version of the MP library is available by anonymous ftp +from from `prep.ai.mit.edu'. The file name is +`/pub/gnu/gmp-M.N.tar.gz'. Many sites around the world mirror `prep'; +please use a mirror site near you. + + +File: gmp.info, Node: Reporting Bugs, Next: Integer Functions, Prev: MP Basics, Up: Top + +Reporting Bugs +************** + + If you think you have found a bug in the MP library, please +investigate it and report it. We have made this library available to +you, and it is not to ask too much from you, to ask you to report the +bugs that you find. + + There are a few things you should think about when you put your bug +report together. + + You have to send us a test case that makes it possible for us to +reproduce the bug. Include instructions on how to run the test case. + + You also have to explain what is wrong; if you get a crash, or if +the results printed are incorrect and in that case, in what way. + + It is not uncommon that an observed problem is actually due to a bug +in the compiler used when building MP; the MP code tends to explore +interesting corners in compilers. Therefore, please include compiler +version information in your bug report. This can be extracted using +`what `which cc`', or, if you're using gcc, `gcc -v'. Also, include +the output from `uname -a'. + + If your bug report is good, we will do our best to help you to get a +corrected version of the library; if the bug report is poor, we won't +do anything about it (aside of chiding you to send better bug reports). + + Send your bug report to: `bug-gmp@prep.ai.mit.edu'. + + If you think something in this manual is unclear, or downright +incorrect, or if the language needs to be improved, please send a note +to the same address. + + +File: gmp.info, Node: Integer Functions, Next: Rational Number Functions, Prev: Reporting Bugs, Up: Top + +Integer Functions +***************** + + This chapter describes the MP functions for performing integer +arithmetic. These functions start with the prefix `mpz_'. + + Arbitrary precision integers are stored in objects of type `mpz_t'. + +* Menu: + +* Initializing Integers:: +* Assigning Integers:: +* Simultaneous Integer Init & Assign:: +* Converting Integers:: +* Integer Arithmetic:: +* Comparison Functions:: +* Integer Logic and Bit Fiddling:: +* I/O of Integers:: +* Miscellaneous Integer Functions:: + + +File: gmp.info, Node: Initializing Integers, Next: Assigning Integers, Up: Integer Functions + +Initialization and Assignment Functions +======================================= + + The functions for integer arithmetic assume that all integer objects +are initialized. You do that by calling the function `mpz_init'. + + - Function: void mpz_init (mpz_t INTEGER) + Initialize INTEGER with limb space and set the initial numeric + value to 0. Each variable should normally only be initialized + once, or at least cleared out (using `mpz_clear') between each + initialization. + + Here is an example of using `mpz_init': + + { + mpz_t integ; + mpz_init (integ); + ... + mpz_add (integ, ...); + ... + mpz_sub (integ, ...); + + /* Unless the program is about to exit, do ... */ + mpz_clear (integ); + } + +As you can see, you can store new values any number of times, once an +object is initialized. + + - Function: void mpz_clear (mpz_t INTEGER) + Free the limb space occupied by INTEGER. Make sure to call this + function for all `mpz_t' variables when you are done with them. + + - Function: void * _mpz_realloc (mpz_t INTEGER, mp_size_t NEW_ALLOC) + Change the limb space allocation to NEW_ALLOC limbs. This + function is not normally called from user code, but it can be used + to give memory back to the heap, or to increase the space of a + variable to avoid repeated automatic re-allocation. + + - Function: void mpz_array_init (mpz_t INTEGER_ARRAY[], size_t + ARRAY_SIZE, mp_size_t FIXED_NUM_BITS) + Allocate *fixed* limb space for all ARRAY_SIZE integers in + INTEGER_ARRAY. The fixed allocation for each integer in the array + is enough to store FIXED_NUM_BITS. If the fixed space will be + insufficient for storing the result of a subsequent calculation, + the result is unpredictable. + + This function is useful for decreasing the working set for some + algorithms that use large integer arrays. + + There is no way to de-allocate the storage allocated by this + function. Don't call `mpz_clear'! + + +File: gmp.info, Node: Assigning Integers, Next: Simultaneous Integer Init & Assign, Prev: Initializing Integers, Up: Integer Functions + +Assignment Functions +-------------------- + + These functions assign new values to already initialized integers +(*note Initializing Integers::.). + + - Function: void mpz_set (mpz_t ROP, mpz_t OP) + - Function: void mpz_set_ui (mpz_t ROP, unsigned long int OP) + - Function: void mpz_set_si (mpz_t ROP, signed long int OP) + - Function: void mpz_set_d (mpz_t ROP, double OP) + - Function: void mpz_set_q (mpz_t ROP, mpq_t OP) + - Function: void mpz_set_f (mpz_t ROP, mpf_t OP) + Set the value of ROP from OP. + + - Function: int mpz_set_str (mpz_t ROP, char *STR, int BASE) + Set the value of ROP from STR, a '\0'-terminated C string in base + BASE. White space is allowed in the string, and is simply + ignored. The base may vary from 2 to 36. If BASE is 0, the + actual base is determined from the leading characters: if the + first two characters are `0x' or `0X', hexadecimal is assumed, + otherwise if the first character is `0', octal is assumed, + otherwise decimal is assumed. + + This function returns 0 if the entire string up to the '\0' is a + valid number in base BASE. Otherwise it returns -1. + + +File: gmp.info, Node: Simultaneous Integer Init & Assign, Next: Converting Integers, Prev: Assigning Integers, Up: Integer Functions + +Combined Initialization and Assignment Functions +------------------------------------------------ + + For convenience, MP provides a parallel series of initialize-and-set +functions which initialize the output and then store the value there. +These functions' names have the form `mpz_init_set...' + + Here is an example of using one: + + { + mpz_t pie; + mpz_init_set_str (pie, "3141592653589793238462643383279502884", 10); + ... + mpz_sub (pie, ...); + ... + mpz_clear (pie); + } + +Once the integer has been initialized by any of the `mpz_init_set...' +functions, it can be used as the source or destination operand for the +ordinary integer functions. Don't use an initialize-and-set function +on a variable already initialized! + + - Function: void mpz_init_set (mpz_t ROP, mpz_t OP) + - Function: void mpz_init_set_ui (mpz_t ROP, unsigned long int OP) + - Function: void mpz_init_set_si (mpz_t ROP, signed long int OP) + - Function: void mpz_init_set_d (mpz_t ROP, double OP) + Initialize ROP with limb space and set the initial numeric value + from OP. + + - Function: int mpz_init_set_str (mpz_t ROP, char *STR, int BASE) + Initialize ROP and set its value like `mpz_set_str' (see its + documentation above for details). + + If the string is a correct base BASE number, the function returns + 0; if an error occurs it returns -1. ROP is initialized even if + an error occurs. (I.e., you have to call `mpz_clear' for it.) + + +File: gmp.info, Node: Converting Integers, Next: Integer Arithmetic, Prev: Simultaneous Integer Init & Assign, Up: Integer Functions + +Conversion Functions +==================== + + This section describes functions for converting arbitrary precision +integers to standard C types. Functions for converting *to* arbitrary +precision integers are described in *Note Assigning Integers:: and +*Note I/O of Integers::. + + - Function: unsigned long int mpz_get_ui (mpz_t OP) + Return the least significant part from OP. This function combined + with + `mpz_tdiv_q_2exp(..., OP, CHAR_BIT*sizeof(unsigned long int))' can + be used to extract the limbs of an integer. + + - Function: signed long int mpz_get_si (mpz_t OP) + If OP fits into a `signed long int' return the value of OP. + Otherwise return the least significant part of OP, with the same + sign as OP. + + If OP is too large to fit in a `signed long int', the returned + result is probably not very useful. + + - Function: double mpz_get_d (mpz_t OP) + Convert OP to a double. + + - Function: char * mpz_get_str (char *STR, int BASE, mpz_t OP) + Convert OP to a string of digits in base BASE. The base may vary + from 2 to 36. + + If STR is NULL, space for the result string is allocated using the + default allocation function, and a pointer to the string is + returned. + + If STR is not NULL, it should point to a block of storage enough + large for the result. To find out the right amount of space to + provide for STR, use `mpz_sizeinbase (OP, BASE) + 2'. The two + extra bytes are for a possible minus sign, and for the terminating + null character. + + +File: gmp.info, Node: Integer Arithmetic, Next: Comparison Functions, Prev: Converting Integers, Up: Integer Functions + +Arithmetic Functions +==================== + + - Function: void mpz_add (mpz_t ROP, mpz_t OP1, mpz_t OP2) + - Function: void mpz_add_ui (mpz_t ROP, mpz_t OP1, unsigned long int + OP2) + Set ROP to OP1 + OP2. + + - Function: void mpz_sub (mpz_t ROP, mpz_t OP1, mpz_t OP2) + - Function: void mpz_sub_ui (mpz_t ROP, mpz_t OP1, unsigned long int + OP2) + Set ROP to OP1 - OP2. + + - Function: void mpz_mul (mpz_t ROP, mpz_t OP1, mpz_t OP2) + - Function: void mpz_mul_ui (mpz_t ROP, mpz_t OP1, unsigned long int + OP2) + Set ROP to OP1 times OP2. + + - Function: void mpz_mul_2exp (mpz_t ROP, mpz_t OP1, unsigned long int + OP2) + Set ROP to OP1 times 2 raised to OP2. This operation can also be + defined as a left shift, OP2 steps. + + - Function: void mpz_neg (mpz_t ROP, mpz_t OP) + Set ROP to -OP. + + - Function: void mpz_abs (mpz_t ROP, mpz_t OP) + Set ROP to the absolute value of OP. + + - Function: void mpz_fac_ui (mpz_t ROP, unsigned long int OP) + Set ROP to OP!, the factorial of OP. + +Division functions +------------------ + + Division is undefined if the divisor is zero, and passing a zero +divisor to the divide or modulo functions, as well passing a zero mod +argument to the `mpz_powm' and `mpz_powm_ui' functions, will make these +functions intentionally divide by zero. This gives the user the +possibility to handle arithmetic exceptions in these functions in the +same manner as other arithmetic exceptions. + + There are three main groups of division functions: + * Functions that truncate the quotient towards 0. The names of these + functions start with `mpz_tdiv'. The `t' in the name is short for + `truncate'. + + * Functions that round the quotient towards -infinity. The names of + these routines start with `mpz_fdiv'. The `f' in the name is + short for `floor'. + + * Functions that round the quotient towards +infinity. The names of + these routines start with `mpz_cdiv'. The `c' in the name is + short for `ceil'. + + For each rounding mode, there are a couple of variants. Here `q' +means that the quotient is computed, while `r' means that the remainder +is computed. Functions that compute both the quotient and remainder +have `qr' in the name. + + - Function: void mpz_tdiv_q (mpz_t ROP, mpz_t OP1, mpz_t OP2) + - Function: void mpz_tdiv_q_ui (mpz_t ROP, mpz_t OP1, unsigned long + int OP2) + Set ROP to [OP1/OP2]. The quotient is truncated towards 0. + + - Function: void mpz_tdiv_r (mpz_t ROP, mpz_t OP1, mpz_t OP2) + - Function: void mpz_tdiv_r_ui (mpz_t ROP, mpz_t OP1, unsigned long + int OP2) + Set ROP to (OP1 - [OP1/OP2] * OP2). Unless the remainder is zero, + it has the same sign as the dividend. + + - Function: void mpz_tdiv_qr (mpz_t ROP1, mpz_t ROP2, mpz_t OP1, mpz_t + OP2) + - Function: void mpz_tdiv_qr_ui (mpz_t ROP1, mpz_t ROP2, mpz_t OP1, + unsigned long int OP2) + Divide OP1 by OP2 and put the quotient in ROP1 and the remainder + in ROP2. The quotient is rounded towards 0. Unless the remainder + is zero, it has the same sign as the dividend. + + If ROP1 and ROP2 are the same variable, the results are undefined. + + - Function: void mpz_fdiv_q (mpz_t ROP1, mpz_t OP1, mpz_t OP2) + - Function: void mpz_fdiv_q_ui (mpz_t ROP, mpz_t OP1, unsigned long + int OP2) + Set ROP to OP1/OP2. The quotient is rounded towards -infinity. + + - Function: void mpz_fdiv_r (mpz_t ROP, mpz_t OP1, mpz_t OP2) + - Function: unsigned long int mpz_fdiv_r_ui (mpz_t ROP, mpz_t OP1, + unsigned long int OP2) + Divide OP1 by OP2 and put the remainder in ROP. Unless the + remainder is zero, it has the same sign as the divisor. + + For `mpz_fdiv_r_ui' the remainder is small enough to fit in an + `unsigned long int', and is therefore returned. + + - Function: void mpz_fdiv_qr (mpz_t ROP1, mpz_t ROP2, mpz_t OP1, mpz_t + OP2) + - Function: unsigned long int mpz_fdiv_qr_ui (mpz_t ROP1, mpz_t ROP2, + mpz_t OP1, unsigned long int OP2) + Divide OP1 by OP2 and put the quotient in ROP1 and the remainder + in ROP2. The quotient is rounded towards -infinity. Unless the + remainder is zero, it has the same sign as the divisor. + + For `mpz_fdiv_qr_ui' the remainder is small enough to fit in an + `unsigned long int', and is therefore returned. + + If ROP1 and ROP2 are the same variable, the results are undefined. + + - Function: unsigned long int mpz_fdiv_ui (mpz_t OP1, unsigned long + int OP2) + This function is similar to `mpz_fdiv_r_ui', but the remainder is + only returned; it is not stored anywhere. + + - Function: void mpz_cdiv_q (mpz_t ROP1, mpz_t OP1, mpz_t OP2) + - Function: void mpz_cdiv_q_ui (mpz_t ROP, mpz_t OP1, unsigned long + int OP2) + Set ROP to OP1/OP2. The quotient is rounded towards +infinity. + + - Function: void mpz_cdiv_r (mpz_t ROP, mpz_t OP1, mpz_t OP2) + - Function: unsigned long int mpz_cdiv_r_ui (mpz_t ROP, mpz_t OP1, + unsigned long int OP2) + Divide OP1 by OP2 and put the remainder in ROP. Unless the + remainder is zero, it has the opposite sign as the divisor. + + For `mpz_cdiv_r_ui' the negated remainder is small enough to fit + in an `unsigned long int', and it is therefore returned. + + - Function: void mpz_cdiv_qr (mpz_t ROP1, mpz_t ROP2, mpz_t OP1, mpz_t + OP2) + - Function: unsigned long int mpz_cdiv_qr_ui (mpz_t ROP1, mpz_t ROP2, + mpz_t OP1, unsigned long int OP2) + Divide OP1 by OP2 and put the quotient in ROP1 and the remainder + in ROP2. The quotient is rounded towards +infinity. Unless the + remainder is zero, it has the opposite sign as the divisor. + + For `mpz_cdiv_qr_ui' the negated remainder is small enough to fit + in an `unsigned long int', and it is therefore returned. + + If ROP1 and ROP2 are the same variable, the results are undefined. + + - Function: unsigned long int mpz_cdiv_ui (mpz_t OP1, unsigned long + int OP2) + Return the negated remainder, similar to `mpz_cdiv_r_ui'. (The + difference is that this function doesn't store the remainder + anywhere.) + + - Function: void mpz_mod (mpz_t ROP, mpz_t OP1, mpz_t OP2) + - Function: unsigned long int mpz_mod_ui (mpz_t ROP, mpz_t OP1, + unsigned long int OP2) + Set ROP to OP1 `mod' OP2. The sign of the divisor is ignored, and + the result is always non-negative. + + For `mpz_mod_ui' the remainder is small enough to fit in an + `unsigned long int', and is therefore returned. + + - Function: void mpz_divexact (mpz_t ROP, mpz_t OP1, mpz_t OP2) + Set ROP to OP1/OP2. This function produces correct results only + when it is known in advance that OP2 divides OP1. + + Since mpz_divexact is much faster than any of the other routines + that produce the quotient (*note References::. Jebelean), it is + the best choice for instances in which exact division is known to + occur, such as reducing a rational to lowest terms. + + - Function: void mpz_tdiv_q_2exp (mpz_t ROP, mpz_t OP1, unsigned long + int OP2) + Set ROP to OP1 divided by 2 raised to OP2. The quotient is + rounded towards 0. + + - Function: void mpz_tdiv_r_2exp (mpz_t ROP, mpz_t OP1, unsigned long + int OP2) + Divide OP1 by (2 raised to OP2) and put the remainder in ROP. + Unless it is zero, ROP will have the same sign as OP1. + + - Function: void mpz_fdiv_q_2exp (mpz_t ROP, mpz_t OP1, unsigned long + int OP2) + Set ROP to OP1 divided by 2 raised to OP2. The quotient is + rounded towards -infinity. + + - Function: void mpz_fdiv_r_2exp (mpz_t ROP, mpz_t OP1, unsigned long + int OP2) + Divide OP1 by (2 raised to OP2) and put the remainder in ROP. The + sign of ROP will always be positive. + + This operation can also be defined as masking of the OP2 least + significant bits. + +Exponentialization Functions +---------------------------- + + - Function: void mpz_powm (mpz_t ROP, mpz_t BASE, mpz_t EXP, mpz_t MOD) + - Function: void mpz_powm_ui (mpz_t ROP, mpz_t BASE, unsigned long int + EXP, mpz_t MOD) + Set ROP to (BASE raised to EXP) `mod' MOD. If EXP is negative, + the result is undefined. + + - Function: void mpz_pow_ui (mpz_t ROP, mpz_t BASE, unsigned long int + EXP) + - Function: void mpz_ui_pow_ui (mpz_t ROP, unsigned long int BASE, + unsigned long int EXP) + Set ROP to BASE raised to EXP. The case of 0^0 yields 1. + +Square Root Functions +--------------------- + + - Function: void mpz_sqrt (mpz_t ROP, mpz_t OP) + Set ROP to the truncated integer part of the square root of OP. + + - Function: void mpz_sqrtrem (mpz_t ROP1, mpz_t ROP2, mpz_t OP) + Set ROP1 to the truncated integer part of the square root of OP, + like `mpz_sqrt'. Set ROP2 to OP-ROP1*ROP1, (i.e., zero if OP is a + perfect square). + + If ROP1 and ROP2 are the same variable, the results are undefined. + + - Function: int mpz_perfect_square_p (mpz_t OP) + Return non-zero if OP is a perfect square, i.e., if the square + root of OP is an integer. Return zero otherwise. + +Number Theoretic Functions +-------------------------- + + - Function: int mpz_probab_prime_p (mpz_t OP, int REPS) + If this function returns 0, OP is definitely not prime. If it + returns 1, then OP is `probably' prime. The probability of a + false positive is (1/4)**REPS. A reasonable value of reps is 25. + + An implementation of the probabilistic primality test found in + Seminumerical Algorithms (*note References::. Knuth). + + - Function: void mpz_gcd (mpz_t ROP, mpz_t OP1, mpz_t OP2) + Set ROP to the greatest common divisor of OP1 and OP2. + + - Function: unsigned long int mpz_gcd_ui (mpz_t ROP, mpz_t OP1, + unsigned long int OP2) + Compute the greatest common divisor of OP1 and OP2. If ROP is not + NULL, store the result there. + + If the result is small enough to fit in an `unsigned long int', it + is returned. If the result does not fit, 0 is returned, and the + result is equal to the argument OP1. Note that the result will + always fit if OP2 is non-zero. + + - Function: void mpz_gcdext (mpz_t G, mpz_t S, mpz_t T, mpz_t A, mpz_t + B) + Compute G, S, and T, such that AS + BT = G = `gcd' (A, B). If T is + NULL, that argument is not computed. + + - Function: int mpz_invert (mpz_t ROP, mpz_t OP1, mpz_t OP2) + Compute the inverse of OP1 modulo OP2 and put the result in ROP. + Return non-zero if an inverse exist, zero otherwise. When the + function returns zero, do not assume anything about the value in + ROP. + + - Function: int mpz_jacobi (mpz_t OP1, mpz_t OP2) + - Function: int mpz_legendre (mpz_t OP1, mpz_t OP2) + Compute the Jacobi and Legendre symbols, respectively. + + +File: gmp.info, Node: Comparison Functions, Next: Integer Logic and Bit Fiddling, Prev: Integer Arithmetic, Up: Integer Functions + +Comparison Functions +==================== + + - Function: int mpz_cmp (mpz_t OP1, mpz_t OP2) + Compare OP1 and OP2. Return a positive value if OP1 > OP2, zero + if OP1 = OP2, and a negative value if OP1 < OP2. + + - Macro: int mpz_cmp_ui (mpz_t OP1, unsigned long int OP2) + - Macro: int mpz_cmp_si (mpz_t OP1, signed long int OP2) + Compare OP1 and OP2. Return a positive value if OP1 > OP2, zero + if OP1 = OP2, and a negative value if OP1 < OP2. + + These functions are actually implemented as macros. They evaluate + their arguments multiple times. + + - Macro: int mpz_sgn (mpz_t OP) + Return +1 if OP > 0, 0 if OP = 0, and -1 if OP < 0. + + This function is actually implemented as a macro. It evaluates its + arguments multiple times. + + +File: gmp.info, Node: Integer Logic and Bit Fiddling, Next: I/O of Integers, Prev: Comparison Functions, Up: Integer Functions + +Logical and Bit Manipulation Functions +====================================== + + These functions behave as if two's complement arithmetic were used +(although sign-magnitude is used by the actual implementation). + + - Function: void mpz_and (mpz_t ROP, mpz_t OP1, mpz_t OP2) + Set ROP to OP1 logical-and OP2. + + - Function: void mpz_ior (mpz_t ROP, mpz_t OP1, mpz_t OP2) + Set ROP to OP1 inclusive-or OP2. + + - Function: void mpz_com (mpz_t ROP, mpz_t OP) + Set ROP to the one's complement of OP. + + - Function: unsigned long int mpz_popcount (mpz_t OP) + For non-negative numbers, return the population count of OP. For + negative numbers, return the largest possible value (MAX_ULONG). + + - Function: unsigned long int mpz_hamdist (mpz_t OP1, mpz_t OP2) + If OP1 and OP2 are both non-negative, return the hamming distance + between the two operands. Otherwise, return the largest possible + value (MAX_ULONG). + + It is possible to extend this function to return a useful value + when the operands are both negative, but the current + implementation returns MAX_ULONG in this case. *Do not depend on + this behavior, since it will change in future versions of the + library.* + + - Function: unsigned long int mpz_scan0 (mpz_t OP, unsigned long int + STARTING_BIT) + Scan OP, starting with bit STARTING_BIT, towards more significant + bits, until the first clear bit is found. Return the index of the + found bit. + + - Function: unsigned long int mpz_scan1 (mpz_t OP, unsigned long int + STARTING_BIT) + Scan OP, starting with bit STARTING_BIT, towards more significant + bits, until the first set bit is found. Return the index of the + found bit. + + - Function: void mpz_setbit (mpz_t ROP, unsigned long int BIT_INDEX) + Set bit BIT_INDEX in OP1. + + - Function: void mpz_clrbit (mpz_t ROP, unsigned long int BIT_INDEX) + Clear bit BIT_INDEX in OP1. + + +File: gmp.info, Node: I/O of Integers, Next: Miscellaneous Integer Functions, Prev: Integer Logic and Bit Fiddling, Up: Integer Functions + +Input and Output Functions +========================== + + Functions that perform input from a stdio stream, and functions that +output to a stdio stream. Passing a NULL pointer for a STREAM argument +to any of these functions will make them read from `stdin' and write to +`stdout', respectively. + + When using any of these functions, it is a good idea to include +`stdio.h' before `gmp.h', since that will allow `gmp.h' to define +prototypes for these functions. + + - Function: size_t mpz_out_str (FILE *STREAM, int BASE, mpz_t OP) + Output OP on stdio stream STREAM, as a string of digits in base + BASE. The base may vary from 2 to 36. + + Return the number of bytes written, or if an error occurred, + return 0. + + - Function: size_t mpz_inp_str (mpz_t ROP, FILE *STREAM, int BASE) + Input a possibly white-space preceded string in base BASE from + stdio stream STREAM, and put the read integer in ROP. The base + may vary from 2 to 36. If BASE is 0, the actual base is + determined from the leading characters: if the first two + characters are `0x' or `0X', hexadecimal is assumed, otherwise if + the first character is `0', octal is assumed, otherwise decimal is + assumed. + + Return the number of bytes read, or if an error occurred, return 0. + + - Function: size_t mpz_out_raw (FILE *STREAM, mpz_t OP) + Output OP on stdio stream STREAM, in raw binary format. The + integer is written in a portable format, with 4 bytes of size + information, and that many bytes of limbs. Both the size and the + limbs are written in decreasing significance order (i.e., in + big-endian). + + The output can be read with `mpz_inp_raw'. + + Return the number of bytes written, or if an error occurred, + return 0. + + The output of this can not be read by `mpz_inp_raw' from GMP 1, + because of changes necessary for compatibility between 32-bit and + 64-bit machines. + + - Function: size_t mpz_inp_raw (mpz_t ROP, FILE *STREAM) + Input from stdio stream STREAM in the format written by + `mpz_out_raw', and put the result in ROP. Return the number of + bytes read, or if an error occurred, return 0. + + This routine can read the output from `mpz_out_raw' also from GMP + 1, in spite of changes necessary for compatibility between 32-bit + and 64-bit machines. + + +File: gmp.info, Node: Miscellaneous Integer Functions, Prev: I/O of Integers, Up: Integer Functions + +Miscellaneous Functions +======================= + + - Function: void mpz_random (mpz_t ROP, mp_size_t MAX_SIZE) + Generate a random integer of at most MAX_SIZE limbs. The generated + random number doesn't satisfy any particular requirements of + randomness. Negative random numbers are generated when MAX_SIZE + is negative. + + - Function: void mpz_random2 (mpz_t ROP, mp_size_t MAX_SIZE) + Generate a random integer of at most MAX_SIZE limbs, with long + strings of zeros and ones in the binary representation. Useful + for testing functions and algorithms, since this kind of random + numbers have proven to be more likely to trigger corner-case bugs. + Negative random numbers are generated when MAX_SIZE is negative. + + - Function: size_t mpz_size (mpz_t OP) + Return the size of OP measured in number of limbs. If OP is zero, + the returned value will be zero. + + *This function is obsolete. It will disappear from future MP + releases.* + + - Function: size_t mpz_sizeinbase (mpz_t OP, int BASE) + Return the size of OP measured in number of digits in base BASE. + The base may vary from 2 to 36. The returned value will be exact + or 1 too big. If BASE is a power of 2, the returned value will + always be exact. + + This function is useful in order to allocate the right amount of + space before converting OP to a string. The right amount of + allocation is normally two more than the value returned by + `mpz_sizeinbase' (one extra for a minus sign and one for the + terminating '\0'). + + +File: gmp.info, Node: Rational Number Functions, Next: Floating-point Functions, Prev: Integer Functions, Up: Top + +Rational Number Functions +************************* + + This chapter describes the MP functions for performing arithmetic on +rational numbers. These functions start with the prefix `mpq_'. + + Rational numbers are stored in objects of type `mpq_t'. + + All rational arithmetic functions assume operands have a canonical +form, and canonicalize their result. The canonical from means that the +denominator and the numerator have no common factors, and that the +denominator is positive. Zero has the unique representation 0/1. + + Pure assignment functions do not canonicalize the assigned variable. +It is the responsibility of the user to canonicalize the assigned +variable before any arithmetic operations are performed on that +variable. *Note that this is an incompatible change from version 1 of +the library.* + + - Function: void mpq_canonicalize (mpq_t OP) + Remove any factors that are common to the numerator and + denominator of OP, and make the denominator positive. + +* Menu: + +* Initializing Rationals:: +* Assigning Rationals:: +* Simultaneous Integer Init & Assign:: +* Comparing Rationals:: +* Applying Integer Functions:: +* Miscellaneous Rational Functions:: + + +File: gmp.info, Node: Initializing Rationals, Next: Assigning Rationals, Prev: Rational Number Functions, Up: Rational Number Functions + +Initialization and Assignment Functions +======================================= + + - Function: void mpq_init (mpq_t DEST_RATIONAL) + Initialize DEST_RATIONAL and set it to 0/1. Each variable should + normally only be initialized once, or at least cleared out (using + the function `mpq_clear') between each initialization. + + - Function: void mpq_clear (mpq_t RATIONAL_NUMBER) + Free the space occupied by RATIONAL_NUMBER. Make sure to call this + function for all `mpq_t' variables when you are done with them. + + - Function: void mpq_set (mpq_t ROP, mpq_t OP) + - Function: void mpq_set_z (mpq_t ROP, mpz_t OP) + Assign ROP from OP. + + - Function: void mpq_set_ui (mpq_t ROP, unsigned long int OP1, + unsigned long int OP2) + - Function: void mpq_set_si (mpq_t ROP, signed long int OP1, unsigned + long int OP2) + Set the value of ROP to OP1/OP2. Note that if OP1 and OP2 have + common factors, ROP has to be passed to `mpq_canonicalize' before + any operations are performed on ROP. + + +File: gmp.info, Node: Assigning Rationals, Next: Comparing Rationals, Prev: Initializing Rationals, Up: Rational Number Functions + +Arithmetic Functions +==================== + + - Function: void mpq_add (mpq_t SUM, mpq_t ADDEND1, mpq_t ADDEND2) + Set SUM to ADDEND1 + ADDEND2. + + - Function: void mpq_sub (mpq_t DIFFERENCE, mpq_t MINUEND, mpq_t + SUBTRAHEND) + Set DIFFERENCE to MINUEND - SUBTRAHEND. + + - Function: void mpq_mul (mpq_t PRODUCT, mpq_t MULTIPLIER, mpq_t + MULTIPLICAND) + Set PRODUCT to MULTIPLIER times MULTIPLICAND. + + - Function: void mpq_div (mpq_t QUOTIENT, mpq_t DIVIDEND, mpq_t + DIVISOR) + Set QUOTIENT to DIVIDEND/DIVISOR. + + - Function: void mpq_neg (mpq_t NEGATED_OPERAND, mpq_t OPERAND) + Set NEGATED_OPERAND to -OPERAND. + + - Function: void mpq_inv (mpq_t INVERTED_NUMBER, mpq_t NUMBER) + Set INVERTED_NUMBER to 1/NUMBER. If the new denominator is zero, + this routine will divide by zero. + + +File: gmp.info, Node: Comparing Rationals, Next: Applying Integer Functions, Prev: Assigning Rationals, Up: Rational Number Functions + +Comparison Functions +==================== + + - Function: int mpq_cmp (mpq_t OP1, mpq_t OP2) + Compare OP1 and OP2. Return a positive value if OP1 > OP2, zero + if OP1 = OP2, and a negative value if OP1 < OP2. + + To determine if two rationals are equal, `mpq_equal' is faster than + `mpq_cmp'. + + - Macro: int mpq_cmp_ui (mpq_t OP1, unsigned long int NUM2, unsigned + long int DEN2) + Compare OP1 and NUM2/DEN2. Return a positive value if OP1 > + NUM2/DEN2, zero if OP1 = NUM2/DEN2, and a negative value if OP1 < + NUM2/DEN2. + + This routine allows that NUM2 and DEN2 have common factors. + + This function is actually implemented as a macro. It evaluates its + arguments multiple times. + + - Macro: int mpq_sgn (mpq_t OP) + Return +1 if OP > 0, 0 if OP = 0, and -1 if OP < 0. + + This function is actually implemented as a macro. It evaluates its + arguments multiple times. + + - Function: int mpq_equal (mpq_t OP1, mpq_t OP2) + Return non-zero if OP1 and OP2 are equal, zero if they are + non-equal. Although `mpq_cmp' can be used for the same purpose, + this function is much faster. + + +File: gmp.info, Node: Applying Integer Functions, Next: Miscellaneous Rational Functions, Prev: Comparing Rationals, Up: Rational Number Functions + +Applying Integer Functions to Rationals +======================================= + + The set of `mpq' functions is quite small. In particular, there are +no functions for either input or output. But there are two macros that +allow us to apply any `mpz' function on the numerator or denominator of +a rational number. If these macros are used to assign to the rational +number, `mpq_canonicalize' normally need to be called afterwards. + + - Macro: mpz_t mpq_numref (mpq_t OP) + - Macro: mpz_t mpq_denref (mpq_t OP) + Return a reference to the numerator and denominator of OP, + respectively. The `mpz' functions can be used on the result of + these macros. + + +File: gmp.info, Node: Miscellaneous Rational Functions, Prev: Applying Integer Functions, Up: Rational Number Functions + +Miscellaneous Functions +======================= + + - Function: double mpq_get_d (mpq_t OP) + Convert OP to a double. + + These functions assign between either the numerator or denominator +of a rational, and an integer. Instead of using these functions, it is +preferable to use the more general mechanisms `mpq_numref' and +`mpq_denref', together with `mpz_set'. + + - Function: void mpq_set_num (mpq_t RATIONAL, mpz_t NUMERATOR) + Copy NUMERATOR to the numerator of RATIONAL. When this risks to + make the numerator and denominator of RATIONAL have common + factors, you have to pass RATIONAL to `mpq_canonicalize' before + any operations are performed on RATIONAL. + + This function is equivalent to `mpz_set (mpq_numref (RATIONAL), + NUMERATOR)'. + + - Function: void mpq_set_den (mpq_t RATIONAL, mpz_t DENOMINATOR) + Copy DENOMINATOR to the denominator of RATIONAL. When this risks + to make the numerator and denominator of RATIONAL have common + factors, or if the denominator might be negative, you have to pass + RATIONAL to `mpq_canonicalize' before any operations are performed + on RATIONAL. + + *In version 1 of the library, negative denominators were handled by + copying the sign to the numerator. That is no longer done.* + + This function is equivalent to `mpz_set (mpq_denref (RATIONAL), + DENOMINATORS)'. + + - Function: void mpq_get_num (mpz_t NUMERATOR, mpq_t RATIONAL) + Copy the numerator of RATIONAL to the integer NUMERATOR, to + prepare for integer operations on the numerator. + + This function is equivalent to `mpz_set (NUMERATOR, mpq_numref + (RATIONAL))'. + + - Function: void mpq_get_den (mpz_t DENOMINATOR, mpq_t RATIONAL) + Copy the denominator of RATIONAL to the integer DENOMINATOR, to + prepare for integer operations on the denominator. + + This function is equivalent to `mpz_set (DENOMINATOR, mpq_denref + (RATIONAL))'. + |
