PACKAGE DOCUMENTATION package big import "math/big" 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.2) // z2 := 6/5 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: package big_test import ( "fmt" "math/big" ) // Use the classic continued fraction for e // e = [1; 0, 1, 1, 2, 1, 1, ... 2n, 1, 1, ...] // i.e., for the nth term, use // 1 if n mod 3 != 1 // (n-1)/3 * 2 if n mod 3 == 1 func recur(n, lim int64) *big.Rat { term := new(big.Rat) if n%3 != 1 { term.SetInt64(1) } else { term.SetInt64((n - 1) / 3 * 2) } if n > lim { return term } // Directly initialize frac as the fractional // inverse of the result of recur. frac := new(big.Rat).Inv(recur(n+1, lim)) return term.Add(term, frac) } // 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). func Example_eConvergents() { for i := 1; i <= 15; i++ { r := recur(0, int64(i)) // Print r both as a fraction and as a floating-point number. // Since big.Rat implements fmt.Formatter, we can use %-13s to // get a left-aligned string representation of the fraction. fmt.Printf("%-13s = %s\n", r, r.FloatString(8)) } // Output: // 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: // Initialize two big ints with the first two numbers in the sequence. a := big.NewInt(0) b := big.NewInt(1) // Initialize limit as 10^99, the smallest integer with 100 digits. var limit big.Int limit.Exp(big.NewInt(10), big.NewInt(99), nil) // Loop while a is smaller than 1e100. for a.Cmp(&limit) < 0 { // Compute the next Fibonacci number, storing it in a. a.Add(a, b) // Swap a and b so that b is the next number in the sequence. a, b = b, a } fmt.Println(a) // 100-digit Fibonacci number // Test a for primality. // (ProbablyPrimes' argument sets the number of Miller-Rabin // rounds to be performed. 20 is a good value.) fmt.Println(a.ProbablyPrime(20)) // Output: // 1344719667586153181419716641724567886890850696275767987106294472017884974410332069524504824747437757 // false Example: // We'll do computations with 200 bits of precision in the mantissa. const prec = 200 // Compute the square root of 2 using Newton's Method. We start with // an initial estimate for sqrt(2), and then iterate: // x_{n+1} = 1/2 * ( x_n + (2.0 / x_n) ) // Since Newton's Method doubles the number of correct digits at each // iteration, we need at least log_2(prec) steps. steps := int(math.Log2(prec)) // Initialize values we need for the computation. two := new(big.Float).SetPrec(prec).SetInt64(2) half := new(big.Float).SetPrec(prec).SetFloat64(0.5) // Use 1 as the initial estimate. x := new(big.Float).SetPrec(prec).SetInt64(1) // We use t as a temporary variable. There's no need to set its precision // since big.Float values with unset (== 0) precision automatically assume // the largest precision of the arguments when used as the result (receiver) // of a big.Float operation. t := new(big.Float) // Iterate. for i := 0; i <= steps; i++ { t.Quo(two, x) // t = 2.0 / x_n t.Add(x, t) // t = x_n + (2.0 / x_n) x.Mul(half, t) // x_{n+1} = 0.5 * t } // We can use the usual fmt.Printf verbs since big.Float implements fmt.Formatter fmt.Printf("sqrt(2) = %.50f\n", x) // Print the error between 2 and x*x. t.Mul(x, x) // t = x*x fmt.Printf("error = %e\n", t.Sub(two, t)) // Output: // sqrt(2) = 1.41421356237309504880168872420969807856967187537695 // error = 0.000000e+00 CONSTANTS const ( // Compute the size _S of a Word in bytes. _m = ^Word(0) _logS = _m>>8&1 + _m>>16&1 + _m>>32&1 _S = 1 << _logS _W = _S << 3 // word size in bits _B = 1 << _W // digit base _M = _B - 1 // digit mask _W2 = _W / 2 // half word size in bits _B2 = 1 << _W2 // half digit base _M2 = _B2 - 1 // half digit mask ) const ( MaxExp = math.MaxInt32 // largest supported exponent MinExp = math.MinInt32 // smallest supported exponent MaxPrec = math.MaxUint32 // largest (theoretically) supported precision; likely memory-limited ) Exponent and precision limits. const MaxBase = 'z' - 'a' + 10 + 1 MaxBase is the largest number base accepted for string conversions. const _Accuracy_name = "BelowExactAbove" const _RoundingMode_name = "ToNearestEvenToNearestAwayToZeroAwayFromZeroToNegativeInfToPositiveInf" const deBruijn32 = 0x077CB531 const deBruijn64 = 0x03f79d71b4ca8b09 const debugFloat = false // enable for debugging const digits = "0123456789abcdefghijklmnopqrstuvwxyz" const intGobVersion byte = 1 Gob codec version. Permits backward-compatible changes to the encoding. const maxShift = _W - 4 Maximum shift amount that can be done in one pass without overflow. A Word has _W bits and (1< (y1<<_W + y2) 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(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(n int) int karatsubaLen computes an approximation to the maximum k <= n such that k = p<= 0. Thus, the result is the largest number that can be divided repeatedly by 2 before becoming about the value of karatsubaThreshold. func karatsubaSub(z, x nat, n int) Like karatsubaAdd, but does subtract. func log2(x Word) int log2 computes the integer binary logarithm of x. The result is the integer n for which 2^n <= x < 2^(n+1). If x == 0, the result is -1. func low32(z nat) uint32 low32 returns the least significant 32 bits of z. func low64(z nat) uint64 low64 returns the least significant 64 bits of z. func max(x, y int) int func min(x, y int) int func msb32(x nat) uint32 msb32 returns the 32 most significant bits of x. func msb64(x nat) uint64 msb64 returns the 64 most significant bits of x. func mulAddWWW_g(x, y, c Word) (z1, z0 Word) z1<<_W + z0 = x*y + c func mulWW(x, y Word) (z1, z0 Word) implemented in arith_$GOARCH.s func mulWW_g(x, y Word) (z1, z0 Word) z1<<_W + z0 = x*y Adapted from Warren, Hacker's Delight, p. 132. func nlz(x Word) uint nlz returns the number of leading zeros in x. func nlz64(x uint64) uint nlz64 returns the number of leading zeros in x. 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(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(ch rune) bool func roundShortest(d *decimal, x *Float) func scanExponent(r io.ByteScanner, binExpOk bool) (exp int64, base int, err error) scanExponent scans the longest possible prefix of r representing a decimal ('e', 'E') or binary ('p') exponent, if any. It returns the exponent, the exponent base (10 or 2), or a read or syntax error, if any. exponent = ( "E" | "e" | "p" ) [ sign ] digits . sign = "+" | "-" . digits = digit { digit } . digit = "0" ... "9" . A binary exponent is only permitted if binExpOk is set. func scanSign(r io.ByteScanner) (neg bool, err error) 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(x *decimal, s uint) shr implements x >> s, for s <= maxShift. func subWW_g(x, y, c Word) (z1, z0 Word) z1<<_W + z0 = x-y-c, with c == 0 or 1 func trailingZeroBits(x Word) uint trailingZeroBits returns the number of consecutive least significant zero bits of x. func trim(x *decimal) trim cuts off any trailing zeros from x's mantissa; they are meaningless for the value of x. func umax32(x, y uint32) uint32 func validateBinaryOperands(x, y *Float) func writeMultiple(s fmt.State, text string, count int) write count copies of text to s TYPES type Accuracy int8 Accuracy describes the rounding error produced by the most recent operation that generated a Float value, relative to the exact value. const ( Below Accuracy = -1 Exact Accuracy = 0 Above Accuracy = +1 ) Constants describing the Accuracy of a Float. func makeAcc(above bool) Accuracy func (i Accuracy) String() string type ErrNaN struct { msg string } 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. func (err ErrNaN) Error() string type Float struct { prec uint32 mode RoundingMode acc Accuracy form form neg bool mant nat exp int32 } 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. 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 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 (z *Float) Abs(x *Float) *Float Abs sets z to the (possibly rounded) value |x| (the absolute value of x) and returns z. func (x *Float) Acc() Accuracy Acc returns the accuracy of x produced by the most recent operation. 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. BUG(gri) When rounding ToNegativeInf, the sign of Float values rounded to 0 is incorrect. Example: // Operating on numbers of different precision. var x, y, z big.Float x.SetInt64(1000) // x is automatically set to 64bit precision y.SetFloat64(2.718281828) // y is automatically set to 53bit precision z.SetPrec(32) z.Add(&x, &y) fmt.Printf("x = %.10g (%s, prec = %d, acc = %s)\n", &x, x.Text('p', 0), x.Prec(), x.Acc()) fmt.Printf("y = %.10g (%s, prec = %d, acc = %s)\n", &y, y.Text('p', 0), y.Prec(), y.Acc()) fmt.Printf("z = %.10g (%s, prec = %d, acc = %s)\n", &z, z.Text('p', 0), z.Prec(), z.Acc()) // Output: // 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 (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 (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: inf := math.Inf(1) zero := 0.0 operands := []float64{-inf, -1.2, -zero, 0, +1.2, +inf} fmt.Println(" x y cmp") fmt.Println("---------------") for _, x64 := range operands { x := big.NewFloat(x64) for _, y64 := range operands { y := big.NewFloat(y64) fmt.Printf("%4g %4g %3d\n", x, y, x.Cmp(y)) } fmt.Println() } // Output: // 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 (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 (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 (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 (x *Float) Format(s fmt.State, format rune) Format implements fmt.Formatter. It accepts all the regular formats for floating-point numbers ('e', 'E', 'f', 'F', 'g', 'G') as well as 'b', 'p', and 'v'. See (*Float).Text for the interpretation of 'b' and '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 verbs '+' and ' ' for sign control, '0' for space or zero padding, and '-' for left or right justification. See the fmt package for details. 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 (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 (x *Float) IsInf() bool IsInf reports whether x is +Inf or -Inf. func (x *Float) IsInt() bool IsInt reports whether x is an integer. ±Inf values are not integers. 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 (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 (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 (x *Float) Mode() RoundingMode Mode returns the rounding mode of x. 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 (z *Float) Neg(x *Float) *Float Neg sets z to the (possibly rounded) value of x with its sign negated, and returns z. 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. 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. If z's precision is 0, it is changed to 64 before rounding takes effect. The number must be of the form: number = [ sign ] [ prefix ] mantissa [ exponent ] | infinity . sign = "+" | "-" . prefix = "0" ( "x" | "X" | "b" | "B" ) . mantissa = digits | digits "." [ digits ] | "." digits . exponent = ( "E" | "e" | "p" ) [ sign ] digits . digits = digit { digit } . digit = "0" ... "9" | "a" ... "z" | "A" ... "Z" . infinity = [ sign ] ( "inf" | "Inf" ) . The base argument must be 0, 2, 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 "0x" or "0X" selects base 16, and a "0b" or "0B" prefix selects base 2; 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" exponent indicates a binary (rather then decimal) exponent; for instance "0x1.fffffffffffffp1023" (using base 0) represents the maximum float64 value. For hexadecimal mantissae, the exponent must be binary, 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 (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 (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 (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 (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 (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 (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 (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 (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 (z *Float) SetMantExp(mant *Float, exp int) *Float SetMantExp sets z to mant × 2**exp and 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 (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 (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 (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 (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. 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 (x *Float) Sign() int Sign returns: -1 if x < 0 0 if x is ±0 +1 if x > 0 func (x *Float) Signbit() bool Signbit returns true if x is negative or negative zero. 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 (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 (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 'b' -ddddddp±dd, binary exponent 'p' -0x.dddp±dd, binary exponent, hexadecimal mantissa For the binary exponent formats, the mantissa is printed in normalized form: 'b' decimal integer mantissa using x.Prec() bits, or -0 'p' hexadecimal fraction with 0.5 <= 0.mantissa < 1.0, or -0 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', and 'G' formats. For 'e', 'E', and 'f' 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' or 'p' format. 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 (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 (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. 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, ad 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. 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 (z *Float) pow5(n uint64) *Float pow5 sets z to 5**n and returns z. n must not be negative. 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 (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 (z *Float) setBits64(neg bool, x uint64) *Float func (z *Float) setExpAndRound(exp int64, sbit uint) 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 (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 (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 (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 (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 (x *Float) validate() debugging support type Int struct { neg bool // sign abs nat // absolute value of the integer } An Int represents a signed multi-precision integer. The zero value for an Int represents the value 0. func NewInt(x int64) *Int NewInt allocates and returns a new Int set to x. func scaleDenom(x *Int, f nat) *Int scaleDenom computes x*f. If f == 0 (zero value of denominator), the result is (a copy of) x. func (z *Int) Abs(x *Int) *Int Abs sets z to |x| (the absolute value of x) and returns z. func (z *Int) Add(x, y *Int) *Int Add sets z to the sum x+y and returns z. func (z *Int) And(x, y *Int) *Int And sets z = x & y and returns z. func (z *Int) AndNot(x, y *Int) *Int AndNot sets z = x &^ y and returns z. 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 (z *Int) Binomial(n, k int64) *Int Binomial sets z to the binomial coefficient of (n, k) and returns z. 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 (x *Int) BitLen() int BitLen returns the length of the absolute value of x in bits. The bit length of 0 is 0. 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 (x *Int) Bytes() []byte Bytes returns the absolute value of x as a big-endian byte slice. 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 (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 (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 (z *Int) Exp(x, y, m *Int) *Int Exp sets z = x**y mod |m| (i.e. the sign of m is ignored), and returns z. If y <= 0, the result is 1 mod |m|; if m == nil or m == 0, z = x**y. See Knuth, volume 2, section 4.6.3. func (x *Int) Format(s fmt.State, ch rune) Format is a support routine for fmt.Formatter. It accepts the formats 'b' (binary), 'o' (octal), 'd' (decimal), 'x' (lowercase hexadecimal), and 'X' (uppercase hexadecimal). Also supported are the full suite of package fmt's format verbs for integral types, including '+', '-', and ' ' for sign control, '#' for leading zero in octal and for hexadecimal, a leading "0x" or "0X" for "%#x" and "%#X" respectively, specification of minimum digits precision, output field width, space or zero padding, and left or right justification. func (z *Int) GCD(x, y, a, b *Int) *Int GCD sets z to the greatest common divisor of a and b, which both must be > 0, and returns z. If x and y are not nil, GCD sets x and y such that z = a*x + b*y. If either a or b is <= 0, GCD sets z = x = y = 0. func (z *Int) GobDecode(buf []byte) error GobDecode implements the gob.GobDecoder interface. func (x *Int) GobEncode() ([]byte, error) GobEncode implements the gob.GobEncoder interface. 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 (z *Int) Lsh(x *Int, n uint) *Int Lsh sets z = x << n and returns z. func (x *Int) MarshalJSON() ([]byte, error) MarshalJSON implements the json.Marshaler interface. func (x *Int) MarshalText() (text []byte, err error) MarshalText implements the encoding.TextMarshaler interface. 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 (z *Int) ModInverse(g, n *Int) *Int ModInverse sets z to the multiplicative inverse of g in the ring ℤ/nℤ and returns z. If g and n are not relatively prime, the result is undefined. func (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 (z *Int) Mul(x, y *Int) *Int Mul sets z to the product x*y and returns z. 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 (z *Int) Neg(x *Int) *Int Neg sets z to -x and returns z. func (z *Int) Not(x *Int) *Int Not sets z = ^x and returns z. func (z *Int) Or(x, y *Int) *Int Or sets z = x | y and returns z. func (x *Int) ProbablyPrime(n int) bool ProbablyPrime performs n Miller-Rabin tests to check whether x is prime. If x is prime, it returns true. If x is not prime, it returns false with probability at least 1 - ¼ⁿ. It is not suitable for judging primes that an adversary may have crafted to fool this test. 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 (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 (z *Int) Rand(rnd *rand.Rand, n *Int) *Int Rand sets z to a pseudo-random number in [0, n) and returns z. 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 (z *Int) Rsh(x *Int, n uint) *Int Rsh sets z = x >> n and returns z. 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: // The Scan function is rarely used directly; // the fmt package recognizes it as an implementation of fmt.Scanner. i := new(big.Int) _, err := fmt.Sscan("18446744073709551617", i) if err != nil { log.Println("error scanning value:", err) } else { fmt.Println(i) } // Output: 18446744073709551617 func (z *Int) Set(x *Int) *Int Set sets z to x and returns z. 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 (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 (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 (z *Int) SetInt64(x int64) *Int SetInt64 sets z to x and returns z. func (z *Int) SetString(s string, base int) (*Int, bool) SetString sets z to the value of s, interpreted in the given base, and returns z and a boolean indicating success. If SetString fails, the value of z is undefined but the returned value is nil. The base argument must be 0 or a value between 2 and MaxBase. If the base is 0, the string prefix determines the actual conversion base. A prefix of ``0x'' or ``0X'' selects base 16; the ``0'' prefix selects base 8, and a ``0b'' or ``0B'' prefix selects base 2. Otherwise the selected base is 10. Example: i := new(big.Int) i.SetString("644", 8) // octal fmt.Println(i) // Output: 420 func (z *Int) SetUint64(x uint64) *Int SetUint64 sets z to x and returns z. func (x *Int) Sign() int Sign returns: -1 if x < 0 0 if x == 0 +1 if x > 0 func (x *Int) String() string func (z *Int) Sub(x, y *Int) *Int Sub sets z to the difference x-y and returns z. func (x *Int) Text(base int) string Text returns the string representation of x in the given base. Base must be between 2 and 36, inclusive. The result uses the lower-case letters 'a' to 'z' for digit values >= 10. No base prefix (such as "0x") is added to the string. 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 (z *Int) UnmarshalJSON(text []byte) error UnmarshalJSON implements the json.Unmarshaler interface. func (z *Int) UnmarshalText(text []byte) error UnmarshalText implements the encoding.TextUnmarshaler interface. func (z *Int) Xor(x, y *Int) *Int Xor sets z = x ^ y and returns z. func (z *Int) binaryGCD(a, b *Int) *Int binaryGCD sets z to the greatest common divisor of a and b, which both must be > 0, and returns z. See Knuth, The Art of Computer Programming, Vol. 2, Section 4.5.2, Algorithm B. 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 (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 (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 ``0x'' or ``0X'' selects base 16; the ``0'' prefix selects base 8, and a ``0b'' or ``0B'' prefix selects base 2. Otherwise the selected base is 10. 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. // a.neg determines the sign of the Rat, b.neg is ignored. a, b Int } A Rat represents a quotient a/b of arbitrary precision. The zero value for a Rat represents the value 0. func NewRat(a, b int64) *Rat NewRat creates a new Rat with numerator a and denominator b. func (z *Rat) Abs(x *Rat) *Rat Abs sets z to |x| (the absolute value of x) and returns z. func (z *Rat) Add(x, y *Rat) *Rat Add sets z to the sum x+y and returns z. 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 (x *Rat) Denom() *Int Denom returns the denominator of x; it is always > 0. The result is a reference to x's denominator; it may change if a new value is assigned to x, and vice versa. func (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 (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 (x *Rat) FloatString(prec int) string FloatString returns a string representation of x in decimal form with prec digits of precision after the decimal point. The last digit is rounded to nearest, with halves rounded away from zero. func (z *Rat) GobDecode(buf []byte) error GobDecode implements the gob.GobDecoder interface. func (x *Rat) GobEncode() ([]byte, error) GobEncode implements the gob.GobEncoder interface. func (z *Rat) Inv(x *Rat) *Rat Inv sets z to 1/x and returns z. func (x *Rat) IsInt() bool IsInt reports whether the denominator of x is 1. func (x *Rat) MarshalText() (text []byte, err error) MarshalText implements the encoding.TextMarshaler interface. func (z *Rat) Mul(x, y *Rat) *Rat Mul sets z to the product x*y and returns z. func (z *Rat) Neg(x *Rat) *Rat Neg sets z to -x and returns z. 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 (z *Rat) Quo(x, y *Rat) *Rat Quo sets z to the quotient x/y and returns z. If y == 0, a division-by-zero run-time panic occurs. func (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 (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: // The Scan function is rarely used directly; // the fmt package recognizes it as an implementation of fmt.Scanner. r := new(big.Rat) _, err := fmt.Sscan("1.5000", r) if err != nil { log.Println("error scanning value:", err) } else { fmt.Println(r) } // Output: 3/2 func (z *Rat) Set(x *Rat) *Rat Set sets z to x (by making a copy of x) and returns z. 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 (z *Rat) SetFrac(a, b *Int) *Rat SetFrac sets z to a/b and returns z. func (z *Rat) SetFrac64(a, b int64) *Rat SetFrac64 sets z to a/b and returns z. func (z *Rat) SetInt(x *Int) *Rat SetInt sets z to x (by making a copy of x) and returns z. func (z *Rat) SetInt64(x int64) *Rat SetInt64 sets z to x and returns z. func (z *Rat) SetString(s string) (*Rat, bool) SetString sets z to the value of s and returns z and a boolean indicating success. s can be given as a fraction "a/b" or as a floating-point number optionally followed by an exponent. If the operation failed, the value of z is undefined but the returned value is nil. Example: r := new(big.Rat) r.SetString("355/113") fmt.Println(r.FloatString(3)) // Output: 3.142 func (x *Rat) Sign() int Sign returns: -1 if x < 0 0 if x == 0 +1 if x > 0 func (x *Rat) String() string String returns a string representation of x in the form "a/b" (even if b == 1). func (z *Rat) Sub(x, y *Rat) *Rat Sub sets z to the difference x-y and returns z. func (z *Rat) UnmarshalText(text []byte) error UnmarshalText implements the encoding.TextUnmarshaler interface. func (z *Rat) norm() *Rat type RoundingMode byte 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. 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 ) These constants define supported rounding modes. func (i RoundingMode) String() string type Word uintptr A Word represents a single digit of a multi-precision unsigned integer. func addMulVVW(z, x []Word, y Word) (c Word) func addMulVVW_g(z, x []Word, y Word) (c Word) TODO(gri) Remove use of addWW_g here and then we can remove addWW_g and subWW_g. func addVV(z, x, y []Word) (c Word) func addVV_g(z, x, y []Word) (c Word) The resulting carry c is either 0 or 1. func addVW(z, x []Word, y Word) (c Word) func addVW_g(z, x []Word, y Word) (c Word) The resulting carry c is either 0 or 1. 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 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 mulAddVWW(z, x []Word, y, r Word) (c Word) func mulAddVWW_g(z, x []Word, y, r Word) (c Word) func pow(x Word, n int) (p Word) pow returns x**n for n > 0, and 1 otherwise. 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) The resulting carry c is either 0 or 1. func subVW(z, x []Word, y Word) (c Word) func subVW_g(z, x []Word, y Word) (c Word) type byteReader struct { fmt.ScanState } byteReader is a local wrapper around fmt.ScanState; it implements the ByteReader interface. func (r byteReader) ReadByte() (byte, error) func (r byteReader) UnreadByte() error type decimal struct { mant []byte // mantissa ASCII digits, big-endian exp int // exponent } 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.5 <= 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. func (x *decimal) String() string func (d *decimal) at(i int) byte at returns the i'th mantissa digit, starting with the most significant digit at 0. 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 (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 (x *decimal) roundDown(n int) func (x *decimal) roundUp(n int) 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 } type form byte A form value describes the internal representation. const ( zero form = iota finite inf ) The form value order is relevant - do not change! type nat []Word 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). 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 (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 bit returns the value of the i'th bit, with lsb == bit 0. func (x nat) bitLen() int Length of x in bits. x must be normalized. func (z nat) bytes(buf []byte) (i int) bytes writes the value of z into buf using big-endian encoding. len(buf) must be >= len(z)*_S. The value of z is encoded in the slice buf[i:]. The number i of unused bytes at the beginning of buf is returned as result. 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) 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 (z nat) div(z2, u, v nat) (q, r nat) func (z nat) divLarge(u, uIn, v nat) (q, r nat) q = (uIn-r)/v, with 0 <= r < y 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(v) >= 2 len(uIn) >= len(v) func (z nat) divW(x nat, y Word) (q nat, r Word) q = (x-r)/y, with 0 <= r < y 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 (z nat) expNNMontgomery(x, y, m nat) nat expNNMontgomery calculates x**y mod m using a fixed, 4-bit window. Uses Montgomery representation. func (z nat) expNNWindowed(x, y, m nat) nat expNNWindowed calculates x**y mod m using a fixed, 4-bit window. func (z nat) expWW(x, y Word) nat expWW computes x**y func (x nat) itoa(neg bool, base int) []byte itoa is like utoa but it prepends a '-' if neg && x != 0. func (z nat) make(n int) nat func (x nat) modW(d Word) (r Word) modW returns x % d. 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 (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 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 (z nat) norm() nat func (z nat) or(x, y nat) nat func (n nat) probablyPrime(reps int) bool probablyPrime performs n Miller-Rabin tests to check whether x is prime. If x is prime, it returns true. If x is not prime, it returns false with probability at least 1 - ¼ⁿ. It is not suitable for judging primes that an adversary may have crafted to fool this test. 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 (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. It returns the corresponding natural number res, the actual base b, a digit count, and a read or syntax error err, if any. number = [ prefix ] mantissa . prefix = "0" [ "x" | "X" | "b" | "B" ] . mantissa = 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, 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 ``0x'' or ``0X'' selects base 16; if fracOk is not set, the ``0'' prefix selects base 8, and a ``0b'' or ``0B'' prefix selects base 2. Otherwise the selected base is 10 and no prefix is accepted. If fracOk is set, an octal prefix is ignored (a leading ``0'' simply stands for a zero digit), and 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. 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 (z nat) set(x nat) nat func (z nat) setBit(x nat, i uint, b uint) nat 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 (z nat) setUint64(x uint64) nat func (z nat) setWord(x Word) nat func (z nat) shl(x nat, s uint) nat z = x << s func (z nat) shr(x nat, s uint) nat z = x >> s 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 (z nat) sub(x, y nat) nat func (x nat) trailingZeroBits() uint trailingZeroBits returns the number of consecutive least significant zero bits of x. 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 (z nat) xor(x, y nat) nat BUGS When rounding ToNegativeInf, the sign of Float values rounded to 0 is incorrect.