BigInteger¶
Usage
use BigInteger;
The bigint record supports arithmetic operations on arbitrary
precision integers in a manner that is broadly consistent with
the conventional operations on primitive fixed length integers.
The current implementation is based on the low-level types and
functions defined in the GMP module i.e. it is implemented using the
GNU Multiple Precision Integer Arithmetic library (GMP). More specifically
the record bigint wraps the GMP type mpz_t.
The primary benefits of bigint over mpz_t are
- support for multi-locale programs
- the convenience of arithmetic operator overloads
- automatic memory management of GMP data structures
In addition to the expected set of operations, this record provides a number of methods that wrap GMP functions in a natural way:
use BigInteger;
var a = new bigint(234958444);
const b = new bigint("4847382292989382987395534934347");
var c = new bigint();
writeln(a * b);
c.fac(100);
writeln(c);
Wrapping an mpz_t in a bigint record may introduce a
measurable overhead in some cases.
The GMP library defines a low-level API that is based on side-effecting compound operations. The documentation recommends that one prefer to reuse a small number of existing mpz_t structures rather than using many values of short duration.
Matching this style using bigint records and the compound
assignment operators is likely to provide comparable performance to an
implementation based on mpz_t. So, for example:
x = b
x *= c;
x += a;
is likely to achieve better performance than:
x = a + b * c;
In the fall of 2016 the Chapel compiler introduces two short lived temporaries for the intermediate results of the binary operators.
If peak performance is required, perhaps in a critical loop, then it is always possible to invoke the GMP functions directly. For example one might express:
a = a + b * c;
as:
mpz_addmul(a.mpz, b.mpz, c.mpz);
As usual the details are application specific and it is best to measure when peak performance is required.
The operators on bigint include variations that accept Chapel
integers e.g.:
var a = new bigint("9738639463465935");
var b = 9395739153 * a;
The Chapel int(64) literal is converted to an underlying, platform-specific C integer, to invoke the underlying GMP primitive function. This example is likely to work well on popular 64-bit platforms but to fail on common 32-bit platforms. Runtime checks are used to ensure the Chapel types can safely be cast to the platform-specific types. Ths program will halt if the Chapel value cannot be represented using the GMP scalar type.
The checks are controlled by the compiler options --[no-]cast-checks,
--fast, etc.
See GMP for more information on how to use GMP with Chapel.
-
record
bigint¶ -
var
mpz: mpz_t¶ The underlying GMP C structure
-
proc
bigint()¶
-
proc
bigint(const ref num: bigint)
-
proc
bigint(num: int)
-
proc
bigint(num: uint)
-
proc
bigint(str: string, base: int = 0)
-
proc
bigint(str: string, base: int = 0, out error: syserr)
-
proc
size(): size_t¶
-
proc
sizeinbase(base: int): uint¶
-
proc
numLimbs: uint¶
-
proc
get_limbn(n: uint): uint¶
-
proc
mpzStruct(): __mpz_struct¶
-
proc
get_d_2exp(): (uint(32), real)¶
-
proc
get_str(base: int = 10): string¶
-
proc
writeThis(writer)¶
-
var
-
proc =(ref lhs: bigint, const ref rhs: bigint)
-
proc =(ref lhs: bigint, rhs: int)
-
proc =(ref lhs: bigint, rhs: uint)
-
proc
+(const ref a: bigint)¶
-
proc
-(const ref a: bigint)¶
-
proc ~(const ref a: bigint)
-
proc
+(const ref a: bigint, const ref b: bigint)
-
proc
+(const ref a: bigint, b: int)
-
proc
+(a: int, const ref b: bigint)
-
proc
+(const ref a: bigint, b: uint)
-
proc
+(a: uint, const ref b: bigint)
-
proc
-(const ref a: bigint, const ref b: bigint)
-
proc
-(const ref a: bigint, const ref b: int)
-
proc
-(a: int, const ref b: bigint)
-
proc
-(const ref a: bigint, b: uint)
-
proc
-(a: uint, const ref b: bigint)
-
proc
*(const ref a: bigint, const ref b: bigint)¶
-
proc
*(const ref a: bigint, b: int)
-
proc
*(a: int, const ref b: bigint)
-
proc
*(const ref a: bigint, b: uint)
-
proc
*(a: uint, const ref b: bigint)
-
proc
/(const ref a: bigint, const ref b: bigint)¶
-
proc
/(const ref a: bigint, b: integral)
-
proc
**(const ref base: bigint, const ref exp: bigint)¶
-
proc
**(const ref base: bigint, exp: int)
-
proc
**(const ref base: bigint, exp: uint)
-
proc %(const ref a: bigint, const ref b: bigint)
-
proc %(const ref a: bigint, b: int)
-
proc %(const ref a: bigint, b: uint)
-
proc <<(const ref a: bigint, b: int)
-
proc <<(const ref a: bigint, b: uint)
-
proc >>(const ref a: bigint, b: int)
-
proc >>(const ref a: bigint, b: uint)
-
proc &(const ref a: bigint, const ref b: bigint)
-
proc |(const ref a: bigint, const ref b: bigint)
-
proc ^(const ref a: bigint, const ref b: bigint)
-
proc ==(const ref a: bigint, const ref b: bigint)
-
proc ==(const ref a: bigint, b: int)
-
proc ==(a: int, const ref b: bigint)
-
proc ==(const ref a: bigint, b: uint)
-
proc ==(a: uint, const ref b: bigint)
-
proc !=(const ref a: bigint, const ref b: bigint)
-
proc !=(const ref a: bigint, b: int)
-
proc !=(a: int, const ref b: bigint)
-
proc !=(const ref a: bigint, b: uint)
-
proc !=(a: uint, const ref b: bigint)
-
proc >(const ref a: bigint, const ref b: bigint)
-
proc >(const ref a: bigint, b: int)
-
proc >(b: int, const ref a: bigint)
-
proc >(const ref a: bigint, b: uint)
-
proc >(b: uint, const ref a: bigint)
-
proc <(const ref a: bigint, const ref b: bigint)
-
proc <(const ref a: bigint, b: int)
-
proc <(b: int, const ref a: bigint)
-
proc <(const ref a: bigint, b: uint)
-
proc <(b: uint, const ref a: bigint)
-
proc >=(const ref a: bigint, const ref b: bigint)
-
proc >=(const ref a: bigint, b: int)
-
proc >=(b: int, const ref a: bigint)
-
proc >=(const ref a: bigint, b: uint)
-
proc >=(b: uint, const ref a: bigint)
-
proc <=(const ref a: bigint, const ref b: bigint)
-
proc <=(const ref a: bigint, b: int)
-
proc <=(b: int, const ref a: bigint)
-
proc <=(const ref a: bigint, b: uint)
-
proc <=(b: uint, const ref a: bigint)
-
proc +=(ref a: bigint, const ref b: bigint)
-
proc +=(ref a: bigint, b: int)
-
proc +=(ref a: bigint, b: uint)
-
proc -=(ref a: bigint, const ref b: bigint)
-
proc -=(ref a: bigint, b: int)
-
proc -=(ref a: bigint, b: uint)
-
proc *=(ref a: bigint, const ref b: bigint)
-
proc *=(ref a: bigint, b: int)
-
proc *=(ref a: bigint, b: uint)
-
proc /=(ref a: bigint, const ref b: bigint)
-
proc /=(ref a: bigint, b: integral)
-
proc **=(ref base: bigint, const ref exp: bigint)
-
proc **=(ref base: bigint, exp: int)
-
proc **=(ref base: bigint, exp: uint)
-
proc %=(ref a: bigint, const ref b: bigint)
-
proc %=(ref a: bigint, b: int)
-
proc %=(ref a: bigint, b: uint)
-
proc &=(ref a: bigint, const ref b: bigint)
-
proc |=(ref a: bigint, const ref b: bigint)
-
proc ^=(ref a: bigint, const ref b: bigint)
-
proc <<=(ref a: bigint, b: int)
-
proc <<=(ref a: bigint, b: uint)
-
proc >>=(ref a: bigint, b: int)
-
proc >>=(ref a: bigint, b: uint)
-
proc <=>(ref a: bigint, ref b: bigint)
-
proc
jacobi(const ref a: bigint, const ref b: bigint): int¶
-
proc
legendre(const ref a: bigint, const ref p: bigint): int¶
-
proc
kronecker(const ref a: bigint, const ref b: bigint): int¶
-
proc
kronecker(const ref a: bigint, b: int): int
-
proc
kronecker(a: int, const ref b: bigint): int
-
proc
kronecker(const ref a: bigint, b: uint): int
-
proc
kronecker(a: uint, const ref b: bigint): int
-
proc
bigint.divexact(const ref n: bigint, const ref d: bigint)¶
-
proc
bigint.divexact(const ref n: bigint, d: integral)
-
proc
bigint.divisible_p(const ref d: bigint): int¶
-
proc
bigint.divisible_p(d: int): int
-
proc
bigint.divisible_p(d: uint): int
-
proc
bigint.divisible_2exp_p(b: integral): int¶
-
proc
bigint.congruent_p(const ref c: bigint, const ref d: bigint): int¶
-
proc
bigint.congruent_p(c: integral, d: integral): int
-
proc
bigint.congruent_2exp_p(const ref c: bigint, b: integral): int¶
-
proc
bigint.powm(const ref base: bigint, const ref exp: bigint, const ref mod: bigint)¶
-
proc
bigint.powm(const ref base: bigint, exp: int, const ref mod: bigint)
-
proc
bigint.powm(const ref base: bigint, exp: uint, const ref mod: bigint)
-
proc
bigint.pow(const ref base: bigint, exp: int)¶
-
proc
bigint.pow(const ref base: bigint, exp: uint)
-
proc
bigint.pow(base: int, exp: int)
-
proc
bigint.pow(base: uint, exp: uint)
-
proc
bigint.root(const ref a: bigint, n: uint): int¶
-
proc
bigint.rootrem(ref rem: bigint, const ref u: bigint, n: uint)¶
-
proc
bigint.sqrt(const ref a: bigint)¶
-
proc
bigint.sqrtrem(ref rem: bigint, const ref a: bigint)¶
-
proc
bigint.perfect_power_p(): int¶
-
proc
bigint.perfect_square_p(): int¶
-
proc
bigint.probab_prime_p(reps: int): int¶
-
proc
bigint.nextprime(const ref a: bigint)¶
-
proc
bigint.gcd(const ref a: bigint, const ref b: bigint)¶
-
proc
bigint.gcd(const ref a: bigint, b: int)
-
proc
bigint.gcd(const ref a: bigint, b: uint)
-
proc
bigint.gcdext(ref s: bigint, ref t: bigint, const ref a: bigint, const ref b: bigint)¶
-
proc
bigint.lcm(const ref a: bigint, const ref b: bigint)¶
-
proc
bigint.lcm(const ref a: bigint, b: int)
-
proc
bigint.lcm(const ref a: bigint, b: uint)
-
proc
bigint.invert(const ref a: bigint, const ref b: bigint): int¶
-
proc
bigint.remove(const ref a: bigint, const ref f: bigint): uint¶
-
proc
bigint.fac(a: integral)¶
-
proc
bigint.bin(const ref n: bigint, k: integral)¶
-
proc
bigint.bin(n: uint, k: integral)
-
proc
bigint.fib(n: integral)¶
-
proc
bigint.fib2(ref fnsub1: bigint, n: integral)¶
-
proc
bigint.lucnum(n: integral)¶
-
proc
bigint.lucnum2(ref fnsub1: bigint, n: integral)¶
-
proc
bigint.popcount(): uint¶
-
proc
bigint.hamdist(const ref b: bigint): uint¶
-
proc
bigint.scan0(starting_bit: integral): uint¶
-
proc
bigint.scan1(starting_bit: integral): uint¶
-
proc
bigint.setbit(bit_index: integral)¶
-
proc
bigint.clrbit(bit_index: integral)¶
-
proc
bigint.combit(bit_index: integral)¶
-
proc
bigint.tstbit(bit_index: integral): int¶
-
proc
bigint.fits_ulong_p(): int¶
-
proc
bigint.fits_slong_p(): int¶
-
proc
bigint.fits_uint_p(): int¶
-
proc
bigint.fits_sint_p(): int¶
-
proc
bigint.fits_ushort_p(): int¶
-
proc
bigint.fits_sshort_p(): int¶
-
proc
bigint.even_p(): int¶
-
proc
bigint.odd_p(): int¶
-
proc
bigint.add(const ref a: bigint, const ref b: bigint)¶
-
proc
bigint.add(const ref a: bigint, b: int)
-
proc
bigint.add(const ref a: bigint, b: uint)
-
proc
bigint.sub(const ref a: bigint, const ref b: bigint)¶
-
proc
bigint.sub(const ref a: bigint, b: int)
-
proc
bigint.sub(const ref a: bigint, b: uint)
-
proc
bigint.sub(a: int, const ref b: bigint)
-
proc
bigint.sub(a: uint, const ref b: bigint)
-
proc
bigint.mul(const ref a: bigint, const ref b: bigint)¶
-
proc
bigint.mul(const ref a: bigint, b: int)
-
proc
bigint.mul(const ref a: bigint, b: uint)
-
proc
bigint.addmul(const ref a: bigint, const ref b: bigint)¶
-
proc
bigint.addmul(const ref a: bigint, b: int)
-
proc
bigint.addmul(const ref a: bigint, b: uint)
-
proc
bigint.submul(const ref a: bigint, const ref b: bigint)¶
-
proc
bigint.submul(const ref a: bigint, b: int)
-
proc
bigint.submul(const ref a: bigint, b: uint)
-
proc
bigint.mul_2exp(const ref a: bigint, b: integral)¶
-
proc
bigint.neg(const ref a: bigint)¶
-
proc
bigint.abs(const ref a: bigint)¶
-
proc
bigint.div_q(const ref n: bigint, const ref d: bigint, param rounding = Round.ZERO)¶
-
proc
bigint.div_q(const ref n: bigint, d: integral, param rounding = Round.ZERO)
-
proc
bigint.div_r(const ref n: bigint, const ref d: bigint, param rounding = Round.ZERO)¶
-
proc
bigint.div_r(const ref n: bigint, d: integral, param rounding = Round.ZERO)
-
proc
bigint.div_qr(ref r: bigint, const ref n: bigint, const ref d: bigint, param rounding = Round.ZERO)¶
-
proc
bigint.div_qr(ref r: bigint, const ref n: bigint, d: integral, param rounding = Round.ZERO)
-
proc
bigint.div_q_2exp(const ref n: bigint, b: integral, param rounding = Round.ZERO)¶
-
proc
bigint.div_r_2exp(const ref n: bigint, b: integral, param rounding = Round.ZERO)¶
-
proc
bigint.mod(const ref a: bigint, const ref b: bigint)¶
-
proc
bigint.mod(const ref a: bigint, b: integral): uint
-
proc
bigint.cmp(const ref b: bigint): int¶
-
proc
bigint.cmp(b: int): int
-
proc
bigint.cmp(b: uint): int
-
proc
bigint.cmp(b: real): int
-
proc
bigint.cmpabs(const ref b: bigint): int¶
-
proc
bigint.cmpabs(b: uint): int
-
proc
bigint.cmpabs(b: real): int
-
proc
bigint.sgn(): int¶
-
proc
bigint.and(const ref a: bigint, const ref b: bigint)¶
-
proc
bigint.ior(const ref a: bigint, const ref b: bigint)¶
-
proc
bigint.xor(const ref a: bigint, const ref b: bigint)¶
-
proc
bigint.com(const ref a: bigint)¶
-
proc
bigint.set(const ref a: bigint)¶
-
proc
bigint.set(num: int)
-
proc
bigint.set(num: uint)
-
proc
bigint.set(num: real)
-
proc
bigint.set(str: string, base: int = 0)
-
proc
bigint.swap(ref a: bigint)¶