BigInteger

Usage

use BigInteger;

The bigint record supports arithmetic operations on arbitrary precision integers in a manner that is broadly consistent with the conventional operations on primitive fixed length integers.

The current implementation is based on the low-level types and functions defined in the GMP module i.e. it is implemented using the GNU Multiple Precision Integer Arithmetic library (GMP). More specifically the record bigint wraps the GMP type mpz_t.

The primary benefits of bigint over mpz_t are

  1. support for multi-locale programs
  2. the convenience of arithmetic operator overloads
  3. automatic memory management of GMP data structures

In addition to the expected set of operations, this record provides a number of methods that wrap GMP functions in a natural way:

use BigInteger;

var   a = new bigint(234958444);
const b = new bigint("4847382292989382987395534934347");
var   c = new bigint();

writeln(a * b);

c.fac(100);
writeln(c);

Wrapping an mpz_t in a bigint record may introduce a measurable overhead in some cases.

The GMP library defines a low-level API that is based on side-effecting compound operations. The documentation recommends that one prefer to reuse a small number of existing mpz_t structures rather than using many values of short duration.

Matching this style using bigint records and the compound assignment operators is likely to provide comparable performance to an implementation based on mpz_t. So, for example:

x  = b
x *= c;
x += a;

is likely to achieve better performance than:

x = a + b * c;

In the fall of 2016 the Chapel compiler introduces two short lived temporaries for the intermediate results of the binary operators.

If peak performance is required, perhaps in a critical loop, then it is always possible to invoke the GMP functions directly. For example one might express:

a = a + b * c;

as:

mpz_addmul(a.mpz, b.mpz, c.mpz);

As usual the details are application specific and it is best to measure when peak performance is required.

The operators on bigint include variations that accept Chapel integers e.g.:

var a = new bigint("9738639463465935");
var b = 9395739153 * a;

The Chapel int(64) literal is converted to an underlying, platform-specific C integer, to invoke the underlying GMP primitive function. This example is likely to work well on popular 64-bit platforms but to fail on common 32-bit platforms. Runtime checks are used to ensure the Chapel types can safely be cast to the platform-specific types. Ths program will halt if the Chapel value cannot be represented using the GMP scalar type.

The checks are controlled by the compiler options --[no-]cast-checks, --fast, etc.

See GMP for more information on how to use GMP with Chapel.

enum Round { DOWN = -1, ZERO = 0, UP = 1 }
record bigint
var mpz: mpz_t

The underlying GMP C structure

proc init()
proc init(const ref num: bigint)
proc init(num: int)
proc init(num: uint)
proc init(str: string, base: int = 0)
proc init(str: string, base: int = 0, out error: syserr)
proc size(): size_t
proc sizeinbase(base: int): uint
proc numLimbs: uint
proc get_limbn(n: uint): uint
proc mpzStruct(): __mpz_struct
proc get_d_2exp(): (uint(32), real)
proc get_str(base: int = 10): string
proc writeThis(writer)
proc =(ref lhs: bigint, const ref rhs: bigint)
proc =(ref lhs: bigint, rhs: int)
proc =(ref lhs: bigint, rhs: uint)
proc +(const ref a: bigint)
proc -(const ref a: bigint)
proc ~(const ref a: bigint)
proc +(const ref a: bigint, const ref b: bigint)
proc +(const ref a: bigint, b: int)
proc +(a: int, const ref b: bigint)
proc +(const ref a: bigint, b: uint)
proc +(a: uint, const ref b: bigint)
proc -(const ref a: bigint, const ref b: bigint)
proc -(const ref a: bigint, const ref b: int)
proc -(a: int, const ref b: bigint)
proc -(const ref a: bigint, b: uint)
proc -(a: uint, const ref b: bigint)
proc *(const ref a: bigint, const ref b: bigint)
proc *(const ref a: bigint, b: int)
proc *(a: int, const ref b: bigint)
proc *(const ref a: bigint, b: uint)
proc *(a: uint, const ref b: bigint)
proc /(const ref a: bigint, const ref b: bigint)
proc /(const ref a: bigint, b: integral)
proc **(const ref base: bigint, const ref exp: bigint)
proc **(const ref base: bigint, exp: int)
proc **(const ref base: bigint, exp: uint)
proc %(const ref a: bigint, const ref b: bigint)
proc %(const ref a: bigint, b: int)
proc %(const ref a: bigint, b: uint)
proc <<(const ref a: bigint, b: int)
proc <<(const ref a: bigint, b: uint)
proc >>(const ref a: bigint, b: int)
proc >>(const ref a: bigint, b: uint)
proc &(const ref a: bigint, const ref b: bigint)
proc |(const ref a: bigint, const ref b: bigint)
proc ^(const ref a: bigint, const ref b: bigint)
proc ==(const ref a: bigint, const ref b: bigint)
proc ==(const ref a: bigint, b: int)
proc ==(a: int, const ref b: bigint)
proc ==(const ref a: bigint, b: uint)
proc ==(a: uint, const ref b: bigint)
proc !=(const ref a: bigint, const ref b: bigint)
proc !=(const ref a: bigint, b: int)
proc !=(a: int, const ref b: bigint)
proc !=(const ref a: bigint, b: uint)
proc !=(a: uint, const ref b: bigint)
proc >(const ref a: bigint, const ref b: bigint)
proc >(const ref a: bigint, b: int)
proc >(b: int, const ref a: bigint)
proc >(const ref a: bigint, b: uint)
proc >(b: uint, const ref a: bigint)
proc <(const ref a: bigint, const ref b: bigint)
proc <(const ref a: bigint, b: int)
proc <(b: int, const ref a: bigint)
proc <(const ref a: bigint, b: uint)
proc <(b: uint, const ref a: bigint)
proc >=(const ref a: bigint, const ref b: bigint)
proc >=(const ref a: bigint, b: int)
proc >=(b: int, const ref a: bigint)
proc >=(const ref a: bigint, b: uint)
proc >=(b: uint, const ref a: bigint)
proc <=(const ref a: bigint, const ref b: bigint)
proc <=(const ref a: bigint, b: int)
proc <=(b: int, const ref a: bigint)
proc <=(const ref a: bigint, b: uint)
proc <=(b: uint, const ref a: bigint)
proc +=(ref a: bigint, const ref b: bigint)
proc +=(ref a: bigint, b: int)
proc +=(ref a: bigint, b: uint)
proc -=(ref a: bigint, const ref b: bigint)
proc -=(ref a: bigint, b: int)
proc -=(ref a: bigint, b: uint)
proc *=(ref a: bigint, const ref b: bigint)
proc *=(ref a: bigint, b: int)
proc *=(ref a: bigint, b: uint)
proc /=(ref a: bigint, const ref b: bigint)
proc /=(ref a: bigint, b: integral)
proc **=(ref base: bigint, const ref exp: bigint)
proc **=(ref base: bigint, exp: int)
proc **=(ref base: bigint, exp: uint)
proc %=(ref a: bigint, const ref b: bigint)
proc %=(ref a: bigint, b: int)
proc %=(ref a: bigint, b: uint)
proc &=(ref a: bigint, const ref b: bigint)
proc |=(ref a: bigint, const ref b: bigint)
proc ^=(ref a: bigint, const ref b: bigint)
proc <<=(ref a: bigint, b: int)
proc <<=(ref a: bigint, b: uint)
proc >>=(ref a: bigint, b: int)
proc >>=(ref a: bigint, b: uint)
proc <=>(ref a: bigint, ref b: bigint)
proc jacobi(const ref a: bigint, const ref b: bigint): int
proc legendre(const ref a: bigint, const ref p: bigint): int
proc kronecker(const ref a: bigint, const ref b: bigint): int
proc kronecker(const ref a: bigint, b: int): int
proc kronecker(a: int, const ref b: bigint): int
proc kronecker(const ref a: bigint, b: uint): int
proc kronecker(a: uint, const ref b: bigint): int
proc bigint.divexact(const ref n: bigint, const ref d: bigint)
proc bigint.divexact(const ref n: bigint, d: integral)
proc bigint.divisible_p(const ref d: bigint): int
proc bigint.divisible_p(d: int): int
proc bigint.divisible_p(d: uint): int
proc bigint.divisible_2exp_p(b: integral): int
proc bigint.congruent_p(const ref c: bigint, const ref d: bigint): int
proc bigint.congruent_p(c: integral, d: integral): int
proc bigint.congruent_2exp_p(const ref c: bigint, b: integral): int
proc bigint.powm(const ref base: bigint, const ref exp: bigint, const ref mod: bigint)
proc bigint.powm(const ref base: bigint, exp: int, const ref mod: bigint)
proc bigint.powm(const ref base: bigint, exp: uint, const ref mod: bigint)
proc bigint.pow(const ref base: bigint, exp: int)
proc bigint.pow(const ref base: bigint, exp: uint)
proc bigint.pow(base: int, exp: int)
proc bigint.pow(base: uint, exp: uint)
proc bigint.root(const ref a: bigint, n: uint): int
proc bigint.rootrem(ref rem: bigint, const ref u: bigint, n: uint)
proc bigint.sqrt(const ref a: bigint)
proc bigint.sqrtrem(ref rem: bigint, const ref a: bigint)
proc bigint.perfect_power_p(): int
proc bigint.perfect_square_p(): int
proc bigint.probab_prime_p(reps: int): int
proc bigint.nextprime(const ref a: bigint)
proc bigint.gcd(const ref a: bigint, const ref b: bigint)
proc bigint.gcd(const ref a: bigint, b: int)
proc bigint.gcd(const ref a: bigint, b: uint)
proc bigint.gcdext(ref s: bigint, ref t: bigint, const ref a: bigint, const ref b: bigint)
proc bigint.lcm(const ref a: bigint, const ref b: bigint)
proc bigint.lcm(const ref a: bigint, b: int)
proc bigint.lcm(const ref a: bigint, b: uint)
proc bigint.invert(const ref a: bigint, const ref b: bigint): int
proc bigint.remove(const ref a: bigint, const ref f: bigint): uint
proc bigint.fac(a: integral)
proc bigint.bin(const ref n: bigint, k: integral)
proc bigint.bin(n: uint, k: integral)
proc bigint.fib(n: integral)
proc bigint.fib2(ref fnsub1: bigint, n: integral)
proc bigint.lucnum(n: integral)
proc bigint.lucnum2(ref fnsub1: bigint, n: integral)
proc bigint.popcount(): uint
proc bigint.hamdist(const ref b: bigint): uint
proc bigint.scan0(starting_bit: integral): uint
proc bigint.scan1(starting_bit: integral): uint
proc bigint.setbit(bit_index: integral)
proc bigint.clrbit(bit_index: integral)
proc bigint.combit(bit_index: integral)
proc bigint.tstbit(bit_index: integral): int
proc bigint.fits_ulong_p(): int
proc bigint.fits_slong_p(): int
proc bigint.fits_uint_p(): int
proc bigint.fits_sint_p(): int
proc bigint.fits_ushort_p(): int
proc bigint.fits_sshort_p(): int
proc bigint.even_p(): int
proc bigint.odd_p(): int
proc bigint.add(const ref a: bigint, const ref b: bigint)
proc bigint.add(const ref a: bigint, b: int)
proc bigint.add(const ref a: bigint, b: uint)
proc bigint.sub(const ref a: bigint, const ref b: bigint)
proc bigint.sub(const ref a: bigint, b: int)
proc bigint.sub(const ref a: bigint, b: uint)
proc bigint.sub(a: int, const ref b: bigint)
proc bigint.sub(a: uint, const ref b: bigint)
proc bigint.mul(const ref a: bigint, const ref b: bigint)
proc bigint.mul(const ref a: bigint, b: int)
proc bigint.mul(const ref a: bigint, b: uint)
proc bigint.addmul(const ref a: bigint, const ref b: bigint)
proc bigint.addmul(const ref a: bigint, b: int)
proc bigint.addmul(const ref a: bigint, b: uint)
proc bigint.submul(const ref a: bigint, const ref b: bigint)
proc bigint.submul(const ref a: bigint, b: int)
proc bigint.submul(const ref a: bigint, b: uint)
proc bigint.mul_2exp(const ref a: bigint, b: integral)
proc bigint.neg(const ref a: bigint)
proc bigint.abs(const ref a: bigint)
proc bigint.div_q(const ref n: bigint, const ref d: bigint, param rounding = Round.ZERO)
proc bigint.div_q(const ref n: bigint, d: integral, param rounding = Round.ZERO)
proc bigint.div_r(const ref n: bigint, const ref d: bigint, param rounding = Round.ZERO)
proc bigint.div_r(const ref n: bigint, d: integral, param rounding = Round.ZERO)
proc bigint.div_qr(ref r: bigint, const ref n: bigint, const ref d: bigint, param rounding = Round.ZERO)
proc bigint.div_qr(ref r: bigint, const ref n: bigint, d: integral, param rounding = Round.ZERO)
proc bigint.div_q_2exp(const ref n: bigint, b: integral, param rounding = Round.ZERO)
proc bigint.div_r_2exp(const ref n: bigint, b: integral, param rounding = Round.ZERO)
proc bigint.mod(const ref a: bigint, const ref b: bigint)
proc bigint.mod(const ref a: bigint, b: integral): uint
proc bigint.cmp(const ref b: bigint): int
proc bigint.cmp(b: int): int
proc bigint.cmp(b: uint): int
proc bigint.cmp(b: real): int
proc bigint.cmpabs(const ref b: bigint): int
proc bigint.cmpabs(b: uint): int
proc bigint.cmpabs(b: real): int
proc bigint.sgn(): int
proc bigint.and(const ref a: bigint, const ref b: bigint)
proc bigint.ior(const ref a: bigint, const ref b: bigint)
proc bigint.xor(const ref a: bigint, const ref b: bigint)
proc bigint.com(const ref a: bigint)
proc bigint.set(const ref a: bigint)
proc bigint.set(num: int)
proc bigint.set(num: uint)
proc bigint.set(num: real)
proc bigint.set(str: string, base: int = 0)
proc bigint.swap(ref a: bigint)