Constant gmp_mpfr_sys::C::GMP::Integer_Functions[−][src]

pub const Integer_Functions: ();

This constant is a place-holder for documentation; do not use it in code.

5 Integer Functions

This chapter describes the GMP functions for performing integer arithmetic. These functions start with the prefix mpz_.

GMP integers are stored in objects of type mpz_t.

5.1 Initialization Functions

The functions for integer arithmetic assume that all integer objects are initialized. You do that by calling the function mpz_init. For example,

{
  mpz_t integ;
  mpz_init (integ);
  …
  mpz_add (integ, …);
  …
  mpz_sub (integ, …);
  /* Unless the program is about to exit, do ... */
  mpz_clear (integ);
}

As you can see, you can store new values any number of times, once an object is initialized.

Function: void mpz_init (mpz_t x): Initialize x, and set its value to 0.

Function: void mpz_inits (mpz_t x, ...): Initialize a NULL-terminated list of mpz_t variables, and set their values to 0.

Function: void mpz_init2 (mpz_t x, mp_bitcnt_t n)

Initialize x, with space for n-bit numbers, and set its value to 0. Calling this function instead of mpz_init or mpz_inits is never necessary; reallocation is handled automatically by GMP when needed.

While n defines the initial space, x will grow automatically in the normal way, if necessary, for subsequent values stored. mpz_init2 makes it possible to avoid such reallocations if a maximum size is known in advance.

In preparation for an operation, GMP often allocates one limb more than ultimately needed. To make sure GMP will not perform reallocation for x, you need to add the number of bits in mp_limb_t to n.

Function: void mpz_clear (mpz_t x): Free the space occupied by x. Call this function for all mpz_t variables when you are done with them.

Function: void mpz_clears (mpz_t x, ...): Free the space occupied by a NULL-terminated list of mpz_t variables.

Function: void mpz_realloc2 (mpz_t x, mp_bitcnt_t n)

Change the space allocated for x to n bits. The value in x is preserved if it fits, or is set to 0 if not.

Calling this function is never necessary; reallocation is handled automatically by GMP when needed. But this function can be used to increase the space for a variable in order to avoid repeated automatic reallocations, or to decrease it to give memory back to the heap.

5.2 Assignment Functions

These functions assign new values to already initialized integers (see Initializing Integers).

Function: void mpz_set (mpz_t rop, const mpz_t op)

Function: void mpz_set_ui (mpz_t rop, unsigned long int op)

Function: void mpz_set_si (mpz_t rop, signed long int op)

Function: void mpz_set_d (mpz_t rop, double op)

Function: void mpz_set_q (mpz_t rop, const mpq_t op)

Function: void mpz_set_f (mpz_t rop, const mpf_t op)

Set the value of rop from op.

mpz_set_d, mpz_set_q and mpz_set_f truncate op to make it an integer.

Function: int mpz_set_str (mpz_t rop, const char *str, int base)

Set the value of rop from str, a null-terminated C string in base base. White space is allowed in the string, and is simply ignored.

The base may vary from 2 to 62, or if base is 0, then the leading characters are used: 0x and 0X for hexadecimal, 0b and 0B for binary, 0 for octal, or decimal otherwise.

For bases up to 36, case is ignored; upper-case and lower-case letters have the same value. For bases 37 to 62, upper-case letter represent the usual 10..35 while lower-case letter represent 36..61.

This function returns 0 if the entire string is a valid number in base base. Otherwise it returns -1.

Function: void mpz_swap (mpz_t rop1, mpz_t rop2): Swap the values rop1 and rop2 efficiently.

5.3 Combined Initialization and Assignment Functions

For convenience, GMP provides a parallel series of initialize-and-set functions which initialize the output and then store the value there. These functions’ names have the form mpz_init_set…

Here is an example of using one:

{
  mpz_t pie;
  mpz_init_set_str (pie, "3141592653589793238462643383279502884", 10);
  …
  mpz_sub (pie, …);
  …
  mpz_clear (pie);
}

Once the integer has been initialized by any of the mpz_init_set… functions, it can be used as the source or destination operand for the ordinary integer functions. Don’t use an initialize-and-set function on a variable already initialized!

Function: void mpz_init_set (mpz_t rop, const mpz_t op)
Function: void mpz_init_set_ui (mpz_t rop, unsigned long int op)
Function: void mpz_init_set_si (mpz_t rop, signed long int op)
Function: void mpz_init_set_d (mpz_t rop, double op): Initialize rop with limb space and set the initial numeric value from op.

Function: int mpz_init_set_str (mpz_t rop, const char *str, int base)

Initialize rop and set its value like mpz_set_str (see its documentation above for details).

If the string is a correct base base number, the function returns 0; if an error occurs it returns -1. rop is initialized even if an error occurs. (I.e., you have to call mpz_clear for it.)

5.4 Conversion Functions

This section describes functions for converting GMP integers to standard C types. Functions for converting to GMP integers are described in Assigning Integers and I/O of Integers.

Function: unsigned long int mpz_get_ui (const mpz_t op)

Return the value of op as an unsigned long.

If op is too big to fit an unsigned long then just the least significant bits that do fit are returned. The sign of op is ignored, only the absolute value is used.

Function: 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 significant part of op, with the same sign as op.

If op is too big to fit in a signed long int, the returned result is probably not very useful. To find out if the value will fit, use the function mpz_fits_slong_p.

Function: double mpz_get_d (const mpz_t op)

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

If the exponent from the conversion is too big, the result is system dependent. An infinity is returned where available. A hardware overflow trap may or may not occur.

Function: double mpz_get_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 separately.

The return value is in the range 0.5<=abs(d)<1 and the exponent is stored to *exp. d * 2^exp is the (truncated) op value. If op is zero, the return is 0.0 and 0 is stored to *exp.

This is similar to the standard C frexp function (see Normalization Functions in The GNU C Library Reference Manual).

Function: char * mpz_get_str (char *str, int base, const mpz_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.

For base in the range 2..36, digits and lower-case letters are used; for -2..-36, digits and upper-case letters are used; for 37..62, digits, upper-case letters, and lower-case letters (in that significance order) are used.

If str is NULL, the result string is allocated using the current allocation function (see Custom Allocation). The block will be strlen(str)+1 bytes, that being exactly enough for the string and null-terminator.

If str is not NULL, it should point to a block of storage large enough for the result, that being mpz_sizeinbase (op, base) + 2. The two extra bytes are for a possible minus sign, and the null-terminator.

A pointer to the result string is returned, being either the allocated block, or the given str.

5.5 Arithmetic Functions

Function: void mpz_add (mpz_t rop, const mpz_t op1, const mpz_t op2)
Function: void mpz_add_ui (mpz_t rop, const mpz_t op1, unsigned long int op2): Set rop to op1 + op2.

Function: void mpz_sub (mpz_t rop, const mpz_t op1, const mpz_t op2)
Function: void mpz_sub_ui (mpz_t rop, const mpz_t op1, unsigned long int op2)
Function: void mpz_ui_sub (mpz_t rop, unsigned long int op1, const mpz_t op2): Set rop to op1 - op2.

Function: void mpz_mul (mpz_t rop, const mpz_t op1, const mpz_t op2)
Function: void mpz_mul_si (mpz_t rop, const mpz_t op1, long int op2)
Function: void mpz_mul_ui (mpz_t rop, const mpz_t op1, unsigned long int op2): Set rop to op1 times op2.

Function: void mpz_addmul (mpz_t rop, const mpz_t op1, const mpz_t op2)
Function: void mpz_addmul_ui (mpz_t rop, const mpz_t op1, unsigned long int op2): Set rop to rop + op1 times op2.

Function: void mpz_submul (mpz_t rop, const mpz_t op1, const mpz_t op2)
Function: void mpz_submul_ui (mpz_t rop, const mpz_t op1, unsigned long int op2): Set rop to rop - op1 times op2.

Function: void mpz_mul_2exp (mpz_t rop, const mpz_t op1, mp_bitcnt_t op2): Set rop to op1 times 2 raised to op2. This operation can also be defined as a left shift by op2 bits.

Function: void mpz_neg (mpz_t rop, const mpz_t op): Set rop to -op.

Function: void mpz_abs (mpz_t rop, const mpz_t op): Set rop to the absolute value of op.

5.6 Division Functions

Division is undefined if the divisor is zero. Passing a zero divisor to the division or modulo functions (including the modular powering functions mpz_powm and mpz_powm_ui), will cause an intentional division by zero. This lets a program handle arithmetic exceptions in these functions the same way as for normal C int arithmetic.

Function: void mpz_cdiv_q (mpz_t q, const mpz_t n, const mpz_t d)
Function: void mpz_cdiv_r (mpz_t r, const mpz_t n, const mpz_t d)
Function: void mpz_cdiv_qr (mpz_t q, mpz_t r, const mpz_t n, const mpz_t d)
Function: unsigned long int mpz_cdiv_q_ui (mpz_t q, const mpz_t n, unsigned long int d)
Function: unsigned long int mpz_cdiv_r_ui (mpz_t r, const mpz_t n, unsigned long int d)
Function: unsigned long int mpz_cdiv_qr_ui (mpz_t q, mpz_t r, const mpz_t n, unsigned long int d)
Function: unsigned long int mpz_cdiv_ui (const mpz_t n, unsigned long int d)
Function: void mpz_cdiv_q_2exp (mpz_t q, const mpz_t n, mp_bitcnt_t b)
Function: void mpz_cdiv_r_2exp (mpz_t r, const mpz_t n, mp_bitcnt_t b)

Function: void mpz_fdiv_q (mpz_t q, const mpz_t n, const mpz_t d)
Function: void mpz_fdiv_r (mpz_t r, const mpz_t n, const mpz_t d)
Function: void mpz_fdiv_qr (mpz_t q, mpz_t r, const mpz_t n, const mpz_t d)
Function: unsigned long int mpz_fdiv_q_ui (mpz_t q, const mpz_t n, unsigned long int d)
Function: unsigned long int mpz_fdiv_r_ui (mpz_t r, const mpz_t n, unsigned long int d)
Function: unsigned long int mpz_fdiv_qr_ui (mpz_t q, mpz_t r, const mpz_t n, unsigned long int d)
Function: unsigned long int mpz_fdiv_ui (const mpz_t n, unsigned long int d)
Function: void mpz_fdiv_q_2exp (mpz_t q, const mpz_t n, mp_bitcnt_t b)
Function: void mpz_fdiv_r_2exp (mpz_t r, const mpz_t n, mp_bitcnt_t b)

Function: void mpz_tdiv_q (mpz_t q, const mpz_t n, const mpz_t d)

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

Function: void mpz_tdiv_qr (mpz_t q, mpz_t r, const mpz_t n, const mpz_t d)

Function: unsigned long int mpz_tdiv_q_ui (mpz_t q, const mpz_t n, unsigned long int d)

Function: unsigned long int mpz_tdiv_r_ui (mpz_t r, const mpz_t n, unsigned long int d)

Function: unsigned long int mpz_tdiv_qr_ui (mpz_t q, mpz_t r, const mpz_t n, unsigned long int d)

Function: unsigned long int mpz_tdiv_ui (const mpz_t n, unsigned long int d)

Function: void mpz_tdiv_q_2exp (mpz_t q, const mpz_t n, mp_bitcnt_t b)

Function: void mpz_tdiv_r_2exp (mpz_t r, const mpz_t n, mp_bitcnt_t b)

Divide n by d, forming a quotient q and/or remainder r. For the 2exp functions, d=2^b. The rounding is in three styles, each suiting different applications.

cdiv rounds q up towards +infinity, and r will have the opposite sign to d. The c stands for “ceil”.
fdiv rounds q down towards -infinity, and r will have the same sign as d. The f stands for “floor”.
tdiv rounds q towards zero, and r will have the same sign as n. The t stands for “truncate”.

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

The q functions calculate only the quotient, the r functions only the remainder, and the qr functions calculate both. Note that for qr the same variable cannot be passed for both q and r, or results will be unpredictable.

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 the 2exp variants the divisor is 2^b. These functions are implemented as right shifts and bit masks, but of course they round the same as the other functions.

For positive n both mpz_fdiv_q_2exp and mpz_tdiv_q_2exp are simple bitwise right shifts. For negative n, mpz_fdiv_q_2exp is effectively an arithmetic right shift treating n as twos complement the same as the bitwise logical functions do, whereas mpz_tdiv_q_2exp effectively treats n as sign and magnitude.

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

Function: unsigned long int mpz_mod_ui (mpz_t r, const mpz_t n, unsigned long int d)

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

mpz_mod_ui is identical to mpz_fdiv_r_ui above, returning the remainder as well as setting r. See mpz_fdiv_ui above if only the return value is wanted.

Function: void mpz_divexact (mpz_t q, const mpz_t n, const mpz_t d)

Function: void mpz_divexact_ui (mpz_t q, const mpz_t n, unsigned long 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.

Function: int mpz_divisible_p (const mpz_t n, const mpz_t d)

Function: int mpz_divisible_ui_p (const mpz_t n, unsigned long int d)

Function: int mpz_divisible_2exp_p (const mpz_t n, mp_bitcnt_t b)

Return non-zero if n is exactly divisible by d, or in the case of mpz_divisible_2exp_p by 2^b.

n is divisible by d if there exists an integer q satisfying n = q*d. Unlike the other division functions, d=0 is accepted and following the rule it can be seen that only 0 is considered divisible by 0.

Function: int mpz_congruent_p (const mpz_t n, const mpz_t c, const mpz_t d)

Function: int mpz_congruent_ui_p (const mpz_t n, unsigned long int c, unsigned long int d)

Function: int mpz_congruent_2exp_p (const mpz_t n, const mpz_t c, mp_bitcnt_t b)

Return non-zero if n is congruent to c modulo d, or in the case of mpz_congruent_2exp_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.

5.7 Exponentiation Functions

Function: void mpz_powm (mpz_t rop, const mpz_t base, const mpz_t exp, const mpz_t mod)

Function: void mpz_powm_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.

Negative exp is supported if the inverse base^-1 mod mod exists (see mpz_invert in Number Theoretic Functions). If an inverse doesn’t exist then a divide by zero is raised.

Function: void mpz_powm_sec (mpz_t rop, const mpz_t base, const mpz_t 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.

This function is designed to take the same time and have the same cache access patterns for any two same-size arguments, assuming that function arguments are placed at the same position and that the machine state is identical upon function entry. This function is intended for cryptographic purposes, where resilience to side-channel attacks is desired.

Function: void mpz_pow_ui (mpz_t rop, const mpz_t base, unsigned long int exp)
Function: 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.

5.8 Root Extraction Functions

Function: int mpz_root (mpz_t rop, const mpz_t op, unsigned long int n): Set rop to the truncated integer part of the nth root of op. Return non-zero if the computation was exact, i.e., if op is rop to the nth power.

Function: void mpz_rootrem (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.

Function: void mpz_sqrt (mpz_t rop, const mpz_t op): Set rop to the truncated integer part of the square root of op.

Function: void mpz_sqrtrem (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-rop1*rop1, which will be zero if op is a perfect square.

If rop1 and rop2 are the same variable, the results are undefined.

Function: int mpz_perfect_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.

Under this definition both 0 and 1 are considered to be perfect powers. Negative values of op are accepted, but of course can only be odd perfect powers.

Function: int mpz_perfect_square_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.

5.9 Number Theoretic Functions

Function: int mpz_probab_prime_p (const mpz_t n, int reps)

Determine whether n is prime. Return 2 if n is definitely prime, return 1 if n is probably prime (without being certain), or return 0 if n is definitely non-prime.

This function performs some trial divisions, a Baillie-PSW probable prime test, then reps-24 Miller-Rabin probabilistic 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 an asymptotic probability of less than 4^(-reps). Reasonable values of reps are between 15 and 50.

GMP versions up to and including 6.1.2 did not use the Baillie-PSW primality test. In those older versions of GMP, this function performed reps Miller-Rabin tests.

Function: void mpz_nextprime (mpz_t rop, const mpz_t op)

Set rop to the next prime greater than op.

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

Function: void mpz_gcd (mpz_t rop, const mpz_t op1, const mpz_t op2): Set rop to the greatest common divisor of op1 and op2. The result is always positive even if one or both input operands are negative. Except if both inputs are zero; then this function defines gcd(0,0) = 0.

Function: 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.

If the result is small enough to fit in an unsigned long int, it is returned. If the result does not fit, 0 is returned, and the result is equal to the argument op1. Note that the result will always fit if op2 is non-zero.

Function: 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 coefficients satisfying a*s + b*t = 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 exceptional cases:

If abs(a) = abs(b), then s = 0, t = sgn(b).

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

In all cases, s = 0 if and only if g = abs(b), i.e., if b divides a or a = b = 0.

If t or g is NULL then that value is not computed.

Function: void mpz_lcm (mpz_t rop, const mpz_t op1, const mpz_t op2)
Function: 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, irrespective of the signs of op1 and op2. rop will be zero if either op1 or op2 is zero.

Function: int mpz_invert (mpz_t rop, const mpz_t op1, const mpz_t op2): Compute the inverse of op1 modulo op2 and put the result in rop. If the inverse exists, the return value is non-zero and rop will satisfy 0 <= rop < abs(op2) (with rop = 0 possible only when abs(op2) = 1, i.e., in the somewhat degenerate zero ring). If an inverse doesn’t exist the return value is zero and rop is undefined. The behaviour of this function is undefined when op2 is zero.

Function: int mpz_jacobi (const mpz_t a, const mpz_t b): Calculate the Jacobi symbol (a/b). This is defined only for b odd.

Function: int mpz_legendre (const mpz_t a, const mpz_t p): Calculate the Legendre symbol (a/p). This is defined only for p an odd positive prime, and for such p it’s identical to the Jacobi symbol.

Function: int mpz_kronecker (const mpz_t a, const mpz_t b)

Function: int mpz_kronecker_si (const mpz_t a, long b)

Function: int mpz_kronecker_ui (const mpz_t a, unsigned long b)

Function: int mpz_si_kronecker (long a, const mpz_t b)

Function: int mpz_ui_kronecker (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.

When b is odd the Jacobi symbol and Kronecker symbol are identical, so mpz_kronecker_ui etc can be used for mixed precision Jacobi symbols too.

For more information see Henri Cohen section 1.4.2 (see References), or any number theory textbook. See also the example program demos/qcn.c which uses mpz_kronecker_ui.

Function: mp_bitcnt_t mpz_remove (mpz_t rop, const mpz_t op, const mpz_t f): Remove all occurrences of the factor f from op and store the result in rop. The return value is how many such occurrences were removed.

Function: void mpz_fac_ui (mpz_t rop, unsigned long int n)
Function: void mpz_2fac_ui (mpz_t rop, unsigned long int n)
Function: void mpz_mfac_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_2fac_ui computes the double-factorial n!!, and mpz_mfac_uiui the m-multi-factorial n!^(m).

Function: void mpz_primorial_ui (mpz_t rop, unsigned long int n): Set rop to the primorial of n, i.e. the product of all positive prime numbers <=n.

Function: void mpz_bin_ui (mpz_t rop, const mpz_t n, unsigned long int k)
Function: void mpz_bin_uiui (mpz_t rop, unsigned long int n, unsigned long int k): Compute the binomial coefficient n over k and store the result in rop. Negative values of n are supported by mpz_bin_ui, using the identity bin(-n,k) = (-1)^k * bin(n+k-1,k), see Knuth volume 1 section 1.2.6 part G.

Function: void mpz_fib_ui (mpz_t fn, unsigned long int n)

Function: void mpz_fib2_ui (mpz_t fn, mpz_t fnsub1, unsigned long int n)

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

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

Function: void mpz_lucnum_ui (mpz_t ln, unsigned long int n)

Function: void mpz_lucnum2_ui (mpz_t ln, mpz_t lnsub1, unsigned long int n)

mpz_lucnum_ui sets ln to to L[n], the n’th Lucas number. mpz_lucnum2_ui sets ln to L[n], and lnsub1 to L[n-1].

These functions are designed for calculating isolated Lucas numbers. When a sequence of values is wanted it’s best to start with mpz_lucnum2_ui and iterate the defining L[n+1]=L[n]+L[n-1] or similar.

The Fibonacci numbers and Lucas numbers are related sequences, so it’s never necessary to call both mpz_fib2_ui and mpz_lucnum2_ui. The formulas for going from Fibonacci to Lucas can be found in Lucas Numbers Algorithm, the reverse is straightforward too.

5.10 Comparison Functions

Function: int mpz_cmp (const mpz_t op1, const mpz_t op2)

Function: int mpz_cmp_d (const mpz_t op1, double op2)

Macro: int mpz_cmp_si (const mpz_t op1, signed long int op2)

Macro: int mpz_cmp_ui (const mpz_t op1, unsigned long int op2)

Compare op1 and op2. Return a positive value if op1 > op2, zero if op1 = op2, or a negative value if op1 < op2.

mpz_cmp_ui and mpz_cmp_si are macros and will evaluate their arguments more than once. mpz_cmp_d can be called with an infinity, but results are undefined for a NaN.

Function: int mpz_cmpabs (const mpz_t op1, const mpz_t op2)

Function: int mpz_cmpabs_d (const mpz_t op1, double op2)

Function: int mpz_cmpabs_ui (const mpz_t op1, unsigned long int op2)

Compare the absolute values of op1 and op2. Return a positive value if abs(op1) > abs(op2), zero if abs(op1) = abs(op2), or a negative value if abs(op1) < abs(op2).

mpz_cmpabs_d can be called with an infinity, but results are undefined for a NaN.

Macro: int mpz_sgn (const mpz_t op)

Return +1 if op > 0, 0 if op = 0, and -1 if op < 0.

This function is actually implemented as a macro. It evaluates its argument multiple times.

5.11 Logical and Bit Manipulation Functions

These functions behave as if twos complement arithmetic were used (although sign-magnitude is the actual implementation). The least significant bit is number 0.

Function: void mpz_and (mpz_t rop, const mpz_t op1, const mpz_t op2): Set rop to op1 bitwise-and op2.

Function: void mpz_ior (mpz_t rop, const mpz_t op1, const mpz_t op2): Set rop to op1 bitwise inclusive-or op2.

Function: void mpz_xor (mpz_t rop, const mpz_t op1, const mpz_t op2): Set rop to op1 bitwise exclusive-or op2.

Function: void mpz_com (mpz_t rop, const mpz_t op): Set rop to the one’s complement of op.

Function: mp_bitcnt_t mpz_popcount (const mpz_t op): If op>=0, return the population count of op, which is the number of 1 bits in the binary representation. If op<0, the number of 1s is infinite, and the return value is the largest possible mp_bitcnt_t.

Function: mp_bitcnt_t mpz_hamdist (const mpz_t op1, const mpz_t op2): If op1 and op2 are both >=0 or both <0, return the hamming distance between the two operands, which is the number of bit positions where op1 and op2 have different bit values. If one operand is >=0 and the other <0 then the number of bits different is infinite, and the return value is the largest possible mp_bitcnt_t.

Function: mp_bitcnt_t mpz_scan0 (const mpz_t op, mp_bitcnt_t starting_bit)

Function: mp_bitcnt_t mpz_scan1 (const mpz_t op, mp_bitcnt_t starting_bit)

Scan op, starting from bit starting_bit, towards more significant bits, until the first 0 or 1 bit (respectively) is found. Return the index of the found bit.

If the bit at starting_bit is already what’s sought, then starting_bit is returned.

If there’s no bit found, then the largest possible mp_bitcnt_t is returned. This will happen in mpz_scan0 past the end of a negative number, or mpz_scan1 past the end of a nonnegative number.

Function: void mpz_setbit (mpz_t rop, mp_bitcnt_t bit_index): Set bit bit_index in rop.

Function: void mpz_clrbit (mpz_t rop, mp_bitcnt_t bit_index): Clear bit bit_index in rop.

Function: void mpz_combit (mpz_t rop, mp_bitcnt_t bit_index): Complement bit bit_index in rop.

Function: int mpz_tstbit (const mpz_t op, mp_bitcnt_t bit_index): Test bit bit_index in op and return 0 or 1 accordingly.

5.12 Input and Output Functions

Functions that perform input from a stdio stream, and functions that output to a stdio stream, of mpz numbers. Passing a NULL pointer for a stream argument to any of these functions will make them read from stdin and write to stdout, respectively.

When using any of these functions, it is a good idea to include stdio.h before gmp.h, since that will allow gmp.h to define prototypes for these functions.

See also Formatted Output and Formatted Input.

Function: size_t mpz_out_str (FILE *stream, int base, const mpz_t op)

Output op on stdio stream stream, as a string of digits in base base. The base argument may vary from 2 to 62 or from -2 to -36.

For base in the range 2..36, digits and lower-case letters are used; for -2..-36, digits and upper-case letters are used; for 37..62, digits, upper-case letters, and lower-case letters (in that significance order) are used.

Return the number of bytes written, or if an error occurred, return 0.

Function: size_t mpz_inp_str (mpz_t rop, FILE *stream, int base)

Input a possibly white-space preceded string in base base from stdio stream stream, and put the read integer in rop.

The base may vary from 2 to 62, or if base is 0, then the leading characters are used: 0x and 0X for hexadecimal, 0b and 0B for binary, 0 for octal, or decimal otherwise.

For bases up to 36, case is ignored; upper-case and lower-case letters have the same value. For bases 37 to 62, upper-case letter represent the usual 10..35 while lower-case letter represent 36..61.

Return the number of bytes read, or if an error occurred, return 0.

Function: size_t mpz_out_raw (FILE *stream, const mpz_t op)

Output op on stdio stream stream, in raw binary format. The integer is written in a portable format, with 4 bytes of size information, and that many bytes of limbs. Both the size and the limbs are written in decreasing significance order (i.e., in big-endian).

The output can be read with mpz_inp_raw.

Return the number of bytes written, or if an error occurred, return 0.

The output of this can not be read by mpz_inp_raw from GMP 1, because of changes necessary for compatibility between 32-bit and 64-bit machines.

Function: size_t mpz_inp_raw (mpz_t rop, FILE *stream)

Input from stdio stream stream in the format written by mpz_out_raw, and put the result in rop. Return the number of bytes read, or if an error occurred, return 0.

This routine can read the output from mpz_out_raw also from GMP 1, in spite of changes necessary for compatibility between 32-bit and 64-bit machines.

5.13 Random Number Functions

The random number functions of GMP come in two groups; older function that rely on a global state, and newer functions that accept a state parameter that is read and modified. Please see the Random Number Functions for more information on how to use and not to use random number functions.

Function: void mpz_urandomb (mpz_t rop, gmp_randstate_t state, mp_bitcnt_t n)

Generate a uniformly distributed random integer in the range 0 to 2ⁿ-1, inclusive.

The variable state must be initialized by calling one of the gmp_randinit functions (Random State Initialization) before invoking this function.

Function: void mpz_urandomm (mpz_t rop, gmp_randstate_t state, const mpz_t n)

Generate a uniform random integer in the range 0 to n-1, inclusive.

The variable state must be initialized by calling one of the gmp_randinit functions (Random State Initialization) before invoking this function.

Function: void mpz_rrandomb (mpz_t rop, gmp_randstate_t state, mp_bitcnt_t n)

Generate a random integer with long strings of zeros and ones in the binary representation. Useful for testing functions and algorithms, since this kind of random numbers have proven to be more likely to trigger corner-case bugs. The random number will be in the range 2^n-1 to 2ⁿ-1, inclusive.

The variable state must be initialized by calling one of the gmp_randinit functions (Random State Initialization) before invoking this function.

Function: void mpz_random (mpz_t rop, mp_size_t max_size)

Generate a random integer of at most max_size limbs. The generated random number doesn’t satisfy any particular requirements of randomness. Negative random numbers are generated when max_size is negative.

This function is obsolete. Use mpz_urandomb or mpz_urandomm instead.

Function: void mpz_random2 (mpz_t rop, mp_size_t max_size)

Generate a random integer of at most max_size limbs, with long strings of zeros and ones in the binary representation. Useful for testing functions and algorithms, since this kind of random numbers have proven to be more likely to trigger corner-case bugs. Negative random numbers are generated when max_size is negative.

This function is obsolete. Use mpz_rrandomb instead.

5.14 Integer Import and Export

mpz_t variables can be converted to and from arbitrary words of binary data with the following functions.

Function: void mpz_import (mpz_t rop, size_t count, int order, size_t size, int endian, size_t nails, const void *op)

Set rop from an array of word data at op.

The parameters specify the format of the data. count many words are read, each size bytes. order can be 1 for most significant word first or -1 for least significant first. Within each word endian can be 1 for most significant byte first, -1 for least significant first, or 0 for the native endianness of the host CPU. The most significant nails bits of each word are skipped, this can be 0 to use the full words.

There is no sign taken from the data, rop will simply be a positive integer. An application can handle any sign itself, and apply it for instance with mpz_neg.

There are no data alignment restrictions on op, any address is allowed.

Here’s an example converting an array of unsigned long data, most significant element first, and host byte order within each value.

unsigned long  a[20];
/* Initialize z and a */
mpz_import (z, 20, 1, sizeof(a[0]), 0, 0, a);

This example assumes the full sizeof bytes are used for data in the given type, which is usually true, and certainly true for unsigned long everywhere we know of. However on Cray vector systems it may be noted that short and int are always stored in 8 bytes (and with sizeof indicating that) but use only 32 or 46 bits. The nails feature can account for this, by passing for instance 8*sizeof(int)-INT_BIT.

Function: void * mpz_export (void *rop, size_t *countp, int order, size_t size, int endian, size_t nails, const mpz_t op)

Fill rop with word data from op.

The parameters specify the format of the data produced. Each word will be size bytes and order can be 1 for most significant word first or -1 for least significant first. Within each word endian can be 1 for most significant byte first, -1 for least significant first, or 0 for the native endianness of the host CPU. The most significant nails bits of each word are unused and set to zero, this can be 0 to produce full words.

The number of words produced is written to *countp, or countp can be NULL to discard the count. rop must have enough space for the data, or if rop is NULL then a result array of the necessary size is allocated using the current GMP allocation function (see Custom Allocation). In either case the return value is the destination used, either rop or the allocated block.

If op is non-zero then the most significant word produced will be non-zero. If op is zero then the count returned will be zero and nothing written to rop. If rop is NULL in this case, no block is allocated, just NULL is returned.

The sign of op is ignored, just the absolute value is exported. An application can use mpz_sgn to get the sign and handle it as desired. (see Integer Comparisons)

There are no data alignment restrictions on rop, any address is allowed.

When an application is allocating space itself the required size can be determined with a calculation like the following. Since mpz_sizeinbase always returns at least 1, count here will be at least one, which avoids any portability problems with malloc(0), though if z is zero no space at all is actually needed (or written).

numb = 8*size - nail;
count = (mpz_sizeinbase (z, 2) + numb-1) / numb;
p = malloc (count * size);

5.15 Miscellaneous Functions

Function: int mpz_fits_ulong_p (const mpz_t op)
Function: int mpz_fits_slong_p (const mpz_t op)
Function: int mpz_fits_uint_p (const mpz_t op)
Function: int mpz_fits_sint_p (const mpz_t op)
Function: int mpz_fits_ushort_p (const mpz_t op)
Function: int mpz_fits_sshort_p (const mpz_t op): Return non-zero iff the value of op fits in an unsigned long int, signed long int, unsigned int, signed int, unsigned short int, or signed short int, respectively. Otherwise, return zero.

Macro: int mpz_odd_p (const mpz_t op)
Macro: int mpz_even_p (const mpz_t op): Determine whether op is odd or even, respectively. Return non-zero if yes, zero if no. These macros evaluate their argument more than once.

Function: size_t mpz_sizeinbase (const mpz_t op, int base)

Return the size of op measured in number of digits in the given base. base can vary from 2 to 62. The sign of op is ignored, just the absolute value is used. The result will be either exact or 1 too big. If base is a power of 2, the result is always exact. If op is zero the return value is always 1.

This function can be used to determine the space required when converting op to a string. The right amount of allocation is normally two more than the value returned by mpz_sizeinbase, one extra for a minus sign and one for the null-terminator.

It will be noted that mpz_sizeinbase(op,2) can be used to locate the most significant 1 bit in op, counting from 1. (Unlike the bitwise functions which start from 0, See Logical and Bit Manipulation Functions.)

5.16 Special Functions

The functions in this section are for various special purposes. Most applications will not need them.

Function: void mpz_array_init (mpz_t integer_array, mp_size_t array_size, mp_size_t fixed_num_bits): This is an obsolete function. Do not use it.

Function: void * _mpz_realloc (mpz_t integer, mp_size_t new_alloc)

Change the space for integer to new_alloc limbs. The value in integer is preserved if it fits, or is set to 0 if not. The return value is not useful to applications and should be ignored.

mpz_realloc2 is the preferred way to accomplish allocation changes like this. mpz_realloc2 and _mpz_realloc are the same except that _mpz_realloc takes its size in limbs.

Function: mp_limb_t mpz_getlimbn (const mpz_t op, mp_size_t n)

Return limb number n from op. The sign of op is ignored, just the absolute value is used. The least significant limb is number 0.

mpz_size can be used to find how many limbs make up op. mpz_getlimbn returns zero if n is outside the range 0 to mpz_size(op)-1.

Function: size_t mpz_size (const mpz_t op): Return the size of op measured in number of limbs. If op is zero, the returned value will be zero.

Function: const mp_limb_t * mpz_limbs_read (const mpz_t x): Return a pointer to the limb array representing the absolute value of x. The size of the array is mpz_size(x). Intended for read access only.

Function: mp_limb_t * mpz_limbs_write (mpz_t x, mp_size_t n)
Function: mp_limb_t * mpz_limbs_modify (mpz_t x, mp_size_t n): Return a pointer to the limb array, intended for write access. The array is reallocated as needed, to make room for n limbs. Requires n > 0. The mpz_limbs_modify function returns an array that holds the old absolute value of x, while mpz_limbs_write may destroy the old value and return an array with unspecified contents.

Function: void mpz_limbs_finish (mpz_t x, mp_size_t s): Updates the internal size field of x. Used after writing to the limb array pointer returned by mpz_limbs_write or mpz_limbs_modify is completed. The array should contain abs(s) valid limbs, representing the new absolute value for x, and the sign of x is taken from the sign of s. This function never reallocates x, so the limb pointer remains valid.

void foo (mpz_t x)
{
  mp_size_t n, i;
  mp_limb_t *xp;
  n = mpz_size (x);
  xp = mpz_limbs_modify (x, 2*n);
  for (i = 0; i < n; i++)
    xp[n+i] = xp[n-1-i];
  mpz_limbs_finish (x, mpz_sgn (x) < 0 ? - 2*n : 2*n);
}

Function: mpz_srcptr mpz_roinit_n (mpz_t x, const mp_limb_t *xp, mp_size_t xs): Special initialization of x, using the given limb array and size. x should be treated as read-only: it can be passed safely as input to any mpz function, but not as an output. The array xp must point to at least a readable limb, its size is abs(xs), and the sign of x is the sign of xs. For convenience, the function returns x, but cast to a const pointer type.

void foo (mpz_t x)
{
  static const mp_limb_t y[3] = { 0x1, 0x2, 0x3 };
  mpz_t tmp;
  mpz_add (x, x, mpz_roinit_n (tmp, y, 3));
}

Macro: mpz_t MPZ_ROINIT_N (mp_limb_t *xp, mp_size_t xs): This macro expands to an initializer which can be assigned to an mpz_t variable. The limb array xp must point to at least a readable limb, moreover, unlike the mpz_roinit_n function, the array must be normalized: if xs is non-zero, then xp[abs(xs)-1] must be non-zero. Intended primarily for constant values. Using it for non-constant values requires a C compiler supporting C99.

void foo (mpz_t x)
{
  static const mp_limb_t ya[3] = { 0x1, 0x2, 0x3 };
  static const mpz_t y = MPZ_ROINIT_N ((mp_limb_t *) ya, 3);
  mpz_add (x, x, y);
}

• Initializing Integers
• Assigning Integers
• Simultaneous Integer Init & Assign
• Converting Integers
• Integer Arithmetic
• Integer Division
• Integer Exponentiation
• Integer Roots
• Number Theoretic Functions
• Integer Comparisons
• Integer Logic and Bit Fiddling
• I/O of Integers
• Integer Random Numbers
• Integer Import and Export
• Miscellaneous Integer Functions
• Integer Special Functions