Package bignum
import "bignum"
A package for arbitrary precision arithmethic. It implements the following numeric types:
- Natural unsigned integers - Integer signed integers - Rational rational numbers
This package has been designed for ease of use but the functions it provides are likely to be quite slow. It may be deprecated eventually. Use package big instead, if possible.
Package files
arith.go bignum.go integer.go rational.gofunc Div128
func Div128(x1, x0, y uint64) (q, r uint64)
q = (x1<<64 + x0)/y + r
func Iadd
func Iadd(z, x, y *Integer)
Iadd sets z to the sum x + y. z must exist and may be x or y.
func Iscale
func Iscale(z *Integer, d int64)
Nscale sets *z to the scaled value (*z) * d.
func Isub
func Isub(z, x, y *Integer)
func Mul128
func Mul128(x, y uint64) (z1, z0 uint64)
z1<<64 + z0 = x*y
func MulAdd128
func MulAdd128(x, y, c uint64) (z1, z0 uint64)
z1<<64 + z0 = x*y + c
func Nadd
func Nadd(zp *Natural, x, y Natural)
Nadd sets *zp to the sum x + y. *zp may be x or y.
func Nscale
func Nscale(z *Natural, d uint64)
Nscale sets *z to the scaled value (*z) * d.
func Nsub
func Nsub(zp *Natural, x, y Natural)
Nsub sets *zp to the difference x - y for x >= y. If x < y, an underflow run-time error occurs (use Cmp to test if x >= y). *zp may be x or y.
type Integer
Integer represents a signed integer value of arbitrary precision.
type Integer struct {
// contains unexported fields
}
func Int
func Int(x int64) *Integer
Int creates a small integer with value x.
func IntFromString
func IntFromString(s string, base uint) (*Integer, uint, int)
IntFromString returns the integer corresponding to the longest possible prefix of s representing an integer in a given conversion base, the actual conversion base used, and the prefix length. The syntax of integers follows the syntax of signed integer literals in Go.
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. Otherwise the selected base is 10.
func MakeInt
func MakeInt(sign bool, mant Natural) *Integer
MakeInt makes an integer given a sign and a mantissa. The number is positive (>= 0) if sign is false or the mantissa is zero; it is negative otherwise.
func (*Integer) Abs
func (x *Integer) Abs() Natural
Abs returns the absolute value of x.
func (*Integer) Add
func (x *Integer) Add(y *Integer) *Integer
Add returns the sum x + y.
func (*Integer) And
func (x *Integer) And(y *Integer) *Integer
And returns the “bitwise and” x & y for the 2's-complement representation of x and y.
func (*Integer) AndNot
func (x *Integer) AndNot(y *Integer) *Integer
AndNot returns the “bitwise clear” x &^ y for the 2's-complement representation of x and y.
func (*Integer) Cmp
func (x *Integer) Cmp(y *Integer) int
Cmp compares x and y. The result is an int value that is
< 0 if x < y == 0 if x == y > 0 if x > y
func (*Integer) Div
func (x *Integer) Div(y *Integer) *Integer
Div returns the quotient q = x / y for y != 0. If y == 0, a division-by-zero run-time error occurs.
Div and Mod implement Euclidian division and modulus:
q = x.Div(y) r = x.Mod(y) with: 0 <= r < |q| and: y = x*q + r
(Raymond T. Boute, “The Euclidian 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 (*Integer) DivMod
func (x *Integer) DivMod(y *Integer) (*Integer, *Integer)
DivMod returns the pair (x.Div(y), x.Mod(y)).
func (*Integer) Format
func (x *Integer) Format(h fmt.State, c int)
Format is a support routine for fmt.Formatter. It accepts the formats 'b' (binary), 'o' (octal), and 'x' (hexadecimal).
func (*Integer) IsEven
func (x *Integer) IsEven() bool
IsEven returns true iff x is divisible by 2.
func (*Integer) IsNeg
func (x *Integer) IsNeg() bool
IsNeg returns true iff x < 0.
func (*Integer) IsOdd
func (x *Integer) IsOdd() bool
IsOdd returns true iff x is not divisible by 2.
func (*Integer) IsPos
func (x *Integer) IsPos() bool
IsPos returns true iff x >= 0.
func (*Integer) IsZero
func (x *Integer) IsZero() bool
IsZero returns true iff x == 0.
func (*Integer) Mod
func (x *Integer) Mod(y *Integer) *Integer
Mod returns the modulus r of the division x / y for y != 0, with r = x - y*x.Div(y). r is always positive. If y == 0, a division-by-zero run-time error occurs.
func (*Integer) Mul
func (x *Integer) Mul(y *Integer) *Integer
Mul returns the product x * y.
func (*Integer) Mul1
func (x *Integer) Mul1(d int64) *Integer
Mul1 returns the product x * d.
func (*Integer) MulNat
func (x *Integer) MulNat(y Natural) *Integer
MulNat returns the product x * y, where y is a (unsigned) natural number.
func (*Integer) Neg
func (x *Integer) Neg() *Integer
Neg returns the negated value of x.
func (*Integer) Not
func (x *Integer) Not() *Integer
Not returns the “bitwise not” ^x for the 2's-complement representation of x.
func (*Integer) Or
func (x *Integer) Or(y *Integer) *Integer
Or returns the “bitwise or” x | y for the 2's-complement representation of x and y.
func (*Integer) Quo
func (x *Integer) Quo(y *Integer) *Integer
Quo returns the quotient q = x / y for y != 0. If y == 0, a division-by-zero run-time error occurs.
Quo and Rem implement T-division and modulus (like C99):
q = x.Quo(y) = trunc(x/y) (truncation towards zero) r = x.Rem(y) = x - y*q
(Daan Leijen, “Division and Modulus for Computer Scientists”.)
func (*Integer) QuoRem
func (x *Integer) QuoRem(y *Integer) (*Integer, *Integer)
QuoRem returns the pair (x.Quo(y), x.Rem(y)) for y != 0. If y == 0, a division-by-zero run-time error occurs.
func (*Integer) Rem
func (x *Integer) Rem(y *Integer) *Integer
Rem returns the remainder r of the division x / y for y != 0, with r = x - y*x.Quo(y). Unless r is zero, its sign corresponds to the sign of x. If y == 0, a division-by-zero run-time error occurs.
func (*Integer) Shl
func (x *Integer) Shl(s uint) *Integer
Shl implements “shift left” x << s. It returns x * 2^s.
func (*Integer) Shr
func (x *Integer) Shr(s uint) *Integer
Shr implements “shift right” x >> s. It returns x / 2^s.
func (*Integer) String
func (x *Integer) String() string
String converts x to its decimal string representation. x.String() is the same as x.ToString(10).
func (*Integer) Sub
func (x *Integer) Sub(y *Integer) *Integer
Sub returns the difference x - y.
func (*Integer) ToString
func (x *Integer) ToString(base uint) string
ToString converts x to a string for a given base, with 2 <= base <= 16.
func (*Integer) Value
func (x *Integer) Value() int64
Value returns the value of x, if x fits into an int64; otherwise the result is undefined.
func (*Integer) Xor
func (x *Integer) Xor(y *Integer) *Integer
Xor returns the “bitwise xor” x | y for the 2's-complement representation of x and y.
type Natural
Natural represents an unsigned integer value of arbitrary precision.
type Natural []digit
func Binomial
func Binomial(n, k uint) Natural
Binomial computes the binomial coefficient of (n, k).
func Fact
func Fact(n uint) Natural
Fact computes the factorial of n (Fact(n) == MulRange(2, n)).
func MulRange
func MulRange(a, b uint) Natural
MulRange computes the product of all the unsigned integers in the range [a, b] inclusively.
func Nat
func Nat(x uint64) Natural
Nat creates a small natural number with value x.
func NatFromString
func NatFromString(s string, base uint) (Natural, uint, int)
NatFromString returns the natural number corresponding to the longest possible prefix of s representing a natural number in a given conversion base, the actual conversion base used, and the prefix length. The syntax of natural numbers follows the syntax of unsigned integer literals in Go.
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. Otherwise the selected base is 10.
func (Natural) Add
func (x Natural) Add(y Natural) Natural
Add returns the sum z = x + y.
func (Natural) And
func (x Natural) And(y Natural) Natural
And returns the “bitwise and” x & y for the 2's-complement representation of x and y.
func (Natural) AndNot
func (x Natural) AndNot(y Natural) Natural
AndNot returns the “bitwise clear” x &^ y for the 2's-complement representation of x and y.
func (Natural) Cmp
func (x Natural) Cmp(y Natural) int
Cmp compares x and y. The result is an int value
< 0 if x < y == 0 if x == y > 0 if x > y
func (Natural) Div
func (x Natural) Div(y Natural) Natural
Div returns the quotient q = x / y for y > 0, with x = y*q + r and 0 <= r < y. If y == 0, a division-by-zero run-time error occurs.
func (Natural) DivMod
func (x Natural) DivMod(y Natural) (Natural, Natural)
DivMod returns the pair (x.Div(y), x.Mod(y)) for y > 0. If y == 0, a division-by-zero run-time error occurs.
func (Natural) Format
func (x Natural) Format(h fmt.State, c int)
Format is a support routine for fmt.Formatter. It accepts the formats 'b' (binary), 'o' (octal), and 'x' (hexadecimal).
func (Natural) Gcd
func (x Natural) Gcd(y Natural) Natural
Gcd computes the gcd of x and y.
func (Natural) IsEven
func (x Natural) IsEven() bool
IsEven returns true iff x is divisible by 2.
func (Natural) IsOdd
func (x Natural) IsOdd() bool
IsOdd returns true iff x is not divisible by 2.
func (Natural) IsZero
func (x Natural) IsZero() bool
IsZero returns true iff x == 0.
func (Natural) Log2
func (x Natural) Log2() uint
Log2 computes the binary logarithm of x for x > 0. The result is the integer n for which 2^n <= x < 2^(n+1). If x == 0 a run-time error occurs.
func (Natural) Mod
func (x Natural) Mod(y Natural) Natural
Mod returns the modulus r of the division x / y for y > 0, with x = y*q + r and 0 <= r < y. If y == 0, a division-by-zero run-time error occurs.
func (Natural) Mul
func (x Natural) Mul(y Natural) Natural
Mul returns the product x * y.
func (Natural) Mul1
func (x Natural) Mul1(d uint64) Natural
Mul1 returns the product x * d.
func (Natural) Or
func (x Natural) Or(y Natural) Natural
Or returns the “bitwise or” x | y for the 2's-complement representation of x and y.
func (Natural) Pop
func (x Natural) Pop() uint
Pop computes the “population count” of (the number of 1 bits in) x.
func (Natural) Pow
func (xp Natural) Pow(n uint) Natural
Pow computes x to the power of n.
func (Natural) Shl
func (x Natural) Shl(s uint) Natural
Shl implements “shift left” x << s. It returns x * 2^s.
func (Natural) Shr
func (x Natural) Shr(s uint) Natural
Shr implements “shift right” x >> s. It returns x / 2^s.
func (Natural) String
func (x Natural) String() string
String converts x to its decimal string representation. x.String() is the same as x.ToString(10).
func (Natural) Sub
func (x Natural) Sub(y Natural) Natural
Sub returns the difference x - y for x >= y. If x < y, an underflow run-time error occurs (use Cmp to test if x >= y).
func (Natural) ToString
func (x Natural) ToString(base uint) string
ToString converts x to a string for a given base, with 2 <= base <= 16.
func (Natural) Value
func (x Natural) Value() uint64
Value returns the lowest 64bits of x.
func (Natural) Xor
func (x Natural) Xor(y Natural) Natural
Xor returns the “bitwise exclusive or” x ^ y for the 2's-complement representation of x and y.
type Rational
Rational represents a quotient a/b of arbitrary precision.
type Rational struct {
// contains unexported fields
}
func MakeRat
func MakeRat(a *Integer, b Natural) *Rational
MakeRat makes a rational number given a numerator a and a denominator b.
func Rat
func Rat(a0 int64, b0 int64) *Rational
Rat creates a small rational number with value a0/b0.
func RatFromString
func RatFromString(s string, base uint) (*Rational, uint, int)
RatFromString returns the rational number corresponding to the longest possible prefix of s representing a rational number in a given conversion base, the actual conversion base used, and the prefix length. The syntax of a rational number is:
rational = mantissa [exponent] .
mantissa = integer ('/' natural | '.' natural) .
exponent = ('e'|'E') integer .
If the base argument is 0, the string prefix determines the actual conversion base for the mantissa. A prefix of “0x” or “0X” selects base 16; the “0” prefix selects base 8. Otherwise the selected base is 10. If the mantissa is represented via a division, both the numerator and denominator may have different base prefixes; in that case the base of of the numerator is returned. If the mantissa contains a decimal point, the base for the fractional part is the same as for the part before the decimal point and the fractional part does not accept a base prefix. The base for the exponent is always 10.
func (*Rational) Add
func (x *Rational) Add(y *Rational) *Rational
Add returns the sum x + y.
func (*Rational) Cmp
func (x *Rational) Cmp(y *Rational) int
Cmp compares x and y. The result is an int value
< 0 if x < y == 0 if x == y > 0 if x > y
func (*Rational) Format
func (x *Rational) Format(h fmt.State, c int)
Format is a support routine for fmt.Formatter. It accepts the formats 'b' (binary), 'o' (octal), and 'x' (hexadecimal).
func (*Rational) IsInt
func (x *Rational) IsInt() bool
IsInt returns true iff x can be written with a denominator 1 in the form x == x'/1; i.e., if x is an integer value.
func (*Rational) IsNeg
func (x *Rational) IsNeg() bool
IsNeg returns true iff x < 0.
func (*Rational) IsPos
func (x *Rational) IsPos() bool
IsPos returns true iff x > 0.
func (*Rational) IsZero
func (x *Rational) IsZero() bool
IsZero returns true iff x == 0.
func (*Rational) Mul
func (x *Rational) Mul(y *Rational) *Rational
Mul returns the product x * y.
func (*Rational) Neg
func (x *Rational) Neg() *Rational
Neg returns the negated value of x.
func (*Rational) Quo
func (x *Rational) Quo(y *Rational) *Rational
Quo returns the quotient x / y for y != 0. If y == 0, a division-by-zero run-time error occurs.
func (*Rational) String
func (x *Rational) String() string
String converts x to its decimal string representation. x.String() is the same as x.ToString(10).
func (*Rational) Sub
func (x *Rational) Sub(y *Rational) *Rational
Sub returns the difference x - y.
func (*Rational) ToString
func (x *Rational) ToString(base uint) string
ToString converts x to a string for a given base, with 2 <= base <= 16. The string representation is of the form "n" if x is an integer; otherwise it is of form "n/d".
func (*Rational) Value
func (x *Rational) Value() (numerator *Integer, denominator Natural)
Value returns the numerator and denominator of x.