diff options
Diffstat (limited to 'gmp-6.3.0/doc/gmp.info-2')
| -rw-r--r-- | gmp-6.3.0/doc/gmp.info-2 | 4104 |
1 files changed, 4104 insertions, 0 deletions
diff --git a/gmp-6.3.0/doc/gmp.info-2 b/gmp-6.3.0/doc/gmp.info-2 new file mode 100644 index 0000000..af839fb --- /dev/null +++ b/gmp-6.3.0/doc/gmp.info-2 @@ -0,0 +1,4104 @@ +This is gmp.info, produced by makeinfo version 6.7 from gmp.texi. + +This manual describes how to install and use the GNU multiple precision +arithmetic library, version 6.3.0. + + Copyright 1991, 1993-2016, 2018-2020 Free Software Foundation, Inc. + + Permission is granted to copy, distribute and/or modify this document +under the terms of the GNU Free Documentation License, Version 1.3 or +any later version published by the Free Software Foundation; with no +Invariant Sections, with the Front-Cover Texts being "A GNU Manual", and +with the Back-Cover Texts being "You have freedom to copy and modify +this GNU Manual, like GNU software". A copy of the license is included +in *note GNU Free Documentation License::. +INFO-DIR-SECTION GNU libraries +START-INFO-DIR-ENTRY +* gmp: (gmp). GNU Multiple Precision Arithmetic Library. +END-INFO-DIR-ENTRY + + +File: gmp.info, Node: Divide and Conquer Division, Next: Block-Wise Barrett Division, Prev: Basecase Division, Up: Division Algorithms + +15.2.3 Divide and Conquer Division +---------------------------------- + +For divisors larger than 'DC_DIV_QR_THRESHOLD', division is done by +dividing. Or to be precise by a recursive divide and conquer algorithm +based on work by Moenck and Borodin, Jebelean, and Burnikel and Ziegler +(*note References::). + + The algorithm consists essentially of recognising that a 2NxN +division can be done with the basecase division algorithm (*note +Basecase Division::), but using N/2 limbs as a base, not just a single +limb. This way the multiplications that arise are (N/2)x(N/2) and can +take advantage of Karatsuba and higher multiplication algorithms (*note +Multiplication Algorithms::). The two "digits" of the quotient are +formed by recursive Nx(N/2) divisions. + + If the (N/2)x(N/2) multiplies are done with a basecase multiplication +then the work is about the same as a basecase division, but with more +function call overheads and with some subtractions separated from the +multiplies. These overheads mean that it's only when N/2 is above +'MUL_TOOM22_THRESHOLD' that divide and conquer is of use. + + 'DC_DIV_QR_THRESHOLD' is based on the divisor size N, so it will be +somewhere above twice 'MUL_TOOM22_THRESHOLD', but how much above depends +on the CPU. An optimized 'mpn_mul_basecase' can lower +'DC_DIV_QR_THRESHOLD' a little by offering a ready-made advantage over +repeated 'mpn_submul_1' calls. + + Divide and conquer is asymptotically O(M(N)*log(N)) where M(N) is the +time for an NxN multiplication done with FFTs. The actual time is a sum +over multiplications of the recursed sizes, as can be seen near the end +of section 2.2 of Burnikel and Ziegler. For example, within the Toom-3 +range, divide and conquer is 2.63*M(N). With higher algorithms the M(N) +term improves and the multiplier tends to log(N). In practice, at +moderate to large sizes, a 2NxN division is about 2 to 4 times slower +than an NxN multiplication. + + +File: gmp.info, Node: Block-Wise Barrett Division, Next: Exact Division, Prev: Divide and Conquer Division, Up: Division Algorithms + +15.2.4 Block-Wise Barrett Division +---------------------------------- + +For the largest divisions, a block-wise Barrett division algorithm is +used. Here, the divisor is inverted to a precision determined by the +relative size of the dividend and divisor. Blocks of quotient limbs are +then generated by multiplying blocks from the dividend by the inverse. + + Our block-wise algorithm computes a smaller inverse than in the plain +Barrett algorithm. For a 2n/n division, the inverse will be just +ceil(n/2) limbs. + + +File: gmp.info, Node: Exact Division, Next: Exact Remainder, Prev: Block-Wise Barrett Division, Up: Division Algorithms + +15.2.5 Exact Division +--------------------- + +A so-called exact division is when the dividend is known to be an exact +multiple of the divisor. Jebelean's exact division algorithm uses this +knowledge to make some significant optimizations (*note References::). + + The idea can be illustrated in decimal for example with 368154 +divided by 543. Because the low digit of the dividend is 4, the low +digit of the quotient must be 8. This is arrived at from 4*7 mod 10, +using the fact 7 is the modular inverse of 3 (the low digit of the +divisor), since 3*7 == 1 mod 10. So 8*543=4344 can be subtracted from +the dividend leaving 363810. Notice the low digit has become zero. + + The procedure is repeated at the second digit, with the next quotient +digit 7 (7 == 1*7 mod 10), subtracting 7*543=3801, leaving 325800. And +finally at the third digit with quotient digit 6 (8*7 mod 10), +subtracting 6*543=3258 leaving 0. So the quotient is 678. + + Notice however that the multiplies and subtractions don't need to +extend past the low three digits of the dividend, since that's enough to +determine the three quotient digits. For the last quotient digit no +subtraction is needed at all. On a 2NxN division like this one, only +about half the work of a normal basecase division is necessary. + + For an NxM exact division producing Q=N-M quotient limbs, the saving +over a normal basecase division is in two parts. Firstly, each of the Q +quotient limbs needs only one multiply, not a 2x1 divide and multiply. +Secondly, the crossproducts are reduced when Q>M to Q*M-M*(M+1)/2, or +when Q<=M to Q*(Q-1)/2. Notice the savings are complementary. If Q is +big then many divisions are saved, or if Q is small then the +crossproducts reduce to a small number. + + The modular inverse used is calculated efficiently by 'binvert_limb' +in 'gmp-impl.h'. This does four multiplies for a 32-bit limb, or six +for a 64-bit limb. 'tune/modlinv.c' has some alternate implementations +that might suit processors better at bit twiddling than multiplying. + + The sub-quadratic exact division described by Jebelean in "Exact +Division with Karatsuba Complexity" is not currently implemented. It +uses a rearrangement similar to the divide and conquer for normal +division (*note Divide and Conquer Division::), but operating from low +to high. A further possibility not currently implemented is +"Bidirectional Exact Integer Division" by Krandick and Jebelean which +forms quotient limbs from both the high and low ends of the dividend, +and can halve once more the number of crossproducts needed in a 2NxN +division. + + A special case exact division by 3 exists in 'mpn_divexact_by3', +supporting Toom-3 multiplication and 'mpq' canonicalizations. It forms +quotient digits with a multiply by the modular inverse of 3 (which is +'0xAA..AAB') and uses two comparisons to determine a borrow for the next +limb. The multiplications don't need to be on the dependent chain, as +long as the effect of the borrows is applied, which can help chips with +pipelined multipliers. + + +File: gmp.info, Node: Exact Remainder, Next: Small Quotient Division, Prev: Exact Division, Up: Division Algorithms + +15.2.6 Exact Remainder +---------------------- + +If the exact division algorithm is done with a full subtraction at each +stage and the dividend isn't a multiple of the divisor, then low zero +limbs are produced but with a remainder in the high limbs. For dividend +a, divisor d, quotient q, and b = 2^mp_bits_per_limb, this remainder r +is of the form + + a = q*d + r*b^n + + n represents the number of zero limbs produced by the subtractions, +that being the number of limbs produced for q. r will be in the range +0<=r<d and can be viewed as a remainder, but one shifted up by a factor +of b^n. + + Carrying out full subtractions at each stage means the same number of +cross products must be done as a normal division, but there's still some +single limb divisions saved. When d is a single limb some +simplifications arise, providing good speedups on a number of +processors. + + The functions 'mpn_divexact_by3', 'mpn_modexact_1_odd' and the +internal 'mpn_redc_X' functions differ subtly in how they return r, +leading to some negations in the above formula, but all are essentially +the same. + + Clearly r is zero when a is a multiple of d, and this leads to +divisibility or congruence tests which are potentially more efficient +than a normal division. + + The factor of b^n on r can be ignored in a GCD when d is odd, hence +the use of 'mpn_modexact_1_odd' by 'mpn_gcd_1' and 'mpz_kronecker_ui' +etc (*note Greatest Common Divisor Algorithms::). + + Montgomery's REDC method for modular multiplications uses operands of +the form of x*b^-n and y*b^-n and on calculating (x*b^-n)*(y*b^-n) uses +the factor of b^n in the exact remainder to reach a product in the same +form (x*y)*b^-n (*note Modular Powering Algorithm::). + + Notice that r generally gives no useful information about the +ordinary remainder a mod d since b^n mod d could be anything. If +however b^n == 1 mod d, then r is the negative of the ordinary +remainder. This occurs whenever d is a factor of b^n-1, as for example +with 3 in 'mpn_divexact_by3'. For a 32 or 64 bit limb other such +factors include 5, 17 and 257, but no particular use has been found for +this. + + +File: gmp.info, Node: Small Quotient Division, Prev: Exact Remainder, Up: Division Algorithms + +15.2.7 Small Quotient Division +------------------------------ + +An NxM division where the number of quotient limbs Q=N-M is small can be +optimized somewhat. + + An ordinary basecase division normalizes the divisor by shifting it +to make the high bit set, shifting the dividend accordingly, and +shifting the remainder back down at the end of the calculation. This is +wasteful if only a few quotient limbs are to be formed. Instead a +division of just the top 2*Q limbs of the dividend by the top Q limbs of +the divisor can be used to form a trial quotient. This requires only +those limbs normalized, not the whole of the divisor and dividend. + + A multiply and subtract then applies the trial quotient to the M-Q +unused limbs of the divisor and N-Q dividend limbs (which includes Q +limbs remaining from the trial quotient division). The starting trial +quotient can be 1 or 2 too big, but all cases of 2 too big and most +cases of 1 too big are detected by first comparing the most significant +limbs that will arise from the subtraction. An addback is done if the +quotient still turns out to be 1 too big. + + This whole procedure is essentially the same as one step of the +basecase algorithm done in a Q limb base, though with the trial quotient +test done only with the high limbs, not an entire Q limb "digit" +product. The correctness of this weaker test can be established by +following the argument of Knuth section 4.3.1 exercise 20 but with the +v2*q>b*r+u2 condition appropriately relaxed. + + +File: gmp.info, Node: Greatest Common Divisor Algorithms, Next: Powering Algorithms, Prev: Division Algorithms, Up: Algorithms + +15.3 Greatest Common Divisor +============================ + +* Menu: + +* Binary GCD:: +* Lehmer's Algorithm:: +* Subquadratic GCD:: +* Extended GCD:: +* Jacobi Symbol:: + + +File: gmp.info, Node: Binary GCD, Next: Lehmer's Algorithm, Prev: Greatest Common Divisor Algorithms, Up: Greatest Common Divisor Algorithms + +15.3.1 Binary GCD +----------------- + +At small sizes GMP uses an O(N^2) binary style GCD. This is described +in many textbooks, for example Knuth section 4.5.2 algorithm B. It +simply consists of successively reducing odd operands a and b using + + a,b = abs(a-b),min(a,b) + strip factors of 2 from a + + The Euclidean GCD algorithm, as per Knuth algorithms E and A, +repeatedly computes the quotient q = floor(a/b) and replaces a,b by v, u +- q v. The binary algorithm has so far been found to be faster than the +Euclidean algorithm everywhere. One reason the binary method does well +is that the implied quotient at each step is usually small, so often +only one or two subtractions are needed to get the same effect as a +division. Quotients 1, 2 and 3 for example occur 67.7% of the time, see +Knuth section 4.5.3 Theorem E. + + When the implied quotient is large, meaning b is much smaller than a, +then a division is worthwhile. This is the basis for the initial a mod +b reductions in 'mpn_gcd' and 'mpn_gcd_1' (the latter for both Nx1 and +1x1 cases). But after that initial reduction, big quotients occur too +rarely to make it worth checking for them. + + + The final 1x1 GCD in 'mpn_gcd_1' is done in the generic C code as +described above. For two N-bit operands, the algorithm takes about 0.68 +iterations per bit. For optimum performance some attention needs to be +paid to the way the factors of 2 are stripped from a. + + Firstly it may be noted that in two's complement the number of low +zero bits on a-b is the same as b-a, so counting or testing can begin on +a-b without waiting for abs(a-b) to be determined. + + A loop stripping low zero bits tends not to branch predict well, +since the condition is data dependent. But on average there's only a +few low zeros, so an option is to strip one or two bits arithmetically +then loop for more (as done for AMD K6). Or use a lookup table to get a +count for several bits then loop for more (as done for AMD K7). An +alternative approach is to keep just one of a and b odd and iterate + + a,b = abs(a-b), min(a,b) + a = a/2 if even + b = b/2 if even + + This requires about 1.25 iterations per bit, but stripping of a +single bit at each step avoids any branching. Repeating the bit strip +reduces to about 0.9 iterations per bit, which may be a worthwhile +tradeoff. + + Generally with the above approaches a speed of perhaps 6 cycles per +bit can be achieved, which is still not terribly fast with for instance +a 64-bit GCD taking nearly 400 cycles. It's this sort of time which +means it's not usually advantageous to combine a set of divisibility +tests into a GCD. + + Currently, the binary algorithm is used for GCD only when N < 3. + + +File: gmp.info, Node: Lehmer's Algorithm, Next: Subquadratic GCD, Prev: Binary GCD, Up: Greatest Common Divisor Algorithms + +15.3.2 Lehmer's algorithm +------------------------- + +Lehmer's improvement of the Euclidean algorithms is based on the +observation that the initial part of the quotient sequence depends only +on the most significant parts of the inputs. The variant of Lehmer's +algorithm used in GMP splits off the most significant two limbs, as +suggested, e.g., in "A Double-Digit Lehmer-Euclid Algorithm" by Jebelean +(*note References::). The quotients of two double-limb inputs are +collected as a 2 by 2 matrix with single-limb elements. This is done by +the function 'mpn_hgcd2'. The resulting matrix is applied to the inputs +using 'mpn_mul_1' and 'mpn_submul_1'. Each iteration usually reduces +the inputs by almost one limb. In the rare case of a large quotient, no +progress can be made by examining just the most significant two limbs, +and the quotient is computed using plain division. + + The resulting algorithm is asymptotically O(N^2), just as the +Euclidean algorithm and the binary algorithm. The quadratic part of the +work are the calls to 'mpn_mul_1' and 'mpn_submul_1'. For small sizes, +the linear work is also significant. There are roughly N calls to the +'mpn_hgcd2' function. This function uses a couple of important +optimizations: + + * It uses the same relaxed notion of correctness as 'mpn_hgcd' (see + next section). This means that when called with the most + significant two limbs of two large numbers, the returned matrix + does not always correspond exactly to the initial quotient sequence + for the two large numbers; the final quotient may sometimes be one + off. + + * It takes advantage of the fact that the quotients are usually + small. The division operator is not used, since the corresponding + assembler instruction is very slow on most architectures. (This + code could probably be improved further, it uses many branches that + are unfriendly to prediction.) + + * It switches from double-limb calculations to single-limb + calculations half-way through, when the input numbers have been + reduced in size from two limbs to one and a half. + + +File: gmp.info, Node: Subquadratic GCD, Next: Extended GCD, Prev: Lehmer's Algorithm, Up: Greatest Common Divisor Algorithms + +15.3.3 Subquadratic GCD +----------------------- + +For inputs larger than 'GCD_DC_THRESHOLD', GCD is computed via the HGCD +(Half GCD) function, as a generalization to Lehmer's algorithm. + + Let the inputs a,b be of size N limbs each. Put S = floor(N/2) + 1. +Then HGCD(a,b) returns a transformation matrix T with non-negative +elements, and reduced numbers (c;d) = T^{-1} (a;b). The reduced numbers +c,d must be larger than S limbs, while their difference abs(c-d) must +fit in S limbs. The matrix elements will also be of size roughly N/2. + + The HGCD base case uses Lehmer's algorithm, but with the above stop +condition that returns reduced numbers and the corresponding +transformation matrix half-way through. For inputs larger than +'HGCD_THRESHOLD', HGCD is computed recursively, using the divide and +conquer algorithm in "On Schönhage's algorithm and subquadratic integer +GCD computation" by Möller (*note References::). The recursive +algorithm consists of these main steps. + + * Call HGCD recursively, on the most significant N/2 limbs. Apply + the resulting matrix T_1 to the full numbers, reducing them to a + size just above 3N/2. + + * Perform a small number of division or subtraction steps to reduce + the numbers to size below 3N/2. This is essential mainly for the + unlikely case of large quotients. + + * Call HGCD recursively, on the most significant N/2 limbs of the + reduced numbers. Apply the resulting matrix T_2 to the full + numbers, reducing them to a size just above N/2. + + * Compute T = T_1 T_2. + + * Perform a small number of division and subtraction steps to satisfy + the requirements, and return. + + GCD is then implemented as a loop around HGCD, similarly to Lehmer's +algorithm. Where Lehmer repeatedly chops off the top two limbs, calls +'mpn_hgcd2', and applies the resulting matrix to the full numbers, the +sub-quadratic GCD chops off the most significant third of the limbs (the +proportion is a tuning parameter, and 1/3 seems to be more efficient +than, e.g., 1/2), calls 'mpn_hgcd', and applies the resulting matrix. +Once the input numbers are reduced to size below 'GCD_DC_THRESHOLD', +Lehmer's algorithm is used for the rest of the work. + + The asymptotic running time of both HGCD and GCD is O(M(N)*log(N)), +where M(N) is the time for multiplying two N-limb numbers. + + +File: gmp.info, Node: Extended GCD, Next: Jacobi Symbol, Prev: Subquadratic GCD, Up: Greatest Common Divisor Algorithms + +15.3.4 Extended GCD +------------------- + +The extended GCD function, or GCDEXT, calculates gcd(a,b) and also +cofactors x and y satisfying a*x+b*y=gcd(a,b). All the algorithms used +for plain GCD are extended to handle this case. The binary algorithm is +used only for single-limb GCDEXT. Lehmer's algorithm is used for sizes +up to 'GCDEXT_DC_THRESHOLD'. Above this threshold, GCDEXT is +implemented as a loop around HGCD, but with more book-keeping to keep +track of the cofactors. This gives the same asymptotic running time as +for GCD and HGCD, O(M(N)*log(N)). + + One difference to plain GCD is that while the inputs a and b are +reduced as the algorithm proceeds, the cofactors x and y grow in size. +This makes the tuning of the chopping-point more difficult. The current +code chops off the most significant half of the inputs for the call to +HGCD in the first iteration, and the most significant two thirds for the +remaining calls. This strategy could surely be improved. Also the stop +condition for the loop, where Lehmer's algorithm is invoked once the +inputs are reduced below 'GCDEXT_DC_THRESHOLD', could maybe be improved +by taking into account the current size of the cofactors. + + +File: gmp.info, Node: Jacobi Symbol, Prev: Extended GCD, Up: Greatest Common Divisor Algorithms + +15.3.5 Jacobi Symbol +-------------------- + +Jacobi symbol (A/B) + + Initially if either operand fits in a single limb, a reduction is +done with either 'mpn_mod_1' or 'mpn_modexact_1_odd', followed by the +binary algorithm on a single limb. The binary algorithm is well suited +to a single limb, and the whole calculation in this case is quite +efficient. + + For inputs larger than 'GCD_DC_THRESHOLD', 'mpz_jacobi', +'mpz_legendre' and 'mpz_kronecker' are computed via the HGCD (Half GCD) +function, as a generalization to Lehmer's algorithm. + + Most GCD algorithms reduce a and b by repeatedly computing the +quotient q = floor(a/b) and iteratively replacing + + a, b = b, a - q * b + + Different algorithms use different methods for calculating q, but the +core algorithm is the same if we use *note Lehmer's Algorithm:: or *note +HGCD: Subquadratic GCD. + + At each step it is possible to compute if the reduction inverts the +Jacobi symbol based on the two least significant bits of A and B. For +more details see "Efficient computation of the Jacobi symbol" by Möller +(*note References::). + + A small set of bits is thus used to track state + * current sign of result (1 bit) + + * two least significant bits of A and B (4 bits) + + * a pointer to which input is currently the denominator (1 bit) + + In all the routines sign changes for the result are accumulated using +fast bit twiddling which avoids conditional jumps. + + The final result is calculated after verifying the inputs are coprime +(GCD = 1) by raising (-1)^e. + + Much of the HGCD code is shared directly with the HGCD +implementations, such as the 2x2 matrix calculation, *Note Lehmer's +Algorithm:: basecase and 'GCD_DC_THRESHOLD'. + + The asymptotic running time is O(M(N)*log(N)), where M(N) is the time +for multiplying two N-limb numbers. + + +File: gmp.info, Node: Powering Algorithms, Next: Root Extraction Algorithms, Prev: Greatest Common Divisor Algorithms, Up: Algorithms + +15.4 Powering Algorithms +======================== + +* Menu: + +* Normal Powering Algorithm:: +* Modular Powering Algorithm:: + + +File: gmp.info, Node: Normal Powering Algorithm, Next: Modular Powering Algorithm, Prev: Powering Algorithms, Up: Powering Algorithms + +15.4.1 Normal Powering +---------------------- + +Normal 'mpz' or 'mpf' powering uses a simple binary algorithm, +successively squaring and then multiplying by the base when a 1 bit is +seen in the exponent, as per Knuth section 4.6.3. The "left to right" +variant described there is used rather than algorithm A, since it's just +as easy and can be done with somewhat less temporary memory. + + +File: gmp.info, Node: Modular Powering Algorithm, Prev: Normal Powering Algorithm, Up: Powering Algorithms + +15.4.2 Modular Powering +----------------------- + +Modular powering is implemented using a 2^k-ary sliding window +algorithm, as per "Handbook of Applied Cryptography" algorithm 14.85 +(*note References::). k is chosen according to the size of the +exponent. Larger exponents use larger values of k, the choice being +made to minimize the average number of multiplications that must +supplement the squaring. + + The modular multiplies and squarings use either a simple division or +the REDC method by Montgomery (*note References::). REDC is a little +faster, essentially saving N single limb divisions in a fashion similar +to an exact remainder (*note Exact Remainder::). + + +File: gmp.info, Node: Root Extraction Algorithms, Next: Radix Conversion Algorithms, Prev: Powering Algorithms, Up: Algorithms + +15.5 Root Extraction Algorithms +=============================== + +* Menu: + +* Square Root Algorithm:: +* Nth Root Algorithm:: +* Perfect Square Algorithm:: +* Perfect Power Algorithm:: + + +File: gmp.info, Node: Square Root Algorithm, Next: Nth Root Algorithm, Prev: Root Extraction Algorithms, Up: Root Extraction Algorithms + +15.5.1 Square Root +------------------ + +Square roots are taken using the "Karatsuba Square Root" algorithm by +Paul Zimmermann (*note References::). + + An input n is split into four parts of k bits each, so with b=2^k we +have n = a3*b^3 + a2*b^2 + a1*b + a0. Part a3 must be "normalized" so +that either the high or second highest bit is set. In GMP, k is kept on +a limb boundary and the input is left shifted (by an even number of +bits) to normalize. + + The square root of the high two parts is taken, by recursive +application of the algorithm (bottoming out in a one-limb Newton's +method), + + s1,r1 = sqrtrem (a3*b + a2) + + This is an approximation to the desired root and is extended by a +division to give s,r, + + q,u = divrem (r1*b + a1, 2*s1) + s = s1*b + q + r = u*b + a0 - q^2 + + The normalization requirement on a3 means at this point s is either +correct or 1 too big. r is negative in the latter case, so + + if r < 0 then + r = r + 2*s - 1 + s = s - 1 + + The algorithm is expressed in a divide and conquer form, but as noted +in the paper it can also be viewed as a discrete variant of Newton's +method, or as a variation on the schoolboy method (no longer taught) for +square roots two digits at a time. + + If the remainder r is not required then usually only a few high limbs +of r and u need to be calculated to determine whether an adjustment to s +is required. This optimization is not currently implemented. + + In the Karatsuba multiplication range this algorithm is +O(1.5*M(N/2)), where M(n) is the time to multiply two numbers of n +limbs. In the FFT multiplication range this grows to a bound of +O(6*M(N/2)). In practice a factor of about 1.5 to 1.8 is found in the +Karatsuba and Toom-3 ranges, growing to 2 or 3 in the FFT range. + + The algorithm does all its calculations in integers and the resulting +'mpn_sqrtrem' is used for both 'mpz_sqrt' and 'mpf_sqrt'. The extended +precision given by 'mpf_sqrt_ui' is obtained by padding with zero limbs. + + +File: gmp.info, Node: Nth Root Algorithm, Next: Perfect Square Algorithm, Prev: Square Root Algorithm, Up: Root Extraction Algorithms + +15.5.2 Nth Root +--------------- + +Integer Nth roots are taken using Newton's method with the following +iteration, where A is the input and n is the root to be taken. + + 1 A + a[i+1] = - * ( --------- + (n-1)*a[i] ) + n a[i]^(n-1) + + The initial approximation a[1] is generated bitwise by successively +powering a trial root with or without new 1 bits, aiming to be just +above the true root. The iteration converges quadratically when started +from a good approximation. When n is large more initial bits are needed +to get good convergence. The current implementation is not particularly +well optimized. + + +File: gmp.info, Node: Perfect Square Algorithm, Next: Perfect Power Algorithm, Prev: Nth Root Algorithm, Up: Root Extraction Algorithms + +15.5.3 Perfect Square +--------------------- + +A significant fraction of non-squares can be quickly identified by +checking whether the input is a quadratic residue modulo small integers. + + 'mpz_perfect_square_p' first tests the input mod 256, which means +just examining the low byte. Only 44 different values occur for squares +mod 256, so 82.8% of inputs can be immediately identified as +non-squares. + + On a 32-bit system similar tests are done mod 9, 5, 7, 13 and 17, for +a total 99.25% of inputs identified as non-squares. On a 64-bit system +97 is tested too, for a total 99.62%. + + These moduli are chosen because they're factors of 2^24-1 (or 2^48-1 +for 64-bits), and such a remainder can be quickly taken just using +additions (see 'mpn_mod_34lsub1'). + + When nails are in use moduli are instead selected by the 'gen-psqr.c' +program and applied with an 'mpn_mod_1'. The same 2^24-1 or 2^48-1 +could be done with nails using some extra bit shifts, but this is not +currently implemented. + + In any case each modulus is applied to the 'mpn_mod_34lsub1' or +'mpn_mod_1' remainder and a table lookup identifies non-squares. By +using a "modexact" style calculation, and suitably permuted tables, just +one multiply each is required, see the code for details. Moduli are +also combined to save operations, so long as the lookup tables don't +become too big. 'gen-psqr.c' does all the pre-calculations. + + A square root must still be taken for any value that passes these +tests, to verify it's really a square and not one of the small fraction +of non-squares that get through (i.e. a pseudo-square to all the tested +bases). + + Clearly more residue tests could be done, 'mpz_perfect_square_p' only +uses a compact and efficient set. Big inputs would probably benefit +from more residue testing, small inputs might be better off with less. +The assumed distribution of squares versus non-squares in the input +would affect such considerations. + + +File: gmp.info, Node: Perfect Power Algorithm, Prev: Perfect Square Algorithm, Up: Root Extraction Algorithms + +15.5.4 Perfect Power +-------------------- + +Detecting perfect powers is required by some factorization algorithms. +Currently 'mpz_perfect_power_p' is implemented using repeated Nth root +extractions, though naturally only prime roots need to be considered. +(*Note Nth Root Algorithm::.) + + If a prime divisor p with multiplicity e can be found, then only +roots which are divisors of e need to be considered, much reducing the +work necessary. To this end divisibility by a set of small primes is +checked. + + +File: gmp.info, Node: Radix Conversion Algorithms, Next: Other Algorithms, Prev: Root Extraction Algorithms, Up: Algorithms + +15.6 Radix Conversion +===================== + +Radix conversions are less important than other algorithms. A program +dominated by conversions should probably use a different data +representation. + +* Menu: + +* Binary to Radix:: +* Radix to Binary:: + + +File: gmp.info, Node: Binary to Radix, Next: Radix to Binary, Prev: Radix Conversion Algorithms, Up: Radix Conversion Algorithms + +15.6.1 Binary to Radix +---------------------- + +Conversions from binary to a power-of-2 radix use a simple and fast O(N) +bit extraction algorithm. + + Conversions from binary to other radices use one of two algorithms. +Sizes below 'GET_STR_PRECOMPUTE_THRESHOLD' use a basic O(N^2) method. +Repeated divisions by b^n are made, where b is the radix and n is the +biggest power that fits in a limb. But instead of simply using the +remainder r from such divisions, an extra divide step is done to give a +fractional limb representing r/b^n. The digits of r can then be +extracted using multiplications by b rather than divisions. Special +case code is provided for decimal, allowing multiplications by 10 to +optimize to shifts and adds. + + Above 'GET_STR_PRECOMPUTE_THRESHOLD' a sub-quadratic algorithm is +used. For an input t, powers b^(n*2^i) of the radix are calculated, +until a power between t and sqrt(t) is reached. t is then divided by +that largest power, giving a quotient which is the digits above that +power, and a remainder which is those below. These two parts are in +turn divided by the second highest power, and so on recursively. When a +piece has been divided down to less than 'GET_STR_DC_THRESHOLD' limbs, +the basecase algorithm described above is used. + + The advantage of this algorithm is that big divisions can make use of +the sub-quadratic divide and conquer division (*note Divide and Conquer +Division::), and big divisions tend to have less overheads than lots of +separate single limb divisions anyway. But in any case the cost of +calculating the powers b^(n*2^i) must first be overcome. + + 'GET_STR_PRECOMPUTE_THRESHOLD' and 'GET_STR_DC_THRESHOLD' represent +the same basic thing, the point where it becomes worth doing a big +division to cut the input in half. 'GET_STR_PRECOMPUTE_THRESHOLD' +includes the cost of calculating the radix power required, whereas +'GET_STR_DC_THRESHOLD' assumes that's already available, which is the +case when recursing. + + Since the base case produces digits from least to most significant +but they want to be stored from most to least, it's necessary to +calculate in advance how many digits there will be, or at least be sure +not to underestimate that. For GMP the number of input bits is +multiplied by 'chars_per_bit_exactly' from 'mp_bases', rounding up. The +result is either correct or one too big. + + Examining some of the high bits of the input could increase the +chance of getting the exact number of digits, but an exact result every +time would not be practical, since in general the difference between +numbers 100... and 99... is only in the last few bits and the work to +identify 99... might well be almost as much as a full conversion. + + The r/b^n scheme described above for using multiplications to bring +out digits might be useful for more than a single limb. Some brief +experiments with it on the base case when recursing didn't give a +noticeable improvement, but perhaps that was only due to the +implementation. Something similar would work for the sub-quadratic +divisions too, though there would be the cost of calculating a bigger +radix power. + + Another possible improvement for the sub-quadratic part would be to +arrange for radix powers that balanced the sizes of quotient and +remainder produced, i.e. the highest power would be an b^(n*k) +approximately equal to sqrt(t), not restricted to a 2^i factor. That +ought to smooth out a graph of times against sizes, but may or may not +be a net speedup. + + +File: gmp.info, Node: Radix to Binary, Prev: Binary to Radix, Up: Radix Conversion Algorithms + +15.6.2 Radix to Binary +---------------------- + +*This section needs to be rewritten, it currently describes the +algorithms used before GMP 4.3.* + + Conversions from a power-of-2 radix into binary use a simple and fast +O(N) bitwise concatenation algorithm. + + Conversions from other radices use one of two algorithms. Sizes +below 'SET_STR_PRECOMPUTE_THRESHOLD' use a basic O(N^2) method. Groups +of n digits are converted to limbs, where n is the biggest power of the +base b which will fit in a limb, then those groups are accumulated into +the result by multiplying by b^n and adding. This saves multi-precision +operations, as per Knuth section 4.4 part E (*note References::). Some +special case code is provided for decimal, giving the compiler a chance +to optimize multiplications by 10. + + Above 'SET_STR_PRECOMPUTE_THRESHOLD' a sub-quadratic algorithm is +used. First groups of n digits are converted into limbs. Then adjacent +limbs are combined into limb pairs with x*b^n+y, where x and y are the +limbs. Adjacent limb pairs are combined into quads similarly with +x*b^(2n)+y. This continues until a single block remains, that being the +result. + + The advantage of this method is that the multiplications for each x +are big blocks, allowing Karatsuba and higher algorithms to be used. +But the cost of calculating the powers b^(n*2^i) must be overcome. +'SET_STR_PRECOMPUTE_THRESHOLD' usually ends up quite big, around 5000 +digits, and on some processors much bigger still. + + 'SET_STR_PRECOMPUTE_THRESHOLD' is based on the input digits (and +tuned for decimal), though it might be better based on a limb count, so +as to be independent of the base. But that sort of count isn't used by +the base case and so would need some sort of initial calculation or +estimate. + + The main reason 'SET_STR_PRECOMPUTE_THRESHOLD' is so much bigger than +the corresponding 'GET_STR_PRECOMPUTE_THRESHOLD' is that 'mpn_mul_1' is +much faster than 'mpn_divrem_1' (often by a factor of 5, or more). + + +File: gmp.info, Node: Other Algorithms, Next: Assembly Coding, Prev: Radix Conversion Algorithms, Up: Algorithms + +15.7 Other Algorithms +===================== + +* Menu: + +* Prime Testing Algorithm:: +* Factorial Algorithm:: +* Binomial Coefficients Algorithm:: +* Fibonacci Numbers Algorithm:: +* Lucas Numbers Algorithm:: +* Random Number Algorithms:: + + +File: gmp.info, Node: Prime Testing Algorithm, Next: Factorial Algorithm, Prev: Other Algorithms, Up: Other Algorithms + +15.7.1 Prime Testing +-------------------- + +The primality testing in 'mpz_probab_prime_p' (*note Number Theoretic +Functions::) first does some trial division by small factors and then +uses the Miller-Rabin probabilistic primality testing algorithm, as +described in Knuth section 4.5.4 algorithm P (*note References::). + + For an odd input n, and with n = q*2^k+1 where q is odd, this +algorithm selects a random base x and tests whether x^q mod n is 1 or +-1, or an x^(q*2^j) mod n is 1, for 1<=j<=k. If so then n is probably +prime, if not then n is definitely composite. + + Any prime n will pass the test, but some composites do too. Such +composites are known as strong pseudoprimes to base x. No n is a strong +pseudoprime to more than 1/4 of all bases (see Knuth exercise 22), hence +with x chosen at random there's no more than a 1/4 chance a "probable +prime" will in fact be composite. + + In fact strong pseudoprimes are quite rare, making the test much more +powerful than this analysis would suggest, but 1/4 is all that's proven +for an arbitrary n. + + +File: gmp.info, Node: Factorial Algorithm, Next: Binomial Coefficients Algorithm, Prev: Prime Testing Algorithm, Up: Other Algorithms + +15.7.2 Factorial +---------------- + +Factorials are calculated by a combination of two algorithms. An idea +is shared among them: to compute the odd part of the factorial; a final +step takes account of the power of 2 term, by shifting. + + For small n, the odd factor of n! is computed with the simple +observation that it is equal to the product of all positive odd numbers +smaller than n times the odd factor of [n/2]!, where [x] is the integer +part of x, and so on recursively. The procedure can be best illustrated +with an example, + + 23! = (23.21.19.17.15.13.11.9.7.5.3)(11.9.7.5.3)(5.3)2^{19} + + Current code collects all the factors in a single list, with a loop +and no recursion, and computes the product, with no special care for +repeated chunks. + + When n is larger, computations pass through prime sieving. A helper +function is used, as suggested by Peter Luschny: + + n + ----- + n! | | L(p,n) + msf(n) = -------------- = | | p + [n/2]!^2.2^k p=3 + + Where p ranges on odd prime numbers. The exponent k is chosen to +obtain an odd integer number: k is the number of 1 bits in the binary +representation of [n/2]. The function L(p,n) can be defined as zero +when p is composite, and, for any prime p, it is computed with: + + --- + \ n + L(p,n) = / [---] mod 2 <= log (n) . + --- p^i p + i>0 + + With this helper function, we are able to compute the odd part of n! +using the recursion implied by n!=[n/2]!^2*msf(n)*2^k. The recursion +stops using the small-n algorithm on some [n/2^i]. + + Both the above algorithms use binary splitting to compute the product +of many small factors. At first as many products as possible are +accumulated in a single register, generating a list of factors that fit +in a machine word. This list is then split into halves, and the product +is computed recursively. + + Such splitting is more efficient than repeated Nx1 multiplies since +it forms big multiplies, allowing Karatsuba and higher algorithms to be +used. And even below the Karatsuba threshold a big block of work can be +more efficient for the basecase algorithm. + + +File: gmp.info, Node: Binomial Coefficients Algorithm, Next: Fibonacci Numbers Algorithm, Prev: Factorial Algorithm, Up: Other Algorithms + +15.7.3 Binomial Coefficients +---------------------------- + +Binomial coefficients C(n,k) are calculated by first arranging k <= n/2 +using C(n,k) = C(n,n-k) if necessary, and then evaluating the following +product simply from i=2 to i=k. + + k (n-k+i) + C(n,k) = (n-k+1) * prod ------- + i=2 i + + It's easy to show that each denominator i will divide the product so +far, so the exact division algorithm is used (*note Exact Division::). + + The numerators n-k+i and denominators i are first accumulated into as +many fit a limb, to save multi-precision operations, though for +'mpz_bin_ui' this applies only to the divisors, since n is an 'mpz_t' +and n-k+i in general won't fit in a limb at all. + + +File: gmp.info, Node: Fibonacci Numbers Algorithm, Next: Lucas Numbers Algorithm, Prev: Binomial Coefficients Algorithm, Up: Other Algorithms + +15.7.4 Fibonacci Numbers +------------------------ + +The Fibonacci functions 'mpz_fib_ui' and 'mpz_fib2_ui' are designed for +calculating isolated F[n] or F[n],F[n-1] values efficiently. + + For small n, a table of single limb values in '__gmp_fib_table' is +used. On a 32-bit limb this goes up to F[47], or on a 64-bit limb up to +F[93]. For convenience the table starts at F[-1]. + + Beyond the table, values are generated with a binary powering +algorithm, calculating a pair F[n] and F[n-1] working from high to low +across the bits of n. The formulas used are + + F[2k+1] = 4*F[k]^2 - F[k-1]^2 + 2*(-1)^k + F[2k-1] = F[k]^2 + F[k-1]^2 + + F[2k] = F[2k+1] - F[2k-1] + + At each step, k is the high b bits of n. If the next bit of n is 0 +then F[2k],F[2k-1] is used, or if it's a 1 then F[2k+1],F[2k] is used, +and the process repeated until all bits of n are incorporated. Notice +these formulas require just two squares per bit of n. + + It'd be possible to handle the first few n above the single limb +table with simple additions, using the defining Fibonacci recurrence +F[k+1]=F[k]+F[k-1], but this is not done since it usually turns out to +be faster for only about 10 or 20 values of n, and including a block of +code for just those doesn't seem worthwhile. If they really mattered +it'd be better to extend the data table. + + Using a table avoids lots of calculations on small numbers, and makes +small n go fast. A bigger table would make more small n go fast, it's +just a question of balancing size against desired speed. For GMP the +code is kept compact, with the emphasis primarily on a good powering +algorithm. + + 'mpz_fib2_ui' returns both F[n] and F[n-1], but 'mpz_fib_ui' is only +interested in F[n]. In this case the last step of the algorithm can +become one multiply instead of two squares. One of the following two +formulas is used, according as n is odd or even. + + F[2k] = F[k]*(F[k]+2F[k-1]) + + F[2k+1] = (2F[k]+F[k-1])*(2F[k]-F[k-1]) + 2*(-1)^k + + F[2k+1] here is the same as above, just rearranged to be a multiply. +For interest, the 2*(-1)^k term both here and above can be applied just +to the low limb of the calculation, without a carry or borrow into +further limbs, which saves some code size. See comments with +'mpz_fib_ui' and the internal 'mpn_fib2_ui' for how this is done. + + +File: gmp.info, Node: Lucas Numbers Algorithm, Next: Random Number Algorithms, Prev: Fibonacci Numbers Algorithm, Up: Other Algorithms + +15.7.5 Lucas Numbers +-------------------- + +'mpz_lucnum2_ui' derives a pair of Lucas numbers from a pair of +Fibonacci numbers with the following simple formulas. + + L[k] = F[k] + 2*F[k-1] + L[k-1] = 2*F[k] - F[k-1] + + 'mpz_lucnum_ui' is only interested in L[n], and some work can be +saved. Trailing zero bits on n can be handled with a single square +each. + + L[2k] = L[k]^2 - 2*(-1)^k + + And the lowest 1 bit can be handled with one multiply of a pair of +Fibonacci numbers, similar to what 'mpz_fib_ui' does. + + L[2k+1] = 5*F[k-1]*(2*F[k]+F[k-1]) - 4*(-1)^k + + +File: gmp.info, Node: Random Number Algorithms, Prev: Lucas Numbers Algorithm, Up: Other Algorithms + +15.7.6 Random Numbers +--------------------- + +For the 'urandomb' functions, random numbers are generated simply by +concatenating bits produced by the generator. As long as the generator +has good randomness properties this will produce well-distributed N bit +numbers. + + For the 'urandomm' functions, random numbers in a range 0<=R<N are +generated by taking values R of ceil(log2(N)) bits each until one +satisfies R<N. This will normally require only one or two attempts, but +the attempts are limited in case the generator is somehow degenerate and +produces only 1 bits or similar. + + The Mersenne Twister generator is by Matsumoto and Nishimura (*note +References::). It has a non-repeating period of 2^19937-1, which is a +Mersenne prime, hence the name of the generator. The state is 624 words +of 32-bits each, which is iterated with one XOR and shift for each +32-bit word generated, making the algorithm very fast. Randomness +properties are also very good and this is the default algorithm used by +GMP. + + Linear congruential generators are described in many text books, for +instance Knuth volume 2 (*note References::). With a modulus M and +parameters A and C, an integer state S is iterated by the formula S <- +A*S+C mod M. At each step the new state is a linear function of the +previous, mod M, hence the name of the generator. + + In GMP only moduli of the form 2^N are supported, and the current +implementation is not as well optimized as it could be. Overheads are +significant when N is small, and when N is large clearly the multiply at +each step will become slow. This is not a big concern, since the +Mersenne Twister generator is better in every respect and is therefore +recommended for all normal applications. + + For both generators the current state can be deduced by observing +enough output and applying some linear algebra (over GF(2) in the case +of the Mersenne Twister). This generally means raw output is unsuitable +for cryptographic applications without further hashing or the like. + + +File: gmp.info, Node: Assembly Coding, Prev: Other Algorithms, Up: Algorithms + +15.8 Assembly Coding +==================== + +The assembly subroutines in GMP are the most significant source of speed +at small to moderate sizes. At larger sizes algorithm selection becomes +more important, but of course speedups in low level routines will still +speed up everything proportionally. + + Carry handling and widening multiplies that are important for GMP +can't be easily expressed in C. GCC 'asm' blocks help a lot and are +provided in 'longlong.h', but hand coding low level routines invariably +offers a speedup over generic C by a factor of anything from 2 to 10. + +* Menu: + +* Assembly Code Organisation:: +* Assembly Basics:: +* Assembly Carry Propagation:: +* Assembly Cache Handling:: +* Assembly Functional Units:: +* Assembly Floating Point:: +* Assembly SIMD Instructions:: +* Assembly Software Pipelining:: +* Assembly Loop Unrolling:: +* Assembly Writing Guide:: + + +File: gmp.info, Node: Assembly Code Organisation, Next: Assembly Basics, Prev: Assembly Coding, Up: Assembly Coding + +15.8.1 Code Organisation +------------------------ + +The various 'mpn' subdirectories contain machine-dependent code, written +in C or assembly. The 'mpn/generic' subdirectory contains default code, +used when there's no machine-specific version of a particular file. + + Each 'mpn' subdirectory is for an ISA family. Generally 32-bit and +64-bit variants in a family cannot share code and have separate +directories. Within a family further subdirectories may exist for CPU +variants. + + In each directory a 'nails' subdirectory may exist, holding code with +nails support for that CPU variant. A 'NAILS_SUPPORT' directive in each +file indicates the nails values the code handles. Nails code only +exists where it's faster, or promises to be faster, than plain code. +There's no effort put into nails if they're not going to enhance a given +CPU. + + +File: gmp.info, Node: Assembly Basics, Next: Assembly Carry Propagation, Prev: Assembly Code Organisation, Up: Assembly Coding + +15.8.2 Assembly Basics +---------------------- + +'mpn_addmul_1' and 'mpn_submul_1' are the most important routines for +overall GMP performance. All multiplications and divisions come down to +repeated calls to these. 'mpn_add_n', 'mpn_sub_n', 'mpn_lshift' and +'mpn_rshift' are next most important. + + On some CPUs assembly versions of the internal functions +'mpn_mul_basecase' and 'mpn_sqr_basecase' give significant speedups, +mainly through avoiding function call overheads. They can also +potentially make better use of a wide superscalar processor, as can +bigger primitives like 'mpn_addmul_2' or 'mpn_addmul_4'. + + The restrictions on overlaps between sources and destinations (*note +Low-level Functions::) are designed to facilitate a variety of +implementations. For example, knowing 'mpn_add_n' won't have partly +overlapping sources and destination means reading can be done far ahead +of writing on superscalar processors, and loops can be vectorized on a +vector processor, depending on the carry handling. + + +File: gmp.info, Node: Assembly Carry Propagation, Next: Assembly Cache Handling, Prev: Assembly Basics, Up: Assembly Coding + +15.8.3 Carry Propagation +------------------------ + +The problem that presents most challenges in GMP is propagating carries +from one limb to the next. In functions like 'mpn_addmul_1' and +'mpn_add_n', carries are the only dependencies between limb operations. + + On processors with carry flags, a straightforward CISC style 'adc' is +generally best. AMD K6 'mpn_addmul_1' however is an example of an +unusual set of circumstances where a branch works out better. + + On RISC processors generally an add and compare for overflow is used. +This sort of thing can be seen in 'mpn/generic/aors_n.c'. Some carry +propagation schemes require 4 instructions, meaning at least 4 cycles +per limb, but other schemes may use just 1 or 2. On wide superscalar +processors performance may be completely determined by the number of +dependent instructions between carry-in and carry-out for each limb. + + On vector processors good use can be made of the fact that a carry +bit only very rarely propagates more than one limb. When adding a +single bit to a limb, there's only a carry out if that limb was +'0xFF...FF' which on random data will be only 1 in 2^mp_bits_per_limb. +'mpn/cray/add_n.c' is an example of this, it adds all limbs in parallel, +adds one set of carry bits in parallel and then only rarely needs to +fall through to a loop propagating further carries. + + On the x86s, GCC (as of version 2.95.2) doesn't generate particularly +good code for the RISC style idioms that are necessary to handle carry +bits in C. Often conditional jumps are generated where 'adc' or 'sbb' +forms would be better. And so unfortunately almost any loop involving +carry bits needs to be coded in assembly for best results. + + +File: gmp.info, Node: Assembly Cache Handling, Next: Assembly Functional Units, Prev: Assembly Carry Propagation, Up: Assembly Coding + +15.8.4 Cache Handling +--------------------- + +GMP aims to perform well both on operands that fit entirely in L1 cache +and those which don't. + + Basic routines like 'mpn_add_n' or 'mpn_lshift' are often used on +large operands, so L2 and main memory performance is important for them. +'mpn_mul_1' and 'mpn_addmul_1' are mostly used for multiply and square +basecases, so L1 performance matters most for them, unless assembly +versions of 'mpn_mul_basecase' and 'mpn_sqr_basecase' exist, in which +case the remaining uses are mostly for larger operands. + + For L2 or main memory operands, memory access times will almost +certainly be more than the calculation time. The aim therefore is to +maximize memory throughput, by starting a load of the next cache line +while processing the contents of the previous one. Clearly this is only +possible if the chip has a lock-up free cache or some sort of prefetch +instruction. Most current chips have both these features. + + Prefetching sources combines well with loop unrolling, since a +prefetch can be initiated once per unrolled loop (or more than once if +the loop covers more than one cache line). + + On CPUs without write-allocate caches, prefetching destinations will +ensure individual stores don't go further down the cache hierarchy, +limiting bandwidth. Of course for calculations which are slow anyway, +like 'mpn_divrem_1', write-throughs might be fine. + + The distance ahead to prefetch will be determined by memory latency +versus throughput. The aim of course is to have data arriving +continuously, at peak throughput. Some CPUs have limits on the number +of fetches or prefetches in progress. + + If a special prefetch instruction doesn't exist then a plain load can +be used, but in that case care must be taken not to attempt to read past +the end of an operand, since that might produce a segmentation +violation. + + Some CPUs or systems have hardware that detects sequential memory +accesses and initiates suitable cache movements automatically, making +life easy. + + +File: gmp.info, Node: Assembly Functional Units, Next: Assembly Floating Point, Prev: Assembly Cache Handling, Up: Assembly Coding + +15.8.5 Functional Units +----------------------- + +When choosing an approach for an assembly loop, consideration is given +to what operations can execute simultaneously and what throughput can +thereby be achieved. In some cases an algorithm can be tweaked to +accommodate available resources. + + Loop control will generally require a counter and pointer updates, +costing as much as 5 instructions, plus any delays a branch introduces. +CPU addressing modes might reduce pointer updates, perhaps by allowing +just one updating pointer and others expressed as offsets from it, or on +CISC chips with all addressing done with the loop counter as a scaled +index. + + The final loop control cost can be amortised by processing several +limbs in each iteration (*note Assembly Loop Unrolling::). This at +least ensures loop control isn't a big fraction of the work done. + + Memory throughput is always a limit. If perhaps only one load or one +store can be done per cycle then 3 cycles/limb will be the top speed for +"binary" operations like 'mpn_add_n', and any code achieving that is +optimal. + + Integer resources can be freed up by having the loop counter in a +float register, or by pressing the float units into use for some +multiplying, perhaps doing every second limb on the float side (*note +Assembly Floating Point::). + + Float resources can be freed up by doing carry propagation on the +integer side, or even by doing integer to float conversions in integers +using bit twiddling. + + +File: gmp.info, Node: Assembly Floating Point, Next: Assembly SIMD Instructions, Prev: Assembly Functional Units, Up: Assembly Coding + +15.8.6 Floating Point +--------------------- + +Floating point arithmetic is used in GMP for multiplications on CPUs +with poor integer multipliers. It's mostly useful for 'mpn_mul_1', +'mpn_addmul_1' and 'mpn_submul_1' on 64-bit machines, and +'mpn_mul_basecase' on both 32-bit and 64-bit machines. + + With IEEE 53-bit double precision floats, integer multiplications +producing up to 53 bits will give exact results. Breaking a 64x64 +multiplication into eight 16x32->48 bit pieces is convenient. With some +care though six 21x32->53 bit products can be used, if one of the lower +two 21-bit pieces also uses the sign bit. + + For the 'mpn_mul_1' family of functions on a 64-bit machine, the +invariant single limb is split at the start, into 3 or 4 pieces. Inside +the loop, the bignum operand is split into 32-bit pieces. Fast +conversion of these unsigned 32-bit pieces to floating point is highly +machine-dependent. In some cases, reading the data into the integer +unit, zero-extending to 64-bits, then transferring to the floating point +unit back via memory is the only option. + + Converting partial products back to 64-bit limbs is usually best done +as a signed conversion. Since all values are smaller than 2^53, signed +and unsigned are the same, but most processors lack unsigned +conversions. + + + + Here is a diagram showing 16x32 bit products for an 'mpn_mul_1' or +'mpn_addmul_1' with a 64-bit limb. The single limb operand V is split +into four 16-bit parts. The multi-limb operand U is split in the loop +into two 32-bit parts. + + +---+---+---+---+ + |v48|v32|v16|v00| V operand + +---+---+---+---+ + + +-------+---+---+ + x | u32 | u00 | U operand (one limb) + +---------------+ + + --------------------------------- + + +-----------+ + | u00 x v00 | p00 48-bit products + +-----------+ + +-----------+ + | u00 x v16 | p16 + +-----------+ + +-----------+ + | u00 x v32 | p32 + +-----------+ + +-----------+ + | u00 x v48 | p48 + +-----------+ + +-----------+ + | u32 x v00 | r32 + +-----------+ + +-----------+ + | u32 x v16 | r48 + +-----------+ + +-----------+ + | u32 x v32 | r64 + +-----------+ + +-----------+ + | u32 x v48 | r80 + +-----------+ + + p32 and r32 can be summed using floating-point addition, and likewise +p48 and r48. p00 and p16 can be summed with r64 and r80 from the +previous iteration. + + For each loop then, four 49-bit quantities are transferred to the +integer unit, aligned as follows, + + |-----64bits----|-----64bits----| + +------------+ + | p00 + r64' | i00 + +------------+ + +------------+ + | p16 + r80' | i16 + +------------+ + +------------+ + | p32 + r32 | i32 + +------------+ + +------------+ + | p48 + r48 | i48 + +------------+ + + The challenge then is to sum these efficiently and add in a carry +limb, generating a low 64-bit result limb and a high 33-bit carry limb +(i48 extends 33 bits into the high half). + + +File: gmp.info, Node: Assembly SIMD Instructions, Next: Assembly Software Pipelining, Prev: Assembly Floating Point, Up: Assembly Coding + +15.8.7 SIMD Instructions +------------------------ + +The single-instruction multiple-data support in current microprocessors +is aimed at signal processing algorithms where each data point can be +treated more or less independently. There's generally not much support +for propagating the sort of carries that arise in GMP. + + SIMD multiplications of say four 16x16 bit multiplies only do as much +work as one 32x32 from GMP's point of view, and need some shifts and +adds besides. But of course if say the SIMD form is fully pipelined and +uses less instruction decoding then it may still be worthwhile. + + On the x86 chips, MMX has so far found a use in 'mpn_rshift' and +'mpn_lshift', and is used in a special case for 16-bit multipliers in +the P55 'mpn_mul_1'. SSE2 is used for Pentium 4 'mpn_mul_1', +'mpn_addmul_1', and 'mpn_submul_1'. + + +File: gmp.info, Node: Assembly Software Pipelining, Next: Assembly Loop Unrolling, Prev: Assembly SIMD Instructions, Up: Assembly Coding + +15.8.8 Software Pipelining +-------------------------- + +Software pipelining consists of scheduling instructions around the +branch point in a loop. For example a loop might issue a load not for +use in the present iteration but the next, thereby allowing extra cycles +for the data to arrive from memory. + + Naturally this is wanted only when doing things like loads or +multiplies that take several cycles to complete, and only where a CPU +has multiple functional units so that other work can be done in the +meantime. + + A pipeline with several stages will have a data value in progress at +each stage and each loop iteration moves them along one stage. This is +like juggling. + + If the latency of some instruction is greater than the loop time then +it will be necessary to unroll, so one register has a result ready to +use while another (or multiple others) are still in progress (*note +Assembly Loop Unrolling::). + + +File: gmp.info, Node: Assembly Loop Unrolling, Next: Assembly Writing Guide, Prev: Assembly Software Pipelining, Up: Assembly Coding + +15.8.9 Loop Unrolling +--------------------- + +Loop unrolling consists of replicating code so that several limbs are +processed in each loop. At a minimum this reduces loop overheads by a +corresponding factor, but it can also allow better register usage, for +example alternately using one register combination and then another. +Judicious use of 'm4' macros can help avoid lots of duplication in the +source code. + + Any amount of unrolling can be handled with a loop counter that's +decremented by N each time, stopping when the remaining count is less +than the further N the loop will process. Or by subtracting N at the +start, the termination condition becomes when the counter C is less than +0 (and the count of remaining limbs is C+N). + + Alternately for a power of 2 unroll the loop count and remainder can +be established with a shift and mask. This is convenient if also making +a computed jump into the middle of a large loop. + + The limbs not a multiple of the unrolling can be handled in various +ways, for example + + * A simple loop at the end (or the start) to process the excess. + Care will be wanted that it isn't too much slower than the unrolled + part. + + * A set of binary tests, for example after an 8-limb unrolling, test + for 4 more limbs to process, then a further 2 more or not, and + finally 1 more or not. This will probably take more code space + than a simple loop. + + * A 'switch' statement, providing separate code for each possible + excess, for example an 8-limb unrolling would have separate code + for 0 remaining, 1 remaining, etc, up to 7 remaining. This might + take a lot of code, but may be the best way to optimize all cases + in combination with a deep pipelined loop. + + * A computed jump into the middle of the loop, thus making the first + iteration handle the excess. This should make times smoothly + increase with size, which is attractive, but setups for the jump + and adjustments for pointers can be tricky and could become quite + difficult in combination with deep pipelining. + + +File: gmp.info, Node: Assembly Writing Guide, Prev: Assembly Loop Unrolling, Up: Assembly Coding + +15.8.10 Writing Guide +--------------------- + +This is a guide to writing software pipelined loops for processing limb +vectors in assembly. + + First determine the algorithm and which instructions are needed. +Code it without unrolling or scheduling, to make sure it works. On a +3-operand CPU try to write each new value to a new register, this will +greatly simplify later steps. + + Then note for each instruction the functional unit and/or issue port +requirements. If an instruction can use either of two units, like U0 or +U1 then make a category "U0/U1". Count the total using each unit (or +combined unit), and count all instructions. + + Figure out from those counts the best possible loop time. The goal +will be to find a perfect schedule where instruction latencies are +completely hidden. The total instruction count might be the limiting +factor, or perhaps a particular functional unit. It might be possible +to tweak the instructions to help the limiting factor. + + Suppose the loop time is N, then make N issue buckets, with the final +loop branch at the end of the last. Now fill the buckets with dummy +instructions using the functional units desired. Run this to make sure +the intended speed is reached. + + Now replace the dummy instructions with the real instructions from +the slow but correct loop you started with. The first will typically be +a load instruction. Then the instruction using that value is placed in +a bucket an appropriate distance down. Run the loop again, to check it +still runs at target speed. + + Keep placing instructions, frequently measuring the loop. After a +few you will need to wrap around from the last bucket back to the top of +the loop. If you used the new-register for new-value strategy above +then there will be no register conflicts. If not then take care not to +clobber something already in use. Changing registers at this time is +very error prone. + + The loop will overlap two or more of the original loop iterations, +and the computation of one vector element result will be started in one +iteration of the new loop, and completed one or several iterations +later. + + The final step is to create feed-in and wind-down code for the loop. +A good way to do this is to make a copy (or copies) of the loop at the +start and delete those instructions which don't have valid antecedents, +and at the end replicate and delete those whose results are unwanted +(including any further loads). + + The loop will have a minimum number of limbs loaded and processed, so +the feed-in code must test if the request size is smaller and skip +either to a suitable part of the wind-down or to special code for small +sizes. + + +File: gmp.info, Node: Internals, Next: Contributors, Prev: Algorithms, Up: Top + +16 Internals +************ + +*This chapter is provided only for informational purposes and the +various internals described here may change in future GMP releases. +Applications expecting to be compatible with future releases should use +only the documented interfaces described in previous chapters.* + +* Menu: + +* Integer Internals:: +* Rational Internals:: +* Float Internals:: +* Raw Output Internals:: +* C++ Interface Internals:: + + +File: gmp.info, Node: Integer Internals, Next: Rational Internals, Prev: Internals, Up: Internals + +16.1 Integer Internals +====================== + +'mpz_t' variables represent integers using sign and magnitude, in space +dynamically allocated and reallocated. The fields are as follows. + +'_mp_size' + The number of limbs, or the negative of that when representing a + negative integer. Zero is represented by '_mp_size' set to zero, + in which case the '_mp_d' data is undefined. + +'_mp_d' + A pointer to an array of limbs which is the magnitude. These are + stored "little endian" as per the 'mpn' functions, so '_mp_d[0]' is + the least significant limb and '_mp_d[ABS(_mp_size)-1]' is the most + significant. Whenever '_mp_size' is non-zero, the most significant + limb is non-zero. + + Currently there's always at least one readable limb, so for + instance 'mpz_get_ui' can fetch '_mp_d[0]' unconditionally (though + its value is undefined if '_mp_size' is zero). + +'_mp_alloc' + '_mp_alloc' is the number of limbs currently allocated at '_mp_d', + and normally '_mp_alloc >= ABS(_mp_size)'. When an 'mpz' routine + is about to (or might be about to) increase '_mp_size', it checks + '_mp_alloc' to see whether there's enough space, and reallocates if + not. 'MPZ_REALLOC' is generally used for this. + + 'mpz_t' variables initialised with the 'mpz_roinit_n' function or + the 'MPZ_ROINIT_N' macro have '_mp_alloc = 0' but can have a + non-zero '_mp_size'. They can only be used as read-only constants. + See *note Integer Special Functions:: for details. + + The various bitwise logical functions like 'mpz_and' behave as if +negative values were two's complement. But sign and magnitude is always +used internally, and necessary adjustments are made during the +calculations. Sometimes this isn't pretty, but sign and magnitude are +best for other routines. + + Some internal temporary variables are set up with 'MPZ_TMP_INIT' and +these have '_mp_d' space obtained from 'TMP_ALLOC' rather than the +memory allocation functions. Care is taken to ensure that these are big +enough that no reallocation is necessary (since it would have +unpredictable consequences). + + '_mp_size' and '_mp_alloc' are 'int', although 'mp_size_t' is usually +a 'long'. This is done to make the fields just 32 bits on some 64 bits +systems, thereby saving a few bytes of data space but still providing +plenty of range. + + +File: gmp.info, Node: Rational Internals, Next: Float Internals, Prev: Integer Internals, Up: Internals + +16.2 Rational Internals +======================= + +'mpq_t' variables represent rationals using an 'mpz_t' numerator and +denominator (*note Integer Internals::). + + The canonical form adopted is denominator positive (and non-zero), no +common factors between numerator and denominator, and zero uniquely +represented as 0/1. + + It's believed that casting out common factors at each stage of a +calculation is best in general. A GCD is an O(N^2) operation so it's +better to do a few small ones immediately than to delay and have to do a +big one later. Knowing the numerator and denominator have no common +factors can be used for example in 'mpq_mul' to make only two cross GCDs +necessary, not four. + + This general approach to common factors is badly sub-optimal in the +presence of simple factorizations or little prospect for cancellation, +but GMP has no way to know when this will occur. As per *note +Efficiency::, that's left to applications. The 'mpq_t' framework might +still suit, with 'mpq_numref' and 'mpq_denref' for direct access to the +numerator and denominator, or of course 'mpz_t' variables can be used +directly. + + +File: gmp.info, Node: Float Internals, Next: Raw Output Internals, Prev: Rational Internals, Up: Internals + +16.3 Float Internals +==================== + +Efficient calculation is the primary aim of GMP floats and the use of +whole limbs and simple rounding facilitates this. + + 'mpf_t' floats have a variable precision mantissa and a single +machine word signed exponent. The mantissa is represented using sign +and magnitude. + + most least + significant significant + limb limb + + _mp_d + |---- _mp_exp ---> | + _____ _____ _____ _____ _____ + |_____|_____|_____|_____|_____| + . <------------ radix point + + <-------- _mp_size ---------> + + +The fields are as follows. + +'_mp_size' + The number of limbs currently in use, or the negative of that when + representing a negative value. Zero is represented by '_mp_size' + and '_mp_exp' both set to zero, and in that case the '_mp_d' data + is unused. (In the future '_mp_exp' might be undefined when + representing zero.) + +'_mp_prec' + The precision of the mantissa, in limbs. In any calculation the + aim is to produce '_mp_prec' limbs of result (the most significant + being non-zero). + +'_mp_d' + A pointer to the array of limbs which is the absolute value of the + mantissa. These are stored "little endian" as per the 'mpn' + functions, so '_mp_d[0]' is the least significant limb and + '_mp_d[ABS(_mp_size)-1]' the most significant. + + The most significant limb is always non-zero, but there are no + other restrictions on its value, in particular the highest 1 bit + can be anywhere within the limb. + + '_mp_prec+1' limbs are allocated to '_mp_d', the extra limb being + for convenience (see below). There are no reallocations during a + calculation, only in a change of precision with 'mpf_set_prec'. + +'_mp_exp' + The exponent, in limbs, determining the location of the implied + radix point. Zero means the radix point is just above the most + significant limb. Positive values mean a radix point offset + towards the lower limbs and hence a value >= 1, as for example in + the diagram above. Negative exponents mean a radix point further + above the highest limb. + + Naturally the exponent can be any value, it doesn't have to fall + within the limbs as the diagram shows, it can be a long way above + or a long way below. Limbs other than those included in the + '{_mp_d,_mp_size}' data are treated as zero. + + The '_mp_size' and '_mp_prec' fields are 'int', although the +'mp_size_t' type is usually a 'long'. The '_mp_exp' field is usually +'long'. This is done to make some fields just 32 bits on some 64 bits +systems, thereby saving a few bytes of data space but still providing +plenty of precision and a very large range. + + +The following various points should be noted. + +Low Zeros + The least significant limbs '_mp_d[0]' etc can be zero, though such + low zeros can always be ignored. Routines likely to produce low + zeros check and avoid them to save time in subsequent calculations, + but for most routines they're quite unlikely and aren't checked. + +Mantissa Size Range + The '_mp_size' count of limbs in use can be less than '_mp_prec' if + the value can be represented in less. This means low precision + values or small integers stored in a high precision 'mpf_t' can + still be operated on efficiently. + + '_mp_size' can also be greater than '_mp_prec'. Firstly a value is + allowed to use all of the '_mp_prec+1' limbs available at '_mp_d', + and secondly when 'mpf_set_prec_raw' lowers '_mp_prec' it leaves + '_mp_size' unchanged and so the size can be arbitrarily bigger than + '_mp_prec'. + +Rounding + All rounding is done on limb boundaries. Calculating '_mp_prec' + limbs with the high non-zero will ensure the application requested + minimum precision is obtained. + + The use of simple "trunc" rounding towards zero is efficient, since + there's no need to examine extra limbs and increment or decrement. + +Bit Shifts + Since the exponent is in limbs, there are no bit shifts in basic + operations like 'mpf_add' and 'mpf_mul'. When differing exponents + are encountered all that's needed is to adjust pointers to line up + the relevant limbs. + + Of course 'mpf_mul_2exp' and 'mpf_div_2exp' will require bit + shifts, but the choice is between an exponent in limbs which + requires shifts there, or one in bits which requires them almost + everywhere else. + +Use of '_mp_prec+1' Limbs + The extra limb on '_mp_d' ('_mp_prec+1' rather than just + '_mp_prec') helps when an 'mpf' routine might get a carry from its + operation. 'mpf_add' for instance will do an 'mpn_add' of + '_mp_prec' limbs. If there's no carry then that's the result, but + if there is a carry then it's stored in the extra limb of space and + '_mp_size' becomes '_mp_prec+1'. + + Whenever '_mp_prec+1' limbs are held in a variable, the low limb is + not needed for the intended precision, only the '_mp_prec' high + limbs. But zeroing it out or moving the rest down is unnecessary. + Subsequent routines reading the value will simply take the high + limbs they need, and this will be '_mp_prec' if their target has + that same precision. This is no more than a pointer adjustment, + and must be checked anyway since the destination precision can be + different from the sources. + + Copy functions like 'mpf_set' will retain a full '_mp_prec+1' limbs + if available. This ensures that a variable which has '_mp_size' + equal to '_mp_prec+1' will get its full exact value copied. + Strictly speaking this is unnecessary since only '_mp_prec' limbs + are needed for the application's requested precision, but it's + considered that an 'mpf_set' from one variable into another of the + same precision ought to produce an exact copy. + +Application Precisions + '__GMPF_BITS_TO_PREC' converts an application requested precision + to an '_mp_prec'. The value in bits is rounded up to a whole limb + then an extra limb is added since the most significant limb of + '_mp_d' is only non-zero and therefore might contain only one bit. + + '__GMPF_PREC_TO_BITS' does the reverse conversion, and removes the + extra limb from '_mp_prec' before converting to bits. The net + effect of reading back with 'mpf_get_prec' is simply the precision + rounded up to a multiple of 'mp_bits_per_limb'. + + Note that the extra limb added here for the high only being + non-zero is in addition to the extra limb allocated to '_mp_d'. + For example with a 32-bit limb, an application request for 250 bits + will be rounded up to 8 limbs, then an extra added for the high + being only non-zero, giving an '_mp_prec' of 9. '_mp_d' then gets + 10 limbs allocated. Reading back with 'mpf_get_prec' will take + '_mp_prec' subtract 1 limb and multiply by 32, giving 256 bits. + + Strictly speaking, the fact that the high limb has at least one bit + means that a float with, say, 3 limbs of 32-bits each will be + holding at least 65 bits, but for the purposes of 'mpf_t' it's + considered simply to be 64 bits, a nice multiple of the limb size. + + +File: gmp.info, Node: Raw Output Internals, Next: C++ Interface Internals, Prev: Float Internals, Up: Internals + +16.4 Raw Output Internals +========================= + +'mpz_out_raw' uses the following format. + + +------+------------------------+ + | size | data bytes | + +------+------------------------+ + + The size is 4 bytes written most significant byte first, being the +number of subsequent data bytes, or the two's complement negative of +that when a negative integer is represented. The data bytes are the +absolute value of the integer, written most significant byte first. + + The most significant data byte is always non-zero, so the output is +the same on all systems, irrespective of limb size. + + In GMP 1, leading zero bytes were written to pad the data bytes to a +multiple of the limb size. 'mpz_inp_raw' will still accept this, for +compatibility. + + The use of "big endian" for both the size and data fields is +deliberate, it makes the data easy to read in a hex dump of a file. +Unfortunately it also means that the limb data must be reversed when +reading or writing, so neither a big endian nor little endian system can +just read and write '_mp_d'. + + +File: gmp.info, Node: C++ Interface Internals, Prev: Raw Output Internals, Up: Internals + +16.5 C++ Interface Internals +============================ + +A system of expression templates is used to ensure something like +'a=b+c' turns into a simple call to 'mpz_add' etc. For 'mpf_class' the +scheme also ensures the precision of the final destination is used for +any temporaries within a statement like 'f=w*x+y*z'. These are +important features which a naive implementation cannot provide. + + A simplified description of the scheme follows. The true scheme is +complicated by the fact that expressions have different return types. +For detailed information, refer to the source code. + + To perform an operation, say, addition, we first define a "function +object" evaluating it, + + struct __gmp_binary_plus + { + static void eval(mpf_t f, const mpf_t g, const mpf_t h) + { + mpf_add(f, g, h); + } + }; + +And an "additive expression" object, + + __gmp_expr<__gmp_binary_expr<mpf_class, mpf_class, __gmp_binary_plus> > + operator+(const mpf_class &f, const mpf_class &g) + { + return __gmp_expr + <__gmp_binary_expr<mpf_class, mpf_class, __gmp_binary_plus> >(f, g); + } + + The seemingly redundant '__gmp_expr<__gmp_binary_expr<...>>' is used +to encapsulate any possible kind of expression into a single template +type. In fact even 'mpf_class' etc are 'typedef' specializations of +'__gmp_expr'. + + Next we define assignment of '__gmp_expr' to 'mpf_class'. + + template <class T> + mpf_class & mpf_class::operator=(const __gmp_expr<T> &expr) + { + expr.eval(this->get_mpf_t(), this->precision()); + return *this; + } + + template <class Op> + void __gmp_expr<__gmp_binary_expr<mpf_class, mpf_class, Op> >::eval + (mpf_t f, mp_bitcnt_t precision) + { + Op::eval(f, expr.val1.get_mpf_t(), expr.val2.get_mpf_t()); + } + + where 'expr.val1' and 'expr.val2' are references to the expression's +operands (here 'expr' is the '__gmp_binary_expr' stored within the +'__gmp_expr'). + + This way, the expression is actually evaluated only at the time of +assignment, when the required precision (that of 'f') is known. +Furthermore the target 'mpf_t' is now available, thus we can call +'mpf_add' directly with 'f' as the output argument. + + Compound expressions are handled by defining operators taking +subexpressions as their arguments, like this: + + template <class T, class U> + __gmp_expr + <__gmp_binary_expr<__gmp_expr<T>, __gmp_expr<U>, __gmp_binary_plus> > + operator+(const __gmp_expr<T> &expr1, const __gmp_expr<U> &expr2) + { + return __gmp_expr + <__gmp_binary_expr<__gmp_expr<T>, __gmp_expr<U>, __gmp_binary_plus> > + (expr1, expr2); + } + + And the corresponding specializations of '__gmp_expr::eval': + + template <class T, class U, class Op> + void __gmp_expr + <__gmp_binary_expr<__gmp_expr<T>, __gmp_expr<U>, Op> >::eval + (mpf_t f, mp_bitcnt_t precision) + { + // declare two temporaries + mpf_class temp1(expr.val1, precision), temp2(expr.val2, precision); + Op::eval(f, temp1.get_mpf_t(), temp2.get_mpf_t()); + } + + The expression is thus recursively evaluated to any level of +complexity and all subexpressions are evaluated to the precision of 'f'. + + +File: gmp.info, Node: Contributors, Next: References, Prev: Internals, Up: Top + +Appendix A Contributors +*********************** + +Torbjörn Granlund wrote the original GMP library and is still the main +developer. Code not explicitly attributed to others was contributed by +Torbjörn. Several other individuals and organizations have contributed +GMP. Here is a list in chronological order on first contribution: + + Gunnar Sjödin and Hans Riesel helped with mathematical problems in +early versions of the library. + + Richard Stallman helped with the interface design and revised the +first version of this manual. + + Brian Beuning and Doug Lea helped with testing of early versions of +the library and made creative suggestions. + + John Amanatides of York University in Canada contributed the function +'mpz_probab_prime_p'. + + Paul Zimmermann wrote the REDC-based mpz_powm code, the +Schönhage-Strassen FFT multiply code, and the Karatsuba square root +code. He also improved the Toom3 code for GMP 4.2. Paul sparked the +development of GMP 2, with his comparisons between bignum packages. The +ECMNET project Paul is organizing was a driving force behind many of the +optimizations in GMP 3. Paul also wrote the new GMP 4.3 nth root code +(with Torbjörn). + + Ken Weber (Kent State University, Universidade Federal do Rio Grande +do Sul) contributed now defunct versions of 'mpz_gcd', 'mpz_divexact', +'mpn_gcd', and 'mpn_bdivmod', partially supported by CNPq (Brazil) grant +301314194-2. + + Per Bothner of Cygnus Support helped to set up GMP to use Cygnus' +configure. He has also made valuable suggestions and tested numerous +intermediary releases. + + Joachim Hollman was involved in the design of the 'mpf' interface, +and in the 'mpz' design revisions for version 2. + + Bennet Yee contributed the initial versions of 'mpz_jacobi' and +'mpz_legendre'. + + Andreas Schwab contributed the files 'mpn/m68k/lshift.S' and +'mpn/m68k/rshift.S' (now in '.asm' form). + + Robert Harley of Inria, France and David Seal of ARM, England, +suggested clever improvements for population count. Robert also wrote +highly optimized Karatsuba and 3-way Toom multiplication functions for +GMP 3, and contributed the ARM assembly code. + + Torsten Ekedahl of the Mathematical Department of Stockholm +University provided significant inspiration during several phases of the +GMP development. His mathematical expertise helped improve several +algorithms. + + Linus Nordberg wrote the new configure system based on autoconf and +implemented the new random functions. + + Kevin Ryde worked on a large number of things: optimized x86 code, m4 +asm macros, parameter tuning, speed measuring, the configure system, +function inlining, divisibility tests, bit scanning, Jacobi symbols, +Fibonacci and Lucas number functions, printf and scanf functions, perl +interface, demo expression parser, the algorithms chapter in the manual, +'gmpasm-mode.el', and various miscellaneous improvements elsewhere. + + Kent Boortz made the Mac OS 9 port. + + Steve Root helped write the optimized alpha 21264 assembly code. + + Gerardo Ballabio wrote the 'gmpxx.h' C++ class interface and the C++ +'istream' input routines. + + Jason Moxham rewrote 'mpz_fac_ui'. + + Pedro Gimeno implemented the Mersenne Twister and made other random +number improvements. + + Niels Möller wrote the sub-quadratic GCD, extended GCD and Jacobi +code, the quadratic Hensel division code, and (with Torbjörn) the new +divide and conquer division code for GMP 4.3. Niels also helped +implement the new Toom multiply code for GMP 4.3 and implemented helper +functions to simplify Toom evaluations for GMP 5.0. He wrote the +original version of mpn_mulmod_bnm1, and he is the main author of the +mini-gmp package used for gmp bootstrapping. + + Alberto Zanoni and Marco Bodrato suggested the unbalanced multiply +strategy, and found the optimal strategies for evaluation and +interpolation in Toom multiplication. + + Marco Bodrato helped implement the new Toom multiply code for GMP 4.3 +and implemented most of the new Toom multiply and squaring code for 5.0. +He is the main author of the current mpn_mulmod_bnm1, mpn_mullo_n, and +mpn_sqrlo. Marco also wrote the functions mpn_invert and +mpn_invertappr, and improved the speed of integer root extraction. He +is the author of mini-mpq, an additional layer to mini-gmp; of most of +the combinatorial functions and the BPSW primality testing +implementation, for both the main library and the mini-gmp package. + + David Harvey suggested the internal function 'mpn_bdiv_dbm1', +implementing division relevant to Toom multiplication. He also worked +on fast assembly sequences, in particular on a fast AMD64 +'mpn_mul_basecase'. He wrote the internal middle product functions +'mpn_mulmid_basecase', 'mpn_toom42_mulmid', 'mpn_mulmid_n' and related +helper routines. + + Martin Boij wrote 'mpn_perfect_power_p'. + + Marc Glisse improved 'gmpxx.h': use fewer temporaries (faster), +specializations of 'numeric_limits' and 'common_type', C++11 features +(move constructors, explicit bool conversion, UDL), make the conversion +from 'mpq_class' to 'mpz_class' explicit, optimize operations where one +argument is a small compile-time constant, replace some heap allocations +by stack allocations. He also fixed the eofbit handling of C++ streams, +and removed one division from 'mpq/aors.c'. + + David S Miller wrote assembly code for SPARC T3 and T4. + + Mark Sofroniou cleaned up the types of mul_fft.c, letting it work for +huge operands. + + Ulrich Weigand ported GMP to the powerpc64le ABI. + + (This list is chronological, not ordered after significance. If you +have contributed to GMP but are not listed above, please tell +<gmp-devel@gmplib.org> about the omission!) + + The development of floating point functions of GNU MP 2 was supported +in part by the ESPRIT-BRA (Basic Research Activities) 6846 project POSSO +(POlynomial System SOlving). + + The development of GMP 2, 3, and 4.0 was supported in part by the IDA +Center for Computing Sciences. + + The development of GMP 4.3, 5.0, and 5.1 was supported in part by the +Swedish Foundation for Strategic Research. + + Thanks go to Hans Thorsen for donating an SGI system for the GMP test +system environment. + + +File: gmp.info, Node: References, Next: GNU Free Documentation License, Prev: Contributors, Up: Top + +Appendix B References +********************* + +B.1 Books +========= + + * Jonathan M. Borwein and Peter B. Borwein, "Pi and the AGM: A Study + in Analytic Number Theory and Computational Complexity", Wiley, + 1998. + + * Richard Crandall and Carl Pomerance, "Prime Numbers: A + Computational Perspective", 2nd edition, Springer-Verlag, 2005. + <https://www.math.dartmouth.edu/~carlp/> + + * Henri Cohen, "A Course in Computational Algebraic Number Theory", + Graduate Texts in Mathematics number 138, Springer-Verlag, 1993. + <https://www.math.u-bordeaux.fr/~cohen/> + + * Donald E. Knuth, "The Art of Computer Programming", volume 2, + "Seminumerical Algorithms", 3rd edition, Addison-Wesley, 1998. + <https://www-cs-faculty.stanford.edu/~knuth/taocp.html> + + * John D. Lipson, "Elements of Algebra and Algebraic Computing", The + Benjamin Cummings Publishing Company Inc, 1981. + + * Alfred J. Menezes, Paul C. van Oorschot and Scott A. Vanstone, + "Handbook of Applied Cryptography", + <http://www.cacr.math.uwaterloo.ca/hac/> + + * Richard M. Stallman and the GCC Developer Community, "Using the GNU + Compiler Collection", Free Software Foundation, 2008, available + online <https://gcc.gnu.org/onlinedocs/>, and in the GCC package + <https://ftp.gnu.org/gnu/gcc/> + +B.2 Papers +========== + + * Yves Bertot, Nicolas Magaud and Paul Zimmermann, "A Proof of GMP + Square Root", Journal of Automated Reasoning, volume 29, 2002, pp. + 225-252. Also available online as INRIA Research Report 4475, June + 2002, <https://hal.inria.fr/docs/00/07/21/13/PDF/RR-4475.pdf> + + * Christoph Burnikel and Joachim Ziegler, "Fast Recursive Division", + Max-Planck-Institut fuer Informatik Research Report MPI-I-98-1-022, + <https://www.mpi-inf.mpg.de/~ziegler/TechRep.ps.gz> + + * Torbjörn Granlund and Peter L. Montgomery, "Division by Invariant + Integers using Multiplication", in Proceedings of the SIGPLAN + PLDI'94 Conference, June 1994. Also available + <https://gmplib.org/~tege/divcnst-pldi94.pdf>. + + * Niels Möller and Torbjörn Granlund, "Improved division by invariant + integers", IEEE Transactions on Computers, 11 June 2010. + <https://gmplib.org/~tege/division-paper.pdf> + + * Torbjörn Granlund and Niels Möller, "Division of integers large and + small", to appear. + + * Tudor Jebelean, "An algorithm for exact division", Journal of + Symbolic Computation, volume 15, 1993, pp. 169-180. Research + report version available + <ftp://ftp.risc.uni-linz.ac.at/pub/techreports/1992/92-35.ps.gz> + + * Tudor Jebelean, "Exact Division with Karatsuba Complexity - + Extended Abstract", RISC-Linz technical report 96-31, + <ftp://ftp.risc.uni-linz.ac.at/pub/techreports/1996/96-31.ps.gz> + + * Tudor Jebelean, "Practical Integer Division with Karatsuba + Complexity", ISSAC 97, pp. 339-341. Technical report available + <ftp://ftp.risc.uni-linz.ac.at/pub/techreports/1996/96-29.ps.gz> + + * Tudor Jebelean, "A Generalization of the Binary GCD Algorithm", + ISSAC 93, pp. 111-116. Technical report version available + <ftp://ftp.risc.uni-linz.ac.at/pub/techreports/1993/93-01.ps.gz> + + * Tudor Jebelean, "A Double-Digit Lehmer-Euclid Algorithm for Finding + the GCD of Long Integers", Journal of Symbolic Computation, volume + 19, 1995, pp. 145-157. Technical report version also available + <ftp://ftp.risc.uni-linz.ac.at/pub/techreports/1992/92-69.ps.gz> + + * Werner Krandick and Tudor Jebelean, "Bidirectional Exact Integer + Division", Journal of Symbolic Computation, volume 21, 1996, pp. + 441-455. Early technical report version also available + <ftp://ftp.risc.uni-linz.ac.at/pub/techreports/1994/94-50.ps.gz> + + * Makoto Matsumoto and Takuji Nishimura, "Mersenne Twister: A + 623-dimensionally equidistributed uniform pseudorandom number + generator", ACM Transactions on Modelling and Computer Simulation, + volume 8, January 1998, pp. 3-30. Available online + <http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/ARTICLES/mt.pdf> + + * R. Moenck and A. Borodin, "Fast Modular Transforms via Division", + Proceedings of the 13th Annual IEEE Symposium on Switching and + Automata Theory, October 1972, pp. 90-96. Reprinted as "Fast + Modular Transforms", Journal of Computer and System Sciences, + volume 8, number 3, June 1974, pp. 366-386. + + * Niels Möller, "On Schönhage's algorithm and subquadratic integer + GCD computation", in Mathematics of Computation, volume 77, January + 2008, pp. 589-607, + <https://www.ams.org/journals/mcom/2008-77-261/S0025-5718-07-02017-0/home.html> + + * Peter L. Montgomery, "Modular Multiplication Without Trial + Division", in Mathematics of Computation, volume 44, number 170, + April 1985. + + * Arnold Schönhage and Volker Strassen, "Schnelle Multiplikation + grosser Zahlen", Computing 7, 1971, pp. 281-292. + + * Kenneth Weber, "The accelerated integer GCD algorithm", ACM + Transactions on Mathematical Software, volume 21, number 1, March + 1995, pp. 111-122. + + * Paul Zimmermann, "Karatsuba Square Root", INRIA Research Report + 3805, November 1999, + <https://hal.inria.fr/inria-00072854/PDF/RR-3805.pdf> + + * Paul Zimmermann, "A Proof of GMP Fast Division and Square Root + Implementations", + <https://homepages.loria.fr/PZimmermann/papers/proof-div-sqrt.ps.gz> + + * Dan Zuras, "On Squaring and Multiplying Large Integers", ARITH-11: + IEEE Symposium on Computer Arithmetic, 1993, pp. 260 to 271. + Reprinted as "More on Multiplying and Squaring Large Integers", + IEEE Transactions on Computers, volume 43, number 8, August 1994, + pp. 899-908. + + * Niels Möller, "Efficient computation of the Jacobi symbol", + <https://arxiv.org/abs/1907.07795> + + +File: gmp.info, Node: GNU Free Documentation License, Next: Concept Index, Prev: References, Up: Top + +Appendix C GNU Free Documentation License +***************************************** + + Version 1.3, 3 November 2008 + + Copyright © 2000-2002, 2007, 2008 Free Software Foundation, Inc. + <http://fsf.org/> + + Everyone is permitted to copy and distribute verbatim copies + of this license document, but changing it is not allowed. + + 0. PREAMBLE + + The purpose of this License is to make a manual, textbook, or other + functional and useful document "free" in the sense of freedom: to + assure everyone the effective freedom to copy and redistribute it, + with or without modifying it, either commercially or + noncommercially. Secondarily, this License preserves for the + author and publisher a way to get credit for their work, while not + being considered responsible for modifications made by others. + + This License is a kind of "copyleft", which means that derivative + works of the document must themselves be free in the same sense. + It complements the GNU General Public License, which is a copyleft + license designed for free software. + + We have designed this License in order to use it for manuals for + free software, because free software needs free documentation: a + free program should come with manuals providing the same freedoms + that the software does. But this License is not limited to + software manuals; it can be used for any textual work, regardless + of subject matter or whether it is published as a printed book. We + recommend this License principally for works whose purpose is + instruction or reference. + + 1. APPLICABILITY AND DEFINITIONS + + This License applies to any manual or other work, in any medium, + that contains a notice placed by the copyright holder saying it can + be distributed under the terms of this License. Such a notice + grants a world-wide, royalty-free license, unlimited in duration, + to use that work under the conditions stated herein. The + "Document", below, refers to any such manual or work. Any member + of the public is a licensee, and is addressed as "you". You accept + the license if you copy, modify or distribute the work in a way + requiring permission under copyright law. + + A "Modified Version" of the Document means any work containing the + Document or a portion of it, either copied verbatim, or with + modifications and/or translated into another language. + + A "Secondary Section" is a named appendix or a front-matter section + of the Document that deals exclusively with the relationship of the + publishers or authors of the Document to the Document's overall + subject (or to related matters) and contains nothing that could + fall directly within that overall subject. (Thus, if the Document + is in part a textbook of mathematics, a Secondary Section may not + explain any mathematics.) The relationship could be a matter of + historical connection with the subject or with related matters, or + of legal, commercial, philosophical, ethical or political position + regarding them. + + The "Invariant Sections" are certain Secondary Sections whose + titles are designated, as being those of Invariant Sections, in the + notice that says that the Document is released under this License. + If a section does not fit the above definition of Secondary then it + is not allowed to be designated as Invariant. The Document may + contain zero Invariant Sections. If the Document does not identify + any Invariant Sections then there are none. + + The "Cover Texts" are certain short passages of text that are + listed, as Front-Cover Texts or Back-Cover Texts, in the notice + that says that the Document is released under this License. A + Front-Cover Text may be at most 5 words, and a Back-Cover Text may + be at most 25 words. + + A "Transparent" copy of the Document means a machine-readable copy, + represented in a format whose specification is available to the + general public, that is suitable for revising the document + straightforwardly with generic text editors or (for images composed + of pixels) generic paint programs or (for drawings) some widely + available drawing editor, and that is suitable for input to text + formatters or for automatic translation to a variety of formats + suitable for input to text formatters. A copy made in an otherwise + Transparent file format whose markup, or absence of markup, has + been arranged to thwart or discourage subsequent modification by + readers is not Transparent. An image format is not Transparent if + used for any substantial amount of text. A copy that is not + "Transparent" is called "Opaque". + + Examples of suitable formats for Transparent copies include plain + ASCII without markup, Texinfo input format, LaTeX input format, + SGML or XML using a publicly available DTD, and standard-conforming + simple HTML, PostScript or PDF designed for human modification. + Examples of transparent image formats include PNG, XCF and JPG. + Opaque formats include proprietary formats that can be read and + edited only by proprietary word processors, SGML or XML for which + the DTD and/or processing tools are not generally available, and + the machine-generated HTML, PostScript or PDF produced by some word + processors for output purposes only. + + The "Title Page" means, for a printed book, the title page itself, + plus such following pages as are needed to hold, legibly, the + material this License requires to appear in the title page. For + works in formats which do not have any title page as such, "Title + Page" means the text near the most prominent appearance of the + work's title, preceding the beginning of the body of the text. + + The "publisher" means any person or entity that distributes copies + of the Document to the public. + + A section "Entitled XYZ" means a named subunit of the Document + whose title either is precisely XYZ or contains XYZ in parentheses + following text that translates XYZ in another language. (Here XYZ + stands for a specific section name mentioned below, such as + "Acknowledgements", "Dedications", "Endorsements", or "History".) + To "Preserve the Title" of such a section when you modify the + Document means that it remains a section "Entitled XYZ" according + to this definition. + + The Document may include Warranty Disclaimers next to the notice + which states that this License applies to the Document. These + Warranty Disclaimers are considered to be included by reference in + this License, but only as regards disclaiming warranties: any other + implication that these Warranty Disclaimers may have is void and + has no effect on the meaning of this License. + + 2. VERBATIM COPYING + + You may copy and distribute the Document in any medium, either + commercially or noncommercially, provided that this License, the + copyright notices, and the license notice saying this License + applies to the Document are reproduced in all copies, and that you + add no other conditions whatsoever to those of this License. You + may not use technical measures to obstruct or control the reading + or further copying of the copies you make or distribute. However, + you may accept compensation in exchange for copies. If you + distribute a large enough number of copies you must also follow the + conditions in section 3. + + You may also lend copies, under the same conditions stated above, + and you may publicly display copies. + + 3. COPYING IN QUANTITY + + If you publish printed copies (or copies in media that commonly + have printed covers) of the Document, numbering more than 100, and + the Document's license notice requires Cover Texts, you must + enclose the copies in covers that carry, clearly and legibly, all + these Cover Texts: Front-Cover Texts on the front cover, and + Back-Cover Texts on the back cover. Both covers must also clearly + and legibly identify you as the publisher of these copies. The + front cover must present the full title with all words of the title + equally prominent and visible. You may add other material on the + covers in addition. Copying with changes limited to the covers, as + long as they preserve the title of the Document and satisfy these + conditions, can be treated as verbatim copying in other respects. + + If the required texts for either cover are too voluminous to fit + legibly, you should put the first ones listed (as many as fit + reasonably) on the actual cover, and continue the rest onto + adjacent pages. + + If you publish or distribute Opaque copies of the Document + numbering more than 100, you must either include a machine-readable + Transparent copy along with each Opaque copy, or state in or with + each Opaque copy a computer-network location from which the general + network-using public has access to download using public-standard + network protocols a complete Transparent copy of the Document, free + of added material. If you use the latter option, you must take + reasonably prudent steps, when you begin distribution of Opaque + copies in quantity, to ensure that this Transparent copy will + remain thus accessible at the stated location until at least one + year after the last time you distribute an Opaque copy (directly or + through your agents or retailers) of that edition to the public. + + It is requested, but not required, that you contact the authors of + the Document well before redistributing any large number of copies, + to give them a chance to provide you with an updated version of the + Document. + + 4. MODIFICATIONS + + You may copy and distribute a Modified Version of the Document + under the conditions of sections 2 and 3 above, provided that you + release the Modified Version under precisely this License, with the + Modified Version filling the role of the Document, thus licensing + distribution and modification of the Modified Version to whoever + possesses a copy of it. In addition, you must do these things in + the Modified Version: + + A. Use in the Title Page (and on the covers, if any) a title + distinct from that of the Document, and from those of previous + versions (which should, if there were any, be listed in the + History section of the Document). You may use the same title + as a previous version if the original publisher of that + version gives permission. + + B. List on the Title Page, as authors, one or more persons or + entities responsible for authorship of the modifications in + the Modified Version, together with at least five of the + principal authors of the Document (all of its principal + authors, if it has fewer than five), unless they release you + from this requirement. + + C. State on the Title page the name of the publisher of the + Modified Version, as the publisher. + + D. Preserve all the copyright notices of the Document. + + E. Add an appropriate copyright notice for your modifications + adjacent to the other copyright notices. + + F. Include, immediately after the copyright notices, a license + notice giving the public permission to use the Modified + Version under the terms of this License, in the form shown in + the Addendum below. + + G. Preserve in that license notice the full lists of Invariant + Sections and required Cover Texts given in the Document's + license notice. + + H. Include an unaltered copy of this License. + + I. Preserve the section Entitled "History", Preserve its Title, + and add to it an item stating at least the title, year, new + authors, and publisher of the Modified Version as given on the + Title Page. If there is no section Entitled "History" in the + Document, create one stating the title, year, authors, and + publisher of the Document as given on its Title Page, then add + an item describing the Modified Version as stated in the + previous sentence. + + J. Preserve the network location, if any, given in the Document + for public access to a Transparent copy of the Document, and + likewise the network locations given in the Document for + previous versions it was based on. These may be placed in the + "History" section. You may omit a network location for a work + that was published at least four years before the Document + itself, or if the original publisher of the version it refers + to gives permission. + + K. For any section Entitled "Acknowledgements" or "Dedications", + Preserve the Title of the section, and preserve in the section + all the substance and tone of each of the contributor + acknowledgements and/or dedications given therein. + + L. Preserve all the Invariant Sections of the Document, unaltered + in their text and in their titles. Section numbers or the + equivalent are not considered part of the section titles. + + M. Delete any section Entitled "Endorsements". Such a section + may not be included in the Modified Version. + + N. Do not retitle any existing section to be Entitled + "Endorsements" or to conflict in title with any Invariant + Section. + + O. Preserve any Warranty Disclaimers. + + If the Modified Version includes new front-matter sections or + appendices that qualify as Secondary Sections and contain no + material copied from the Document, you may at your option designate + some or all of these sections as invariant. To do this, add their + titles to the list of Invariant Sections in the Modified Version's + license notice. These titles must be distinct from any other + section titles. + + You may add a section Entitled "Endorsements", provided it contains + nothing but endorsements of your Modified Version by various + parties--for example, statements of peer review or that the text + has been approved by an organization as the authoritative + definition of a standard. + + You may add a passage of up to five words as a Front-Cover Text, + and a passage of up to 25 words as a Back-Cover Text, to the end of + the list of Cover Texts in the Modified Version. Only one passage + of Front-Cover Text and one of Back-Cover Text may be added by (or + through arrangements made by) any one entity. If the Document + already includes a cover text for the same cover, previously added + by you or by arrangement made by the same entity you are acting on + behalf of, you may not add another; but you may replace the old + one, on explicit permission from the previous publisher that added + the old one. + + The author(s) and publisher(s) of the Document do not by this + License give permission to use their names for publicity for or to + assert or imply endorsement of any Modified Version. + + 5. COMBINING DOCUMENTS + + You may combine the Document with other documents released under + this License, under the terms defined in section 4 above for + modified versions, provided that you include in the combination all + of the Invariant Sections of all of the original documents, + unmodified, and list them all as Invariant Sections of your + combined work in its license notice, and that you preserve all + their Warranty Disclaimers. + + The combined work need only contain one copy of this License, and + multiple identical Invariant Sections may be replaced with a single + copy. If there are multiple Invariant Sections with the same name + but different contents, make the title of each such section unique + by adding at the end of it, in parentheses, the name of the + original author or publisher of that section if known, or else a + unique number. Make the same adjustment to the section titles in + the list of Invariant Sections in the license notice of the + combined work. + + In the combination, you must combine any sections Entitled + "History" in the various original documents, forming one section + Entitled "History"; likewise combine any sections Entitled + "Acknowledgements", and any sections Entitled "Dedications". You + must delete all sections Entitled "Endorsements." + + 6. COLLECTIONS OF DOCUMENTS + + You may make a collection consisting of the Document and other + documents released under this License, and replace the individual + copies of this License in the various documents with a single copy + that is included in the collection, provided that you follow the + rules of this License for verbatim copying of each of the documents + in all other respects. + + You may extract a single document from such a collection, and + distribute it individually under this License, provided you insert + a copy of this License into the extracted document, and follow this + License in all other respects regarding verbatim copying of that + document. + + 7. AGGREGATION WITH INDEPENDENT WORKS + + A compilation of the Document or its derivatives with other + separate and independent documents or works, in or on a volume of a + storage or distribution medium, is called an "aggregate" if the + copyright resulting from the compilation is not used to limit the + legal rights of the compilation's users beyond what the individual + works permit. When the Document is included in an aggregate, this + License does not apply to the other works in the aggregate which + are not themselves derivative works of the Document. + + If the Cover Text requirement of section 3 is applicable to these + copies of the Document, then if the Document is less than one half + of the entire aggregate, the Document's Cover Texts may be placed + on covers that bracket the Document within the aggregate, or the + electronic equivalent of covers if the Document is in electronic + form. Otherwise they must appear on printed covers that bracket + the whole aggregate. + + 8. TRANSLATION + + Translation is considered a kind of modification, so you may + distribute translations of the Document under the terms of section + 4. Replacing Invariant Sections with translations requires special + permission from their copyright holders, but you may include + translations of some or all Invariant Sections in addition to the + original versions of these Invariant Sections. You may include a + translation of this License, and all the license notices in the + Document, and any Warranty Disclaimers, provided that you also + include the original English version of this License and the + original versions of those notices and disclaimers. In case of a + disagreement between the translation and the original version of + this License or a notice or disclaimer, the original version will + prevail. + + If a section in the Document is Entitled "Acknowledgements", + "Dedications", or "History", the requirement (section 4) to + Preserve its Title (section 1) will typically require changing the + actual title. + + 9. TERMINATION + + You may not copy, modify, sublicense, or distribute the Document + except as expressly provided under this License. Any attempt + otherwise to copy, modify, sublicense, or distribute it is void, + and will automatically terminate your rights under this License. + + However, if you cease all violation of this License, then your + license from a particular copyright holder is reinstated (a) + provisionally, unless and until the copyright holder explicitly and + finally terminates your license, and (b) permanently, if the + copyright holder fails to notify you of the violation by some + reasonable means prior to 60 days after the cessation. + + Moreover, your license from a particular copyright holder is + reinstated permanently if the copyright holder notifies you of the + violation by some reasonable means, this is the first time you have + received notice of violation of this License (for any work) from + that copyright holder, and you cure the violation prior to 30 days + after your receipt of the notice. + + Termination of your rights under this section does not terminate + the licenses of parties who have received copies or rights from you + under this License. If your rights have been terminated and not + permanently reinstated, receipt of a copy of some or all of the + same material does not give you any rights to use it. + + 10. FUTURE REVISIONS OF THIS LICENSE + + The Free Software Foundation may publish new, revised versions of + the GNU Free Documentation License from time to time. Such new + versions will be similar in spirit to the present version, but may + differ in detail to address new problems or concerns. See + <https://www.gnu.org/copyleft/>. + + Each version of the License is given a distinguishing version + number. If the Document specifies that a particular numbered + version of this License "or any later version" applies to it, you + have the option of following the terms and conditions either of + that specified version or of any later version that has been + published (not as a draft) by the Free Software Foundation. If the + Document does not specify a version number of this License, you may + choose any version ever published (not as a draft) by the Free + Software Foundation. If the Document specifies that a proxy can + decide which future versions of this License can be used, that + proxy's public statement of acceptance of a version permanently + authorizes you to choose that version for the Document. + + 11. RELICENSING + + "Massive Multiauthor Collaboration Site" (or "MMC Site") means any + World Wide Web server that publishes copyrightable works and also + provides prominent facilities for anybody to edit those works. A + public wiki that anybody can edit is an example of such a server. + A "Massive Multiauthor Collaboration" (or "MMC") contained in the + site means any set of copyrightable works thus published on the MMC + site. + + "CC-BY-SA" means the Creative Commons Attribution-Share Alike 3.0 + license published by Creative Commons Corporation, a not-for-profit + corporation with a principal place of business in San Francisco, + California, as well as future copyleft versions of that license + published by that same organization. + + "Incorporate" means to publish or republish a Document, in whole or + in part, as part of another Document. + + An MMC is "eligible for relicensing" if it is licensed under this + License, and if all works that were first published under this + License somewhere other than this MMC, and subsequently + incorporated in whole or in part into the MMC, (1) had no cover + texts or invariant sections, and (2) were thus incorporated prior + to November 1, 2008. + + The operator of an MMC Site may republish an MMC contained in the + site under CC-BY-SA on the same site at any time before August 1, + 2009, provided the MMC is eligible for relicensing. + +ADDENDUM: How to use this License for your documents +==================================================== + +To use this License in a document you have written, include a copy of +the License in the document and put the following copyright and license +notices just after the title page: + + Copyright (C) YEAR YOUR NAME. + Permission is granted to copy, distribute and/or modify this document + under the terms of the GNU Free Documentation License, Version 1.3 + or any later version published by the Free Software Foundation; + with no Invariant Sections, no Front-Cover Texts, and no Back-Cover + Texts. A copy of the license is included in the section entitled ``GNU + Free Documentation License''. + + If you have Invariant Sections, Front-Cover Texts and Back-Cover +Texts, replace the "with...Texts." line with this: + + with the Invariant Sections being LIST THEIR TITLES, with + the Front-Cover Texts being LIST, and with the Back-Cover Texts + being LIST. + + If you have Invariant Sections without Cover Texts, or some other +combination of the three, merge those two alternatives to suit the +situation. + + If your document contains nontrivial examples of program code, we +recommend releasing these examples in parallel under your choice of free +software license, such as the GNU General Public License, to permit +their use in free software. + + +File: gmp.info, Node: Concept Index, Next: Function Index, Prev: GNU Free Documentation License, Up: Top + +Concept Index +************* + + +* Menu: + +* #include: Headers and Libraries. + (line 6) +* --build: Build Options. (line 51) +* --disable-fft: Build Options. (line 307) +* --disable-shared: Build Options. (line 44) +* --disable-static: Build Options. (line 44) +* --enable-alloca: Build Options. (line 273) +* --enable-assert: Build Options. (line 313) +* --enable-cxx: Build Options. (line 225) +* --enable-fat: Build Options. (line 160) +* --enable-profiling: Build Options. (line 317) +* --enable-profiling <1>: Profiling. (line 6) +* --exec-prefix: Build Options. (line 32) +* --host: Build Options. (line 65) +* --prefix: Build Options. (line 32) +* -finstrument-functions: Profiling. (line 66) +* 2exp functions: Efficiency. (line 43) +* 68000: Notes for Particular Systems. + (line 94) +* 80x86: Notes for Particular Systems. + (line 150) +* ABI: Build Options. (line 167) +* ABI <1>: ABI and ISA. (line 6) +* About this manual: Introduction to GMP. (line 57) +* AC_CHECK_LIB: Autoconf. (line 11) +* AIX: ABI and ISA. (line 174) +* AIX <1>: Notes for Particular Systems. + (line 7) +* Algorithms: Algorithms. (line 6) +* alloca: Build Options. (line 273) +* Allocation of memory: Custom Allocation. (line 6) +* AMD64: ABI and ISA. (line 44) +* Anonymous FTP of latest version: Introduction to GMP. (line 37) +* Application Binary Interface: ABI and ISA. (line 6) +* Arithmetic functions: Integer Arithmetic. (line 6) +* Arithmetic functions <1>: Rational Arithmetic. (line 6) +* Arithmetic functions <2>: Float Arithmetic. (line 6) +* ARM: Notes for Particular Systems. + (line 20) +* Assembly cache handling: Assembly Cache Handling. + (line 6) +* Assembly carry propagation: Assembly Carry Propagation. + (line 6) +* Assembly code organisation: Assembly Code Organisation. + (line 6) +* Assembly coding: Assembly Coding. (line 6) +* Assembly floating point: Assembly Floating Point. + (line 6) +* Assembly loop unrolling: Assembly Loop Unrolling. + (line 6) +* Assembly SIMD: Assembly SIMD Instructions. + (line 6) +* Assembly software pipelining: Assembly Software Pipelining. + (line 6) +* Assembly writing guide: Assembly Writing Guide. + (line 6) +* Assertion checking: Build Options. (line 313) +* Assertion checking <1>: Debugging. (line 74) +* Assignment functions: Assigning Integers. (line 6) +* Assignment functions <1>: Simultaneous Integer Init & Assign. + (line 6) +* Assignment functions <2>: Initializing Rationals. + (line 6) +* Assignment functions <3>: Assigning Floats. (line 6) +* Assignment functions <4>: Simultaneous Float Init & Assign. + (line 6) +* Autoconf: Autoconf. (line 6) +* Basics: GMP Basics. (line 6) +* Binomial coefficient algorithm: Binomial Coefficients Algorithm. + (line 6) +* Binomial coefficient functions: Number Theoretic Functions. + (line 137) +* Binutils strip: Known Build Problems. + (line 28) +* Bit manipulation functions: Integer Logic and Bit Fiddling. + (line 6) +* Bit scanning functions: Integer Logic and Bit Fiddling. + (line 39) +* Bit shift left: Integer Arithmetic. (line 38) +* Bit shift right: Integer Division. (line 74) +* Bits per limb: Useful Macros and Constants. + (line 7) +* Bug reporting: Reporting Bugs. (line 6) +* Build directory: Build Options. (line 19) +* Build notes for binary packaging: Notes for Package Builds. + (line 6) +* Build notes for particular systems: Notes for Particular Systems. + (line 6) +* Build options: Build Options. (line 6) +* Build problems known: Known Build Problems. + (line 6) +* Build system: Build Options. (line 51) +* Building GMP: Installing GMP. (line 6) +* Bus error: Debugging. (line 7) +* C compiler: Build Options. (line 178) +* C++ compiler: Build Options. (line 249) +* C++ interface: C++ Class Interface. (line 6) +* C++ interface internals: C++ Interface Internals. + (line 6) +* C++ istream input: C++ Formatted Input. (line 6) +* C++ ostream output: C++ Formatted Output. + (line 6) +* C++ support: Build Options. (line 225) +* CC: Build Options. (line 178) +* CC_FOR_BUILD: Build Options. (line 212) +* CFLAGS: Build Options. (line 178) +* Checker: Debugging. (line 110) +* checkergcc: Debugging. (line 117) +* Code organisation: Assembly Code Organisation. + (line 6) +* Compaq C++: Notes for Particular Systems. + (line 25) +* Comparison functions: Integer Comparisons. (line 6) +* Comparison functions <1>: Comparing Rationals. (line 6) +* Comparison functions <2>: Float Comparison. (line 6) +* Compatibility with older versions: Compatibility with older versions. + (line 6) +* Conditions for copying GNU MP: Copying. (line 6) +* Configuring GMP: Installing GMP. (line 6) +* Congruence algorithm: Exact Remainder. (line 30) +* Congruence functions: Integer Division. (line 150) +* Constants: Useful Macros and Constants. + (line 6) +* Contributors: Contributors. (line 6) +* Conventions for parameters: Parameter Conventions. + (line 6) +* Conventions for variables: Variable Conventions. + (line 6) +* Conversion functions: Converting Integers. (line 6) +* Conversion functions <1>: Rational Conversions. + (line 6) +* Conversion functions <2>: Converting Floats. (line 6) +* Copying conditions: Copying. (line 6) +* CPPFLAGS: Build Options. (line 204) +* CPU types: Introduction to GMP. (line 24) +* CPU types <1>: Build Options. (line 107) +* Cross compiling: Build Options. (line 65) +* Cryptography functions, low-level: Low-level Functions. (line 507) +* Custom allocation: Custom Allocation. (line 6) +* CXX: Build Options. (line 249) +* CXXFLAGS: Build Options. (line 249) +* Cygwin: Notes for Particular Systems. + (line 57) +* Darwin: Known Build Problems. + (line 51) +* Debugging: Debugging. (line 6) +* Demonstration programs: Demonstration Programs. + (line 6) +* Digits in an integer: Miscellaneous Integer Functions. + (line 23) +* Divisibility algorithm: Exact Remainder. (line 30) +* Divisibility functions: Integer Division. (line 136) +* Divisibility functions <1>: Integer Division. (line 150) +* Divisibility testing: Efficiency. (line 91) +* Division algorithms: Division Algorithms. (line 6) +* Division functions: Integer Division. (line 6) +* Division functions <1>: Rational Arithmetic. (line 24) +* Division functions <2>: Float Arithmetic. (line 33) +* DJGPP: Notes for Particular Systems. + (line 57) +* DJGPP <1>: Known Build Problems. + (line 18) +* DLLs: Notes for Particular Systems. + (line 70) +* DocBook: Build Options. (line 340) +* Documentation formats: Build Options. (line 333) +* Documentation license: GNU Free Documentation License. + (line 6) +* DVI: Build Options. (line 336) +* Efficiency: Efficiency. (line 6) +* Emacs: Emacs. (line 6) +* Exact division functions: Integer Division. (line 125) +* Exact remainder: Exact Remainder. (line 6) +* Example programs: Demonstration Programs. + (line 6) +* Exec prefix: Build Options. (line 32) +* Execution profiling: Build Options. (line 317) +* Execution profiling <1>: Profiling. (line 6) +* Exponentiation functions: Integer Exponentiation. + (line 6) +* Exponentiation functions <1>: Float Arithmetic. (line 41) +* Export: Integer Import and Export. + (line 45) +* Expression parsing demo: Demonstration Programs. + (line 15) +* Expression parsing demo <1>: Demonstration Programs. + (line 17) +* Expression parsing demo <2>: Demonstration Programs. + (line 19) +* Extended GCD: Number Theoretic Functions. + (line 56) +* Factor removal functions: Number Theoretic Functions. + (line 117) +* Factorial algorithm: Factorial Algorithm. (line 6) +* Factorial functions: Number Theoretic Functions. + (line 125) +* Factorization demo: Demonstration Programs. + (line 22) +* Fast Fourier Transform: FFT Multiplication. (line 6) +* Fat binary: Build Options. (line 160) +* FFT multiplication: Build Options. (line 307) +* FFT multiplication <1>: FFT Multiplication. (line 6) +* Fibonacci number algorithm: Fibonacci Numbers Algorithm. + (line 6) +* Fibonacci sequence functions: Number Theoretic Functions. + (line 145) +* Float arithmetic functions: Float Arithmetic. (line 6) +* Float assignment functions: Assigning Floats. (line 6) +* Float assignment functions <1>: Simultaneous Float Init & Assign. + (line 6) +* Float comparison functions: Float Comparison. (line 6) +* Float conversion functions: Converting Floats. (line 6) +* Float functions: Floating-point Functions. + (line 6) +* Float initialization functions: Initializing Floats. (line 6) +* Float initialization functions <1>: Simultaneous Float Init & Assign. + (line 6) +* Float input and output functions: I/O of Floats. (line 6) +* Float internals: Float Internals. (line 6) +* Float miscellaneous functions: Miscellaneous Float Functions. + (line 6) +* Float random number functions: Miscellaneous Float Functions. + (line 27) +* Float rounding functions: Miscellaneous Float Functions. + (line 9) +* Float sign tests: Float Comparison. (line 34) +* Floating point mode: Notes for Particular Systems. + (line 34) +* Floating-point functions: Floating-point Functions. + (line 6) +* Floating-point number: Nomenclature and Types. + (line 21) +* fnccheck: Profiling. (line 77) +* Formatted input: Formatted Input. (line 6) +* Formatted output: Formatted Output. (line 6) +* Free Documentation License: GNU Free Documentation License. + (line 6) +* FreeBSD: Notes for Particular Systems. + (line 43) +* FreeBSD <1>: Notes for Particular Systems. + (line 52) +* frexp: Converting Integers. (line 43) +* frexp <1>: Converting Floats. (line 24) +* FTP of latest version: Introduction to GMP. (line 37) +* Function classes: Function Classes. (line 6) +* FunctionCheck: Profiling. (line 77) +* GCC Checker: Debugging. (line 110) +* GCD algorithms: Greatest Common Divisor Algorithms. + (line 6) +* GCD extended: Number Theoretic Functions. + (line 56) +* GCD functions: Number Theoretic Functions. + (line 39) +* GDB: Debugging. (line 53) +* Generic C: Build Options. (line 151) +* GMP Perl module: Demonstration Programs. + (line 28) +* GMP version number: Useful Macros and Constants. + (line 12) +* gmp.h: Headers and Libraries. + (line 6) +* gmpxx.h: C++ Interface General. + (line 8) +* GNU Debugger: Debugging. (line 53) +* GNU Free Documentation License: GNU Free Documentation License. + (line 6) +* GNU strip: Known Build Problems. + (line 28) +* gprof: Profiling. (line 41) +* Greatest common divisor algorithms: Greatest Common Divisor Algorithms. + (line 6) +* Greatest common divisor functions: Number Theoretic Functions. + (line 39) +* Hardware floating point mode: Notes for Particular Systems. + (line 34) +* Headers: Headers and Libraries. + (line 6) +* Heap problems: Debugging. (line 23) +* Home page: Introduction to GMP. (line 33) +* Host system: Build Options. (line 65) +* HP-UX: ABI and ISA. (line 76) +* HP-UX <1>: ABI and ISA. (line 114) +* HPPA: ABI and ISA. (line 76) +* I/O functions: I/O of Integers. (line 6) +* I/O functions <1>: I/O of Rationals. (line 6) +* I/O functions <2>: I/O of Floats. (line 6) +* i386: Notes for Particular Systems. + (line 150) +* IA-64: ABI and ISA. (line 114) +* Import: Integer Import and Export. + (line 11) +* In-place operations: Efficiency. (line 57) +* Include files: Headers and Libraries. + (line 6) +* info-lookup-symbol: Emacs. (line 6) +* Initialization functions: Initializing Integers. + (line 6) +* Initialization functions <1>: Simultaneous Integer Init & Assign. + (line 6) +* Initialization functions <2>: Initializing Rationals. + (line 6) +* Initialization functions <3>: Initializing Floats. (line 6) +* Initialization functions <4>: Simultaneous Float Init & Assign. + (line 6) +* Initialization functions <5>: Random State Initialization. + (line 6) +* Initializing and clearing: Efficiency. (line 21) +* Input functions: I/O of Integers. (line 6) +* Input functions <1>: I/O of Rationals. (line 6) +* Input functions <2>: I/O of Floats. (line 6) +* Input functions <3>: Formatted Input Functions. + (line 6) +* Install prefix: Build Options. (line 32) +* Installing GMP: Installing GMP. (line 6) +* Instruction Set Architecture: ABI and ISA. (line 6) +* instrument-functions: Profiling. (line 66) +* Integer: Nomenclature and Types. + (line 6) +* Integer arithmetic functions: Integer Arithmetic. (line 6) +* Integer assignment functions: Assigning Integers. (line 6) +* Integer assignment functions <1>: Simultaneous Integer Init & Assign. + (line 6) +* Integer bit manipulation functions: Integer Logic and Bit Fiddling. + (line 6) +* Integer comparison functions: Integer Comparisons. (line 6) +* Integer conversion functions: Converting Integers. (line 6) +* Integer division functions: Integer Division. (line 6) +* Integer exponentiation functions: Integer Exponentiation. + (line 6) +* Integer export: Integer Import and Export. + (line 45) +* Integer functions: Integer Functions. (line 6) +* Integer import: Integer Import and Export. + (line 11) +* Integer initialization functions: Initializing Integers. + (line 6) +* Integer initialization functions <1>: Simultaneous Integer Init & Assign. + (line 6) +* Integer input and output functions: I/O of Integers. (line 6) +* Integer internals: Integer Internals. (line 6) +* Integer logical functions: Integer Logic and Bit Fiddling. + (line 6) +* Integer miscellaneous functions: Miscellaneous Integer Functions. + (line 6) +* Integer random number functions: Integer Random Numbers. + (line 6) +* Integer root functions: Integer Roots. (line 6) +* Integer sign tests: Integer Comparisons. (line 28) +* Integer special functions: Integer Special Functions. + (line 6) +* Interix: Notes for Particular Systems. + (line 65) +* Internals: Internals. (line 6) +* Introduction: Introduction to GMP. (line 6) +* Inverse modulo functions: Number Theoretic Functions. + (line 83) +* IRIX: ABI and ISA. (line 139) +* IRIX <1>: Known Build Problems. + (line 38) +* ISA: ABI and ISA. (line 6) +* istream input: C++ Formatted Input. (line 6) +* Jacobi symbol algorithm: Jacobi Symbol. (line 6) +* Jacobi symbol functions: Number Theoretic Functions. + (line 92) +* Karatsuba multiplication: Karatsuba Multiplication. + (line 6) +* Karatsuba square root algorithm: Square Root Algorithm. + (line 6) +* Kronecker symbol functions: Number Theoretic Functions. + (line 104) +* Language bindings: Language Bindings. (line 6) +* Latest version of GMP: Introduction to GMP. (line 37) +* LCM functions: Number Theoretic Functions. + (line 77) +* Least common multiple functions: Number Theoretic Functions. + (line 77) +* Legendre symbol functions: Number Theoretic Functions. + (line 95) +* libgmp: Headers and Libraries. + (line 24) +* libgmpxx: Headers and Libraries. + (line 29) +* Libraries: Headers and Libraries. + (line 24) +* Libtool: Headers and Libraries. + (line 36) +* Libtool versioning: Notes for Package Builds. + (line 9) +* License conditions: Copying. (line 6) +* Limb: Nomenclature and Types. + (line 31) +* Limb size: Useful Macros and Constants. + (line 7) +* Linear congruential algorithm: Random Number Algorithms. + (line 25) +* Linear congruential random numbers: Random State Initialization. + (line 18) +* Linear congruential random numbers <1>: Random State Initialization. + (line 32) +* Linking: Headers and Libraries. + (line 24) +* Logical functions: Integer Logic and Bit Fiddling. + (line 6) +* Low-level functions: Low-level Functions. (line 6) +* Low-level functions for cryptography: Low-level Functions. (line 507) +* Lucas number algorithm: Lucas Numbers Algorithm. + (line 6) +* Lucas number functions: Number Theoretic Functions. + (line 156) +* MacOS X: Known Build Problems. + (line 51) +* Mailing lists: Introduction to GMP. (line 44) +* Malloc debugger: Debugging. (line 29) +* Malloc problems: Debugging. (line 23) +* Memory allocation: Custom Allocation. (line 6) +* Memory management: Memory Management. (line 6) +* Mersenne twister algorithm: Random Number Algorithms. + (line 17) +* Mersenne twister random numbers: Random State Initialization. + (line 13) +* MINGW: Notes for Particular Systems. + (line 57) +* MIPS: ABI and ISA. (line 139) +* Miscellaneous float functions: Miscellaneous Float Functions. + (line 6) +* Miscellaneous integer functions: Miscellaneous Integer Functions. + (line 6) +* MMX: Notes for Particular Systems. + (line 156) +* Modular inverse functions: Number Theoretic Functions. + (line 83) +* Most significant bit: Miscellaneous Integer Functions. + (line 34) +* MPN_PATH: Build Options. (line 321) +* MS Windows: Notes for Particular Systems. + (line 57) +* MS Windows <1>: Notes for Particular Systems. + (line 70) +* MS-DOS: Notes for Particular Systems. + (line 57) +* Multi-threading: Reentrancy. (line 6) +* Multiplication algorithms: Multiplication Algorithms. + (line 6) +* Nails: Low-level Functions. (line 686) +* Native compilation: Build Options. (line 51) +* NetBSD: Notes for Particular Systems. + (line 100) +* NeXT: Known Build Problems. + (line 57) +* Next prime function: Number Theoretic Functions. + (line 23) +* Nomenclature: Nomenclature and Types. + (line 6) +* Non-Unix systems: Build Options. (line 11) +* Nth root algorithm: Nth Root Algorithm. (line 6) +* Number sequences: Efficiency. (line 145) +* Number theoretic functions: Number Theoretic Functions. + (line 6) +* Numerator and denominator: Applying Integer Functions. + (line 6) +* obstack output: Formatted Output Functions. + (line 79) +* OpenBSD: Notes for Particular Systems. + (line 109) +* Optimizing performance: Performance optimization. + (line 6) +* ostream output: C++ Formatted Output. + (line 6) +* Other languages: Language Bindings. (line 6) +* Output functions: I/O of Integers. (line 6) +* Output functions <1>: I/O of Rationals. (line 6) +* Output functions <2>: I/O of Floats. (line 6) +* Output functions <3>: Formatted Output Functions. + (line 6) +* Packaged builds: Notes for Package Builds. + (line 6) +* Parameter conventions: Parameter Conventions. + (line 6) +* Parsing expressions demo: Demonstration Programs. + (line 15) +* Parsing expressions demo <1>: Demonstration Programs. + (line 17) +* Parsing expressions demo <2>: Demonstration Programs. + (line 19) +* Particular systems: Notes for Particular Systems. + (line 6) +* Past GMP versions: Compatibility with older versions. + (line 6) +* PDF: Build Options. (line 336) +* Perfect power algorithm: Perfect Power Algorithm. + (line 6) +* Perfect power functions: Integer Roots. (line 28) +* Perfect square algorithm: Perfect Square Algorithm. + (line 6) +* Perfect square functions: Integer Roots. (line 37) +* perl: Demonstration Programs. + (line 28) +* Perl module: Demonstration Programs. + (line 28) +* Pointer types: Nomenclature and Types. + (line 55) +* Postscript: Build Options. (line 336) +* Power/PowerPC: Notes for Particular Systems. + (line 115) +* Power/PowerPC <1>: Known Build Problems. + (line 63) +* Powering algorithms: Powering Algorithms. (line 6) +* Powering functions: Integer Exponentiation. + (line 6) +* Powering functions <1>: Float Arithmetic. (line 41) +* PowerPC: ABI and ISA. (line 173) +* Precision of floats: Floating-point Functions. + (line 6) +* Precision of hardware floating point: Notes for Particular Systems. + (line 34) +* Prefix: Build Options. (line 32) +* Previous prime function: Number Theoretic Functions. + (line 26) +* Prime testing algorithms: Prime Testing Algorithm. + (line 6) +* Prime testing functions: Number Theoretic Functions. + (line 7) +* Primorial functions: Number Theoretic Functions. + (line 130) +* printf formatted output: Formatted Output. (line 6) +* Probable prime testing functions: Number Theoretic Functions. + (line 7) +* prof: Profiling. (line 24) +* Profiling: Profiling. (line 6) +* Radix conversion algorithms: Radix Conversion Algorithms. + (line 6) +* Random number algorithms: Random Number Algorithms. + (line 6) +* Random number functions: Integer Random Numbers. + (line 6) +* Random number functions <1>: Miscellaneous Float Functions. + (line 27) +* Random number functions <2>: Random Number Functions. + (line 6) +* Random number seeding: Random State Seeding. + (line 6) +* Random number state: Random State Initialization. + (line 6) +* Random state: Nomenclature and Types. + (line 46) +* Rational arithmetic: Efficiency. (line 111) +* Rational arithmetic functions: Rational Arithmetic. (line 6) +* Rational assignment functions: Initializing Rationals. + (line 6) +* Rational comparison functions: Comparing Rationals. (line 6) +* Rational conversion functions: Rational Conversions. + (line 6) +* Rational initialization functions: Initializing Rationals. + (line 6) +* Rational input and output functions: I/O of Rationals. (line 6) +* Rational internals: Rational Internals. (line 6) +* Rational number: Nomenclature and Types. + (line 16) +* Rational number functions: Rational Number Functions. + (line 6) +* Rational numerator and denominator: Applying Integer Functions. + (line 6) +* Rational sign tests: Comparing Rationals. (line 28) +* Raw output internals: Raw Output Internals. + (line 6) +* Reallocations: Efficiency. (line 30) +* Reentrancy: Reentrancy. (line 6) +* References: References. (line 5) +* Remove factor functions: Number Theoretic Functions. + (line 117) +* Reporting bugs: Reporting Bugs. (line 6) +* Root extraction algorithm: Nth Root Algorithm. (line 6) +* Root extraction algorithms: Root Extraction Algorithms. + (line 6) +* Root extraction functions: Integer Roots. (line 6) +* Root extraction functions <1>: Float Arithmetic. (line 37) +* Root testing functions: Integer Roots. (line 28) +* Root testing functions <1>: Integer Roots. (line 37) +* Rounding functions: Miscellaneous Float Functions. + (line 9) +* Sample programs: Demonstration Programs. + (line 6) +* Scan bit functions: Integer Logic and Bit Fiddling. + (line 39) +* scanf formatted input: Formatted Input. (line 6) +* SCO: Known Build Problems. + (line 38) +* Seeding random numbers: Random State Seeding. + (line 6) +* Segmentation violation: Debugging. (line 7) +* Sequent Symmetry: Known Build Problems. + (line 68) +* Services for Unix: Notes for Particular Systems. + (line 65) +* Shared library versioning: Notes for Package Builds. + (line 9) +* Sign tests: Integer Comparisons. (line 28) +* Sign tests <1>: Comparing Rationals. (line 28) +* Sign tests <2>: Float Comparison. (line 34) +* Size in digits: Miscellaneous Integer Functions. + (line 23) +* Small operands: Efficiency. (line 7) +* Solaris: ABI and ISA. (line 204) +* Solaris <1>: Known Build Problems. + (line 72) +* Solaris <2>: Known Build Problems. + (line 77) +* Sparc: Notes for Particular Systems. + (line 127) +* Sparc <1>: Notes for Particular Systems. + (line 132) +* Sparc V9: ABI and ISA. (line 204) +* Special integer functions: Integer Special Functions. + (line 6) +* Square root algorithm: Square Root Algorithm. + (line 6) +* SSE2: Notes for Particular Systems. + (line 156) +* Stack backtrace: Debugging. (line 45) +* Stack overflow: Build Options. (line 273) +* Stack overflow <1>: Debugging. (line 7) +* Static linking: Efficiency. (line 14) +* stdarg.h: Headers and Libraries. + (line 19) +* stdio.h: Headers and Libraries. + (line 13) +* Stripped libraries: Known Build Problems. + (line 28) +* Sun: ABI and ISA. (line 204) +* SunOS: Notes for Particular Systems. + (line 144) +* Systems: Notes for Particular Systems. + (line 6) +* Temporary memory: Build Options. (line 273) +* Texinfo: Build Options. (line 333) +* Text input/output: Efficiency. (line 151) +* Thread safety: Reentrancy. (line 6) +* Toom multiplication: Toom 3-Way Multiplication. + (line 6) +* Toom multiplication <1>: Toom 4-Way Multiplication. + (line 6) +* Toom multiplication <2>: Higher degree Toom'n'half. + (line 6) +* Toom multiplication <3>: Other Multiplication. + (line 6) +* Types: Nomenclature and Types. + (line 6) +* ui and si functions: Efficiency. (line 50) +* Unbalanced multiplication: Unbalanced Multiplication. + (line 6) +* Upward compatibility: Compatibility with older versions. + (line 6) +* Useful macros and constants: Useful Macros and Constants. + (line 6) +* User-defined precision: Floating-point Functions. + (line 6) +* Valgrind: Debugging. (line 125) +* Variable conventions: Variable Conventions. + (line 6) +* Version number: Useful Macros and Constants. + (line 12) +* Web page: Introduction to GMP. (line 33) +* Windows: Notes for Particular Systems. + (line 57) +* Windows <1>: Notes for Particular Systems. + (line 70) +* x86: Notes for Particular Systems. + (line 150) +* x87: Notes for Particular Systems. + (line 34) +* XML: Build Options. (line 340) + + +File: gmp.info, Node: Function Index, Prev: Concept Index, Up: Top + +Function and Type Index +*********************** + + +* Menu: + +* _mpz_realloc: Integer Special Functions. + (line 13) +* __GMP_CC: Useful Macros and Constants. + (line 22) +* __GMP_CFLAGS: Useful Macros and Constants. + (line 23) +* __GNU_MP_VERSION: Useful Macros and Constants. + (line 9) +* __GNU_MP_VERSION_MINOR: Useful Macros and Constants. + (line 10) +* __GNU_MP_VERSION_PATCHLEVEL: Useful Macros and Constants. + (line 11) +* abs: C++ Interface Integers. + (line 46) +* abs <1>: C++ Interface Rationals. + (line 47) +* abs <2>: C++ Interface Floats. + (line 82) +* ceil: C++ Interface Floats. + (line 83) +* cmp: C++ Interface Integers. + (line 47) +* cmp <1>: C++ Interface Integers. + (line 48) +* cmp <2>: C++ Interface Rationals. + (line 48) +* cmp <3>: C++ Interface Rationals. + (line 49) +* cmp <4>: C++ Interface Floats. + (line 84) +* cmp <5>: C++ Interface Floats. + (line 85) +* factorial: C++ Interface Integers. + (line 71) +* fibonacci: C++ Interface Integers. + (line 75) +* floor: C++ Interface Floats. + (line 95) +* gcd: C++ Interface Integers. + (line 68) +* gmp_asprintf: Formatted Output Functions. + (line 63) +* gmp_errno: Random State Initialization. + (line 56) +* GMP_ERROR_INVALID_ARGUMENT: Random State Initialization. + (line 56) +* GMP_ERROR_UNSUPPORTED_ARGUMENT: Random State Initialization. + (line 56) +* gmp_fprintf: Formatted Output Functions. + (line 28) +* gmp_fscanf: Formatted Input Functions. + (line 24) +* GMP_LIMB_BITS: Low-level Functions. (line 714) +* GMP_NAIL_BITS: Low-level Functions. (line 712) +* GMP_NAIL_MASK: Low-level Functions. (line 722) +* GMP_NUMB_BITS: Low-level Functions. (line 713) +* GMP_NUMB_MASK: Low-level Functions. (line 723) +* GMP_NUMB_MAX: Low-level Functions. (line 731) +* gmp_obstack_printf: Formatted Output Functions. + (line 75) +* gmp_obstack_vprintf: Formatted Output Functions. + (line 77) +* gmp_printf: Formatted Output Functions. + (line 23) +* gmp_randclass: C++ Interface Random Numbers. + (line 6) +* gmp_randclass::get_f: C++ Interface Random Numbers. + (line 44) +* gmp_randclass::get_f <1>: C++ Interface Random Numbers. + (line 45) +* gmp_randclass::get_z_bits: C++ Interface Random Numbers. + (line 37) +* gmp_randclass::get_z_bits <1>: C++ Interface Random Numbers. + (line 38) +* gmp_randclass::get_z_range: C++ Interface Random Numbers. + (line 41) +* gmp_randclass::gmp_randclass: C++ Interface Random Numbers. + (line 11) +* gmp_randclass::gmp_randclass <1>: C++ Interface Random Numbers. + (line 26) +* gmp_randclass::seed: C++ Interface Random Numbers. + (line 32) +* gmp_randclass::seed <1>: C++ Interface Random Numbers. + (line 33) +* gmp_randclear: Random State Initialization. + (line 62) +* gmp_randinit: Random State Initialization. + (line 45) +* gmp_randinit_default: Random State Initialization. + (line 6) +* gmp_randinit_lc_2exp: Random State Initialization. + (line 16) +* gmp_randinit_lc_2exp_size: Random State Initialization. + (line 30) +* gmp_randinit_mt: Random State Initialization. + (line 12) +* gmp_randinit_set: Random State Initialization. + (line 41) +* gmp_randseed: Random State Seeding. + (line 6) +* gmp_randseed_ui: Random State Seeding. + (line 8) +* gmp_randstate_ptr: Nomenclature and Types. + (line 55) +* gmp_randstate_srcptr: Nomenclature and Types. + (line 55) +* gmp_randstate_t: Nomenclature and Types. + (line 46) +* GMP_RAND_ALG_DEFAULT: Random State Initialization. + (line 50) +* GMP_RAND_ALG_LC: Random State Initialization. + (line 50) +* gmp_scanf: Formatted Input Functions. + (line 20) +* gmp_snprintf: Formatted Output Functions. + (line 44) +* gmp_sprintf: Formatted Output Functions. + (line 33) +* gmp_sscanf: Formatted Input Functions. + (line 28) +* gmp_urandomb_ui: Random State Miscellaneous. + (line 6) +* gmp_urandomm_ui: Random State Miscellaneous. + (line 12) +* gmp_vasprintf: Formatted Output Functions. + (line 64) +* gmp_version: Useful Macros and Constants. + (line 18) +* gmp_vfprintf: Formatted Output Functions. + (line 29) +* gmp_vfscanf: Formatted Input Functions. + (line 25) +* gmp_vprintf: Formatted Output Functions. + (line 24) +* gmp_vscanf: Formatted Input Functions. + (line 21) +* gmp_vsnprintf: Formatted Output Functions. + (line 46) +* gmp_vsprintf: Formatted Output Functions. + (line 34) +* gmp_vsscanf: Formatted Input Functions. + (line 29) +* hypot: C++ Interface Floats. + (line 96) +* lcm: C++ Interface Integers. + (line 69) +* mpf_abs: Float Arithmetic. (line 46) +* mpf_add: Float Arithmetic. (line 6) +* mpf_add_ui: Float Arithmetic. (line 7) +* mpf_ceil: Miscellaneous Float Functions. + (line 6) +* mpf_class: C++ Interface General. + (line 19) +* mpf_class::fits_sint_p: C++ Interface Floats. + (line 87) +* mpf_class::fits_slong_p: C++ Interface Floats. + (line 88) +* mpf_class::fits_sshort_p: C++ Interface Floats. + (line 89) +* mpf_class::fits_uint_p: C++ Interface Floats. + (line 91) +* mpf_class::fits_ulong_p: C++ Interface Floats. + (line 92) +* mpf_class::fits_ushort_p: C++ Interface Floats. + (line 93) +* mpf_class::get_d: C++ Interface Floats. + (line 98) +* mpf_class::get_mpf_t: C++ Interface General. + (line 65) +* mpf_class::get_prec: C++ Interface Floats. + (line 120) +* mpf_class::get_si: C++ Interface Floats. + (line 99) +* mpf_class::get_str: C++ Interface Floats. + (line 100) +* mpf_class::get_ui: C++ Interface Floats. + (line 102) +* mpf_class::mpf_class: C++ Interface Floats. + (line 11) +* mpf_class::mpf_class <1>: C++ Interface Floats. + (line 12) +* mpf_class::mpf_class <2>: C++ Interface Floats. + (line 32) +* mpf_class::mpf_class <3>: C++ Interface Floats. + (line 33) +* mpf_class::mpf_class <4>: C++ Interface Floats. + (line 41) +* mpf_class::mpf_class <5>: C++ Interface Floats. + (line 42) +* mpf_class::mpf_class <6>: C++ Interface Floats. + (line 44) +* mpf_class::mpf_class <7>: C++ Interface Floats. + (line 45) +* mpf_class::operator=: C++ Interface Floats. + (line 59) +* mpf_class::set_prec: C++ Interface Floats. + (line 121) +* mpf_class::set_prec_raw: C++ Interface Floats. + (line 122) +* mpf_class::set_str: C++ Interface Floats. + (line 104) +* mpf_class::set_str <1>: C++ Interface Floats. + (line 105) +* mpf_class::swap: C++ Interface Floats. + (line 109) +* mpf_clear: Initializing Floats. (line 36) +* mpf_clears: Initializing Floats. (line 40) +* mpf_cmp: Float Comparison. (line 6) +* mpf_cmp_d: Float Comparison. (line 8) +* mpf_cmp_si: Float Comparison. (line 10) +* mpf_cmp_ui: Float Comparison. (line 9) +* mpf_cmp_z: Float Comparison. (line 7) +* mpf_div: Float Arithmetic. (line 28) +* mpf_div_2exp: Float Arithmetic. (line 53) +* mpf_div_ui: Float Arithmetic. (line 31) +* mpf_eq: Float Comparison. (line 17) +* mpf_fits_sint_p: Miscellaneous Float Functions. + (line 19) +* mpf_fits_slong_p: Miscellaneous Float Functions. + (line 17) +* mpf_fits_sshort_p: Miscellaneous Float Functions. + (line 21) +* mpf_fits_uint_p: Miscellaneous Float Functions. + (line 18) +* mpf_fits_ulong_p: Miscellaneous Float Functions. + (line 16) +* mpf_fits_ushort_p: Miscellaneous Float Functions. + (line 20) +* mpf_floor: Miscellaneous Float Functions. + (line 7) +* mpf_get_d: Converting Floats. (line 6) +* mpf_get_default_prec: Initializing Floats. (line 11) +* mpf_get_d_2exp: Converting Floats. (line 15) +* mpf_get_prec: Initializing Floats. (line 61) +* mpf_get_si: Converting Floats. (line 27) +* mpf_get_str: Converting Floats. (line 36) +* mpf_get_ui: Converting Floats. (line 28) +* mpf_init: Initializing Floats. (line 18) +* mpf_init2: Initializing Floats. (line 25) +* mpf_inits: Initializing Floats. (line 30) +* mpf_init_set: Simultaneous Float Init & Assign. + (line 15) +* mpf_init_set_d: Simultaneous Float Init & Assign. + (line 18) +* mpf_init_set_si: Simultaneous Float Init & Assign. + (line 17) +* mpf_init_set_str: Simultaneous Float Init & Assign. + (line 24) +* mpf_init_set_ui: Simultaneous Float Init & Assign. + (line 16) +* mpf_inp_str: I/O of Floats. (line 38) +* mpf_integer_p: Miscellaneous Float Functions. + (line 13) +* mpf_mul: Float Arithmetic. (line 18) +* mpf_mul_2exp: Float Arithmetic. (line 49) +* mpf_mul_ui: Float Arithmetic. (line 19) +* mpf_neg: Float Arithmetic. (line 43) +* mpf_out_str: I/O of Floats. (line 17) +* mpf_pow_ui: Float Arithmetic. (line 39) +* mpf_ptr: Nomenclature and Types. + (line 55) +* mpf_random2: Miscellaneous Float Functions. + (line 35) +* mpf_reldiff: Float Comparison. (line 28) +* mpf_set: Assigning Floats. (line 9) +* mpf_set_d: Assigning Floats. (line 12) +* mpf_set_default_prec: Initializing Floats. (line 6) +* mpf_set_prec: Initializing Floats. (line 64) +* mpf_set_prec_raw: Initializing Floats. (line 71) +* mpf_set_q: Assigning Floats. (line 14) +* mpf_set_si: Assigning Floats. (line 11) +* mpf_set_str: Assigning Floats. (line 17) +* mpf_set_ui: Assigning Floats. (line 10) +* mpf_set_z: Assigning Floats. (line 13) +* mpf_sgn: Float Comparison. (line 33) +* mpf_sqrt: Float Arithmetic. (line 35) +* mpf_sqrt_ui: Float Arithmetic. (line 36) +* mpf_srcptr: Nomenclature and Types. + (line 55) +* mpf_sub: Float Arithmetic. (line 11) +* mpf_sub_ui: Float Arithmetic. (line 14) +* mpf_swap: Assigning Floats. (line 50) +* mpf_t: Nomenclature and Types. + (line 21) +* mpf_trunc: Miscellaneous Float Functions. + (line 8) +* mpf_ui_div: Float Arithmetic. (line 29) +* mpf_ui_sub: Float Arithmetic. (line 12) +* mpf_urandomb: Miscellaneous Float Functions. + (line 25) +* mpn_add: Low-level Functions. (line 67) +* mpn_addmul_1: Low-level Functions. (line 148) +* mpn_add_1: Low-level Functions. (line 62) +* mpn_add_n: Low-level Functions. (line 52) +* mpn_andn_n: Low-level Functions. (line 462) +* mpn_and_n: Low-level Functions. (line 447) +* mpn_cmp: Low-level Functions. (line 293) +* mpn_cnd_add_n: Low-level Functions. (line 540) +* mpn_cnd_sub_n: Low-level Functions. (line 542) +* mpn_cnd_swap: Low-level Functions. (line 567) +* mpn_com: Low-level Functions. (line 487) +* mpn_copyd: Low-level Functions. (line 496) +* mpn_copyi: Low-level Functions. (line 492) +* mpn_divexact_1: Low-level Functions. (line 231) +* mpn_divexact_by3: Low-level Functions. (line 238) +* mpn_divexact_by3c: Low-level Functions. (line 240) +* mpn_divmod: Low-level Functions. (line 226) +* mpn_divmod_1: Low-level Functions. (line 210) +* mpn_divrem: Low-level Functions. (line 183) +* mpn_divrem_1: Low-level Functions. (line 208) +* mpn_gcd: Low-level Functions. (line 301) +* mpn_gcdext: Low-level Functions. (line 316) +* mpn_gcd_1: Low-level Functions. (line 311) +* mpn_get_str: Low-level Functions. (line 371) +* mpn_hamdist: Low-level Functions. (line 436) +* mpn_iorn_n: Low-level Functions. (line 467) +* mpn_ior_n: Low-level Functions. (line 452) +* mpn_lshift: Low-level Functions. (line 269) +* mpn_mod_1: Low-level Functions. (line 264) +* mpn_mul: Low-level Functions. (line 114) +* mpn_mul_1: Low-level Functions. (line 133) +* mpn_mul_n: Low-level Functions. (line 103) +* mpn_nand_n: Low-level Functions. (line 472) +* mpn_neg: Low-level Functions. (line 96) +* mpn_nior_n: Low-level Functions. (line 477) +* mpn_perfect_square_p: Low-level Functions. (line 442) +* mpn_popcount: Low-level Functions. (line 432) +* mpn_random: Low-level Functions. (line 422) +* mpn_random2: Low-level Functions. (line 423) +* mpn_rshift: Low-level Functions. (line 281) +* mpn_scan0: Low-level Functions. (line 406) +* mpn_scan1: Low-level Functions. (line 414) +* mpn_sec_add_1: Low-level Functions. (line 553) +* mpn_sec_div_qr: Low-level Functions. (line 630) +* mpn_sec_div_qr_itch: Low-level Functions. (line 633) +* mpn_sec_div_r: Low-level Functions. (line 649) +* mpn_sec_div_r_itch: Low-level Functions. (line 651) +* mpn_sec_invert: Low-level Functions. (line 665) +* mpn_sec_invert_itch: Low-level Functions. (line 667) +* mpn_sec_mul: Low-level Functions. (line 574) +* mpn_sec_mul_itch: Low-level Functions. (line 577) +* mpn_sec_powm: Low-level Functions. (line 604) +* mpn_sec_powm_itch: Low-level Functions. (line 607) +* mpn_sec_sqr: Low-level Functions. (line 590) +* mpn_sec_sqr_itch: Low-level Functions. (line 592) +* mpn_sec_sub_1: Low-level Functions. (line 555) +* mpn_sec_tabselect: Low-level Functions. (line 622) +* mpn_set_str: Low-level Functions. (line 386) +* mpn_sizeinbase: Low-level Functions. (line 364) +* mpn_sqr: Low-level Functions. (line 125) +* mpn_sqrtrem: Low-level Functions. (line 346) +* mpn_sub: Low-level Functions. (line 88) +* mpn_submul_1: Low-level Functions. (line 160) +* mpn_sub_1: Low-level Functions. (line 83) +* mpn_sub_n: Low-level Functions. (line 74) +* mpn_tdiv_qr: Low-level Functions. (line 172) +* mpn_xnor_n: Low-level Functions. (line 482) +* mpn_xor_n: Low-level Functions. (line 457) +* mpn_zero: Low-level Functions. (line 500) +* mpn_zero_p: Low-level Functions. (line 298) +* mpq_abs: Rational Arithmetic. (line 33) +* mpq_add: Rational Arithmetic. (line 6) +* mpq_canonicalize: Rational Number Functions. + (line 21) +* mpq_class: C++ Interface General. + (line 18) +* mpq_class::canonicalize: C++ Interface Rationals. + (line 41) +* mpq_class::get_d: C++ Interface Rationals. + (line 51) +* mpq_class::get_den: C++ Interface Rationals. + (line 67) +* mpq_class::get_den_mpz_t: C++ Interface Rationals. + (line 77) +* mpq_class::get_mpq_t: C++ Interface General. + (line 64) +* mpq_class::get_num: C++ Interface Rationals. + (line 66) +* mpq_class::get_num_mpz_t: C++ Interface Rationals. + (line 76) +* mpq_class::get_str: C++ Interface Rationals. + (line 52) +* mpq_class::mpq_class: C++ Interface Rationals. + (line 9) +* mpq_class::mpq_class <1>: C++ Interface Rationals. + (line 10) +* mpq_class::mpq_class <2>: C++ Interface Rationals. + (line 21) +* mpq_class::mpq_class <3>: C++ Interface Rationals. + (line 26) +* mpq_class::mpq_class <4>: C++ Interface Rationals. + (line 28) +* mpq_class::set_str: C++ Interface Rationals. + (line 54) +* mpq_class::set_str <1>: C++ Interface Rationals. + (line 55) +* mpq_class::swap: C++ Interface Rationals. + (line 58) +* mpq_clear: Initializing Rationals. + (line 15) +* mpq_clears: Initializing Rationals. + (line 19) +* mpq_cmp: Comparing Rationals. (line 6) +* mpq_cmp_si: Comparing Rationals. (line 16) +* mpq_cmp_ui: Comparing Rationals. (line 14) +* mpq_cmp_z: Comparing Rationals. (line 7) +* mpq_denref: Applying Integer Functions. + (line 16) +* mpq_div: Rational Arithmetic. (line 22) +* mpq_div_2exp: Rational Arithmetic. (line 26) +* mpq_equal: Comparing Rationals. (line 33) +* mpq_get_d: Rational Conversions. + (line 6) +* mpq_get_den: Applying Integer Functions. + (line 24) +* mpq_get_num: Applying Integer Functions. + (line 23) +* mpq_get_str: Rational Conversions. + (line 21) +* mpq_init: Initializing Rationals. + (line 6) +* mpq_inits: Initializing Rationals. + (line 11) +* mpq_inp_str: I/O of Rationals. (line 32) +* mpq_inv: Rational Arithmetic. (line 36) +* mpq_mul: Rational Arithmetic. (line 14) +* mpq_mul_2exp: Rational Arithmetic. (line 18) +* mpq_neg: Rational Arithmetic. (line 30) +* mpq_numref: Applying Integer Functions. + (line 15) +* mpq_out_str: I/O of Rationals. (line 17) +* mpq_ptr: Nomenclature and Types. + (line 55) +* mpq_set: Initializing Rationals. + (line 23) +* mpq_set_d: Rational Conversions. + (line 16) +* mpq_set_den: Applying Integer Functions. + (line 26) +* mpq_set_f: Rational Conversions. + (line 17) +* mpq_set_num: Applying Integer Functions. + (line 25) +* mpq_set_si: Initializing Rationals. + (line 29) +* mpq_set_str: Initializing Rationals. + (line 35) +* mpq_set_ui: Initializing Rationals. + (line 27) +* mpq_set_z: Initializing Rationals. + (line 24) +* mpq_sgn: Comparing Rationals. (line 27) +* mpq_srcptr: Nomenclature and Types. + (line 55) +* mpq_sub: Rational Arithmetic. (line 10) +* mpq_swap: Initializing Rationals. + (line 54) +* mpq_t: Nomenclature and Types. + (line 16) +* mpz_2fac_ui: Number Theoretic Functions. + (line 122) +* mpz_abs: Integer Arithmetic. (line 44) +* mpz_add: Integer Arithmetic. (line 6) +* mpz_addmul: Integer Arithmetic. (line 24) +* mpz_addmul_ui: Integer Arithmetic. (line 26) +* mpz_add_ui: Integer Arithmetic. (line 7) +* mpz_and: Integer Logic and Bit Fiddling. + (line 10) +* mpz_array_init: Integer Special Functions. + (line 9) +* mpz_bin_ui: Number Theoretic Functions. + (line 133) +* mpz_bin_uiui: Number Theoretic Functions. + (line 135) +* mpz_cdiv_q: Integer Division. (line 12) +* mpz_cdiv_qr: Integer Division. (line 14) +* mpz_cdiv_qr_ui: Integer Division. (line 21) +* mpz_cdiv_q_2exp: Integer Division. (line 26) +* mpz_cdiv_q_ui: Integer Division. (line 17) +* mpz_cdiv_r: Integer Division. (line 13) +* mpz_cdiv_r_2exp: Integer Division. (line 29) +* mpz_cdiv_r_ui: Integer Division. (line 19) +* mpz_cdiv_ui: Integer Division. (line 23) +* mpz_class: C++ Interface General. + (line 17) +* mpz_class::factorial: C++ Interface Integers. + (line 70) +* mpz_class::fibonacci: C++ Interface Integers. + (line 74) +* mpz_class::fits_sint_p: C++ Interface Integers. + (line 50) +* mpz_class::fits_slong_p: C++ Interface Integers. + (line 51) +* mpz_class::fits_sshort_p: C++ Interface Integers. + (line 52) +* mpz_class::fits_uint_p: C++ Interface Integers. + (line 54) +* mpz_class::fits_ulong_p: C++ Interface Integers. + (line 55) +* mpz_class::fits_ushort_p: C++ Interface Integers. + (line 56) +* mpz_class::get_d: C++ Interface Integers. + (line 58) +* mpz_class::get_mpz_t: C++ Interface General. + (line 63) +* mpz_class::get_si: C++ Interface Integers. + (line 59) +* mpz_class::get_str: C++ Interface Integers. + (line 60) +* mpz_class::get_ui: C++ Interface Integers. + (line 61) +* mpz_class::mpz_class: C++ Interface Integers. + (line 6) +* mpz_class::mpz_class <1>: C++ Interface Integers. + (line 14) +* mpz_class::mpz_class <2>: C++ Interface Integers. + (line 19) +* mpz_class::mpz_class <3>: C++ Interface Integers. + (line 21) +* mpz_class::primorial: C++ Interface Integers. + (line 72) +* mpz_class::set_str: C++ Interface Integers. + (line 63) +* mpz_class::set_str <1>: C++ Interface Integers. + (line 64) +* mpz_class::swap: C++ Interface Integers. + (line 77) +* mpz_clear: Initializing Integers. + (line 48) +* mpz_clears: Initializing Integers. + (line 52) +* mpz_clrbit: Integer Logic and Bit Fiddling. + (line 54) +* mpz_cmp: Integer Comparisons. (line 6) +* mpz_cmpabs: Integer Comparisons. (line 17) +* mpz_cmpabs_d: Integer Comparisons. (line 18) +* mpz_cmpabs_ui: Integer Comparisons. (line 19) +* mpz_cmp_d: Integer Comparisons. (line 7) +* mpz_cmp_si: Integer Comparisons. (line 8) +* mpz_cmp_ui: Integer Comparisons. (line 9) +* mpz_com: Integer Logic and Bit Fiddling. + (line 19) +* mpz_combit: Integer Logic and Bit Fiddling. + (line 57) +* mpz_congruent_2exp_p: Integer Division. (line 148) +* mpz_congruent_p: Integer Division. (line 144) +* mpz_congruent_ui_p: Integer Division. (line 146) +* mpz_divexact: Integer Division. (line 122) +* mpz_divexact_ui: Integer Division. (line 123) +* mpz_divisible_2exp_p: Integer Division. (line 135) +* mpz_divisible_p: Integer Division. (line 132) +* mpz_divisible_ui_p: Integer Division. (line 133) +* mpz_even_p: Miscellaneous Integer Functions. + (line 17) +* mpz_export: Integer Import and Export. + (line 43) +* mpz_fac_ui: Number Theoretic Functions. + (line 121) +* mpz_fdiv_q: Integer Division. (line 33) +* mpz_fdiv_qr: Integer Division. (line 35) +* mpz_fdiv_qr_ui: Integer Division. (line 42) +* mpz_fdiv_q_2exp: Integer Division. (line 47) +* mpz_fdiv_q_ui: Integer Division. (line 38) +* mpz_fdiv_r: Integer Division. (line 34) +* mpz_fdiv_r_2exp: Integer Division. (line 50) +* mpz_fdiv_r_ui: Integer Division. (line 40) +* mpz_fdiv_ui: Integer Division. (line 44) +* mpz_fib2_ui: Number Theoretic Functions. + (line 143) +* mpz_fib_ui: Number Theoretic Functions. + (line 142) +* mpz_fits_sint_p: Miscellaneous Integer Functions. + (line 9) +* mpz_fits_slong_p: Miscellaneous Integer Functions. + (line 7) +* mpz_fits_sshort_p: Miscellaneous Integer Functions. + (line 11) +* mpz_fits_uint_p: Miscellaneous Integer Functions. + (line 8) +* mpz_fits_ulong_p: Miscellaneous Integer Functions. + (line 6) +* mpz_fits_ushort_p: Miscellaneous Integer Functions. + (line 10) +* mpz_gcd: Number Theoretic Functions. + (line 38) +* mpz_gcdext: Number Theoretic Functions. + (line 54) +* mpz_gcd_ui: Number Theoretic Functions. + (line 44) +* mpz_getlimbn: Integer Special Functions. + (line 22) +* mpz_get_d: Converting Integers. (line 26) +* mpz_get_d_2exp: Converting Integers. (line 34) +* mpz_get_si: Converting Integers. (line 17) +* mpz_get_str: Converting Integers. (line 46) +* mpz_get_ui: Converting Integers. (line 10) +* mpz_hamdist: Integer Logic and Bit Fiddling. + (line 28) +* mpz_import: Integer Import and Export. + (line 9) +* mpz_init: Initializing Integers. + (line 25) +* mpz_init2: Initializing Integers. + (line 32) +* mpz_inits: Initializing Integers. + (line 28) +* mpz_init_set: Simultaneous Integer Init & Assign. + (line 26) +* mpz_init_set_d: Simultaneous Integer Init & Assign. + (line 29) +* mpz_init_set_si: Simultaneous Integer Init & Assign. + (line 28) +* mpz_init_set_str: Simultaneous Integer Init & Assign. + (line 33) +* mpz_init_set_ui: Simultaneous Integer Init & Assign. + (line 27) +* mpz_inp_raw: I/O of Integers. (line 61) +* mpz_inp_str: I/O of Integers. (line 30) +* mpz_invert: Number Theoretic Functions. + (line 81) +* mpz_ior: Integer Logic and Bit Fiddling. + (line 13) +* mpz_jacobi: Number Theoretic Functions. + (line 91) +* mpz_kronecker: Number Theoretic Functions. + (line 99) +* mpz_kronecker_si: Number Theoretic Functions. + (line 100) +* mpz_kronecker_ui: Number Theoretic Functions. + (line 101) +* mpz_lcm: Number Theoretic Functions. + (line 74) +* mpz_lcm_ui: Number Theoretic Functions. + (line 75) +* mpz_legendre: Number Theoretic Functions. + (line 94) +* mpz_limbs_finish: Integer Special Functions. + (line 47) +* mpz_limbs_modify: Integer Special Functions. + (line 40) +* mpz_limbs_read: Integer Special Functions. + (line 34) +* mpz_limbs_write: Integer Special Functions. + (line 39) +* mpz_lucnum2_ui: Number Theoretic Functions. + (line 154) +* mpz_lucnum_ui: Number Theoretic Functions. + (line 153) +* mpz_mfac_uiui: Number Theoretic Functions. + (line 123) +* mpz_mod: Integer Division. (line 112) +* mpz_mod_ui: Integer Division. (line 113) +* mpz_mul: Integer Arithmetic. (line 18) +* mpz_mul_2exp: Integer Arithmetic. (line 36) +* mpz_mul_si: Integer Arithmetic. (line 19) +* mpz_mul_ui: Integer Arithmetic. (line 20) +* mpz_neg: Integer Arithmetic. (line 41) +* mpz_nextprime: Number Theoretic Functions. + (line 22) +* mpz_odd_p: Miscellaneous Integer Functions. + (line 16) +* mpz_out_raw: I/O of Integers. (line 45) +* mpz_out_str: I/O of Integers. (line 17) +* mpz_perfect_power_p: Integer Roots. (line 27) +* mpz_perfect_square_p: Integer Roots. (line 36) +* mpz_popcount: Integer Logic and Bit Fiddling. + (line 22) +* mpz_powm: Integer Exponentiation. + (line 6) +* mpz_powm_sec: Integer Exponentiation. + (line 16) +* mpz_powm_ui: Integer Exponentiation. + (line 8) +* mpz_pow_ui: Integer Exponentiation. + (line 29) +* mpz_prevprime: Number Theoretic Functions. + (line 25) +* mpz_primorial_ui: Number Theoretic Functions. + (line 129) +* mpz_probab_prime_p: Number Theoretic Functions. + (line 6) +* mpz_ptr: Nomenclature and Types. + (line 55) +* mpz_random: Integer Random Numbers. + (line 41) +* mpz_random2: Integer Random Numbers. + (line 50) +* mpz_realloc2: Initializing Integers. + (line 56) +* mpz_remove: Number Theoretic Functions. + (line 115) +* mpz_roinit_n: Integer Special Functions. + (line 67) +* MPZ_ROINIT_N: Integer Special Functions. + (line 83) +* mpz_root: Integer Roots. (line 6) +* mpz_rootrem: Integer Roots. (line 12) +* mpz_rrandomb: Integer Random Numbers. + (line 29) +* mpz_scan0: Integer Logic and Bit Fiddling. + (line 35) +* mpz_scan1: Integer Logic and Bit Fiddling. + (line 37) +* mpz_set: Assigning Integers. (line 9) +* mpz_setbit: Integer Logic and Bit Fiddling. + (line 51) +* mpz_set_d: Assigning Integers. (line 12) +* mpz_set_f: Assigning Integers. (line 14) +* mpz_set_q: Assigning Integers. (line 13) +* mpz_set_si: Assigning Integers. (line 11) +* mpz_set_str: Assigning Integers. (line 20) +* mpz_set_ui: Assigning Integers. (line 10) +* mpz_sgn: Integer Comparisons. (line 27) +* mpz_size: Integer Special Functions. + (line 30) +* mpz_sizeinbase: Miscellaneous Integer Functions. + (line 22) +* mpz_si_kronecker: Number Theoretic Functions. + (line 102) +* mpz_sqrt: Integer Roots. (line 17) +* mpz_sqrtrem: Integer Roots. (line 20) +* mpz_srcptr: Nomenclature and Types. + (line 55) +* mpz_sub: Integer Arithmetic. (line 11) +* mpz_submul: Integer Arithmetic. (line 30) +* mpz_submul_ui: Integer Arithmetic. (line 32) +* mpz_sub_ui: Integer Arithmetic. (line 12) +* mpz_swap: Assigning Integers. (line 36) +* mpz_t: Nomenclature and Types. + (line 6) +* mpz_tdiv_q: Integer Division. (line 54) +* mpz_tdiv_qr: Integer Division. (line 56) +* mpz_tdiv_qr_ui: Integer Division. (line 63) +* mpz_tdiv_q_2exp: Integer Division. (line 68) +* mpz_tdiv_q_ui: Integer Division. (line 59) +* mpz_tdiv_r: Integer Division. (line 55) +* mpz_tdiv_r_2exp: Integer Division. (line 71) +* mpz_tdiv_r_ui: Integer Division. (line 61) +* mpz_tdiv_ui: Integer Division. (line 65) +* mpz_tstbit: Integer Logic and Bit Fiddling. + (line 60) +* mpz_ui_kronecker: Number Theoretic Functions. + (line 103) +* mpz_ui_pow_ui: Integer Exponentiation. + (line 31) +* mpz_ui_sub: Integer Arithmetic. (line 14) +* mpz_urandomb: Integer Random Numbers. + (line 12) +* mpz_urandomm: Integer Random Numbers. + (line 21) +* mpz_xor: Integer Logic and Bit Fiddling. + (line 16) +* mp_bitcnt_t: Nomenclature and Types. + (line 42) +* mp_bits_per_limb: Useful Macros and Constants. + (line 7) +* mp_exp_t: Nomenclature and Types. + (line 27) +* mp_get_memory_functions: Custom Allocation. (line 86) +* mp_limb_t: Nomenclature and Types. + (line 31) +* mp_set_memory_functions: Custom Allocation. (line 14) +* mp_size_t: Nomenclature and Types. + (line 37) +* operator"": C++ Interface Integers. + (line 29) +* operator"" <1>: C++ Interface Rationals. + (line 36) +* operator"" <2>: C++ Interface Floats. + (line 55) +* operator%: C++ Interface Integers. + (line 34) +* operator/: C++ Interface Integers. + (line 33) +* operator<<: C++ Formatted Output. + (line 10) +* operator<< <1>: C++ Formatted Output. + (line 19) +* operator<< <2>: C++ Formatted Output. + (line 32) +* operator>>: C++ Formatted Input. (line 10) +* operator>> <1>: C++ Formatted Input. (line 13) +* operator>> <2>: C++ Formatted Input. (line 24) +* operator>> <3>: C++ Interface Rationals. + (line 86) +* primorial: C++ Interface Integers. + (line 73) +* sgn: C++ Interface Integers. + (line 65) +* sgn <1>: C++ Interface Rationals. + (line 56) +* sgn <2>: C++ Interface Floats. + (line 106) +* sqrt: C++ Interface Integers. + (line 66) +* sqrt <1>: C++ Interface Floats. + (line 107) +* swap: C++ Interface Integers. + (line 78) +* swap <1>: C++ Interface Rationals. + (line 59) +* swap <2>: C++ Interface Floats. + (line 110) +* trunc: C++ Interface Floats. + (line 111) + |