...

Package big

import "math/big"
Overview
Index
Examples

Overview ▾

Package big implements multi-precision arithmetic (big numbers). The following numeric types are supported:

- Int	signed integers
- Rat	rational numbers

Methods are typically of the form:

func (z *Int) Op(x, y *Int) *Int	(similar for *Rat)

and implement operations z = x Op y with the result as 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. Methods returning a result other than *Int or *Rat take one of the operands as the receiver.

Index ▾

Constants
type Int
    func NewInt(x int64) *Int
    func (z *Int) Abs(x *Int) *Int
    func (z *Int) Add(x, y *Int) *Int
    func (z *Int) And(x, y *Int) *Int
    func (z *Int) AndNot(x, y *Int) *Int
    func (z *Int) Binomial(n, k int64) *Int
    func (x *Int) Bit(i int) uint
    func (x *Int) BitLen() int
    func (x *Int) Bits() []Word
    func (x *Int) Bytes() []byte
    func (x *Int) Cmp(y *Int) (r int)
    func (z *Int) Div(x, y *Int) *Int
    func (z *Int) DivMod(x, y, m *Int) (*Int, *Int)
    func (z *Int) Exp(x, y, m *Int) *Int
    func (x *Int) Format(s fmt.State, ch rune)
    func (z *Int) GCD(x, y, a, b *Int) *Int
    func (z *Int) GobDecode(buf []byte) error
    func (x *Int) GobEncode() ([]byte, error)
    func (x *Int) Int64() int64
    func (z *Int) Lsh(x *Int, n uint) *Int
    func (z *Int) MarshalJSON() ([]byte, error)
    func (z *Int) MarshalText() (text []byte, err error)
    func (z *Int) Mod(x, y *Int) *Int
    func (z *Int) ModInverse(g, n *Int) *Int
    func (z *Int) Mul(x, y *Int) *Int
    func (z *Int) MulRange(a, b int64) *Int
    func (z *Int) Neg(x *Int) *Int
    func (z *Int) Not(x *Int) *Int
    func (z *Int) Or(x, y *Int) *Int
    func (x *Int) ProbablyPrime(n int) bool
    func (z *Int) Quo(x, y *Int) *Int
    func (z *Int) QuoRem(x, y, r *Int) (*Int, *Int)
    func (z *Int) Rand(rnd *rand.Rand, n *Int) *Int
    func (z *Int) Rem(x, y *Int) *Int
    func (z *Int) Rsh(x *Int, n uint) *Int
    func (z *Int) Scan(s fmt.ScanState, ch rune) error
    func (z *Int) Set(x *Int) *Int
    func (z *Int) SetBit(x *Int, i int, b uint) *Int
    func (z *Int) SetBits(abs []Word) *Int
    func (z *Int) SetBytes(buf []byte) *Int
    func (z *Int) SetInt64(x int64) *Int
    func (z *Int) SetString(s string, base int) (*Int, bool)
    func (z *Int) SetUint64(x uint64) *Int
    func (x *Int) Sign() int
    func (x *Int) String() string
    func (z *Int) Sub(x, y *Int) *Int
    func (x *Int) Uint64() uint64
    func (z *Int) UnmarshalJSON(text []byte) error
    func (z *Int) UnmarshalText(text []byte) error
    func (z *Int) Xor(x, y *Int) *Int
type Rat
    func NewRat(a, b int64) *Rat
    func (z *Rat) Abs(x *Rat) *Rat
    func (z *Rat) Add(x, y *Rat) *Rat
    func (x *Rat) Cmp(y *Rat) int
    func (x *Rat) Denom() *Int
    func (x *Rat) Float32() (f float32, exact bool)
    func (x *Rat) Float64() (f float64, exact bool)
    func (x *Rat) FloatString(prec int) string
    func (z *Rat) GobDecode(buf []byte) error
    func (x *Rat) GobEncode() ([]byte, error)
    func (z *Rat) Inv(x *Rat) *Rat
    func (x *Rat) IsInt() bool
    func (r *Rat) MarshalText() (text []byte, err error)
    func (z *Rat) Mul(x, y *Rat) *Rat
    func (z *Rat) Neg(x *Rat) *Rat
    func (x *Rat) Num() *Int
    func (z *Rat) Quo(x, y *Rat) *Rat
    func (x *Rat) RatString() string
    func (z *Rat) Scan(s fmt.ScanState, ch rune) error
    func (z *Rat) Set(x *Rat) *Rat
    func (z *Rat) SetFloat64(f float64) *Rat
    func (z *Rat) SetFrac(a, b *Int) *Rat
    func (z *Rat) SetFrac64(a, b int64) *Rat
    func (z *Rat) SetInt(x *Int) *Rat
    func (z *Rat) SetInt64(x int64) *Rat
    func (z *Rat) SetString(s string) (*Rat, bool)
    func (x *Rat) Sign() int
    func (x *Rat) String() string
    func (z *Rat) Sub(x, y *Rat) *Rat
    func (r *Rat) UnmarshalText(text []byte) error
type Word

Package files

arith.go arith_decl.go int.go nat.go rat.go

Constants

const MaxBase = 'z' - 'a' + 10 + 1 // = hexValue('z') + 1

MaxBase is the largest number base accepted for string conversions.

type Int

type Int struct {
    // contains filtered or unexported fields
}

An Int represents a signed multi-precision integer. The zero value for an Int represents the value 0.

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

func (x *Int) Bit(i int) uint

Bit returns the value of the i'th bit of x. That is, it returns (x>>i)&1. The bit index i must be >= 0.

func (*Int) BitLen

func (x *Int) BitLen() int

BitLen returns the length of the absolute value of x in bits. The bit length of 0 is 0.

func (*Int) Bits

func (x *Int) Bits() []Word

Bits provides raw (unchecked but fast) access to x by returning its absolute value as a little-endian Word slice. The result and x share the same underlying array. Bits is intended to support implementation of missing low-level Int functionality outside this package; it should be avoided otherwise.

func (*Int) Bytes

func (x *Int) Bytes() []byte

Bytes returns the absolute value of x as a big-endian byte slice.

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. Div implements Euclidean division (unlike Go); 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.) See QuoRem for T-division and modulus (like Go).

func (*Int) Exp

func (z *Int) Exp(x, y, m *Int) *Int

Exp sets z = x**y mod |m| (i.e. the sign of m is ignored), and returns z. If y <= 0, the result is 1 mod |m|; if m == nil or m == 0, z = x**y. See Knuth, volume 2, section 4.6.3.

func (*Int) Format

func (x *Int) Format(s fmt.State, ch rune)

Format is a support routine for fmt.Formatter. It accepts the formats 'b' (binary), 'o' (octal), 'd' (decimal), 'x' (lowercase hexadecimal), and 'X' (uppercase hexadecimal). Also supported are the full suite of package fmt's format verbs for integral types, including '+', '-', and ' ' for sign control, '#' for leading zero in octal and for hexadecimal, a leading "0x" or "0X" for "%#x" and "%#X" respectively, specification of minimum digits precision, output field width, space or zero padding, and left or right justification.

func (*Int) GCD

func (z *Int) GCD(x, y, a, b *Int) *Int

GCD sets z to the greatest common divisor of a and b, which both must be > 0, and returns z. If x and y are not nil, GCD sets x and y such that z = a*x + b*y. If either a or b is <= 0, GCD sets z = x = y = 0.

func (*Int) GobDecode

func (z *Int) GobDecode(buf []byte) error

GobDecode implements the gob.GobDecoder interface.

func (*Int) GobEncode

func (x *Int) GobEncode() ([]byte, error)

GobEncode implements the gob.GobEncoder interface.

func (*Int) Int64

func (x *Int) Int64() int64

Int64 returns the int64 representation of x. If x 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) MarshalJSON

func (z *Int) MarshalJSON() ([]byte, error)

MarshalJSON implements the json.Marshaler interface.

func (*Int) MarshalText

func (z *Int) MarshalText() (text []byte, err error)

MarshalText implements the encoding.TextMarshaler interface.

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. Mod implements Euclidean modulus (unlike Go); see DivMod for more details.

func (*Int) ModInverse

func (z *Int) ModInverse(g, n *Int) *Int

ModInverse sets z to the multiplicative inverse of g in the ring ℤ/nℤ and returns z. If g and n are not relatively prime, the result is undefined.

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

func (x *Int) ProbablyPrime(n int) bool

ProbablyPrime performs n Miller-Rabin tests to check whether x is prime. If it returns true, x is prime with probability 1 - 1/4^n. If it returns false, x is not prime.

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. Quo implements truncated division (like Go); 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”.) See DivMod for Euclidean division and modulus (unlike Go).

func (*Int) Rand

func (z *Int) Rand(rnd *rand.Rand, n *Int) *Int

Rand sets z to a pseudo-random number in [0, n) and returns z.

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. Rem implements truncated modulus (like Go); 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) Scan

func (z *Int) Scan(s fmt.ScanState, ch rune) error

Scan is a support routine for fmt.Scanner; it sets z to the value of the scanned number. It accepts the formats 'b' (binary), 'o' (octal), 'd' (decimal), 'x' (lowercase hexadecimal), and 'X' (uppercase hexadecimal).

Example

Code:

// The Scan function is rarely used directly;
// the fmt package recognizes it as an implementation of fmt.Scanner.
i := new(big.Int)
_, err := fmt.Sscan("18446744073709551617", i)
if err != nil {
    log.Println("error scanning value:", err)
} else {
    fmt.Println(i)
}

Output:

18446744073709551617

func (*Int) Set

func (z *Int) Set(x *Int) *Int

Set sets z to x and returns z.

func (*Int) SetBit

func (z *Int) SetBit(x *Int, i int, b uint) *Int

SetBit sets z to x, with x's i'th bit set to b (0 or 1). That is, if b is 1 SetBit sets z = x | (1 << i); if b is 0 SetBit sets z = x &^ (1 << i). If b is not 0 or 1, SetBit will panic.

func (*Int) SetBits

func (z *Int) SetBits(abs []Word) *Int

SetBits provides raw (unchecked but fast) access to z by setting its value to abs, interpreted as a little-endian Word slice, and returning z. The result and abs share the same underlying array. SetBits is intended to support implementation of missing low-level Int functionality outside this package; it should be avoided otherwise.

func (*Int) SetBytes

func (z *Int) SetBytes(buf []byte) *Int

SetBytes interprets buf as the bytes of a big-endian unsigned integer, sets z to that value, and returns z.

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 but the returned value is nil.

The base argument must be 0 or a value from 2 through MaxBase. If the base 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.

Example

Code:

i := new(big.Int)
i.SetString("644", 8) // octal
fmt.Println(i)

Output:

420

func (*Int) SetUint64

func (z *Int) SetUint64(x uint64) *Int

SetUint64 sets z to x and returns z.

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

func (x *Int) Uint64() uint64

Uint64 returns the uint64 representation of x. If x cannot be represented in a uint64, the result is undefined.

func (*Int) UnmarshalJSON

func (z *Int) UnmarshalJSON(text []byte) error

UnmarshalJSON implements the json.Unmarshaler interface.

func (*Int) UnmarshalText

func (z *Int) UnmarshalText(text []byte) error

UnmarshalText implements the encoding.TextUnmarshaler interface.

func (*Int) Xor

func (z *Int) Xor(x, y *Int) *Int

Xor sets z = x ^ y and returns z.

type Rat

type Rat struct {
    // contains filtered or unexported fields
}

A Rat represents a quotient a/b of arbitrary precision. The zero value for a Rat represents the value 0.

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

Cmp compares x and y and returns:

-1 if x <  y
 0 if x == y
+1 if x >  y

func (*Rat) Denom

func (x *Rat) Denom() *Int

Denom returns the denominator of x; it is always > 0. The result is a reference to x's denominator; it may change if a new value is assigned to x, and vice versa.

func (*Rat) Float32

func (x *Rat) Float32() (f float32, exact bool)

Float32 returns the nearest float32 value for x and a bool indicating whether f represents x exactly. If the magnitude of x is too large to be represented by a float32, f is an infinity and exact is false. The sign of f always matches the sign of x, even if f == 0.

func (*Rat) Float64

func (x *Rat) Float64() (f float64, exact bool)

Float64 returns the nearest float64 value for x and a bool indicating whether f represents x exactly. If the magnitude of x is too large to be represented by a float64, f is an infinity and exact is false. The sign of f always matches the sign of x, even if f == 0.

func (*Rat) FloatString

func (x *Rat) FloatString(prec int) string

FloatString returns a string representation of x in decimal form with prec digits of precision after the decimal point and the last digit rounded.

func (*Rat) GobDecode

func (z *Rat) GobDecode(buf []byte) error

GobDecode implements the gob.GobDecoder interface.

func (*Rat) GobEncode

func (x *Rat) GobEncode() ([]byte, error)

GobEncode implements the gob.GobEncoder interface.

func (*Rat) Inv

func (z *Rat) Inv(x *Rat) *Rat

Inv sets z to 1/x and returns z.

func (*Rat) IsInt

func (x *Rat) IsInt() bool

IsInt returns true if the denominator of x is 1.

func (*Rat) MarshalText

func (r *Rat) MarshalText() (text []byte, err error)

MarshalText implements the encoding.TextMarshaler interface.

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 and returns z.

func (*Rat) Num

func (x *Rat) Num() *Int

Num returns the numerator of x; it may be <= 0. The result is a reference to x's numerator; it may change if a new value is assigned to x, and vice versa. The sign of the numerator corresponds to the sign of x.

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

func (x *Rat) RatString() string

RatString returns a string representation of x in the form "a/b" if b != 1, and in the form "a" if b == 1.

func (*Rat) Scan

func (z *Rat) Scan(s fmt.ScanState, ch rune) error

Scan is a support routine for fmt.Scanner. It accepts the formats 'e', 'E', 'f', 'F', 'g', 'G', and 'v'. All formats are equivalent.

Example

Code:

// The Scan function is rarely used directly;
// the fmt package recognizes it as an implementation of fmt.Scanner.
r := new(big.Rat)
_, err := fmt.Sscan("1.5000", r)
if err != nil {
    log.Println("error scanning value:", err)
} else {
    fmt.Println(r)
}

Output:

3/2

func (*Rat) Set

func (z *Rat) Set(x *Rat) *Rat

Set sets z to x (by making a copy of x) and returns z.

func (*Rat) SetFloat64

func (z *Rat) SetFloat64(f float64) *Rat

SetFloat64 sets z to exactly f and returns z. If f is not finite, SetFloat returns nil.

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 but the returned value is nil.

Example

Code:

r := new(big.Rat)
r.SetString("355/113")
fmt.Println(r.FloatString(3))

Output:

3.142

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 (x *Rat) String() string

String returns a string representation of x in the form "a/b" (even if b == 1).

func (*Rat) Sub

func (z *Rat) Sub(x, y *Rat) *Rat

Sub sets z to the difference x-y and returns z.

func (*Rat) UnmarshalText

func (r *Rat) UnmarshalText(text []byte) error

UnmarshalText implements the encoding.TextUnmarshaler interface.

type Word

type Word uintptr

A Word represents a single digit of a multi-precision unsigned integer.