BigInteger

Usage

use BigInteger;

or

import BigInteger;

Provides a ‘bigint’ type and supporting math operations.

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

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

config param bigintInitThrows = false

A compile-time parameter to control the behavior of bigint initializers that take a string argument.

When false, the deprecated behavior is used (i.e., errors will trigger a halt at execution.)

When true, the new behavior is used (i.e., errors will cause a BadFormatError to be thrown)

record bigint
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)

Warning

bigint initializers that halt are deprecated, please set the config param bigintInitThrows to ‘true’ to opt in to using the new initializer that throws

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

Warning

bigint initializers that return the errorCode type via an ‘out’ argument are deprecated, please remove the argument and ensure the config param bigintInitThrows is set to ‘true’ to opt in to using the new initializer that throws

proc init(str: 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

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

  • base : int – The base to use when creating the bigint from str. May vary from 2 to 62 or be 0. Defaults to 0, which causes the base to be read from the start of the str 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 str is not a correctly formatted number in base base.

proc size(): c_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 mpzStruct(): __mpz_struct

Warning

mpzStruct is deprecated, please use getImpl instead

proc getImpl(): __mpz_struct

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

This method is provided as a convenience but its result may change in the future.

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

Warning

get_d_2exp is deprecated in favor of bigint.getD2Exp, which returns (d, exp) instead of (exp, d). Please use that method instead

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

proc get_str(base: int = 10): string
proc writeThis(writer) throws
operator bigint. = (ref lhs: bigint, const ref rhs: bigint)
operator bigint. = (ref lhs: bigint, rhs: int)
operator bigint. = (ref lhs: bigint, rhs: uint)
operator bigint.+(const ref a: bigint): bigint
operator bigint.-(const ref a: bigint): bigint
operator bigint.~(const ref a: bigint): bigint
operator bigint.+(const ref a: bigint, const ref b: bigint): bigint
operator bigint.+(const ref a: bigint, b: int): bigint
operator bigint.+(const ref a: bigint, b: uint): bigint
operator bigint.+(a: int, const ref b: bigint): bigint
operator bigint.+(a: uint, const ref b: bigint): bigint
operator bigint.-(const ref a: bigint, const ref b: bigint): bigint
operator bigint.-(const ref a: bigint, b: int): bigint
operator bigint.-(const ref a: bigint, b: uint): bigint
operator bigint.-(a: int, const ref b: bigint): bigint
operator bigint.-(a: uint, const ref b: bigint): bigint
operator bigint.*(const ref a: bigint, const ref b: bigint): bigint
operator bigint.*(const ref a: bigint, b: int): bigint
operator bigint.*(const ref a: bigint, b: uint): bigint
operator bigint.*(a: int, const ref b: bigint): bigint
operator bigint.*(a: uint, const ref b: bigint): bigint
operator bigint./(const ref a: bigint, const ref b: bigint): bigint
operator bigint./(const ref a: bigint, b: integral): bigint

Divide a by b, returning the result.

Arguments

  • a : bigint – The numerator of the division operation

  • b : bigint or integral – The denominator of the division operation

Returns

The result of dividing a by b

Return type

bigint

operator bigint.**(const ref base: bigint, const ref exp: bigint): bigint
operator bigint.**(const ref base: bigint, exp: int): bigint
operator bigint.**(const ref base: bigint, exp: uint): bigint
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.

operator bigint.%(const ref a: bigint, b: int): 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.

operator bigint.%(const ref a: bigint, b: uint): 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.

operator bigint.<<(const ref a: bigint, b: int): bigint
operator bigint.<<(const ref a: bigint, b: uint): bigint
operator bigint.>>(const ref a: bigint, b: int): bigint
operator bigint.>>(const ref a: bigint, b: uint): bigint
operator bigint.&(const ref a: bigint, const ref b: bigint): bigint
operator bigint.|(const ref a: bigint, const ref b: bigint): bigint
operator bigint.^(const ref a: bigint, const ref b: bigint): bigint
operator bigint.==(const ref a: bigint, const ref b: bigint): bool
operator bigint.==(const ref a: bigint, b: int): bool
operator bigint.==(const ref a: bigint, b: uint): bool
operator bigint.==(a: int, const ref b: bigint): bool
operator bigint.==(a: uint, const ref b: bigint): bool
operator bigint.!=(const ref a: bigint, const ref b: bigint): bool
operator bigint.!=(const ref a: bigint, b: int): bool
operator bigint.!=(const ref a: bigint, b: uint): bool
operator bigint.!=(a: int, const ref b: bigint): bool
operator bigint.!=(a: uint, const ref b: bigint): bool
operator bigint.>(const ref a: bigint, const ref b: bigint): bool
operator bigint.>(const ref a: bigint, b: int): bool
operator bigint.>(const ref a: bigint, b: uint): bool
operator bigint.>(a: int, const ref b: bigint): bool
operator bigint.>(a: uint, const ref b: bigint): bool
operator bigint.<(const ref a: bigint, const ref b: bigint): bool
operator bigint.<(const ref a: bigint, b: int): bool
operator bigint.<(const ref a: bigint, b: uint): bool
operator bigint.<(a: int, const ref b: bigint): bool
operator bigint.<(a: uint, const ref b: bigint): bool
operator bigint.>=(const ref a: bigint, const ref b: bigint): bool
operator bigint.>=(const ref a: bigint, b: int): bool
operator bigint.>=(const ref a: bigint, b: uint): bool
operator bigint.>=(a: int, const ref b: bigint): bool
operator bigint.>=(a: uint, const ref b: bigint): bool
operator bigint.<=(const ref a: bigint, const ref b: bigint): bool
operator bigint.<=(const ref a: bigint, b: int): bool
operator bigint.<=(const ref a: bigint, b: uint): bool
operator bigint.<=(a: int, const ref b: bigint): bool
operator bigint.<=(a: uint, const ref b: bigint): bool
operator bigint.+=(ref a: bigint, const ref b: bigint)
operator bigint.+=(ref a: bigint, b: int)
operator bigint.+=(ref a: bigint, b: uint)
operator bigint.-=(ref a: bigint, const ref b: bigint)
operator bigint.-=(ref a: bigint, b: int)
operator bigint.-=(ref a: bigint, b: uint)
operator bigint.*=(ref a: bigint, const ref b: bigint)
operator bigint.*=(ref a: bigint, b: int)
operator bigint.*=(ref a: bigint, b: uint)
operator bigint./=(ref a: bigint, const ref b: bigint)
operator bigint./=(ref a: bigint, b: integral)

Divide a by b, storing the result in a.

Arguments

  • a : bigint – The numerator of the division operation

  • b : bigint or integral – The denominator of the division operation

operator bigint.**=(ref base: bigint, const ref exp: bigint)
operator bigint.**=(ref base: bigint, exp: int)
operator bigint.**=(ref base: bigint, exp: uint)
operator bigint.%=(ref a: bigint, const ref b: bigint)

Mod a by b, storing the result in a.

Here, the modulo operation is defined as a % b = a - b * trunc(a / b).

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

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

Mod a by b, storing the result in a.

Here, the modulo operation is defined as a % b = a - b * trunc(a / b).

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

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

Mod a by b, storing the result in a.

Here, the modulo operation is defined as a % b = a - b * trunc(a / b).

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

operator bigint.&=(ref a: bigint, const ref b: bigint)
operator bigint.|=(ref a: bigint, const ref b: bigint)
operator bigint.^=(ref a: bigint, const ref b: bigint)
operator bigint.<<=(ref a: bigint, b: int)
operator bigint.<<=(ref a: bigint, b: uint)
operator bigint.>>=(ref a: bigint, b: int)
operator bigint.>>=(ref a: bigint, b: uint)
operator 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)

Warning

n and d are deprecated - please use numer and denom respectively

proc bigint.divexact(const ref n: bigint, d: integral)

Warning

n and d are deprecated - please use numer and denom respectively

proc divexact(ref result: bigint, const ref numer: bigint, const ref denom: bigint)
proc bigint.divexact(const ref numer: bigint, const ref denom: bigint)

Warning

bigint.divexact method is deprecated - please use the standalone function divexact

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

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

proc bigint.divexact(const ref numer: bigint, denom: integral)

Computes numer/denom and stores the result in this, 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

  • numer : bigint – numerator

  • denom : bigint or integral – denominator

Warning

bigint.divexact method is deprecated - please use the standalone function divexact

proc bigint.divisible_p(const ref d: bigint): int

Warning

bigint.divisible_p is deprecated, use bigint.isDivisible instead

proc bigint.divisible_p(d: int): int

Warning

bigint.divisible_p is deprecated, use bigint.isDivisible instead

proc bigint.divisible_p(d: uint): int

Warning

bigint.divisible_p is deprecated, use bigint.isDivisible instead

proc bigint.isDivisible(const ref div: bigint): bool
proc bigint.isDivisible(div: int): bool
proc bigint.isDivisible(div: uint): 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

proc bigint.divisible_2exp_p(b: integral): int

Warning

bigint.divisible_2exp_p is deprecated, use bigint.isDivisibleBy2Pow instead

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

proc bigint.congruent_p(const ref c: bigint, const ref d: bigint): int

Warning

bigint.congruent_p is deprecated, use bigint.isCongruent instead

proc bigint.congruent_p(c: integral, d: integral): int

Warning

bigint.congruent_p is deprecated, use bigint.isCongruent instead

proc bigint.isCongruent(const ref con: bigint, const ref mod: bigint): bool
proc bigint.isCongruent(con: integral, mod: integral): 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

proc bigint.congruent_2exp_p(const ref c: bigint, b: integral): int

Warning

bigint.congruent_2exp_p is deprecated, use bigint.isCongruentBy2Pow instead

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

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 powMod(ref result: bigint, const ref base: bigint, const ref exp: bigint, const ref mod: bigint)
proc bigint.powMod(const ref base: bigint, const ref exp: bigint, const ref mod: bigint)

Warning

bigint.powMod method is deprecated - please use the standalone function powMod

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

Warning

bigint.powMod method is deprecated - please use the standalone function powMod

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

Set result to the result of (base raised to 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.

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.

Warning

bigint.powMod method is deprecated - please use the standalone function powMod

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

Warning

bigint.pow method is deprecated - please use the standalone function pow

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

Warning

bigint.pow method is deprecated - please use the standalone function pow

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

Warning

bigint.pow method is deprecated - please use the standalone function pow

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

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.

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.

Warning

bigint.pow method is deprecated - please use the standalone function pow

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

Warning

bigint.root method is deprecated - please use the standalone function root

proc rootrem(ref root: bigint, ref rem: bigint, const ref u: bigint, n: uint)
proc bigint.rootrem(ref rem: bigint, const ref u: bigint, n: uint)

Warning

bigint.rootrem method is deprecated - please use the standalone function rootrem

proc sqrt(ref result: bigint, const ref a: bigint)
proc bigint.sqrt(const ref a: bigint)

Warning

bigint.sqrt method is deprecated - please use the standalone function sqrt

proc sqrtrem(ref root: bigint, ref rem: bigint, const ref a: bigint)
proc bigint.sqrtrem(ref rem: bigint, const ref a: bigint)

Warning

bigint.sqrtrem method is deprecated - please use the standalone function sqrtrem

proc bigint.perfect_power_p(): int

Warning

bigint.perfect_power_p is deprecated, use bigint.isPerfectPower instead

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.

proc bigint.perfect_square_p(): int

Warning

bigint.perfect_square_p is deprecated, use bigint.isPerfectSquare instead

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

proc bigint.probab_prime_p(reps: int): int

Warning

bigint.probab_prime_p is deprecated, use bigint.probablyPrime instead

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.

  • primality.notPrime indicates that the number is not a prime.

  • primality.maybePrime indicates that the number may or may not be a prime.

  • primality.isPrime indicates that the number is a prime.

proc bigint.probablyPrime(reps: int): primality

Determine whether this is prime. Returns one of the primality constants - primality.isPrime, primality.maybePrime, or primality.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 primality.maybePrime if a definitive answer can’t be found before then.

Returns

primality.isPrime, primality.maybePrime or primality.notPrime.

Return type

primality

proc nextprime(ref result: bigint, const ref a: bigint)
proc bigint.nextprime(const ref a: bigint)

Warning

bigint.nextprime method is deprecated - please use the standalone function nextprime

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

Warning

bigint.gcd method is deprecated - please use the standalone function gcd

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

Warning

bigint.gcd method is deprecated - please use the standalone function gcd

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

Warning

bigint.gcd method is deprecated - please use the standalone function gcd

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

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

This fulfills the same role as the GMP function mpz_gcdext.

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.

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

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

Note

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

This fulfills the same role as the GMP function mpz_gcdext.

Arguments

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

Warning

bigint.gcd method is deprecated - please use the standalone function gcd

proc bigint.gcdext(ref s: bigint, ref t: bigint, const ref a: bigint, const ref b: bigint)

Warning

gcdext is deprecated, please use the new overload of bigint.gcd with s and t arguments instead

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

Warning

bigint.lcm method is deprecated - please use the standalone function lcm

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

Warning

bigint.lcm method is deprecated - please use the standalone function lcm

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

Warning

bigint.lcm method is deprecated - please use the standalone function lcm

class InversionError: Error

An InversionError is thrown if a bigint.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 a: bigint, const ref b: bigint) throws

Set the value of result to the inverse of a modulo b

Note

If an inverse does not exist, an InversionError will be thrown, and the value of result will be left undefined

This fulfills the same role as the GMP number theoretic function mpz_invert.

Arguments

  • result : bigint – Where the result is stored

  • a : bigint – The dividend of the modulo operation

  • b : bigint – The divisor of the modulo operation

proc bigint.invert(const ref a: bigint, const ref b: bigint) throws

Set the value of this to the inverse of a modulo b

Note

If an inverse does not exist, an InversionError will be thrown, and the value of this will be left undefined

This fulfills the same role as the GMP number theoretic function mpz_invert.

Arguments

  • a : bigint – The dividend of the modulo operation

  • b : bigint – The divisor of the modulo operation

Warning

bigint.invert method is deprecated - please use the standalone function invert

proc bigint.remove(const ref a: bigint, const ref f: bigint): uint

Warning

bigint.remove is deprecated, use bigint.removeFactor instead

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

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

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

Arguments

  • 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

Warning

bigint.removeFactor method is deprecated - please use the standalone function removeFactor

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

Warning

bigint.fac method is deprecated - please use the standalone function fac

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

Warning

bigint.bin method is deprecated - please use the standalone function bin

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

Warning

bigint.bin method is deprecated - please use the standalone function bin

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

Warning

bigint.fib method is deprecated - please use the standalone function fib

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

Warning

bigint.fib2 method is deprecated - please use the standalone function fib2

proc lucnum(ref result: bigint, n: integral)
proc bigint.lucnum(n: integral)

Warning

bigint.lucnum method is deprecated - please use the standalone function lucnum

proc lucnum2(ref result: bigint, ref fnsub1: bigint, n: integral)
proc bigint.lucnum2(ref fnsub1: bigint, n: integral)

Warning

bigint.lucnum2 method is deprecated - please use the standalone function lucnum2

proc bigint.popcount(): uint
proc bigint.hamdist(const ref b: bigint): uint
proc bigint.scan0(starting_bit: integral): uint

Warning

The ‘starting_bit’ argument is deprecated, please use ‘startBitIdx’ instead

proc bigint.scan0(startBitIdx: integral): uint

Scan this, starting from startBitIdx, towards more significant bits until the first 0 bit is found. Return the index of the found bit.

If the bit at startBitIdx is 0, 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

proc bigint.scan1(starting_bit: integral): uint

Warning

The ‘starting_bit’ argument is deprecated, please use ‘startBitIdx’ instead

proc bigint.scan1(startBitIdx: integral): uint

Scan this, starting from startBitIdx, towards more significant bits until the first 1 bit is found. Return the index of the found bit.

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

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

proc bigint.fits_ulong_p(): int

Warning

fits_ulong_p is deprecated - please use bigint.fitsInto(c_ulong) instead

proc bigint.fits_slong_p(): int

Warning

fits_slong_p is deprecated - please use bigint.fitsInto(c_long) instead

proc bigint.fits_uint_p(): int

Warning

fits_uint_p is deprecated - please use bigint.fitsInto(c_uint) instead

proc bigint.fits_sint_p(): int

Warning

fits_sint_p is deprecated - please use bigint.fitsInto(c_int) instead

proc bigint.fits_ushort_p(): int

Warning

fits_ushort_p is deprecated - please use bigint.fitsInto(c_ushort) instead

proc bigint.fits_sshort_p(): int

Warning

fits_sshort_p is deprecated - please use bigint.fitsInto(c_short) instead

proc bigint.even_p(): int

Warning

bigint.even_p is deprecated, use bigint.isEven instead

proc bigint.isEven(): bool

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

proc bigint.odd_p(): int

Warning

bigint.odd_p is deprecated, use bigint.isOdd instead

proc bigint.isOdd(): bool

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

proc add(ref result: bigint, const ref a: bigint, const ref b: bigint)
proc bigint.add(const ref a: bigint, const ref b: bigint)

Warning

bigint.add method is deprecated - please use the standalone function add

proc add(ref result: bigint, const ref a: bigint, b: int)
proc bigint.add(const ref a: bigint, b: int)

Warning

bigint.add method is deprecated - please use the standalone function add

proc add(ref result: bigint, const ref a: bigint, b: uint)
proc bigint.add(const ref a: bigint, b: uint)

Warning

bigint.add method is deprecated - please use the standalone function add

proc sub(ref result: bigint, const ref a: bigint, const ref b: bigint)
proc bigint.sub(const ref a: bigint, const ref b: bigint)

Warning

bigint.sub method is deprecated - please use the standalone function sub

proc sub(ref result: bigint, const ref a: bigint, b: int)
proc bigint.sub(const ref a: bigint, b: int)

Warning

bigint.sub method is deprecated - please use the standalone function sub

proc sub(ref result: bigint, const ref a: bigint, b: uint)
proc bigint.sub(const ref a: bigint, b: uint)

Warning

bigint.sub method is deprecated - please use the standalone function sub

proc sub(ref result: bigint, a: int, const ref b: bigint)
proc bigint.sub(a: int, const ref b: bigint)

Warning

bigint.sub method is deprecated - please use the standalone function sub

proc sub(ref result: bigint, a: uint, const ref b: bigint)
proc bigint.sub(a: uint, const ref b: bigint)

Warning

bigint.sub method is deprecated - please use the standalone function sub

proc mul(ref result: bigint, const ref a: bigint, const ref b: bigint)
proc bigint.mul(const ref a: bigint, const ref b: bigint)

Warning

bigint.mul method is deprecated - please use the standalone function mul

proc mul(ref result: bigint, const ref a: bigint, b: int)
proc bigint.mul(const ref a: bigint, b: int)

Warning

bigint.mul method is deprecated - please use the standalone function mul

proc mul(ref result: bigint, const ref a: bigint, b: uint)
proc bigint.mul(const ref a: bigint, b: uint)

Warning

bigint.mul method is deprecated - please use the standalone function mul

proc addmul(ref result: bigint, const ref a: bigint, const ref b: bigint)
proc bigint.addmul(const ref a: bigint, const ref b: bigint)

Warning

bigint.addmul method is deprecated - please use the standalone function addmul

proc addmul(ref result: bigint, const ref a: bigint, b: int)
proc bigint.addmul(const ref a: bigint, b: int)

Warning

bigint.addmul method is deprecated - please use the standalone function addmul

proc addmul(ref result: bigint, const ref a: bigint, b: uint)
proc bigint.addmul(const ref a: bigint, b: uint)

Warning

bigint.addmul method is deprecated - please use the standalone function addmul

proc submul(ref result: bigint, const ref a: bigint, const ref b: bigint)
proc bigint.submul(const ref a: bigint, const ref b: bigint)

Warning

bigint.submul method is deprecated - please use the standalone function submul

proc submul(ref result: bigint, const ref a: bigint, b: int)
proc bigint.submul(const ref a: bigint, b: int)

Warning

bigint.submul method is deprecated - please use the standalone function submul

proc submul(ref result: bigint, const ref a: bigint, b: uint)
proc bigint.submul(const ref a: bigint, b: uint)

Warning

bigint.submul method is deprecated - please use the standalone function submul

proc mul_2exp(ref result: bigint, const ref a: bigint, b: integral)
proc bigint.mul_2exp(const ref a: bigint, b: integral)

Warning

bigint.mul_2exp method is deprecated - please use the standalone function mul_2exp

proc neg(ref result: bigint, const ref a: bigint)
proc bigint.neg(const ref a: bigint)

Warning

bigint.neg method is deprecated - please use the standalone function neg

proc abs(ref result: bigint, const ref a: bigint)
proc bigint.abs(const ref a: bigint)

Warning

bigint.abs method is deprecated - please use the standalone function abs

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 divQ(ref result: bigint, const ref numer: bigint, const ref denom: bigint, param rounding = round.zero)
proc bigint.divQ(const ref numer: bigint, const ref denom: bigint, param rounding = round.zero)

Warning

bigint.divQ method is deprecated - please use the standalone function divQ

proc divQ(ref result: bigint, const ref numer: bigint, denom: integral, param rounding = round.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 : 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.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.

Warning

bigint.divQ method is deprecated - please use the standalone function divQ

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 divR(ref result: bigint, const ref numer: bigint, const ref denom: bigint, param rounding = round.zero)
proc bigint.divR(const ref numer: bigint, const ref denom: bigint, param rounding = round.zero)

Warning

bigint.divR method is deprecated - please use the standalone function divR

proc divR(ref result: bigint, const ref numer: bigint, denom: integral, param rounding = round.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 : 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.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.

Warning

bigint.divR method is deprecated - please use the standalone function divR

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 divQR(ref result: bigint, 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, const ref denom: bigint, param rounding = round.zero)

Warning

bigint.divQR method is deprecated - please use the standalone function divQR

proc divQR(ref result: bigint, ref remain: bigint, const ref numer: bigint, denom: integral, param rounding = round.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 : 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.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.

Warning

bigint.divQR method is deprecated - please use the standalone function divQR

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 divQ2Exp(ref result: bigint, const ref numer: bigint, exp: integral, param rounding = round.zero)

Divide numer by 2^exp, 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

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

Warning

bigint.divQ2Exp method is deprecated - please use the standalone function divQ2Exp

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 divR2Exp(ref result: bigint, const ref numer: bigint, exp: integral, param rounding = round.zero)

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

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

Warning

bigint.divR2Exp method is deprecated - please use the standalone function divR2Exp

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

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

The result is stored in result.

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

proc bigint.mod(const ref a: bigint, const ref b: bigint)

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

The result is stored in this.

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

Warning

bigint.mod method is deprecated - please use the standalone function mod

proc mod(ref result: bigint, const ref a: bigint, b: integral): int

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

If b is of an unsigned type, then fewer conditionals will be evaluated at run time.

The result is stored in result and returned as an int.

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

proc bigint.mod(const ref a: bigint, b: integral): int

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

If b is of an unsigned type, then fewer conditionals will be evaluated at run time.

The result is stored in this and returned as an int.

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

Warning

bigint.mod method is deprecated - please use the standalone function mod

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 and(ref result: bigint, const ref a: bigint, const ref b: bigint)
proc bigint.and(const ref a: bigint, const ref b: bigint)

Warning

bigint.and method is deprecated - please use the standalone function and

proc ior(ref result: bigint, const ref a: bigint, const ref b: bigint)
proc bigint.ior(const ref a: bigint, const ref b: bigint)

Warning

bigint.ior method is deprecated - please use the standalone function ior

proc xor(ref result: bigint, const ref a: bigint, const ref b: bigint)
proc bigint.xor(const ref a: bigint, const ref b: bigint)

Warning

bigint.xor method is deprecated - please use the standalone function xor

proc com(ref result: bigint, const ref a: bigint)
proc bigint.com(const ref a: bigint)

Warning

bigint.com method is deprecated - please use the standalone function com

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)