gfiber / toolchains / bruno / f0dcd7f7efd6f7b917902cadf4d492dcb3676093 / . / usr / share / info / gmp.info-2

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 6.1.0. | |

Copyright 1991, 1993-2015 Free Software Foundation, Inc. | |

Permission is granted to copy, distribute and/or modify this | |

document under the terms of the GNU Free Documentation License, Version | |

1.3 or any later version published by the Free Software Foundation; | |

with no Invariant Sections, with the Front-Cover Texts being "A GNU | |

Manual", and with the Back-Cover Texts being "You have freedom to copy | |

and modify this GNU Manual, like GNU software". A copy of the license | |

is included in *Note GNU Free Documentation License::. | |

INFO-DIR-SECTION GNU libraries | |

START-INFO-DIR-ENTRY | |

* gmp: (gmp). GNU Multiple Precision Arithmetic Library. | |

END-INFO-DIR-ENTRY | |

File: gmp.info, Node: Exact Division, Next: Exact Remainder, Prev: Block-Wise Barrett Division, Up: Division Algorithms | |

15.2.5 Exact Division | |

--------------------- | |

A so-called exact division is when the dividend is known to be an exact | |

multiple of the divisor. Jebelean's exact division algorithm uses this | |

knowledge to make some significant optimizations (*note References::). | |

The idea can be illustrated in decimal for example with 368154 | |

divided by 543. Because the low digit of the dividend is 4, the low | |

digit of the quotient must be 8. This is arrived at from 4*7 mod 10, | |

using the fact 7 is the modular inverse of 3 (the low digit of the | |

divisor), since 3*7 == 1 mod 10. So 8*543=4344 can be subtracted from | |

the dividend leaving 363810. Notice the low digit has become zero. | |

The procedure is repeated at the second digit, with the next | |

quotient digit 7 (7 == 1*7 mod 10), subtracting 7*543=3801, leaving | |

325800. And finally at the third digit with quotient digit 6 (8*7 mod | |

10), subtracting 6*543=3258 leaving 0. So the quotient is 678. | |

Notice however that the multiplies and subtractions don't need to | |

extend past the low three digits of the dividend, since that's enough | |

to determine the three quotient digits. For the last quotient digit no | |

subtraction is needed at all. On a 2NxN division like this one, only | |

about half the work of a normal basecase division is necessary. | |

For an NxM exact division producing Q=N-M quotient limbs, the saving | |

over a normal basecase division is in two parts. Firstly, each of the | |

Q quotient limbs needs only one multiply, not a 2x1 divide and | |

multiply. Secondly, the crossproducts are reduced when Q>M to | |

Q*M-M*(M+1)/2, or when Q<=M to Q*(Q-1)/2. Notice the savings are | |

complementary. If Q is big then many divisions are saved, or if Q is | |

small then the crossproducts reduce to a small number. | |

The modular inverse used is calculated efficiently by `binvert_limb' | |

in `gmp-impl.h'. This does four multiplies for a 32-bit limb, or six | |

for a 64-bit limb. `tune/modlinv.c' has some alternate implementations | |

that might suit processors better at bit twiddling than multiplying. | |

The sub-quadratic exact division described by Jebelean in "Exact | |

Division with Karatsuba Complexity" is not currently implemented. It | |

uses a rearrangement similar to the divide and conquer for normal | |

division (*note Divide and Conquer Division::), but operating from low | |

to high. A further possibility not currently implemented is | |

"Bidirectional Exact Integer Division" by Krandick and Jebelean which | |

forms quotient limbs from both the high and low ends of the dividend, | |

and can halve once more the number of crossproducts needed in a 2NxN | |

division. | |

A special case exact division by 3 exists in `mpn_divexact_by3', | |

supporting Toom-3 multiplication and `mpq' canonicalizations. It forms | |

quotient digits with a multiply by the modular inverse of 3 (which is | |

`0xAA..AAB') and uses two comparisons to determine a borrow for the next | |

limb. The multiplications don't need to be on the dependent chain, as | |

long as the effect of the borrows is applied, which can help chips with | |

pipelined multipliers. | |

File: gmp.info, Node: Exact Remainder, Next: Small Quotient Division, Prev: Exact Division, Up: Division Algorithms | |

15.2.6 Exact Remainder | |

---------------------- | |

If the exact division algorithm is done with a full subtraction at each | |

stage and the dividend isn't a multiple of the divisor, then low zero | |

limbs are produced but with a remainder in the high limbs. For | |

dividend a, divisor d, quotient q, and b = 2^mp_bits_per_limb, this | |

remainder r is of the form | |

a = q*d + r*b^n | |

n represents the number of zero limbs produced by the subtractions, | |

that being the number of limbs produced for q. r will be in the range | |

0<=r<d and can be viewed as a remainder, but one shifted up by a factor | |

of b^n. | |

Carrying out full subtractions at each stage means the same number | |

of cross products must be done as a normal division, but there's still | |

some single limb divisions saved. When d is a single limb some | |

simplifications arise, providing good speedups on a number of | |

processors. | |

The functions `mpn_divexact_by3', `mpn_modexact_1_odd' and the | |

internal `mpn_redc_X' functions differ subtly in how they return r, | |

leading to some negations in the above formula, but all are essentially | |

the same. | |

Clearly r is zero when a is a multiple of d, and this leads to | |

divisibility or congruence tests which are potentially more efficient | |

than a normal division. | |

The factor of b^n on r can be ignored in a GCD when d is odd, hence | |

the use of `mpn_modexact_1_odd' by `mpn_gcd_1' and `mpz_kronecker_ui' | |

etc (*note Greatest Common Divisor Algorithms::). | |

Montgomery's REDC method for modular multiplications uses operands | |

of the form of x*b^-n and y*b^-n and on calculating (x*b^-n)*(y*b^-n) | |

uses the factor of b^n in the exact remainder to reach a product in the | |

same form (x*y)*b^-n (*note Modular Powering Algorithm::). | |

Notice that r generally gives no useful information about the | |

ordinary remainder a mod d since b^n mod d could be anything. If | |

however b^n == 1 mod d, then r is the negative of the ordinary | |

remainder. This occurs whenever d is a factor of b^n-1, as for example | |

with 3 in `mpn_divexact_by3'. For a 32 or 64 bit limb other such | |

factors include 5, 17 and 257, but no particular use has been found for | |

this. | |

File: gmp.info, Node: Small Quotient Division, Prev: Exact Remainder, Up: Division Algorithms | |

15.2.7 Small Quotient Division | |

------------------------------ | |

An NxM division where the number of quotient limbs Q=N-M is small can | |

be optimized somewhat. | |

An ordinary basecase division normalizes the divisor by shifting it | |

to make the high bit set, shifting the dividend accordingly, and | |

shifting the remainder back down at the end of the calculation. This | |

is wasteful if only a few quotient limbs are to be formed. Instead a | |

division of just the top 2*Q limbs of the dividend by the top Q limbs | |

of the divisor can be used to form a trial quotient. This requires | |

only those limbs normalized, not the whole of the divisor and dividend. | |

A multiply and subtract then applies the trial quotient to the M-Q | |

unused limbs of the divisor and N-Q dividend limbs (which includes Q | |

limbs remaining from the trial quotient division). The starting trial | |

quotient can be 1 or 2 too big, but all cases of 2 too big and most | |

cases of 1 too big are detected by first comparing the most significant | |

limbs that will arise from the subtraction. An addback is done if the | |

quotient still turns out to be 1 too big. | |

This whole procedure is essentially the same as one step of the | |

basecase algorithm done in a Q limb base, though with the trial | |

quotient test done only with the high limbs, not an entire Q limb | |

"digit" product. The correctness of this weaker test can be | |

established by following the argument of Knuth section 4.3.1 exercise | |

20 but with the v2*q>b*r+u2 condition appropriately relaxed. | |

File: gmp.info, Node: Greatest Common Divisor Algorithms, Next: Powering Algorithms, Prev: Division Algorithms, Up: Algorithms | |

15.3 Greatest Common Divisor | |

============================ | |

* Menu: | |

* Binary GCD:: | |

* Lehmer's Algorithm:: | |

* Subquadratic GCD:: | |

* Extended GCD:: | |

* Jacobi Symbol:: | |

File: gmp.info, Node: Binary GCD, Next: Lehmer's Algorithm, Prev: Greatest Common Divisor Algorithms, Up: Greatest Common Divisor Algorithms | |

15.3.1 Binary GCD | |

----------------- | |

At small sizes GMP uses an O(N^2) binary style GCD. This is described | |

in many textbooks, for example Knuth section 4.5.2 algorithm B. It | |

simply consists of successively reducing odd operands a and b using | |

a,b = abs(a-b),min(a,b) | |

strip factors of 2 from a | |

The Euclidean GCD algorithm, as per Knuth algorithms E and A, | |

repeatedly computes the quotient q = floor(a/b) and replaces a,b by v, | |

u - q v. The binary algorithm has so far been found to be faster than | |

the Euclidean algorithm everywhere. One reason the binary method does | |

well is that the implied quotient at each step is usually small, so | |

often only one or two subtractions are needed to get the same effect as | |

a division. Quotients 1, 2 and 3 for example occur 67.7% of the time, | |

see Knuth section 4.5.3 Theorem E. | |

When the implied quotient is large, meaning b is much smaller than | |

a, then a division is worthwhile. This is the basis for the initial a | |

mod b reductions in `mpn_gcd' and `mpn_gcd_1' (the latter for both Nx1 | |

and 1x1 cases). But after that initial reduction, big quotients occur | |

too rarely to make it worth checking for them. | |

The final 1x1 GCD in `mpn_gcd_1' is done in the generic C code as | |

described above. For two N-bit operands, the algorithm takes about | |

0.68 iterations per bit. For optimum performance some attention needs | |

to be paid to the way the factors of 2 are stripped from a. | |

Firstly it may be noted that in twos complement the number of low | |

zero bits on a-b is the same as b-a, so counting or testing can begin on | |

a-b without waiting for abs(a-b) to be determined. | |

A loop stripping low zero bits tends not to branch predict well, | |

since the condition is data dependent. But on average there's only a | |

few low zeros, so an option is to strip one or two bits arithmetically | |

then loop for more (as done for AMD K6). Or use a lookup table to get | |

a count for several bits then loop for more (as done for AMD K7). An | |

alternative approach is to keep just one of a or b odd and iterate | |

a,b = abs(a-b), min(a,b) | |

a = a/2 if even | |

b = b/2 if even | |

This requires about 1.25 iterations per bit, but stripping of a | |

single bit at each step avoids any branching. Repeating the bit strip | |

reduces to about 0.9 iterations per bit, which may be a worthwhile | |

tradeoff. | |

Generally with the above approaches a speed of perhaps 6 cycles per | |

bit can be achieved, which is still not terribly fast with for instance | |

a 64-bit GCD taking nearly 400 cycles. It's this sort of time which | |

means it's not usually advantageous to combine a set of divisibility | |

tests into a GCD. | |

Currently, the binary algorithm is used for GCD only when N < 3. | |

File: gmp.info, Node: Lehmer's Algorithm, Next: Subquadratic GCD, Prev: Binary GCD, Up: Greatest Common Divisor Algorithms | |

15.3.2 Lehmer's algorithm | |

------------------------- | |

Lehmer's improvement of the Euclidean algorithms is based on the | |

observation that the initial part of the quotient sequence depends only | |

on the most significant parts of the inputs. The variant of Lehmer's | |

algorithm used in GMP splits off the most significant two limbs, as | |

suggested, e.g., in "A Double-Digit Lehmer-Euclid Algorithm" by | |

Jebelean (*note References::). The quotients of two double-limb inputs | |

are collected as a 2 by 2 matrix with single-limb elements. This is | |

done by the function `mpn_hgcd2'. The resulting matrix is applied to | |

the inputs using `mpn_mul_1' and `mpn_submul_1'. Each iteration usually | |

reduces the inputs by almost one limb. In the rare case of a large | |

quotient, no progress can be made by examining just the most | |

significant two limbs, and the quotient is computed using plain | |

division. | |

The resulting algorithm is asymptotically O(N^2), just as the | |

Euclidean algorithm and the binary algorithm. The quadratic part of the | |

work are the calls to `mpn_mul_1' and `mpn_submul_1'. For small sizes, | |

the linear work is also significant. There are roughly N calls to the | |

`mpn_hgcd2' function. This function uses a couple of important | |

optimizations: | |

* It uses the same relaxed notion of correctness as `mpn_hgcd' (see | |

next section). This means that when called with the most | |

significant two limbs of two large numbers, the returned matrix | |

does not always correspond exactly to the initial quotient | |

sequence for the two large numbers; the final quotient may | |

sometimes be one off. | |

* It takes advantage of the fact the quotients are usually small. | |

The division operator is not used, since the corresponding | |

assembler instruction is very slow on most architectures. (This | |

code could probably be improved further, it uses many branches | |

that are unfriendly to prediction). | |

* It switches from double-limb calculations to single-limb | |

calculations half-way through, when the input numbers have been | |

reduced in size from two limbs to one and a half. | |

File: gmp.info, Node: Subquadratic GCD, Next: Extended GCD, Prev: Lehmer's Algorithm, Up: Greatest Common Divisor Algorithms | |

15.3.3 Subquadratic GCD | |

----------------------- | |

For inputs larger than `GCD_DC_THRESHOLD', GCD is computed via the HGCD | |

(Half GCD) function, as a generalization to Lehmer's algorithm. | |

Let the inputs a,b be of size N limbs each. Put S = floor(N/2) + 1. | |

Then HGCD(a,b) returns a transformation matrix T with non-negative | |

elements, and reduced numbers (c;d) = T^-1 (a;b). The reduced numbers | |

c,d must be larger than S limbs, while their difference abs(c-d) must | |

fit in S limbs. The matrix elements will also be of size roughly N/2. | |

The HGCD base case uses Lehmer's algorithm, but with the above stop | |

condition that returns reduced numbers and the corresponding | |

transformation matrix half-way through. For inputs larger than | |

`HGCD_THRESHOLD', HGCD is computed recursively, using the divide and | |

conquer algorithm in "On Scho"nhage's algorithm and subquadratic | |

integer GCD computation" by Mo"ller (*note References::). The recursive | |

algorithm consists of these main steps. | |

* Call HGCD recursively, on the most significant N/2 limbs. Apply the | |

resulting matrix T_1 to the full numbers, reducing them to a size | |

just above 3N/2. | |

* Perform a small number of division or subtraction steps to reduce | |

the numbers to size below 3N/2. This is essential mainly for the | |

unlikely case of large quotients. | |

* Call HGCD recursively, on the most significant N/2 limbs of the | |

reduced numbers. Apply the resulting matrix T_2 to the full | |

numbers, reducing them to a size just above N/2. | |

* Compute T = T_1 T_2. | |

* Perform a small number of division and subtraction steps to | |

satisfy the requirements, and return. | |

GCD is then implemented as a loop around HGCD, similarly to Lehmer's | |

algorithm. Where Lehmer repeatedly chops off the top two limbs, calls | |

`mpn_hgcd2', and applies the resulting matrix to the full numbers, the | |

sub-quadratic GCD chops off the most significant third of the limbs (the | |

proportion is a tuning parameter, and 1/3 seems to be more efficient | |

than, e.g, 1/2), calls `mpn_hgcd', and applies the resulting matrix. | |

Once the input numbers are reduced to size below `GCD_DC_THRESHOLD', | |

Lehmer's algorithm is used for the rest of the work. | |

The asymptotic running time of both HGCD and GCD is O(M(N)*log(N)), | |

where M(N) is the time for multiplying two N-limb numbers. | |

File: gmp.info, Node: Extended GCD, Next: Jacobi Symbol, Prev: Subquadratic GCD, Up: Greatest Common Divisor Algorithms | |

15.3.4 Extended GCD | |

------------------- | |

The extended GCD function, or GCDEXT, calculates gcd(a,b) and also | |

cofactors x and y satisfying a*x+b*y=gcd(a,b). All the algorithms used | |

for plain GCD are extended to handle this case. The binary algorithm is | |

used only for single-limb GCDEXT. Lehmer's algorithm is used for sizes | |

up to `GCDEXT_DC_THRESHOLD'. Above this threshold, GCDEXT is | |

implemented as a loop around HGCD, but with more book-keeping to keep | |

track of the cofactors. This gives the same asymptotic running time as | |

for GCD and HGCD, O(M(N)*log(N)) | |

One difference to plain GCD is that while the inputs a and b are | |

reduced as the algorithm proceeds, the cofactors x and y grow in size. | |

This makes the tuning of the chopping-point more difficult. The current | |

code chops off the most significant half of the inputs for the call to | |

HGCD in the first iteration, and the most significant two thirds for | |

the remaining calls. This strategy could surely be improved. Also the | |

stop condition for the loop, where Lehmer's algorithm is invoked once | |

the inputs are reduced below `GCDEXT_DC_THRESHOLD', could maybe be | |

improved by taking into account the current size of the cofactors. | |

File: gmp.info, Node: Jacobi Symbol, Prev: Extended GCD, Up: Greatest Common Divisor Algorithms | |

15.3.5 Jacobi Symbol | |

-------------------- | |

[This section is obsolete. The current Jacobi code actually uses a very | |

efficient algorithm.] | |

`mpz_jacobi' and `mpz_kronecker' are currently implemented with a | |

simple binary algorithm similar to that described for the GCDs (*note | |

Binary GCD::). They're not very fast when both inputs are large. | |

Lehmer's multi-step improvement or a binary based multi-step algorithm | |

is likely to be better. | |

When one operand fits a single limb, and that includes | |

`mpz_kronecker_ui' and friends, an initial reduction is done with | |

either `mpn_mod_1' or `mpn_modexact_1_odd', followed by the binary | |

algorithm on a single limb. The binary algorithm is well suited to a | |

single limb, and the whole calculation in this case is quite efficient. | |

In all the routines sign changes for the result are accumulated | |

using some bit twiddling, avoiding table lookups or conditional jumps. | |

File: gmp.info, Node: Powering Algorithms, Next: Root Extraction Algorithms, Prev: Greatest Common Divisor Algorithms, Up: Algorithms | |

15.4 Powering Algorithms | |

======================== | |

* Menu: | |

* Normal Powering Algorithm:: | |

* Modular Powering Algorithm:: | |

File: gmp.info, Node: Normal Powering Algorithm, Next: Modular Powering Algorithm, Prev: Powering Algorithms, Up: Powering Algorithms | |

15.4.1 Normal Powering | |

---------------------- | |

Normal `mpz' or `mpf' powering uses a simple binary algorithm, | |

successively squaring and then multiplying by the base when a 1 bit is | |

seen in the exponent, as per Knuth section 4.6.3. The "left to right" | |

variant described there is used rather than algorithm A, since it's | |

just as easy and can be done with somewhat less temporary memory. | |

File: gmp.info, Node: Modular Powering Algorithm, Prev: Normal Powering Algorithm, Up: Powering Algorithms | |

15.4.2 Modular Powering | |

----------------------- | |

Modular powering is implemented using a 2^k-ary sliding window | |

algorithm, as per "Handbook of Applied Cryptography" algorithm 14.85 | |

(*note References::). k is chosen according to the size of the | |

exponent. Larger exponents use larger values of k, the choice being | |

made to minimize the average number of multiplications that must | |

supplement the squaring. | |

The modular multiplies and squarings use either a simple division or | |

the REDC method by Montgomery (*note References::). REDC is a little | |

faster, essentially saving N single limb divisions in a fashion similar | |

to an exact remainder (*note Exact Remainder::). | |

File: gmp.info, Node: Root Extraction Algorithms, Next: Radix Conversion Algorithms, Prev: Powering Algorithms, Up: Algorithms | |

15.5 Root Extraction Algorithms | |

=============================== | |

* Menu: | |

* Square Root Algorithm:: | |

* Nth Root Algorithm:: | |

* Perfect Square Algorithm:: | |

* Perfect Power Algorithm:: | |

File: gmp.info, Node: Square Root Algorithm, Next: Nth Root Algorithm, Prev: Root Extraction Algorithms, Up: Root Extraction Algorithms | |

15.5.1 Square Root | |

------------------ | |

Square roots are taken using the "Karatsuba Square Root" algorithm by | |

Paul Zimmermann (*note References::). | |

An input n is split into four parts of k bits each, so with b=2^k we | |

have n = a3*b^3 + a2*b^2 + a1*b + a0. Part a3 must be "normalized" so | |

that either the high or second highest bit is set. In GMP, k is kept | |

on a limb boundary and the input is left shifted (by an even number of | |

bits) to normalize. | |

The square root of the high two parts is taken, by recursive | |

application of the algorithm (bottoming out in a one-limb Newton's | |

method), | |

s1,r1 = sqrtrem (a3*b + a2) | |

This is an approximation to the desired root and is extended by a | |

division to give s,r, | |

q,u = divrem (r1*b + a1, 2*s1) | |

s = s1*b + q | |

r = u*b + a0 - q^2 | |

The normalization requirement on a3 means at this point s is either | |

correct or 1 too big. r is negative in the latter case, so | |

if r < 0 then | |

r = r + 2*s - 1 | |

s = s - 1 | |

The algorithm is expressed in a divide and conquer form, but as | |

noted in the paper it can also be viewed as a discrete variant of | |

Newton's method, or as a variation on the schoolboy method (no longer | |

taught) for square roots two digits at a time. | |

If the remainder r is not required then usually only a few high limbs | |

of r and u need to be calculated to determine whether an adjustment to | |

s is required. This optimization is not currently implemented. | |

In the Karatsuba multiplication range this algorithm is | |

O(1.5*M(N/2)), where M(n) is the time to multiply two numbers of n | |

limbs. In the FFT multiplication range this grows to a bound of | |

O(6*M(N/2)). In practice a factor of about 1.5 to 1.8 is found in the | |

Karatsuba and Toom-3 ranges, growing to 2 or 3 in the FFT range. | |

The algorithm does all its calculations in integers and the resulting | |

`mpn_sqrtrem' is used for both `mpz_sqrt' and `mpf_sqrt'. The extended | |

precision given by `mpf_sqrt_ui' is obtained by padding with zero limbs. | |

File: gmp.info, Node: Nth Root Algorithm, Next: Perfect Square Algorithm, Prev: Square Root Algorithm, Up: Root Extraction Algorithms | |

15.5.2 Nth Root | |

--------------- | |

Integer Nth roots are taken using Newton's method with the following | |

iteration, where A is the input and n is the root to be taken. | |

1 A | |

a[i+1] = - * ( --------- + (n-1)*a[i] ) | |

n a[i]^(n-1) | |

The initial approximation a[1] is generated bitwise by successively | |

powering a trial root with or without new 1 bits, aiming to be just | |

above the true root. The iteration converges quadratically when | |

started from a good approximation. When n is large more initial bits | |

are needed to get good convergence. The current implementation is not | |

particularly well optimized. | |

File: gmp.info, Node: Perfect Square Algorithm, Next: Perfect Power Algorithm, Prev: Nth Root Algorithm, Up: Root Extraction Algorithms | |

15.5.3 Perfect Square | |

--------------------- | |

A significant fraction of non-squares can be quickly identified by | |

checking whether the input is a quadratic residue modulo small integers. | |

`mpz_perfect_square_p' first tests the input mod 256, which means | |

just examining the low byte. Only 44 different values occur for | |

squares mod 256, so 82.8% of inputs can be immediately identified as | |

non-squares. | |

On a 32-bit system similar tests are done mod 9, 5, 7, 13 and 17, | |

for a total 99.25% of inputs identified as non-squares. On a 64-bit | |

system 97 is tested too, for a total 99.62%. | |

These moduli are chosen because they're factors of 2^24-1 (or 2^48-1 | |

for 64-bits), and such a remainder can be quickly taken just using | |

additions (see `mpn_mod_34lsub1'). | |

When nails are in use moduli are instead selected by the `gen-psqr.c' | |

program and applied with an `mpn_mod_1'. The same 2^24-1 or 2^48-1 | |

could be done with nails using some extra bit shifts, but this is not | |

currently implemented. | |

In any case each modulus is applied to the `mpn_mod_34lsub1' or | |

`mpn_mod_1' remainder and a table lookup identifies non-squares. By | |

using a "modexact" style calculation, and suitably permuted tables, | |

just one multiply each is required, see the code for details. Moduli | |

are also combined to save operations, so long as the lookup tables | |

don't become too big. `gen-psqr.c' does all the pre-calculations. | |

A square root must still be taken for any value that passes these | |

tests, to verify it's really a square and not one of the small fraction | |

of non-squares that get through (i.e. a pseudo-square to all the tested | |

bases). | |

Clearly more residue tests could be done, `mpz_perfect_square_p' only | |

uses a compact and efficient set. Big inputs would probably benefit | |

from more residue testing, small inputs might be better off with less. | |

The assumed distribution of squares versus non-squares in the input | |

would affect such considerations. | |

File: gmp.info, Node: Perfect Power Algorithm, Prev: Perfect Square Algorithm, Up: Root Extraction Algorithms | |

15.5.4 Perfect Power | |

-------------------- | |

Detecting perfect powers is required by some factorization algorithms. | |

Currently `mpz_perfect_power_p' is implemented using repeated Nth root | |

extractions, though naturally only prime roots need to be considered. | |

(*Note Nth Root Algorithm::.) | |

If a prime divisor p with multiplicity e can be found, then only | |

roots which are divisors of e need to be considered, much reducing the | |

work necessary. To this end divisibility by a set of small primes is | |

checked. | |

File: gmp.info, Node: Radix Conversion Algorithms, Next: Other Algorithms, Prev: Root Extraction Algorithms, Up: Algorithms | |

15.6 Radix Conversion | |

===================== | |

Radix conversions are less important than other algorithms. A program | |

dominated by conversions should probably use a different data | |

representation. | |

* Menu: | |

* Binary to Radix:: | |

* Radix to Binary:: | |

File: gmp.info, Node: Binary to Radix, Next: Radix to Binary, Prev: Radix Conversion Algorithms, Up: Radix Conversion Algorithms | |

15.6.1 Binary to Radix | |

---------------------- | |

Conversions from binary to a power-of-2 radix use a simple and fast | |

O(N) bit extraction algorithm. | |

Conversions from binary to other radices use one of two algorithms. | |

Sizes below `GET_STR_PRECOMPUTE_THRESHOLD' use a basic O(N^2) method. | |

Repeated divisions by b^n are made, where b is the radix and n is the | |

biggest power that fits in a limb. But instead of simply using the | |

remainder r from such divisions, an extra divide step is done to give a | |

fractional limb representing r/b^n. The digits of r can then be | |

extracted using multiplications by b rather than divisions. Special | |

case code is provided for decimal, allowing multiplications by 10 to | |

optimize to shifts and adds. | |

Above `GET_STR_PRECOMPUTE_THRESHOLD' a sub-quadratic algorithm is | |

used. For an input t, powers b^(n*2^i) of the radix are calculated, | |

until a power between t and sqrt(t) is reached. t is then divided by | |

that largest power, giving a quotient which is the digits above that | |

power, and a remainder which is those below. These two parts are in | |

turn divided by the second highest power, and so on recursively. When | |

a piece has been divided down to less than `GET_STR_DC_THRESHOLD' | |

limbs, the basecase algorithm described above is used. | |

The advantage of this algorithm is that big divisions can make use | |

of the sub-quadratic divide and conquer division (*note Divide and | |

Conquer Division::), and big divisions tend to have less overheads than | |

lots of separate single limb divisions anyway. But in any case the | |

cost of calculating the powers b^(n*2^i) must first be overcome. | |

`GET_STR_PRECOMPUTE_THRESHOLD' and `GET_STR_DC_THRESHOLD' represent | |

the same basic thing, the point where it becomes worth doing a big | |

division to cut the input in half. `GET_STR_PRECOMPUTE_THRESHOLD' | |

includes the cost of calculating the radix power required, whereas | |

`GET_STR_DC_THRESHOLD' assumes that's already available, which is the | |

case when recursing. | |

Since the base case produces digits from least to most significant | |

but they want to be stored from most to least, it's necessary to | |

calculate in advance how many digits there will be, or at least be sure | |

not to underestimate that. For GMP the number of input bits is | |

multiplied by `chars_per_bit_exactly' from `mp_bases', rounding up. | |

The result is either correct or one too big. | |

Examining some of the high bits of the input could increase the | |

chance of getting the exact number of digits, but an exact result every | |

time would not be practical, since in general the difference between | |

numbers 100... and 99... is only in the last few bits and the work to | |

identify 99... might well be almost as much as a full conversion. | |

The r/b^n scheme described above for using multiplications to bring | |

out digits might be useful for more than a single limb. Some brief | |

experiments with it on the base case when recursing didn't give a | |

noticeable improvement, but perhaps that was only due to the | |

implementation. Something similar would work for the sub-quadratic | |

divisions too, though there would be the cost of calculating a bigger | |

radix power. | |

Another possible improvement for the sub-quadratic part would be to | |

arrange for radix powers that balanced the sizes of quotient and | |

remainder produced, i.e. the highest power would be an b^(n*k) | |

approximately equal to sqrt(t), not restricted to a 2^i factor. That | |

ought to smooth out a graph of times against sizes, but may or may not | |

be a net speedup. | |

File: gmp.info, Node: Radix to Binary, Prev: Binary to Radix, Up: Radix Conversion Algorithms | |

15.6.2 Radix to Binary | |

---------------------- | |

*This section needs to be rewritten, it currently describes the | |

algorithms used before GMP 4.3.* | |

Conversions from a power-of-2 radix into binary use a simple and fast | |

O(N) bitwise concatenation algorithm. | |

Conversions from other radices use one of two algorithms. Sizes | |

below `SET_STR_PRECOMPUTE_THRESHOLD' use a basic O(N^2) method. Groups | |

of n digits are converted to limbs, where n is the biggest power of the | |

base b which will fit in a limb, then those groups are accumulated into | |

the result by multiplying by b^n and adding. This saves | |

multi-precision operations, as per Knuth section 4.4 part E (*note | |

References::). Some special case code is provided for decimal, giving | |

the compiler a chance to optimize multiplications by 10. | |

Above `SET_STR_PRECOMPUTE_THRESHOLD' a sub-quadratic algorithm is | |

used. First groups of n digits are converted into limbs. Then adjacent | |

limbs are combined into limb pairs with x*b^n+y, where x and y are the | |

limbs. Adjacent limb pairs are combined into quads similarly with | |

x*b^(2n)+y. This continues until a single block remains, that being | |

the result. | |

The advantage of this method is that the multiplications for each x | |

are big blocks, allowing Karatsuba and higher algorithms to be used. | |

But the cost of calculating the powers b^(n*2^i) must be overcome. | |

`SET_STR_PRECOMPUTE_THRESHOLD' usually ends up quite big, around 5000 | |

digits, and on some processors much bigger still. | |

`SET_STR_PRECOMPUTE_THRESHOLD' is based on the input digits (and | |

tuned for decimal), though it might be better based on a limb count, so | |

as to be independent of the base. But that sort of count isn't used by | |

the base case and so would need some sort of initial calculation or | |

estimate. | |

The main reason `SET_STR_PRECOMPUTE_THRESHOLD' is so much bigger | |

than the corresponding `GET_STR_PRECOMPUTE_THRESHOLD' is that | |

`mpn_mul_1' is much faster than `mpn_divrem_1' (often by a factor of 5, | |

or more). | |

File: gmp.info, Node: Other Algorithms, Next: Assembly Coding, Prev: Radix Conversion Algorithms, Up: Algorithms | |

15.7 Other Algorithms | |

===================== | |

* Menu: | |

* Prime Testing Algorithm:: | |

* Factorial Algorithm:: | |

* Binomial Coefficients Algorithm:: | |

* Fibonacci Numbers Algorithm:: | |

* Lucas Numbers Algorithm:: | |

* Random Number Algorithms:: | |

File: gmp.info, Node: Prime Testing Algorithm, Next: Factorial Algorithm, Prev: Other Algorithms, Up: Other Algorithms | |

15.7.1 Prime Testing | |

-------------------- | |

The primality testing in `mpz_probab_prime_p' (*note Number Theoretic | |

Functions::) first does some trial division by small factors and then | |

uses the Miller-Rabin probabilistic primality testing algorithm, as | |

described in Knuth section 4.5.4 algorithm P (*note References::). | |

For an odd input n, and with n = q*2^k+1 where q is odd, this | |

algorithm selects a random base x and tests whether x^q mod n is 1 or | |

-1, or an x^(q*2^j) mod n is 1, for 1<=j<=k. If so then n is probably | |

prime, if not then n is definitely composite. | |

Any prime n will pass the test, but some composites do too. Such | |

composites are known as strong pseudoprimes to base x. No n is a | |

strong pseudoprime to more than 1/4 of all bases (see Knuth exercise | |

22), hence with x chosen at random there's no more than a 1/4 chance a | |

"probable prime" will in fact be composite. | |

In fact strong pseudoprimes are quite rare, making the test much more | |

powerful than this analysis would suggest, but 1/4 is all that's proven | |

for an arbitrary n. | |

File: gmp.info, Node: Factorial Algorithm, Next: Binomial Coefficients Algorithm, Prev: Prime Testing Algorithm, Up: Other Algorithms | |

15.7.2 Factorial | |

---------------- | |

Factorials are calculated by a combination of two algorithms. An idea is | |

shared among them: to compute the odd part of the factorial; a final | |

step takes account of the power of 2 term, by shifting. | |

For small n, the odd factor of n! is computed with the simple | |

observation that it is equal to the product of all positive odd numbers | |

smaller than n times the odd factor of [n/2]!, where [x] is the integer | |

part of x, and so on recursively. The procedure can be best illustrated | |

with an example, | |

23! = (23.21.19.17.15.13.11.9.7.5.3)(11.9.7.5.3)(5.3)2^19 | |

Current code collects all the factors in a single list, with a loop | |

and no recursion, and compute the product, with no special care for | |

repeated chunks. | |

When n is larger, computation pass trough prime sieving. An helper | |

function is used, as suggested by Peter Luschny: | |

n | |

----- | |

n! | | L(p,n) | |

msf(n) = -------------- = | | p | |

[n/2]!^2.2^k p=3 | |

Where p ranges on odd prime numbers. The exponent k is chosen to | |

obtain an odd integer number: k is the number of 1 bits in the binary | |

representation of [n/2]. The function L(p,n) can be defined as zero | |

when p is composite, and, for any prime p, it is computed with: | |

--- | |

\ n | |

L(p,n) = / [---] mod 2 <= log (n) . | |

--- p^i p | |

i>0 | |

With this helper function, we are able to compute the odd part of n! | |

using the recursion implied by n!=[n/2]!^2*msf(n)*2^k. The recursion | |

stops using the small-n algorithm on some [n/2^i]. | |

Both the above algorithms use binary splitting to compute the | |

product of many small factors. At first as many products as possible | |

are accumulated in a single register, generating a list of factors that | |

fit in a machine word. This list is then split into halves, and the | |

product is computed recursively. | |

Such splitting is more efficient than repeated Nx1 multiplies since | |

it forms big multiplies, allowing Karatsuba and higher algorithms to be | |

used. And even below the Karatsuba threshold a big block of work can | |

be more efficient for the basecase algorithm. | |

File: gmp.info, Node: Binomial Coefficients Algorithm, Next: Fibonacci Numbers Algorithm, Prev: Factorial Algorithm, Up: Other Algorithms | |

15.7.3 Binomial Coefficients | |

---------------------------- | |

Binomial coefficients C(n,k) are calculated by first arranging k <= n/2 | |

using C(n,k) = C(n,n-k) if necessary, and then evaluating the following | |

product simply from i=2 to i=k. | |

k (n-k+i) | |

C(n,k) = (n-k+1) * prod ------- | |

i=2 i | |

It's easy to show that each denominator i will divide the product so | |

far, so the exact division algorithm is used (*note Exact Division::). | |

The numerators n-k+i and denominators i are first accumulated into | |

as many fit a limb, to save multi-precision operations, though for | |

`mpz_bin_ui' this applies only to the divisors, since n is an `mpz_t' | |

and n-k+i in general won't fit in a limb at all. | |

File: gmp.info, Node: Fibonacci Numbers Algorithm, Next: Lucas Numbers Algorithm, Prev: Binomial Coefficients Algorithm, Up: Other Algorithms | |

15.7.4 Fibonacci Numbers | |

------------------------ | |

The Fibonacci functions `mpz_fib_ui' and `mpz_fib2_ui' are designed for | |

calculating isolated F[n] or F[n],F[n-1] values efficiently. | |

For small n, a table of single limb values in `__gmp_fib_table' is | |

used. On a 32-bit limb this goes up to F[47], or on a 64-bit limb up | |

to F[93]. For convenience the table starts at F[-1]. | |

Beyond the table, values are generated with a binary powering | |

algorithm, calculating a pair F[n] and F[n-1] working from high to low | |

across the bits of n. The formulas used are | |

F[2k+1] = 4*F[k]^2 - F[k-1]^2 + 2*(-1)^k | |

F[2k-1] = F[k]^2 + F[k-1]^2 | |

F[2k] = F[2k+1] - F[2k-1] | |

At each step, k is the high b bits of n. If the next bit of n is 0 | |

then F[2k],F[2k-1] is used, or if it's a 1 then F[2k+1],F[2k] is used, | |

and the process repeated until all bits of n are incorporated. Notice | |

these formulas require just two squares per bit of n. | |

It'd be possible to handle the first few n above the single limb | |

table with simple additions, using the defining Fibonacci recurrence | |

F[k+1]=F[k]+F[k-1], but this is not done since it usually turns out to | |

be faster for only about 10 or 20 values of n, and including a block of | |

code for just those doesn't seem worthwhile. If they really mattered | |

it'd be better to extend the data table. | |

Using a table avoids lots of calculations on small numbers, and | |

makes small n go fast. A bigger table would make more small n go fast, | |

it's just a question of balancing size against desired speed. For GMP | |

the code is kept compact, with the emphasis primarily on a good | |

powering algorithm. | |

`mpz_fib2_ui' returns both F[n] and F[n-1], but `mpz_fib_ui' is only | |

interested in F[n]. In this case the last step of the algorithm can | |

become one multiply instead of two squares. One of the following two | |

formulas is used, according as n is odd or even. | |

F[2k] = F[k]*(F[k]+2F[k-1]) | |

F[2k+1] = (2F[k]+F[k-1])*(2F[k]-F[k-1]) + 2*(-1)^k | |

F[2k+1] here is the same as above, just rearranged to be a multiply. | |

For interest, the 2*(-1)^k term both here and above can be applied | |

just to the low limb of the calculation, without a carry or borrow into | |

further limbs, which saves some code size. See comments with | |

`mpz_fib_ui' and the internal `mpn_fib2_ui' for how this is done. | |

File: gmp.info, Node: Lucas Numbers Algorithm, Next: Random Number Algorithms, Prev: Fibonacci Numbers Algorithm, Up: Other Algorithms | |

15.7.5 Lucas Numbers | |

-------------------- | |

`mpz_lucnum2_ui' derives a pair of Lucas numbers from a pair of | |

Fibonacci numbers with the following simple formulas. | |

L[k] = F[k] + 2*F[k-1] | |

L[k-1] = 2*F[k] - F[k-1] | |

`mpz_lucnum_ui' is only interested in L[n], and some work can be | |

saved. Trailing zero bits on n can be handled with a single square | |

each. | |

L[2k] = L[k]^2 - 2*(-1)^k | |

And the lowest 1 bit can be handled with one multiply of a pair of | |

Fibonacci numbers, similar to what `mpz_fib_ui' does. | |

L[2k+1] = 5*F[k-1]*(2*F[k]+F[k-1]) - 4*(-1)^k | |

File: gmp.info, Node: Random Number Algorithms, Prev: Lucas Numbers Algorithm, Up: Other Algorithms | |

15.7.6 Random Numbers | |

--------------------- | |

For the `urandomb' functions, random numbers are generated simply by | |

concatenating bits produced by the generator. As long as the generator | |

has good randomness properties this will produce well-distributed N bit | |

numbers. | |

For the `urandomm' functions, random numbers in a range 0<=R<N are | |

generated by taking values R of ceil(log2(N)) bits each until one | |

satisfies R<N. This will normally require only one or two attempts, | |

but the attempts are limited in case the generator is somehow | |

degenerate and produces only 1 bits or similar. | |

The Mersenne Twister generator is by Matsumoto and Nishimura (*note | |

References::). It has a non-repeating period of 2^19937-1, which is a | |

Mersenne prime, hence the name of the generator. The state is 624 | |

words of 32-bits each, which is iterated with one XOR and shift for each | |

32-bit word generated, making the algorithm very fast. Randomness | |

properties are also very good and this is the default algorithm used by | |

GMP. | |

Linear congruential generators are described in many text books, for | |

instance Knuth volume 2 (*note References::). With a modulus M and | |

parameters A and C, an integer state S is iterated by the formula S <- | |

A*S+C mod M. At each step the new state is a linear function of the | |

previous, mod M, hence the name of the generator. | |

In GMP only moduli of the form 2^N are supported, and the current | |

implementation is not as well optimized as it could be. Overheads are | |

significant when N is small, and when N is large clearly the multiply | |

at each step will become slow. This is not a big concern, since the | |

Mersenne Twister generator is better in every respect and is therefore | |

recommended for all normal applications. | |

For both generators the current state can be deduced by observing | |

enough output and applying some linear algebra (over GF(2) in the case | |

of the Mersenne Twister). This generally means raw output is | |

unsuitable for cryptographic applications without further hashing or | |

the like. | |

File: gmp.info, Node: Assembly Coding, Prev: Other Algorithms, Up: Algorithms | |

15.8 Assembly Coding | |

==================== | |

The assembly subroutines in GMP are the most significant source of | |

speed at small to moderate sizes. At larger sizes algorithm selection | |

becomes more important, but of course speedups in low level routines | |

will still speed up everything proportionally. | |

Carry handling and widening multiplies that are important for GMP | |

can't be easily expressed in C. GCC `asm' blocks help a lot and are | |

provided in `longlong.h', but hand coding low level routines invariably | |

offers a speedup over generic C by a factor of anything from 2 to 10. | |

* Menu: | |

* Assembly Code Organisation:: | |

* Assembly Basics:: | |

* Assembly Carry Propagation:: | |

* Assembly Cache Handling:: | |

* Assembly Functional Units:: | |

* Assembly Floating Point:: | |

* Assembly SIMD Instructions:: | |

* Assembly Software Pipelining:: | |

* Assembly Loop Unrolling:: | |

* Assembly Writing Guide:: | |

File: gmp.info, Node: Assembly Code Organisation, Next: Assembly Basics, Prev: Assembly Coding, Up: Assembly Coding | |

15.8.1 Code Organisation | |

------------------------ | |

The various `mpn' subdirectories contain machine-dependent code, written | |

in C or assembly. The `mpn/generic' subdirectory contains default code, | |

used when there's no machine-specific version of a particular file. | |

Each `mpn' subdirectory is for an ISA family. Generally 32-bit and | |

64-bit variants in a family cannot share code and have separate | |

directories. Within a family further subdirectories may exist for CPU | |

variants. | |

In each directory a `nails' subdirectory may exist, holding code with | |

nails support for that CPU variant. A `NAILS_SUPPORT' directive in each | |

file indicates the nails values the code handles. Nails code only | |

exists where it's faster, or promises to be faster, than plain code. | |

There's no effort put into nails if they're not going to enhance a | |

given CPU. | |

File: gmp.info, Node: Assembly Basics, Next: Assembly Carry Propagation, Prev: Assembly Code Organisation, Up: Assembly Coding | |

15.8.2 Assembly Basics | |

---------------------- | |

`mpn_addmul_1' and `mpn_submul_1' are the most important routines for | |

overall GMP performance. All multiplications and divisions come down to | |

repeated calls to these. `mpn_add_n', `mpn_sub_n', `mpn_lshift' and | |

`mpn_rshift' are next most important. | |

On some CPUs assembly versions of the internal functions | |

`mpn_mul_basecase' and `mpn_sqr_basecase' give significant speedups, | |

mainly through avoiding function call overheads. They can also | |

potentially make better use of a wide superscalar processor, as can | |

bigger primitives like `mpn_addmul_2' or `mpn_addmul_4'. | |

The restrictions on overlaps between sources and destinations (*note | |

Low-level Functions::) are designed to facilitate a variety of | |

implementations. For example, knowing `mpn_add_n' won't have partly | |

overlapping sources and destination means reading can be done far ahead | |

of writing on superscalar processors, and loops can be vectorized on a | |

vector processor, depending on the carry handling. | |

File: gmp.info, Node: Assembly Carry Propagation, Next: Assembly Cache Handling, Prev: Assembly Basics, Up: Assembly Coding | |

15.8.3 Carry Propagation | |

------------------------ | |

The problem that presents most challenges in GMP is propagating carries | |

from one limb to the next. In functions like `mpn_addmul_1' and | |

`mpn_add_n', carries are the only dependencies between limb operations. | |

On processors with carry flags, a straightforward CISC style `adc' is | |

generally best. AMD K6 `mpn_addmul_1' however is an example of an | |

unusual set of circumstances where a branch works out better. | |

On RISC processors generally an add and compare for overflow is | |

used. This sort of thing can be seen in `mpn/generic/aors_n.c'. Some | |

carry propagation schemes require 4 instructions, meaning at least 4 | |

cycles per limb, but other schemes may use just 1 or 2. On wide | |

superscalar processors performance may be completely determined by the | |

number of dependent instructions between carry-in and carry-out for | |

each limb. | |

On vector processors good use can be made of the fact that a carry | |

bit only very rarely propagates more than one limb. When adding a | |

single bit to a limb, there's only a carry out if that limb was | |

`0xFF...FF' which on random data will be only 1 in 2^mp_bits_per_limb. | |

`mpn/cray/add_n.c' is an example of this, it adds all limbs in | |

parallel, adds one set of carry bits in parallel and then only rarely | |

needs to fall through to a loop propagating further carries. | |

On the x86s, GCC (as of version 2.95.2) doesn't generate | |

particularly good code for the RISC style idioms that are necessary to | |

handle carry bits in C. Often conditional jumps are generated where | |

`adc' or `sbb' forms would be better. And so unfortunately almost any | |

loop involving carry bits needs to be coded in assembly for best | |

results. | |

File: gmp.info, Node: Assembly Cache Handling, Next: Assembly Functional Units, Prev: Assembly Carry Propagation, Up: Assembly Coding | |

15.8.4 Cache Handling | |

--------------------- | |

GMP aims to perform well both on operands that fit entirely in L1 cache | |

and those which don't. | |

Basic routines like `mpn_add_n' or `mpn_lshift' are often used on | |

large operands, so L2 and main memory performance is important for them. | |

`mpn_mul_1' and `mpn_addmul_1' are mostly used for multiply and square | |

basecases, so L1 performance matters most for them, unless assembly | |

versions of `mpn_mul_basecase' and `mpn_sqr_basecase' exist, in which | |

case the remaining uses are mostly for larger operands. | |

For L2 or main memory operands, memory access times will almost | |

certainly be more than the calculation time. The aim therefore is to | |

maximize memory throughput, by starting a load of the next cache line | |

while processing the contents of the previous one. Clearly this is | |

only possible if the chip has a lock-up free cache or some sort of | |

prefetch instruction. Most current chips have both these features. | |

Prefetching sources combines well with loop unrolling, since a | |

prefetch can be initiated once per unrolled loop (or more than once if | |

the loop covers more than one cache line). | |

On CPUs without write-allocate caches, prefetching destinations will | |

ensure individual stores don't go further down the cache hierarchy, | |

limiting bandwidth. Of course for calculations which are slow anyway, | |

like `mpn_divrem_1', write-throughs might be fine. | |

The distance ahead to prefetch will be determined by memory latency | |

versus throughput. The aim of course is to have data arriving | |

continuously, at peak throughput. Some CPUs have limits on the number | |

of fetches or prefetches in progress. | |

If a special prefetch instruction doesn't exist then a plain load | |

can be used, but in that case care must be taken not to attempt to read | |

past the end of an operand, since that might produce a segmentation | |

violation. | |

Some CPUs or systems have hardware that detects sequential memory | |

accesses and initiates suitable cache movements automatically, making | |

life easy. | |

File: gmp.info, Node: Assembly Functional Units, Next: Assembly Floating Point, Prev: Assembly Cache Handling, Up: Assembly Coding | |

15.8.5 Functional Units | |

----------------------- | |

When choosing an approach for an assembly loop, consideration is given | |

to what operations can execute simultaneously and what throughput can | |

thereby be achieved. In some cases an algorithm can be tweaked to | |

accommodate available resources. | |

Loop control will generally require a counter and pointer updates, | |

costing as much as 5 instructions, plus any delays a branch introduces. | |

CPU addressing modes might reduce pointer updates, perhaps by allowing | |

just one updating pointer and others expressed as offsets from it, or | |

on CISC chips with all addressing done with the loop counter as a | |

scaled index. | |

The final loop control cost can be amortised by processing several | |

limbs in each iteration (*note Assembly Loop Unrolling::). This at | |

least ensures loop control isn't a big fraction 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. | |

File: gmp.info, Node: Assembly Floating Point, Next: Assembly SIMD Instructions, Prev: Assembly Functional Units, Up: Assembly Coding | |

15.8.6 Floating Point | |

--------------------- | |

Floating point arithmetic is used in GMP for multiplications on CPUs | |

with poor integer multipliers. It's mostly useful for `mpn_mul_1', | |

`mpn_addmul_1' and `mpn_submul_1' on 64-bit machines, and | |

`mpn_mul_basecase' on both 32-bit and 64-bit machines. | |

With IEEE 53-bit double precision floats, integer multiplications | |

producing up to 53 bits will give exact results. Breaking a 64x64 | |

multiplication into eight 16x32->48 bit pieces is convenient. With | |

some care though six 21x32->53 bit products can be used, if one of the | |

lower two 21-bit pieces also uses the sign bit. | |

For the `mpn_mul_1' family of functions on a 64-bit machine, the | |

invariant single limb is split at the start, into 3 or 4 pieces. | |

Inside the loop, the bignum operand is split into 32-bit pieces. Fast | |

conversion of these unsigned 32-bit pieces to floating point is highly | |

machine-dependent. In some cases, reading the data into the integer | |

unit, zero-extending to 64-bits, then transferring to the floating | |

point unit back via memory is the only option. | |

Converting partial products back to 64-bit limbs is usually best | |

done as a signed conversion. Since all values are smaller than 2^53, | |

signed and unsigned are the same, but most processors lack unsigned | |

conversions. | |

Here is a diagram showing 16x32 bit products for an `mpn_mul_1' or | |

`mpn_addmul_1' with a 64-bit limb. The single limb operand V is split | |

into four 16-bit parts. The multi-limb operand U is split in the loop | |

into two 32-bit parts. | |

+---+---+---+---+ | |

|v48|v32|v16|v00| V operand | |

+---+---+---+---+ | |

+-------+---+---+ | |

x | u32 | u00 | U operand (one limb) | |

+---------------+ | |

--------------------------------- | |

+-----------+ | |

| u00 x v00 | p00 48-bit products | |

+-----------+ | |

+-----------+ | |

| u00 x v16 | p16 | |

+-----------+ | |

+-----------+ | |

| u00 x v32 | p32 | |

+-----------+ | |

+-----------+ | |

| u00 x v48 | p48 | |

+-----------+ | |

+-----------+ | |

| u32 x v00 | r32 | |

+-----------+ | |

+-----------+ | |

| u32 x v16 | r48 | |

+-----------+ | |

+-----------+ | |

| u32 x v32 | r64 | |

+-----------+ | |

+-----------+ | |

| u32 x v48 | r80 | |

+-----------+ | |

p32 and r32 can be summed using floating-point addition, and | |

likewise p48 and r48. p00 and p16 can be summed with r64 and r80 from | |

the previous iteration. | |

For each loop then, four 49-bit quantities are transferred to the | |

integer unit, aligned as follows, | |

|-----64bits----|-----64bits----| | |

+------------+ | |

| p00 + r64' | i00 | |

+------------+ | |

+------------+ | |

| p16 + r80' | i16 | |

+------------+ | |

+------------+ | |

| p32 + r32 | i32 | |

+------------+ | |

+------------+ | |

| p48 + r48 | i48 | |

+------------+ | |

The challenge then is to sum these efficiently and add in a carry | |

limb, generating a low 64-bit result limb and a high 33-bit carry limb | |

(i48 extends 33 bits into the high half). | |

File: gmp.info, Node: Assembly SIMD Instructions, Next: Assembly Software Pipelining, Prev: Assembly Floating Point, Up: Assembly Coding | |

15.8.7 SIMD Instructions | |

------------------------ | |

The single-instruction multiple-data support in current microprocessors | |

is aimed at signal processing algorithms where each data point can be | |

treated more or less independently. There's generally not much support | |

for propagating the sort of carries that arise in GMP. | |

SIMD multiplications of say four 16x16 bit multiplies only do as much | |

work as one 32x32 from GMP's point of view, and need some shifts and | |

adds besides. But of course if say the SIMD form is fully pipelined | |

and uses less instruction decoding then it may still be worthwhile. | |

On the x86 chips, MMX has so far found a use in `mpn_rshift' and | |

`mpn_lshift', and is used in a special case for 16-bit multipliers in | |

the P55 `mpn_mul_1'. SSE2 is used for Pentium 4 `mpn_mul_1', | |

`mpn_addmul_1', and `mpn_submul_1'. | |

File: gmp.info, Node: Assembly Software Pipelining, Next: Assembly Loop Unrolling, Prev: Assembly SIMD Instructions, Up: Assembly Coding | |

15.8.8 Software Pipelining | |

-------------------------- | |

Software pipelining consists of scheduling instructions around the | |

branch point in a loop. For example a loop might issue a load not for | |

use in the present iteration but the next, thereby allowing extra | |

cycles for the data to arrive from memory. | |

Naturally this is wanted only when doing things like loads or | |

multiplies that take several cycles to complete, and only where a CPU | |

has multiple functional units so that other work can be done in the | |

meantime. | |

A pipeline with several stages will have a data value in progress at | |

each stage and each loop iteration moves them along one stage. This is | |

like juggling. | |

If the latency of some instruction is greater than the loop time | |

then it will be necessary to unroll, so one register has a result ready | |

to use while another (or multiple others) are still in progress. | |

(*note Assembly Loop Unrolling::). | |

File: gmp.info, Node: Assembly Loop Unrolling, Next: Assembly Writing Guide, Prev: Assembly Software Pipelining, Up: Assembly Coding | |

15.8.9 Loop Unrolling | |

--------------------- | |

Loop unrolling consists of replicating code so that several limbs are | |

processed in each loop. At a minimum this reduces loop overheads by a | |

corresponding factor, but it can also allow better register usage, for | |

example alternately using one register combination and then another. | |

Judicious use of `m4' macros can help avoid lots of duplication in the | |

source code. | |

Any amount of unrolling can be handled with a loop counter that's | |

decremented by N each time, stopping when the remaining count is less | |

than the further N the loop will process. Or by subtracting N at the | |

start, the termination condition becomes when the counter C is less | |

than 0 (and the count of remaining limbs is C+N). | |

Alternately for a power of 2 unroll the loop count and remainder can | |

be established with a shift and mask. This is convenient if also | |

making a computed jump into the middle of a large loop. | |

The limbs not a multiple of the unrolling can be handled in various | |

ways, for example | |

* A simple loop at the end (or the start) to process the excess. | |

Care will be wanted that it isn't too much slower than the | |

unrolled part. | |

* A set of binary tests, for example after an 8-limb unrolling, test | |

for 4 more limbs to process, then a further 2 more or not, and | |

finally 1 more or not. This will probably take more code space | |

than a simple loop. | |

* A `switch' statement, providing separate code for each possible | |

excess, for example an 8-limb unrolling would have separate code | |

for 0 remaining, 1 remaining, etc, up to 7 remaining. This might | |

take a lot of code, but may be the best way to optimize all cases | |

in combination with a deep pipelined loop. | |

* A computed jump into the middle of the loop, thus making the first | |

iteration handle the excess. This should make times smoothly | |

increase with size, which is attractive, but setups for the jump | |

and adjustments for pointers can be tricky and could become quite | |

difficult in combination with deep pipelining. | |

File: gmp.info, Node: Assembly Writing Guide, Prev: Assembly Loop Unrolling, Up: Assembly Coding | |

15.8.10 Writing Guide | |

--------------------- | |

This is a guide to writing software pipelined loops for processing limb | |

vectors in assembly. | |

First determine the algorithm and which instructions are needed. | |

Code it without unrolling or scheduling, to make sure it works. On a | |

3-operand CPU try to write each new value to a new register, this will | |

greatly simplify later steps. | |

Then note for each instruction the functional unit and/or issue port | |

requirements. If an instruction can use either of two units, like U0 | |

or U1 then make a category "U0/U1". Count the total using each unit | |

(or combined unit), and count all instructions. | |

Figure out from those counts the best possible loop time. The goal | |

will be to find a perfect schedule where instruction latencies are | |

completely hidden. The total instruction count might be the limiting | |

factor, or perhaps a particular functional unit. It might be possible | |

to tweak the instructions to help the limiting factor. | |

Suppose the loop time is N, then make N issue buckets, with the | |

final loop branch at the end of the last. Now fill the buckets with | |

dummy instructions using the functional units desired. Run this to | |

make sure the intended speed is reached. | |

Now replace the dummy instructions with the real instructions from | |

the slow but correct loop you started with. The first will typically | |

be a load instruction. Then the instruction using that value is placed | |

in a bucket an appropriate distance down. Run the loop again, to check | |

it still runs at target speed. | |

Keep placing instructions, frequently measuring the loop. After a | |

few you will need to wrap around from the last bucket back to the top | |

of the loop. If you used the new-register for new-value strategy above | |

then there will be no register conflicts. If not then take care not to | |

clobber something already in use. Changing registers at this time is | |

very error prone. | |

The loop will overlap two or more of the original loop iterations, | |

and the computation of one vector element result will be started in one | |

iteration of the new loop, and completed one or several iterations | |

later. | |

The final step is to create feed-in and wind-down code for the loop. | |

A good way to do this is to make a copy (or copies) of the loop at the | |

start and delete those instructions which don't have valid antecedents, | |

and at the end replicate and delete those whose results are unwanted | |

(including any further loads). | |

The loop will have a minimum number of limbs loaded and processed, | |

so the feed-in code must test if the request size is smaller and skip | |

either to a suitable part of the wind-down or to special code for small | |

sizes. | |

File: gmp.info, Node: Internals, Next: Contributors, Prev: Algorithms, Up: Top | |

16 Internals | |

************ | |

*This chapter is provided only for informational purposes and the | |

various internals described here may change in future GMP releases. | |

Applications expecting to be compatible with future releases should use | |

only the documented interfaces described in previous chapters.* | |

* Menu: | |

* Integer Internals:: | |

* Rational Internals:: | |

* Float Internals:: | |

* Raw Output Internals:: | |

* C++ Interface Internals:: | |

File: gmp.info, Node: Integer Internals, Next: Rational Internals, Prev: Internals, Up: Internals | |

16.1 Integer Internals | |

====================== | |

`mpz_t' variables represent integers using sign and magnitude, in space | |

dynamically allocated and reallocated. The fields are as follows. | |

`_mp_size' | |

The number of limbs, or the negative of that when representing a | |

negative integer. Zero is represented by `_mp_size' set to zero, | |

in which case the `_mp_d' data is 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. | |

File: gmp.info, Node: Rational Internals, Next: Float Internals, Prev: Integer Internals, Up: Internals | |

16.2 Rational Internals | |

======================= | |

`mpq_t' variables represent rationals using an `mpz_t' numerator and | |

denominator (*note Integer Internals::). | |

The canonical form adopted is denominator positive (and non-zero), | |

no common factors between numerator and denominator, and zero uniquely | |

represented as 0/1. | |

It's believed that casting out common factors at each stage of a | |

calculation is best in general. A GCD is an O(N^2) operation so it's | |

better to do a few small ones immediately than to delay and have to do | |

a big one later. Knowing the numerator and denominator have no common | |

factors can be used for example in `mpq_mul' to make only two cross | |

GCDs necessary, not four. | |

This general approach to common factors is badly sub-optimal in the | |

presence of simple factorizations or little prospect for cancellation, | |

but GMP has no way to know when this will occur. As per *Note | |

Efficiency::, that's left to applications. The `mpq_t' framework might | |

still suit, with `mpq_numref' and `mpq_denref' for direct access to the | |

numerator and denominator, or of course `mpz_t' variables can be used | |

directly. | |

File: gmp.info, Node: Float Internals, Next: Raw Output Internals, Prev: Rational Internals, Up: Internals | |

16.3 Float Internals | |

==================== | |

Efficient calculation is the primary aim of GMP floats and the use of | |

whole limbs and simple rounding facilitates this. | |

`mpf_t' floats have a variable precision mantissa and a single | |

machine word signed exponent. The mantissa is represented using sign | |

and magnitude. | |

most least | |

significant significant | |

limb limb | |

_mp_d | |

|---- _mp_exp ---> | | |

_____ _____ _____ _____ _____ | |

|_____|_____|_____|_____|_____| | |

. <------------ radix point | |

<-------- _mp_size ---------> | |

The fields are as follows. | |

`_mp_size' | |

The number of limbs currently in use, or the negative of that when | |

representing a negative value. Zero is represented by `_mp_size' | |

and `_mp_exp' both set to zero, and in that case the `_mp_d' data | |

is unused. (In the future `_mp_exp' might be undefined when | |

representing zero.) | |

`_mp_prec' | |

The precision of the mantissa, in limbs. In any calculation the | |

aim is to produce `_mp_prec' limbs of result (the most significant | |

being non-zero). | |

`_mp_d' | |

A pointer to the array of limbs which is the absolute value of the | |

mantissa. These are stored "little endian" as per the `mpn' | |

functions, so `_mp_d[0]' is the least significant limb and | |

`_mp_d[ABS(_mp_size)-1]' the most significant. | |

The most significant limb is always non-zero, but there are no | |

other restrictions on its value, in particular the highest 1 bit | |

can be anywhere within the limb. | |

`_mp_prec+1' limbs are allocated to `_mp_d', the extra limb being | |

for convenience (see below). There are no reallocations during a | |

calculation, only in a change of precision with `mpf_set_prec'. | |

`_mp_exp' | |

The exponent, in limbs, determining the location of the implied | |

radix point. Zero means the radix point is just above the most | |

significant limb. Positive values mean a radix point offset | |

towards the lower limbs and hence a value >= 1, as for example in | |

the diagram above. Negative exponents mean a radix point further | |

above the highest limb. | |

Naturally the exponent can be any value, it doesn't have to fall | |

within the limbs as the diagram shows, it can be a long way above | |

or a long way below. Limbs other than those included in the | |

`{_mp_d,_mp_size}' data are treated as zero. | |

The `_mp_size' and `_mp_prec' fields are `int', although the | |

`mp_size_t' type is usually a `long'. The `_mp_exp' field is usually | |

`long'. This is done to make some fields just 32 bits on some 64 bits | |

systems, thereby saving a few bytes of data space but still providing | |

plenty of precision and a very large range. | |

The following various points should be noted. | |

Low Zeros | |

The least significant limbs `_mp_d[0]' etc can be zero, though | |

such low zeros can always be ignored. Routines likely to produce | |

low zeros check and avoid them to save time in subsequent | |

calculations, but for most routines they're quite unlikely and | |

aren't checked. | |

Mantissa Size Range | |

The `_mp_size' count of limbs in use can be less than `_mp_prec' if | |

the value can be represented in less. This means low precision | |

values or small integers stored in a high precision `mpf_t' can | |

still be operated on efficiently. | |

`_mp_size' can also be greater than `_mp_prec'. Firstly a value is | |

allowed to use all of the `_mp_prec+1' limbs available at `_mp_d', | |

and secondly when `mpf_set_prec_raw' lowers `_mp_prec' it leaves | |

`_mp_size' unchanged and so the size can be arbitrarily bigger than | |

`_mp_prec'. | |

Rounding | |

All rounding is done on limb boundaries. Calculating `_mp_prec' | |

limbs with the high non-zero will ensure the application requested | |

minimum precision is obtained. | |

The use of simple "trunc" rounding towards zero is efficient, | |

since there's no need to examine extra limbs and increment or | |

decrement. | |

Bit Shifts | |

Since the exponent is in limbs, there are no bit shifts in basic | |

operations like `mpf_add' and `mpf_mul'. When differing exponents | |

are encountered all that's needed is to adjust pointers to line up | |

the relevant limbs. | |

Of course `mpf_mul_2exp' and `mpf_div_2exp' will require bit | |

shifts, but the choice is between an exponent in limbs which | |

requires shifts there, or one in bits which requires them almost | |

everywhere else. | |

Use of `_mp_prec+1' Limbs | |

The extra limb on `_mp_d' (`_mp_prec+1' rather than just | |

`_mp_prec') helps when an `mpf' routine might get a carry from its | |

operation. `mpf_add' for instance will do an `mpn_add' of | |

`_mp_prec' limbs. If there's no carry then that's the result, but | |

if there is a carry then it's stored in the extra limb of space and | |

`_mp_size' becomes `_mp_prec+1'. | |

Whenever `_mp_prec+1' limbs are held in a variable, the low limb | |

is not needed for the intended precision, only the `_mp_prec' high | |

limbs. But zeroing it out or moving the rest down is unnecessary. | |

Subsequent routines reading the value will simply take the high | |

limbs they need, and this will be `_mp_prec' if their target has | |

that same precision. This is no more than a pointer adjustment, | |

and must be checked anyway since the destination precision can be | |

different from the sources. | |

Copy functions like `mpf_set' will retain a full `_mp_prec+1' limbs | |

if available. This ensures that a variable which has `_mp_size' | |

equal to `_mp_prec+1' will get its full exact value copied. | |

Strictly speaking this is unnecessary since only `_mp_prec' limbs | |

are needed for the application's requested precision, but it's | |

considered that an `mpf_set' from one variable into another of the | |

same precision ought to produce an exact copy. | |

Application Precisions | |

`__GMPF_BITS_TO_PREC' converts an application requested precision | |

to an `_mp_prec'. The value in bits is rounded up to a whole limb | |

then an extra limb is added since the most significant limb of | |

`_mp_d' is only non-zero and therefore might contain only one bit. | |

`__GMPF_PREC_TO_BITS' does the reverse conversion, and removes the | |

extra limb from `_mp_prec' before converting to bits. The net | |

effect of reading back with `mpf_get_prec' is simply the precision | |

rounded up to a multiple of `mp_bits_per_limb'. | |

Note that the extra limb added here for the high only being | |

non-zero is in addition to the extra limb allocated to `_mp_d'. | |

For example with a 32-bit limb, an application request for 250 | |

bits will be rounded up to 8 limbs, then an extra added for the | |

high being only non-zero, giving an `_mp_prec' of 9. `_mp_d' then | |

gets 10 limbs allocated. Reading back with `mpf_get_prec' will | |

take `_mp_prec' subtract 1 limb and multiply by 32, giving 256 | |

bits. | |

Strictly speaking, the fact the high limb has at least one bit | |

means that a float with, say, 3 limbs of 32-bits each will be | |

holding at least 65 bits, but for the purposes of `mpf_t' it's | |

considered simply to be 64 bits, a nice multiple of the limb size. | |

File: gmp.info, Node: Raw Output Internals, Next: C++ Interface Internals, Prev: Float Internals, Up: Internals | |

16.4 Raw Output Internals | |

========================= | |

`mpz_out_raw' uses the following format. | |

+------+------------------------+ | |

| size | data bytes | | |

+------+------------------------+ | |

The size is 4 bytes written most significant byte first, being the | |

number of subsequent data bytes, or the 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'. | |

File: gmp.info, Node: C++ Interface Internals, Prev: Raw Output Internals, Up: Internals | |

16.5 C++ Interface Internals | |

============================ | |

A system of expression templates is used to ensure something like | |

`a=b+c' turns into a simple call to `mpz_add' etc. For `mpf_class' the | |

scheme also ensures the precision of the final destination is used for | |

any temporaries within a statement like `f=w*x+y*z'. These are | |

important features which a naive implementation cannot provide. | |

A simplified description of the scheme follows. The true scheme is | |

complicated by the fact that expressions have different return types. | |

For detailed information, refer to the source code. | |

To perform an operation, say, addition, we first define a "function | |

object" evaluating it, | |

struct __gmp_binary_plus | |

{ | |

static void eval(mpf_t f, const mpf_t g, const mpf_t h) | |

{ | |

mpf_add(f, g, h); | |

} | |

}; | |

And an "additive expression" object, | |

__gmp_expr<__gmp_binary_expr<mpf_class, mpf_class, __gmp_binary_plus> > | |

operator+(const mpf_class &f, const mpf_class &g) | |

{ | |

return __gmp_expr | |

<__gmp_binary_expr<mpf_class, mpf_class, __gmp_binary_plus> >(f, g); | |

} | |

The seemingly redundant `__gmp_expr<__gmp_binary_expr<...>>' is used | |

to encapsulate any possible kind of expression into a single template | |

type. In fact even `mpf_class' etc are `typedef' specializations of | |

`__gmp_expr'. | |

Next we define assignment of `__gmp_expr' to `mpf_class'. | |

template <class T> | |

mpf_class & mpf_class::operator=(const __gmp_expr<T> &expr) | |

{ | |

expr.eval(this->get_mpf_t(), this->precision()); | |

return *this; | |

} | |

template <class Op> | |

void __gmp_expr<__gmp_binary_expr<mpf_class, mpf_class, Op> >::eval | |

(mpf_t f, mp_bitcnt_t precision) | |

{ | |

Op::eval(f, expr.val1.get_mpf_t(), expr.val2.get_mpf_t()); | |

} | |

where `expr.val1' and `expr.val2' are references to the expression's | |

operands (here `expr' is the `__gmp_binary_expr' stored within the | |

`__gmp_expr'). | |

This way, the expression is actually evaluated only at the time of | |

assignment, when the required precision (that of `f') is known. | |

Furthermore the target `mpf_t' is now available, thus we can call | |

`mpf_add' directly with `f' as the output argument. | |

Compound expressions are handled by defining operators taking | |

subexpressions as their arguments, like this: | |

template <class T, class U> | |

__gmp_expr | |

<__gmp_binary_expr<__gmp_expr<T>, __gmp_expr<U>, __gmp_binary_plus> > | |

operator+(const __gmp_expr<T> &expr1, const __gmp_expr<U> &expr2) | |

{ | |

return __gmp_expr | |

<__gmp_binary_expr<__gmp_expr<T>, __gmp_expr<U>, __gmp_binary_plus> > | |

(expr1, expr2); | |

} | |

And the corresponding specializations of `__gmp_expr::eval': | |

template <class T, class U, class Op> | |

void __gmp_expr | |

<__gmp_binary_expr<__gmp_expr<T>, __gmp_expr<U>, Op> >::eval | |

(mpf_t f, mp_bitcnt_t precision) | |

{ | |

// declare two temporaries | |

mpf_class temp1(expr.val1, precision), temp2(expr.val2, precision); | |

Op::eval(f, temp1.get_mpf_t(), temp2.get_mpf_t()); | |

} | |

The expression is thus recursively evaluated to any level of | |

complexity and all subexpressions are evaluated to the precision of `f'. | |

File: gmp.info, Node: Contributors, Next: References, Prev: Internals, Up: Top | |

Appendix A Contributors | |

*********************** | |

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, extended GCD and jacobi | |

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, and he is the main author of the | |

mini-gmp package used for gmp bootstrapping. | |

Alberto Zanoni and Marco Bodrato suggested the unbalanced multiply | |

strategy, and found the optimal strategies for evaluation and | |

interpolation in Toom multiplication. | |

Marco Bodrato helped implement the new Toom multiply code for GMP | |

4.3 and implemented most of the new Toom multiply and squaring code for | |

5.0. He is the main author of the current mpn_mulmod_bnm1, | |

mpn_mullo_n, and mpn_sqrlo. Marco also wrote the functions mpn_invert | |

and mpn_invertappr, and improved the speed of integer root extraction. | |

He is the author of the current combinatorial functions: binomial, | |

factorial, multifactorial, primorial. | |

David Harvey suggested the internal function `mpn_bdiv_dbm1', | |

implementing division relevant to Toom multiplication. He also worked | |

on fast assembly sequences, in particular on a fast AMD64 | |

`mpn_mul_basecase'. He wrote the internal middle product functions | |

`mpn_mulmid_basecase', `mpn_toom42_mulmid', `mpn_mulmid_n' and related | |

helper routines. | |

Martin Boij wrote `mpn_perfect_power_p'. | |

Marc Glisse improved `gmpxx.h': use fewer temporaries (faster), | |

specializations of `numeric_limits' and `common_type', C++11 features | |

(move constructors, explicit bool conversion, UDL), make the conversion | |

from `mpq_class' to `mpz_class' explicit, optimize operations where one | |

argument is a small compile-time constant, replace some heap | |

allocations by stack allocations. He also fixed the eofbit handling of | |

C++ streams, and removed one division from `mpq/aors.c'. | |

David S Miller wrote assembly code for SPARC T3 and T4. | |

Mark Sofroniou cleaned up the types of mul_fft.c, letting it work | |

for huge operands. | |

Ulrich Weigand ported GMP to the powerpc64le ABI. | |

(This list is chronological, not ordered after significance. If you | |

have contributed to GMP but are not listed above, please tell | |

<gmp-devel@gmplib.org> about the omission!) | |

The development of floating point functions of GNU MP 2, 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.0 was supported in part by the | |

IDA Center for Computing Sciences. | |

The development of GMP 4.3, 5.0, and 5.1 was supported in part by | |

the Swedish Foundation for Strategic Research. | |

Thanks go to Hans Thorsen for donating an SGI system for the GMP | |

test system environment. | |

File: gmp.info, Node: References, Next: GNU Free Documentation License, Prev: Contributors, Up: Top | |

Appendix B References | |

********************* | |

B.1 Books | |

========= | |

* Jonathan M. Borwein and Peter B. Borwein, "Pi and the AGM: A Study | |

in Analytic Number Theory and Computational Complexity", Wiley, | |

1998. | |

* Richard Crandall and Carl Pomerance, "Prime Numbers: A | |

Computational Perspective", 2nd edition, Springer-Verlag, 2005. | |

`http://www.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 `https://gcc.gnu.org/onlinedocs/', and in the GCC | |

package `https://ftp.gnu.org/gnu/gcc/' | |

B.2 Papers | |

========== | |

* Yves Bertot, Nicolas Magaud and Paul Zimmermann, "A Proof of GMP | |

Square Root", Journal of Automated Reasoning, volume 29, 2002, pp. | |

225-252. Also available online as INRIA Research Report 4475, | |

June 2002, `http://hal.inria.fr/docs/00/07/21/13/PDF/RR-4475.pdf' | |

* Christoph Burnikel and Joachim Ziegler, "Fast Recursive Division", | |

Max-Planck-Institut fuer Informatik Research Report MPI-I-98-1-022, | |

`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 | |

`https://gmplib.org/~tege/divcnst-pldi94.pdf'. | |

* Niels Mo"ller and Torbjo"rn Granlund, "Improved division by | |

invariant integers", IEEE Transactions on Computers, 11 June 2010. | |

`https://gmplib.org/~tege/division-paper.pdf' | |

* 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://hal.inria.fr/inria-00072854/PDF/RR-3805.pdf' | |

* 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. | |

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-2002, 2007, 2008 Free Software Foundation, Inc. | |

`http://fsf.org/' | |

Everyone is permitted to copy and distribute verbatim copies | |

of this license document, but changing it is not allowed. | |

0. PREAMBLE | |

The purpose of this License is to make a manual, textbook, or other | |

functional and useful document "free" in the sense of freedom: to | |

assure everyone the effective freedom to copy and redistribute it, | |

with or without modifying it, either commercially or | |

noncommercially. Secondarily, this License preserves for the | |

author and publisher a way to get credit for their work, while not | |

being considered responsible for modifications made by others. | |

This License is a kind of "copyleft", which means that derivative | |

works of the document must themselves be free in the same sense. | |

It complements the GNU General Public License, which is a copyleft | |

license designed for free software. | |

We have designed this License in order to use it for manuals for | |

free software, because free software needs free documentation: a | |

free program should come with manuals providing the same freedoms | |

that the software does. But this License is not limited to | |

software manuals; it can be used for any textual work, regardless | |

of subject matter or whether it is published as a printed book. | |

We recommend this License principally for works whose purpose is | |

instruction or reference. | |

1. APPLICABILITY AND DEFINITIONS | |

This License applies to any manual or other work, in any medium, | |

that contains a notice placed by the copyright holder saying it | |

can be distributed under the terms of this License. Such a notice | |

grants a world-wide, royalty-free license, unlimited in duration, | |

to use that work under the conditions stated herein. The | |

"Document", below, refers to any such manual or work. Any member | |

of the public is a licensee, and is addressed as "you". You | |

accept the license if you copy, modify or distribute the work in a | |

way requiring permission under copyright law. | |

A "Modified Version" of the Document means any work containing the | |

Document or a portion of it, either copied verbatim, or with | |

modifications and/or translated into another language. | |

A "Secondary Section" is a named appendix or a front-matter section | |

of the Document that deals exclusively with the relationship of the | |

publishers or authors of the Document to the Document's overall | |

subject (or to related matters) and contains nothing that could | |

fall directly within that overall subject. (Thus, if the Document | |

is in part a textbook of mathematics, a Secondary Section may not | |

explain any mathematics.) The relationship could be a matter of | |

historical connection with the subject or with related matters, or | |

of legal, commercial, philosophical, ethical or political position | |

regarding them. | |

The "Invariant Sections" are certain Secondary Sections whose | |

titles are designated, as being those of Invariant Sections, in | |

the notice that says that the Document is released under this | |

License. If a section does not fit the above definition of | |

Secondary then it is not allowed to be designated as Invariant. | |

The Document may contain zero Invariant Sections. If the Document | |

does not identify any Invariant Sections then there are none. | |

The "Cover Texts" are certain short passages of text that are | |

listed, as Front-Cover Texts or Back-Cover Texts, in the notice | |

that says that the Document is released under this License. A | |

Front-Cover Text may be at most 5 words, and a Back-Cover Text may | |

be at most 25 words. | |

A "Transparent" copy of the Document means a machine-readable copy, | |

represented in a format whose specification is available to the | |

general public, that is suitable for revising the document | |

straightforwardly with generic text editors or (for images | |

composed of pixels) generic paint programs or (for drawings) some | |

widely available drawing editor, and that is suitable for input to | |

text formatters or for automatic translation to a variety of | |

formats suitable for input to text formatters. A copy made in an | |

otherwise Transparent file format whose markup, or absence of | |

markup, has been arranged to thwart or discourage subsequent | |

modification by readers is not Transparent. An image format is | |

not Transparent if used for any substantial amount of text. A | |

copy that is not "Transparent" is called "Opaque". | |

Examples of suitable formats for Transparent copies include plain | |

ASCII without markup, Texinfo input format, LaTeX input format, | |

SGML or XML using a publicly available DTD, and | |

standard-conforming simple HTML, PostScript or PDF designed for | |

human modification. Examples of transparent image formats include | |

PNG, XCF and JPG. Opaque formats include proprietary formats that | |

can be read and edited only by proprietary word processors, SGML or | |

XML for which the DTD and/or processing tools are not generally | |

available, and the machine-generated HTML, PostScript or PDF | |

produced by some word processors for output purposes only. | |

The "Title Page" means, for a printed book, the title page itself, | |

plus such following pages as are needed to hold, legibly, the | |

material this License requires to appear in the title page. For | |

works in formats which do not have any title page as such, "Title | |

Page" means the text near the most prominent appearance of the | |

work's title, preceding the beginning of the body of the text. | |

The "publisher" means any person or entity that distributes copies | |

of the Document to the public. | |

A section "Entitled XYZ" means a named subunit of the Document | |

whose title either is precisely XYZ or contains XYZ in parentheses | |

following text that translates XYZ in another language. (Here XYZ | |

stands for a specific section name mentioned below, such as | |

"Acknowledgements", "Dedications", "Endorsements", or "History".) | |

To "Preserve the Title" of such a section when you modify the | |

Document means that it remains a section "Entitled XYZ" according | |

to this definition. | |

The Document may include Warranty Disclaimers next to the notice | |

which states that this License applies to the Document. These | |

Warranty Disclaimers are considered to be included by reference in | |

this License, but only as regards disclaiming warranties: any other | |

implication that these Warranty Disclaimers may have is void and | |

has no effect on the meaning of this License. | |

2. VERBATIM COPYING | |

You may copy and distribute the Document in any medium, either | |

commercially or noncommercially, provided that this License, the | |

copyright notices, and the license notice saying this License | |

applies to the Document are reproduced in all copies, and that you | |

add no other conditions whatsoever to those of this License. You | |

may not use technical measures to obstruct or control the reading | |

or further copying of the copies you make or distribute. However, | |

you may accept compensation in exchange for copies. If you | |

distribute a large enough number of copies you must also follow | |

the conditions in section 3. | |

You may also lend copies, under the same conditions stated above, | |

and you may publicly display copies. | |

3. COPYING IN QUANTITY | |

If you publish printed copies (or copies in media that commonly | |

have printed covers) of the Document, numbering more than 100, and | |

the Document's license notice requires Cover Texts, you must | |

enclose the copies in covers that carry, clearly and legibly, all | |

these Cover Texts: Front-Cover Texts on the front cover, and | |

Back-Cover Texts on the back cover. Both covers must also clearly | |

and legibly identify you as the publisher of these copies. The | |

front cover must present the full title with all words of the | |

title equally prominent and visible. You may add other material | |

on the covers in addition. Copying with changes limited to the | |

covers, as long as they preserve the title of the Document and | |

satisfy these conditions, can be treated as verbatim copying in | |

other respects. | |

If the required texts for either cover are too voluminous to fit | |

legibly, you should put the first ones listed (as many as fit | |

reasonably) on the actual cover, and continue the rest onto | |

adjacent pages. | |

If you publish or distribute Opaque copies of the Document | |

numbering more than 100, you must either include a | |

machine-readable Transparent copy along with each Opaque copy, or | |

state in or with each Opaque copy a computer-network location from | |

which the general network-using public has access to download | |

using public-standard network protocols a complete Transparent | |

copy of the Document, free of added material. If you use the | |

latter option, you must take reasonably prudent steps, when you | |

begin distribution of Opaque copies in quantity, to ensure that | |

this Transparent copy will remain thus accessible at the stated | |

location until at least one year after the last time you | |

distribute an Opaque copy (directly or through your agents or | |

retailers) of that edition to the public. | |

It is requested, but not required, that you contact the authors of | |

the Document well before redistributing any large number of | |

copies, to give them a chance to provide you with an updated | |

version of the Document. | |

4. MODIFICATIONS | |

You may copy and distribute a Modified Version of the Document | |

under the conditions of sections 2 and 3 above, provided that you | |

release the Modified Version under precisely this License, with | |

the Modified Version filling the role of the Document, thus | |

licensing distribution and modification of the Modified Version to | |

whoever possesses a copy of it. In addition, you must do these | |

things in the Modified Version: | |

A. Use in the Title Page (and on the covers, if any) a title | |

distinct from that of the Document, and from those of | |

previous versions (which should, if there were any, be listed | |

in the History section of the Document). You may use the | |

same title as a previous version if the original publisher of | |

that version gives permission. | |

B. List on the Title Page, as authors, one or more persons or | |

entities responsible for authorship of the modifications in | |

the Modified Version, together with at least five of the | |

principal authors of the Document (all of its principal | |

authors, if it has fewer than five), unless they release you | |

from this requirement. | |

C. State on the Title page the name of the publisher of the | |

Modified Version, as the publisher. | |

D. Preserve all the copyright notices of the Document. | |

E. Add an appropriate copyright notice for your modifications | |

adjacent to the other copyright notices. | |

F. Include, immediately after the copyright notices, a license | |

notice giving the public permission to use the Modified | |

Version under the terms of this License, in the form shown in | |

the Addendum below. | |

G. Preserve in that license notice the full lists of Invariant | |

Sections and required Cover Texts given in the Document's | |

license notice. | |

H. Include an unaltered copy of this License. | |

I. Preserve the section Entitled "History", Preserve its Title, | |

and add to it an item stating at least the title, year, new | |

authors, and publisher of the Modified Version as given on | |

the Title Page. If there is no section Entitled "History" in | |

the Document, create one stating the title, year, authors, | |

and publisher of the Document as given on its Title Page, | |

then add an item describing the Modified Version as stated in | |

the previous sentence. | |

J. Preserve the network location, if any, given in the Document | |

for public access to a Transparent copy of the Document, and | |

likewise the network locations given in the Document for | |

previous versions it was based on. These may be placed in | |

the "History" section. You may omit a network location for a | |

work that was published at least four years before the | |

Document itself, or if the original publisher of the version | |

it refers to gives permission. | |

K. For any section Entitled "Acknowledgements" or "Dedications", | |

Preserve the Title of the section, and preserve in the | |

section all the substance and tone of each of the contributor | |

acknowledgements and/or dedications given therein. | |

L. Preserve all the Invariant Sections of the Document, | |

unaltered in their text and in their titles. Section numbers | |

or the equivalent are not considered part of the section | |

titles. | |

M. Delete any section Entitled "Endorsements". Such a section | |

may not be included in the Modified Version. | |

N. Do not retitle any existing section to be Entitled | |

"Endorsements" or to conflict in title with any Invariant | |

Section. | |

O. Preserve any Warranty Disclaimers. | |

If the Modified Version includes new front-matter sections or | |

appendices that qualify as Secondary Sections and contain no | |

material copied from the Document, you may at your option | |

designate some or all of these sections as invariant. To do this, | |

add their titles to the list of Invariant Sections in the Modified | |

Version's license notice. These titles must be distinct from any | |

other section titles. | |

You may add a section Entitled "Endorsements", provided it contains | |

nothing but endorsements of your Modified Version by various | |

parties--for example, statements of peer review or that the text | |

has been approved by an organization as the authoritative | |

definition of a standard. | |

You may add a passage of up to five words as a Front-Cover Text, | |

and a passage of up to 25 words as a Back-Cover Text, to the end | |

of the list of Cover Texts in the Modified Version. Only one | |

passage of Front-Cover Text and one of Back-Cover Text may be | |

added by (or through arrangements made by) any one entity. If the | |

Document already includes a cover text for the same cover, | |

previously added by you or by arrangement made by the same entity | |

you are acting on behalf of, you may not add another; but you may | |

replace the old one, on explicit permission from the previous | |

publisher that added the old one. | |

The author(s) and publisher(s) of the Document do not by this | |

License give permission to use their names for publicity for or to | |

assert or imply endorsement of any Modified Version. | |

5. COMBINING DOCUMENTS | |

You may combine the Document with other documents released under | |

this License, under the terms defined in section 4 above for | |

modified versions, provided that you include in the combination | |

all of the Invariant Sections of all of the original documents, | |

unmodified, and list them all as Invariant Sections of your | |

combined work in its license notice, and that you preserve all | |

their Warranty Disclaimers. | |

The combined work need only contain one copy of this License, and | |

multiple identical Invariant Sections may be replaced with a single | |

copy. If there are multiple Invariant Sections with the same name | |

but different contents, make the title of each such section unique | |

by adding at the end of it, in parentheses, the name of the | |

original author or publisher of that section if known, or else a | |

unique number. Make the same adjustment to the section titles in | |

the list of Invariant Sections in the license notice of the | |

combined work. | |

In the combination, you must combine any sections Entitled | |

"History" in the various original documents, forming one section | |

Entitled "History"; likewise combine any sections Entitled | |

"Acknowledgements", and any sections Entitled "Dedications". You | |

must delete all sections Entitled "Endorsements." | |

6. COLLECTIONS OF DOCUMENTS | |

You may make a collection consisting of the Document and other | |

documents released under this License, and replace the individual | |

copies of this License in the various documents with a single copy | |

that is included in the collection, provided that you follow the | |

rules of this License for verbatim copying of each of the | |

documents in all other respects. | |

You may extract a single document from such a collection, and | |

distribute it individually under this License, provided you insert | |

a copy of this License into the extracted document, and follow | |

this License in all other respects regarding verbatim copying of | |

that document. | |

7. AGGREGATION WITH INDEPENDENT WORKS | |

A compilation of the Document or its derivatives with other | |

separate and independent documents or works, in or on a volume of | |

a storage or distribution medium, is called an "aggregate" if the | |

copyright resulting from the compilation is not used to limit the | |

legal rights of the compilation's users beyond what the individual | |

works permit. When the Document is included in an aggregate, this | |

License does not apply to the other works in the aggregate which | |

are not themselves derivative works of the Document. | |

If the Cover Text requirement of section 3 is applicable to these | |

copies of the Document, then if the Document is less than one half | |

of the entire aggregate, the Document's Cover Texts may be placed | |

on covers that bracket the Document within the aggregate, or the | |

electronic equivalent of covers if the Document is in electronic | |

form. Otherwise they must appear on printed covers that bracket | |

the whole aggregate. | |

8. TRANSLATION | |

Translation is considered a kind of modification, so you may | |

distribute translations of the Document under the terms of section | |

4. Replacing Invariant Sections with translations requires special | |

permission from their copyright holders, but you may include | |

translations of some or all Invariant Sections in addition to the | |

original versions of these Invariant Sections. You may include a | |

translation of this License, and all the license notices in the | |

Document, and any Warranty Disclaimers, provided that you also | |

include the original English version of this License and the | |

original versions of those notices and disclaimers. In case of a | |

disagreement between the translation and the original version of | |

this License or a notice or disclaimer, the original version will | |

prevail. | |

If a section in the Document is Entitled "Acknowledgements", | |

"Dedications", or "History", the requirement (section 4) to | |

Preserve its Title (section 1) will typically require changing the | |

actual title. | |

9. TERMINATION | |

You may not copy, modify, sublicense, or distribute the Document | |

except as expressly provided under this License. Any attempt | |

otherwise to copy, modify, sublicense, or distribute it is void, | |

and will automatically terminate your rights under this License. | |

However, if you cease all violation of this License, then your | |

license from a particular copyright holder is reinstated (a) | |

provisionally, unless and until the copyright holder explicitly | |

and finally terminates your license, and (b) permanently, if the | |

copyright holder fails to notify you of the violation by some | |

reasonable means prior to 60 days after the cessation. | |

Moreover, your license from a particular copyright holder is | |

reinstated permanently if the copyright holder notifies you of the | |

violation by some reasonable means, this is the first time you have | |

received notice of violation of this License (for any work) from | |

that copyright holder, and you cure the violation prior to 30 days | |

after your receipt of the notice. | |

Termination of your rights under this section does not terminate | |

the licenses of parties who have received copies or rights from | |

you under this License. If your rights have been terminated and | |

not permanently reinstated, receipt of a copy of some or all of | |

the same material does not give you any rights to use it. | |

10. FUTURE REVISIONS OF THIS LICENSE | |

The Free Software Foundation may publish new, revised versions of | |

the GNU Free Documentation License from time to time. Such new | |

versions will be similar in spirit to the present version, but may | |

differ in detail to address new problems or concerns. See | |

`https://www.gnu.org/copyleft/'. | |

Each version of the License is given a distinguishing version | |

number. If the Document specifies that a particular numbered | |

version of this License "or any later version" applies to it, you | |

have the option of following the terms and conditions either of | |

that specified version or of any later version that has been | |

published (not as a draft) by the Free Software Foundation. If | |

the Document does not specify a version number of this License, | |

you may choose any version ever published (not as a draft) by the | |

Free Software Foundation. If the Document specifies that a proxy | |

can decide which future versions of this License can be used, that | |

proxy's public statement of acceptance of a version permanently | |

authorizes you to choose that version for the Document. | |

11. RELICENSING | |

"Massive Multiauthor Collaboration Site" (or "MMC Site") means any | |

World Wide Web server that publishes copyrightable works and also | |

provides prominent facilities for anybody to edit those works. A | |

public wiki that anybody can edit is an example of such a server. | |

A "Massive Multiauthor Collaboration" (or "MMC") contained in the | |

site means any set of copyrightable works thus published on the MMC | |

site. | |

"CC-BY-SA" means the Creative Commons Attribution-Share Alike 3.0 | |

license published by Creative Commons Corporation, a not-for-profit | |

corporation with a principal place of business in San Francisco, | |

California, as well as future copyleft versions of that license | |

published by that same organization. | |

"Incorporate" means to publish or republish a Document, in whole or | |

in part, as part of another Document. | |

An MMC is "eligible for relicensing" if it is licensed under this | |

License, and if all works that were first published under this | |

License somewhere other than this MMC, and subsequently | |

incorporated in whole or in part into the MMC, (1) had no cover | |

texts or invariant sections, and (2) were thus incorporated prior | |

to November 1, 2008. | |

The operator of an MMC Site may republish an MMC contained in the | |

site under CC-BY-SA on the same site at any time before August 1, | |

2009, provided the MMC is eligible for relicensing. | |

ADDENDUM: How to use this License for your documents | |

==================================================== | |

To use this License in a document you have written, include a copy of | |

the License in the document and put the following copyright and license | |

notices just after the title page: | |

Copyright (C) YEAR YOUR NAME. | |

Permission is granted to copy, distribute and/or modify this document | |

under the terms of the GNU Free Documentation License, Version 1.3 | |

or any later version published by the Free Software Foundation; | |

with no Invariant Sections, no Front-Cover Texts, and no Back-Cover | |

Texts. A copy of the license is included in the section entitled ``GNU | |

Free Documentation License''. | |

If you have Invariant Sections, Front-Cover Texts and Back-Cover | |

Texts, replace the "with...Texts." line with this: | |

with the Invariant Sections being LIST THEIR TITLES, with | |

the Front-Cover Texts being LIST, and with the Back-Cover Texts | |

being LIST. | |

If you have Invariant Sections without Cover Texts, or some other | |

combination of the three, merge those two alternatives to suit the | |

situation. | |

If your document contains nontrivial examples of program code, we | |

recommend releasing these examples in parallel under your choice of | |

free software license, such as the GNU General Public License, to | |

permit their use in free software. | |

File: gmp.info, Node: Concept Index, Next: Function Index, Prev: GNU Free Documentation License, Up: Top | |

Concept Index | |

************* | |

�[index�] | |

* Menu: | |

* #include: Headers and Libraries. | |

(line 6) | |

* --build: Build Options. (line 52) | |

* --disable-fft: Build Options. (line 313) | |

* --disable-shared: Build Options. (line 45) | |

* --disable-static: Build Options. (line 45) | |

* --enable-alloca: Build Options. (line 274) | |

* --enable-assert: Build Options. (line 319) | |

* --enable-cxx: Build Options. (line 226) | |

* --enable-fat: Build Options. (line 161) | |

* --enable-profiling <1>: Build Options. (line 323) | |

* --enable-profiling: Profiling. (line 6) | |

* --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 94) | |

* 80x86: Notes for Particular Systems. | |

(line 150) | |

* ABI <1>: Build Options. (line 168) | |

* ABI: ABI and ISA. (line 6) | |

* About this manual: Introduction to GMP. (line 57) | |

* AC_CHECK_LIB: Autoconf. (line 11) | |

* AIX <1>: Notes for Particular Systems. | |

(line 7) | |

* AIX: ABI and ISA. (line 178) | |

* Algorithms: Algorithms. (line 6) | |

* alloca: Build Options. (line 274) | |

* Allocation of memory: Custom Allocation. (line 6) | |

* AMD64: ABI and ISA. (line 44) | |

* Anonymous FTP of latest version: Introduction to GMP. (line 37) | |

* Application Binary Interface: ABI and ISA. (line 6) | |

* Arithmetic functions <1>: Rational Arithmetic. (line 6) | |

* Arithmetic functions <2>: Float Arithmetic. (line 6) | |

* Arithmetic functions: Integer 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 319) | |

* Assignment functions <1>: Assigning Integers. (line 6) | |

* Assignment functions <2>: Initializing Rationals. | |

(line 6) | |

* Assignment functions <3>: Simultaneous Float Init & Assign. | |

(line 6) | |

* Assignment functions <4>: Simultaneous Integer Init & Assign. | |

(line 6) | |

* Assignment functions: Assigning Floats. (line 6) | |

* Autoconf: Autoconf. (line 6) | |

* Basics: GMP Basics. (line 6) | |

* Binomial coefficient algorithm: Binomial Coefficients Algorithm. | |

(line 6) | |

* Binomial coefficient functions: Number Theoretic Functions. | |

(line 124) | |

* 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 40) | |

* Bit shift left: Integer Arithmetic. (line 38) | |

* Bit shift right: Integer Division. (line 62) | |

* Bits per limb: Useful Macros and Constants. | |

(line 7) | |

* Bug reporting: Reporting Bugs. (line 6) | |

* Build directory: Build Options. (line 19) | |

* Build notes for binary packaging: Notes for Package Builds. | |

(line 6) | |

* Build notes for particular systems: Notes for Particular Systems. | |

(line 6) | |

* Build options: Build Options. (line 6) | |

* Build problems known: Known Build Problems. | |

(line 6) | |

* Build system: Build Options. (line 52) | |

* Building GMP: Installing GMP. (line 6) | |

* Bus error: Debugging. (line 7) | |

* C compiler: Build Options. (line 179) | |

* C++ compiler: Build Options. (line 250) | |

* 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 226) | |

* CC: Build Options. (line 179) | |

* CC_FOR_BUILD: Build Options. (line 213) | |

* CFLAGS: Build Options. (line 179) | |

* 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>: Float Comparison. (line 6) | |

* Comparison functions: Comparing Rationals. (line 6) | |

* Compatibility with older versions: Compatibility with older versions. | |

(line 6) | |

* Conditions for copying GNU MP: Copying. (line 6) | |

* Configuring GMP: Installing GMP. (line 6) | |

* Congruence algorithm: Exact Remainder. (line 30) | |

* Congruence functions: Integer Division. (line 137) | |

* 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 205) | |

* CPU types <1>: Introduction to GMP. (line 24) | |

* CPU types: Build Options. (line 108) | |

* Cross compiling: Build Options. (line 66) | |

* Cryptography functions, low-level: Low-level Functions. (line 507) | |

* Custom allocation: Custom Allocation. (line 6) | |

* CXX: Build Options. (line 250) | |

* CXXFLAGS: Build Options. (line 250) | |

* Cygwin: Notes for Particular Systems. | |

(line 57) | |

* Darwin: Known Build Problems. | |

(line 51) | |

* Debugging: Debugging. (line 6) | |

* Demonstration programs: Demonstration Programs. | |

(line 6) | |

* Digits in an integer: Miscellaneous Integer Functions. | |

(line 23) | |

* Divisibility algorithm: Exact Remainder. (line 30) | |

* Divisibility functions: Integer Division. (line 137) | |

* Divisibility testing: Efficiency. (line 91) | |

* Division algorithms: Division Algorithms. (line 6) | |

* Division functions <1>: Rational Arithmetic. (line 24) | |

* Division functions <2>: Integer Division. (line 6) | |

* Division functions: Float Arithmetic. (line 33) | |

* DJGPP <1>: Notes for Particular Systems. | |

(line 57) | |

* DJGPP: Known Build Problems. | |

(line 18) | |

* DLLs: Notes for Particular Systems. | |

(line 70) | |

* DocBook: Build Options. (line 346) | |

* Documentation formats: Build Options. (line 339) | |

* Documentation license: GNU Free Documentation License. | |

(line 6) | |

* DVI: Build Options. (line 342) | |

* Efficiency: Efficiency. (line 6) | |

* Emacs: Emacs. (line 6) | |

* Exact division functions: Integer Division. (line 112) | |

* Exact remainder: Exact Remainder. (line 6) | |

* Example programs: Demonstration Programs. | |

(line 6) | |

* Exec prefix: Build Options. (line 32) | |

* Execution profiling <1>: Build Options. (line 323) | |

* Execution profiling: Profiling. (line 6) | |

* Exponentiation functions <1>: Float Arithmetic. (line 41) | |

* Exponentiation functions: Integer Exponentiation. | |

(line 6) | |

* Export: Integer Import and Export. | |

(line 45) | |

* Expression parsing demo: Demonstration Programs. | |

(line 15) | |

* Extended GCD: Number Theoretic Functions. | |

(line 43) | |

* Factor removal functions: Number Theoretic Functions. | |

(line 104) | |

* Factorial algorithm: Factorial Algorithm. (line 6) | |

* Factorial functions: Number Theoretic Functions. | |

(line 112) | |

* Factorization demo: Demonstration Programs. | |

(line 25) | |

* Fast Fourier Transform: FFT Multiplication. (line 6) | |

* Fat binary: Build Options. (line 161) | |

* FFT multiplication <1>: FFT Multiplication. (line 6) | |

* FFT multiplication: Build Options. (line 313) | |

* Fibonacci number algorithm: Fibonacci Numbers Algorithm. | |

(line 6) | |

* Fibonacci sequence functions: Number Theoretic Functions. | |

(line 132) | |

* 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 34) | |

* Floating point mode: Notes for Particular Systems. | |

(line 34) | |

* Floating-point functions: Floating-point Functions. | |

(line 6) | |

* Floating-point number: Nomenclature and Types. | |

(line 21) | |

* fnccheck: Profiling. (line 77) | |

* Formatted input: Formatted Input. (line 6) | |

* Formatted output: Formatted Output. (line 6) | |

* Free Documentation License: GNU Free Documentation License. | |

(line 6) | |

* FreeBSD: Notes for Particular Systems. | |

(line 43) | |

* frexp <1>: Converting Integers. (line 43) | |

* frexp: Converting Floats. (line 24) | |

* FTP of latest version: Introduction to GMP. (line 37) | |

* Function classes: Function Classes. (line 6) | |

* FunctionCheck: Profiling. (line 77) | |

* GCC Checker: Debugging. (line 115) | |

* GCD algorithms: Greatest Common Divisor Algorithms. | |

(line 6) | |

* GCD extended: Number Theoretic Functions. | |

(line 43) | |

* GCD functions: Number Theoretic Functions. | |

(line 26) | |

* GDB: Debugging. (line 58) | |

* Generic C: Build Options. (line 152) | |

* 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 26) | |

* 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 33) | |

* Host system: Build Options. (line 66) | |

* HP-UX: ABI and ISA. (line 77) | |

* HPPA: ABI and ISA. (line 77) | |

* I/O functions <1>: I/O of Integers. (line 6) | |

* I/O functions <2>: I/O of Floats. (line 6) | |

* I/O functions: I/O of Rationals. (line 6) | |

* i386: Notes for Particular Systems. | |

(line 150) | |

* IA-64: ABI and ISA. (line 116) | |

* 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 Floats. (line 6) | |

* Initialization functions <2>: Random State Initialization. | |

(line 6) | |

* Initialization functions <3>: Simultaneous Float Init & Assign. | |

(line 6) | |

* Initialization functions <4>: Simultaneous Integer Init & Assign. | |

(line 6) | |

* Initialization functions <5>: Initializing Rationals. | |

(line 6) | |

* Initialization functions: Initializing Integers. | |

(line 6) | |

* Initializing and clearing: Efficiency. (line 21) | |

* Input functions <1>: Formatted Input Functions. | |

(line 6) | |

* Input functions <2>: I/O of Rationals. (line 6) | |

* Input functions <3>: I/O of Floats. (line 6) | |

* Input functions: I/O of Integers. (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>: Assigning Integers. (line 6) | |

* Integer assignment functions: Simultaneous Integer Init & Assign. | |

(line 6) | |

* Integer bit manipulation functions: Integer Logic and Bit Fiddling. | |

(line 6) | |

* Integer comparison functions: Integer Comparisons. (line 6) | |

* Integer conversion functions: Converting Integers. (line 6) | |

* Integer division functions: Integer Division. (line 6) | |

* Integer exponentiation functions: Integer Exponentiation. | |

(line 6) | |

* Integer export: Integer Import and Export. | |

(line 45) | |

* Integer functions: Integer Functions. (line 6) | |

* Integer import: Integer Import and Export. | |

(line 11) | |

* Integer initialization functions <1>: Initializing Integers. | |

(line 6) | |

* Integer initialization functions: Simultaneous Integer Init & Assign. | |

(line 6) | |

* Integer input and output functions: I/O of Integers. (line 6) | |

* Integer internals: Integer Internals. (line 6) | |

* Integer logical functions: Integer Logic and Bit Fiddling. | |

(line 6) | |

* Integer miscellaneous functions: Miscellaneous Integer Functions. | |

(line 6) | |

* Integer random number functions: Integer Random Numbers. | |

(line 6) | |

* Integer root functions: Integer Roots. (line 6) | |

* Integer sign tests: Integer Comparisons. (line 28) | |

* Integer special functions: Integer Special Functions. | |

(line 6) | |

* Interix: Notes for Particular Systems. | |

(line 65) | |

* Internals: Internals. (line 6) | |

* Introduction: Introduction to GMP. (line 6) | |

* Inverse modulo functions: Number Theoretic Functions. | |

(line 70) | |

* IRIX <1>: ABI and ISA. (line 141) | |

* IRIX: Known Build Problems. | |

(line 38) | |

* ISA: ABI and ISA. (line 6) | |

* istream input: C++ Formatted Input. (line 6) | |

* Jacobi symbol algorithm: Jacobi Symbol. (line 6) | |

* Jacobi symbol functions: Number Theoretic Functions. | |

(line 79) | |

* Karatsuba multiplication: Karatsuba Multiplication. | |

(line 6) | |

* Karatsuba square root algorithm: Square Root Algorithm. | |

(line 6) | |

* Kronecker symbol functions: Number Theoretic Functions. | |

(line 91) | |

* Language bindings: Language Bindings. (line 6) | |

* Latest version of GMP: Introduction to GMP. (line 37) | |

* LCM functions: Number Theoretic Functions. | |

(line 64) | |

* Least common multiple functions: Number Theoretic Functions. | |

(line 64) | |

* Legendre symbol functions: Number Theoretic Functions. | |

(line 82) | |

* 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) | |

* Low-level functions for cryptography: Low-level Functions. (line 507) | |

* Lucas number algorithm: Lucas Numbers Algorithm. | |

(line 6) | |

* Lucas number functions: Number Theoretic Functions. | |

(line 143) | |

* MacOS X: Known Build Problems. | |

(line 51) | |

* Mailing lists: Introduction to GMP. (line 44) | |

* 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 57) | |

* MIPS: ABI and ISA. (line 141) | |

* Miscellaneous float functions: Miscellaneous Float Functions. | |

(line 6) | |

* Miscellaneous integer functions: Miscellaneous Integer Functions. | |

(line 6) | |

* MMX: Notes for Particular Systems. | |

(line 156) | |

* Modular inverse functions: Number Theoretic Functions. | |

(line 70) | |

* Most significant bit: Miscellaneous Integer Functions. | |

(line 34) | |

* MPN_PATH: Build Options. (line 327) | |

* MS Windows: Notes for Particular Systems. | |

(line 57) | |

* MS-DOS: Notes for Particular Systems. | |

(line 57) | |

* Multi-threading: Reentrancy. (line 6) | |

* Multiplication algorithms: Multiplication Algorithms. | |

(line 6) | |

* Nails: Low-level Functions. (line 683) | |

* Native compilation: Build Options. (line 52) | |

* NetBSD: Notes for Particular Systems. | |

(line 100) | |

* NeXT: Known Build Problems. | |

(line 57) | |

* Next prime function: Number Theoretic Functions. | |

(line 19) | |

* 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 109) | |

* Optimizing performance: Performance optimization. | |

(line 6) | |

* ostream output: C++ Formatted Output. | |

(line 6) | |

* Other languages: Language Bindings. (line 6) | |

* Output functions <1>: Formatted Output Functions. | |

(line 6) | |

* Output functions <2>: I/O of Rationals. (line 6) | |

* Output functions <3>: I/O of Integers. (line 6) | |

* Output functions: I/O of Floats. (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 342) | |

* Perfect power algorithm: Perfect Power Algorithm. | |

(line 6) | |

* Perfect power functions: Integer Roots. (line 28) | |

* Perfect square algorithm: Perfect Square Algorithm. | |

(line 6) | |

* Perfect square functions: Integer Roots. (line 37) | |

* perl: Demonstration Programs. | |

(line 35) | |

* Perl module: Demonstration Programs. | |

(line 35) | |

* Postscript: Build Options. (line 342) | |

* Power/PowerPC <1>: Known Build Problems. | |

(line 63) | |

* Power/PowerPC: Notes for Particular Systems. | |

(line 115) | |

* Powering algorithms: Powering Algorithms. (line 6) | |

* Powering functions <1>: Float Arithmetic. (line 41) | |

* Powering functions: Integer Exponentiation. | |

(line 6) | |

* PowerPC: ABI and ISA. (line 176) | |

* 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) | |

* Primorial functions: Number Theoretic Functions. | |

(line 117) | |

* 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>: Random Number Functions. | |

(line 6) | |

* Random number functions: Miscellaneous Float Functions. | |

(line 27) | |

* 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 28) | |

* 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 104) | |

* 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 28) | |

* Rounding functions: Miscellaneous Float Functions. | |

(line 9) | |

* Sample programs: Demonstration Programs. | |

(line 6) | |

* Scan bit functions: Integer Logic and Bit Fiddling. | |

(line 40) | |

* scanf formatted input: Formatted Input. (line 6) | |

* SCO: Known Build Problems. | |

(line 38) | |

* Seeding random numbers: Random State Seeding. | |

(line 6) | |

* Segmentation violation: Debugging. (line 7) | |

* Sequent Symmetry: Known Build Problems. | |

(line 68) | |

* Services for Unix: Notes for Particular Systems. | |

(line 65) | |

* Shared library versioning: Notes for Package Builds. | |

(line 9) | |

* Sign tests <1>: Comparing Rationals. (line 28) | |

* Sign tests <2>: Float Comparison. (line 34) | |

* Sign tests: Integer Comparisons. (line 28) | |

* Size in digits: Miscellaneous Integer Functions. | |

(line 23) | |

* Small operands: Efficiency. (line 7) | |

* Solaris <1>: ABI and ISA. (line 208) | |

* Solaris: Known Build Problems. | |

(line 72) | |

* Sparc: Notes for Particular Systems. | |

(line 127) | |

* Sparc V9: ABI and ISA. (line 208) | |

* Special integer functions: Integer Special Functions. | |

(line 6) | |

* Square root algorithm: Square Root Algorithm. | |

(line 6) | |

* SSE2: Notes for Particular Systems. | |

(line 156) | |

* Stack backtrace: Debugging. (line 50) | |

* Stack overflow <1>: Debugging. (line 7) | |

* Stack overflow: Build Options. (line 274) | |

* 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 208) | |

* SunOS: Notes for Particular Systems. | |

(line 144) | |

* Systems: Notes for Particular Systems. | |

(line 6) | |

* Temporary memory: Build Options. (line 274) | |

* Texinfo: Build Options. (line 339) | |

* Text input/output: Efficiency. (line 153) | |

* Thread safety: Reentrancy. (line 6) | |

* Toom multiplication <1>: Higher degree Toom'n'half. | |

(line 6) | |

* Toom multiplication <2>: Other Multiplication. | |

(line 6) | |

* Toom multiplication <3>: 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 33) | |

* Windows: Notes for Particular Systems. | |

(line 70) | |

* x86: Notes for Particular Systems. | |

(line 150) | |

* x87: Notes for Particular Systems. | |

(line 34) | |

* XML: Build Options. (line 346) | |

File: gmp.info, Node: Function Index, Prev: Concept Index, Up: Top | |

Function and Type Index | |

*********************** | |

�[index�] | |

* 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 14) | |

* abs <1>: C++ Interface Rationals. | |

(line 49) | |

* abs <2>: C++ Interface Integers. | |

(line 47) | |

* abs: C++ Interface Floats. | |

(line 83) | |

* ceil: C++ Interface Floats. | |

(line 84) | |

* cmp <1>: C++ Interface Floats. | |

(line 85) | |

* cmp <2>: C++ Interface Integers. | |

(line 48) | |

* cmp <3>: C++ Interface Rationals. | |

(line 51) | |

* cmp: C++ Interface Floats. | |

(line 86) | |

* floor: C++ Interface Floats. | |

(line 93) | |

* gcd: C++ Interface Integers. | |

(line 64) | |

* 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 713) | |

* GMP_NAIL_BITS: Low-level Functions. (line 711) | |

* GMP_NAIL_MASK: Low-level Functions. (line 721) | |

* GMP_NUMB_BITS: Low-level Functions. (line 712) | |

* GMP_NUMB_MASK: Low-level Functions. (line 722) | |

* GMP_NUMB_MAX: Low-level Functions. (line 730) | |

* 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 46) | |

* 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 27) | |

* gmp_randclass::seed: C++ Interface Random Numbers. | |

(line 34) | |

* 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 8) | |

* gmp_randseed_ui: Random State Seeding. | |

(line 10) | |

* 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 94) | |

* lcm: C++ Interface Integers. | |

(line 65) | |

* 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 90) | |

* mp_limb_t: Nomenclature and Types. | |

(line 31) | |

* mp_set_memory_functions: Custom Allocation. (line 18) | |

* 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 87) | |

* mpf_class::fits_slong_p: C++ Interface Floats. | |

(line 88) | |

* mpf_class::fits_sshort_p: C++ Interface Floats. | |

(line 89) | |

* mpf_class::fits_uint_p: C++ Interface Floats. | |

(line 90) | |

* mpf_class::fits_ulong_p: C++ Interface Floats. | |

(line 91) | |

* mpf_class::fits_ushort_p: C++ Interface Floats. | |

(line 92) | |

* mpf_class::get_d: C++ Interface Floats. | |

(line 95) | |

* mpf_class::get_mpf_t: C++ Interface General. | |

(line 66) | |

* mpf_class::get_prec: C++ Interface Floats. | |

(line 115) | |

* mpf_class::get_si: C++ Interface Floats. | |

(line 96) | |

* mpf_class::get_str: C++ Interface Floats. | |

(line 98) | |

* mpf_class::get_ui: C++ Interface Floats. | |

(line 99) | |

* mpf_class::mpf_class: C++ Interface Floats. | |

(line 47) | |

* mpf_class::operator=: C++ Interface Floats. | |

(line 60) | |

* mpf_class::set_prec: C++ Interface Floats. | |

(line 116) | |

* mpf_class::set_prec_raw: C++ Interface Floats. | |

(line 117) | |

* mpf_class::set_str: C++ Interface Floats. | |

(line 101) | |

* mpf_class::swap: C++ Interface Floats. | |

(line 104) | |

* mpf_clear: Initializing Floats. (line 37) | |

* mpf_clears: Initializing Floats. (line 41) | |

* mpf_cmp: Float Comparison. (line 7) | |

* mpf_cmp_d: Float Comparison. (line 9) | |

* mpf_cmp_si: Float Comparison. (line 11) | |

* mpf_cmp_ui: Float Comparison. (line 10) | |

* mpf_cmp_z: Float Comparison. (line 8) | |

* mpf_div: Float Arithmetic. (line 29) | |

* mpf_div_2exp: Float Arithmetic. (line 55) | |

* mpf_div_ui: Float Arithmetic. (line 33) | |

* mpf_eq: Float Comparison. (line 19) | |

* 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 17) | |

* mpf_get_default_prec: Initializing Floats. (line 12) | |

* mpf_get_prec: Initializing Floats. (line 62) | |

* mpf_get_si: Converting Floats. (line 28) | |

* mpf_get_str: Converting Floats. (line 38) | |

* mpf_get_ui: Converting Floats. (line 29) | |

* 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 26) | |

* mpf_init_set_ui: Simultaneous Float Init & Assign. | |

(line 17) | |

* mpf_inits: Initializing Floats. (line 31) | |

* mpf_inp_str: I/O of Floats. (line 39) | |

* mpf_integer_p: Miscellaneous Float Functions. | |

(line 14) | |

* mpf_mul: Float Arithmetic. (line 19) | |

* mpf_mul_2exp: Float Arithmetic. (line 51) | |

* mpf_mul_ui: Float Arithmetic. (line 21) | |

* mpf_neg: Float Arithmetic. (line 44) | |

* mpf_out_str: I/O of Floats. (line 19) | |

* mpf_pow_ui: Float Arithmetic. (line 41) | |

* mpf_random2: Miscellaneous Float Functions. | |

(line 37) | |

* mpf_reldiff: Float Comparison. (line 30) | |

* 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 34) | |

* 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 150) | |

* mpn_and_n: Low-level Functions. (line 449) | |

* mpn_andn_n: Low-level Functions. (line 464) | |

* mpn_cmp: Low-level Functions. (line 295) | |

* mpn_cnd_add_n: Low-level Functions. (line 542) | |

* mpn_cnd_sub_n: Low-level Functions. (line 544) | |

* mpn_cnd_swap: Low-level Functions. (line 569) | |

* mpn_com: Low-level Functions. (line 489) | |

* mpn_copyd: Low-level Functions. (line 498) | |

* mpn_copyi: Low-level Functions. (line 494) | |

* mpn_divexact_1: Low-level Functions. (line 233) | |

* mpn_divexact_by3: Low-level Functions. (line 240) | |

* mpn_divexact_by3c: Low-level Functions. (line 242) | |

* mpn_divmod: Low-level Functions. (line 228) | |

* mpn_divmod_1: Low-level Functions. (line 212) | |

* mpn_divrem: Low-level Functions. (line 186) | |

* mpn_divrem_1: Low-level Functions. (line 210) | |

* mpn_gcd: Low-level Functions. (line 303) | |

* mpn_gcd_1: Low-level Functions. (line 313) | |

* mpn_gcdext: Low-level Functions. (line 319) | |

* mpn_get_str: Low-level Functions. (line 373) | |

* mpn_hamdist: Low-level Functions. (line 438) | |

* mpn_ior_n: Low-level Functions. (line 454) | |

* mpn_iorn_n: Low-level Functions. (line 469) | |

* mpn_lshift: Low-level Functions. (line 271) | |

* mpn_mod_1: Low-level Functions. (line 266) | |

* mpn_mul: Low-level Functions. (line 116) | |

* mpn_mul_1: Low-level Functions. (line 135) | |

* mpn_mul_n: Low-level Functions. (line 105) | |

* mpn_nand_n: Low-level Functions. (line 474) | |

* mpn_neg: Low-level Functions. (line 98) | |

* mpn_nior_n: Low-level Functions. (line 479) | |

* mpn_perfect_square_p: Low-level Functions. (line 444) | |

* mpn_popcount: Low-level Functions. (line 434) | |

* mpn_random: Low-level Functions. (line 423) | |

* mpn_random2: Low-level Functions. (line 424) | |

* mpn_rshift: Low-level Functions. (line 283) | |

* mpn_scan0: Low-level Functions. (line 408) | |

* mpn_scan1: Low-level Functions. (line 416) | |

* mpn_sec_add_1: Low-level Functions. (line 555) | |

* mpn_sec_div_qr: Low-level Functions. (line 632) | |

* mpn_sec_div_qr_itch: Low-level Functions. (line 633) | |

* mpn_sec_div_r: Low-level Functions. (line 649) | |

* mpn_sec_div_r_itch: Low-level Functions. (line 650) | |

* mpn_sec_invert: Low-level Functions. (line 664) | |

* mpn_sec_invert_itch: Low-level Functions. (line 665) | |

* mpn_sec_mul: Low-level Functions. (line 577) | |

* mpn_sec_mul_itch: Low-level Functions. (line 578) | |

* mpn_sec_powm: Low-level Functions. (line 607) | |

* mpn_sec_powm_itch: Low-level Functions. (line 609) | |

* mpn_sec_sqr: Low-level Functions. (line 592) | |

* mpn_sec_sqr_itch: Low-level Functions. (line 593) | |

* mpn_sec_sub_1: Low-level Functions. (line 557) | |

* mpn_sec_tabselect: Low-level Functions. (line 623) | |

* mpn_set_str: Low-level Functions. (line 388) | |

* mpn_sizeinbase: Low-level Functions. (line 366) | |

* mpn_sqr: Low-level Functions. (line 127) | |

* mpn_sqrtrem: Low-level Functions. (line 348) | |

* 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 162) | |

* mpn_tdiv_qr: Low-level Functions. (line 175) | |

* mpn_xnor_n: Low-level Functions. (line 484) | |

* mpn_xor_n: Low-level Functions. (line 459) | |

* mpn_zero: Low-level Functions. (line 501) | |

* mpn_zero_p: Low-level Functions. (line 299) | |

* mpq_abs: Rational Arithmetic. (line 34) | |

* mpq_add: Rational Arithmetic. (line 8) | |

* mpq_canonicalize: Rational Number Functions. | |

(line 22) | |

* mpq_class: C++ Interface General. | |

(line 19) | |

* mpq_class::canonicalize: C++ Interface Rationals. | |

(line 43) | |

* mpq_class::get_d: C++ Interface Rationals. | |

(line 52) | |

* mpq_class::get_den: C++ Interface Rationals. | |

(line 66) | |

* mpq_class::get_den_mpz_t: C++ Interface Rationals. | |

(line 76) | |

* mpq_class::get_mpq_t: C++ Interface General. | |

(line 65) | |

* mpq_class::get_num: C++ Interface Rationals. | |

(line 65) | |

* mpq_class::get_num_mpz_t: C++ Interface Rationals. | |

(line 75) | |

* mpq_class::get_str: C++ Interface Rationals. | |

(line 53) | |

* mpq_class::mpq_class: C++ Interface Rationals. | |

(line 12) | |

* mpq_class::set_str: C++ Interface Rationals. | |

(line 55) | |

* mpq_class::swap: C++ Interface Rationals. | |

(line 57) | |

* mpq_clear: Initializing Rationals. | |

(line 16) | |

* mpq_clears: Initializing Rationals. | |

(line 20) | |

* mpq_cmp: Comparing Rationals. (line 7) | |

* mpq_cmp_si: Comparing Rationals. (line 18) | |

* mpq_cmp_ui: Comparing Rationals. (line 16) | |

* mpq_cmp_z: Comparing Rationals. (line 8) | |

* mpq_denref: Applying Integer Functions. | |

(line 18) | |

* mpq_div: Rational Arithmetic. (line 24) | |

* mpq_div_2exp: Rational Arithmetic. (line 28) | |

* mpq_equal: Comparing Rationals. (line 34) | |

* 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 27) | |

* mpq_inv: Rational Arithmetic. (line 37) | |

* mpq_mul: Rational Arithmetic. (line 16) | |

* mpq_mul_2exp: Rational Arithmetic. (line 20) | |

* mpq_neg: Rational Arithmetic. (line 31) | |

* mpq_numref: Applying Integer Functions. | |

(line 17) | |

* mpq_out_str: I/O of Rationals. (line 19) | |

* 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 28) | |

* mpq_sub: Rational Arithmetic. (line 12) | |

* mpq_swap: Initializing Rationals. | |

(line 56) | |

* mpq_t: Nomenclature and Types. | |

(line 16) | |

* mpz_2fac_ui: Number Theoretic Functions. | |

(line 110) | |

* mpz_abs: Integer Arithmetic. (line 45) | |

* mpz_add: Integer Arithmetic. (line 7) | |

* mpz_add_ui: Integer Arithmetic. (line 9) | |

* mpz_addmul: Integer Arithmetic. (line 26) | |

* mpz_addmul_ui: Integer Arithmetic. (line 28) | |

* mpz_and: Integer Logic and Bit Fiddling. | |

(line 11) | |

* mpz_array_init: Integer Special Functions. | |

(line 11) | |

* mpz_bin_ui: Number Theoretic Functions. | |

(line 122) | |

* mpz_bin_uiui: Number Theoretic Functions. | |

(line 124) | |

* mpz_cdiv_q: Integer Division. (line 13) | |

* mpz_cdiv_q_2exp: Integer Division. (line 26) | |

* mpz_cdiv_q_ui: Integer Division. (line 18) | |

* mpz_cdiv_qr: Integer Division. (line 16) | |

* mpz_cdiv_qr_ui: Integer Division. (line 22) | |

* mpz_cdiv_r: Integer Division. (line 14) | |

* mpz_cdiv_r_2exp: Integer Division. (line 28) | |

* mpz_cdiv_r_ui: Integer Division. (line 20) | |

* mpz_cdiv_ui: Integer Division. (line 24) | |

* mpz_class: C++ Interface General. | |

(line 18) | |

* mpz_class::fits_sint_p: C++ Interface Integers. | |

(line 50) | |

* mpz_class::fits_slong_p: C++ Interface Integers. | |

(line 51) | |

* mpz_class::fits_sshort_p: C++ Interface Integers. | |

(line 52) | |

* mpz_class::fits_uint_p: C++ Interface Integers. | |

(line 53) | |

* mpz_class::fits_ulong_p: C++ Interface Integers. | |

(line 54) | |

* mpz_class::fits_ushort_p: C++ Interface Integers. | |

(line 55) | |

* mpz_class::get_d: C++ Interface Integers. | |

(line 56) | |

* mpz_class::get_mpz_t: C++ Interface General. | |

(line 64) | |

* mpz_class::get_si: C++ Interface Integers. | |

(line 57) | |

* mpz_class::get_str: C++ Interface Integers. | |

(line 58) | |

* mpz_class::get_ui: C++ Interface Integers. | |

(line 59) | |

* mpz_class::mpz_class: C++ Interface Integers. | |

(line 7) | |

* mpz_class::set_str: C++ Interface Integers. | |

(line 61) | |

* mpz_class::swap: C++ Interface Integers. | |

(line 66) | |

* mpz_clear: Initializing Integers. | |

(line 49) | |

* mpz_clears: Initializing Integers. | |

(line 53) | |

* mpz_clrbit: Integer Logic and Bit Fiddling. | |

(line 56) | |

* 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 59) | |

* mpz_congruent_2exp_p: Integer Division. (line 137) | |

* mpz_congruent_p: Integer Division. (line 133) | |

* mpz_congruent_ui_p: Integer Division. (line 135) | |

* mpz_divexact: Integer Division. (line 110) | |

* mpz_divexact_ui: Integer Division. (line 112) | |

* mpz_divisible_2exp_p: Integer Division. (line 123) | |

* mpz_divisible_p: Integer Division. (line 120) | |

* mpz_divisible_ui_p: Integer Division. (line 122) | |

* mpz_even_p: Miscellaneous Integer Functions. | |

(line 18) | |

* mpz_export: Integer Import and Export. | |

(line 45) | |

* mpz_fac_ui: Number Theoretic Functions. | |

(line 109) | |

* mpz_fdiv_q: Integer Division. (line 30) | |

* mpz_fdiv_q_2exp: Integer Division. (line 43) | |

* mpz_fdiv_q_ui: Integer Division. (line 35) | |

* mpz_fdiv_qr: Integer Division. (line 33) | |

* mpz_fdiv_qr_ui: Integer Division. (line 39) | |

* mpz_fdiv_r: Integer Division. (line 31) | |

* mpz_fdiv_r_2exp: Integer Division. (line 45) | |

* mpz_fdiv_r_ui: Integer Division. (line 37) | |

* mpz_fdiv_ui: Integer Division. (line 41) | |

* mpz_fib2_ui: Number Theoretic Functions. | |

(line 132) | |

* mpz_fib_ui: Number Theoretic Functions. | |

(line 130) | |

* 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 26) | |

* mpz_gcd_ui: Number Theoretic Functions. | |

(line 33) | |

* mpz_gcdext: Number Theoretic Functions. | |

(line 43) | |

* mpz_get_d: Converting Integers. (line 27) | |

* mpz_get_d_2exp: Converting Integers. (line 36) | |

* mpz_get_si: Converting Integers. (line 18) | |

* mpz_get_str: Converting Integers. (line 47) | |

* mpz_get_ui: Converting Integers. (line 11) | |

* mpz_getlimbn: Integer Special Functions. | |

(line 23) | |

* 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 35) | |

* mpz_init_set_ui: Simultaneous Integer Init & Assign. | |

(line 28) | |

* mpz_inits: Initializing Integers. | |

(line 29) | |

* mpz_inp_raw: I/O of Integers. (line 62) | |

* mpz_inp_str: I/O of Integers. (line 31) | |

* mpz_invert: Number Theoretic Functions. | |

(line 70) | |

* mpz_ior: Integer Logic and Bit Fiddling. | |

(line 14) | |

* mpz_jacobi: Number Theoretic Functions. | |

(line 79) | |

* mpz_kronecker: Number Theoretic Functions. | |

(line 87) | |

* mpz_kronecker_si: Number Theoretic Functions. | |

(line 88) | |

* mpz_kronecker_ui: Number Theoretic Functions. | |

(line 89) | |

* mpz_lcm: Number Theoretic Functions. | |

(line 62) | |

* mpz_lcm_ui: Number Theoretic Functions. | |

(line 64) | |

* mpz_legendre: Number Theoretic Functions. | |

(line 82) | |

* mpz_limbs_finish: Integer Special Functions. | |

(line 48) | |

* mpz_limbs_modify: Integer Special Functions. | |

(line 41) | |

* mpz_limbs_read: Integer Special Functions. | |

(line 35) | |

* mpz_limbs_write: Integer Special Functions. | |

(line 40) | |

* mpz_lucnum2_ui: Number Theoretic Functions. | |

(line 143) | |

* mpz_lucnum_ui: Number Theoretic Functions. | |

(line 141) | |

* mpz_mfac_uiui: Number Theoretic Functions. | |

(line 112) | |

* mpz_mod: Integer Division. (line 100) | |

* mpz_mod_ui: Integer Division. (line 102) | |

* mpz_mul: Integer Arithmetic. (line 19) | |

* mpz_mul_2exp: Integer Arithmetic. (line 38) | |

* mpz_mul_si: Integer Arithmetic. (line 20) | |

* mpz_mul_ui: Integer Arithmetic. (line 22) | |

* mpz_neg: Integer Arithmetic. (line 42) | |

* mpz_nextprime: Number Theoretic Functions. | |

(line 19) | |

* mpz_odd_p: Miscellaneous Integer Functions. | |

(line 17) | |

* mpz_out_raw: I/O of Integers. (line 46) | |

* mpz_out_str: I/O of Integers. (line 19) | |

* mpz_perfect_power_p: Integer Roots. (line 28) | |

* mpz_perfect_square_p: Integer Roots. (line 37) | |

* 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_primorial_ui: Number Theoretic Functions. | |

(line 117) | |

* 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 57) | |

* mpz_remove: Number Theoretic Functions. | |

(line 104) | |

* mpz_roinit_n: Integer Special Functions. | |

(line 69) | |

* MPZ_ROINIT_N: Integer Special Functions. | |

(line 84) | |

* mpz_root: Integer Roots. (line 8) | |

* mpz_rootrem: Integer Roots. (line 14) | |

* mpz_rrandomb: Integer Random Numbers. | |

(line 31) | |

* mpz_scan0: Integer Logic and Bit Fiddling. | |

(line 38) | |

* mpz_scan1: Integer Logic and Bit Fiddling. | |

(line 40) | |

* 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 53) | |

* mpz_sgn: Integer Comparisons. (line 28) | |

* mpz_si_kronecker: Number Theoretic Functions. | |

(line 90) | |

* mpz_size: Integer Special Functions. | |

(line 31) | |

* mpz_sizeinbase: Miscellaneous Integer Functions. | |

(line 23) | |

* mpz_sqrt: Integer Roots. (line 18) | |

* mpz_sqrtrem: Integer Roots. (line 21) | |

* mpz_sub: Integer Arithmetic. (line 12) | |

* mpz_sub_ui: Integer Arithmetic. (line 14) | |

* mpz_submul: Integer Arithmetic. (line 32) | |

* mpz_submul_ui: Integer Arithmetic. (line 34) | |

* mpz_swap: Assigning Integers. (line 37) | |

* mpz_t: Nomenclature and Types. | |

(line 6) | |

* mpz_tdiv_q: Integer Division. (line 47) | |

* mpz_tdiv_q_2exp: Integer Division. (line 60) | |

* mpz_tdiv_q_ui: Integer Division. (line 52) | |

* mpz_tdiv_qr: Integer Division. (line 50) | |

* mpz_tdiv_qr_ui: Integer Division. (line 56) | |

* mpz_tdiv_r: Integer Division. (line 48) | |

* mpz_tdiv_r_2exp: Integer Division. (line 62) | |

* mpz_tdiv_r_ui: Integer Division. (line 54) | |

* mpz_tdiv_ui: Integer Division. (line 58) | |

* mpz_tstbit: Integer Logic and Bit Fiddling. | |

(line 62) | |

* mpz_ui_kronecker: Number Theoretic Functions. | |

(line 91) | |

* 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) | |

* operator"" <1>: C++ Interface Floats. | |

(line 56) | |

* operator"" <2>: C++ Interface Rationals. | |

(line 38) | |

* operator"": C++ Interface Integers. | |

(line 30) | |

* operator%: C++ Interface Integers. | |

(line 35) | |

* operator/: C++ Interface Integers. | |

(line 34) | |

* operator<<: C++ Formatted Output. | |

(line 33) | |

* operator>> <1>: C++ Formatted Input. (line 14) | |

* operator>> <2>: C++ Interface Rationals. | |

(line 85) | |

* operator>>: C++ Formatted Input. (line 25) | |

* sgn <1>: C++ Interface Integers. | |

(line 62) | |

* sgn <2>: C++ Interface Rationals. | |

(line 56) | |

* sgn: C++ Interface Floats. | |

(line 102) | |

* sqrt <1>: C++ Interface Integers. | |

(line 63) | |

* sqrt: C++ Interface Floats. | |

(line 103) | |

* swap <1>: C++ Interface Floats. | |

(line 105) | |

* swap <2>: C++ Interface Rationals. | |

(line 58) | |

* swap: C++ Interface Integers. | |

(line 67) | |

* trunc: C++ Interface Floats. | |

(line 106) | |