Involved Source Filesaccuracy_string.goarith.goarith_amd64.goarith_decl.godecimal.go 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 [fmt.Scanner] for scanning
and (except for *Rat) the Formatter interface for formatted printing.float.gofloatconv.gofloatmarsh.goftoa.goint.gointconv.gointmarsh.gonat.gonatconv.gonatdiv.goprime.gorat.goratconv.goratmarsh.goroundingmode_string.gosqrt.goarith_amd64.s
Code Examples
package main
import (
"fmt"
"log"
"math/big"
)
func main() {
// The Scan function is rarely used directly;
// the fmt package recognizes it as an implementation of fmt.Scanner.
f := new(big.Float)
_, err := fmt.Sscan("1.19282e99", f)
if err != nil {
log.Println("error scanning value:", err)
} else {
fmt.Println(f)
}
}
package main
import (
"fmt"
"math/big"
)
func main() {
f := new(big.Float)
f.SetString("3.14159")
fmt.Println(f)
}
package main
import (
"fmt"
"log"
"math/big"
)
func main() {
// 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)
}
}
package main
import (
"fmt"
"math/big"
)
func main() {
i := new(big.Int)
i.SetString("644", 8) // octal
fmt.Println(i)
}
package main
import (
"fmt"
"log"
"math/big"
)
func main() {
// 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)
}
}
package main
import (
"fmt"
"math/big"
)
func main() {
r := new(big.Rat)
r.SetString("355/113")
fmt.Println(r.FloatString(3))
}
package main
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 main() {
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))
}
}
package main
import (
"fmt"
"math/big"
)
func main() {
// 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))
}
package main
import (
"fmt"
"math"
"math/big"
)
func main() {
// 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))
}
Package-Level Type Names (total 12, in which 7 are exported)
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.msgstring( ErrNaN) Error() string
ErrNaN : error
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.accAccuracyexpint32formformmantnatmodeRoundingModenegboolprecuint32 Abs sets z to the (possibly rounded) value |x| (the absolute value of x)
and returns z. Acc returns the accuracy of x produced by the most recent
operation, unless explicitly documented otherwise by that
operation. 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. Append appends to buf the string form of the floating-point number x,
as generated by x.Text, and returns the extended buffer. 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 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. 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. 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. 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. 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. GobEncode implements the gob.GobEncoder interface.
The Float value and all its attributes (precision,
rounding mode, accuracy) are marshaled. 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. 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. IsInf reports whether x is +Inf or -Inf. IsInt reports whether x is an integer.
±Inf values are not integers. 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. MarshalText implements the encoding.TextMarshaler interface.
Only the Float value is marshaled (in full precision), other
attributes such as precision or accuracy are ignored. 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. Mode returns the rounding mode of x. 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. Neg sets z to the (possibly rounded) value of x with its sign negated,
and returns z. 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 than 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. Prec returns the mantissa precision of x in bits.
The result may be 0 for |x| == 0 and |x| == Inf. 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. 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. 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. 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. 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. 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. 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). 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). 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, for a
given x of type *Float, SetMantExp relates to MantExp
as follows:
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. 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. 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. 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. 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. 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). Sign returns:
-1 if x < 0
0 if x is ±0
+1 if x > 0 Signbit reports whether x is negative or negative zero. 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. String formats x like x.Text('g', 10).
(String must be called explicitly, Float.Format does not support %s verb.) 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. 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. 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. 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. 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.) 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.) 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.) 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 pow5 sets z to 5**n and returns z.
n must not be negative. 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. 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.(*Float) setBits64(neg bool, x uint64) *Float(*Float) setExpAndRound(exp int64, sbit uint) Compute √x (to z.prec precision) by solving
1/t² - x = 0
for t (using Newton's method), and then inverting. 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. 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. 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. 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. 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. debugging support(*Float) validate0() string
*Float : encoding.TextMarshaler
*Float : encoding.TextUnmarshaler
*Float : fmt.Formatter
*Float : fmt.Scanner
*Float : fmt.Stringer
*Float : context.stringer
*Float : runtime.stringer
func NewFloat(x float64) *Float
func ParseFloat(s string, base int, prec uint, mode RoundingMode) (f *Float, b int, err error)
func (*Float).Abs(x *Float) *Float
func (*Float).Add(x, y *Float) *Float
func (*Float).Copy(x *Float) *Float
func (*Float).Mul(x, y *Float) *Float
func (*Float).Neg(x *Float) *Float
func (*Float).Parse(s string, base int) (f *Float, b int, err error)
func (*Float).Quo(x, y *Float) *Float
func (*Float).Set(x *Float) *Float
func (*Float).SetFloat64(x float64) *Float
func (*Float).SetInf(signbit bool) *Float
func (*Float).SetInt(x *Int) *Float
func (*Float).SetInt64(x int64) *Float
func (*Float).SetMantExp(mant *Float, exp int) *Float
func (*Float).SetMode(mode RoundingMode) *Float
func (*Float).SetPrec(prec uint) *Float
func (*Float).SetRat(x *Rat) *Float
func (*Float).SetString(s string) (*Float, bool)
func (*Float).SetUint64(x uint64) *Float
func (*Float).Sqrt(x *Float) *Float
func (*Float).Sub(x, y *Float) *Float
func github.com/go-faster/jx.(*Decoder).BigFloat() (*Float, error)
func newFloat(prec2 uint32) *Float
func three() *Float
func (*Float).pow5(n uint64) *Float
func (*Float).scan(r io.ByteScanner, base int) (f *Float, b int, err error)
func (*Float).setBits64(neg bool, x uint64) *Float
func (*Float).Abs(x *Float) *Float
func (*Float).Add(x, y *Float) *Float
func (*Float).Cmp(y *Float) int
func (*Float).Copy(x *Float) *Float
func (*Float).MantExp(mant *Float) (exp int)
func (*Float).Mul(x, y *Float) *Float
func (*Float).Neg(x *Float) *Float
func (*Float).Quo(x, y *Float) *Float
func (*Float).Set(x *Float) *Float
func (*Float).SetMantExp(mant *Float, exp int) *Float
func (*Float).Sqrt(x *Float) *Float
func (*Float).Sub(x, y *Float) *Float
func roundShortest(d *decimal, x *Float)
func validateBinaryOperands(x, y *Float)
func (*Float).sqrtInverse(x *Float)
func (*Float).uadd(x, y *Float)
func (*Float).ucmp(y *Float) int
func (*Float).umul(x, y *Float)
func (*Float).uquo(x, y *Float)
func (*Float).usub(x, y *Float)
var floatZero
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.
Note that methods may leak the Int's value through timing side-channels.
Because of this and because of the scope and complexity of the
implementation, Int is not well-suited to implement cryptographic operations.
The standard library avoids exposing non-trivial Int methods to
attacker-controlled inputs and the determination of whether a bug in math/big
is considered a security vulnerability might depend on the impact on the
standard library. // absolute value of the integer // sign Abs sets z to |x| (the absolute value of x) and returns z. Add sets z to the sum x+y and returns z. And sets z = x & y and returns z. AndNot sets z = x &^ y and returns z. Append appends the string representation of x, as generated by
x.Text(base), to buf and returns the extended buffer. Binomial sets z to the binomial coefficient C(n, k) and returns z. 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. BitLen returns the length of the absolute value of x in bits.
The bit length of 0 is 0. 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. 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. Cmp compares x and y and returns:
-1 if x < y
0 if x == y
+1 if x > y CmpAbs compares the absolute values of x and y and returns:
-1 if |x| < |y|
0 if |x| == |y|
+1 if |x| > |y| 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. 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). 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. 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. Float64 returns the float64 value nearest x,
and an indication of any rounding that occurred. 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. 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. GobDecode implements the gob.GobDecoder interface. GobEncode implements the gob.GobEncoder interface. Int64 returns the int64 representation of x.
If x cannot be represented in an int64, the result is undefined. IsInt64 reports whether x can be represented as an int64. IsUint64 reports whether x can be represented as a uint64. Lsh sets z = x << n and returns z. MarshalJSON implements the json.Marshaler interface. MarshalText implements the encoding.TextMarshaler interface. 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. 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. If n == 0, a division-by-zero run-time panic occurs. 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, its behavior is undefined if p is odd but not prime. Mul sets z to the product x*y and returns z. 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. Neg sets z to -x and returns z. Not sets z = ^x and returns z. Or sets z = x | y and returns z. 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. 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. 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). 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. 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. Rsh sets z = x >> n and returns z. 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). Set sets z to x and returns z. 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. 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. SetBytes interprets buf as the bytes of a big-endian unsigned
integer, sets z to that value, and returns z. SetInt64 sets z to x and returns z. 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. SetUint64 sets z to x and returns z. Sign returns:
-1 if x < 0
0 if x == 0
+1 if x > 0 Sqrt sets z to ⌊√x⌋, the largest integer such that z² ≤ x, and returns z.
It panics if x is negative. String returns the decimal representation of x as generated by
x.Text(10). Sub sets z to the difference x-y and returns z. 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>". TrailingZeroBits returns the number of consecutive least significant zero
bits of |x|. Uint64 returns the uint64 representation of x.
If x cannot be represented in a uint64, the result is undefined. UnmarshalJSON implements the json.Unmarshaler interface. UnmarshalText implements the encoding.TextUnmarshaler interface. Xor sets z = x ^ y and returns z.(*Int) exp(x, y, m *Int, slow bool) *Int(*Int) expSlow(x, y, m *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. 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. modSqrt5Mod8Prime 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. modSqrtTonelliShanks uses the Tonelli-Shanks algorithm to find the square
root of a quadratic residue modulo any prime. scaleDenom sets z to the product x*f.
If f == 0 (zero value of denominator), z is set to (a copy of) x. 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. setFromScanner implements SetString given an io.ByteScanner.
For documentation see comments of SetString.
*Int : encoding.TextMarshaler
*Int : encoding.TextUnmarshaler
*Int : encoding/json.Marshaler
*Int : encoding/json.Unmarshaler
*Int : fmt.Formatter
*Int : fmt.Scanner
*Int : fmt.Stringer
*Int : context.stringer
*Int : runtime.stringer
func NewInt(x int64) *Int
func (*Float).Int(z *Int) (*Int, Accuracy)
func (*Int).Abs(x *Int) *Int
func (*Int).Add(x, y *Int) *Int
func (*Int).And(x, y *Int) *Int
func (*Int).AndNot(x, y *Int) *Int
func (*Int).Binomial(n, k int64) *Int
func (*Int).Div(x, y *Int) *Int
func (*Int).DivMod(x, y, m *Int) (*Int, *Int)
func (*Int).DivMod(x, y, m *Int) (*Int, *Int)
func (*Int).Exp(x, y, m *Int) *Int
func (*Int).GCD(x, y, a, b *Int) *Int
func (*Int).Lsh(x *Int, n uint) *Int
func (*Int).Mod(x, y *Int) *Int
func (*Int).ModInverse(g, n *Int) *Int
func (*Int).ModSqrt(x, p *Int) *Int
func (*Int).Mul(x, y *Int) *Int
func (*Int).MulRange(a, b int64) *Int
func (*Int).Neg(x *Int) *Int
func (*Int).Not(x *Int) *Int
func (*Int).Or(x, y *Int) *Int
func (*Int).Quo(x, y *Int) *Int
func (*Int).QuoRem(x, y, r *Int) (*Int, *Int)
func (*Int).QuoRem(x, y, r *Int) (*Int, *Int)
func (*Int).Rand(rnd *rand.Rand, n *Int) *Int
func (*Int).Rem(x, y *Int) *Int
func (*Int).Rsh(x *Int, n uint) *Int
func (*Int).Set(x *Int) *Int
func (*Int).SetBit(x *Int, i int, b uint) *Int
func (*Int).SetBits(abs []Word) *Int
func (*Int).SetBytes(buf []byte) *Int
func (*Int).SetInt64(x int64) *Int
func (*Int).SetString(s string, base int) (*Int, bool)
func (*Int).SetUint64(x uint64) *Int
func (*Int).Sqrt(x *Int) *Int
func (*Int).Sub(x, y *Int) *Int
func (*Int).Xor(x, y *Int) *Int
func (*Rat).Denom() *Int
func (*Rat).Num() *Int
func crypto/dsa.Sign(rand io.Reader, priv *dsa.PrivateKey, hash []byte) (r, s *Int, err error)
func crypto/ecdsa.Sign(rand io.Reader, priv *ecdsa.PrivateKey, hash []byte) (r, s *Int, err error)
func crypto/elliptic.GenerateKey(curve elliptic.Curve, rand io.Reader) (priv []byte, x, y *Int, err error)
func crypto/elliptic.Unmarshal(curve elliptic.Curve, data []byte) (x, y *Int)
func crypto/elliptic.UnmarshalCompressed(curve elliptic.Curve, data []byte) (x, y *Int)
func crypto/elliptic.Curve.Add(x1, y1, x2, y2 *Int) (x, y *Int)
func crypto/elliptic.Curve.Double(x1, y1 *Int) (x, y *Int)
func crypto/elliptic.Curve.ScalarBaseMult(k []byte) (x, y *Int)
func crypto/elliptic.Curve.ScalarMult(x1, y1 *Int, k []byte) (x, y *Int)
func crypto/elliptic.(*CurveParams).Add(x1, y1, x2, y2 *Int) (*Int, *Int)
func crypto/elliptic.(*CurveParams).Add(x1, y1, x2, y2 *Int) (*Int, *Int)
func crypto/elliptic.(*CurveParams).Double(x1, y1 *Int) (*Int, *Int)
func crypto/elliptic.(*CurveParams).Double(x1, y1 *Int) (*Int, *Int)
func crypto/elliptic.(*CurveParams).ScalarBaseMult(k []byte) (*Int, *Int)
func crypto/elliptic.(*CurveParams).ScalarBaseMult(k []byte) (*Int, *Int)
func crypto/elliptic.(*CurveParams).ScalarMult(Bx, By *Int, k []byte) (*Int, *Int)
func crypto/elliptic.(*CurveParams).ScalarMult(Bx, By *Int, k []byte) (*Int, *Int)
func crypto/internal/boring/bbig.Dec(b boring.BigInt) *Int
func crypto/rand.Int(rand io.Reader, max *Int) (n *Int, err error)
func crypto/rand.Prime(rand io.Reader, bits int) (*Int, error)
func github.com/go-faster/jx.(*Decoder).BigInt() (*Int, error)
func github.com/gotd/td/bin.Int128.BigInt() *Int
func github.com/gotd/td/bin.Int256.BigInt() *Int
func github.com/gotd/td/internal/crypto.DecomposePQ(pq *Int, randSource io.Reader) (p, q *Int, err error)
func github.com/gotd/td/internal/exchange.ServerRNG.DhPrime() (p *Int, err error)
func github.com/gotd/td/internal/exchange.ServerRNG.GA(g int, dhPrime *Int) (a, ga *Int, err error)
func github.com/gotd/td/internal/exchange.ServerRNG.PQ() (pq *Int, err error)
func github.com/gotd/td/internal/exchange.TestServerRNG.DhPrime() (p *Int, err error)
func github.com/gotd/td/internal/exchange.TestServerRNG.GA(g int, dhPrime *Int) (a, ga *Int, err error)
func github.com/gotd/td/internal/exchange.TestServerRNG.PQ() (pq *Int, err error)
func (*Int).exp(x, y, m *Int, slow bool) *Int
func (*Int).expSlow(x, y, m *Int) *Int
func (*Int).lehmerGCD(x, y, a, b *Int) *Int
func (*Int).modSqrt3Mod4Prime(x, p *Int) *Int
func (*Int).modSqrt5Mod8Prime(x, p *Int) *Int
func (*Int).modSqrtTonelliShanks(x, p *Int) *Int
func (*Int).scan(r io.ByteScanner, base int) (*Int, int, error)
func (*Int).setFromScanner(r io.ByteScanner, base int) (*Int, bool)
func crypto/dsa.fermatInverse(k, P *Int) *Int
func crypto/ecdsa.hashToInt(hash []byte, c elliptic.Curve) *Int
func crypto/ecdsa.randFieldElement(c elliptic.Curve, rand io.Reader) (k *Int, err error)
func crypto/elliptic.bigFromDecimal(s string) *Int
func crypto/elliptic.bigFromHex(s string) *Int
func crypto/elliptic.zForAffine(x, y *Int) *Int
func crypto/elliptic.(*CurveParams).addJacobian(x1, y1, z1, x2, y2, z2 *Int) (*Int, *Int, *Int)
func crypto/elliptic.(*CurveParams).addJacobian(x1, y1, z1, x2, y2, z2 *Int) (*Int, *Int, *Int)
func crypto/elliptic.(*CurveParams).addJacobian(x1, y1, z1, x2, y2, z2 *Int) (*Int, *Int, *Int)
func crypto/elliptic.(*CurveParams).affineFromJacobian(x, y, z *Int) (xOut, yOut *Int)
func crypto/elliptic.(*CurveParams).doubleJacobian(x, y, z *Int) (*Int, *Int, *Int)
func crypto/elliptic.(*CurveParams).doubleJacobian(x, y, z *Int) (*Int, *Int, *Int)
func crypto/elliptic.(*CurveParams).doubleJacobian(x, y, z *Int) (*Int, *Int, *Int)
func crypto/elliptic.(*CurveParams).polynomial(x *Int) *Int
func encoding/asn1.parseBigInt(bytes []byte) (*Int, error)
func github.com/gotd/td/internal/crypto/srp.SRP.bigExp(x, y, m *Int) *Int
func github.com/gotd/td/internal/crypto/srp.SRP.bigFromBytes(b []byte) *Int
func github.com/gotd/td/internal/crypto/srp.SRP.computeXV(password, clientSalt, serverSalt []byte, g, p *Int) (x, v *Int)
func github.com/gotd/td/internal/exchange.TestServerRNG.bigFromHex(hexString string) (p *Int, err error)
func Jacobi(x, y *Int) int
func (*Float).Int(z *Int) (*Int, Accuracy)
func (*Float).SetInt(x *Int) *Float
func (*Int).Abs(x *Int) *Int
func (*Int).Add(x, y *Int) *Int
func (*Int).And(x, y *Int) *Int
func (*Int).AndNot(x, y *Int) *Int
func (*Int).Cmp(y *Int) (r int)
func (*Int).CmpAbs(y *Int) int
func (*Int).Div(x, y *Int) *Int
func (*Int).DivMod(x, y, m *Int) (*Int, *Int)
func (*Int).Exp(x, y, m *Int) *Int
func (*Int).GCD(x, y, a, b *Int) *Int
func (*Int).Lsh(x *Int, n uint) *Int
func (*Int).Mod(x, y *Int) *Int
func (*Int).ModInverse(g, n *Int) *Int
func (*Int).ModSqrt(x, p *Int) *Int
func (*Int).Mul(x, y *Int) *Int
func (*Int).Neg(x *Int) *Int
func (*Int).Not(x *Int) *Int
func (*Int).Or(x, y *Int) *Int
func (*Int).Quo(x, y *Int) *Int
func (*Int).QuoRem(x, y, r *Int) (*Int, *Int)
func (*Int).Rand(rnd *rand.Rand, n *Int) *Int
func (*Int).Rem(x, y *Int) *Int
func (*Int).Rsh(x *Int, n uint) *Int
func (*Int).Set(x *Int) *Int
func (*Int).SetBit(x *Int, i int, b uint) *Int
func (*Int).Sqrt(x *Int) *Int
func (*Int).Sub(x, y *Int) *Int
func (*Int).Xor(x, y *Int) *Int
func (*Rat).SetFrac(a, b *Int) *Rat
func (*Rat).SetInt(x *Int) *Rat
func crypto/dsa.Verify(pub *dsa.PublicKey, hash []byte, r, s *Int) bool
func crypto/ecdsa.Verify(pub *ecdsa.PublicKey, hash []byte, r, s *Int) bool
func crypto/elliptic.Marshal(curve elliptic.Curve, x, y *Int) []byte
func crypto/elliptic.MarshalCompressed(curve elliptic.Curve, x, y *Int) []byte
func crypto/elliptic.Curve.Add(x1, y1, x2, y2 *Int) (x, y *Int)
func crypto/elliptic.Curve.Double(x1, y1 *Int) (x, y *Int)
func crypto/elliptic.Curve.IsOnCurve(x, y *Int) bool
func crypto/elliptic.Curve.ScalarMult(x1, y1 *Int, k []byte) (x, y *Int)
func crypto/elliptic.(*CurveParams).Add(x1, y1, x2, y2 *Int) (*Int, *Int)
func crypto/elliptic.(*CurveParams).Double(x1, y1 *Int) (*Int, *Int)
func crypto/elliptic.(*CurveParams).IsOnCurve(x, y *Int) bool
func crypto/elliptic.(*CurveParams).ScalarMult(Bx, By *Int, k []byte) (*Int, *Int)
func crypto/internal/bigmod.NewModulusFromBig(n *Int) (*bigmod.Modulus, error)
func crypto/internal/boring/bbig.Enc(b *Int) boring.BigInt
func crypto/rand.Int(rand io.Reader, max *Int) (n *Int, err error)
func github.com/gotd/td/internal/crypto.CheckDH(g int, p *Int) error
func github.com/gotd/td/internal/crypto.CheckDHParams(dhPrime, g, gA, gB *Int) error
func github.com/gotd/td/internal/crypto.CheckGP(g int, p *Int) error
func github.com/gotd/td/internal/crypto.DecomposePQ(pq *Int, randSource io.Reader) (p, q *Int, err error)
func github.com/gotd/td/internal/crypto.FillBytes(b *Int, to []byte) bool
func github.com/gotd/td/internal/crypto.InRange(x, min, max *Int) bool
func github.com/gotd/td/internal/crypto.Prime(p *Int) bool
func github.com/gotd/td/internal/crypto.TempAESKeys(newNonce, serverNonce *Int) (key, iv []byte)
func github.com/gotd/td/internal/exchange.ServerRNG.GA(g int, dhPrime *Int) (a, ga *Int, err error)
func github.com/gotd/td/internal/exchange.TestServerRNG.GA(g int, dhPrime *Int) (a, ga *Int, err error)
func vendor/golang.org/x/crypto/cryptobyte.(*Builder).AddASN1BigInt(n *Int)
func euclidUpdate(A, B, Ua, Ub, q, r, s, t *Int, extended bool)
func lehmerSimulate(A, B *Int) (u0, u1, v0, v1 Word, even bool)
func lehmerUpdate(A, B, q, r, s, t *Int, u0, u1, v0, v1 Word, even bool)
func (*Int).exp(x, y, m *Int, slow bool) *Int
func (*Int).expSlow(x, y, m *Int) *Int
func (*Int).lehmerGCD(x, y, a, b *Int) *Int
func (*Int).modSqrt3Mod4Prime(x, p *Int) *Int
func (*Int).modSqrt5Mod8Prime(x, p *Int) *Int
func (*Int).modSqrtTonelliShanks(x, p *Int) *Int
func (*Int).scaleDenom(x *Int, f nat)
func crypto/dsa.fermatInverse(k, P *Int) *Int
func crypto/ecdsa.bigIntEqual(a, b *Int) bool
func crypto/elliptic.panicIfNotOnCurve(curve elliptic.Curve, x, y *Int)
func crypto/elliptic.zForAffine(x, y *Int) *Int
func crypto/elliptic.(*CurveParams).addJacobian(x1, y1, z1, x2, y2, z2 *Int) (*Int, *Int, *Int)
func crypto/elliptic.(*CurveParams).affineFromJacobian(x, y, z *Int) (xOut, yOut *Int)
func crypto/elliptic.(*CurveParams).doubleJacobian(x, y, z *Int) (*Int, *Int, *Int)
func crypto/elliptic.(*CurveParams).polynomial(x *Int) *Int
func crypto/internal/bigmod.(*Nat).setBig(n *Int) *bigmod.Nat
func crypto/rsa.bigIntEqual(a, b *Int) bool
func encoding/asn1.makeBigInt(n *Int) (asn1.encoder, error)
func github.com/gotd/td/internal/crypto.checkPrime(p *Int) error
func github.com/gotd/td/internal/crypto.checkSubgroup(p *Int, divider int64, expected ...int64) bool
func github.com/gotd/td/internal/crypto.sha1BigInt(a, b *Int) []byte
func github.com/gotd/td/internal/crypto/srp.checkInput(g int, p *Int) error
func github.com/gotd/td/internal/crypto/srp.SRP.bigExp(x, y, m *Int) *Int
func github.com/gotd/td/internal/crypto/srp.SRP.computeXV(password, clientSalt, serverSalt []byte, g, p *Int) (x, v *Int)
func github.com/gotd/td/internal/crypto/srp.SRP.pad256FromBig(i *Int) (b [256]byte, r bool)
func vendor/golang.org/x/crypto/cryptobyte.(*String).readASN1BigInt(out *Int) bool
var intOne *Int
var crypto/ecdsa.one *Int
var crypto/rsa.bigOne *Int
var encoding/asn1.bigOne *Int
var vendor/golang.org/x/crypto/cryptobyte.bigOne *Int
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. 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. 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. Abs sets z to |x| (the absolute value of x) and returns z. Add sets z to the sum x+y and returns z. Cmp compares x and y and returns:
-1 if x < y
0 if x == y
+1 if x > y 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. 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. 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. 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. GobDecode implements the gob.GobDecoder interface. GobEncode implements the gob.GobEncoder interface. Inv sets z to 1/x and returns z.
If x == 0, Inv panics. IsInt reports whether the denominator of x is 1. MarshalText implements the encoding.TextMarshaler interface. Mul sets z to the product x*y and returns z. Neg sets z to -x and returns z. 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. Quo sets z to the quotient x/y and returns z.
If y == 0, Quo panics. RatString returns a string representation of x in the form "a/b" if b != 1,
and in the form "a" if b == 1. Scan is a support routine for fmt.Scanner. It accepts the formats
'e', 'E', 'f', 'F', 'g', 'G', and 'v'. All formats are equivalent. Set sets z to x (by making a copy of x) and returns z. SetFloat64 sets z to exactly f and returns z.
If f is not finite, SetFloat returns nil. SetFrac sets z to a/b and returns z.
If b == 0, SetFrac panics. SetFrac64 sets z to a/b and returns z.
If b == 0, SetFrac64 panics. SetInt sets z to x (by making a copy of x) and returns z. SetInt64 sets z to x and returns z. 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). If the exponent's absolute value
is too large, the operation may fail.
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. SetUint64 sets z to x and returns z. Sign returns:
-1 if x < 0
0 if x == 0
+1 if x > 0 String returns a string representation of x in the form "a/b" (even if b == 1). Sub sets z to the difference x-y and returns z. UnmarshalText implements the encoding.TextUnmarshaler interface. marshal implements String returning a slice of bytes(*Rat) norm() *Rat
*Rat : encoding.TextMarshaler
*Rat : encoding.TextUnmarshaler
*Rat : fmt.Scanner
*Rat : fmt.Stringer
*Rat : context.stringer
*Rat : runtime.stringer
func NewRat(a, b int64) *Rat
func (*Float).Rat(z *Rat) (*Rat, Accuracy)
func (*Rat).Abs(x *Rat) *Rat
func (*Rat).Add(x, y *Rat) *Rat
func (*Rat).Inv(x *Rat) *Rat
func (*Rat).Mul(x, y *Rat) *Rat
func (*Rat).Neg(x *Rat) *Rat
func (*Rat).Quo(x, y *Rat) *Rat
func (*Rat).Set(x *Rat) *Rat
func (*Rat).SetFloat64(f float64) *Rat
func (*Rat).SetFrac(a, b *Int) *Rat
func (*Rat).SetFrac64(a, b int64) *Rat
func (*Rat).SetInt(x *Int) *Rat
func (*Rat).SetInt64(x int64) *Rat
func (*Rat).SetString(s string) (*Rat, bool)
func (*Rat).SetUint64(x uint64) *Rat
func (*Rat).Sub(x, y *Rat) *Rat
func (*Rat).norm() *Rat
func (*Float).Rat(z *Rat) (*Rat, Accuracy)
func (*Float).SetRat(x *Rat) *Float
func (*Rat).Abs(x *Rat) *Rat
func (*Rat).Add(x, y *Rat) *Rat
func (*Rat).Cmp(y *Rat) int
func (*Rat).Inv(x *Rat) *Rat
func (*Rat).Mul(x, y *Rat) *Rat
func (*Rat).Neg(x *Rat) *Rat
func (*Rat).Quo(x, y *Rat) *Rat
func (*Rat).Set(x *Rat) *Rat
func (*Rat).Sub(x, y *Rat) *Rat
var ratZero
A Word represents a single digit of a multi-precision unsigned integer.
func (*Int).Bits() []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 divWW(x1, x0, y, m Word) (q, r Word)
func lehmerSimulate(A, B *Int) (u0, u1, v0, v1 Word, even bool)
func maxPow(b Word) (p Word, n int)
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 pow(x Word, n int) (p Word)
func reciprocalWord(d1 Word) 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)
func (*Int).SetBits(abs []Word) *Int
func addMulVVW(z, x []Word, y Word) (c Word)
func addMulVVW(z, x []Word, y Word) (c Word)
func addMulVVW_g(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(z, x []Word, y Word) (c Word)
func addVW_g(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 addVWlarge(z, x []Word, y Word) (c Word)
func divisors(m int, b Word, ndigits int, bb Word) []divisor
func divisors(m int, b Word, ndigits int, bb Word) []divisor
func divWVW(z []Word, xn Word, x []Word, y Word) (r Word)
func divWVW(z []Word, xn Word, x []Word, y Word) (r Word)
func divWVW(z []Word, xn Word, x []Word, y Word) (r Word)
func divWVW(z []Word, xn Word, x []Word, y Word) (r Word)
func divWW(x1, x0, y, m Word) (q, r Word)
func greaterThan(x1, x2, y1, y2 Word) bool
func lehmerUpdate(A, B, q, r, s, t *Int, u0, u1, v0, v1 Word, even bool)
func maxPow(b Word) (p Word, n int)
func mulAddVWW(z, x []Word, y, r Word) (c Word)
func mulAddVWW(z, x []Word, y, r Word) (c Word)
func mulAddVWW_g(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 nlz(x Word) uint
func pow(x Word, n int) (p Word)
func reciprocalWord(d1 Word) 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(z, x []Word, y Word) (c Word)
func subVW_g(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)
func subVWlarge(z, x []Word, y Word) (c Word)
byteReader is a local wrapper around fmt.ScanState;
it implements the ByteReader interface.ScanStatefmt.ScanState Because ReadRune is implemented by the interface, Read should never be
called by the scanning routines and a valid implementation of
ScanState may choose always to return an error from Read.( byteReader) ReadByte() (byte, error) ReadRune reads the next rune (Unicode code point) from the input.
If invoked during Scanln, Fscanln, or Sscanln, ReadRune() will
return EOF after returning the first '\n' or when reading beyond
the specified width. SkipSpace skips space in the input. Newlines are treated appropriately
for the operation being performed; see the package documentation
for more information. Token skips space in the input if skipSpace is true, then returns the
run of Unicode code points c satisfying f(c). If f is nil,
!unicode.IsSpace(c) is used; that is, the token will hold non-space
characters. Newlines are treated appropriately for the operation being
performed; see the package documentation for more information.
The returned slice points to shared data that may be overwritten
by the next call to Token, a call to a Scan function using the ScanState
as input, or when the calling Scan method returns.( byteReader) UnreadByte() error UnreadRune causes the next call to ReadRune to return the same rune. Width returns the value of the width option and whether it has been set.
The unit is Unicode code points.
byteReader : compress/flate.Reader
byteReader : fmt.ScanState
byteReader : github.com/klauspost/compress/flate.Reader
byteReader : io.ByteReader
byteReader : io.ByteScanner
byteReader : io.Reader
byteReader : io.RuneReader
byteReader : io.RuneScanner
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. // exponent // mantissa ASCII digits, big-endian(*decimal) String() string at returns the i'th mantissa digit, starting with the most significant digit at 0. Init initializes x to the decimal representation of m << shift (for
shift >= 0), or m >> -shift (for shift < 0). 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.(*decimal) roundDown(n int)(*decimal) roundUp(n int)
*decimal : fmt.Stringer
*decimal : context.stringer
*decimal : runtime.stringer
func fmtE(buf []byte, fmt byte, prec int, d decimal) []byte
func fmtF(buf []byte, prec int, d decimal) []byte
func roundShortest(d *decimal, x *Float)
func shouldRoundUp(x *decimal, n int) bool
func shr(x *decimal, s uint)
func trim(x *decimal)
// divisor // bit length of divisor (discounting leading zeros) ~= log2(bbb) // digit length of divisor in terms of output base digits
func divisors(m int, b Word, ndigits int, bb Word) []divisor
A form value describes the internal representation.
const finite
const inf
const zero
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).( nat) String() string( nat) add(x, y nat) nat( nat) and(x, y nat) nat( nat) andNot(x, y nat) nat bit returns the value of the i'th bit, with lsb == bit 0. bitLen returns the length of x in bits.
Unlike most methods, it works even if x is not normalized. 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.( nat) clear()( nat) cmp(y nat) (r int) 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. div returns q, r such that q = ⌊u/v⌋ and r = u%v = u - q·v.
It uses z and z2 as the storage for q and r. divBasic implements long division as described above.
It overwrites q with ⌊u/v⌋ and overwrites u with the remainder r.
q must be large enough to hold ⌊u/v⌋. div returns q, r such that q = ⌊uIn/vIn⌋ and r = uIn%vIn = uIn - q·vIn.
It uses z and u as the storage for q and r.
The caller must ensure that len(vIn) ≥ 2 (use divW otherwise)
and that len(uIn) ≥ len(vIn) (the answer is 0, uIn otherwise). divRecursive implements recursive division as described above.
It overwrites z with ⌊u/v⌋ and overwrites u with the remainder r.
z must be large enough to hold ⌊u/v⌋.
This function is just for allocating and freeing temporaries
around divRecursiveStep, the real implementation. divRecursiveStep is the actual implementation of recursive division.
It adds ⌊u/v⌋ to z and overwrites u with the remainder r.
z must be large enough to hold ⌊u/v⌋.
It uses temps[depth] (allocating if needed) as a temporary live across
the recursive call. It also uses tmp, but not live across the recursion. divW returns q, r such that q = ⌊x/y⌋ and r = x%y = x - q·y.
It uses z as the storage for q.
Note that y is a single digit (Word), not a big number. 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. expNNMontgomery calculates x**y mod m using a fixed, 4-bit window.
Uses Montgomery representation. expNNMontgomeryEven calculates x**y mod m where m = m1 × m2 for m1 = 2ⁿ and m2 odd.
It uses two recursive calls to expNN for x**y mod m1 and x**y mod m2
and then uses the Chinese Remainder Theorem to combine the results.
The recursive call using m1 will use expNNWindowed,
while the recursive call using m2 will use expNNMontgomery.
For more details, see Ç. K. Koç, “Montgomery Reduction with Even Modulus”,
IEE Proceedings: Computers and Digital Techniques, 141(5) 314-316, September 1994.
http://www.people.vcu.edu/~jwang3/CMSC691/j34monex.pdf expNNWindowed calculates x**y mod m using a fixed, 4-bit window,
where m = 2**logM. expWW computes x**y isPow2 returns i, true when x == 2**i and 0, false otherwise. itoa is like utoa but it prepends a '-' if neg && x != 0.( nat) make(n int) nat( nat) modInverse(g, n nat) nat modW returns x % d. 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.( nat) mul(x, y nat) nat( nat) mulAddWW(x nat, y, r Word) 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.( nat) norm() nat( nat) or(x, y nat) nat 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", https://web.archive.org/web/20191121062007/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. 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. random creates a random integer in [0..limit), using the space in z if
possible. n is the bit length of limit. rem returns r such that r = u%v.
It uses z as the storage for r. 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.( nat) set(x nat) nat( nat) setBit(x nat, i uint, b uint) nat setBytes interprets buf as the bytes of a big-endian unsigned
integer, sets z to that value, and returns z.( nat) setUint64(x uint64) nat( nat) setWord(x Word) nat z = x << s z = x >> s z = x*x sqrt sets z = ⌊√x⌋ sticky returns 1 if there's a 1 bit within the
i least significant bits, otherwise it returns 0.( nat) sub(x, y nat) nat subMod2N returns z = (x - y) mod 2ⁿ. trailingZeroBits returns the number of consecutive least significant zero
bits of x. trunc returns z = x mod 2ⁿ. utoa converts x to an ASCII representation in the given base;
base must be between 2 and MaxBase, inclusive.( nat) xor(x, y nat) nat
nat : fmt.Stringer
nat : context.stringer
nat : runtime.stringer
func getNat(n int) *nat
func mulDenom(z, x, y nat) nat
func addAt(z, x nat, i int)
func alias(x, y nat) bool
func basicMul(z, x, y nat)
func basicSqr(z, x nat)
func fnorm(m nat) int64
func karatsuba(z, x, y nat)
func karatsubaAdd(z, x nat, n int)
func karatsubaSqr(z, x nat)
func karatsubaSub(z, x nat, n int)
func low32(x nat) uint32
func low64(x nat) uint64
func msb32(x nat) uint32
func msb64(x nat) uint64
func mulDenom(z, x, y nat) nat
func putNat(x *nat)
func quotToFloat32(a, b nat) (f float32, exact bool)
func quotToFloat64(a, b nat) (f float64, exact bool)
func same(x, y nat) bool
func (*Int).scaleDenom(x *Int, f nat)
var natFive
var natOne
var natTen
var natTwo
Package-Level Functions (total 75, in which 5 are exported)
Jacobi returns the Jacobi symbol (x/y), either +1, -1, or 0.
The y argument must be an odd integer.
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.
NewInt allocates and returns a new Int set to x.
NewRat creates a new Rat with numerator a and denominator b.
ParseFloat is like f.Parse(s, base) with f set to the given precision
and rounding mode.
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)
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.
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).
appendZeros appends n 0 digits to buf and returns buf.
basicMul multiplies x and y and leaves the result in z.
The (non-normalized) result is placed in z[0 : len(x) + len(y)].
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.
bigEndianWord returns the contents of buf interpreted as a big-endian encoded Word value.
construct table of powers of bb*leafSize to use in subdivisions.
divWVW overwrites z with ⌊x/y⌋, returning the remainder r.
The caller must ensure that len(z) = len(x).
q = ( x1 << _W + x0 - r)/y. m = floor(( _B^2 - 1 ) / d - _B). Requiring x1<y.
An approximate reciprocal with a reference to "Improved Division by Invariant Integers
(IEEE Transactions on Computers, 11 Jun. 2010)"
euclidUpdate performs a single step of the Euclidean GCD algorithm
if extended is true, it also updates the cosequence Ua, Ub.
%e: d.ddddde±dd
%f: ddddddd.ddddd
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.
getNat returns a *nat of len n. The contents may not be zero.
The pool holds *nat to avoid allocation when converting to interface{}.
greaterThan reports whether the two digit numbers x1 x2 > y1 y2.
TODO(rsc): In contradiction to most of this file, x1 is the high
digit and x2 is the low digit. This should be fixed.
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].
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.
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.
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.
Like karatsubaAdd, but does subtract.
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
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.
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.
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.
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.
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.
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.
Operands that are shorter than karatsubaThreshold are multiplied using
"grade school" multiplication; for longer operands the Karatsuba algorithm
is used.
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
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.
Gob codec version. Permits backward-compatible changes to the encoding.
The form value order is relevant - do not change!
The pages are generated with Goldsv0.6.7. (GOOS=linux GOARCH=amd64)
Golds is a Go 101 project developed by Tapir Liu.
PR and bug reports are welcome and can be submitted to the issue list.
Please follow @Go100and1 (reachable from the left QR code) to get the latest news of Golds.
