+++ /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)
-
-
projects / xonotic / xonotic.git / blobdiff