Package big
import "big"
This package implements multi-precision arithmetic (big numbers). The following numeric types are supported:
- Int signed integers - Rat rational numbers
All methods on Int take the result as the receiver; if it is one of the operands it may be overwritten (and its memory reused). To enable chaining of operations, the result is also returned.
Package files
arith.go arith_decl.go int.go nat.go rat.gofunc GcdInt
func GcdInt(d, x, y, a, b *Int)
GcdInt sets d to the greatest common divisor of a and b, which must be positive numbers. If x and y are not nil, GcdInt sets x and y such that d = a*x + b*y. If either a or b is not positive, GcdInt sets d = x = y = 0.
func ProbablyPrime
func ProbablyPrime(z *Int, n int) bool
ProbablyPrime performs n Miller-Rabin tests to check whether z is prime. If it returns true, z is prime with probability 1 - 1/4^n. If it returns false, z is not prime.
type Int
An Int represents a signed multi-precision integer. The zero value for an Int represents the value 0.
type Int struct {
// contains unexported fields
}
func NewInt
func NewInt(x int64) *Int
NewInt allocates and returns a new Int set to x.
func (*Int) Abs
func (z *Int) Abs(x *Int) *Int
Abs sets z to |x| (the absolute value of x) and returns z.
func (*Int) Add
func (z *Int) Add(x, y *Int) *Int
Add sets z to the sum x+y and returns z.
func (*Int) And
func (z *Int) And(x, y *Int) *Int
And sets z = x & y and returns z.
func (*Int) AndNot
func (z *Int) AndNot(x, y *Int) *Int
AndNot sets z = x &^ y and returns z.
func (*Int) Binomial
func (z *Int) Binomial(n, k int64) *Int
Binomial sets z to the binomial coefficient of (n, k) and returns z.
func (*Int) BitLen
func (z *Int) BitLen() int
BitLen returns the length of the absolute value of z in bits. The bit length of 0 is 0.
func (*Int) Bytes
func (z *Int) Bytes() []byte
Bytes returns the absolute value of x as a big-endian byte array.
func (*Int) Cmp
func (x *Int) Cmp(y *Int) (r int)
Cmp compares x and y and returns:
-1 if x < y 0 if x == y +1 if x > y
func (*Int) Div
func (z *Int) Div(x, y *Int) *Int
Div sets z to the quotient x/y for y != 0 and returns z. If y == 0, a division-by-zero run-time panic occurs. See DivMod for more details.
func (*Int) DivMod
func (z *Int) DivMod(x, y, m *Int) (*Int, *Int)
DivMod sets z to the quotient x div y and m to the modulus x mod y and returns the pair (z, m) for y != 0. If y == 0, a division-by-zero run-time panic occurs.
DivMod implements Euclidean division and modulus (unlike Go):
q = x div y such that m = x - y*q with 0 <= m < |q|
(See Raymond T. Boute, “The Euclidean definition of the functions div and mod”. ACM Transactions on Programming Languages and Systems (TOPLAS), 14(2):127-144, New York, NY, USA, 4/1992. ACM press.)
func (*Int) Exp
func (z *Int) Exp(x, y, m *Int) *Int
Exp sets z = x**y mod m. If m is nil, z = x**y. See Knuth, volume 2, section 4.6.3.
func (*Int) Format
func (x *Int) Format(s fmt.State, ch int)
Format is a support routine for fmt.Formatter. It accepts the formats 'b' (binary), 'o' (octal), 'd' (decimal) and 'x' (hexadecimal).
func (*Int) Int64
func (x *Int) Int64() int64
Int64 returns the int64 representation of z. If z cannot be represented in an int64, the result is undefined.
func (*Int) Lsh
func (z *Int) Lsh(x *Int, n uint) *Int
Lsh sets z = x << n and returns z.
func (*Int) Mod
func (z *Int) Mod(x, y *Int) *Int
Mod sets z to the modulus x%y for y != 0 and returns z. If y == 0, a division-by-zero run-time panic occurs. See DivMod for more details.
func (*Int) ModInverse
func (z *Int) ModInverse(g, p *Int) *Int
ModInverse sets z to the multiplicative inverse of g in the group ℤ/pℤ (where p is a prime) and returns z.
func (*Int) Mul
func (z *Int) Mul(x, y *Int) *Int
Mul sets z to the product x*y and returns z.
func (*Int) MulRange
func (z *Int) MulRange(a, b int64) *Int
MulRange sets z to the product of all integers in the range [a, b] inclusively and returns z. If a > b (empty range), the result is 1.
func (*Int) Neg
func (z *Int) Neg(x *Int) *Int
Neg sets z to -x and returns z.
func (*Int) Not
func (z *Int) Not(x *Int) *Int
Not sets z = ^x and returns z.
func (*Int) Or
func (z *Int) Or(x, y *Int) *Int
Or sets z = x | y and returns z.
func (*Int) Quo
func (z *Int) Quo(x, y *Int) *Int
Quo sets z to the quotient x/y for y != 0 and returns z. If y == 0, a division-by-zero run-time panic occurs. See QuoRem for more details.
func (*Int) QuoRem
func (z *Int) QuoRem(x, y, r *Int) (*Int, *Int)
QuoRem sets z to the quotient x/y and r to the remainder x%y and returns the pair (z, r) for y != 0. If y == 0, a division-by-zero run-time panic occurs.
QuoRem implements T-division and modulus (like Go):
q = x/y with the result truncated to zero r = x - y*q
(See Daan Leijen, “Division and Modulus for Computer Scientists”.)
func (*Int) Rem
func (z *Int) Rem(x, y *Int) *Int
Rem sets z to the remainder x%y for y != 0 and returns z. If y == 0, a division-by-zero run-time panic occurs. See QuoRem for more details.
func (*Int) Rsh
func (z *Int) Rsh(x *Int, n uint) *Int
Rsh sets z = x >> n and returns z.
func (*Int) Set
func (z *Int) Set(x *Int) *Int
Set sets z to x and returns z.
func (*Int) SetBytes
func (z *Int) SetBytes(b []byte) *Int
SetBytes interprets b as the bytes of a big-endian, unsigned integer and sets z to that value.
func (*Int) SetInt64
func (z *Int) SetInt64(x int64) *Int
SetInt64 sets z to x and returns z.
func (*Int) SetString
func (z *Int) SetString(s string, base int) (*Int, bool)
SetString sets z to the value of s, interpreted in the given base, and returns z and a boolean indicating success. If SetString fails, the value of z is undefined.
If the base argument is 0, the string prefix determines the actual conversion base. A prefix of “0x” or “0X” selects base 16; the “0” prefix selects base 8, and a “0b” or “0B” prefix selects base 2. Otherwise the selected base is 10.
func (*Int) Sign
func (x *Int) Sign() int
Sign returns:
-1 if x < 0 0 if x == 0 +1 if x > 0
func (*Int) String
func (x *Int) String() string
func (*Int) Sub
func (z *Int) Sub(x, y *Int) *Int
Sub sets z to the difference x-y and returns z.
func (*Int) Xor
func (z *Int) Xor(x, y *Int) *Int
Xor sets z = x ^ y and returns z.
type Rat
A Rat represents a quotient a/b of arbitrary precision. The zero value for a Rat, 0/0, is not a legal Rat.
type Rat struct {
// contains unexported fields
}
func NewRat
func NewRat(a, b int64) *Rat
NewRat creates a new Rat with numerator a and denominator b.
func (*Rat) Abs
func (z *Rat) Abs(x *Rat) *Rat
Abs sets z to |x| (the absolute value of x) and returns z.
func (*Rat) Add
func (z *Rat) Add(x, y *Rat) *Rat
Add sets z to the sum x+y and returns z.
func (*Rat) Cmp
func (x *Rat) Cmp(y *Rat) (r int)
Cmp compares x and y and returns:
-1 if x < y 0 if x == y +1 if x > y
func (*Rat) Denom
func (z *Rat) Denom() *Int
Demom returns the denominator of z; it is always > 0. The result is a reference to z's denominator; it may change if a new value is assigned to z.
func (*Rat) FloatString
func (z *Rat) FloatString(prec int) string
FloatString returns a string representation of z in decimal form with prec digits of precision after the decimal point and the last digit rounded.
func (*Rat) IsInt
func (x *Rat) IsInt() bool
IsInt returns true if the denominator of x is 1.
func (*Rat) Mul
func (z *Rat) Mul(x, y *Rat) *Rat
Mul sets z to the product x*y and returns z.
func (*Rat) Neg
func (z *Rat) Neg(x *Rat) *Rat
Neg sets z to -x (by making a copy of x if necessary) and returns z.
func (*Rat) Num
func (z *Rat) Num() *Int
Num returns the numerator of z; it may be <= 0. The result is a reference to z's numerator; it may change if a new value is assigned to z.
func (*Rat) Quo
func (z *Rat) Quo(x, y *Rat) *Rat
Quo sets z to the quotient x/y and returns z. If y == 0, a division-by-zero run-time panic occurs.
func (*Rat) Set
func (z *Rat) Set(x *Rat) *Rat
Set sets z to x (by making a copy of x if necessary) and returns z.
func (*Rat) SetFrac
func (z *Rat) SetFrac(a, b *Int) *Rat
SetFrac sets z to a/b and returns z.
func (*Rat) SetFrac64
func (z *Rat) SetFrac64(a, b int64) *Rat
SetFrac64 sets z to a/b and returns z.
func (*Rat) SetInt
func (z *Rat) SetInt(x *Int) *Rat
SetInt sets z to x (by making a copy of x) and returns z.
func (*Rat) SetInt64
func (z *Rat) SetInt64(x int64) *Rat
SetInt64 sets z to x and returns z.
func (*Rat) SetString
func (z *Rat) SetString(s string) (*Rat, bool)
SetString sets z to the value of s and returns z and a boolean indicating success. s can be given as a fraction "a/b" or as a floating-point number optionally followed by an exponent. If the operation failed, the value of z is undefined.
func (*Rat) Sign
func (x *Rat) Sign() int
Sign returns:
-1 if x < 0 0 if x == 0 +1 if x > 0
func (*Rat) String
func (z *Rat) String() string
String returns a string representation of z in the form "a/b".
func (*Rat) Sub
func (z *Rat) Sub(x, y *Rat) *Rat
Sub sets z to the difference x-y and returns z.
type Word
type Word uintptr