GMP

Usage

use GMP;

Support for GNU Multiple Precision Arithmetic

This module provides a low-level interface to a substantial fraction of the GMP library (the GNU Multiple Precision arithmetic library). This support includes the C types for GMP integers, floating point numbers, and random numbers, and nearly every operation on those types. These types and functions enable efficient multi-precision computation within a single locale. See the GMP homepage for more information on this library.

The module BigInteger leverages this interface to define the record bigint. The methods on the record bigint are locale aware so that Chapel programs can, for example, create a distributed array of GMP integers. That record also provides operator overloads for the standard arithmetic and assignment operators which tend to enable a more natural expression of some algorithms. Please see the documentation in BigInteger for details.

Using the GMP Module

Step 1:

Build Chapel with GMP

# To use the already-installed GMP
export CHPL_GMP=system
# To use the distributed GMP
export CHPL_GMP=gmp
# From $CHPL_HOME
make clean; make
Step 2:

Have your Chapel program use the standard GMP module

use GMP;   // put this statement in your Chapel program
Step 3:
Start using the supported subset of GMP types and routines defined in this module or the bigint record (see BigInteger).

Calling GMP functions directly

The low-level option for Chapel programs using multi-precision numbers is to the GMP functions directly. For a full reference to GMP capabilities, please refer to the GMP website and the GMP documentation.

At present, Chapel's GMP module supports the following GMP types:

And all mpz_t GMP routines, as well as the following routines:

proc chpl_gmp_alloc(size: size_t): c_void_ptr
proc chpl_gmp_realloc(ptr: c_void_ptr, old_size: size_t, new_size: size_t): c_void_ptr
proc chpl_gmp_free(ptr: c_void_ptr, old_size: size_t)
proc chpl_gmp_init()
type mp_bitcnt_t = c_ulong

The GMP mp_bitcnt_t type

type mp_size_t = c_long

The GMP mp_size_t type

type mp_limb_t

This is normally uint(64) but can depend on configuration.

const mp_bits_per_limb: c_int

The GMP mp_bits_per_limb` constant

type mpz_t = 1*__mpz_struct

The GMP mpz_t type

type mpf_t = 1*__mpf_struct

The GMP mpf_t type

type gmp_randstate_t = 1*__gmp_randstate_struct

The GMP gmp_randstate_t type

proc mpz_init(ref x: mpz_t)
proc mpz_init2(ref x: mpz_t, n: mp_bitcnt_t)
proc mpz_clear(ref x: mpz_t)
proc _mpz_realloc(ref x: mpz_t, new_alloc: mp_size_t)
proc mpz_realloc2(ref x: mpz_t, n: mp_bitcnt_t)
proc mpz_set(ref rop: mpz_t, const ref op: mpz_t)
proc mpz_set_ui(ref rop: mpz_t, op: c_ulong)
proc mpz_set_si(ref rop: mpz_t, op: c_long)
proc mpz_set_d(ref rop: mpz_t, op: c_double)
proc mpz_set_str(ref rop: mpz_t, str: c_string, base: c_int)
proc mpz_swap(ref rop1: mpz_t, ref rop2: mpz_t)
proc mpz_init_set(ref rop: mpz_t, const ref op: mpz_t)
proc mpz_init_set_ui(ref rop: mpz_t, op: c_ulong)
proc mpz_init_set_si(ref rop: mpz_t, op: c_long)
proc mpz_init_set_d(ref rop: mpz_t, op: c_double)
proc mpz_init_set_str(ref rop: mpz_t, str: c_string, base: c_int): c_int
proc mpz_get_ui(const ref op: mpz_t): c_ulong
proc mpz_get_si(const ref op: mpz_t): c_long
proc mpz_get_d(const ref op: mpz_t): c_double
proc mpz_get_d_2exp(ref exp: c_long, const ref op: mpz_t): c_double
proc mpz_get_str(str: c_string, base: c_int, const ref op: mpz_t): c_string
proc mpz_add(ref rop: mpz_t, const ref op1: mpz_t, const ref op2: mpz_t)
proc mpz_add_ui(ref rop: mpz_t, const ref op1: mpz_t, op2: c_ulong)
proc mpz_sub(ref rop: mpz_t, const ref op1: mpz_t, const ref op2: mpz_t)
proc mpz_sub_ui(ref rop: mpz_t, const ref op1: mpz_t, op2: c_ulong)
proc mpz_ui_sub(ref rop: mpz_t, op1: c_ulong, const ref op2: mpz_t)
proc mpz_mul(ref rop: mpz_t, const ref op1: mpz_t, const ref op2: mpz_t)
proc mpz_mul_si(ref rop: mpz_t, const ref op1: mpz_t, op2: c_long)
proc mpz_mul_ui(ref rop: mpz_t, const ref op1: mpz_t, op2: c_ulong)
proc mpz_addmul(ref rop: mpz_t, const ref op1: mpz_t, const ref op2: mpz_t)
proc mpz_addmul_ui(ref rop: mpz_t, const ref op1: mpz_t, op2: c_ulong)
proc mpz_submul(ref rop: mpz_t, const ref op1: mpz_t, const ref op2: mpz_t)
proc mpz_submul_ui(ref rop: mpz_t, const ref op1: mpz_t, op2: c_ulong)
proc mpz_mul_2exp(ref rop: mpz_t, const ref op1: mpz_t, op2: mp_bitcnt_t)
proc mpz_neg(ref rop: mpz_t, const ref op: mpz_t)
proc mpz_abs(ref rop: mpz_t, const ref op: mpz_t)
proc mpz_cdiv_q(ref q: mpz_t, const ref n: mpz_t, const ref d: mpz_t)
proc mpz_cdiv_r(ref r: mpz_t, const ref n: mpz_t, const ref d: mpz_t)
proc mpz_cdiv_qr(ref q: mpz_t, ref r: mpz_t, const ref n: mpz_t, const ref d: mpz_t)
proc mpz_cdiv_q_ui(ref q: mpz_t, const ref n: mpz_t, d: c_ulong): c_ulong
proc mpz_cdiv_r_ui(ref r: mpz_t, const ref n: mpz_t, d: c_ulong): c_ulong
proc mpz_cdiv_qr_ui(ref q: mpz_t, ref r: mpz_t, const ref n: mpz_t, d: c_ulong): c_ulong
proc mpz_cdiv_ui(const ref n: mpz_t, d: c_ulong): c_ulong
proc mpz_cdiv_q_2exp(ref q: mpz_t, const ref n: mpz_t, b: mp_bitcnt_t)
proc mpz_cdiv_r_2exp(ref r: mpz_t, const ref n: mpz_t, b: mp_bitcnt_t)
proc mpz_fdiv_q(ref q: mpz_t, const ref n: mpz_t, const ref d: mpz_t)
proc mpz_fdiv_r(ref r: mpz_t, const ref n: mpz_t, const ref d: mpz_t)
proc mpz_fdiv_qr(ref q: mpz_t, ref r: mpz_t, const ref n: mpz_t, const ref d: mpz_t)
proc mpz_fdiv_q_ui(ref q: mpz_t, const ref n: mpz_t, d: c_ulong): c_ulong
proc mpz_fdiv_r_ui(ref r: mpz_t, const ref n: mpz_t, d: c_ulong): c_ulong
proc mpz_fdiv_qr_ui(ref q: mpz_t, ref r: mpz_t, const ref n: mpz_t, d: c_ulong): c_ulong
proc mpz_fdiv_ui(const ref n: mpz_t, d: c_ulong): c_ulong
proc mpz_fdiv_q_2exp(ref q: mpz_t, const ref n: mpz_t, b: mp_bitcnt_t)
proc mpz_fdiv_r_2exp(ref r: mpz_t, const ref n: mpz_t, b: mp_bitcnt_t)
proc mpz_tdiv_q(ref q: mpz_t, const ref n: mpz_t, const ref d: mpz_t)
proc mpz_tdiv_r(ref r: mpz_t, const ref n: mpz_t, const ref d: mpz_t)
proc mpz_tdiv_qr(ref q: mpz_t, ref r: mpz_t, const ref n: mpz_t, const ref d: mpz_t)
proc mpz_tdiv_q_ui(ref q: mpz_t, const ref n: mpz_t, d: c_ulong): c_ulong
proc mpz_tdiv_r_ui(ref r: mpz_t, const ref n: mpz_t, d: c_ulong): c_ulong
proc mpz_tdiv_qr_ui(ref q: mpz_t, ref r: mpz_t, const ref n: mpz_t, d: c_ulong): c_ulong
proc mpz_tdiv_ui(const ref n: mpz_t, d: c_ulong): c_ulong
proc mpz_tdiv_q_2exp(ref q: mpz_t, const ref n: mpz_t, b: mp_bitcnt_t)
proc mpz_tdiv_r_2exp(ref r: mpz_t, const ref n: mpz_t, b: mp_bitcnt_t)
proc mpz_mod(ref rop: mpz_t, const ref n: mpz_t, const ref d: mpz_t)
proc mpz_mod_ui(ref rop: mpz_t, const ref n: mpz_t, d: c_ulong): c_ulong
proc mpz_divexact(ref q: mpz_t, const ref n: mpz_t, const ref d: mpz_t)
proc mpz_divexact_ui(ref q: mpz_t, const ref n: mpz_t, d: c_ulong)
proc mpz_divisible_p(const ref n: mpz_t, const ref d: mpz_t): c_int
proc mpz_divisible_ui_p(const ref n: mpz_t, d: c_ulong): c_int
proc mpz_divisible_2exp_p(const ref n: mpz_t, b: mp_bitcnt_t): c_int
proc mpz_congruent_p(const ref n: mpz_t, const ref c: mpz_t, const ref d: mpz_t): c_int
proc mpz_congruent_ui_p(const ref n: mpz_t, c: c_ulong, d: c_ulong): c_int
proc mpz_congruent_2exp_p(const ref n: mpz_t, const ref c: mpz_t, b: mp_bitcnt_t): c_int
proc mpz_powm(ref rop: mpz_t, const ref base: mpz_t, const ref exp: mpz_t, const ref mod: mpz_t)
proc mpz_powm_ui(ref rop: mpz_t, const ref base: mpz_t, exp: c_ulong, const ref mod: mpz_t)
proc mpz_powm_sec(ref rop: mpz_t, const ref base: mpz_t, const ref exp: mpz_t, const ref mod: mpz_t)
proc mpz_pow_ui(ref rop: mpz_t, const ref base: mpz_t, exp: c_ulong)
proc mpz_ui_pow_ui(ref rop: mpz_t, base: c_ulong, exp: c_ulong)
proc mpz_root(ref rop: mpz_t, const ref op: mpz_t, n: c_ulong): c_int
proc mpz_rootrem(ref root: mpz_t, ref rem: mpz_t, const ref u: mpz_t, n: c_ulong)
proc mpz_sqrt(ref rop: mpz_t, const ref op: mpz_t)
proc mpz_sqrtrem(ref rop1: mpz_t, ref rop2: mpz_t, const ref op: mpz_t)
proc mpz_perfect_power_p(const ref op: mpz_t): c_int
proc mpz_perfect_square_p(const ref op: mpz_t): c_int
proc mpz_probab_prime_p(ref n: mpz_t, reps: c_int): c_int
proc mpz_nextprime(ref rop: mpz_t, const ref op: mpz_t)
proc mpz_gcd(ref rop: mpz_t, const ref op1: mpz_t, const ref op2: mpz_t)
proc mpz_gcd_ui(ref rop: mpz_t, const ref op1: mpz_t, op2: c_ulong)
proc mpz_gcdext(ref g: mpz_t, ref s: mpz_t, ref t: mpz_t, const ref a: mpz_t, const ref b: mpz_t)
proc mpz_lcm(ref rop: mpz_t, const ref op1: mpz_t, const ref op2: mpz_t)
proc mpz_lcm_ui(ref rop: mpz_t, const ref op1: mpz_t, op2: c_ulong)
proc mpz_invert(ref rop: mpz_t, const ref op1: mpz_t, const ref op2: mpz_t): c_int
proc mpz_jacobi(const ref a: mpz_t, const ref b: mpz_t): c_int
proc mpz_legendre(const ref a: mpz_t, const ref p: mpz_t): c_int
proc mpz_kronecker(const ref a: mpz_t, const ref b: mpz_t): c_int
proc mpz_kronecker_si(const ref a: mpz_t, b: c_long): c_int
proc mpz_kronecker_ui(const ref a: mpz_t, b: c_ulong): c_int
proc mpz_si_kronecker(a: c_long, const ref b: mpz_t): c_int
proc mpz_ui_kronecker(a: c_ulong, const ref b: mpz_t): c_int
proc mpz_remove(ref rop: mpz_t, const ref op: mpz_t, const ref f: mpz_t): c_ulong
proc mpz_fac_ui(ref rop: mpz_t, n: c_ulong)
proc mpz_2fac_ui(ref rop: mpz_t, n: c_ulong)
proc mpz_mfac_uiui(ref rop: mpz_t, n: c_ulong, m: c_ulong)
proc mpz_primorial_ui(ref rop: mpz_t, n: c_ulong)
proc mpz_bin_ui(ref rop: mpz_t, const ref n: mpz_t, k: c_ulong)
proc mpz_bin_uiui(ref rop: mpz_t, n: c_ulong, k: c_ulong)
proc mpz_fib_ui(ref fn: mpz_t, n: c_ulong)
proc mpz_fib2_ui(ref fn: mpz_t, ref fnsub1: mpz_t, n: c_ulong)
proc mpz_lucnum_ui(ref ln: mpz_t, n: c_ulong)
proc mpz_lucnum2_ui(ref ln: mpz_t, ref lnsub1: mpz_t, n: c_ulong)
proc mpz_cmp(const ref op1: mpz_t, const ref op2: mpz_t): c_int
proc mpz_cmp_d(const ref op1: mpz_t, op2: c_double): c_int
proc mpz_cmp_si(const ref op1: mpz_t, op2: c_long): c_int
proc mpz_cmp_ui(const ref op1: mpz_t, op2: c_ulong): c_int
proc mpz_cmpabs(const ref op1: mpz_t, const ref op2: mpz_t): c_int
proc mpz_cmpabs_d(const ref op1: mpz_t, op2: c_double): c_int
proc mpz_cmpabs_ui(const ref op1: mpz_t, op2: c_ulong): c_int
proc mpz_sgn(const ref op: mpz_t): c_int
proc mpz_and(ref rop: mpz_t, const ref op1: mpz_t, const ref op2: mpz_t)
proc mpz_ior(ref rop: mpz_t, const ref op1: mpz_t, const ref op2: mpz_t)
proc mpz_xor(ref rop: mpz_t, const ref op1: mpz_t, const ref op2: mpz_t)
proc mpz_com(ref rop: mpz_t, const ref op: mpz_t)
proc mpz_popcount(const ref op: mpz_t): c_ulong
proc mpz_hamdist(const ref op1: mpz_t, const ref op2: mpz_t): c_ulong
proc mpz_scan0(const ref op: mpz_t, starting_bit: mp_bitcnt_t): c_ulong
proc mpz_scan1(const ref op: mpz_t, starting_bit: mp_bitcnt_t): c_ulong
proc mpz_setbit(ref rop: mpz_t, bit_index: mp_bitcnt_t)
proc mpz_clrbit(ref rop: mpz_t, bit_index: mp_bitcnt_t)
proc mpz_combit(ref rop: mpz_t, bit_index: mp_bitcnt_t)
proc mpz_tstbit(const ref op: mpz_t, bit_index: mp_bitcnt_t): c_int
proc mpz_urandomb(ref rop: mpz_t, ref state: gmp_randstate_t, n: mp_bitcnt_t)
proc mpz_urandomm(ref rop: mpz_t, ref state: gmp_randstate_t, const ref n: mpz_t)
proc mpz_rrandomb(ref rop: mpz_t, ref state: gmp_randstate_t, n: mp_bitcnt_t)
proc mpz_random(ref rop: mpz_t, max_size: mp_size_t)
proc mpz_random2(ref rop: mpz_t, max_size: mp_size_t)
proc mpz_fits_ulong_p(const ref op: mpz_t): c_int
proc mpz_fits_slong_p(const ref op: mpz_t): c_int
proc mpz_fits_uint_p(const ref op: mpz_t): c_int
proc mpz_fits_sint_p(const ref op: mpz_t): c_int
proc mpz_fits_ushort_p(const ref op: mpz_t): c_int
proc mpz_fits_sshort_p(const ref op: mpz_t): c_int
proc mpz_odd_p(const ref op: mpz_t): c_int
proc mpz_even_p(const ref op: mpz_t): c_int
proc mpz_sizeinbase(const ref op: mpz_t, base: c_int): size_t
proc mpz_size(const ref x: mpz_t): size_t
proc mpz_limbs_write(ref x: mpz_t, n: mp_size_t): c_ptr(mp_limb_t)
proc mpz_limbs_finish(ref x: mpz_t, s: mp_size_t)
proc mpf_set_default_prec(prec: mp_bitcnt_t)
proc mpf_get_default_prec(): mp_bitcnt_t
proc mpf_init(ref x: mpf_t)
proc mpf_init2(ref x: mpf_t, prec: mp_bitcnt_t)
proc mpf_clear(ref x: mpf_t)
proc mpf_get_prec(const ref op: mpf_t): mp_bitcnt_t
proc mpf_set_prec(ref rop: mpf_t, prec: mp_bitcnt_t)
proc mpf_set_prec_raw(ref rop: mpf_t, prec: mp_bitcnt_t)
proc mpf_set(ref rop: mpf_t, const ref op: mpz_t)
proc mpf_set_ui(ref rop: mpf_t, op: c_ulong)
proc mpf_set_si(ref rop: mpf_t, op: c_long)
proc mpf_set_d(ref rop: mpf_t, op: c_double)
proc mpf_set_z(ref rop: mpf_t, const ref op: mpz_t)
proc mpf_set_q(ref rop: mpf_t, const ref op: mpz_t)
proc mpf_set_str(ref rop: mpz_t, str: c_string, base: c_int)
proc mpf_swap(ref rop1: mpf_t, ref rop2: mpz_t)
proc mpf_init_set(ref rop: mpf_t, const ref op: mpz_t)
proc mpf_init_set_ui(ref rop: mpf_t, op: c_ulong)
proc mpf_init_set_si(ref rop: mpf_t, op: c_long)
proc mpf_init_set_d(ref rop: mpf_t, op: c_double)
proc mpf_get_d(const ref op: mpf_t): c_double
proc mpf_get_d_2exp(ref exp: c_long, const ref op: mpz_t): c_double
proc mpf_get_si(const ref op: mpf_t): c_long
proc mpf_get_ui(const ref op: mpf_t): c_ulong
proc mpf_add(ref rop: mpf_t, const ref op1: mpf_t, const ref op2: mpf_t)
proc mpf_add_ui(ref rop: mpf_t, const ref op1: mpf_t, op2: c_ulong)
proc mpf_sub(ref rop: mpf_t, const ref op1: mpf_t, const ref op2: mpf_t)
proc mpf_ui_sub(ref rop: mpf_t, op1: c_ulong, const ref op2: mpf_t)
proc mpf_sub_ui(ref rop: mpf_t, const ref op1: mpf_t, op2: c_ulong)
proc mpf_mul(ref rop: mpf_t, const ref op1: mpf_t, const ref op2: mpf_t)
proc mpf_mul_ui(ref rop: mpf_t, const ref op1: mpf_t, op2: c_ulong)
proc mpf_div(ref rop: mpf_t, const ref op1: mpf_t, const ref op2: mpf_t)
proc mpf_ui_div(ref rop: mpf_t, op1: c_ulong, const ref op2: mpf_t)
proc mpf_div_ui(ref rop: mpf_t, const ref op1: mpf_t, op2: c_ulong)
proc mpf_sqrt(ref rop: mpf_t, const ref op: mpf_t)
proc mpf_sqrt_ui(ref rop: mpf_t, op: c_ulong)
proc mpf_pow_ui(ref rop: mpf_t, const ref op1: mpf_t, op2: c_ulong)
proc mpf_neg(ref rop: mpf_t, const ref op: mpf_t)
proc mpf_abs(ref rop: mpf_t, const ref op: mpf_t)
proc mpf_mul_2exp(ref rop: mpf_t, const ref op1: mpf_t, op2: mp_bitcnt_t)
proc mpf_div_2exp(ref rop: mpf_t, const ref op1: mpf_t, op2: mp_bitcnt_t)
proc mpf_cmp(const ref op1: mpf_t, const ref op2: mpf_t): c_int
proc mpf_cmp_z(const ref op1: mpf_t, const ref op2: mpf_t): c_int
proc mpf_cmp_d(const ref op1: mpf_t, op2: c_double): c_int
proc mpf_cmp_ui(const ref op1: mpf_t, op2: c_ulong): c_int
proc mpf_cmp_si(const ref op1: mpf_t, op2: c_long): c_int
proc mpf_eq(const ref op1: mpf_t, const ref op2: mpf_t, op3: mp_bitcnt_t): c_int
proc mpf_reldiff(const ref rop: mpf_t, const ref op1: mpf_t, const ref op2: mpf_t)
proc mpf_sgn(const ref op: mpf_t)
proc mpf_out_str(stream: _file, base: c_int, n_digits: size_t, const ref op: mpf_t)
proc mpf_inp_str(ref rop: mpf_t, stream: _file, base: c_int)
proc mpf_ceil(ref rop: mpf_t, const ref op: mpf_t)
proc mpf_floor(ref rop: mpf_t, const ref op: mpf_t)
proc mpf_trunc(ref rop: mpf_t, const ref op: mpf_t)
proc mpf_integer_p(const ref op: mpf_t): c_int
proc mpf_fits_ulong_p(const ref op: mpf_t): c_int
proc mpf_fits_slong_p(const ref op: mpf_t): c_int
proc mpf_fits_uint_p(const ref op: mpf_t): c_int
proc mpf_fits_sint_p(const ref op: mpf_t): c_int
proc mpf_fits_ushort_p(const ref op: mpf_t): c_int
proc mpf_fits_sshort_p(const ref op: mpf_t): c_int
proc mpf_urandomb(ref rop: mpf_t, ref state: gmp_randstate_t, nbits: mp_bitcnt_t)
proc gmp_randinit_default(ref state: gmp_randstate_t)
proc gmp_randinit_mt(ref state: gmp_randstate_t)
proc gmp_randinit_lc_2exp(ref state: gmp_randstate_t, const ref a: mpz_t, c: c_ulong, m2exp: mp_bitcnt_t)
proc gmp_randinit_lc_2exp_size(ref state: gmp_randstate_t, size: mp_bitcnt_t)
proc gmp_randinit_set(ref rop: gmp_randstate_t, ref op: gmp_randstate_t)
proc gmp_randclear(ref state: gmp_randstate_t)
proc gmp_randseed(ref state: gmp_randstate_t, const ref seed: mpz_t)
proc gmp_randseed_ui(ref state: gmp_randstate_t, seed: c_ulong)
proc gmp_urandomb_ui(ref state: gmp_randstate_t, n: c_ulong): c_ulong
proc gmp_urandomm_ui(ref state: gmp_randstate_t, n: c_ulong): c_ulong
proc gmp_printf(fmt: c_string, arg ...)
proc gmp_fprintf(fp: _file, fmt: c_string, arg ...)
proc gmp_fprintf(fp: _file, fmt: c_string, arg ...)
proc gmp_asprintf(ref ret: c_string, fmt: c_string, arg ...)
proc chpl_gmp_get_mpz(ref ret: mpz_t, src_locale: int, in from: __mpz_struct, copy_allocated: bool = false)

Get an MPZ value stored on another locale

proc chpl_gmp_mpz_nlimbs(const ref from: mpz_t): uint(64)

Return the number of limbs used in the number

proc chpl_gmp_mpz_getlimbn(const ref from: mpz_t, n: integral): uint(64)

Return the i'th limb used in the number (counting from 0)

proc chpl_gmp_mpz_get_str(base: c_int, const ref x: mpz_t): c_string

Get an mpz_t as a string

class GMPRandom
var state: gmp_randstate_t
proc init()
proc init(twister: bool)
proc init(a: bigint, c: uint, m2exp: uint)
proc init(size: uint)
proc seed(seed: bigint)
proc seed(seed: uint)
proc urandomb(nbits: uint): uint
proc urandomm(n: uint): uint
proc urandomb_ui(nbits: uint): uint
proc urandomm_ui(n: uint): uint
proc urandomb(ref r: bigint, nbits: uint)
proc urandomm(ref r: bigint, n: bigint)
proc rrandomb(ref r: bigint, nbits: uint)