Black Lives Matter. Support the Equal Justice Initiative.

Package big

import "math/big"
Overview
Index
Examples

Overview ▾

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

Int    signed integers
Rat    rational numbers
Float  floating-point numbers

The zero value for an Int, Rat, or Float correspond to 0. Thus, new values can be declared in the usual ways and denote 0 without further initialization:

var x Int        // &x is an *Int of value 0
var r = &Rat{}   // r is a *Rat of value 0
y := new(Float)  // y is a *Float of value 0

Alternatively, new values can be allocated and initialized with factory functions of the form:

func NewT(v V) *T

For instance, NewInt(x) returns an *Int set to the value of the int64 argument x, NewRat(a, b) returns a *Rat set to the fraction a/b where a and b are int64 values, and NewFloat(f) returns a *Float initialized to the float64 argument f. More flexibility is provided with explicit setters, for instance:

var z1 Int
z1.SetUint64(123)                 // z1 := 123
z2 := new(Rat).SetFloat64(1.25)   // z2 := 5/4
z3 := new(Float).SetInt(z1)       // z3 := 123.0

Setters, numeric operations and predicates are represented as methods of the form:

func (z *T) SetV(v V) *T          // z = v
func (z *T) Unary(x *T) *T        // z = unary x
func (z *T) Binary(x, y *T) *T    // z = x binary y
func (x *T) Pred() P              // p = pred(x)

with T one of Int, Rat, or Float. For unary and binary operations, the result is the receiver (usually named z in that case; see below); if it is one of the operands x or y it may be safely overwritten (and its memory reused).

Arithmetic expressions are typically written as a sequence of individual method calls, with each call corresponding to an operation. The receiver denotes the result and the method arguments are the operation's operands. For instance, given three *Int values a, b and c, the invocation

c.Add(a, b)

computes the sum a + b and stores the result in c, overwriting whatever value was held in c before. Unless specified otherwise, operations permit aliasing of parameters, so it is perfectly ok to write

sum.Add(sum, x)

to accumulate values x in a sum.

(By always passing in a result value via the receiver, memory use can be much better controlled. Instead of having to allocate new memory for each result, an operation can reuse the space allocated for the result value, and overwrite that value with the new result in the process.)

Notational convention: Incoming method parameters (including the receiver) are named consistently in the API to clarify their use. Incoming operands are usually named x, y, a, b, and so on, but never z. A parameter specifying the result is named z (typically the receiver).

For instance, the arguments for (*Int).Add are named x and y, and because the receiver specifies the result destination, it is called z:

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

Methods of this form typically return the incoming receiver as well, to enable simple call chaining.

Methods which don't require a result value to be passed in (for instance, Int.Sign), simply return the result. In this case, the receiver is typically the first operand, named x:

func (x *Int) Sign() int

Various methods support conversions between strings and corresponding numeric values, and vice versa: *Int, *Rat, and *Float values implement the Stringer interface for a (default) string representation of the value, but also provide SetString methods to initialize a value from a string in a variety of supported formats (see the respective SetString documentation).

Finally, *Int, *Rat, and *Float satisfy the fmt package's Scanner interface for scanning and (except for *Rat) the Formatter interface for formatted printing.

Example (EConvergents)

This example demonstrates how to use big.Rat to compute the first 15 terms in the sequence of rational convergents for the constant e (base of natural logarithm).

2/1           = 2.00000000
3/1           = 3.00000000
8/3           = 2.66666667
11/4          = 2.75000000
19/7          = 2.71428571
87/32         = 2.71875000
106/39        = 2.71794872
193/71        = 2.71830986
1264/465      = 2.71827957
1457/536      = 2.71828358
2721/1001     = 2.71828172
23225/8544    = 2.71828184
25946/9545    = 2.71828182
49171/18089   = 2.71828183
517656/190435 = 2.71828183

Example (Fibonacci)

This example demonstrates how to use big.Int to compute the smallest Fibonacci number with 100 decimal digits and to test whether it is prime.

1344719667586153181419716641724567886890850696275767987106294472017884974410332069524504824747437757
false

Example (Sqrt2)

This example shows how to use big.Float to compute the square root of 2 with a precision of 200 bits, and how to print the result as a decimal number.

sqrt(2) = 1.41421356237309504880168872420969807856967187537695
error = 0.000000e+00

Index ▾

Constants
Variables
func Jacobi(x, y *Int) int
func ParseFloat(s string, base int, prec uint, mode RoundingMode) (f *Float, b int, err error)
func addAt(z, x nat, i int)
func alias(x, y nat) bool
func appendZeros(buf []byte, n int) []byte
func basicMul(z, x, y nat)
func basicSqr(z, x nat)
func euclidUpdate(A, B, Ua, Ub, q, r, s, t *Int, extended bool)
func fmtE(buf []byte, fmt byte, prec int, d decimal) []byte
func fmtF(buf []byte, prec int, d decimal) []byte
func fnorm(m nat) int64
func greaterThan(x1, x2, y1, y2 Word) bool
func karatsuba(z, x, y nat)
func karatsubaAdd(z, x nat, n int)
func karatsubaLen(n, threshold int) int
func karatsubaSqr(z, x nat)
func karatsubaSub(z, x nat, n int)
func lehmerUpdate(A, B, q, r, s, t *Int, u0, u1, v0, v1 Word, even bool)
func low32(x nat) uint32
func low64(x nat) uint64
func max(x, y int) int
func maxPow(b Word) (p Word, n int)
func min(x, y int) int
func msb32(x nat) uint32
func msb64(x nat) uint64
func nlz(x Word) uint
func putNat(x *nat)
func quotToFloat32(a, b nat) (f float32, exact bool)
func quotToFloat64(a, b nat) (f float64, exact bool)
func ratTok(ch rune) bool
func roundShortest(d *decimal, x *Float)
func same(x, y nat) bool
func scanExponent(r io.ByteScanner, base2ok, sepOk bool) (exp int64, base int, err error)
func scanSign(r io.ByteScanner) (neg bool, err error)
func shouldRoundUp(x *decimal, n int) bool
func shr(x *decimal, s uint)
func trim(x *decimal)
func umax32(x, y uint32) uint32
func validateBinaryOperands(x, y *Float)
func writeMultiple(s fmt.State, text string, count int)
type Accuracy
    func makeAcc(above bool) Accuracy
    func (i Accuracy) String() string
type ErrNaN
    func (err ErrNaN) Error() string
type Float
    func NewFloat(x float64) *Float
    func newFloat(prec2 uint32) *Float
    func three() *Float
    func (z *Float) Abs(x *Float) *Float
    func (x *Float) Acc() Accuracy
    func (z *Float) Add(x, y *Float) *Float
    func (x *Float) Append(buf []byte, fmt byte, prec int) []byte
    func (x *Float) Cmp(y *Float) int
    func (z *Float) Copy(x *Float) *Float
    func (x *Float) Float32() (float32, Accuracy)
    func (x *Float) Float64() (float64, Accuracy)
    func (x *Float) Format(s fmt.State, format rune)
    func (z *Float) GobDecode(buf []byte) error
    func (x *Float) GobEncode() ([]byte, error)
    func (x *Float) Int(z *Int) (*Int, Accuracy)
    func (x *Float) Int64() (int64, Accuracy)
    func (x *Float) IsInf() bool
    func (x *Float) IsInt() bool
    func (x *Float) MantExp(mant *Float) (exp int)
    func (x *Float) MarshalText() (text []byte, err error)
    func (x *Float) MinPrec() uint
    func (x *Float) Mode() RoundingMode
    func (z *Float) Mul(x, y *Float) *Float
    func (z *Float) Neg(x *Float) *Float
    func (z *Float) Parse(s string, base int) (f *Float, b int, err error)
    func (x *Float) Prec() uint
    func (z *Float) Quo(x, y *Float) *Float
    func (x *Float) Rat(z *Rat) (*Rat, Accuracy)
    func (z *Float) Scan(s fmt.ScanState, ch rune) error
    func (z *Float) Set(x *Float) *Float
    func (z *Float) SetFloat64(x float64) *Float
    func (z *Float) SetInf(signbit bool) *Float
    func (z *Float) SetInt(x *Int) *Float
    func (z *Float) SetInt64(x int64) *Float
    func (z *Float) SetMantExp(mant *Float, exp int) *Float
    func (z *Float) SetMode(mode RoundingMode) *Float
    func (z *Float) SetPrec(prec uint) *Float
    func (z *Float) SetRat(x *Rat) *Float
    func (z *Float) SetString(s string) (*Float, bool)
    func (z *Float) SetUint64(x uint64) *Float
    func (x *Float) Sign() int
    func (x *Float) Signbit() bool
    func (z *Float) Sqrt(x *Float) *Float
    func (x *Float) String() string
    func (z *Float) Sub(x, y *Float) *Float
    func (x *Float) Text(format byte, prec int) string
    func (x *Float) Uint64() (uint64, Accuracy)
    func (z *Float) UnmarshalText(text []byte) error
    func (x *Float) fmtB(buf []byte) []byte
    func (x *Float) fmtP(buf []byte) []byte
    func (x *Float) fmtX(buf []byte, prec int) []byte
    func (x *Float) ord() int
    func (z *Float) pow5(n uint64) *Float
    func (z *Float) round(sbit uint)
    func (z *Float) scan(r io.ByteScanner, base int) (f *Float, b int, err error)
    func (z *Float) setBits64(neg bool, x uint64) *Float
    func (z *Float) setExpAndRound(exp int64, sbit uint)
    func (z *Float) sqrtInverse(x *Float)
    func (z *Float) uadd(x, y *Float)
    func (x *Float) ucmp(y *Float) int
    func (z *Float) umul(x, y *Float)
    func (z *Float) uquo(x, y *Float)
    func (z *Float) usub(x, y *Float)
    func (x *Float) validate()
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 (x *Int) Append(buf []byte, base int) []byte
    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 (x *Int) CmpAbs(y *Int) 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) FillBytes(buf []byte) []byte
    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 (x *Int) IsInt64() bool
    func (x *Int) IsUint64() bool
    func (z *Int) Lsh(x *Int, n uint) *Int
    func (x *Int) MarshalJSON() ([]byte, error)
    func (x *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) ModSqrt(x, p *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 (z *Int) Sqrt(x *Int) *Int
    func (x *Int) String() string
    func (z *Int) Sub(x, y *Int) *Int
    func (x *Int) Text(base int) string
    func (x *Int) TrailingZeroBits() uint
    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
    func (z *Int) lehmerGCD(x, y, a, b *Int) *Int
    func (z *Int) modSqrt3Mod4Prime(x, p *Int) *Int
    func (z *Int) modSqrt5Mod8Prime(x, p *Int) *Int
    func (z *Int) modSqrtTonelliShanks(x, p *Int) *Int
    func (z *Int) scaleDenom(x *Int, f nat)
    func (z *Int) scan(r io.ByteScanner, base int) (*Int, int, error)
    func (z *Int) setFromScanner(r io.ByteScanner, base int) (*Int, bool)
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 (x *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 (z *Rat) SetUint64(x uint64) *Rat
    func (x *Rat) Sign() int
    func (x *Rat) String() string
    func (z *Rat) Sub(x, y *Rat) *Rat
    func (z *Rat) UnmarshalText(text []byte) error
    func (x *Rat) marshal() []byte
    func (z *Rat) norm() *Rat
type RoundingMode
    func (i RoundingMode) String() string
type Word
    func addMulVVW(z, x []Word, y Word) (c Word)
    func addMulVVW_g(z, x []Word, y Word) (c Word)
    func addVV(z, x, y []Word) (c Word)
    func addVV_g(z, x, y []Word) (c Word)
    func addVW(z, x []Word, y Word) (c Word)
    func addVW_g(z, x []Word, y Word) (c Word)
    func addVWlarge(z, x []Word, y Word) (c Word)
    func bigEndianWord(buf []byte) Word
    func divWVW(z []Word, xn Word, x []Word, y Word) (r Word)
    func divWVW_g(z []Word, xn Word, x []Word, y Word) (r Word)
    func divWW(x1, x0, y Word) (q, r Word)
    func divWW_g(u1, u0, v Word) (q, r Word)
    func lehmerSimulate(A, B *Int) (u0, u1, v0, v1 Word, even bool)
    func mulAddVWW(z, x []Word, y, r Word) (c Word)
    func mulAddVWW_g(z, x []Word, y, r Word) (c Word)
    func mulAddWWW_g(x, y, c Word) (z1, z0 Word)
    func mulWW(x, y Word) (z1, z0 Word)
    func mulWW_g(x, y Word) (z1, z0 Word)
    func pow(x Word, n int) (p Word)
    func shlVU(z, x []Word, s uint) (c Word)
    func shlVU_g(z, x []Word, s uint) (c Word)
    func shrVU(z, x []Word, s uint) (c Word)
    func shrVU_g(z, x []Word, s uint) (c Word)
    func subVV(z, x, y []Word) (c Word)
    func subVV_g(z, x, y []Word) (c Word)
    func subVW(z, x []Word, y Word) (c Word)
    func subVW_g(z, x []Word, y Word) (c Word)
    func subVWlarge(z, x []Word, y Word) (c Word)
type byteReader
    func (r byteReader) ReadByte() (byte, error)
    func (r byteReader) UnreadByte() error
type decimal
    func (x *decimal) String() string
    func (d *decimal) at(i int) byte
    func (x *decimal) init(m nat, shift int)
    func (x *decimal) round(n int)
    func (x *decimal) roundDown(n int)
    func (x *decimal) roundUp(n int)
type divisor
    func divisors(m int, b Word, ndigits int, bb Word) []divisor
type form
type nat
    func getNat(n int) *nat
    func mulDenom(z, x, y nat) nat
    func (z nat) add(x, y nat) nat
    func (z nat) and(x, y nat) nat
    func (z nat) andNot(x, y nat) nat
    func (x nat) bit(i uint) uint
    func (x nat) bitLen() int
    func (z nat) bytes(buf []byte) (i int)
    func (z nat) clear()
    func (x nat) cmp(y nat) (r int)
    func (q nat) convertWords(s []byte, b Word, ndigits int, bb Word, table []divisor)
    func (z nat) div(z2, u, v nat) (q, r nat)
    func (q nat) divBasic(u, v nat)
    func (z nat) divLarge(u, uIn, vIn nat) (q, r nat)
    func (z nat) divRecursive(u, v nat)
    func (z nat) divRecursiveStep(u, v nat, depth int, tmp *nat, temps []*nat)
    func (z nat) divW(x nat, y Word) (q nat, r Word)
    func (z nat) expNN(x, y, m nat) nat
    func (z nat) expNNMontgomery(x, y, m nat) nat
    func (z nat) expNNWindowed(x, y, m nat) nat
    func (z nat) expWW(x, y Word) nat
    func (x nat) itoa(neg bool, base int) []byte
    func (z nat) make(n int) nat
    func (x nat) modW(d Word) (r Word)
    func (z nat) montgomery(x, y, m nat, k Word, n int) nat
    func (z nat) mul(x, y nat) nat
    func (z nat) mulAddWW(x nat, y, r Word) nat
    func (z nat) mulRange(a, b uint64) nat
    func (z nat) norm() nat
    func (z nat) or(x, y nat) nat
    func (n nat) probablyPrimeLucas() bool
    func (n nat) probablyPrimeMillerRabin(reps int, force2 bool) bool
    func (z nat) random(rand *rand.Rand, limit nat, n int) nat
    func (z nat) scan(r io.ByteScanner, base int, fracOk bool) (res nat, b, count int, err error)
    func (z nat) set(x nat) nat
    func (z nat) setBit(x nat, i uint, b uint) nat
    func (z nat) setBytes(buf []byte) nat
    func (z nat) setUint64(x uint64) nat
    func (z nat) setWord(x Word) nat
    func (z nat) shl(x nat, s uint) nat
    func (z nat) shr(x nat, s uint) nat
    func (z nat) sqr(x nat) nat
    func (z nat) sqrt(x nat) nat
    func (x nat) sticky(i uint) uint
    func (z nat) sub(x, y nat) nat
    func (x nat) trailingZeroBits() uint
    func (x nat) utoa(base int) []byte
    func (z nat) xor(x, y nat) nat

Package files

accuracy_string.go arith.go arith_amd64.go arith_decl.go decimal.go doc.go float.go floatconv.go floatmarsh.go ftoa.go int.go intconv.go intmarsh.go nat.go natconv.go prime.go rat.go ratconv.go ratmarsh.go roundingmode_string.go sqrt.go

Constants

const (
    _S = _W / 8 // word size in bytes

    _W = bits.UintSize // word size in bits
    _B = 1 << _W       // digit base
    _M = _B - 1        // digit mask
)

Exponent and precision limits.

const (
    MaxExp  = math.MaxInt32  // largest supported exponent
    MinExp  = math.MinInt32  // smallest supported exponent
    MaxPrec = math.MaxUint32 // largest (theoretically) supported precision; likely memory-limited
)

MaxBase is the largest number base accepted for string conversions.

const MaxBase = 10 + ('z' - 'a' + 1) + ('Z' - 'A' + 1)
const _Accuracy_name = "BelowExactAbove"
const _RoundingMode_name = "ToNearestEvenToNearestAwayToZeroAwayFromZeroToNegativeInfToPositiveInf"
const debugFloat = false // enable for debugging
const digits = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"
const divRecursiveThreshold = 100

Gob codec version. Permits backward-compatible changes to the encoding.

const floatGobVersion byte = 1

Gob codec version. Permits backward-compatible changes to the encoding.

const intGobVersion byte = 1
const maxBaseSmall = 10 + ('z' - 'a' + 1)

Maximum shift amount that can be done in one pass without overflow. A Word has _W bits and (1<<maxShift - 1)*10 + 9 must fit into Word.

const maxShift = _W - 4

Gob codec version. Permits backward-compatible changes to the encoding.

const ratGobVersion byte = 1

Variables

var (
    natOne  = nat{1}
    natTwo  = nat{2}
    natFive = nat{5}
    natTen  = nat{10}
)

scan errors

var (
    errNoDigits = errors.New("number has no digits")
    errInvalSep = errors.New("'_' must separate successive digits")
)
var _ fmt.Scanner = (*Float)(nil) // *Float must implement fmt.Scanner
var _ fmt.Formatter = &floatZero // *Float must implement fmt.Formatter
var _ fmt.Formatter = intOne // *Int must implement fmt.Formatter
var _ fmt.Scanner = intOne // *Int must implement fmt.Scanner
var _ fmt.Scanner = &ratZero // *Rat must implement fmt.Scanner
var _Accuracy_index = [...]uint8{0, 5, 10, 15}
var _RoundingMode_index = [...]uint8{0, 13, 26, 32, 44, 57, 70}

Operands that are shorter than basicSqrThreshold are squared using "grade school" multiplication; for operands longer than karatsubaSqrThreshold we use the Karatsuba algorithm optimized for x == y.

var basicSqrThreshold = 20 // computed by calibrate_test.go
var cacheBase10 struct {
    sync.Mutex
    table [64]divisor // cached divisors for base 10
}
var intOne = &Int{false, natOne}
var karatsubaSqrThreshold = 260 // computed by calibrate_test.go

Operands that are shorter than karatsubaThreshold are multiplied using "grade school" multiplication; for longer operands the Karatsuba algorithm is used.

var karatsubaThreshold = 40 // computed by calibrate_test.go

Split blocks greater than leafSize Words (or set to 0 to disable recursive conversion) Benchmark and configure leafSize using: go test -bench="Leaf"

8 and 16 effective on 3.0 GHz Xeon "Clovertown" CPU (128 byte cache lines)
8 and 16 effective on 2.66 GHz Core 2 Duo "Penryn" CPU
var leafSize int = 8 // number of Word-size binary values treat as a monolithic block
var natPool sync.Pool

These powers of 5 fit into a uint64.

for p, q := uint64(0), uint64(1); p < q; p, q = q, q*5 {
	fmt.Println(q)
}
var pow5tab = [...]uint64{
    1,
    5,
    25,
    125,
    625,
    3125,
    15625,
    78125,
    390625,
    1953125,
    9765625,
    48828125,
    244140625,
    1220703125,
    6103515625,
    30517578125,
    152587890625,
    762939453125,
    3814697265625,
    19073486328125,
    95367431640625,
    476837158203125,
    2384185791015625,
    11920928955078125,
    59604644775390625,
    298023223876953125,
    1490116119384765625,
    7450580596923828125,
}
var support_adx = cpu.X86.HasADX && cpu.X86.HasBMI2
var threeOnce struct {
    sync.Once
    v *Float
}

func Jacobi 1.5

func Jacobi(x, y *Int) int

Jacobi returns the Jacobi symbol (x/y), either +1, -1, or 0. The y argument must be an odd integer.

func ParseFloat 1.5

func ParseFloat(s string, base int, prec uint, mode RoundingMode) (f *Float, b int, err error)

ParseFloat is like f.Parse(s, base) with f set to the given precision and rounding mode.

func addAt

func addAt(z, x nat, i int)

addAt implements z += x<<(_W*i); z must be long enough. (we don't use nat.add because we need z to stay the same slice, and we don't need to normalize z after each addition)

func alias

func alias(x, y nat) bool

alias reports whether x and y share the same base array. Note: alias assumes that the capacity of underlying arrays

is never changed for nat values; i.e. that there are
no 3-operand slice expressions in this code (or worse,
reflect-based operations to the same effect).

func appendZeros

func appendZeros(buf []byte, n int) []byte

appendZeros appends n 0 digits to buf and returns buf.

func basicMul

func basicMul(z, x, y nat)

basicMul multiplies x and y and leaves the result in z. The (non-normalized) result is placed in z[0 : len(x) + len(y)].

func basicSqr

func basicSqr(z, x nat)

basicSqr sets z = x*x and is asymptotically faster than basicMul by about a factor of 2, but slower for small arguments due to overhead. Requirements: len(x) > 0, len(z) == 2*len(x) The (non-normalized) result is placed in z.

func euclidUpdate

func euclidUpdate(A, B, Ua, Ub, q, r, s, t *Int, extended bool)

euclidUpdate performs a single step of the Euclidean GCD algorithm if extended is true, it also updates the cosequence Ua, Ub

func fmtE

func fmtE(buf []byte, fmt byte, prec int, d decimal) []byte

%e: d.ddddde±dd

func fmtF

func fmtF(buf []byte, prec int, d decimal) []byte

%f: ddddddd.ddddd

func fnorm

func fnorm(m nat) int64

fnorm normalizes mantissa m by shifting it to the left such that the msb of the most-significant word (msw) is 1. It returns the shift amount. It assumes that len(m) != 0.

func greaterThan

func greaterThan(x1, x2, y1, y2 Word) bool

greaterThan reports whether (x1<<_W + x2) > (y1<<_W + y2)

func karatsuba

func karatsuba(z, x, y nat)

karatsuba multiplies x and y and leaves the result in z. Both x and y must have the same length n and n must be a power of 2. The result vector z must have len(z) >= 6*n. The (non-normalized) result is placed in z[0 : 2*n].

func karatsubaAdd

func karatsubaAdd(z, x nat, n int)

Fast version of z[0:n+n>>1].add(z[0:n+n>>1], x[0:n]) w/o bounds checks. Factored out for readability - do not use outside karatsuba.

func karatsubaLen

func karatsubaLen(n, threshold int) int

karatsubaLen computes an approximation to the maximum k <= n such that k = p<<i for a number p <= threshold and an i >= 0. Thus, the result is the largest number that can be divided repeatedly by 2 before becoming about the value of threshold.

func karatsubaSqr

func karatsubaSqr(z, x nat)

karatsubaSqr squares x and leaves the result in z. len(x) must be a power of 2 and len(z) >= 6*len(x). The (non-normalized) result is placed in z[0 : 2*len(x)].

The algorithm and the layout of z are the same as for karatsuba.

func karatsubaSub

func karatsubaSub(z, x nat, n int)

Like karatsubaAdd, but does subtract.

func lehmerUpdate

func lehmerUpdate(A, B, q, r, s, t *Int, u0, u1, v0, v1 Word, even bool)

lehmerUpdate updates the inputs A and B such that:

A = u0*A + v0*B
B = u1*A + v1*B

where the signs of u0, u1, v0, v1 are given by even For even == true: u0, v1 >= 0 && u1, v0 <= 0 For even == false: u0, v1 <= 0 && u1, v0 >= 0 q, r, s, t are temporary variables to avoid allocations in the multiplication

func low32

func low32(x nat) uint32

low32 returns the least significant 32 bits of x.

func low64

func low64(x nat) uint64

low64 returns the least significant 64 bits of x.

func max

func max(x, y int) int

func maxPow

func maxPow(b Word) (p Word, n int)

maxPow returns (b**n, n) such that b**n is the largest power b**n <= _M. For instance maxPow(10) == (1e19, 19) for 19 decimal digits in a 64bit Word. In other words, at most n digits in base b fit into a Word. TODO(gri) replace this with a table, generated at build time.

func min

func min(x, y int) int

func msb32

func msb32(x nat) uint32

msb32 returns the 32 most significant bits of x.

func msb64

func msb64(x nat) uint64

msb64 returns the 64 most significant bits of x.

func nlz

func nlz(x Word) uint

nlz returns the number of leading zeros in x. Wraps bits.LeadingZeros call for convenience.

func putNat

func putNat(x *nat)

func quotToFloat32

func quotToFloat32(a, b nat) (f float32, exact bool)

quotToFloat32 returns the non-negative float32 value nearest to the quotient a/b, using round-to-even in halfway cases. It does not mutate its arguments. Preconditions: b is non-zero; a and b have no common factors.

func quotToFloat64

func quotToFloat64(a, b nat) (f float64, exact bool)

quotToFloat64 returns the non-negative float64 value nearest to the quotient a/b, using round-to-even in halfway cases. It does not mutate its arguments. Preconditions: b is non-zero; a and b have no common factors.

func ratTok

func ratTok(ch rune) bool

func roundShortest

func roundShortest(d *decimal, x *Float)

func same

func same(x, y nat) bool

func scanExponent

func scanExponent(r io.ByteScanner, base2ok, sepOk bool) (exp int64, base int, err error)

scanExponent scans the longest possible prefix of r representing a base 10 (“e”, “E”) or a base 2 (“p”, “P”) exponent, if any. It returns the exponent, the exponent base (10 or 2), or a read or syntax error, if any.

If sepOk is set, an underscore character “_” may appear between successive exponent digits; such underscores do not change the value of the exponent. Incorrect placement of underscores is reported as an error if there are no other errors. If sepOk is not set, underscores are not recognized and thus terminate scanning like any other character that is not a valid digit.

exponent = ( "e" | "E" | "p" | "P" ) [ sign ] digits .
sign     = "+" | "-" .
digits   = digit { [ '_' ] digit } .
digit    = "0" ... "9" .

A base 2 exponent is only permitted if base2ok is set.

func scanSign

func scanSign(r io.ByteScanner) (neg bool, err error)

func shouldRoundUp

func shouldRoundUp(x *decimal, n int) bool

shouldRoundUp reports if x should be rounded up if shortened to n digits. n must be a valid index for x.mant.

func shr

func shr(x *decimal, s uint)

shr implements x >> s, for s <= maxShift.

func trim

func trim(x *decimal)

trim cuts off any trailing zeros from x's mantissa; they are meaningless for the value of x.

func umax32

func umax32(x, y uint32) uint32

func validateBinaryOperands

func validateBinaryOperands(x, y *Float)

func writeMultiple

func writeMultiple(s fmt.State, text string, count int)

write count copies of text to s

type Accuracy 1.5

Accuracy describes the rounding error produced by the most recent operation that generated a Float value, relative to the exact value.

type Accuracy int8

Constants describing the Accuracy of a Float.

const (
    Below Accuracy = -1
    Exact Accuracy = 0
    Above Accuracy = +1
)

func makeAcc

func makeAcc(above bool) Accuracy

func (Accuracy) String 1.5

func (i Accuracy) String() string

type ErrNaN 1.5

An ErrNaN panic is raised by a Float operation that would lead to a NaN under IEEE-754 rules. An ErrNaN implements the error interface.

type ErrNaN struct {
    msg string
}

func (ErrNaN) Error 1.5

func (err ErrNaN) Error() string

type Float 1.5

A nonzero finite Float represents a multi-precision floating point number

sign × mantissa × 2**exponent

with 0.5 <= mantissa < 1.0, and MinExp <= exponent <= MaxExp. A Float may also be zero (+0, -0) or infinite (+Inf, -Inf). All Floats are ordered, and the ordering of two Floats x and y is defined by x.Cmp(y).

Each Float value also has a precision, rounding mode, and accuracy. The precision is the maximum number of mantissa bits available to represent the value. The rounding mode specifies how a result should be rounded to fit into the mantissa bits, and accuracy describes the rounding error with respect to the exact result.

Unless specified otherwise, all operations (including setters) that specify a *Float variable for the result (usually via the receiver with the exception of MantExp), round the numeric result according to the precision and rounding mode of the result variable.

If the provided result precision is 0 (see below), it is set to the precision of the argument with the largest precision value before any rounding takes place, and the rounding mode remains unchanged. Thus, uninitialized Floats provided as result arguments will have their precision set to a reasonable value determined by the operands, and their mode is the zero value for RoundingMode (ToNearestEven).

By setting the desired precision to 24 or 53 and using matching rounding mode (typically ToNearestEven), Float operations produce the same results as the corresponding float32 or float64 IEEE-754 arithmetic for operands that correspond to normal (i.e., not denormal) float32 or float64 numbers. Exponent underflow and overflow lead to a 0 or an Infinity for different values than IEEE-754 because Float exponents have a much larger range.

The zero (uninitialized) value for a Float is ready to use and represents the number +0.0 exactly, with precision 0 and rounding mode ToNearestEven.

Operations always take pointer arguments (*Float) rather than Float values, and each unique Float value requires its own unique *Float pointer. To "copy" a Float value, an existing (or newly allocated) Float must be set to a new value using the Float.Set method; shallow copies of Floats are not supported and may lead to errors.

type Float struct {
    prec uint32
    mode RoundingMode
    acc  Accuracy
    form form
    neg  bool
    mant nat
    exp  int32
}
var floatZero Float

Example (Shift)

0.015625
0.03125
0.0625
0.125
0.25
0.5
1
2
4
8
16

func NewFloat 1.5

func NewFloat(x float64) *Float

NewFloat allocates and returns a new Float set to x, with precision 53 and rounding mode ToNearestEven. NewFloat panics with ErrNaN if x is a NaN.

func newFloat

func newFloat(prec2 uint32) *Float

newFloat returns a new *Float with space for twice the given precision.

func three

func three() *Float

func (*Float) Abs 1.5

func (z *Float) Abs(x *Float) *Float

Abs sets z to the (possibly rounded) value |x| (the absolute value of x) and returns z.

func (*Float) Acc 1.5

func (x *Float) Acc() Accuracy

Acc returns the accuracy of x produced by the most recent operation, unless explicitly documented otherwise by that operation.

func (*Float) Add 1.5

func (z *Float) Add(x, y *Float) *Float

Add sets z to the rounded sum x+y and returns z. If z's precision is 0, it is changed to the larger of x's or y's precision before the operation. Rounding is performed according to z's precision and rounding mode; and z's accuracy reports the result error relative to the exact (not rounded) result. Add panics with ErrNaN if x and y are infinities with opposite signs. The value of z is undefined in that case.

Example

x = 1000 (0x.fap+10, prec = 64, acc = Exact)
y = 2.718281828 (0x.adf85458248cd8p+2, prec = 53, acc = Exact)
z = 1002.718282 (0x.faadf854p+10, prec = 32, acc = Below)

func (*Float) Append 1.5

func (x *Float) Append(buf []byte, fmt byte, prec int) []byte

Append appends to buf the string form of the floating-point number x, as generated by x.Text, and returns the extended buffer.

func (*Float) Cmp 1.5

func (x *Float) Cmp(y *Float) int

Cmp compares x and y and returns:

-1 if x <  y
 0 if x == y (incl. -0 == 0, -Inf == -Inf, and +Inf == +Inf)
+1 if x >  y

Example

   x     y  cmp
---------------
-Inf  -Inf    0
-Inf  -1.2   -1
-Inf    -0   -1
-Inf     0   -1
-Inf   1.2   -1
-Inf  +Inf   -1

-1.2  -Inf    1
-1.2  -1.2    0
-1.2    -0   -1
-1.2     0   -1
-1.2   1.2   -1
-1.2  +Inf   -1

  -0  -Inf    1
  -0  -1.2    1
  -0    -0    0
  -0     0    0
  -0   1.2   -1
  -0  +Inf   -1

   0  -Inf    1
   0  -1.2    1
   0    -0    0
   0     0    0
   0   1.2   -1
   0  +Inf   -1

 1.2  -Inf    1
 1.2  -1.2    1
 1.2    -0    1
 1.2     0    1
 1.2   1.2    0
 1.2  +Inf   -1

+Inf  -Inf    1
+Inf  -1.2    1
+Inf    -0    1
+Inf     0    1
+Inf   1.2    1
+Inf  +Inf    0

func (*Float) Copy 1.5

func (z *Float) Copy(x *Float) *Float

Copy sets z to x, with the same precision, rounding mode, and accuracy as x, and returns z. x is not changed even if z and x are the same.

func (*Float) Float32 1.5

func (x *Float) Float32() (float32, Accuracy)

Float32 returns the float32 value nearest to x. If x is too small to be represented by a float32 (|x| < math.SmallestNonzeroFloat32), the result is (0, Below) or (-0, Above), respectively, depending on the sign of x. If x is too large to be represented by a float32 (|x| > math.MaxFloat32), the result is (+Inf, Above) or (-Inf, Below), depending on the sign of x.

func (*Float) Float64 1.5

func (x *Float) Float64() (float64, Accuracy)

Float64 returns the float64 value nearest to x. If x is too small to be represented by a float64 (|x| < math.SmallestNonzeroFloat64), the result is (0, Below) or (-0, Above), respectively, depending on the sign of x. If x is too large to be represented by a float64 (|x| > math.MaxFloat64), the result is (+Inf, Above) or (-Inf, Below), depending on the sign of x.

func (*Float) Format 1.5

func (x *Float) Format(s fmt.State, format rune)

Format implements fmt.Formatter. It accepts all the regular formats for floating-point numbers ('b', 'e', 'E', 'f', 'F', 'g', 'G', 'x') as well as 'p' and 'v'. See (*Float).Text for the interpretation of 'p'. The 'v' format is handled like 'g'. Format also supports specification of the minimum precision in digits, the output field width, as well as the format flags '+' and ' ' for sign control, '0' for space or zero padding, and '-' for left or right justification. See the fmt package for details.

func (*Float) GobDecode 1.7

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

GobDecode implements the gob.GobDecoder interface. The result is rounded per the precision and rounding mode of z unless z's precision is 0, in which case z is set exactly to the decoded value.

func (*Float) GobEncode 1.7

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

GobEncode implements the gob.GobEncoder interface. The Float value and all its attributes (precision, rounding mode, accuracy) are marshaled.

func (*Float) Int 1.5

func (x *Float) Int(z *Int) (*Int, Accuracy)

Int returns the result of truncating x towards zero; or nil if x is an infinity. The result is Exact if x.IsInt(); otherwise it is Below for x > 0, and Above for x < 0. If a non-nil *Int argument z is provided, Int stores the result in z instead of allocating a new Int.

func (*Float) Int64 1.5

func (x *Float) Int64() (int64, Accuracy)

Int64 returns the integer resulting from truncating x towards zero. If math.MinInt64 <= x <= math.MaxInt64, the result is Exact if x is an integer, and Above (x < 0) or Below (x > 0) otherwise. The result is (math.MinInt64, Above) for x < math.MinInt64, and (math.MaxInt64, Below) for x > math.MaxInt64.

func (*Float) IsInf 1.5

func (x *Float) IsInf() bool

IsInf reports whether x is +Inf or -Inf.

func (*Float) IsInt 1.5

func (x *Float) IsInt() bool

IsInt reports whether x is an integer. ±Inf values are not integers.

func (*Float) MantExp 1.5

func (x *Float) MantExp(mant *Float) (exp int)

MantExp breaks x into its mantissa and exponent components and returns the exponent. If a non-nil mant argument is provided its value is set to the mantissa of x, with the same precision and rounding mode as x. The components satisfy x == mant × 2**exp, with 0.5 <= |mant| < 1.0. Calling MantExp with a nil argument is an efficient way to get the exponent of the receiver.

Special cases are:

(  ±0).MantExp(mant) = 0, with mant set to   ±0
(±Inf).MantExp(mant) = 0, with mant set to ±Inf

x and mant may be the same in which case x is set to its mantissa value.

func (*Float) MarshalText 1.6

func (x *Float) MarshalText() (text []byte, err error)

MarshalText implements the encoding.TextMarshaler interface. Only the Float value is marshaled (in full precision), other attributes such as precision or accuracy are ignored.

func (*Float) MinPrec 1.5

func (x *Float) MinPrec() uint

MinPrec returns the minimum precision required to represent x exactly (i.e., the smallest prec before x.SetPrec(prec) would start rounding x). The result is 0 for |x| == 0 and |x| == Inf.

func (*Float) Mode 1.5

func (x *Float) Mode() RoundingMode

Mode returns the rounding mode of x.

func (*Float) Mul 1.5

func (z *Float) Mul(x, y *Float) *Float

Mul sets z to the rounded product x*y and returns z. Precision, rounding, and accuracy reporting are as for Add. Mul panics with ErrNaN if one operand is zero and the other operand an infinity. The value of z is undefined in that case.

func (*Float) Neg 1.5

func (z *Float) Neg(x *Float) *Float

Neg sets z to the (possibly rounded) value of x with its sign negated, and returns z.

func (*Float) Parse 1.5

func (z *Float) Parse(s string, base int) (f *Float, b int, err error)

Parse parses s which must contain a text representation of a floating- point number with a mantissa in the given conversion base (the exponent is always a decimal number), or a string representing an infinite value.

For base 0, an underscore character “_” may appear between a base prefix and an adjacent digit, and between successive digits; such underscores do not change the value of the number, or the returned digit count. Incorrect placement of underscores is reported as an error if there are no other errors. If base != 0, underscores are not recognized and thus terminate scanning like any other character that is not a valid radix point or digit.

It sets z to the (possibly rounded) value of the corresponding floating- point value, and returns z, the actual base b, and an error err, if any. The entire string (not just a prefix) must be consumed for success. If z's precision is 0, it is changed to 64 before rounding takes effect. The number must be of the form:

number    = [ sign ] ( float | "inf" | "Inf" ) .
sign      = "+" | "-" .
float     = ( mantissa | prefix pmantissa ) [ exponent ] .
prefix    = "0" [ "b" | "B" | "o" | "O" | "x" | "X" ] .
mantissa  = digits "." [ digits ] | digits | "." digits .
pmantissa = [ "_" ] digits "." [ digits ] | [ "_" ] digits | "." digits .
exponent  = ( "e" | "E" | "p" | "P" ) [ sign ] digits .
digits    = digit { [ "_" ] digit } .
digit     = "0" ... "9" | "a" ... "z" | "A" ... "Z" .

The base argument must be 0, 2, 8, 10, or 16. Providing an invalid base argument will lead to a run-time panic.

For base 0, the number prefix determines the actual base: A prefix of “0b” or “0B” selects base 2, “0o” or “0O” selects base 8, and “0x” or “0X” selects base 16. Otherwise, the actual base is 10 and no prefix is accepted. The octal prefix "0" is not supported (a leading "0" is simply considered a "0").

A "p" or "P" exponent indicates a base 2 (rather then base 10) exponent; for instance, "0x1.fffffffffffffp1023" (using base 0) represents the maximum float64 value. For hexadecimal mantissae, the exponent character must be one of 'p' or 'P', if present (an "e" or "E" exponent indicator cannot be distinguished from a mantissa digit).

The returned *Float f is nil and the value of z is valid but not defined if an error is reported.

func (*Float) Prec 1.5

func (x *Float) Prec() uint

Prec returns the mantissa precision of x in bits. The result may be 0 for |x| == 0 and |x| == Inf.

func (*Float) Quo 1.5

func (z *Float) Quo(x, y *Float) *Float

Quo sets z to the rounded quotient x/y and returns z. Precision, rounding, and accuracy reporting are as for Add. Quo panics with ErrNaN if both operands are zero or infinities. The value of z is undefined in that case.

func (*Float) Rat 1.5

func (x *Float) Rat(z *Rat) (*Rat, Accuracy)

Rat returns the rational number corresponding to x; or nil if x is an infinity. The result is Exact if x is not an Inf. If a non-nil *Rat argument z is provided, Rat stores the result in z instead of allocating a new Rat.

func (*Float) Scan 1.8

func (z *Float) 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 formats whose verbs are supported by fmt.Scan for floating point values, which are: 'b' (binary), 'e', 'E', 'f', 'F', 'g' and 'G'. Scan doesn't handle ±Inf.

Example

1.19282e+99

func (*Float) Set 1.5

func (z *Float) Set(x *Float) *Float

Set sets z to the (possibly rounded) value of x and returns z. If z's precision is 0, it is changed to the precision of x before setting z (and rounding will have no effect). Rounding is performed according to z's precision and rounding mode; and z's accuracy reports the result error relative to the exact (not rounded) result.

func (*Float) SetFloat64 1.5

func (z *Float) SetFloat64(x float64) *Float

SetFloat64 sets z to the (possibly rounded) value of x and returns z. If z's precision is 0, it is changed to 53 (and rounding will have no effect). SetFloat64 panics with ErrNaN if x is a NaN.

func (*Float) SetInf 1.5

func (z *Float) SetInf(signbit bool) *Float

SetInf sets z to the infinite Float -Inf if signbit is set, or +Inf if signbit is not set, and returns z. The precision of z is unchanged and the result is always Exact.

func (*Float) SetInt 1.5

func (z *Float) SetInt(x *Int) *Float

SetInt sets z to the (possibly rounded) value of x and returns z. If z's precision is 0, it is changed to the larger of x.BitLen() or 64 (and rounding will have no effect).

func (*Float) SetInt64 1.5

func (z *Float) SetInt64(x int64) *Float

SetInt64 sets z to the (possibly rounded) value of x and returns z. If z's precision is 0, it is changed to 64 (and rounding will have no effect).

func (*Float) SetMantExp 1.5

func (z *Float) SetMantExp(mant *Float, exp int) *Float

SetMantExp sets z to mant × 2**exp and returns z. The result z has the same precision and rounding mode as mant. SetMantExp is an inverse of MantExp but does not require 0.5 <= |mant| < 1.0. Specifically:

mant := new(Float)
new(Float).SetMantExp(mant, x.MantExp(mant)).Cmp(x) == 0

Special cases are:

z.SetMantExp(  ±0, exp) =   ±0
z.SetMantExp(±Inf, exp) = ±Inf

z and mant may be the same in which case z's exponent is set to exp.

func (*Float) SetMode 1.5

func (z *Float) SetMode(mode RoundingMode) *Float

SetMode sets z's rounding mode to mode and returns an exact z. z remains unchanged otherwise. z.SetMode(z.Mode()) is a cheap way to set z's accuracy to Exact.

func (*Float) SetPrec 1.5

func (z *Float) SetPrec(prec uint) *Float

SetPrec sets z's precision to prec and returns the (possibly) rounded value of z. Rounding occurs according to z's rounding mode if the mantissa cannot be represented in prec bits without loss of precision. SetPrec(0) maps all finite values to ±0; infinite values remain unchanged. If prec > MaxPrec, it is set to MaxPrec.

func (*Float) SetRat 1.5

func (z *Float) SetRat(x *Rat) *Float

SetRat sets z to the (possibly rounded) value of x and returns z. If z's precision is 0, it is changed to the largest of a.BitLen(), b.BitLen(), or 64; with x = a/b.

func (*Float) SetString 1.5

func (z *Float) SetString(s string) (*Float, bool)

SetString sets z to the value of s and returns z and a boolean indicating success. s must be a floating-point number of the same format as accepted by Parse, with base argument 0. The entire string (not just a prefix) must be valid for success. If the operation failed, the value of z is undefined but the returned value is nil.

func (*Float) SetUint64 1.5

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

SetUint64 sets z to the (possibly rounded) value of x and returns z. If z's precision is 0, it is changed to 64 (and rounding will have no effect).

func (*Float) Sign 1.5

func (x *Float) Sign() int

Sign returns:

-1 if x <   0
 0 if x is ±0
+1 if x >   0

func (*Float) Signbit 1.5

func (x *Float) Signbit() bool

Signbit reports whether x is negative or negative zero.

func (*Float) Sqrt 1.10

func (z *Float) Sqrt(x *Float) *Float

Sqrt sets z to the rounded square root of x, and returns it.

If z's precision is 0, it is changed to x's precision before the operation. Rounding is performed according to z's precision and rounding mode, but z's accuracy is not computed. Specifically, the result of z.Acc() is undefined.

The function panics if z < 0. The value of z is undefined in that case.

func (*Float) String 1.5

func (x *Float) String() string

String formats x like x.Text('g', 10). (String must be called explicitly, Float.Format does not support %s verb.)

func (*Float) Sub 1.5

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

Sub sets z to the rounded difference x-y and returns z. Precision, rounding, and accuracy reporting are as for Add. Sub panics with ErrNaN if x and y are infinities with equal signs. The value of z is undefined in that case.

func (*Float) Text 1.5

func (x *Float) Text(format byte, prec int) string

Text converts the floating-point number x to a string according to the given format and precision prec. The format is one of:

'e'	-d.dddde±dd, decimal exponent, at least two (possibly 0) exponent digits
'E'	-d.ddddE±dd, decimal exponent, at least two (possibly 0) exponent digits
'f'	-ddddd.dddd, no exponent
'g'	like 'e' for large exponents, like 'f' otherwise
'G'	like 'E' for large exponents, like 'f' otherwise
'x'	-0xd.dddddp±dd, hexadecimal mantissa, decimal power of two exponent
'p'	-0x.dddp±dd, hexadecimal mantissa, decimal power of two exponent (non-standard)
'b'	-ddddddp±dd, decimal mantissa, decimal power of two exponent (non-standard)

For the power-of-two exponent formats, the mantissa is printed in normalized form:

'x'	hexadecimal mantissa in [1, 2), or 0
'p'	hexadecimal mantissa in [½, 1), or 0
'b'	decimal integer mantissa using x.Prec() bits, or 0

Note that the 'x' form is the one used by most other languages and libraries.

If format is a different character, Text returns a "%" followed by the unrecognized format character.

The precision prec controls the number of digits (excluding the exponent) printed by the 'e', 'E', 'f', 'g', 'G', and 'x' formats. For 'e', 'E', 'f', and 'x', it is the number of digits after the decimal point. For 'g' and 'G' it is the total number of digits. A negative precision selects the smallest number of decimal digits necessary to identify the value x uniquely using x.Prec() mantissa bits. The prec value is ignored for the 'b' and 'p' formats.

func (*Float) Uint64 1.5

func (x *Float) Uint64() (uint64, Accuracy)

Uint64 returns the unsigned integer resulting from truncating x towards zero. If 0 <= x <= math.MaxUint64, the result is Exact if x is an integer and Below otherwise. The result is (0, Above) for x < 0, and (math.MaxUint64, Below) for x > math.MaxUint64.

func (*Float) UnmarshalText 1.6

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

UnmarshalText implements the encoding.TextUnmarshaler interface. The result is rounded per the precision and rounding mode of z. If z's precision is 0, it is changed to 64 before rounding takes effect.

func (*Float) fmtB

func (x *Float) fmtB(buf []byte) []byte

fmtB appends the string of x in the format mantissa "p" exponent with a decimal mantissa and a binary exponent, or 0" if x is zero, and returns the extended buffer. The mantissa is normalized such that is uses x.Prec() bits in binary representation. The sign of x is ignored, and x must not be an Inf. (The caller handles Inf before invoking fmtB.)

func (*Float) fmtP

func (x *Float) fmtP(buf []byte) []byte

fmtP appends the string of x in the format "0x." mantissa "p" exponent with a hexadecimal mantissa and a binary exponent, or "0" if x is zero, and returns the extended buffer. The mantissa is normalized such that 0.5 <= 0.mantissa < 1.0. The sign of x is ignored, and x must not be an Inf. (The caller handles Inf before invoking fmtP.)

func (*Float) fmtX

func (x *Float) fmtX(buf []byte, prec int) []byte

fmtX appends the string of x in the format "0x1." mantissa "p" exponent with a hexadecimal mantissa and a binary exponent, or "0x0p0" if x is zero, and returns the extended buffer. A non-zero mantissa is normalized such that 1.0 <= mantissa < 2.0. The sign of x is ignored, and x must not be an Inf. (The caller handles Inf before invoking fmtX.)

func (*Float) ord

func (x *Float) ord() int

ord classifies x and returns:

-2 if -Inf == x
-1 if -Inf < x < 0
 0 if x == 0 (signed or unsigned)
+1 if 0 < x < +Inf
+2 if x == +Inf

func (*Float) pow5

func (z *Float) pow5(n uint64) *Float

pow5 sets z to 5**n and returns z. n must not be negative.

func (*Float) round

func (z *Float) round(sbit uint)

round rounds z according to z.mode to z.prec bits and sets z.acc accordingly. sbit must be 0 or 1 and summarizes any "sticky bit" information one might have before calling round. z's mantissa must be normalized (with the msb set) or empty.

CAUTION: The rounding modes ToNegativeInf, ToPositiveInf are affected by the sign of z. For correct rounding, the sign of z must be set correctly before calling round.

func (*Float) scan

func (z *Float) scan(r io.ByteScanner, base int) (f *Float, b int, err error)

scan is like Parse but reads the longest possible prefix representing a valid floating point number from an io.ByteScanner rather than a string. It serves as the implementation of Parse. It does not recognize ±Inf and does not expect EOF at the end.

func (*Float) setBits64

func (z *Float) setBits64(neg bool, x uint64) *Float

func (*Float) setExpAndRound

func (z *Float) setExpAndRound(exp int64, sbit uint)

func (*Float) sqrtInverse

func (z *Float) sqrtInverse(x *Float)

Compute √x (to z.prec precision) by solving

1/t² - x = 0

for t (using Newton's method), and then inverting.

func (*Float) uadd

func (z *Float) uadd(x, y *Float)

z = x + y, ignoring signs of x and y for the addition but using the sign of z for rounding the result. x and y must have a non-empty mantissa and valid exponent.

func (*Float) ucmp

func (x *Float) ucmp(y *Float) int

ucmp returns -1, 0, or +1, depending on whether |x| < |y|, |x| == |y|, or |x| > |y|. x and y must have a non-empty mantissa and valid exponent.

func (*Float) umul

func (z *Float) umul(x, y *Float)

z = x * y, ignoring signs of x and y for the multiplication but using the sign of z for rounding the result. x and y must have a non-empty mantissa and valid exponent.

func (*Float) uquo

func (z *Float) uquo(x, y *Float)

z = x / y, ignoring signs of x and y for the division but using the sign of z for rounding the result. x and y must have a non-empty mantissa and valid exponent.

func (*Float) usub

func (z *Float) usub(x, y *Float)

z = x - y for |x| > |y|, ignoring signs of x and y for the subtraction but using the sign of z for rounding the result. x and y must have a non-empty mantissa and valid exponent.

func (*Float) validate

func (x *Float) validate()

debugging support

type Int

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

Operations always take pointer arguments (*Int) rather than Int values, and each unique Int value requires its own unique *Int pointer. To "copy" an Int value, an existing (or newly allocated) Int must be set to a new value using the Int.Set method; shallow copies of Ints are not supported and may lead to errors.

type Int struct {
    neg bool // sign
    abs nat  // absolute value of the integer
}

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) Append 1.6

func (x *Int) Append(buf []byte, base int) []byte

Append appends the string representation of x, as generated by x.Text(base), to buf and returns the extended buffer.

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.

To use a fixed length slice, or a preallocated one, use FillBytes.

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) CmpAbs 1.10

func (x *Int) CmpAbs(y *Int) int

CmpAbs compares the absolute values of 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 < |y|

(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 m == nil or m == 0, z = x**y unless y <= 0 then z = 1. If m != 0, y < 0, and x and m are not relatively prime, z is unchanged and nil is returned.

Modular exponentiation of inputs of a particular size is not a cryptographically constant-time operation.

func (*Int) FillBytes 1.15

func (x *Int) FillBytes(buf []byte) []byte

FillBytes sets buf to the absolute value of x, storing it as a zero-extended big-endian byte slice, and returns buf.

If the absolute value of x doesn't fit in buf, FillBytes will panic.

func (*Int) Format

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

Format implements fmt.Formatter. It accepts the formats 'b' (binary), 'o' (octal with 0 prefix), 'O' (octal with 0o prefix), 'd' (decimal), 'x' (lowercase hexadecimal), and 'X' (uppercase hexadecimal). Also supported are the full suite of package fmt's format flags 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 '-' for 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 and returns z. If x or y are not nil, GCD sets their value such that z = a*x + b*y.

a and b may be positive, zero or negative. (Before Go 1.14 both had to be > 0.) Regardless of the signs of a and b, z is always >= 0.

If a == b == 0, GCD sets z = x = y = 0.

If a == 0 and b != 0, GCD sets z = |b|, x = 0, y = sign(b) * 1.

If a != 0 and b == 0, GCD sets z = |a|, x = sign(a) * 1, 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) IsInt64 1.9

func (x *Int) IsInt64() bool

IsInt64 reports whether x can be represented as an int64.

func (*Int) IsUint64 1.9

func (x *Int) IsUint64() bool

IsUint64 reports whether x can be represented as a uint64.

func (*Int) Lsh

func (z *Int) Lsh(x *Int, n uint) *Int

Lsh sets z = x << n and returns z.

func (*Int) MarshalJSON 1.1

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

MarshalJSON implements the json.Marshaler interface.

func (*Int) MarshalText 1.3

func (x *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, g has no multiplicative inverse in the ring ℤ/nℤ. In this case, z is unchanged and the return value is nil.

func (*Int) ModSqrt 1.5

func (z *Int) ModSqrt(x, p *Int) *Int

ModSqrt sets z to a square root of x mod p if such a square root exists, and returns z. The modulus p must be an odd prime. If x is not a square mod p, ModSqrt leaves z unchanged and returns nil. This function panics if p is not an odd integer.

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 reports whether x is probably prime, applying the Miller-Rabin test with n pseudorandomly chosen bases as well as a Baillie-PSW test.

If x is prime, ProbablyPrime returns true. If x is chosen randomly and not prime, ProbablyPrime probably returns false. The probability of returning true for a randomly chosen non-prime is at most ¼ⁿ.

ProbablyPrime is 100% accurate for inputs less than 2⁶⁴. See Menezes et al., Handbook of Applied Cryptography, 1997, pp. 145-149, and FIPS 186-4 Appendix F for further discussion of the error probabilities.

ProbablyPrime is not suitable for judging primes that an adversary may have crafted to fool the test.

As of Go 1.8, ProbablyPrime(0) is allowed and applies only a Baillie-PSW test. Before Go 1.8, ProbablyPrime applied only the Miller-Rabin tests, and ProbablyPrime(0) panicked.

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.

As this uses the math/rand package, it must not be used for security-sensitive work. Use crypto/rand.Int instead.

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

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. The entire string (not just a prefix) must be valid for 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 between 2 and MaxBase. For base 0, the number prefix determines the actual base: A prefix of “0b” or “0B” selects base 2, “0”, “0o” or “0O” selects base 8, and “0x” or “0X” selects base 16. Otherwise, the selected base is 10 and no prefix is accepted.

For bases <= 36, lower and upper case letters are considered the same: The letters 'a' to 'z' and 'A' to 'Z' represent digit values 10 to 35. For bases > 36, the upper case letters 'A' to 'Z' represent the digit values 36 to 61.

For base 0, an underscore character “_” may appear between a base prefix and an adjacent digit, and between successive digits; such underscores do not change the value of the number. Incorrect placement of underscores is reported as an error if there are no other errors. If base != 0, underscores are not recognized and act like any other character that is not a valid digit.

Example

420

func (*Int) SetUint64 1.1

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) Sqrt 1.8

func (z *Int) Sqrt(x *Int) *Int

Sqrt sets z to ⌊√x⌋, the largest integer such that z² ≤ x, and returns z. It panics if x is negative.

func (*Int) String

func (x *Int) String() string

String returns the decimal representation of x as generated by x.Text(10).

func (*Int) Sub

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

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

func (*Int) Text 1.6

func (x *Int) Text(base int) string

Text returns the string representation of x in the given base. Base must be between 2 and 62, inclusive. The result uses the lower-case letters 'a' to 'z' for digit values 10 to 35, and the upper-case letters 'A' to 'Z' for digit values 36 to 61. No prefix (such as "0x") is added to the string. If x is a nil pointer it returns "<nil>".

func (*Int) TrailingZeroBits 1.13

func (x *Int) TrailingZeroBits() uint

TrailingZeroBits returns the number of consecutive least significant zero bits of |x|.

func (*Int) Uint64 1.1

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 1.1

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

UnmarshalJSON implements the json.Unmarshaler interface.

func (*Int) UnmarshalText 1.3

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.

func (*Int) lehmerGCD

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

lehmerGCD sets z to the greatest common divisor of a and b, which both must be != 0, and returns z. If x or y are not nil, their values are set such that z = a*x + b*y. See Knuth, The Art of Computer Programming, Vol. 2, Section 4.5.2, Algorithm L. This implementation uses the improved condition by Collins requiring only one quotient and avoiding the possibility of single Word overflow. See Jebelean, "Improving the multiprecision Euclidean algorithm", Design and Implementation of Symbolic Computation Systems, pp 45-58. The cosequences are updated according to Algorithm 10.45 from Cohen et al. "Handbook of Elliptic and Hyperelliptic Curve Cryptography" pp 192.

func (*Int) modSqrt3Mod4Prime

func (z *Int) modSqrt3Mod4Prime(x, p *Int) *Int

modSqrt3Mod4 uses the identity

   (a^((p+1)/4))^2  mod p
== u^(p+1)          mod p
== u^2              mod p

to calculate the square root of any quadratic residue mod p quickly for 3 mod 4 primes.

func (*Int) modSqrt5Mod8Prime

func (z *Int) modSqrt5Mod8Prime(x, p *Int) *Int

modSqrt5Mod8 uses Atkin's observation that 2 is not a square mod p

alpha ==  (2*a)^((p-5)/8)    mod p
beta  ==  2*a*alpha^2        mod p  is a square root of -1
b     ==  a*alpha*(beta-1)   mod p  is a square root of a

to calculate the square root of any quadratic residue mod p quickly for 5 mod 8 primes.

func (*Int) modSqrtTonelliShanks

func (z *Int) modSqrtTonelliShanks(x, p *Int) *Int

modSqrtTonelliShanks uses the Tonelli-Shanks algorithm to find the square root of a quadratic residue modulo any prime.

func (*Int) scaleDenom

func (z *Int) scaleDenom(x *Int, f nat)

scaleDenom sets z to the product x*f. If f == 0 (zero value of denominator), z is set to (a copy of) x.

func (*Int) scan

func (z *Int) scan(r io.ByteScanner, base int) (*Int, int, error)

scan sets z to the integer value corresponding to the longest possible prefix read from r representing a signed integer number in a given conversion base. It returns z, the actual conversion base used, and an error, if any. In the error case, the value of z is undefined but the returned value is nil. The syntax follows the syntax of integer literals in Go.

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 “0b” or “0B” selects base 2; a “0”, “0o”, or “0O” prefix selects base 8, and a “0x” or “0X” prefix selects base 16. Otherwise the selected base is 10.

func (*Int) setFromScanner

func (z *Int) setFromScanner(r io.ByteScanner, base int) (*Int, bool)

setFromScanner implements SetString given an io.BytesScanner. For documentation see comments of SetString.

type Rat

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

Operations always take pointer arguments (*Rat) rather than Rat values, and each unique Rat value requires its own unique *Rat pointer. To "copy" a Rat value, an existing (or newly allocated) Rat must be set to a new value using the Rat.Set method; shallow copies of Rats are not supported and may lead to errors.

type Rat struct {
    // To make zero values for Rat work w/o initialization,
    // a zero value of b (len(b) == 0) acts like b == 1. At
    // the earliest opportunity (when an assignment to the Rat
    // is made), such uninitialized denominators are set to 1.
    // a.neg determines the sign of the Rat, b.neg is ignored.
    a, b Int
}
var ratZero Rat

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, unless x is an uninitialized (zero value) Rat, in which case the result is a new Int of value 1. (To initialize x, any operation that sets x will do, including x.Set(x).) If 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 1.4

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 1.1

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 radix point. The last digit is rounded to nearest, with halves rounded away from zero.

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. If x == 0, Inv panics.

func (*Rat) IsInt

func (x *Rat) IsInt() bool

IsInt reports whether the denominator of x is 1.

func (*Rat) MarshalText 1.3

func (x *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, Quo panics.

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

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 1.1

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. If b == 0, SetFrac panics.

func (*Rat) SetFrac64

func (z *Rat) SetFrac64(a, b int64) *Rat

SetFrac64 sets z to a/b and returns z. If b == 0, SetFrac64 panics.

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 (possibly signed) fraction "a/b", or as a floating-point number optionally followed by an exponent. If a fraction is provided, both the dividend and the divisor may be a decimal integer or independently use a prefix of “0b”, “0” or “0o”, or “0x” (or their upper-case variants) to denote a binary, octal, or hexadecimal integer, respectively. The divisor may not be signed. If a floating-point number is provided, it may be in decimal form or use any of the same prefixes as above but for “0” to denote a non-decimal mantissa. A leading “0” is considered a decimal leading 0; it does not indicate octal representation in this case. An optional base-10 “e” or base-2 “p” (or their upper-case variants) exponent may be provided as well, except for hexadecimal floats which only accept an (optional) “p” exponent (because an “e” or “E” cannot be distinguished from a mantissa digit). The entire string, not just a prefix, must be valid for success. If the operation failed, the value of z is undefined but the returned value is nil.

Example

3.142

func (*Rat) SetUint64 1.13

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

SetUint64 sets z to x and returns z.

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 1.3

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

UnmarshalText implements the encoding.TextUnmarshaler interface.

func (*Rat) marshal

func (x *Rat) marshal() []byte

marshal implements String returning a slice of bytes

func (*Rat) norm

func (z *Rat) norm() *Rat

type RoundingMode 1.5

RoundingMode determines how a Float value is rounded to the desired precision. Rounding may change the Float value; the rounding error is described by the Float's Accuracy.

type RoundingMode byte

These constants define supported rounding modes.

const (
    ToNearestEven RoundingMode = iota // == IEEE 754-2008 roundTiesToEven
    ToNearestAway                     // == IEEE 754-2008 roundTiesToAway
    ToZero                            // == IEEE 754-2008 roundTowardZero
    AwayFromZero                      // no IEEE 754-2008 equivalent
    ToNegativeInf                     // == IEEE 754-2008 roundTowardNegative
    ToPositiveInf                     // == IEEE 754-2008 roundTowardPositive
)

Example

   x  ToNearestEven  ToNearestAway  ToZero  AwayFromZero  ToNegativeInf  ToPositiveInf
 2.6              3              3       2             3              2              3
 2.5              2              3       2             3              2              3
 2.1              2              2       2             3              2              3
-2.1             -2             -2      -2            -3             -3             -2
-2.5             -2             -3      -2            -3             -3             -2
-2.6             -3             -3      -2            -3             -3             -2

func (RoundingMode) String 1.5

func (i RoundingMode) String() string

type Word 1.9

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

type Word uint

func addMulVVW

func addMulVVW(z, x []Word, y Word) (c Word)

func addMulVVW_g

func addMulVVW_g(z, x []Word, y Word) (c Word)

func addVV

func addVV(z, x, y []Word) (c Word)

func addVV_g

func addVV_g(z, x, y []Word) (c Word)

The resulting carry c is either 0 or 1.

func addVW

func addVW(z, x []Word, y Word) (c Word)

func addVW_g

func addVW_g(z, x []Word, y Word) (c Word)

The resulting carry c is either 0 or 1.

func addVWlarge

func addVWlarge(z, x []Word, y Word) (c Word)

addVWlarge is addVW, but intended for large z. The only difference is that we check on every iteration whether we are done with carries, and if so, switch to a much faster copy instead. This is only a good idea for large z, because the overhead of the check and the function call outweigh the benefits when z is small.

func bigEndianWord

func bigEndianWord(buf []byte) Word

bigEndianWord returns the contents of buf interpreted as a big-endian encoded Word value.

func divWVW

func divWVW(z []Word, xn Word, x []Word, y Word) (r Word)

func divWVW_g

func divWVW_g(z []Word, xn Word, x []Word, y Word) (r Word)

func divWW

func divWW(x1, x0, y Word) (q, r Word)

func divWW_g

func divWW_g(u1, u0, v Word) (q, r Word)

q = (u1<<_W + u0 - r)/v

func lehmerSimulate

func lehmerSimulate(A, B *Int) (u0, u1, v0, v1 Word, even bool)

lehmerSimulate attempts to simulate several Euclidean update steps using the leading digits of A and B. It returns u0, u1, v0, v1 such that A and B can be updated as:

A = u0*A + v0*B
B = u1*A + v1*B

Requirements: A >= B and len(B.abs) >= 2 Since we are calculating with full words to avoid overflow, we use 'even' to track the sign of the cosequences. For even iterations: u0, v1 >= 0 && u1, v0 <= 0 For odd iterations: u0, v1 <= 0 && u1, v0 >= 0

func mulAddVWW

func mulAddVWW(z, x []Word, y, r Word) (c Word)

func mulAddVWW_g

func mulAddVWW_g(z, x []Word, y, r Word) (c Word)

func mulAddWWW_g

func mulAddWWW_g(x, y, c Word) (z1, z0 Word)

z1<<_W + z0 = x*y + c

func mulWW

func mulWW(x, y Word) (z1, z0 Word)

implemented in arith_$GOARCH.s

func mulWW_g

func mulWW_g(x, y Word) (z1, z0 Word)

z1<<_W + z0 = x*y

func pow

func pow(x Word, n int) (p Word)

pow returns x**n for n > 0, and 1 otherwise.

func shlVU

func shlVU(z, x []Word, s uint) (c Word)

func shlVU_g

func shlVU_g(z, x []Word, s uint) (c Word)

func shrVU

func shrVU(z, x []Word, s uint) (c Word)

func shrVU_g

func shrVU_g(z, x []Word, s uint) (c Word)

func subVV

func subVV(z, x, y []Word) (c Word)

func subVV_g

func subVV_g(z, x, y []Word) (c Word)

The resulting carry c is either 0 or 1.

func subVW

func subVW(z, x []Word, y Word) (c Word)

func subVW_g

func subVW_g(z, x []Word, y Word) (c Word)

func subVWlarge

func subVWlarge(z, x []Word, y Word) (c Word)

subVWlarge is to subVW as addVWlarge is to addVW.

type byteReader

byteReader is a local wrapper around fmt.ScanState; it implements the ByteReader interface.

type byteReader struct {
    fmt.ScanState
}

func (byteReader) ReadByte

func (r byteReader) ReadByte() (byte, error)

func (byteReader) UnreadByte

func (r byteReader) UnreadByte() error

type decimal

A decimal represents an unsigned floating-point number in decimal representation. The value of a non-zero decimal d is d.mant * 10**d.exp with 0.1 <= d.mant < 1, with the most-significant mantissa digit at index 0. For the zero decimal, the mantissa length and exponent are 0. The zero value for decimal represents a ready-to-use 0.0.

type decimal struct {
    mant []byte // mantissa ASCII digits, big-endian
    exp  int    // exponent
}

func (*decimal) String

func (x *decimal) String() string

func (*decimal) at

func (d *decimal) at(i int) byte

at returns the i'th mantissa digit, starting with the most significant digit at 0.

func (*decimal) init

func (x *decimal) init(m nat, shift int)

Init initializes x to the decimal representation of m << shift (for shift >= 0), or m >> -shift (for shift < 0).

func (*decimal) round

func (x *decimal) round(n int)

round sets x to (at most) n mantissa digits by rounding it to the nearest even value with n (or fever) mantissa digits. If n < 0, x remains unchanged.

func (*decimal) roundDown

func (x *decimal) roundDown(n int)

func (*decimal) roundUp

func (x *decimal) roundUp(n int)

type divisor

type divisor struct {
    bbb     nat // divisor
    nbits   int // bit length of divisor (discounting leading zeros) ~= log2(bbb)
    ndigits int // digit length of divisor in terms of output base digits
}

func divisors

func divisors(m int, b Word, ndigits int, bb Word) []divisor

construct table of powers of bb*leafSize to use in subdivisions

type form

A form value describes the internal representation.

type form byte

The form value order is relevant - do not change!

const (
    zero form = iota
    finite
    inf
)

type nat

An unsigned integer x of the form

x = x[n-1]*_B^(n-1) + x[n-2]*_B^(n-2) + ... + x[1]*_B + x[0]

with 0 <= x[i] < _B and 0 <= i < n is stored in a slice of length n, with the digits x[i] as the slice elements.

A number is normalized if the slice contains no leading 0 digits. During arithmetic operations, denormalized values may occur but are always normalized before returning the final result. The normalized representation of 0 is the empty or nil slice (length = 0).

type nat []Word

func getNat

func getNat(n int) *nat

getNat returns a *nat of len n. The contents may not be zero. The pool holds *nat to avoid allocation when converting to interface{}.

func mulDenom

func mulDenom(z, x, y nat) nat

mulDenom sets z to the denominator product x*y (by taking into account that 0 values for x or y must be interpreted as 1) and returns z.

func (nat) add

func (z nat) add(x, y nat) nat

func (nat) and

func (z nat) and(x, y nat) nat

func (nat) andNot

func (z nat) andNot(x, y nat) nat

func (nat) bit

func (x nat) bit(i uint) uint

bit returns the value of the i'th bit, with lsb == bit 0.

func (nat) bitLen

func (x nat) bitLen() int

Length of x in bits. x must be normalized.

func (nat) bytes

func (z nat) bytes(buf []byte) (i int)

bytes writes the value of z into buf using big-endian encoding. The value of z is encoded in the slice buf[i:]. If the value of z cannot be represented in buf, bytes panics. The number i of unused bytes at the beginning of buf is returned as result.

func (nat) clear

func (z nat) clear()

func (nat) cmp

func (x nat) cmp(y nat) (r int)

func (nat) convertWords

func (q nat) convertWords(s []byte, b Word, ndigits int, bb Word, table []divisor)

Convert words of q to base b digits in s. If q is large, it is recursively "split in half" by nat/nat division using tabulated divisors. Otherwise, it is converted iteratively using repeated nat/Word division.

The iterative method processes n Words by n divW() calls, each of which visits every Word in the incrementally shortened q for a total of n + (n-1) + (n-2) ... + 2 + 1, or n(n+1)/2 divW()'s. Recursive conversion divides q by its approximate square root, yielding two parts, each half the size of q. Using the iterative method on both halves means 2 * (n/2)(n/2 + 1)/2 divW()'s plus the expensive long div(). Asymptotically, the ratio is favorable at 1/2 the divW()'s, and is made better by splitting the subblocks recursively. Best is to split blocks until one more split would take longer (because of the nat/nat div()) than the twice as many divW()'s of the iterative approach. This threshold is represented by leafSize. Benchmarking of leafSize in the range 2..64 shows that values of 8 and 16 work well, with a 4x speedup at medium lengths and ~30x for 20000 digits. Use nat_test.go's BenchmarkLeafSize tests to optimize leafSize for specific hardware.

func (nat) div

func (z nat) div(z2, u, v nat) (q, r nat)

func (nat) divBasic

func (q nat) divBasic(u, v nat)

divBasic performs word-by-word division of u by v. The quotient is written in pre-allocated q. The remainder overwrites input u.

Precondition: - q is large enough to hold the quotient u / v

which has a maximum length of len(u)-len(v)+1.

func (nat) divLarge

func (z nat) divLarge(u, uIn, vIn nat) (q, r nat)

q = (uIn-r)/vIn, with 0 <= r < vIn Uses z as storage for q, and u as storage for r if possible. See Knuth, Volume 2, section 4.3.1, Algorithm D. Preconditions:

len(vIn) >= 2
len(uIn) >= len(vIn)
u must not alias z

func (nat) divRecursive

func (z nat) divRecursive(u, v nat)

divRecursive performs word-by-word division of u by v. The quotient is written in pre-allocated z. The remainder overwrites input u.

Precondition: - len(z) >= len(u)-len(v)

See Burnikel, Ziegler, "Fast Recursive Division", Algorithm 1 and 2.

func (nat) divRecursiveStep

func (z nat) divRecursiveStep(u, v nat, depth int, tmp *nat, temps []*nat)

divRecursiveStep computes the division of u by v. - z must be large enough to hold the quotient - the quotient will overwrite z - the remainder will overwrite u

func (nat) divW

func (z nat) divW(x nat, y Word) (q nat, r Word)

q = (x-r)/y, with 0 <= r < y

func (nat) expNN

func (z nat) expNN(x, y, m nat) nat

If m != 0 (i.e., len(m) != 0), expNN sets z to x**y mod m; otherwise it sets z to x**y. The result is the value of z.

func (nat) expNNMontgomery

func (z nat) expNNMontgomery(x, y, m nat) nat

expNNMontgomery calculates x**y mod m using a fixed, 4-bit window. Uses Montgomery representation.

func (nat) expNNWindowed

func (z nat) expNNWindowed(x, y, m nat) nat

expNNWindowed calculates x**y mod m using a fixed, 4-bit window.

func (nat) expWW

func (z nat) expWW(x, y Word) nat

expWW computes x**y

func (nat) itoa

func (x nat) itoa(neg bool, base int) []byte

itoa is like utoa but it prepends a '-' if neg && x != 0.

func (nat) make

func (z nat) make(n int) nat

func (nat) modW

func (x nat) modW(d Word) (r Word)

modW returns x % d.

func (nat) montgomery

func (z nat) montgomery(x, y, m nat, k Word, n int) nat

montgomery computes z mod m = x*y*2**(-n*_W) mod m, assuming k = -1/m mod 2**_W. z is used for storing the result which is returned; z must not alias x, y or m. See Gueron, "Efficient Software Implementations of Modular Exponentiation". https://eprint.iacr.org/2011/239.pdf In the terminology of that paper, this is an "Almost Montgomery Multiplication": x and y are required to satisfy 0 <= z < 2**(n*_W) and then the result z is guaranteed to satisfy 0 <= z < 2**(n*_W), but it may not be < m.

func (nat) mul

func (z nat) mul(x, y nat) nat

func (nat) mulAddWW

func (z nat) mulAddWW(x nat, y, r Word) nat

func (nat) mulRange

func (z nat) mulRange(a, b uint64) nat

mulRange computes the product of all the unsigned integers in the range [a, b] inclusively. If a > b (empty range), the result is 1.

func (nat) norm

func (z nat) norm() nat

func (nat) or

func (z nat) or(x, y nat) nat

func (nat) probablyPrimeLucas

func (n nat) probablyPrimeLucas() bool

probablyPrimeLucas reports whether n passes the "almost extra strong" Lucas probable prime test, using Baillie-OEIS parameter selection. This corresponds to "AESLPSP" on Jacobsen's tables (link below). The combination of this test and a Miller-Rabin/Fermat test with base 2 gives a Baillie-PSW test.

References:

Baillie and Wagstaff, "Lucas Pseudoprimes", Mathematics of Computation 35(152), October 1980, pp. 1391-1417, especially page 1401. https://www.ams.org/journals/mcom/1980-35-152/S0025-5718-1980-0583518-6/S0025-5718-1980-0583518-6.pdf

Grantham, "Frobenius Pseudoprimes", Mathematics of Computation 70(234), March 2000, pp. 873-891. https://www.ams.org/journals/mcom/2001-70-234/S0025-5718-00-01197-2/S0025-5718-00-01197-2.pdf

Baillie, "Extra strong Lucas pseudoprimes", OEIS A217719, https://oeis.org/A217719.

Jacobsen, "Pseudoprime Statistics, Tables, and Data", http://ntheory.org/pseudoprimes.html.

Nicely, "The Baillie-PSW Primality Test", http://www.trnicely.net/misc/bpsw.html. (Note that Nicely's definition of the "extra strong" test gives the wrong Jacobi condition, as pointed out by Jacobsen.)

Crandall and Pomerance, Prime Numbers: A Computational Perspective, 2nd ed. Springer, 2005.

func (nat) probablyPrimeMillerRabin

func (n nat) probablyPrimeMillerRabin(reps int, force2 bool) bool

probablyPrimeMillerRabin reports whether n passes reps rounds of the Miller-Rabin primality test, using pseudo-randomly chosen bases. If force2 is true, one of the rounds is forced to use base 2. See Handbook of Applied Cryptography, p. 139, Algorithm 4.24. The number n is known to be non-zero.

func (nat) random

func (z nat) random(rand *rand.Rand, limit nat, n int) nat

random creates a random integer in [0..limit), using the space in z if possible. n is the bit length of limit.

func (nat) scan

func (z nat) scan(r io.ByteScanner, base int, fracOk bool) (res nat, b, count int, err error)

scan scans the number corresponding to the longest possible prefix from r representing an unsigned number in a given conversion base. scan returns the corresponding natural number res, the actual base b, a digit count, and a read or syntax error err, if any.

For base 0, an underscore character “_” may appear between a base prefix and an adjacent digit, and between successive digits; such underscores do not change the value of the number, or the returned digit count. Incorrect placement of underscores is reported as an error if there are no other errors. If base != 0, underscores are not recognized and thus terminate scanning like any other character that is not a valid radix point or digit.

number    = mantissa | prefix pmantissa .
prefix    = "0" [ "b" | "B" | "o" | "O" | "x" | "X" ] .
mantissa  = digits "." [ digits ] | digits | "." digits .
pmantissa = [ "_" ] digits "." [ digits ] | [ "_" ] digits | "." digits .
digits    = digit { [ "_" ] digit } .
digit     = "0" ... "9" | "a" ... "z" | "A" ... "Z" .

Unless fracOk is set, the base argument must be 0 or a value between 2 and MaxBase. If fracOk is set, the base argument must be one of 0, 2, 8, 10, or 16. Providing an invalid base argument leads to a run- time panic.

For base 0, the number prefix determines the actual base: A prefix of “0b” or “0B” selects base 2, “0o” or “0O” selects base 8, and “0x” or “0X” selects base 16. If fracOk is false, a “0” prefix (immediately followed by digits) selects base 8 as well. Otherwise, the selected base is 10 and no prefix is accepted.

If fracOk is set, a period followed by a fractional part is permitted. The result value is computed as if there were no period present; and the count value is used to determine the fractional part.

For bases <= 36, lower and upper case letters are considered the same: The letters 'a' to 'z' and 'A' to 'Z' represent digit values 10 to 35. For bases > 36, the upper case letters 'A' to 'Z' represent the digit values 36 to 61.

A result digit count > 0 corresponds to the number of (non-prefix) digits parsed. A digit count <= 0 indicates the presence of a period (if fracOk is set, only), and -count is the number of fractional digits found. In this case, the actual value of the scanned number is res * b**count.

func (nat) set

func (z nat) set(x nat) nat

func (nat) setBit

func (z nat) setBit(x nat, i uint, b uint) nat

func (nat) setBytes

func (z nat) setBytes(buf []byte) nat

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

func (nat) setUint64

func (z nat) setUint64(x uint64) nat

func (nat) setWord

func (z nat) setWord(x Word) nat

func (nat) shl

func (z nat) shl(x nat, s uint) nat

z = x << s

func (nat) shr

func (z nat) shr(x nat, s uint) nat

z = x >> s

func (nat) sqr

func (z nat) sqr(x nat) nat

z = x*x

func (nat) sqrt

func (z nat) sqrt(x nat) nat

sqrt sets z = ⌊√x⌋

func (nat) sticky

func (x nat) sticky(i uint) uint

sticky returns 1 if there's a 1 bit within the i least significant bits, otherwise it returns 0.

func (nat) sub

func (z nat) sub(x, y nat) nat

func (nat) trailingZeroBits

func (x nat) trailingZeroBits() uint

trailingZeroBits returns the number of consecutive least significant zero bits of x.

func (nat) utoa

func (x nat) utoa(base int) []byte

utoa converts x to an ASCII representation in the given base; base must be between 2 and MaxBase, inclusive.

func (nat) xor

func (z nat) xor(x, y nat) nat