BigInteger

Usage

use BigInteger;

or

import BigInteger;

Provides a ‘bigint’ type and supporting math operations.

The bigint type 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, 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);

fac(c, 00);
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;

The Chapel compiler currently introduces two short lived temporaries for the intermediate results of the binary operators.

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

var a = new bigint("9738639463465935");
var b = 939573915 * 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.

record bigint : serializable

The bigint type supports arithmetic operations on arbitrary precision integers across multiple locales.

proc init()

Initializes a bigint to an initial value of 0.

proc init(const ref x: bigint)

Initializes a bigint to the value of x.

Arguments:

x : bigint, int, uint – The value to be stored in the resulting bigint.

proc init(x: int(?))

See init

proc init(x: uint(?))

See init

proc init(x: string, base: int = 0) throws

Initialize a bigint from a string and optionally a provided base to use with the string. If the string is not a correct base base number, will throw a BadFormatError.

Arguments:

• x : string – The value to be stored in the resulting bigint.

• base : int – The base to use when creating the bigint from x. May vary from 2 to 62 or be 0. Defaults to 0, which causes the base to be read from the start of the x itself (0x and 0X will give hexadecimal, 0b and 0B will give binary, 0 will give octal, and everything else will be interpreted as decimal).

Throws:

BadFormatError – Thrown when x is not a correctly formatted number in base base.

proc init=(const ref x: bigint)

Copy initializes a bigint to the value of x.

Arguments:

x : bigint, integral – The value to be stored in the resulting bigint.

proc init=(x: integral)

See init=

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

See also

GMP.mpz_sizeinbase and mpz_sizeinbase.

proc getImpl() : __mpz_struct

Warning

getImpl is provided as a convenience but its result may change in the future

Return the underlying implementation of bigint. Currently, the type returned is __mpz_struct.

proc getD2Exp() : (real, uint(32))

Convert this to a tuple containing a real (truncated if necessary, by rounding towards zero) and the exponent. The returned tuple fulfills the condition d * 2^exp == this where d is the first value in the tuple and exp is the second.

Returns:

a tuple representing the number in multiple parts, (d, exp), such that their combination d * 2^exp is equal to this.

d in this case will be in the range 0.5 <= abs(d) < 1, unless this is 0, in which case d == 0.0 and exp == 0.

Return type:

(real, uint(32))

See also

GMP.mpz_get_d_2exp and mpz_get_d_2exp.

proc serialize(writer, ref serializer) throws

Writes this number to a fileWriter

proc ref deserialize(reader, ref deserializer) throws

Read this number from a fileReader

enum roundingMode { down = -1, zero = 0, up = 1 }

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

enum constant down = -1

Indicates that the quotient should be rounded down towards -infinity and any remainder should have the same sign as the denominator.

enum constant zero = 0

Indicates that the quotient should be rounded towards zero and any remainder should have the same sign as the numerator.

enum constant up = 1

Indicates that the quotient should be rounded up towards +infinity and any remainder should have the opposite sign as the denominator.

operator :(x: integral, type t: bigint) : bigint

Constructs a new bigint from x, see bigint.init.

operator :(x: string, type t: bigint) : bigint throws

Constructs a new bigint from x, see the bigint.init overload which takes a string.

operator :(x: bool, type t: bigint) : bigint throws

Constructs a new bigint from x, see bigint.init.

operator :(x: real, type t: bigint) : bigint

Constructs a new bigint from x

operator :(const ref x: bigint, type t: numeric)  where isIntType(t)

Convert x to a signed integer. If x is larger than t, the value returned is the least significant part of x with the same sign as x.

See also

GMP.mpz_get_si and mpz_get_si.

operator :(const ref x: bigint, type t: numeric)  where isUintType(t)

Convert x to an unsigned integer. If x is larger than t, the value returned is the least significant part of x ignoring the sign of x.

See also

GMP.mpz_get_ui and mpz_get_ui.

operator :(const ref x: bigint, type t: numeric)  where isRealType(t)

Convert x to a real with type t (truncated if necessary, by rounding towards zero).

Warning

If the resulting exponent from the conversion is too big, the result is system dependent. If supported, an infinity may be returned. A hardware overflow trap may also occur.

See also

GMP.mpz_get_d and mpz_get_d.

operator :(const ref x: bigint, type t: string)

Convert x to a string representation.

operator bigint.=(ref lhs: bigint, const ref rhs: bigint)

See bigint.set

operator bigint.=(ref lhs: bigint, rhs: int(?))

See bigint.set

operator bigint.=(ref lhs: bigint, rhs: uint(?))

See bigint.set

operator bigint.+(const ref a: bigint) : bigint

See bigint.init

operator bigint.-(const ref a: bigint) : bigint

See neg

operator bigint.~(const ref a: bigint) : bigint

See com

operator bigint.+(const ref a: bigint, const ref b: bigint) : bigint

See add

operator bigint.+(const ref a: bigint, b: int(?)) : bigint

See add

operator bigint.+(const ref a: bigint, b: uint(?)) : bigint

See add

operator bigint.+(a: int(?), const ref b: bigint) : bigint

See add

operator bigint.+(a: uint(?), const ref b: bigint) : bigint

See add

operator bigint.-(const ref a: bigint, const ref b: bigint) : bigint

See sub

operator bigint.-(const ref a: bigint, b: int(?)) : bigint

See sub

operator bigint.-(const ref a: bigint, b: uint(?)) : bigint

See sub

operator bigint.-(a: int(?), const ref b: bigint) : bigint

See sub

operator bigint.-(a: uint(?), const ref b: bigint) : bigint

See sub

operator bigint.*(const ref a: bigint, const ref b: bigint) : bigint

See mul

operator bigint.*(const ref a: bigint, b: int(?)) : bigint

See mul

operator bigint.*(const ref a: bigint, b: uint(?)) : bigint

See mul

operator bigint.*(a: int(?), const ref b: bigint) : bigint

See mul

operator bigint.*(a: uint(?), const ref b: bigint) : bigint

See mul

operator bigint./(const ref a: bigint, const ref b: bigint) : bigint

See div

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

See div

operator bigint.**(const ref base: bigint, const ref exp: bigint) : bigint

See pow

operator bigint.**(const ref base: bigint, exp: int(?)) : bigint

See pow

operator bigint.**(const ref base: bigint, exp: uint(?)) : bigint

See pow

operator bigint.%(const ref a: bigint, const ref b: bigint) : bigint

Computes the mod operator on the two arguments, defined as a % b = a - b * trunc(a / b).

The result is always >= 0 if a > 0. It is an error if b == 0.

See rem

operator bigint.%(const ref a: bigint, b: int(?)) : bigint

See bigint.%

operator bigint.%(const ref a: bigint, b: uint(?)) : bigint

See bigint.%

operator bigint.<<(const ref a: bigint, b: int(?)) : bigint

See shiftLeft

operator bigint.<<(const ref a: bigint, b: uint(?)) : bigint

See shiftLeft

operator bigint.>>(const ref a: bigint, b: int(?)) : bigint

See shiftRight

operator bigint.>>(const ref a: bigint, b: uint(?)) : bigint

See shiftRight

operator bigint.&(const ref a: bigint, const ref b: bigint) : bigint

See and

operator bigint.|(const ref a: bigint, const ref b: bigint) : bigint

See or

operator bigint.^(const ref a: bigint, const ref b: bigint) : bigint

See xor

operator bigint.==(const ref a: bigint, const ref b: bigint) : bool

See bigint.cmp

operator bigint.==(const ref a: bigint, b: int(?)) : bool

See bigint.cmp

operator bigint.==(const ref a: bigint, b: uint(?)) : bool

See bigint.cmp

operator bigint.==(a: int(?), const ref b: bigint) : bool

See bigint.cmp

operator bigint.==(a: uint(?), const ref b: bigint) : bool

See bigint.cmp

operator bigint.!=(const ref a: bigint, const ref b: bigint) : bool

See bigint.cmp

operator bigint.!=(const ref a: bigint, b: int(?)) : bool

See bigint.cmp

operator bigint.!=(const ref a: bigint, b: uint(?)) : bool

See bigint.cmp

operator bigint.!=(a: int(?), const ref b: bigint) : bool

See bigint.cmp

operator bigint.!=(a: uint(?), const ref b: bigint) : bool

See bigint.cmp

operator bigint.>(const ref a: bigint, const ref b: bigint) : bool

See bigint.cmp

operator bigint.>(const ref a: bigint, b: int(?)) : bool

See bigint.cmp

operator bigint.>(const ref a: bigint, b: uint(?)) : bool

See bigint.cmp

operator bigint.>(a: int(?), const ref b: bigint) : bool

See bigint.cmp

operator bigint.>(a: uint(?), const ref b: bigint) : bool

See bigint.cmp

operator bigint.<(const ref a: bigint, const ref b: bigint) : bool

See bigint.cmp

operator bigint.<(const ref a: bigint, b: int(?)) : bool

See bigint.cmp

operator bigint.<(const ref a: bigint, b: uint(?)) : bool

See bigint.cmp

operator bigint.<(a: int(?), const ref b: bigint) : bool

See bigint.cmp

operator bigint.<(a: uint(?), const ref b: bigint) : bool

See bigint.cmp

operator bigint.>=(const ref a: bigint, const ref b: bigint) : bool

See bigint.cmp

operator bigint.>=(const ref a: bigint, b: int(?)) : bool

See bigint.cmp

operator bigint.>=(const ref a: bigint, b: uint(?)) : bool

See bigint.cmp

operator bigint.>=(a: int(?), const ref b: bigint) : bool

See bigint.cmp

operator bigint.>=(a: uint(?), const ref b: bigint) : bool

See bigint.cmp

operator bigint.<=(const ref a: bigint, const ref b: bigint) : bool

See bigint.cmp

operator bigint.<=(const ref a: bigint, b: int(?)) : bool

See bigint.cmp

operator bigint.<=(const ref a: bigint, b: uint(?)) : bool

See bigint.cmp

operator bigint.<=(a: int(?), const ref b: bigint) : bool

See bigint.cmp

operator bigint.<=(a: uint(?), const ref b: bigint) : bool

See bigint.cmp

operator bigint.+=(ref a: bigint, const ref b: bigint)

See add

operator bigint.+=(ref a: bigint, b: int(?))

See add

operator bigint.+=(ref a: bigint, b: uint(?))

See add

operator bigint.-=(ref a: bigint, const ref b: bigint)

See sub

operator bigint.-=(ref a: bigint, b: int(?))

See sub

operator bigint.-=(ref a: bigint, b: uint(?))

See sub

operator bigint.*=(ref a: bigint, const ref b: bigint)

See mul

operator bigint.*=(ref a: bigint, b: int(?))

See mul

operator bigint.*=(ref a: bigint, b: uint(?))

See mul

operator bigint./=(ref a: bigint, const ref b: bigint)

See div

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

See div

operator bigint.**=(ref base: bigint, const ref exp: bigint)

See pow

operator bigint.**=(ref base: bigint, exp: int(?))

See pow

operator bigint.**=(ref base: bigint, exp: uint(?))

See pow

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

See bigint.%

operator bigint.%=(ref a: bigint, b: int(?))

See bigint.%

operator bigint.%=(ref a: bigint, b: uint(?))

See bigint.%

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

See and

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

See or

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

See xor

operator bigint.<<=(ref a: bigint, b: int(?))

See shiftLeft

operator bigint.<<=(ref a: bigint, b: uint(?))

See shiftLeft

operator bigint.>>=(ref a: bigint, b: int(?))

See shiftRight

operator bigint.>>=(ref a: bigint, b: uint(?))

See shiftRight

operator bigint.<=>(ref a: bigint, ref b: bigint)

See bigint.swap

proc jacobi(const ref a: bigint, const ref b: bigint) : int

Warning

jacobi is unstable and may change in the future

Returns the Jacobi symbol a/b, which is defined only when b is odd.

Return type:

int

See also

GMP.mpz_jacobi and mpz_jacobi.

proc legendre(const ref a: bigint, const ref p: bigint) : int

Warning

legendre is unstable and may change in the future

Returns the Legendre symbol a/p, which is defined only when p is an odd positive prime number.

Return type:

int

See also

GMP.mpz_legendre and mpz_legendre.

proc kronecker(const ref a: bigint, const ref b: bigint) : int

Warning

kronecker is unstable and may change in the future

Returns the Jacobi symbol a/b with the Kronecker extension. When b is odd this is the same as the Jacobi symbol.

Return type:

int

See also

GMP.mpz_kronecker and mpz_kronecker.

proc kronecker(const ref a: bigint, b: int(?)) : int

Warning

kronecker is unstable and may change in the future

See kronecker

proc kronecker(a: int(?), const ref b: bigint) : int

Warning

kronecker is unstable and may change in the future

See kronecker

proc kronecker(const ref a: bigint, b: uint(?)) : int

Warning

kronecker is unstable and may change in the future

See kronecker

proc kronecker(a: uint(?), const ref b: bigint) : int

Warning

kronecker is unstable and may change in the future

See kronecker

proc divExact(ref result: bigint, const ref numer: bigint, const ref denom: bigint)

Computes numer/denom and stores the result in result, which is a bigint instance.

Warning

divExact is optimized to handle cases where numer/denom results in an integer. When numer/denom does not produce an integer, this method may produce incorrect results.

Arguments:

• result : bigint – Where the result is stored

• numer : bigint – numerator

• denom : bigint or integral – denominator

See also

GMP.mpz_divexact and mpz_divexact.

proc divExact(ref result: bigint, const ref numer: bigint, denom: integral)

See divExact

proc bigint.isDivisible(const ref div: bigint) : bool

Return true if this is exactly divisible by div. this is divisible by div if there exists an integer q satisfying this = q*div. Unlike the other division functions, 0 is an acceptable value for div and only 0 is considered divisible by 0.

Arguments:

div : bigint, int or uint – number to check if this is divisible by

Returns:

true if this is exactly divisible by div, false otherwise

Return type:

bool

See also

GMP.mpz_divisible_p and mpz_divisible_p.

proc bigint.isDivisible(div: int(?)) : bool

See isDivisible

proc bigint.isDivisible(div: uint(?)) : bool

See isDivisible

proc bigint.isDivisibleBy2Pow(exp: integral) : bool

Return true if this is exactly divisible by 2^exp. this is divisible by 2^exp if there exists an integer q satisfying this = q*2^exp.

Arguments:

exp : integral – power of 2 to check if this is divisible by

Returns:

true if this is exactly divisible by 2^exp, false otherwise

Return type:

bool

See also

GMP.mpz_divisible_2exp_p and mpz_divisible_2exp_p.

proc bigint.isCongruent(const ref con: bigint, const ref mod: bigint) : bool

Return true if this is congruent to con % mod. this is congruent to con % mod if there exists an integer q satisfying this = con + q*mod. Unlike the other division functions, 0 is an acceptable value for mod. As a result this and con are considered congruent modulo 0 only when exactly equal.

Arguments:

• con : bigint or integral – number to determine if this is congruent to, modulo mod

• mod : bigint or integral – divisor of con when determining if con is congruent to this

Returns:

true if this is congruent to con modulo mod, false otherwise

Return type:

bool

See also

GMP.mpz_congruent_p and mpz_congruent_p.

proc bigint.isCongruent(con: integral, mod: integral) : bool

See isCongruent

proc bigint.isCongruentBy2Pow(const ref con: bigint, modExp: integral) : bool

Return true if this is congruent to con % 2^modExp. this is congruent to con % 2^modExp if there exists an integer q satisfying this = con + q*2^modExp.

Arguments:

• con : bigint or integral – number to determine if this is congruent to, modulo 2^modExp.

• modExp : integral – power of 2 to use as the divisor of con when determining if con is congruent to this.

Returns:

true if this is congruent to con modulo 2^modExp, false otherwise.

Return type:

bool

See also

GMP.mpz_congruent_2exp_p and mpz_congruent_2exp_p.

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

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

Arguments:

• result : bigint – Where the result is stored

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

See also

GMP.mpz_powm and mpz_powm.

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

See powMod

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

See powMod

proc pow(ref result: bigint, const ref base: bigint, exp: int(?))

Set result to the result of base raised to exp.

Arguments:

• result : bigint – Where the result is stored

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

See also

GMP.mpz_pow_ui and mpz_pow_ui.

proc pow(ref result: bigint, const ref base: bigint, exp: uint(?))

See pow

proc pow(ref result: bigint, base: int(?), exp: int(?))

See pow

proc pow(ref result: bigint, base: uint(?), exp: uint(?))

See pow

proc root(ref result: bigint, const ref x: bigint, n: uint) : int

Sets result to the truncated integer n th root of x.

Arguments:

• result : bigint – Where the result is stored

• x : bigint – Number to take the root of

• n : uint – Which root to take

See also

GMP.mpz_root and mpz_root.

proc rootRem(ref result: bigint, ref remain: bigint, const ref x: bigint, n: uint)

Sets result to the truncated integer n th root of x. Stores the remainder in remain.

Arguments:

• result : bigint – Where the result is stored

• remain : bigint – Where the remainder is stored

• x : bigint – Number to take the root of

• n : uint – Which root to take

See also

GMP.mpz_rootrem and mpz_rootrem.

proc sqrt(ref result: bigint, const ref x: bigint)

Sets result to the truncated integer square root of x.

Arguments:

• result : bigint – Where the result is stored

• x : bigint – Number to take the square root of

See also

GMP.mpz_sqrt and mpz_sqrt.

proc sqrtRem(ref result: bigint, ref remain: bigint, const ref x: bigint)

Sets result to the truncated integer square root of x. Stores the remainder in remain.

Warning

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

Arguments:

• result : bigint – Where the result is stored

• remain : bigint – Where the remainder is stored

• x : bigint – Number to take the square root of

See also

GMP.mpz_sqrtrem and mpz_sqrtrem.

proc bigint.isPerfectPower() : bool

Return true if this is a perfect power, i.e., if there exist integers a and b with b > 1, such that this = a^b.

Under this definition both 0 and 1 are considered to be perfect powers. Negative values can only be odd perfect powers.

Returns:

true if this is a perfect power, false otherwise.

Return type:

bool

See also

GMP.mpz_perfect_power_p and mpz_perfect_power_p.

proc bigint.isPerfectSquare() : bool

Return true if this is a perfect square, i.e., if the square root of this is an integer.

Under this definition both 0 and 1 are considered to be perfect squares.

Returns:

true if this is a perfect square, false otherwise.

Return type:

bool

See also

GMP.mpz_perfect_square_p and mpz_perfect_square_p.

enum primality { notPrime = 0, maybePrime, isPrime }

An enumeration of the different possibilities of a number being prime, for use with e.g. probablyPrime to determine if a number is prime or not.

enum constant notPrime = 0

Indicates that the number is not a prime.

enum constant maybePrime

Indicates that the number may or may not be a prime.

enum constant isPrime

Indicates that the number is a prime.

proc bigint.probablyPrime(reps: int) : primality

Warning

bigint.probablyPrime is unstable and may change in the future

Determine whether this is prime. Returns one of the primality constants - isPrime, maybePrime, or notPrime.

Performs some trial divisions, a Baillie-PSW probable prime test, and 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^(-reps). Reasonable values of reps are between 15 and 50.

Arguments:

reps : int – number of attempts before returning maybePrime if a definitive answer can’t be found before then.

Returns:

isPrime, maybePrime, or notPrime.

Return type:

primality

See also

GMP.mpz_probab_prime_p and mpz_probab_prime_p.

proc nextPrime(ref result: bigint, const ref x: bigint)

Warning

nextPrime is unstable and may change in the future

Set result to the next prime number greater than x.

Note

This is a probabilistic function and in an unlikely case may set result to a composite number.

Arguments:

• result : bigint – return value that will contain the next prime number

• x : bigint – the result will be a prime number bigger than this value

See also

GMP.mpz_nextprime and mpz_nextprime.

proc gcd(ref result: bigint, const ref a: bigint, const ref b: bigint)

Warning

gcd is unstable and may change in the future

Set result to the greatest common divisor of a and b

Arguments:

• result : bigint – Where the result is stored

• a : bigint – One of the numbers to compute the greatest common divisor of

• b : bigint, int, uint – One of the numbers to compute the greatest common divisor of

See also

GMP.mpz_gcd and mpz_gcd.

proc gcd(ref result: bigint, const ref a: bigint, b: int(?))

Warning

gcd is unstable and may change in the future

See gcd

proc gcd(ref result: bigint, const ref a: bigint, b: uint(?))

Warning

gcd is unstable and may change in the future

See gcd

proc gcd(ref result: bigint, const ref a: bigint, const ref b: bigint, ref s: bigint, ref t: bigint) : void

Warning

gcd is unstable and may change in the future

Set result to the greatest common divisor of a and b, and set s and t to coefficients such that a*s + b*t == result.

Note

The result stored in result is always positive, even if one or both of a and b are negative (or zero if both are zero).

Arguments:

• result : bigint – Where the result is stored

• a : bigint – One of the numbers to compute the greatest common divisor of

• b : bigint – One of the numbers to compute the greatest common divisor of

• s : bigint – The returned coefficient that can be multiplied by a.

• t : bigint – The returned coefficient that can be multiplied by b.

See also

GMP.mpz_gcdext and mpz_gcdext.

proc lcm(ref result: bigint, const ref a: bigint, const ref b: bigint)

Warning

lcm is unstable and may change in the future

Set result to the least common multiple of a and b

Arguments:

• result : bigint – Where the result is stored

• a : bigint – One of the numbers to compute the least common multiple of

• b : bigint, int, uint – One of the numbers to compute the least common multiple of

See also

GMP.mpz_lcm and mpz_lcm.

proc lcm(ref result: bigint, const ref a: bigint, b: int(?))

Warning

lcm is unstable and may change in the future

See lcm

proc lcm(ref result: bigint, const ref a: bigint, b: uint(?))

Warning

lcm is unstable and may change in the future

See lcm

class InversionError : Error

An InversionError is thrown if a invert() is attempted with invalid arguments that result in a non-existent inverse. Specifically, if the arguments cause a divide by zero, this error notifies the caller that the internal value of the bigint was left in an undefined state.

proc init()

Create an InversionError with the default error message: Inverse does not exist

proc invert(ref result: bigint, const ref x: bigint, const ref y: bigint) throws

Set the value of result to the inverse of x modulo y

Arguments:

• result : bigint – Where the result is stored

• x : bigint – The dividend of the modulo operation

• y : bigint – The divisor of the modulo operation

Throws:

InversionError – Thrown when the inverse does not exist and the value of result will be left undefined.

See also

GMP.mpz_invert and mpz_invert.

proc removeFactor(ref result: bigint, const ref x: bigint, const ref fac: bigint) : uint

Remove all occurrences of the factor fac from x and store the result in result. Return the number of occurrences removed.

Arguments:

• result : bigint – Where the result is stored

• x : bigint – The value to remove all occurrences of fac from

• fac : bigint – The factor to remove from x.

Returns:

The number of occurrences of fac found in x.

Return type:

uint

See also

GMP.mpz_remove and

mpz_remove.

proc fac(ref result: bigint, a: integral)

Warning

fac is unstable and may change in the future

Set result to the factorial of a.

Arguments:

• result : bigint – Where the result is stored

• a : integral – Number to take the factorial of

See also

GMP.mpz_fac_ui and mpz_fac_ui.

proc bin(ref result: bigint, const ref n: bigint, k: integral)

Warning

bin is unstable and may change in the future

Set result to the binomial coefficient of n over k.

Arguments:

• result : bigint – Where the result is stored

• n : bigint or uint – Top number of the binomial

• k : integral – Bottom number of the binomial

See also

GMP.mpz_bin_ui and mpz_bin_ui.

proc bin(ref result: bigint, n: uint, k: integral)

Warning

bin is unstable and may change in the future

See bin

proc fib(ref result: bigint, n: integral)

Warning

fib is unstable and may change in the future

Set result to the n th Fibonacci number.

Arguments:

• result : bigint – return value that will contain the Fibonacci number

• n : integral – which Fibonacci number to compute for result.

See also

GMP.mpz_fib_ui and mpz_fib_ui.

proc fib2(ref result: bigint, ref fnsub1: bigint, n: integral)

Warning

fib2 is unstable and may change in the future

Set result to the n th Fibonacci number and set fnsub1 to the n-1 th Fibonacci number.

Arguments:

• result : bigint – return value that will contain the Fibonacci number

• fnsub1 : bigint – return value that will contain the previous Fibonacci number

• n : integral – which Fibonacci number to compute for result. fnsub1 is set to the n-1 Fibonacci number.

See also

GMP.mpz_fib2_ui and mpz_fib2_ui.

proc lucNum(ref result: bigint, n: integral)

Warning

lucNum is unstable and may change in the future

Set result to the n th Lucas number.

Arguments:

• result : bigint – return value that will contain the Lucas number

• n : integral – which Lucas number to compute

See also

GMP.mpz_lucnum_ui and mpz_lucnum_ui.

proc lucNum2(ref result: bigint, ref fnsub1: bigint, n: integral)

Warning

lucNum2 is unstable and may change in the future

Set result to the n th Lucas number and set fnsub1 to the n-1 th Lucas number.

Arguments:

• result : bigint – return value that will contain the Lucas number

• fnsub1 : bigint – return value that will contain the previous Lucas number

• n : integral – which Lucas number to compute for result. fnsub1 is set to the n-1 Lucas number.

See also

GMP.mpz_lucnum2_ui and mpz_lucnum2_ui.

proc bigint.popCount() : uint

Returns the number of 1 bits in this. If this is negative, the number of 1 bits is infinite and the return value is the largest possible mp_bitcnt_t.

Returns:

The number of 1 bits in this

Return type:

uint

See also

GMP.mpz_popcount and mpz_popcount.

proc bigint.hammingDistance(const ref x: bigint) : uint

Warning

bigint.hammingDistance is unstable and may change in the future

Returns the number of bit positions that differ between this and x. If this and x have different signs, the number of bits that differ is infinite and the return value is the largest possible mp_bitcnt_t.

Arguments:

x : bigint – value to compare this against

Returns:

The number of bits that differ

Return type:

uint

See also

GMP.mpz_hamdist and mpz_hamdist.

proc bigint.findNext0(startBitIdx: integral) : uint

Returns the index of the first 0 bit found, starting from startBitIdx and searching towards the more significant bits.

If the bit at startBitIdx is 1, will return startBitIdx.

Arguments:

startBitIdx : integral – The index of the first bit to start searching for a 0

Returns:

The index of the first 0 bit after startBitIdx, inclusive

Return type:

uint

See also

GMP.mpz_scan0 and mpz_scan0.

proc bigint.findNext1(startBitIdx: integral) : uint

Returns the index of the first 1 bit found, starting from startBitIdx and searching towards the more significant bits.

If the bit at startBitIdx is 1, will return startBitIdx.

Arguments:

startBitIdx : integral – The index of the first bit to start searching for a 1

Returns:

The index of the first 1 bit after startBitIdx, inclusive

Return type:

uint

See also

GMP.mpz_scan1 and mpz_scan1.

proc ref bigint.setBit(idx: integral)

Set the bit at idx of this.

Arguments:

idx : integral – The index of the bit to be set

See also

GMP.mpz_setbit and mpz_setbit.

proc ref bigint.clearBit(idx: integral)

Clear the bit at idx of this.

Arguments:

idx : integral – The index of the bit to be cleared

See also

GMP.mpz_clrbit and mpz_clrbit.

proc ref bigint.toggleBit(idx: integral)

Toggle the bit at idx of this. If the bit was 1, set it to 0. If the bit was 0, set it to 1.

Arguments:

idx : integral – The index of the bit to be toggled

See also

GMP.mpz_combit and mpz_combit.

proc bigint.getBit(idx: integral) : int

Get the bit at idx of this.

Arguments:

idx : integral – The index of the bit to be returned

Returns:

The bit at index idx

Return type:

int

See also

GMP.mpz_tstbit and mpz_tstbit.

proc bigint.fitsInto(type t: integral) : bool

Test whether a bigint will fit into one of the standard integer types.

Arguments:

t : integral – The Integral type to check against.

Return type:

bool

See also

mpz_fits_*.

proc bigint.isEven() : bool

Returns true if this is an even number, false otherwise.

Return type:

bool

See also

GMP.mpz_even_p and mpz_even_p.

proc bigint.isOdd() : bool

Returns true if this is an odd number, false otherwise.

Return type:

bool

See also

GMP.mpz_odd_p and mpz_odd_p.

proc add(ref result: bigint, const ref x: bigint, const ref y: bigint)

Sets result to the sum of x and y.

Arguments:

• result : bigint – Where the result is stored

• x : bigint – The first operand of the sum

• y : bigint, uint, int – The second operand of the sum

See also

GMP.mpz_add, GMP.mpz_add_ui, and mpz_add.

proc add(ref result: bigint, const ref x: bigint, y: int(?))

See add

proc add(ref result: bigint, const ref x: bigint, y: uint(?))

See add

proc sub(ref result: bigint, const ref x: bigint, const ref y: bigint)

Sets result to the difference of x and y.

Arguments:

• result : bigint – Where the result is stored

• x : bigint, uint, int – The first operand of the difference

• y : bigint, uint, int – The second operand of the difference

See also

GMP.mpz_sub, GMP.mpz_sub_ui, and mpz_sub.

proc sub(ref result: bigint, const ref x: bigint, y: int(?))

See sub

proc sub(ref result: bigint, const ref x: bigint, y: uint(?))

See sub

proc sub(ref result: bigint, x: int(?), const ref y: bigint)

See sub

proc sub(ref result: bigint, x: uint(?), const ref y: bigint)

See sub

proc mul(ref result: bigint, const ref x: bigint, const ref y: bigint)

Sets result to the product of x and y.

Arguments:

• result : bigint – Where the result is stored

• x : bigint – The first operand of the product

• y : bigint, uint, int – The second operand of the product

See also

GMP.mpz_mul, GMP.mpz_mul_ui, GMP.mpz_mul_si, and mpz_mul.

proc mul(ref result: bigint, const ref x: bigint, y: int(?))

See mul

proc mul(ref result: bigint, const ref x: bigint, y: uint(?))

See mul

proc addMul(ref result: bigint, const ref x: bigint, const ref y: bigint)

Adds the product of x and y to result (result = result + (x * y)).

Arguments:

• result : bigint – Where the result is stored

• x : bigint – The first operand of the product

• y : bigint, uint, int – The second operand of the product

See also

GMP.mpz_addmul, GMP.mpz_addmul_ui, and mpz_addmul.

proc addMul(ref result: bigint, const ref x: bigint, y: int(?))

See addMul

proc addMul(ref result: bigint, const ref x: bigint, y: uint(?))

See addMul

proc subMul(ref result: bigint, const ref x: bigint, const ref y: bigint)

Subtracts the product of x and y from result (result = result - (x * y)).

Arguments:

• result : bigint – Where the result is stored

• x : bigint – The first operand of the product

• y : bigint, uint, int – The second operand of the product

See also

GMP.mpz_submul, GMP.mpz_submul_ui, and mpz_submul.

proc subMul(ref result: bigint, const ref x: bigint, y: int(?))

See addMul

proc subMul(ref result: bigint, const ref x: bigint, y: uint(?))

See addMul

proc mul2Exp(ref result: bigint, const ref x: bigint, exp: integral)

Warning

mul2Exp is unstable and may change in the future

Computes x*(2**exp) and stores the result in result.

This is the same as performing a left bit shift of x by exp bits.

Arguments:

• result : bigint – Where the result is stored

• x : bigint – The number to be multiplied

• exp : integral – The exponent that 2 should be raised to before being used

See also

GMP.mpz_mul_2exp and mpz_mul_2exp.

proc neg(ref result: bigint, const ref x: bigint)

Sets result to the negation of x.

Arguments:

• result : bigint – Where the result is stored

• x : bigint – The number to be negated

See also

GMP.mpz_neg amd mpz_neg.

proc abs(ref result: bigint, const ref x: bigint)

Sets result to the absolute value of x.

Arguments:

• result : bigint – Where the result is stored

• x : bigint – The number to take the absolute value of

See also

GMP.mpz_abs amd mpz_abs.

proc div(ref result: bigint, const ref numer: bigint, const ref denom: bigint, param rounding = roundingMode.zero)

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

Arguments:

• result : bigint – Where the result is stored

• numer : bigint – The numerator of the division operation to be performed

• denom : bigint, integral – The denominator of the division operation to be performed

• rounding : roundingMode – The rounding style to use, see roundingMode 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.

See also

GMP.mpz_cdiv_q, GMP.mpz_fdiv_q, GMP.mpz_tdiv_q, and mpz_*div_q.

proc div(ref result: bigint, const ref numer: bigint, denom: integral, param rounding = roundingMode.zero)

See div

proc rem(ref result: bigint, const ref numer: bigint, const ref denom: bigint, param rounding = roundingMode.zero)

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

Arguments:

• result : bigint – Where the result is stored

• numer : bigint – The numerator of the division operation to be performed

• denom : bigint, integral – The denominator of the division operation to be performed

• rounding : roundingMode – The rounding style to use, see roundingMode 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.

Note

When rounding is down, this procedure is equivalent to mod.

See also

GMP.mpz_cdiv_r, GMP.mpz_fdiv_r, GMP.mpz_tdiv_r, and mpz_*div_r.

proc rem(ref result: bigint, const ref numer: bigint, denom: integral, param rounding = roundingMode.zero)

See rem

proc divRem(ref result: bigint, ref remain: bigint, const ref numer: bigint, const ref denom: bigint, param rounding = roundingMode.zero)

Divide numer by denom, forming a quotient and storing it in result, and a remainder and storing it in remain. The quotient and remainder will always satisfy numer = result*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(result) < abs(denom)).

Warning

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

Arguments:

• result : bigint – Where the result is stored

• 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 : roundingMode – The rounding style to use, see roundingMode 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.

See also

GMP.mpz_cdiv_qr, GMP.mpz_fdiv_qr, GMP.mpz_tdiv_qr, and mpz_*div_qr.

proc divRem(ref result: bigint, ref remain: bigint, const ref numer: bigint, denom: integral, param rounding = roundingMode.zero)

See divRem

proc div2Exp(ref result: bigint, const ref numer: bigint, exp: integral, param rounding = roundingMode.zero)

Warning

div2Exp is unstable and may change in the future

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

This is the same as performing a right bit shift of numer by exp bits when rounding is down.

Arguments:

• result : bigint – Where the result is stored

• 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 : roundingMode – The rounding style to use, see roundingMode for a description of what the rounding styles entail. Defaults to zero if unspecified

See also

GMP.mpz_cdiv_q_2exp, GMP.mpz_fdiv_q_2exp, GMP.mpz_tdiv_q_2exp, and mpz_*div_q_2exp.

proc rem2Exp(ref result: bigint, const ref numer: bigint, exp: integral, param rounding = roundingMode.zero)

Warning

rem2Exp is unstable and may change in the future

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

Arguments:

• result : bigint – Where the result is stored

• 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 : roundingMode – The rounding style to use, see roundingMode for a description of what the rounding styles entail. Defaults to zero if unspecified

See also

GMP.mpz_cdiv_r_2exp, GMP.mpz_fdiv_r_2exp, GMP.mpz_tdiv_r_2exp, and mpz_*div_r_2exp.

proc shiftLeft(ref result: bigint, const ref x: bigint, n: integral)

Stores x shifted left by n bits in result. Negative n will result in a right shift.

Arguments:

• result : bigint – Where the result is stored

• x : bigint – The number to be shifted

• n : integral – The number of bits to be shifted

See also

mul2Exp and div2Exp

proc shiftRight(ref result: bigint, const ref x: bigint, n: integral)

Stores x shifted right by n bits in result. Negative n will result in a left shift.

Arguments:

• result : bigint – Where the result is stored

• x : bigint – The number to be shifted

• n : integral – The number of bits to be shifted

See also

div2Exp and mul2Exp

proc mod(ref result: bigint, const ref x: bigint, const ref y: bigint)

Computes the mod operator on the two arguments, defined as mod(x, y) = x - y * floor(x / y).

The result is always >= 0 if y > 0. It is an error if y == 0.

Arguments:

• result : bigint – Where the result is stored

• x : bigint – The dividend

• y : bigint or integral – The divisor

Note

If y is a uint, then fewer conditionals will be evaluated at run time.

Note

This procedure is equivalent to calling rem with rounding set to down.

proc mod(ref result: bigint, const ref x: bigint, y: integral) : int

See mod

proc bigint.cmp(const ref x: bigint) : int

Compares this and x.

Arguments:

x : bigint, uint, int, real – The number to compare against

Returns:

Returns a positive value if this is greater than x, a negative value if this is less than x, or zero if they are equal.

Return type:

int

See also

GMP.mpz_cmp and mpz_cmp.

proc bigint.cmp(x: int(?)) : int

See cmp

proc bigint.cmp(x: uint(?)) : int

See cmp

proc bigint.cmp(x: real) : int

See cmp

proc bigint.cmpabs(const ref x: bigint) : int

Compares the absolute value of this and the absolute value of x.

Arguments:

x : bigint, uint, real – The number to compare against

Returns:

Returns a positive value if abs(this) is greater than abs(x), a negative value if abs(this) is less than abs(x), or zero if they are equal.

Return type:

int

See also

GMP.mpz_cmpabs and mpz_cmpabs.

proc bigint.cmpabs(x: uint) : int

See cmpabs

proc bigint.cmpabs(x: real) : int

See cmpabs

proc bigint.sgn() : int

Warning

bigint.sgn is unstable and may change its name and return type in the future

Returns the sign of this.

Returns:

Returns 1 if positive, -1 if negative, and 0 if zero.

Return type:

int

See also

GMP.mpz_sgn and mpz_sgn.

proc and(ref result: bigint, const ref x: bigint, const ref y: bigint)

Compute the bitwise and of x and y and store it in result.

Arguments:

• result : bigint – Where the result is stored

• x : bigint – First operand

• y : bigint – Second operand

See also

GMP.mpz_and and mpz_and.

proc or(ref result: bigint, const ref x: bigint, const ref y: bigint)

Compute the bitwise inclusive or of x and y and store it in result.

Arguments:

• result : bigint – Where the result is stored

• x : bigint – First operand

• y : bigint – Second operand

See also

GMP.mpz_ior and mpz_ior.

proc xor(ref result: bigint, const ref x: bigint, const ref y: bigint)

Compute the bitwise exclusive or of x and y and store it in result.

Arguments:

• result : bigint – Where the result is stored

• x : bigint – First operand

• y : bigint – Second operand

See also

GMP.mpz_xor and mpz_xor.

proc com(ref result: bigint, const ref x: bigint)

Compute the bitwise one’s complement of x and store it in result.

Arguments:

• result : bigint – Where the result is stored

• x : bigint – Number to be complemented

See also

GMP.mpz_com and mpz_com.

proc ref bigint.set(const ref x: bigint)

Assign x to this

Arguments:

x : bigint – Number to be assigned

See also

GMP.mpz_set and mpz_set.

proc ref bigint.set(x: int(?))

See bigint.set

proc ref bigint.set(x: uint(?))

See bigint.set

proc ref bigint.set(x: real)

See bigint.set

proc ref bigint.set(x: string, base: int = 0)

See bigint.set

proc ref bigint.swap(ref x: bigint)

Swaps this and x

Arguments:

x : bigint – Number to be swapped

See also

GMP.mpz_swap and mpz_swap.