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

Next: Rational Number Functions, Previous: Reporting Bugs, Up: Top [Index]

## 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`

.

Next: Assigning Integers, Previous: Integer Functions, Up: Integer Functions [Index]

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

Next: Simultaneous Integer Init & Assign, Previous: Initializing Integers, Up: Integer Functions [Index]

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

Next: Converting Integers, Previous: Assigning Integers, Up: Integer Functions [Index]

### 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.)

Next: Integer Arithmetic, Previous: Simultaneous Integer Init & Assign, Up: Integer Functions [Index]

### 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(*and the exponent is stored to`d`)<1`*`

.`exp`is the (truncated)`d`* 2^`exp``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 (`

. The two extra bytes are for a possible minus sign, and the null-terminator.`op`,`base`) + 2A pointer to the result string is returned, being either the allocated block, or the given

`str`.

Next: Integer Division, Previous: Converting Integers, Up: Integer Functions [Index]

### 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. This operation can also be defined as a left shift by`op1`times 2 raised to`op2``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`.

Next: Integer Exponentiation, Previous: Integer Arithmetic, Up: Integer Functions [Index]

### 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,. The rounding is in three styles, each suiting different applications.`d`=2^`b`-
`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, and`n`=`q`*`d`+`r``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^*. These functions are implemented as right shifts and bit masks, but of course they round the same as the other functions.`b`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. Unlike the other division functions,`n`=`q`*`d`is accepted and following the rule it can be seen that only 0 is considered divisible by 0.`d`=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. Unlike the other division functions,`n`=`c`+`q`*`d`is accepted and following the rule it can be seen that`d`=0`n`and`c`are considered congruent mod 0 only when exactly equal.

Next: Integer Roots, Previous: Integer Division, Up: Integer Functions [Index]

### 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 inverseexists (see`base`^{-1}mod`mod``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

and that`exp`> 0`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. The case`base`raised to`exp`*0^0*yields 1.

Next: Number Theoretic Functions, Previous: Integer Exponentiation, Up: Integer Functions [Index]

### 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`n`th root of`op`. Return non-zero if the computation was exact, i.e., if`op`is`rop`to the`n`th 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`n`th 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*, like`op``mpz_sqrt`

. Set`rop2`to the remainder, which will be zero if`op`-`rop1`*`rop1``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 integersand`a`, with`b`, such that`b`>1.`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.

Next: Integer Comparisons, Previous: Integer Roots, Up: Integer Functions [Index]

### 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^(-*. Reasonable values of`reps`)`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. The value in`a`*`s`+`b`*`t`=`g``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(*and`s`) < abs(`b`) / (2`g`)*abs(*, and these relations define`t`) < abs(`a`) / (2`g`)`s`and`t`uniquely. There are a few exceptional cases:If

*abs(*, then`a`) = abs(`b`),`s`= 0.`t`= sgn(`b`)Otherwise,

if`s`= sgn(`a`)or`b`= 0*abs(*, and`b`) = 2`g`if`t`= sgn(`b`)or`a`= 0*abs(*.`a`) = 2`g`In all cases,

if and only if`s`= 0, i.e., if`g`= abs(`b`)`b`divides`a`or.`a`=`b`= 0If

`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 <=*(with`rop`< abs(`op2`)possible only when`rop`= 0*abs(*, i.e., in the somewhat degenerate zero ring). If an inverse doesn’t exist the return value is zero and`op2`) = 1`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

*(*. This is defined only for`a`/`b`)`b`odd.

- Function:
*int***mpz_legendre***(const mpz_t*`a`, const mpz_t`p`) -
Calculate the Legendre symbol

*(*. This is defined only for`a`/`p`)`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

*(*with the Kronecker extension`a`/`b`)*(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

and store the result in`n`over`k``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.

Next: Integer Logic and Bit Fiddling, Previous: Number Theoretic Functions, Up: Integer Functions [Index]

### 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, zero if`op1`>`op2`, or a negative value if`op1`=`op2`.`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(*, zero if`op1`) > abs(`op2`)*abs(*, or a negative value if`op1`) = abs(`op2`)*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, 0 if`op`> 0, and`op`= 0*-1*if.`op`< 0This function is actually implemented as a macro. It evaluates its argument multiple times.

Next: I/O of Integers, Previous: Integer Comparisons, Up: Integer Functions [Index]

### 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

, return the population count of`op`>=0`op`, which is the number of 1 bits in the binary representation. If, the number of 1s is infinite, and the return value is the largest possible`op`<0`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.

Next: Integer Random Numbers, Previous: Integer Logic and Bit Fiddling, Up: Integer Functions [Index]

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

Next: Integer Import and Export, Previous: I/O of Integers, Up: Integer Functions [Index]

### 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*, inclusive.^{n}-1The 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

, inclusive.`n`-1The 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*to^{n-1}*2*, inclusive.^{n}-1The 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.

Next: Miscellaneous Integer Functions, Previous: Integer Random Numbers, Up: Integer Functions [Index]

### 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

`*`

, or`countp``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);

Next: Integer Special Functions, Previous: Integer Import and Export, Up: Integer Functions [Index]

### 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(`

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

Previous: Miscellaneous Integer Functions, Up: Integer Functions [Index]

### 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(`

. Intended for read access only.`x`)

- 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. The`n`> 0`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(*valid limbs, representing the new absolute value for`s`)`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(*, and the sign of`xs`)`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

must be non-zero. Intended primarily for constant values. Using it for non-constant values requires a C compiler supporting C99.`xp`[*abs(*]`xs`)-1

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); }

Previous: Miscellaneous Integer Functions, Up: Integer Functions [Index]