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 two’s 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.