BigInteger¶

Usage

use BigInteger;

or

import 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

support for multi-locale programs

the convenience of arithmetic operator overloads

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

Casting and declarations can be used to create bigint records as well:

use BigInteger;

var   a = 234958444: bigint;
const b = "4847382292989382987395534934347": bigint;
var   c: bigint;

Warning

Creating a bigint from an integer literal that is larger than max(uint(64)) would cause integer overflow before the bigint is created, and so results in a compile-time error. Strings should be used instead of integer literals for cases like this:

// These would result in integer overflow and cause compile-time errors
var bad1 = 4847382292989382987395534934347: bigint;
var bad2 = new bigint(4847382292989382987395534934347);

// These give the desired result
var good1 = "4847382292989382987395534934347": bigint;
var good2 = new bigint("4847382292989382987395534934347");

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.

Casting from bigint to integral and real types is also supported. Values that are too large for the resultant type are truncated. GMP primitives are used to first cast to platform-specific C types, which are then cast to Chapel types. As a result, casting to 64-bit types on 32-bit platforms may result in additional truncation. Additionally, casting a negative bigint to a uint will result in the absolute value truncated to fit within the type.:

var a = new bigint(-1);
writeln(a:uint);        // prints "1"

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

enum Round { DOWN = -1, ZERO = 0, UP = 1 }¶: Warning

The enum Round is deprecated, please use the enum round instead

enum round { down = -1, zero = 0, up = 1 }¶

An enumeration of the different rounding strategies, for use with e.g. divQ to determine how to round the quotient when performing the computation.

round.down indicates that the quotient should be rounded down towards -infinity and any remainder should have the same sign as the denominator.
round.zero indicates that the quotient should be rounded towards zero and any remainder should have the same sign as the numerator.
round.up indicates that the quotient should be rounded up towards +infinity and any remainder should have the opposite sign as the denominator.

record bigint¶

var mpz: mpz_t¶: The underlying GMP C structure

proc init()¶

proc init(const ref num: bigint)

proc init=(const ref num: bigint)¶

proc init(num: int)

proc init(num: uint)

proc init=(num: integral)

proc init(str: string, base: int = 0)

proc init(str: string, base: int = 0, out error: syserr)

proc size(): size_t¶: Warning

bigint.size() is deprecated

proc sizeinbase(base: int): uint¶: Warning

bigint.sizeinbase() is deprecated, use bigint.sizeInBase() instead

proc sizeInBase(base: int): int¶

Determine the size of this measured in number of digits in the given base. The sign of this is ignored, only the absolute value is used.

Arguments: base : int – The base in which to compute the number of digits used to represent this. Can be between 2 and 62.
Returns: The size of this measured in number of digits in the given base. Will either be exact or 1 too big. If base is a power of 2, will always be exact. If this is 0, will always return 1.
Return type: int

proc numLimbs: uint¶: Warning

This method is deprecated, please use GMP.chpl_gmp_mpz_nlimbs on the mpz field instead

proc get_limbn(n: integral): uint¶: Warning

This method is deprecated, please use GMP.chpl_gmp_mpz_getlimbn on the mpz field instead

proc mpzStruct(): __mpz_struct¶

proc get_d_2exp(): (uint(32), real)¶

proc get_str(base: int = 10): string¶

proc writeThis(writer) throws¶

proc type bigint.=(ref lhs: bigint, const ref rhs: bigint)¶

proc type bigint.=(ref lhs: bigint, rhs: int)

proc type bigint.=(ref lhs: bigint, rhs: uint)

proc type bigint.+(const ref a: bigint)¶

proc type bigint.-(const ref a: bigint)¶

proc type bigint.~(const ref a: bigint)

proc type bigint.+(const ref a: bigint, const ref b: bigint)

proc type bigint.+(const ref a: bigint, b: int)

proc type bigint.+(a: int, const ref b: bigint)

proc type bigint.+(const ref a: bigint, b: uint)

proc type bigint.+(a: uint, const ref b: bigint)

proc type bigint.-(const ref a: bigint, const ref b: bigint)

proc type bigint.-(const ref a: bigint, b: int)

proc type bigint.-(a: int, const ref b: bigint)

proc type bigint.-(const ref a: bigint, b: uint)

proc type bigint.-(a: uint, const ref b: bigint)

proc type bigint.*(const ref a: bigint, const ref b: bigint)¶

proc type bigint.*(const ref a: bigint, b: int)

proc type bigint.*(a: int, const ref b: bigint)

proc type bigint.*(const ref a: bigint, b: uint)

proc type bigint.*(a: uint, const ref b: bigint)

proc type bigint./(const ref a: bigint, const ref b: bigint)¶

proc type bigint./(const ref a: bigint, b: integral)

proc type bigint.**(const ref base: bigint, const ref exp: bigint)¶

proc type bigint.**(const ref base: bigint, exp: int)

proc type bigint.**(const ref base: bigint, exp: uint)

proc type bigint.%(const ref a: bigint, const ref b: bigint)

proc type bigint.%(const ref a: bigint, b: int)

proc type bigint.%(const ref a: bigint, b: uint)

proc type bigint.<<(const ref a: bigint, b: int)¶

proc type bigint.<<(const ref a: bigint, b: uint)

proc type bigint.>>(const ref a: bigint, b: int)¶

proc type bigint.>>(const ref a: bigint, b: uint)

proc type bigint.&(const ref a: bigint, const ref b: bigint)

proc type bigint.|(const ref a: bigint, const ref b: bigint)

proc type bigint.^(const ref a: bigint, const ref b: bigint)

proc type bigint.==(const ref a: bigint, const ref b: bigint)¶

proc type bigint.==(const ref a: bigint, b: int)

proc type bigint.==(a: int, const ref b: bigint)

proc type bigint.==(const ref a: bigint, b: uint)

proc type bigint.==(a: uint, const ref b: bigint)

proc type bigint.!=(const ref a: bigint, const ref b: bigint)¶

proc type bigint.!=(const ref a: bigint, b: int)

proc type bigint.!=(a: int, const ref b: bigint)

proc type bigint.!=(const ref a: bigint, b: uint)

proc type bigint.!=(a: uint, const ref b: bigint)

proc type bigint.>(const ref a: bigint, const ref b: bigint)¶

proc type bigint.>(const ref a: bigint, b: int)

proc type bigint.>(a: int, const ref b: bigint)

proc type bigint.>(const ref a: bigint, b: uint)

proc type bigint.>(a: uint, const ref b: bigint)

proc type bigint.<(const ref a: bigint, const ref b: bigint)¶

proc type bigint.<(const ref a: bigint, b: int)

proc type bigint.<(a: int, const ref b: bigint)

proc type bigint.<(const ref a: bigint, b: uint)

proc type bigint.<(a: uint, const ref b: bigint)

proc type bigint.>=(const ref a: bigint, const ref b: bigint)¶

proc type bigint.>=(const ref a: bigint, b: int)

proc type bigint.>=(a: int, const ref b: bigint)

proc type bigint.>=(const ref a: bigint, b: uint)

proc type bigint.>=(a: uint, const ref b: bigint)

proc type bigint.<=(const ref a: bigint, const ref b: bigint)¶

proc type bigint.<=(const ref a: bigint, b: int)

proc type bigint.<=(a: int, const ref b: bigint)

proc type bigint.<=(const ref a: bigint, b: uint)

proc type bigint.<=(a: uint, const ref b: bigint)

proc type bigint.+=(ref a: bigint, const ref b: bigint)¶

proc type bigint.+=(ref a: bigint, b: int)

proc type bigint.+=(ref a: bigint, b: uint)

proc type bigint.-=(ref a: bigint, const ref b: bigint)¶

proc type bigint.-=(ref a: bigint, b: int)

proc type bigint.-=(ref a: bigint, b: uint)

proc type bigint.*=(ref a: bigint, const ref b: bigint)¶

proc type bigint.*=(ref a: bigint, b: int)

proc type bigint.*=(ref a: bigint, b: uint)

proc type bigint./=(ref a: bigint, const ref b: bigint)¶

proc type bigint./=(ref a: bigint, b: integral)

proc type bigint.**=(ref base: bigint, const ref exp: bigint)¶

proc type bigint.**=(ref base: bigint, exp: int)

proc type bigint.**=(ref base: bigint, exp: uint)

proc type bigint.%=(ref a: bigint, const ref b: bigint)

proc type bigint.%=(ref a: bigint, b: int)

proc type bigint.%=(ref a: bigint, b: uint)

proc type bigint.&=(ref a: bigint, const ref b: bigint)

proc type bigint.|=(ref a: bigint, const ref b: bigint)

proc type bigint.^=(ref a: bigint, const ref b: bigint)

proc type bigint.<<=(ref a: bigint, b: int)¶

proc type bigint.<<=(ref a: bigint, b: uint)

proc type bigint.>>=(ref a: bigint, b: int)¶

proc type bigint.>>=(ref a: bigint, b: uint)

proc type bigint.<=>(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)¶

Computes n/d and stores the result in bigint instance.

divexact is optimized to handle cases where n/d results in an integer. When n/d does not produce an integer, this method may produce incorrect results.

Arguments

n : bigint – numerator
d : bigint – denominator

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)¶: Warning

bigint.powm is deprecated, use bigint.powMod instead

proc bigint.powm(const ref base: bigint, exp: int, const ref mod: bigint): Warning

bigint.powm is deprecated, use bigint.powMod instead

proc bigint.powm(const ref base: bigint, exp: uint, const ref mod: bigint): Warning

bigint.powm is deprecated, use bigint.powMod instead

proc bigint.powMod(const ref base: bigint, const ref exp: bigint, const ref mod: bigint)¶

proc bigint.powMod(const ref base: bigint, exp: int, const ref mod: bigint)

proc bigint.powMod(const ref base: bigint, exp: uint, const ref mod: bigint)

Set this to the result of (base raised to exp) modulo mod.

Arguments

base : bigint – The value to be raised to the power of exp before performing a modulo operation on.
exp : bigint, int, or uint – The exponent to raise base to the power of prior to the modulo operation. Can be negative if the inverse (1/base) modulo mod exists.
mod : bigint – The divisor for the modulo operation.

Warning

The program behavior is undefined if exp is negative and the inverse (1/base) modulo mod does not exist.

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)

Set this to the result of base raised to exp.

Arguments

base : bigint, int or uint – The value to be raised to the power of exp.
exp : int or uint – The exponent to raise base to the power of.

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)¶: Warning

bigint.div_q using Round is deprecated, use bigint.divQ with round instead

proc bigint.div_q(const ref n: bigint, d: integral, param rounding = Round.ZERO): Warning

bigint.div_q using Round is deprecated, use bigint.divQ with round instead

proc bigint.divQ(const ref numer: bigint, const ref denom: bigint, param rounding = round.zero)¶

proc bigint.divQ(const ref numer: bigint, denom: integral, param rounding = round.zero)

Divide numer by denom, forming a quotient and storing it in this.

Arguments

numer : bigint – The numerator of the division operation to be performed
denom : bigint, integral – The denominator of the division operation to be performed
rounding : round – The rounding style to use, see round for a description of what the rounding styles entail. Defaults to zero if unspecified

Warning

If the denominator is zero, the program behavior is undefined.

proc bigint.div_r(const ref n: bigint, const ref d: bigint, param rounding = Round.ZERO)¶: Warning

bigint.div_r using Round is deprecated, use bigint.divR with round instead

proc bigint.div_r(const ref n: bigint, d: integral, param rounding = Round.ZERO): Warning

bigint.div_r using Round is deprecated, use bigint.divR with round instead

proc bigint.divR(const ref numer: bigint, const ref denom: bigint, param rounding = round.zero)¶

proc bigint.divR(const ref numer: bigint, denom: integral, param rounding = round.zero)

Divide numer by denom, forming a remainder and storing it in this. The absolute value of the remainder will always be less than the absolute value of the denominator (i.e. abs(this) < abs(denom)).

Arguments

numer : bigint – The numerator of the division operation to be performed
denom : bigint, integral – The denominator of the division operation to be performed
rounding : round – The rounding style to use, see round for a description of what the rounding styles entail. Defaults to zero if unspecified

Warning

If the denominator is zero, the program behavior is undefined.

proc bigint.div_qr(ref r: bigint, const ref n: bigint, const ref d: bigint, param rounding = Round.ZERO)¶: Warning

bigint.div_qr using Round is deprecated, use bigint.divQR with round instead

proc bigint.div_qr(ref r: bigint, const ref n: bigint, d: integral, param rounding = Round.ZERO): Warning

bigint.div_qr using Round is deprecated, use bigint.divQR with round instead

proc bigint.divQR(ref remain: bigint, const ref numer: bigint, const ref denom: bigint, param rounding = round.zero)¶

proc bigint.divQR(ref remain: bigint, const ref numer: bigint, denom: integral, param rounding = round.zero)

Divide numer by denom, forming a quotient and storing it in this, and a remainder and storing it in remain. The quotient and remainder will always satisfy numer = this*denom + remain after the operation has finished. The absolute value of the remainder will always be less than the absolute value of the denominator (i.e. abs(this) < abs(denom)).

Warning

If this is also passed as the remain argument, the program behavior is undefined.

Arguments

remain : bigint – Stores the remainder of the division
numer : bigint – The numerator of the division operation to be performed
denom : bigint, integral – The denominator of the division operation to be performed
rounding : round – The rounding style to use, see round for a description of what the rounding styles entail. Defaults to zero if unspecified

Warning

If the denominator is zero, the program behavior is undefined.

proc bigint.div_q_2exp(const ref n: bigint, b: integral, param rounding = Round.ZERO)¶: Warning

bigint.div_q_2exp using Round is deprecated, use bigint.divQ2Exp with round instead

proc bigint.divQ2Exp(const ref numer: bigint, exp: integral, param rounding = round.zero)¶

Divide numer by 2^exp, forming a quotient and storing it in this.

Arguments

numer : bigint – The numerator of the division operation to be performed
exp : integral – The exponent that 2 should be raised to before being used as the denominator of the division operation to be performed
rounding : round – The rounding style to use, see round for a description of what the rounding styles entail. Defaults to zero if unspecified

proc bigint.div_r_2exp(const ref n: bigint, b: integral, param rounding = Round.ZERO)¶: Warning

bigint.div_r_2exp using Round is deprecated, use bigint.divR2Exp with round instead

proc bigint.divR2Exp(const ref numer: bigint, exp: integral, param rounding = round.zero)¶

Divide numer by 2^exp, forming a remainder and storing it in this.

Arguments

numer : bigint – The numerator of the division operation to be performed
exp : integral – The exponent that 2 should be raised to before being used as the denominator of the division operation to be performed
rounding : round – The rounding style to use, see round for a description of what the rounding styles entail. Defaults to zero if unspecified

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)¶