--- /dev/null
+This is ../../gmp/doc/gmp.info, produced by makeinfo version 4.8 from
+../../gmp/doc/gmp.texi.
+
+ This manual describes how to install and use the GNU multiple
+precision arithmetic library, version 5.0.1.
+
+ Copyright 1991, 1993, 1994, 1995, 1996, 1997, 1998, 1999, 2000,
+2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010 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
+
+\1f
+File: gmp.info, Node: Powering Algorithms, Next: Root Extraction Algorithms, Prev: Greatest Common Divisor Algorithms, Up: Algorithms
+
+16.4 Powering Algorithms
+========================
+
+* Menu:
+
+* Normal Powering Algorithm::
+* Modular Powering Algorithm::
+
+\1f
+File: gmp.info, Node: Normal Powering Algorithm, Next: Modular Powering Algorithm, Prev: Powering Algorithms, Up: Powering Algorithms
+
+16.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.
+
+\1f
+File: gmp.info, Node: Modular Powering Algorithm, Prev: Normal Powering Algorithm, Up: Powering Algorithms
+
+16.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 squares 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::).
+
+\1f
+File: gmp.info, Node: Root Extraction Algorithms, Next: Radix Conversion Algorithms, Prev: Powering Algorithms, Up: Algorithms
+
+16.5 Root Extraction Algorithms
+===============================
+
+* Menu:
+
+* Square Root Algorithm::
+* Nth Root Algorithm::
+* Perfect Square Algorithm::
+* Perfect Power Algorithm::
+
+\1f
+File: gmp.info, Node: Square Root Algorithm, Next: Nth Root Algorithm, Prev: Root Extraction Algorithms, Up: Root Extraction Algorithms
+
+16.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.
+
+\1f
+File: gmp.info, Node: Nth Root Algorithm, Next: Perfect Square Algorithm, Prev: Square Root Algorithm, Up: Root Extraction Algorithms
+
+16.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.
+
+\1f
+File: gmp.info, Node: Perfect Square Algorithm, Next: Perfect Power Algorithm, Prev: Nth Root Algorithm, Up: Root Extraction Algorithms
+
+16.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 (ie. 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.
+
+\1f
+File: gmp.info, Node: Perfect Power Algorithm, Prev: Perfect Square Algorithm, Up: Root Extraction Algorithms
+
+16.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.
+
+\1f
+File: gmp.info, Node: Radix Conversion Algorithms, Next: Other Algorithms, Prev: Root Extraction Algorithms, Up: Algorithms
+
+16.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::
+
+\1f
+File: gmp.info, Node: Binary to Radix, Next: Radix to Binary, Prev: Radix Conversion Algorithms, Up: Radix Conversion Algorithms
+
+16.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.
+
+ `mpf_get_str' doesn't currently use the algorithm described here, it
+multiplies or divides by a power of b to move the radix point to the
+just above the highest non-zero digit (or at worst one above that
+location), then multiplies by b^n to bring out digits. This is O(N^2)
+and is certainly not optimal.
+
+ 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, ie. 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.
+
+\1f
+File: gmp.info, Node: Radix to Binary, Prev: Binary to Radix, Up: Radix Conversion Algorithms
+
+16.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).
+
+\1f
+File: gmp.info, Node: Other Algorithms, Next: Assembly Coding, Prev: Radix Conversion Algorithms, Up: Algorithms
+
+16.7 Other Algorithms
+=====================
+
+* Menu:
+
+* Prime Testing Algorithm::
+* Factorial Algorithm::
+* Binomial Coefficients Algorithm::
+* Fibonacci Numbers Algorithm::
+* Lucas Numbers Algorithm::
+* Random Number Algorithms::
+
+\1f
+File: gmp.info, Node: Prime Testing Algorithm, Next: Factorial Algorithm, Prev: Other Algorithms, Up: Other Algorithms
+
+16.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.
+
+\1f
+File: gmp.info, Node: Factorial Algorithm, Next: Binomial Coefficients Algorithm, Prev: Prime Testing Algorithm, Up: Other Algorithms
+
+16.7.2 Factorial
+----------------
+
+Factorials are calculated by a combination of removal of twos,
+powering, and binary splitting. The procedure can be best illustrated
+with an example,
+
+ 23! = 1.2.3.4.5.6.7.8.9.10.11.12.13.14.15.16.17.18.19.20.21.22.23
+
+has factors of two removed,
+
+ 23! = 2^19.1.1.3.1.5.3.7.1.9.5.11.3.13.7.15.1.17.9.19.5.21.11.23
+
+and the resulting terms collected up according to their multiplicity,
+
+ 23! = 2^19.(3.5)^3.(7.9.11)^2.(13.15.17.19.21.23)
+
+ Each sequence such as 13.15.17.19.21.23 is evaluated by splitting
+into every second term, as for instance (13.17.21).(15.19.23), and the
+same recursively on each half. This is implemented iteratively using
+some bit twiddling.
+
+ 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.
+
+ Splitting into subsequences of every second term keeps the resulting
+products more nearly equal in size than would the simpler approach of
+say taking the first half and second half of the sequence. Nearly
+equal products are more efficient for the current multiply
+implementation.
+
+\1f
+File: gmp.info, Node: Binomial Coefficients Algorithm, Next: Fibonacci Numbers Algorithm, Prev: Factorial Algorithm, Up: Other Algorithms
+
+16.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.
+
+\1f
+File: gmp.info, Node: Fibonacci Numbers Algorithm, Next: Lucas Numbers Algorithm, Prev: Binomial Coefficients Algorithm, Up: Other Algorithms
+
+16.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.
+
+\1f
+File: gmp.info, Node: Lucas Numbers Algorithm, Next: Random Number Algorithms, Prev: Fibonacci Numbers Algorithm, Up: Other Algorithms
+
+16.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
+
+\1f
+File: gmp.info, Node: Random Number Algorithms, Prev: Lucas Numbers Algorithm, Up: Other Algorithms
+
+16.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, a 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.
+
+\1f
+File: gmp.info, Node: Assembly Coding, Prev: Other Algorithms, Up: Algorithms
+
+16.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::
+
+\1f
+File: gmp.info, Node: Assembly Code Organisation, Next: Assembly Basics, Prev: Assembly Coding, Up: Assembly Coding
+
+16.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.
+
+\1f
+File: gmp.info, Node: Assembly Basics, Next: Assembly Carry Propagation, Prev: Assembly Code Organisation, Up: Assembly Coding
+
+16.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.
+
+\1f
+File: gmp.info, Node: Assembly Carry Propagation, Next: Assembly Cache Handling, Prev: Assembly Basics, Up: Assembly Coding
+
+16.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.
+
+\1f
+File: gmp.info, Node: Assembly Cache Handling, Next: Assembly Functional Units, Prev: Assembly Carry Propagation, Up: Assembly Coding
+
+16.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.
+
+\1f
+File: gmp.info, Node: Assembly Functional Units, Next: Assembly Floating Point, Prev: Assembly Cache Handling, Up: Assembly Coding
+
+16.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 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 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.
+
+\1f
+File: gmp.info, Node: Assembly Floating Point, Next: Assembly SIMD Instructions, Prev: Assembly Functional Units, Up: Assembly Coding
+
+16.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).
+
+\1f
+File: gmp.info, Node: Assembly SIMD Instructions, Next: Assembly Software Pipelining, Prev: Assembly Floating Point, Up: Assembly Coding
+
+16.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'.
+
+\1f
+File: gmp.info, Node: Assembly Software Pipelining, Next: Assembly Loop Unrolling, Prev: Assembly SIMD Instructions, Up: Assembly Coding
+
+16.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::).
+
+\1f
+File: gmp.info, Node: Assembly Loop Unrolling, Next: Assembly Writing Guide, Prev: Assembly Software Pipelining, Up: Assembly Coding
+
+16.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.
+
+\1f
+File: gmp.info, Node: Assembly Writing Guide, Prev: Assembly Loop Unrolling, Up: Assembly Coding
+
+16.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.
+
+\1f
+File: gmp.info, Node: Internals, Next: Contributors, Prev: Algorithms, Up: Top
+
+17 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::
+
+\1f
+File: gmp.info, Node: Integer Internals, Next: Rational Internals, Prev: Internals, Up: Internals
+
+17.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 unused.
+
+`_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 limb allocated, so for
+ instance `mpz_set_ui' never needs to reallocate, and `mpz_get_ui'
+ can fetch `_mp_d[0]' unconditionally (though its value is then
+ only wanted if `_mp_size' is non-zero).
+
+`_mp_alloc'
+ `_mp_alloc' is the number of limbs currently allocated at `_mp_d',
+ and naturally `_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.
+
+ The various bitwise logical functions like `mpz_and' behave as if
+negative values were twos 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 setup 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.
+
+\1f
+File: gmp.info, Node: Rational Internals, Next: Float Internals, Prev: Integer Internals, Up: Internals
+
+17.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.
+
+\1f
+File: gmp.info, Node: Float Internals, Next: Raw Output Internals, Prev: Rational Internals, Up: Internals
+
+17.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 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.
+
+\1f
+File: gmp.info, Node: Raw Output Internals, Next: C++ Interface Internals, Prev: Float Internals, Up: Internals
+
+17.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 twos 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'.
+
+\1f
+File: gmp.info, Node: C++ Interface Internals, Prev: Raw Output Internals, Up: Internals
+
+17.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, mpf_t g, 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'.
+
+\1f
+File: gmp.info, Node: Contributors, Next: References, Prev: Internals, Up: Top
+
+Appendix A Contributors
+***********************
+
+Torbjo"rn Granlund wrote the original GMP library and is still the main
+developer. Code not explicitly attributed to others, was contributed by
+Torbjo"rn. Several other individuals and organizations have contributed
+GMP. Here is a list in chronological order on first contribution:
+
+ Gunnar Sjo"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
+Scho"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 Torbjo"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 Mo"ller wrote the sub-quadratic GCD and extended GCD code, the
+quadratic Hensel division code, and (with Torbjo"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.
+
+ 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 and
+mpn_mullo_n. Marco also wrote the functions mpn_invert and
+mpn_invertappr.
+
+ 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'.
+
+ Martin Boij wrote `mpn_perfect_power_p'.
+
+ (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, were
+supported in part by the ESPRIT-BRA (Basic Research Activities) 6846
+project POSSO (POlynomial System SOlving).
+
+ The development of GMP 2, 3, and 4 was supported in part by the IDA
+Center for Computing Sciences.
+
+ Thanks go to Hans Thorsen for donating an SGI system for the GMP
+test system environment.
+
+\1f
+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.
+ `http://math.dartmouth.edu/~carlp/'
+
+ * Henri Cohen, "A Course in Computational Algebraic Number Theory",
+ Graduate Texts in Mathematics number 138, Springer-Verlag, 1993.
+ `http://www.math.u-bordeaux.fr/~cohen/'
+
+ * Donald E. Knuth, "The Art of Computer Programming", volume 2,
+ "Seminumerical Algorithms", 3rd edition, Addison-Wesley, 1998.
+ `http://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 `http://gcc.gnu.org/onlinedocs/', and in the GCC
+ package `ftp://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 2001, `http://www.inria.fr/rrrt/rr-4475.html'
+
+ * Christoph Burnikel and Joachim Ziegler, "Fast Recursive Division",
+ Max-Planck-Institut fuer Informatik Research Report MPI-I-98-1-022,
+ `http://data.mpi-sb.mpg.de/internet/reports.nsf/NumberView/1998-1-022'
+
+ * Torbjo"rn Granlund and Peter L. Montgomery, "Division by Invariant
+ Integers using Multiplication", in Proceedings of the SIGPLAN
+ PLDI'94 Conference, June 1994. Also available
+ `ftp://ftp.cwi.nl/pub/pmontgom/divcnst.psa4.gz' (and .psl.gz).
+
+ * Niels Mo"ller and Torbjo"rn Granlund, "Improved division by
+ invariant integers", to appear.
+
+ * Torbjo"rn Granlund and Niels Mo"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.ps.gz'
+ (or .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 Mo"ller, "On Scho"nhage's algorithm and subquadratic integer
+ GCD computation", in Mathematics of Computation, volume 77,
+ January 2008, pp. 589-607.
+
+ * Peter L. Montgomery, "Modular Multiplication Without Trial
+ Division", in Mathematics of Computation, volume 44, number 170,
+ April 1985.
+
+ * Arnold Scho"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, `http://www.inria.fr/rrrt/rr-3805.html'
+
+ * Paul Zimmermann, "A Proof of GMP Fast Division and Square Root
+ Implementations",
+ `http://www.loria.fr/~zimmerma/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.
+
+\1f
+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 (C) 2000, 2001, 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
+ `http://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.
+
+\1f
+File: gmp.info, Node: Concept Index, Next: Function Index, Prev: GNU Free Documentation License, Up: Top
+
+Concept Index
+*************
+
+\0\b[index\0\b]
+* Menu:
+
+* #include: Headers and Libraries.
+ (line 6)
+* --build: Build Options. (line 52)
+* --disable-fft: Build Options. (line 317)
+* --disable-shared: Build Options. (line 45)
+* --disable-static: Build Options. (line 45)
+* --enable-alloca: Build Options. (line 278)
+* --enable-assert: Build Options. (line 327)
+* --enable-cxx: Build Options. (line 230)
+* --enable-fat: Build Options. (line 164)
+* --enable-mpbsd: Build Options. (line 322)
+* --enable-profiling <1>: Profiling. (line 6)
+* --enable-profiling: Build Options. (line 331)
+* --exec-prefix: Build Options. (line 32)
+* --host: Build Options. (line 66)
+* --prefix: Build Options. (line 32)
+* -finstrument-functions: Profiling. (line 66)
+* 2exp functions: Efficiency. (line 43)
+* 68000: Notes for Particular Systems.
+ (line 80)
+* 80x86: Notes for Particular Systems.
+ (line 126)
+* ABI <1>: Build Options. (line 171)
+* ABI: ABI and ISA. (line 6)
+* About this manual: Introduction to GMP. (line 58)
+* AC_CHECK_LIB: Autoconf. (line 11)
+* AIX <1>: ABI and ISA. (line 184)
+* AIX <2>: Notes for Particular Systems.
+ (line 7)
+* AIX: ABI and ISA. (line 169)
+* Algorithms: Algorithms. (line 6)
+* alloca: Build Options. (line 278)
+* Allocation of memory: Custom Allocation. (line 6)
+* AMD64: ABI and ISA. (line 44)
+* Anonymous FTP of latest version: Introduction to GMP. (line 38)
+* Application Binary Interface: ABI and ISA. (line 6)
+* Arithmetic functions <1>: Float Arithmetic. (line 6)
+* Arithmetic functions <2>: Integer Arithmetic. (line 6)
+* Arithmetic functions: Rational 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 <1>: Debugging. (line 79)
+* Assertion checking: Build Options. (line 327)
+* Assignment functions <1>: Assigning Floats. (line 6)
+* Assignment functions <2>: Initializing Rationals.
+ (line 6)
+* Assignment functions <3>: Simultaneous Integer Init & Assign.
+ (line 6)
+* Assignment functions <4>: Simultaneous Float Init & Assign.
+ (line 6)
+* Assignment functions: Assigning Integers. (line 6)
+* Autoconf: Autoconf. (line 6)
+* Basics: GMP Basics. (line 6)
+* Berkeley MP compatible functions <1>: Build Options. (line 322)
+* Berkeley MP compatible functions: BSD Compatible Functions.
+ (line 6)
+* Binomial coefficient algorithm: Binomial Coefficients Algorithm.
+ (line 6)
+* Binomial coefficient functions: Number Theoretic Functions.
+ (line 100)
+* 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 38)
+* Bit shift left: Integer Arithmetic. (line 35)
+* Bit shift right: Integer Division. (line 53)
+* Bits per limb: Useful Macros and Constants.
+ (line 7)
+* BSD MP compatible functions <1>: Build Options. (line 322)
+* BSD MP compatible functions: BSD Compatible Functions.
+ (line 6)
+* 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 52)
+* Building GMP: Installing GMP. (line 6)
+* Bus error: Debugging. (line 7)
+* C compiler: Build Options. (line 182)
+* C++ compiler: Build Options. (line 254)
+* 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 230)
+* CC: Build Options. (line 182)
+* CC_FOR_BUILD: Build Options. (line 217)
+* CFLAGS: Build Options. (line 182)
+* Checker: Debugging. (line 115)
+* checkergcc: Debugging. (line 122)
+* Code organisation: Assembly Code Organisation.
+ (line 6)
+* Compaq C++: Notes for Particular Systems.
+ (line 25)
+* Comparison functions <1>: Integer Comparisons. (line 6)
+* Comparison functions <2>: Comparing Rationals. (line 6)
+* Comparison functions: 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 29)
+* Congruence functions: Integer Division. (line 124)
+* 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 <1>: Converting Integers. (line 6)
+* Conversion functions <2>: Converting Floats. (line 6)
+* Conversion functions: Rational Conversions.
+ (line 6)
+* Copying conditions: Copying. (line 6)
+* CPPFLAGS: Build Options. (line 208)
+* CPU types <1>: Introduction to GMP. (line 24)
+* CPU types: Build Options. (line 108)
+* Cross compiling: Build Options. (line 66)
+* Custom allocation: Custom Allocation. (line 6)
+* CXX: Build Options. (line 254)
+* CXXFLAGS: Build Options. (line 254)
+* Cygwin: Notes for Particular Systems.
+ (line 43)
+* 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 29)
+* Divisibility functions: Integer Division. (line 124)
+* Divisibility testing: Efficiency. (line 91)
+* Division algorithms: Division Algorithms. (line 6)
+* Division functions <1>: Rational Arithmetic. (line 22)
+* Division functions <2>: Integer Division. (line 6)
+* Division functions: Float Arithmetic. (line 33)
+* DJGPP <1>: Notes for Particular Systems.
+ (line 43)
+* DJGPP: Known Build Problems.
+ (line 18)
+* DLLs: Notes for Particular Systems.
+ (line 56)
+* DocBook: Build Options. (line 354)
+* Documentation formats: Build Options. (line 347)
+* Documentation license: GNU Free Documentation License.
+ (line 6)
+* DVI: Build Options. (line 350)
+* Efficiency: Efficiency. (line 6)
+* Emacs: Emacs. (line 6)
+* Exact division functions: Integer Division. (line 102)
+* Exact remainder: Exact Remainder. (line 6)
+* Example programs: Demonstration Programs.
+ (line 6)
+* Exec prefix: Build Options. (line 32)
+* Execution profiling <1>: Profiling. (line 6)
+* Execution profiling: Build Options. (line 331)
+* Exponentiation functions <1>: Integer Exponentiation.
+ (line 6)
+* Exponentiation functions: Float Arithmetic. (line 41)
+* Export: Integer Import and Export.
+ (line 45)
+* Expression parsing demo: Demonstration Programs.
+ (line 18)
+* Extended GCD: Number Theoretic Functions.
+ (line 45)
+* Factor removal functions: Number Theoretic Functions.
+ (line 90)
+* Factorial algorithm: Factorial Algorithm. (line 6)
+* Factorial functions: Number Theoretic Functions.
+ (line 95)
+* Factorization demo: Demonstration Programs.
+ (line 25)
+* Fast Fourier Transform: FFT Multiplication. (line 6)
+* Fat binary: Build Options. (line 164)
+* FFT multiplication <1>: FFT Multiplication. (line 6)
+* FFT multiplication: Build Options. (line 317)
+* Fibonacci number algorithm: Fibonacci Numbers Algorithm.
+ (line 6)
+* Fibonacci sequence functions: Number Theoretic Functions.
+ (line 108)
+* Float arithmetic functions: Float Arithmetic. (line 6)
+* Float assignment functions <1>: Simultaneous Float Init & Assign.
+ (line 6)
+* Float assignment functions: Assigning Floats. (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 <1>: Simultaneous Float Init & Assign.
+ (line 6)
+* Float initialization functions: Initializing Floats. (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 33)
+* 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)
+* frexp <1>: Converting Floats. (line 23)
+* frexp: Converting Integers. (line 42)
+* FTP of latest version: Introduction to GMP. (line 38)
+* Function classes: Function Classes. (line 6)
+* FunctionCheck: Profiling. (line 77)
+* GCC Checker: Debugging. (line 115)
+* GCD algorithms: Greatest Common Divisor Algorithms.
+ (line 6)
+* GCD extended: Number Theoretic Functions.
+ (line 45)
+* GCD functions: Number Theoretic Functions.
+ (line 30)
+* GDB: Debugging. (line 58)
+* Generic C: Build Options. (line 153)
+* GMP Perl module: Demonstration Programs.
+ (line 35)
+* 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 58)
+* 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 30)
+* Hardware floating point mode: Notes for Particular Systems.
+ (line 34)
+* Headers: Headers and Libraries.
+ (line 6)
+* Heap problems: Debugging. (line 24)
+* Home page: Introduction to GMP. (line 34)
+* Host system: Build Options. (line 66)
+* HP-UX: ABI and ISA. (line 107)
+* HPPA: ABI and ISA. (line 68)
+* I/O functions <1>: I/O of Integers. (line 6)
+* I/O functions <2>: I/O of Rationals. (line 6)
+* I/O functions: I/O of Floats. (line 6)
+* i386: Notes for Particular Systems.
+ (line 126)
+* IA-64: ABI and ISA. (line 107)
+* 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 <1>: Initializing Integers.
+ (line 6)
+* Initialization functions <2>: Initializing Rationals.
+ (line 6)
+* Initialization functions <3>: Random State Initialization.
+ (line 6)
+* Initialization functions <4>: Simultaneous Float Init & Assign.
+ (line 6)
+* Initialization functions <5>: Simultaneous Integer Init & Assign.
+ (line 6)
+* Initialization functions: Initializing Floats. (line 6)
+* Initializing and clearing: Efficiency. (line 21)
+* Input functions <1>: I/O of Integers. (line 6)
+* Input functions <2>: I/O of Rationals. (line 6)
+* Input functions <3>: I/O of Floats. (line 6)
+* Input functions: 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 <1>: Simultaneous Integer Init & Assign.
+ (line 6)
+* Integer assignment functions: Assigning Integers. (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 <1>: Simultaneous Integer Init & Assign.
+ (line 6)
+* Integer initialization functions: Initializing Integers.
+ (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 51)
+* Internals: Internals. (line 6)
+* Introduction: Introduction to GMP. (line 6)
+* Inverse modulo functions: Number Theoretic Functions.
+ (line 60)
+* IRIX <1>: Known Build Problems.
+ (line 38)
+* IRIX: ABI and ISA. (line 132)
+* 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 66)
+* Karatsuba multiplication: Karatsuba Multiplication.
+ (line 6)
+* Karatsuba square root algorithm: Square Root Algorithm.
+ (line 6)
+* Kronecker symbol functions: Number Theoretic Functions.
+ (line 78)
+* Language bindings: Language Bindings. (line 6)
+* Latest version of GMP: Introduction to GMP. (line 38)
+* LCM functions: Number Theoretic Functions.
+ (line 55)
+* Least common multiple functions: Number Theoretic Functions.
+ (line 55)
+* Legendre symbol functions: Number Theoretic Functions.
+ (line 69)
+* libgmp: Headers and Libraries.
+ (line 22)
+* libgmpxx: Headers and Libraries.
+ (line 27)
+* Libraries: Headers and Libraries.
+ (line 22)
+* Libtool: Headers and Libraries.
+ (line 33)
+* 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 32)
+* Linking: Headers and Libraries.
+ (line 22)
+* Logical functions: Integer Logic and Bit Fiddling.
+ (line 6)
+* Low-level functions: Low-level Functions. (line 6)
+* Lucas number algorithm: Lucas Numbers Algorithm.
+ (line 6)
+* Lucas number functions: Number Theoretic Functions.
+ (line 119)
+* MacOS X: Known Build Problems.
+ (line 51)
+* Mailing lists: Introduction to GMP. (line 45)
+* Malloc debugger: Debugging. (line 30)
+* Malloc problems: Debugging. (line 24)
+* 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 43)
+* MIPS: ABI and ISA. (line 132)
+* Miscellaneous float functions: Miscellaneous Float Functions.
+ (line 6)
+* Miscellaneous integer functions: Miscellaneous Integer Functions.
+ (line 6)
+* MMX: Notes for Particular Systems.
+ (line 132)
+* Modular inverse functions: Number Theoretic Functions.
+ (line 60)
+* Most significant bit: Miscellaneous Integer Functions.
+ (line 34)
+* mp.h: BSD Compatible Functions.
+ (line 21)
+* MPN_PATH: Build Options. (line 335)
+* MS Windows: Notes for Particular Systems.
+ (line 56)
+* MS-DOS: Notes for Particular Systems.
+ (line 43)
+* Multi-threading: Reentrancy. (line 6)
+* Multiplication algorithms: Multiplication Algorithms.
+ (line 6)
+* Nails: Low-level Functions. (line 478)
+* Native compilation: Build Options. (line 52)
+* 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 147)
+* Number theoretic functions: Number Theoretic Functions.
+ (line 6)
+* Numerator and denominator: Applying Integer Functions.
+ (line 6)
+* obstack output: Formatted Output Functions.
+ (line 81)
+* OpenBSD: Notes for Particular Systems.
+ (line 86)
+* Optimizing performance: Performance optimization.
+ (line 6)
+* ostream output: C++ Formatted Output.
+ (line 6)
+* Other languages: Language Bindings. (line 6)
+* Output functions <1>: I/O of Floats. (line 6)
+* Output functions <2>: I/O of Rationals. (line 6)
+* Output functions <3>: Formatted Output Functions.
+ (line 6)
+* Output functions: I/O of Integers. (line 6)
+* Packaged builds: Notes for Package Builds.
+ (line 6)
+* Parameter conventions: Parameter Conventions.
+ (line 6)
+* Parsing expressions demo: Demonstration Programs.
+ (line 21)
+* Particular systems: Notes for Particular Systems.
+ (line 6)
+* Past GMP versions: Compatibility with older versions.
+ (line 6)
+* PDF: Build Options. (line 350)
+* Perfect power algorithm: Perfect Power Algorithm.
+ (line 6)
+* Perfect power functions: Integer Roots. (line 27)
+* Perfect square algorithm: Perfect Square Algorithm.
+ (line 6)
+* Perfect square functions: Integer Roots. (line 36)
+* perl: Demonstration Programs.
+ (line 35)
+* Perl module: Demonstration Programs.
+ (line 35)
+* Postscript: Build Options. (line 350)
+* Power/PowerPC <1>: Known Build Problems.
+ (line 63)
+* Power/PowerPC: Notes for Particular Systems.
+ (line 92)
+* Powering algorithms: Powering Algorithms. (line 6)
+* Powering functions <1>: Float Arithmetic. (line 41)
+* Powering functions: Integer Exponentiation.
+ (line 6)
+* PowerPC: ABI and ISA. (line 167)
+* Precision of floats: Floating-point Functions.
+ (line 6)
+* Precision of hardware floating point: Notes for Particular Systems.
+ (line 34)
+* Prefix: Build Options. (line 32)
+* Prime testing algorithms: Prime Testing Algorithm.
+ (line 6)
+* Prime testing functions: Number Theoretic Functions.
+ (line 7)
+* 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 <1>: Integer Random Numbers.
+ (line 6)
+* Random number functions <2>: Miscellaneous Float Functions.
+ (line 27)
+* Random number functions: 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 113)
+* 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 27)
+* Raw output internals: Raw Output Internals.
+ (line 6)
+* Reallocations: Efficiency. (line 30)
+* Reentrancy: Reentrancy. (line 6)
+* References: References. (line 6)
+* Remove factor functions: Number Theoretic Functions.
+ (line 90)
+* 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 <1>: Float Arithmetic. (line 37)
+* Root extraction functions: Integer Roots. (line 6)
+* Root testing functions: Integer Roots. (line 36)
+* Rounding functions: Miscellaneous Float Functions.
+ (line 9)
+* Sample programs: Demonstration Programs.
+ (line 6)
+* Scan bit functions: Integer Logic and Bit Fiddling.
+ (line 38)
+* 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 51)
+* Shared library versioning: Notes for Package Builds.
+ (line 9)
+* Sign tests <1>: Float Comparison. (line 33)
+* Sign tests <2>: Integer Comparisons. (line 28)
+* Sign tests: Comparing Rationals. (line 27)
+* Size in digits: Miscellaneous Integer Functions.
+ (line 23)
+* Small operands: Efficiency. (line 7)
+* Solaris <1>: ABI and ISA. (line 201)
+* Solaris: Known Build Problems.
+ (line 78)
+* Sparc: Notes for Particular Systems.
+ (line 108)
+* Sparc V9: ABI and ISA. (line 201)
+* Special integer functions: Integer Special Functions.
+ (line 6)
+* Square root algorithm: Square Root Algorithm.
+ (line 6)
+* SSE2: Notes for Particular Systems.
+ (line 132)
+* Stack backtrace: Debugging. (line 50)
+* Stack overflow <1>: Debugging. (line 7)
+* Stack overflow: Build Options. (line 278)
+* Static linking: Efficiency. (line 14)
+* stdarg.h: Headers and Libraries.
+ (line 17)
+* stdio.h: Headers and Libraries.
+ (line 11)
+* Stripped libraries: Known Build Problems.
+ (line 28)
+* Sun: ABI and ISA. (line 201)
+* SunOS: Notes for Particular Systems.
+ (line 120)
+* Systems: Notes for Particular Systems.
+ (line 6)
+* Temporary memory: Build Options. (line 278)
+* Texinfo: Build Options. (line 347)
+* Text input/output: Efficiency. (line 153)
+* Thread safety: Reentrancy. (line 6)
+* Toom multiplication <1>: Other Multiplication.
+ (line 6)
+* Toom multiplication <2>: Toom 4-Way Multiplication.
+ (line 6)
+* Toom multiplication: Toom 3-Way 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 130)
+* Variable conventions: Variable Conventions.
+ (line 6)
+* Version number: Useful Macros and Constants.
+ (line 12)
+* Web page: Introduction to GMP. (line 34)
+* Windows: Notes for Particular Systems.
+ (line 56)
+* x86: Notes for Particular Systems.
+ (line 126)
+* x87: Notes for Particular Systems.
+ (line 34)
+* XML: Build Options. (line 354)
+
+\1f
+File: gmp.info, Node: Function Index, Prev: Concept Index, Up: Top
+
+Function and Type Index
+***********************
+
+\0\b[index\0\b]
+* Menu:
+
+* __GMP_CC: Useful Macros and Constants.
+ (line 23)
+* __GMP_CFLAGS: Useful Macros and Constants.
+ (line 24)
+* __GNU_MP_VERSION: Useful Macros and Constants.
+ (line 10)
+* __GNU_MP_VERSION_MINOR: Useful Macros and Constants.
+ (line 11)
+* __GNU_MP_VERSION_PATCHLEVEL: Useful Macros and Constants.
+ (line 12)
+* _mpz_realloc: Integer Special Functions.
+ (line 51)
+* abs <1>: C++ Interface Rationals.
+ (line 43)
+* abs <2>: C++ Interface Integers.
+ (line 42)
+* abs: C++ Interface Floats.
+ (line 70)
+* ceil: C++ Interface Floats.
+ (line 71)
+* cmp <1>: C++ Interface Floats.
+ (line 72)
+* cmp <2>: C++ Interface Rationals.
+ (line 44)
+* cmp <3>: C++ Interface Integers.
+ (line 44)
+* cmp: C++ Interface Rationals.
+ (line 45)
+* floor: C++ Interface Floats.
+ (line 80)
+* gcd: BSD Compatible Functions.
+ (line 82)
+* gmp_asprintf: Formatted Output Functions.
+ (line 65)
+* gmp_errno: Random State Initialization.
+ (line 55)
+* GMP_ERROR_INVALID_ARGUMENT: Random State Initialization.
+ (line 55)
+* GMP_ERROR_UNSUPPORTED_ARGUMENT: Random State Initialization.
+ (line 55)
+* gmp_fprintf: Formatted Output Functions.
+ (line 29)
+* gmp_fscanf: Formatted Input Functions.
+ (line 25)
+* GMP_LIMB_BITS: Low-level Functions. (line 508)
+* GMP_NAIL_BITS: Low-level Functions. (line 506)
+* GMP_NAIL_MASK: Low-level Functions. (line 516)
+* GMP_NUMB_BITS: Low-level Functions. (line 507)
+* GMP_NUMB_MASK: Low-level Functions. (line 517)
+* GMP_NUMB_MAX: Low-level Functions. (line 525)
+* gmp_obstack_printf: Formatted Output Functions.
+ (line 79)
+* gmp_obstack_vprintf: Formatted Output Functions.
+ (line 81)
+* gmp_printf: Formatted Output Functions.
+ (line 24)
+* GMP_RAND_ALG_DEFAULT: Random State Initialization.
+ (line 49)
+* GMP_RAND_ALG_LC: Random State Initialization.
+ (line 49)
+* gmp_randclass: C++ Interface Random Numbers.
+ (line 7)
+* gmp_randclass::get_f: C++ Interface Random Numbers.
+ (line 45)
+* gmp_randclass::get_z_bits: C++ Interface Random Numbers.
+ (line 39)
+* gmp_randclass::get_z_range: C++ Interface Random Numbers.
+ (line 42)
+* gmp_randclass::gmp_randclass: C++ Interface Random Numbers.
+ (line 13)
+* gmp_randclass::seed: C++ Interface Random Numbers.
+ (line 33)
+* gmp_randclear: Random State Initialization.
+ (line 62)
+* gmp_randinit: Random State Initialization.
+ (line 47)
+* gmp_randinit_default: Random State Initialization.
+ (line 7)
+* gmp_randinit_lc_2exp: Random State Initialization.
+ (line 18)
+* gmp_randinit_lc_2exp_size: Random State Initialization.
+ (line 32)
+* gmp_randinit_mt: Random State Initialization.
+ (line 13)
+* gmp_randinit_set: Random State Initialization.
+ (line 43)
+* gmp_randseed: Random State Seeding.
+ (line 7)
+* gmp_randseed_ui: Random State Seeding.
+ (line 9)
+* gmp_randstate_t: Nomenclature and Types.
+ (line 46)
+* gmp_scanf: Formatted Input Functions.
+ (line 21)
+* gmp_snprintf: Formatted Output Functions.
+ (line 46)
+* gmp_sprintf: Formatted Output Functions.
+ (line 34)
+* gmp_sscanf: Formatted Input Functions.
+ (line 29)
+* gmp_urandomb_ui: Random State Miscellaneous.
+ (line 8)
+* gmp_urandomm_ui: Random State Miscellaneous.
+ (line 14)
+* gmp_vasprintf: Formatted Output Functions.
+ (line 66)
+* gmp_version: Useful Macros and Constants.
+ (line 18)
+* gmp_vfprintf: Formatted Output Functions.
+ (line 30)
+* gmp_vfscanf: Formatted Input Functions.
+ (line 26)
+* gmp_vprintf: Formatted Output Functions.
+ (line 25)
+* gmp_vscanf: Formatted Input Functions.
+ (line 22)
+* gmp_vsnprintf: Formatted Output Functions.
+ (line 48)
+* gmp_vsprintf: Formatted Output Functions.
+ (line 35)
+* gmp_vsscanf: Formatted Input Functions.
+ (line 31)
+* hypot: C++ Interface Floats.
+ (line 81)
+* itom: BSD Compatible Functions.
+ (line 29)
+* madd: BSD Compatible Functions.
+ (line 43)
+* mcmp: BSD Compatible Functions.
+ (line 85)
+* mdiv: BSD Compatible Functions.
+ (line 53)
+* mfree: BSD Compatible Functions.
+ (line 105)
+* min: BSD Compatible Functions.
+ (line 89)
+* MINT: BSD Compatible Functions.
+ (line 21)
+* mout: BSD Compatible Functions.
+ (line 94)
+* move: BSD Compatible Functions.
+ (line 39)
+* 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 93)
+* mp_limb_t: Nomenclature and Types.
+ (line 31)
+* mp_set_memory_functions: Custom Allocation. (line 21)
+* mp_size_t: Nomenclature and Types.
+ (line 37)
+* mpf_abs: Float Arithmetic. (line 47)
+* mpf_add: Float Arithmetic. (line 7)
+* mpf_add_ui: Float Arithmetic. (line 9)
+* mpf_ceil: Miscellaneous Float Functions.
+ (line 7)
+* mpf_class: C++ Interface General.
+ (line 20)
+* mpf_class::fits_sint_p: C++ Interface Floats.
+ (line 74)
+* mpf_class::fits_slong_p: C++ Interface Floats.
+ (line 75)
+* mpf_class::fits_sshort_p: C++ Interface Floats.
+ (line 76)
+* mpf_class::fits_uint_p: C++ Interface Floats.
+ (line 77)
+* mpf_class::fits_ulong_p: C++ Interface Floats.
+ (line 78)
+* mpf_class::fits_ushort_p: C++ Interface Floats.
+ (line 79)
+* mpf_class::get_d: C++ Interface Floats.
+ (line 82)
+* mpf_class::get_mpf_t: C++ Interface General.
+ (line 66)
+* mpf_class::get_prec: C++ Interface Floats.
+ (line 100)
+* mpf_class::get_si: C++ Interface Floats.
+ (line 83)
+* mpf_class::get_str: C++ Interface Floats.
+ (line 85)
+* mpf_class::get_ui: C++ Interface Floats.
+ (line 86)
+* mpf_class::mpf_class: C++ Interface Floats.
+ (line 38)
+* mpf_class::operator=: C++ Interface Floats.
+ (line 47)
+* mpf_class::set_prec: C++ Interface Floats.
+ (line 101)
+* mpf_class::set_prec_raw: C++ Interface Floats.
+ (line 102)
+* mpf_class::set_str: C++ Interface Floats.
+ (line 88)
+* mpf_clear: Initializing Floats. (line 37)
+* mpf_clears: Initializing Floats. (line 41)
+* mpf_cmp: Float Comparison. (line 7)
+* mpf_cmp_d: Float Comparison. (line 8)
+* mpf_cmp_si: Float Comparison. (line 10)
+* mpf_cmp_ui: Float Comparison. (line 9)
+* mpf_div: Float Arithmetic. (line 29)
+* mpf_div_2exp: Float Arithmetic. (line 53)
+* mpf_div_ui: Float Arithmetic. (line 33)
+* mpf_eq: Float Comparison. (line 17)
+* mpf_fits_sint_p: Miscellaneous Float Functions.
+ (line 20)
+* mpf_fits_slong_p: Miscellaneous Float Functions.
+ (line 18)
+* mpf_fits_sshort_p: Miscellaneous Float Functions.
+ (line 22)
+* mpf_fits_uint_p: Miscellaneous Float Functions.
+ (line 19)
+* mpf_fits_ulong_p: Miscellaneous Float Functions.
+ (line 17)
+* mpf_fits_ushort_p: Miscellaneous Float Functions.
+ (line 21)
+* mpf_floor: Miscellaneous Float Functions.
+ (line 8)
+* mpf_get_d: Converting Floats. (line 7)
+* mpf_get_d_2exp: Converting Floats. (line 16)
+* mpf_get_default_prec: Initializing Floats. (line 12)
+* mpf_get_prec: Initializing Floats. (line 62)
+* mpf_get_si: Converting Floats. (line 27)
+* mpf_get_str: Converting Floats. (line 37)
+* mpf_get_ui: Converting Floats. (line 28)
+* mpf_init: Initializing Floats. (line 19)
+* mpf_init2: Initializing Floats. (line 26)
+* mpf_init_set: Simultaneous Float Init & Assign.
+ (line 16)
+* mpf_init_set_d: Simultaneous Float Init & Assign.
+ (line 19)
+* mpf_init_set_si: Simultaneous Float Init & Assign.
+ (line 18)
+* mpf_init_set_str: Simultaneous Float Init & Assign.
+ (line 25)
+* mpf_init_set_ui: Simultaneous Float Init & Assign.
+ (line 17)
+* mpf_inits: Initializing Floats. (line 31)
+* mpf_inp_str: I/O of Floats. (line 37)
+* mpf_integer_p: Miscellaneous Float Functions.
+ (line 14)
+* mpf_mul: Float Arithmetic. (line 19)
+* mpf_mul_2exp: Float Arithmetic. (line 50)
+* mpf_mul_ui: Float Arithmetic. (line 21)
+* mpf_neg: Float Arithmetic. (line 44)
+* mpf_out_str: I/O of Floats. (line 17)
+* mpf_pow_ui: Float Arithmetic. (line 41)
+* mpf_random2: Miscellaneous Float Functions.
+ (line 36)
+* mpf_reldiff: Float Comparison. (line 29)
+* mpf_set: Assigning Floats. (line 10)
+* mpf_set_d: Assigning Floats. (line 13)
+* mpf_set_default_prec: Initializing Floats. (line 7)
+* mpf_set_prec: Initializing Floats. (line 65)
+* mpf_set_prec_raw: Initializing Floats. (line 72)
+* mpf_set_q: Assigning Floats. (line 15)
+* mpf_set_si: Assigning Floats. (line 12)
+* mpf_set_str: Assigning Floats. (line 18)
+* mpf_set_ui: Assigning Floats. (line 11)
+* mpf_set_z: Assigning Floats. (line 14)
+* mpf_sgn: Float Comparison. (line 33)
+* mpf_sqrt: Float Arithmetic. (line 36)
+* mpf_sqrt_ui: Float Arithmetic. (line 37)
+* mpf_sub: Float Arithmetic. (line 12)
+* mpf_sub_ui: Float Arithmetic. (line 16)
+* mpf_swap: Assigning Floats. (line 52)
+* mpf_t: Nomenclature and Types.
+ (line 21)
+* mpf_trunc: Miscellaneous Float Functions.
+ (line 9)
+* mpf_ui_div: Float Arithmetic. (line 31)
+* mpf_ui_sub: Float Arithmetic. (line 14)
+* mpf_urandomb: Miscellaneous Float Functions.
+ (line 27)
+* mpn_add: Low-level Functions. (line 69)
+* mpn_add_1: Low-level Functions. (line 64)
+* mpn_add_n: Low-level Functions. (line 54)
+* mpn_addmul_1: Low-level Functions. (line 148)
+* mpn_and_n: Low-level Functions. (line 420)
+* mpn_andn_n: Low-level Functions. (line 435)
+* mpn_cmp: Low-level Functions. (line 284)
+* mpn_com: Low-level Functions. (line 460)
+* mpn_copyd: Low-level Functions. (line 469)
+* mpn_copyi: Low-level Functions. (line 465)
+* mpn_divexact_by3: Low-level Functions. (line 229)
+* mpn_divexact_by3c: Low-level Functions. (line 231)
+* mpn_divmod: Low-level Functions. (line 224)
+* mpn_divmod_1: Low-level Functions. (line 208)
+* mpn_divrem: Low-level Functions. (line 182)
+* mpn_divrem_1: Low-level Functions. (line 206)
+* mpn_gcd: Low-level Functions. (line 289)
+* mpn_gcd_1: Low-level Functions. (line 299)
+* mpn_gcdext: Low-level Functions. (line 305)
+* mpn_get_str: Low-level Functions. (line 346)
+* mpn_hamdist: Low-level Functions. (line 410)
+* mpn_ior_n: Low-level Functions. (line 425)
+* mpn_iorn_n: Low-level Functions. (line 440)
+* mpn_lshift: Low-level Functions. (line 260)
+* mpn_mod_1: Low-level Functions. (line 255)
+* 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 445)
+* mpn_neg: Low-level Functions. (line 98)
+* mpn_nior_n: Low-level Functions. (line 450)
+* mpn_perfect_square_p: Low-level Functions. (line 416)
+* mpn_popcount: Low-level Functions. (line 406)
+* mpn_random: Low-level Functions. (line 395)
+* mpn_random2: Low-level Functions. (line 396)
+* mpn_rshift: Low-level Functions. (line 272)
+* mpn_scan0: Low-level Functions. (line 380)
+* mpn_scan1: Low-level Functions. (line 388)
+* mpn_set_str: Low-level Functions. (line 361)
+* mpn_sqr: Low-level Functions. (line 125)
+* mpn_sqrtrem: Low-level Functions. (line 328)
+* mpn_sub: Low-level Functions. (line 90)
+* mpn_sub_1: Low-level Functions. (line 85)
+* mpn_sub_n: Low-level Functions. (line 76)
+* mpn_submul_1: Low-level Functions. (line 159)
+* mpn_tdiv_qr: Low-level Functions. (line 171)
+* mpn_xnor_n: Low-level Functions. (line 455)
+* mpn_xor_n: Low-level Functions. (line 430)
+* mpn_zero: Low-level Functions. (line 472)
+* mpq_abs: Rational Arithmetic. (line 31)
+* mpq_add: Rational Arithmetic. (line 7)
+* mpq_canonicalize: Rational Number Functions.
+ (line 22)
+* mpq_class: C++ Interface General.
+ (line 19)
+* mpq_class::canonicalize: C++ Interface Rationals.
+ (line 37)
+* mpq_class::get_d: C++ Interface Rationals.
+ (line 46)
+* mpq_class::get_den: C++ Interface Rationals.
+ (line 58)
+* mpq_class::get_den_mpz_t: C++ Interface Rationals.
+ (line 68)
+* mpq_class::get_mpq_t: C++ Interface General.
+ (line 65)
+* mpq_class::get_num: C++ Interface Rationals.
+ (line 57)
+* mpq_class::get_num_mpz_t: C++ Interface Rationals.
+ (line 67)
+* mpq_class::get_str: C++ Interface Rationals.
+ (line 47)
+* mpq_class::mpq_class: C++ Interface Rationals.
+ (line 22)
+* mpq_class::set_str: C++ Interface Rationals.
+ (line 49)
+* mpq_clear: Initializing Rationals.
+ (line 16)
+* mpq_clears: Initializing Rationals.
+ (line 20)
+* mpq_cmp: Comparing Rationals. (line 7)
+* mpq_cmp_si: Comparing Rationals. (line 17)
+* mpq_cmp_ui: Comparing Rationals. (line 15)
+* mpq_denref: Applying Integer Functions.
+ (line 18)
+* mpq_div: Rational Arithmetic. (line 22)
+* mpq_div_2exp: Rational Arithmetic. (line 25)
+* mpq_equal: Comparing Rationals. (line 33)
+* mpq_get_d: Rational Conversions.
+ (line 7)
+* mpq_get_den: Applying Integer Functions.
+ (line 24)
+* mpq_get_num: Applying Integer Functions.
+ (line 23)
+* mpq_get_str: Rational Conversions.
+ (line 22)
+* mpq_init: Initializing Rationals.
+ (line 7)
+* mpq_inits: Initializing Rationals.
+ (line 12)
+* mpq_inp_str: I/O of Rationals. (line 23)
+* mpq_inv: Rational Arithmetic. (line 34)
+* mpq_mul: Rational Arithmetic. (line 15)
+* mpq_mul_2exp: Rational Arithmetic. (line 18)
+* mpq_neg: Rational Arithmetic. (line 28)
+* mpq_numref: Applying Integer Functions.
+ (line 17)
+* mpq_out_str: I/O of Rationals. (line 15)
+* mpq_set: Initializing Rationals.
+ (line 24)
+* mpq_set_d: Rational Conversions.
+ (line 17)
+* mpq_set_den: Applying Integer Functions.
+ (line 26)
+* mpq_set_f: Rational Conversions.
+ (line 18)
+* mpq_set_num: Applying Integer Functions.
+ (line 25)
+* mpq_set_si: Initializing Rationals.
+ (line 31)
+* mpq_set_str: Initializing Rationals.
+ (line 36)
+* mpq_set_ui: Initializing Rationals.
+ (line 29)
+* mpq_set_z: Initializing Rationals.
+ (line 25)
+* mpq_sgn: Comparing Rationals. (line 27)
+* mpq_sub: Rational Arithmetic. (line 11)
+* mpq_swap: Initializing Rationals.
+ (line 56)
+* mpq_t: Nomenclature and Types.
+ (line 16)
+* mpz_abs: Integer Arithmetic. (line 42)
+* mpz_add: Integer Arithmetic. (line 7)
+* mpz_add_ui: Integer Arithmetic. (line 9)
+* mpz_addmul: Integer Arithmetic. (line 25)
+* mpz_addmul_ui: Integer Arithmetic. (line 27)
+* mpz_and: Integer Logic and Bit Fiddling.
+ (line 11)
+* mpz_array_init: Integer Special Functions.
+ (line 11)
+* mpz_bin_ui: Number Theoretic Functions.
+ (line 98)
+* mpz_bin_uiui: Number Theoretic Functions.
+ (line 100)
+* mpz_cdiv_q: Integer Division. (line 13)
+* mpz_cdiv_q_2exp: Integer Division. (line 24)
+* mpz_cdiv_q_ui: Integer Division. (line 17)
+* mpz_cdiv_qr: Integer Division. (line 15)
+* mpz_cdiv_qr_ui: Integer Division. (line 21)
+* mpz_cdiv_r: Integer Division. (line 14)
+* mpz_cdiv_r_2exp: Integer Division. (line 25)
+* mpz_cdiv_r_ui: Integer Division. (line 19)
+* mpz_cdiv_ui: Integer Division. (line 23)
+* mpz_class: C++ Interface General.
+ (line 18)
+* mpz_class::fits_sint_p: C++ Interface Integers.
+ (line 45)
+* mpz_class::fits_slong_p: C++ Interface Integers.
+ (line 46)
+* mpz_class::fits_sshort_p: C++ Interface Integers.
+ (line 47)
+* mpz_class::fits_uint_p: C++ Interface Integers.
+ (line 48)
+* mpz_class::fits_ulong_p: C++ Interface Integers.
+ (line 49)
+* mpz_class::fits_ushort_p: C++ Interface Integers.
+ (line 50)
+* mpz_class::get_d: C++ Interface Integers.
+ (line 51)
+* mpz_class::get_mpz_t: C++ Interface General.
+ (line 64)
+* mpz_class::get_si: C++ Interface Integers.
+ (line 52)
+* mpz_class::get_str: C++ Interface Integers.
+ (line 53)
+* mpz_class::get_ui: C++ Interface Integers.
+ (line 54)
+* mpz_class::mpz_class: C++ Interface Integers.
+ (line 7)
+* mpz_class::set_str: C++ Interface Integers.
+ (line 56)
+* mpz_clear: Initializing Integers.
+ (line 44)
+* mpz_clears: Initializing Integers.
+ (line 48)
+* mpz_clrbit: Integer Logic and Bit Fiddling.
+ (line 54)
+* mpz_cmp: Integer Comparisons. (line 7)
+* mpz_cmp_d: Integer Comparisons. (line 8)
+* mpz_cmp_si: Integer Comparisons. (line 9)
+* mpz_cmp_ui: Integer Comparisons. (line 10)
+* mpz_cmpabs: Integer Comparisons. (line 18)
+* mpz_cmpabs_d: Integer Comparisons. (line 19)
+* mpz_cmpabs_ui: Integer Comparisons. (line 20)
+* mpz_com: Integer Logic and Bit Fiddling.
+ (line 20)
+* mpz_combit: Integer Logic and Bit Fiddling.
+ (line 57)
+* mpz_congruent_2exp_p: Integer Division. (line 124)
+* mpz_congruent_p: Integer Division. (line 121)
+* mpz_congruent_ui_p: Integer Division. (line 123)
+* mpz_divexact: Integer Division. (line 101)
+* mpz_divexact_ui: Integer Division. (line 102)
+* mpz_divisible_2exp_p: Integer Division. (line 112)
+* mpz_divisible_p: Integer Division. (line 110)
+* mpz_divisible_ui_p: Integer Division. (line 111)
+* mpz_even_p: Miscellaneous Integer Functions.
+ (line 18)
+* mpz_export: Integer Import and Export.
+ (line 45)
+* mpz_fac_ui: Number Theoretic Functions.
+ (line 95)
+* mpz_fdiv_q: Integer Division. (line 27)
+* mpz_fdiv_q_2exp: Integer Division. (line 38)
+* mpz_fdiv_q_ui: Integer Division. (line 31)
+* mpz_fdiv_qr: Integer Division. (line 29)
+* mpz_fdiv_qr_ui: Integer Division. (line 35)
+* mpz_fdiv_r: Integer Division. (line 28)
+* mpz_fdiv_r_2exp: Integer Division. (line 39)
+* mpz_fdiv_r_ui: Integer Division. (line 33)
+* mpz_fdiv_ui: Integer Division. (line 37)
+* mpz_fib2_ui: Number Theoretic Functions.
+ (line 108)
+* mpz_fib_ui: Number Theoretic Functions.
+ (line 106)
+* mpz_fits_sint_p: Miscellaneous Integer Functions.
+ (line 10)
+* mpz_fits_slong_p: Miscellaneous Integer Functions.
+ (line 8)
+* mpz_fits_sshort_p: Miscellaneous Integer Functions.
+ (line 12)
+* mpz_fits_uint_p: Miscellaneous Integer Functions.
+ (line 9)
+* mpz_fits_ulong_p: Miscellaneous Integer Functions.
+ (line 7)
+* mpz_fits_ushort_p: Miscellaneous Integer Functions.
+ (line 11)
+* mpz_gcd: Number Theoretic Functions.
+ (line 30)
+* mpz_gcd_ui: Number Theoretic Functions.
+ (line 35)
+* mpz_gcdext: Number Theoretic Functions.
+ (line 45)
+* mpz_get_d: Converting Integers. (line 27)
+* mpz_get_d_2exp: Converting Integers. (line 35)
+* mpz_get_si: Converting Integers. (line 18)
+* mpz_get_str: Converting Integers. (line 46)
+* mpz_get_ui: Converting Integers. (line 11)
+* mpz_getlimbn: Integer Special Functions.
+ (line 60)
+* mpz_hamdist: Integer Logic and Bit Fiddling.
+ (line 29)
+* mpz_import: Integer Import and Export.
+ (line 11)
+* mpz_init: Initializing Integers.
+ (line 26)
+* mpz_init2: Initializing Integers.
+ (line 33)
+* mpz_init_set: Simultaneous Integer Init & Assign.
+ (line 27)
+* mpz_init_set_d: Simultaneous Integer Init & Assign.
+ (line 30)
+* mpz_init_set_si: Simultaneous Integer Init & Assign.
+ (line 29)
+* mpz_init_set_str: Simultaneous Integer Init & Assign.
+ (line 34)
+* mpz_init_set_ui: Simultaneous Integer Init & Assign.
+ (line 28)
+* mpz_inits: Initializing Integers.
+ (line 29)
+* mpz_inp_raw: I/O of Integers. (line 59)
+* mpz_inp_str: I/O of Integers. (line 28)
+* mpz_invert: Number Theoretic Functions.
+ (line 60)
+* mpz_ior: Integer Logic and Bit Fiddling.
+ (line 14)
+* mpz_jacobi: Number Theoretic Functions.
+ (line 66)
+* mpz_kronecker: Number Theoretic Functions.
+ (line 74)
+* mpz_kronecker_si: Number Theoretic Functions.
+ (line 75)
+* mpz_kronecker_ui: Number Theoretic Functions.
+ (line 76)
+* mpz_lcm: Number Theoretic Functions.
+ (line 54)
+* mpz_lcm_ui: Number Theoretic Functions.
+ (line 55)
+* mpz_legendre: Number Theoretic Functions.
+ (line 69)
+* mpz_lucnum2_ui: Number Theoretic Functions.
+ (line 119)
+* mpz_lucnum_ui: Number Theoretic Functions.
+ (line 117)
+* mpz_mod: Integer Division. (line 91)
+* mpz_mod_ui: Integer Division. (line 93)
+* mpz_mul: Integer Arithmetic. (line 19)
+* mpz_mul_2exp: Integer Arithmetic. (line 35)
+* mpz_mul_si: Integer Arithmetic. (line 20)
+* mpz_mul_ui: Integer Arithmetic. (line 22)
+* mpz_neg: Integer Arithmetic. (line 39)
+* mpz_nextprime: Number Theoretic Functions.
+ (line 23)
+* mpz_odd_p: Miscellaneous Integer Functions.
+ (line 17)
+* mpz_out_raw: I/O of Integers. (line 43)
+* mpz_out_str: I/O of Integers. (line 16)
+* mpz_perfect_power_p: Integer Roots. (line 27)
+* mpz_perfect_square_p: Integer Roots. (line 36)
+* mpz_popcount: Integer Logic and Bit Fiddling.
+ (line 23)
+* mpz_pow_ui: Integer Exponentiation.
+ (line 31)
+* mpz_powm: Integer Exponentiation.
+ (line 8)
+* mpz_powm_sec: Integer Exponentiation.
+ (line 18)
+* mpz_powm_ui: Integer Exponentiation.
+ (line 10)
+* mpz_probab_prime_p: Number Theoretic Functions.
+ (line 7)
+* mpz_random: Integer Random Numbers.
+ (line 42)
+* mpz_random2: Integer Random Numbers.
+ (line 51)
+* mpz_realloc2: Initializing Integers.
+ (line 52)
+* mpz_remove: Number Theoretic Functions.
+ (line 90)
+* mpz_root: Integer Roots. (line 7)
+* mpz_rootrem: Integer Roots. (line 13)
+* mpz_rrandomb: Integer Random Numbers.
+ (line 31)
+* mpz_scan0: Integer Logic and Bit Fiddling.
+ (line 37)
+* mpz_scan1: Integer Logic and Bit Fiddling.
+ (line 38)
+* mpz_set: Assigning Integers. (line 10)
+* mpz_set_d: Assigning Integers. (line 13)
+* mpz_set_f: Assigning Integers. (line 15)
+* mpz_set_q: Assigning Integers. (line 14)
+* mpz_set_si: Assigning Integers. (line 12)
+* mpz_set_str: Assigning Integers. (line 21)
+* mpz_set_ui: Assigning Integers. (line 11)
+* mpz_setbit: Integer Logic and Bit Fiddling.
+ (line 51)
+* mpz_sgn: Integer Comparisons. (line 28)
+* mpz_si_kronecker: Number Theoretic Functions.
+ (line 77)
+* mpz_size: Integer Special Functions.
+ (line 68)
+* mpz_sizeinbase: Miscellaneous Integer Functions.
+ (line 23)
+* mpz_sqrt: Integer Roots. (line 17)
+* mpz_sqrtrem: Integer Roots. (line 20)
+* mpz_sub: Integer Arithmetic. (line 12)
+* mpz_sub_ui: Integer Arithmetic. (line 14)
+* mpz_submul: Integer Arithmetic. (line 30)
+* mpz_submul_ui: Integer Arithmetic. (line 32)
+* mpz_swap: Assigning Integers. (line 37)
+* mpz_t: Nomenclature and Types.
+ (line 6)
+* mpz_tdiv_q: Integer Division. (line 41)
+* mpz_tdiv_q_2exp: Integer Division. (line 52)
+* mpz_tdiv_q_ui: Integer Division. (line 45)
+* mpz_tdiv_qr: Integer Division. (line 43)
+* mpz_tdiv_qr_ui: Integer Division. (line 49)
+* mpz_tdiv_r: Integer Division. (line 42)
+* mpz_tdiv_r_2exp: Integer Division. (line 53)
+* mpz_tdiv_r_ui: Integer Division. (line 47)
+* mpz_tdiv_ui: Integer Division. (line 51)
+* mpz_tstbit: Integer Logic and Bit Fiddling.
+ (line 60)
+* mpz_ui_kronecker: Number Theoretic Functions.
+ (line 78)
+* mpz_ui_pow_ui: Integer Exponentiation.
+ (line 33)
+* mpz_ui_sub: Integer Arithmetic. (line 16)
+* mpz_urandomb: Integer Random Numbers.
+ (line 14)
+* mpz_urandomm: Integer Random Numbers.
+ (line 23)
+* mpz_xor: Integer Logic and Bit Fiddling.
+ (line 17)
+* msqrt: BSD Compatible Functions.
+ (line 63)
+* msub: BSD Compatible Functions.
+ (line 46)
+* mtox: BSD Compatible Functions.
+ (line 98)
+* mult: BSD Compatible Functions.
+ (line 49)
+* operator%: C++ Interface Integers.
+ (line 30)
+* operator/: C++ Interface Integers.
+ (line 29)
+* operator<<: C++ Formatted Output.
+ (line 20)
+* operator>> <1>: C++ Formatted Input. (line 11)
+* operator>>: C++ Interface Rationals.
+ (line 77)
+* pow: BSD Compatible Functions.
+ (line 71)
+* rpow: BSD Compatible Functions.
+ (line 79)
+* sdiv: BSD Compatible Functions.
+ (line 55)
+* sgn <1>: C++ Interface Rationals.
+ (line 50)
+* sgn <2>: C++ Interface Integers.
+ (line 57)
+* sgn: C++ Interface Floats.
+ (line 89)
+* sqrt <1>: C++ Interface Integers.
+ (line 58)
+* sqrt: C++ Interface Floats.
+ (line 90)
+* trunc: C++ Interface Floats.
+ (line 91)
+* xtom: BSD Compatible Functions.
+ (line 34)
+
+