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
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);
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.
- record bigint : serializable¶
The bigint type supports arithmetic operations on arbitrary precision integers across multiple locales.
- proc init(const ref x: bigint)
Initializes a
bigint
to the value ofx
.
- 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 basebase
number, will throw aBadFormatError
.- Arguments:
x :
string
– The value to be stored in the resultingbigint
.base :
int
– The base to use when creating thebigint
fromx
. May vary from2
to62
or be0
. Defaults to0
, which causes the base to be read from the start of thex
itself (0x
and0X
will give hexadecimal,0b
and0B
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 basebase
.
- proc init=(x: integral)
See
init=
- proc sizeInBase(base: int) : int¶
Determine the size of
this
measured in number of digits in the givenbase
. The sign ofthis
is ignored, only the absolute value is used.- Arguments:
base :
int
– The base in which to compute the number of digits used to representthis
. Can be between 2 and 62.- Returns:
The size of
this
measured in number of digits in the givenbase
. Will either be exact or 1 too big. Ifbase
is a power of 2, will always be exact. Ifthis
is 0, will always return 1.- Return type:
int
See also
- 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 areal
(truncated if necessary, by rounding towards zero) and the exponent. The returned tuple fulfills the conditiond * 2^exp == this
whered
is the first value in the tuple andexp
is the second.- Returns:
a tuple representing the number in multiple parts,
(d, exp)
, such that their combinationd * 2^exp
is equal tothis
.d
in this case will be in the range0.5 <= abs(d) < 1
, unlessthis
is0
, in which cased == 0.0
andexp == 0
.- Return type:
(real, uint(32))
See also
- 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
fromx
, seebigint.init
.
- operator :(x: string, type t: bigint) : bigint throws
Constructs a new
bigint
fromx
, see thebigint.init
overload which takes astring
.
- operator :(x: bool, type t: bigint) : bigint throws
Constructs a new
bigint
fromx
, seebigint.init
.
- operator :(const ref x: bigint, type t: numeric) where isIntType(t)
Convert
x
to a signed integer. Ifx
is larger thant
, the value returned is the least significant part ofx
with the same sign asx
.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. Ifx
is larger thant
, the value returned is the least significant part ofx
ignoring the sign ofx
.See also
GMP.mpz_get_ui
and mpz_get_ui.
- operator :(const ref x: bigint, type t: numeric) where isRealType(t)
Convert
x
to areal
with typet
(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, 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, 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, b: integral) : bigint
See
div
- 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: 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) : 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, b: int)
See
add
- operator bigint.+=(ref a: bigint, b: uint)
See
add
- operator bigint.-=(ref a: bigint, b: int)
See
sub
- operator bigint.-=(ref a: bigint, b: uint)
See
sub
- operator bigint.*=(ref a: bigint, b: int)
See
mul
- operator bigint.*=(ref a: bigint, b: uint)
See
mul
- operator bigint./=(ref a: bigint, b: integral)
See
div
- operator bigint.**=(ref base: bigint, exp: int)
See
pow
- operator bigint.**=(ref base: bigint, exp: uint)
See
pow
- operator bigint.%=(ref a: bigint, b: int)
See
bigint.%
- operator bigint.%=(ref a: bigint, b: uint)
See
bigint.%
- 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 whenb
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 whenp
is an odd positive prime number.- Return type:
int
See also
- 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. Whenb
is odd this is the same as the Jacobi symbol.- Return type:
int
See also
- 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 inresult
, which is abigint
instance.Warning
divExact
is optimized to handle cases wherenumer/denom
results in an integer. Whennumer/denom
does not produce an integer, this method may produce incorrect results.- Arguments:
See also
- proc divExact(ref result: bigint, const ref numer: bigint, denom: integral)
See
divExact
- proc bigint.isDivisible(const ref div: bigint) : bool¶
Return
true
ifthis
is exactly divisible bydiv
.this
is divisible bydiv
if there exists an integerq
satisfyingthis = q*div
. Unlike the other division functions,0
is an acceptable value fordiv
and only0
is considered divisible by0
.- Arguments:
div :
bigint
,int
oruint
– number to check ifthis
is divisible by- Returns:
true
ifthis
is exactly divisible bydiv
,false
otherwise- Return type:
bool
See also
- proc bigint.isDivisible(div: int) : bool
See
isDivisible
- proc bigint.isDivisible(div: uint) : bool
See
isDivisible
- proc bigint.isDivisibleBy2Pow(exp: integral) : bool¶
Return
true
ifthis
is exactly divisible by2^exp
.this
is divisible by2^exp
if there exists an integerq
satisfyingthis = q*2^exp
.- Arguments:
exp :
integral
– power of 2 to check ifthis
is divisible by- Returns:
true
ifthis
is exactly divisible by2^exp
,false
otherwise- Return type:
bool
See also
- proc bigint.isCongruent(const ref con: bigint, const ref mod: bigint) : bool¶
Return
true
ifthis
is congruent tocon % mod
.this
is congruent tocon % mod
if there exists an integerq
satisfyingthis = con + q*mod
. Unlike the other division functions,0
is an acceptable value formod
. As a resultthis
andcon
are considered congruent modulo0
only when exactly equal.- Arguments:
- Returns:
true
ifthis
is congruent tocon
modulomod
,false
otherwise- Return type:
bool
See also
- proc bigint.isCongruent(con: integral, mod: integral) : bool
See
isCongruent
- proc bigint.isCongruentBy2Pow(const ref con: bigint, modExp: integral) : bool¶
Return
true
ifthis
is congruent tocon % 2^modExp
.this
is congruent tocon % 2^modExp
if there exists an integerq
satisfyingthis = con + q*2^modExp
.- Arguments:
con :
bigint
orintegral
– number to determine ifthis
is congruent to, modulo2^modExp
.modExp :
integral
– power of 2 to use as the divisor ofcon
when determining ifcon
is congruent tothis
.
- Returns:
true
ifthis
is congruent tocon
modulo2^modExp
,false
otherwise.- Return type:
bool
See also
- 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 storedbase :
bigint
– The value to be raised to the power ofexp
before performing a modulo operation on.exp :
bigint
,int
, oruint
– The exponent to raisebase
to the power of prior to the modulo operation. Can be negative if the inverse (1/base
) modulomod
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 ofbase
raised toexp
.- Arguments:
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 integern
th root ofx
.- Arguments:
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 integern
th root ofx
. Stores the remainder inremain
.- Arguments:
See also
- proc sqrt(ref result: bigint, const ref x: bigint)¶
Sets
result
to the truncated integer square root ofx
.- Arguments:
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 ofx
. Stores the remainder inremain
.Warning
If
result
is also passed as theremain
argument, the program behavior is undefined.- Arguments:
See also
- proc bigint.isPerfectPower() : bool¶
Return
true
ifthis
is a perfect power, i.e., if there exist integersa
andb
withb > 1
, such thatthis = 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
ifthis
is a perfect power,false
otherwise.- Return type:
bool
See also
- proc bigint.isPerfectSquare() : bool¶
Return
true
ifthis
is a perfect square, i.e., if the square root ofthis
is an integer.Under this definition both
0
and1
are considered to be perfect squares.- Returns:
true
ifthis
is a perfect square,false
otherwise.- Return type:
bool
See also
- 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 theprimality
constants -isPrime
,maybePrime
, ornotPrime
.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 than4^(-reps)
. Reasonable values ofreps
are between 15 and 50.- Arguments:
reps :
int
– number of attempts before returningmaybePrime
if a definitive answer can’t be found before then.- Returns:
isPrime
,maybePrime
, ornotPrime
.- Return type:
See also
- 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 thanx
.Note
This is a probabilistic function and in an unlikely case may set
result
to a composite number.- Arguments:
See also
- 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 ofa
andb
- Arguments:
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 ofa
andb
, and sets
andt
to coefficients such thata*s + b*t == result
.Note
The result stored in
result
is always positive, even if one or both ofa
andb
are negative (or zero if both are zero).- Arguments:
result :
bigint
– Where the result is storeda :
bigint
– One of the numbers to compute the greatest common divisor ofb :
bigint
– One of the numbers to compute the greatest common divisor ofs :
bigint
– The returned coefficient that can be multiplied bya
.t :
bigint
– The returned coefficient that can be multiplied byb
.
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 ofa
andb
- Arguments:
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 ainvert()
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 thebigint
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 ofx
moduloy
- Arguments:
- 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
fromx
and store the result inresult
. Return the number of occurrences removed.- Arguments:
- Returns:
The number of occurrences of
fac
found inx
.- Return type:
uint
See also
- proc fac(ref result: bigint, a: integral)¶
Warning
fac is unstable and may change in the future
Set
result
to the factorial ofa
.- Arguments:
result :
bigint
– Where the result is storeda :
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 ofn
overk
.- Arguments:
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 then
th Fibonacci number.- Arguments:
result :
bigint
– return value that will contain the Fibonacci numbern :
integral
– which Fibonacci number to compute forresult
.
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 then
th Fibonacci number and setfnsub1
to then-1
th Fibonacci number.- Arguments:
See also
- proc lucNum(ref result: bigint, n: integral)¶
Warning
lucNum is unstable and may change in the future
Set
result
to then
th Lucas number.- Arguments:
result :
bigint
– return value that will contain the Lucas numbern :
integral
– which Lucas number to compute
See also
- proc lucNum2(ref result: bigint, ref fnsub1: bigint, n: integral)¶
Warning
lucNum2 is unstable and may change in the future
Set
result
to then
th Lucas number and setfnsub1
to then-1
th Lucas number.- Arguments:
See also
- proc bigint.popCount() : uint¶
Returns the number of
1
bits inthis
. Ifthis
is negative, the number of1
bits is infinite and the return value is the largest possiblemp_bitcnt_t
.- Returns:
The number of
1
bits inthis
- Return type:
uint
See also
- 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
andx
. Ifthis
andx
have different signs, the number of bits that differ is infinite and the return value is the largest possiblemp_bitcnt_t
.- Arguments:
x :
bigint
– value to comparethis
against- Returns:
The number of bits that differ
- Return type:
uint
See also
- proc bigint.findNext0(startBitIdx: integral) : uint¶
Returns the index of the first
0
bit found, starting fromstartBitIdx
and searching towards the more significant bits.If the bit at
startBitIdx
is1
, will returnstartBitIdx
.- Arguments:
startBitIdx :
integral
– The index of the first bit to start searching for a0
- Returns:
The index of the first
0
bit afterstartBitIdx
, 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 fromstartBitIdx
and searching towards the more significant bits.If the bit at
startBitIdx
is1
, will returnstartBitIdx
.- Arguments:
startBitIdx :
integral
– The index of the first bit to start searching for a1
- Returns:
The index of the first
1
bit afterstartBitIdx
, inclusive- Return type:
uint
See also
GMP.mpz_scan1
and mpz_scan1.
- proc ref bigint.setBit(idx: integral)¶
Set the bit at
idx
ofthis
.- 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
ofthis
.- 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
ofthis
. 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
ofthis
.- 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
- proc bigint.isEven() : bool¶
Returns
true
ifthis
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
ifthis
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 ofx
andy
.- Arguments:
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 ofx
andy
.- Arguments:
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 ofx
andy
.- Arguments:
See also
- 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
andy
toresult
(result = result + (x * y)
).- Arguments:
See also
- 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
andy
fromresult
(result = result - (x * y)
).- Arguments:
See also
- 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 inresult
.This is the same as performing a left bit shift of
x
byexp
bits.- Arguments:
See also
- proc neg(ref result: bigint, const ref x: bigint)¶
Sets
result
to the negation ofx
.See also
GMP.mpz_neg
amd mpz_neg.
- proc abs(ref result: bigint, const ref x: bigint)¶
Sets
result
to the absolute value ofx
.- Arguments:
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
bydenom
, forming a quotient and storing it inresult
.- Arguments:
result :
bigint
– Where the result is storednumer :
bigint
– The numerator of the division operation to be performeddenom :
bigint
,integral
– The denominator of the division operation to be performedrounding :
roundingMode
– The rounding style to use, seeroundingMode
for a description of what the rounding styles entail. Defaults tozero
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
bydenom
, forming a remainder and storing it inresult
. 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 storednumer :
bigint
– The numerator of the division operation to be performeddenom :
bigint
,integral
– The denominator of the division operation to be performedrounding :
roundingMode
– The rounding style to use, seeroundingMode
for a description of what the rounding styles entail. Defaults tozero
if unspecified
Warning
If the denominator is zero, the program behavior is undefined.
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
bydenom
, forming a quotient and storing it inresult
, and a remainder and storing it inremain
. The quotient and remainder will always satisfynumer = 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 theremain
argument, the program behavior is undefined.- Arguments:
result :
bigint
– Where the result is storedremain :
bigint
– Stores the remainder of the divisionnumer :
bigint
– The numerator of the division operation to be performeddenom :
bigint
,integral
– The denominator of the division operation to be performedrounding :
roundingMode
– The rounding style to use, seeroundingMode
for a description of what the rounding styles entail. Defaults tozero
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
by2^exp
, forming a quotient and storing it inresult
.This is the same as performing a right bit shift of
numer
byexp
bits whenrounding
isdown
.- Arguments:
result :
bigint
– Where the result is storednumer :
bigint
– The numerator of the division operation to be performedexp :
integral
– The exponent that 2 should be raised to before being used as the denominator of the division operation to be performedrounding :
roundingMode
– The rounding style to use, seeroundingMode
for a description of what the rounding styles entail. Defaults tozero
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
by2^exp
, forming a remainder and storing it inresult
.- Arguments:
result :
bigint
– Where the result is storednumer :
bigint
– The numerator of the division operation to be performedexp :
integral
– The exponent that 2 should be raised to before being used as the denominator of the division operation to be performedrounding :
roundingMode
– The rounding style to use, seeroundingMode
for a description of what the rounding styles entail. Defaults tozero
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 byn
bits inresult
. Negativen
will result in a right shift.
- proc shiftRight(ref result: bigint, const ref x: bigint, n: integral)¶
Stores
x
shifted right byn
bits inresult
. Negativen
will result in a left shift.
- 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:
Note
If
y
is auint
, then fewer conditionals will be evaluated at run time.
- proc mod(ref result: bigint, const ref x: bigint, y: integral) : int
See
mod
- proc bigint.cmp(const ref x: bigint) : int¶
Compares
this
andx
.- Arguments:
x :
bigint
,uint
,int
,real
– The number to compare against- Returns:
Returns a positive value if
this
is greater thanx
, a negative value ifthis
is less thanx
, 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 ofx
.- Arguments:
x :
bigint
,uint
,real
– The number to compare against- Returns:
Returns a positive value if
abs(this)
is greater thanabs(x)
, a negative value ifabs(this)
is less thanabs(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
andy
and store it inresult
.- Arguments:
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
andy
and store it inresult
.- Arguments:
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
andy
and store it inresult
.- Arguments:
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 inresult
.See also
GMP.mpz_com
and mpz_com.
- proc ref bigint.set(const ref x: bigint)¶
Assign
x
tothis
- 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
andx
- Arguments:
x :
bigint
– Number to be swapped
See also
GMP.mpz_swap
and mpz_swap.