GNU Multiple Precision - GNU MP - GMP Cheat Sheet (DRAFT) by andystp

mpq_t

multiple precision fraction

mp_exp_t

floating point functions accept and return exponents in this type

mp_size_t

counts of limbs of a multi-­pre­cision number repres­ented

gmp_ra­nds­tate_t

random state means an algorithm selection and current state data

mpq_

Functions for rational number arithmetic

mpn_

Fast low-level functions that operate on natural numbers. These are used by the functions in the preceding groups, and you can also call them directly from very time-c­ritical user programs.

void mpq_init (mpq_t x)

Initialize x and set it to 0/1.

void mp[z,q­,f]­_inits (mp[z,q,f] x, ...)

Initialize a NULL-t­erm­inated list of mp[z,q­,f]_t variables, and set their values to 0.

void mp[z,q­,f]­_clears (mp[z,­q,f]_t x, ...)

Free the space occupied by a NULL-t­erm­inated list of mp[z,q­,f]_t variables.

void mpz_set_ui (mpz_t rop, unsigned long int op)

"

void mpz_set_d (mpz_t rop, double op)

truncate

void mpz_set_f (mpz_t rop, const mpf_t op)

"

void mpq_set_z (mpq_t rop, const mpz_t op)

"

void mpq_set_si (mpq_t rop, signed long int op1, unsigned long int op2)

"

void mpf_set_ui (mpf_t rop, unsigned long int op)

"

void mpf_set_d (mpf_t rop, double op)

"

void mpf_set_q (mpf_t rop, const mpq_t op)

"

int mpq_se­t_str (mpq_t rop, const char *str, int base)

Set rop from a null-t­erm­inated string str in the given base. Should return 0, if error returns -1.

void mpz_swap (mpz_t rop1, mpz_t rop2)

Swap the values rop1 and rop2 effici­ently.

void mpf_swap (mpf_t rop1, mpf_t rop2)

Swap rop1 and rop2 effici­ently. Both the values and the precisions of the two variables are swapped.

signed long int mpz_get_si (const mpz_t op)

If op fits into a signed long int return the value of op. Otherwise return the least signif­icant part of op, with the same sign as op.

double mpz_ge­t_d­_2exp (signed long int *exp, const mpz_t op)

Convert op to a double, truncating if necessary (i.e. rounding towards zero), and returning the exponent separa­tely.

double mpq_get_d (const mpq_t op)

Convert op to a double, truncating if necessary (i.e. rounding towards zero).

void mpq_set_f (mpq_t rop, const mpf_t op)

Set rop to the value of op. There is no rounding, this conversion is exact.

double mpf_get_d (const mpf_t op)

Convert op to a double, truncating if necessary (i.e. rounding towards zero).

long mpf_get_si (const mpf_t op)

Convert op to a long or unsigned long, truncating any fraction part. If op is too big for the return type, the result is undefined.

char mpf_ge­t_str (char str, mp_exp_t *expptr, int base, size_t n_digits, const mpf_t op)

Convert op to a string of digits in base base. The base argument may vary from 2 to 62 or from -2 to -36. Up to n_digits digits will be generated. Trailing zeros are not returned. No more digits than can be accurately repres­ented by op are ever generated. If n_digits is 0 then that accurate maximum number of digits are generated.

void mpz_add_ui (mpz_t rop, const mpz_t op1, unsigned long int op2)

Set rop to op1 + op2.

void mpz_sub_ui (mpz_t rop, const mpz_t op1, unsigned long int op2)

Set rop to op1 - op2.

void mpz_mul (mpz_t rop, const mpz_t op1, const mpz_t op2)

Set rop to op1 times op2.

void mpz_mul_ui (mpz_t rop, const mpz_t op1, unsigned long int op2)

Set rop to op1 times op2.

void mpz_ad­dmul_ui (mpz_t rop, const mpz_t op1, unsigned long int op2)

Set rop to rop + op1 times op2.

void mpz_su­bmul_ui (mpz_t rop, const mpz_t op1, unsigned long int op2)

Set rop to rop - op1 times op2.

void mpz_neg (mpz_t rop, const mpz_t op)

Set rop to -op.

void mpq_sub (mpq_t differ­ence, const mpq_t minuend, const mpq_t subtra­hend)

Set difference to minuend - subtra­hend.

void mpq_mu­l_2exp (mpq_t rop, const mpq_t op1, mp_bit­cnt_t op2)

Set rop to op1 times 2 raised to op2. This operation can also be defined as a left shift by op2 bits.

void mpq_di­v_2exp (mpq_t rop, const mpq_t op1, mp_bit­cnt_t op2)

Set rop to op1 divided by 2 raised to op2.

void mpq_abs (mpq_t rop, const mpq_t op)

Set rop to the absolute value of op.

void mpf_add_ui (mpf_t rop, const mpf_t op1, unsigned long int op2)

Set rop to op1 + op2.

void mpf_ui_sub (mpf_t rop, unsigned long int op1, const mpf_t op2)

Set rop to op1 - op2.

void mpf_mul (mpf_t rop, const mpf_t op1, const mpf_t op2)

Set rop to op1 times op2.

void mpf_div (mpf_t rop, const mpf_t op1, const mpf_t op2)

Set rop to op1/op2.

void mpf_div_ui (mpf_t rop, const mpf_t op1, unsigned long int op2)

Set rop to op1/op2.

void mpf_sq­rt_ui (mpf_t rop, unsigned long int op)

Set rop to the square root of op.

void mpf_neg (mpf_t rop, const mpf_t op)

Set rop to -op.

void mpf_mu­l_2exp (mpf_t rop, const mpf_t op1, mp_bit­cnt_t op2)

Set rop to op1 times 2 raised to op2. This operation can also be defined as a left shift by op2 bits.

void mpz_cdiv_r (mpz_t r, const mpz_t n, const mpz_t d)

unsigned long int mpz_cd­iv_q_ui (mpz_t q, const mpz_t n, unsigned long int d)

unsigned long int mpz_cd­iv_­qr_ui (mpz_t q, mpz_t r, const mpz_t n, unsigned long int d)

void mpz_cd­iv_­q_2exp (mpz_t q, const mpz_t n, mp_bit­cnt_t b)

void mpz_fdiv_r (mpz_t r, const mpz_t n, const mpz_t d)

unsigned long int mpz_fd­iv_q_ui (mpz_t q, const mpz_t n, unsigned long int d)

unsigned long int mpz_fd­iv_­qr_ui (mpz_t q, mpz_t r, const mpz_t n, unsigned long int d)

void mpz_fd­iv_­q_2exp (mpz_t q, const mpz_t n, mp_bit­cnt_t b)

void mpz_tdiv_r (mpz_t r, const mpz_t n, const mpz_t d)

unsigned long int mpz_td­iv_q_ui (mpz_t q, const mpz_t n, unsigned long int d)

unsigned long int mpz_td­iv_­qr_ui (mpz_t q, mpz_t r, const mpz_t n, unsigned long int d)

void mpz_td­iv_­q_2exp (mpz_t q, const mpz_t n, mp_bit­cnt_t b)

fdiv rounds q down towards -infinity, and r will have the same sign as d. The f stands for “floor”.

In all cases q and r will satisfy n=q*d+r, and r will satisfy 0<=­abs­(r)­<ab­s(d).

For the ui variants the return value is the remainder, and in fact returning the remainder is all the div_ui functions do. For tdiv and cdiv the remainder can be negative, so for those the return value is the absolute value of the remainder.

For positive n both mpz_fd­iv_­q_2exp and mpz_td­iv_­q_2exp are simple bitwise right shifts. For negative n, mpz_fd­iv_­q_2exp is effect­ively an arithmetic right shift treating n as twos complement the same as the bitwise logical functions do, whereas mpz_td­iv_­q_2exp effect­ively treats n as sign and magnitude.

void mpz_mod (mpz_t r, const mpz_t n, const mpz_t d)

Set r to n mod d. The sign of the divisor is ignored; the result is always non-ne­gative.

mpz_mod_ui is identical to mpz_fd­iv_r_ui above, returning the remainder as well as setting r. See mpz_fd­iv_ui above if only the return value is wanted.

void mpz_di­vexact (mpz_t q, const mpz_t n, const mpz_t d)

Set q to n/d. These functions produce correct results only when it is known in advance that d divides n.

These routines are much faster than the other division functions, and are the best choice when exact division is known to occur, for example reducing a rational to lowest terms.

int mpz_di­vis­ible_p (const mpz_t n, const mpz_t d)

Return non-zero if n is exactly divisible by d, or in the case of mpz_di­vis­ibl­e_2­exp_p by 2^b.

int mpz_di­vis­ibl­e_2­exp_p (const mpz_t n, mp_bit­cnt_t b)

Return non-zero if n is exactly divisible by d, or in the case of mpz_di­vis­ibl­e_2­exp_p by 2^b.

int mpz_co­ngr­uen­t_ui_p (const mpz_t n, unsigned long int c, unsigned long int d)

Return non-zero if n is congruent to c modulo d, or in the case of mpz_co­ngr­uen­t_2­exp_p modulo 2^b.

n is congruent to c mod d if there exists an integer q satisfying n = c + q*d. Unlike the other division functions, d=0 is accepted and following the rule it can be seen that n and c are considered congruent mod 0 only when exactly equal.

void mpz_po­wm_ui (mpz_t rop, const mpz_t base, unsigned long int exp, const mpz_t mod)

Set rop to (base raised to exp) modulo mod.

It is required that exp > 0 and that mod is odd.

void mpz_ui­_pow_ui (mpz_t rop, unsigned long int base, unsigned long int exp)

Set rop to base raised to exp. The case 0^0 yields 1.

void mpz_ro­otrem (mpz_t root, mpz_t rem, const mpz_t u, unsigned long int n)

Set root to the truncated integer part of the nth root of u. Set rem to the remainder, u-root**n.

void mpz_sq­rtrem (mpz_t rop1, mpz_t rop2, const mpz_t op)

Set rop1 to the truncated integer part of the square root of op, like mpz_sqrt. Set rop2 to the remainder op-rop­1*rop1, which will be zero if op is a perfect square.

int mpz_pe­rfe­ct_­power_p (const mpz_t op)

Return non-zero if op is a perfect power, i.e., if there exist integers a and b, with b>1, such that op equals a raised to the power b.

int mpz_pe­rfe­ct_­squ­are_p (const mpz_t op)

Return non-zero if op is a perfect square, i.e., if the square root of op is an integer. Under this definition both 0 and 1 are considered to be perfect squares.

This function performs some trial divisions, then reps Miller­-Rabin probab­ilistic primality tests. A higher reps value will reduce the chances of a non-prime being identified as “probably prime”. A composite number will be identified as a prime with a probab­ility of less than 4^(-reps). Reasonable values of reps are between 15 and 50.

This function uses a probab­ilistic algorithm to identify primes. For practical purposes it’s adequate, the chance of a composite passing will be extremely small.

unsigned long int mpz_gcd_ui (mpz_t rop, const mpz_t op1, unsigned long int op2)

Compute the greatest common divisor of op1 and op2. If rop is not NULL, store the result there.

void mpz_gcdext (mpz_t g, mpz_t s, mpz_t t, const mpz_t a, const mpz_t b)

Set g to the greatest common divisor of a and b, and in addition set s and t to coeffi­cients satisfying as + bt = g. The value in g is always positive, even if one or both of a and b are negative (or zero if both inputs are zero). The values in s and t are chosen such that normally, abs(s) < abs(b) / (2 g) and abs(t) < abs(a) / (2 g), and these relations define s and t uniquely. There are a few except­ional cases:

Otherwise, s = sgn(a) if b = 0 or abs(b) = 2 g, and t = sgn(b) if a = 0 or abs(a) = 2 g.

If t is NULL then that value is not computed.

void mpz_lcm_ui (mpz_t rop, const mpz_t op1, unsigned long op2)

Set rop to the least common multiple of op1 and op2. rop is always positive, irresp­ective of the signs of op1 and op2. rop will be zero if either op1 or op2 is zero.

int mpz_jacobi (const mpz_t a, const mpz_t b)

Calculate the Jacobi symbol (a/b). This is defined only for b odd.

int mpz_kr­onecker (const mpz_t a, const mpz_t b)

Calculate the Jacobi symbol (a/b) with the Kronecker extension (a/2)=­(2/a) when a odd, or (a/2)=0 when a even.

int mpz_kr­one­cker_ui (const mpz_t a, unsigned long b)

Calculate the Jacobi symbol (a/b) with the Kronecker extension (a/2)=­(2/a) when a odd, or (a/2)=0 when a even.

int mpz_ui­_kr­onecker (unsigned long a, const mpz_t b)

Calculate the Jacobi symbol (a/b) with the Kronecker extension (a/2)=­(2/a) when a odd, or (a/2)=0 when a even.

void mpz_fac_ui (mpz_t rop, unsigned long int n)

Set rop to the factorial of n: mpz_fac_ui computes the plain factorial n!, mpz_2f­ac_ui computes the double­-fa­ctorial n!!, and mpz_mf­ac_uiui the m-mult­i-f­act­orial n!^(m).

void mpz_mf­ac_uiui (mpz_t rop, unsigned long int n, unsigned long int m)

Set rop to the factorial of n: mpz_fac_ui computes the plain factorial n!, mpz_2f­ac_ui computes the double­-fa­ctorial n!!, and mpz_mf­ac_uiui the m-mult­i-f­act­orial n!^(m).

void mpz_bin_ui (mpz_t rop, const mpz_t n, unsigned long int k)

Compute the binomial coeffi­cient n over k and store the result in rop. Negative values of n are supported by mpz_bi­n_ui, using the identity bin(-n,k) = (-1)^k * bin(n+­k-1,k), see Knuth volume 1 section 1.2.6 part G.

void mpz_fib_ui (mpz_t fn, unsigned long int n)

mpz_fib_ui sets fn to to F[n], the n’th Fibonacci number. mpz_fi­b2_ui sets fn to F[n], and fnsub1 to F[n-1].

These functions are designed for calcul­ating isolated Fibonacci numbers. When a sequence of values is wanted it’s best to start with mpz_fi­b2_ui and iterate the defining F[n+1]­=F[­n]+­F[n-1] or similar.

void mpz_lu­cnu­m2_ui (mpz_t ln, mpz_t lnsub1, unsigned long int n)

mpz_lu­cnum_ui sets ln to to L[n], the n’th Lucas number. mpz_lu­cnu­m2_ui sets ln to L[n], and lnsub1 to L[n-1].

The Fibonacci numbers and Lucas numbers are related sequences, so it’s never necessary to call both mpz_fi­b2_ui and mpz_lu­cnu­m2_ui. The formulas for going from Fibonacci to Lucas can be found in Lucas Numbers Algorithm, the reverse is straig­htf­orward too.