README
¶
Gmp
This package provides a drop in replacement for Go's built in math/big big integer package using the GNU Multiprecision Library (GMP).
GMP is very much faster than Go's math/big however it is an external C library with all the problems that entails (cgo, dependencies etc)
This library was made by taking the cgo example of wrapping GMP from the Go source and doing the following to it
- Copying the implementation from misc/cgo/gmp/gmp.go
- Copying the documentation from src/pkg/math/big/int.go
- Additional implementation of missing methods
- Bug fixes for existing implementations
- Making it passes the test suite from src/pkg/math/big/int_test.go
- Adding memory management
- Fix problems on 32 bit platforms when using
int64values which don't fit into aC.long - Implementing Rat support making it pass src/pkg/math/big/rat_test.go
See here for package docs
Install
Use go to install the library
go get github.com/ncw/gmp
Usage
See here for full package docs
To use as in a drop in replacement for math/big, replace
import "math/big"
With
import big "github.com/ncw/gmp"
Features that aren't part of math/big are clearly marked and if you are using those, then I suggest you import as
import "github.com/ncw/gmp"
Testing
To run the tests use
go test github.com/ncw/gmp
The tests have been copied from the tests for the math/big library in the Go source and modified as little as possible so it should be 100% compatible.
Differences
Here are the differences between math/big and this package
Int.BitsandInt.SetBitsnot implementedRat.Num()andRat.Denom()return a copy not a reference, so- If you want to set them use the new methods
Rat.SetNum()andRat.SetDenom()
License
As this contains a great deal of code copied from the Go source it is licenced identically to the Go source itself - see the LICENSE file for details.
Contact and support
The project website is at:
There you can file bug reports, ask for help or contribute patches.
Authors
- The Go team
- Nick Craig-Wood nick@craig-wood.com
Documentation
¶
Overview ¶
Package gmp implements multi-precision arithmetic (big numbers).
This package provides a drop in replacement for Go's built in math/big integer package using the GNU Multiprecision Library (GMP) to implement the operations.
GMP is very much faster than Go's math/big however it is an external C library with all the problems that entails (cgo, dependencies etc)
The following numeric types are supported:
- Int signed integers - Rat rational numbers are NOT yet supported
Methods are typically of the form:
func (z *Int) Op(x, y *Int) *Int (similar for *Rat)
and implement operations z = x Op y with the result as receiver; if it is one of the operands it may be overwritten (and its memory reused). To enable chaining of operations, the result is also returned. Methods returning a result other than *Int or *Rat take one of the operands as the receiver.
Index ¶
- type Int
- func (z *Int) Abs(x *Int) *Int
- func (z *Int) Add(x, y *Int) *Int
- func (z *Int) AddMul(x, y *Int) *Int
- func (z *Int) AddMulUint32(x *Int, y uint32) *Int
- func (z *Int) AddUint32(x *Int, y uint32) *Int
- func (z *Int) And(x, y *Int) *Int
- func (z *Int) AndNot(x, y *Int) *Int
- func (z *Int) Binomial(n, k int64) *Int
- func (z *Int) Bit(i int) uint
- func (z *Int) BitLen() int
- func (z *Int) Bytes() []byte
- func (z *Int) Clear()
- func (z *Int) Cmp(y *Int) (r int)
- func (z *Int) CmpAbs(x *Int) int
- func (z *Int) CmpAbsUint32(x uint32) int
- func (z *Int) CmpInt32(x int32) int
- func (z *Int) CmpUint32(x uint32) int
- func (z *Int) Div(x, y *Int) *Int
- func (z *Int) DivMod(x, y, m *Int) (*Int, *Int)
- func (z *Int) Exp(x, y, m *Int) *Int
- func (z *Int) Format(s fmt.State, ch rune)
- func (z *Int) GCD(x, y, a, b *Int) *Int
- func (z *Int) GobDecode(buf []byte) error
- func (z *Int) GobEncode() ([]byte, error)
- func (z *Int) Int32() int32
- func (z *Int) Int64() (y int64)
- func (z *Int) Lsh(x *Int, n uint) *Int
- func (z *Int) MarshalJSON() ([]byte, error)
- func (z *Int) Mod(x, y *Int) *Int
- func (z *Int) ModInverse(g, p *Int) *Int
- func (z *Int) Mul(x, y *Int) *Int
- func (z *Int) MulInt32(x *Int, y int32) *Int
- func (z *Int) MulRange(a, b int64) *Int
- func (z *Int) MulUint32(x *Int, y uint32) *Int
- func (z *Int) Neg(x *Int) *Int
- func (z *Int) Not(x *Int) *Int
- func (z *Int) Or(x, y *Int) *Int
- func (z *Int) ProbablyPrime(n int) bool
- func (z *Int) Quo(x, y *Int) *Int
- func (z *Int) QuoRem(x, y, r *Int) (*Int, *Int)
- func (z *Int) Rand(rnd *rand.Rand, n *Int) *Int
- func (z *Int) Rem(x, y *Int) *Int
- func (z *Int) Rsh(x *Int, n uint) *Int
- func (z *Int) Scan(s fmt.ScanState, ch rune) error
- func (z *Int) Set(x *Int) *Int
- func (z *Int) SetBit(x *Int, i int, b uint) *Int
- func (z *Int) SetBytes(buf []byte) *Int
- func (z *Int) SetInt64(x int64) *Int
- func (z *Int) SetString(s string, base int) (*Int, bool)
- func (z *Int) SetUint64(x uint64) *Int
- func (z *Int) Sign() int
- func (z *Int) Sqrt(x *Int) *Int
- func (z *Int) String() string
- func (z *Int) Sub(x, y *Int) *Int
- func (z *Int) SubMul(x, y *Int) *Int
- func (z *Int) SubMulUint32(x *Int, y uint32) *Int
- func (z *Int) SubUint32(x *Int, y uint32) *Int
- func (z *Int) Swap(x *Int) *Int
- func (z *Int) Uint32() uint32
- func (z *Int) Uint32Sub(x uint32, y *Int) *Int
- func (z *Int) Uint64() (y uint64)
- func (z *Int) UnmarshalJSON(x []byte) error
- func (z *Int) Xor(x, y *Int) *Int
- type Rat
- func (z *Rat) Abs(x *Rat) *Rat
- func (z *Rat) Add(x, y *Rat) *Rat
- func (z *Rat) Clear()
- func (z *Rat) Cmp(y *Rat) (r int)
- func (z *Rat) Denom() *Int
- func (z *Rat) Float64() (f float64, exact bool)
- func (z *Rat) Float64Gmp() (f float64, exact bool)
- func (z *Rat) FloatString(prec int) string
- func (z *Rat) GobDecode(buf []byte) error
- func (z *Rat) GobEncode() ([]byte, error)
- func (z *Rat) Inv(x *Rat) *Rat
- func (z *Rat) IsInt() bool
- func (z *Rat) Mul(x, y *Rat) *Rat
- func (z *Rat) Neg(x *Rat) *Rat
- func (z *Rat) Num() *Int
- func (z *Rat) Quo(x, y *Rat) *Rat
- func (z *Rat) RatString() string
- func (z *Rat) Scan(s fmt.ScanState, ch rune) error
- func (z *Rat) Set(x *Rat) *Rat
- func (z *Rat) SetDenom(a *Int) *Rat
- func (z *Rat) SetFloat64(f float64) *Rat
- func (z *Rat) SetFrac(a, b *Int) *Rat
- func (z *Rat) SetFrac64(a, b int64) *Rat
- func (z *Rat) SetInt(x *Int) *Rat
- func (z *Rat) SetInt64(x int64) *Rat
- func (z *Rat) SetNum(a *Int) *Rat
- func (z *Rat) SetString(s string) (*Rat, bool)
- func (z *Rat) Sign() int
- func (z *Rat) String() string
- func (z *Rat) Sub(x, y *Rat) *Rat
Examples ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Int ¶
type Int struct {
// contains filtered or unexported fields
}
An Int represents a signed multi-precision integer. The zero value for an Int represents the value 0.
func (*Int) AddMul ¶ added in v1.0.2
AddMul sets z to z + x*y and returns z.
NB This is not part of big.Int
func (*Int) AddMulUint32 ¶ added in v1.0.2
AddMulUint32 sets z to z + x*y and returns z.
NB This is not part of big.Int
func (*Int) AddUint32 ¶ added in v1.0.2
AddUint32 sets z to the sum x+y and returns z.
NB This is not part of big.Int
func (*Int) Bit ¶
Bit returns the value of the i'th bit of z. That is, it returns (z>>i)&1. The bit index i must be >= 0.
func (*Int) BitLen ¶
BitLen returns the length of the absolute value of z in bits. The bit length of 0 is 0.
func (*Int) Clear ¶
func (z *Int) Clear()
Clear the allocated space used by the number
This normally happens on a runtime.SetFinalizer call, but if you want immediate deallocation you can call it.
NB This is not part of big.Int
func (*Int) CmpAbs ¶ added in v1.0.2
CmpAbs compares |z| and |x| and returns:
-1 if |z| < |x| 0 if |z| == |x| +1 if |z| > |x|
NB This is not part of big.Int
func (*Int) CmpAbsUint32 ¶ added in v1.0.2
CmpAbsUint32 compares |z| and |x| and returns:
-1 if |z| < |x| 0 if |z| == |x| +1 if |z| > |x|
NB This is not part of big.Int
func (*Int) CmpInt32 ¶ added in v1.0.2
CmpInt32 compares z and x and returns:
-1 if z < x 0 if z == x +1 if z > x
NB This is not part of big.Int
func (*Int) CmpUint32 ¶ added in v1.0.2
CmpUint32 compares z and x and returns:
-1 if z < x 0 if z == x +1 if z > x
NB This is not part of big.Int
func (*Int) Div ¶
Div sets z to the quotient x/y for y != 0 and returns z. If y == 0, a division-by-zero run-time panic occurs. Div implements Euclidean division (unlike Go); see DivMod for more details.
func (*Int) DivMod ¶
DivMod sets z to the quotient x div y and m to the modulus x mod y and returns the pair (z, m) for y != 0. If y == 0, a division-by-zero run-time panic occurs.
DivMod implements Euclidean division and modulus (unlike Go):
q = x div y such that m = x - y*q with 0 <= m < |q|
(See Raymond T. Boute, “The Euclidean definition of the functions div and mod”. ACM Transactions on Programming Languages and Systems (TOPLAS), 14(2):127-144, New York, NY, USA, 4/1992. ACM press.) See QuoRem for T-division and modulus (like Go).
func (*Int) Exp ¶
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; if m == nil or m == 0, z = x**y. See Knuth, volume 2, section 4.6.3.
func (*Int) Format ¶
Format is a support routine for fmt.Formatter. It accepts the formats 'b' (binary), 'o' (octal), 'd' (decimal), 'x' (lowercase hexadecimal), and 'X' (uppercase hexadecimal). Also supported are the full suite of package fmt's format verbs for integral types, including '+', '-', and ' ' for sign control, '#' for leading zero in octal and for hexadecimal, a leading "0x" or "0X" for "%#x" and "%#X" respectively, specification of minimum digits precision, output field width, space or zero padding, and left or right justification.
func (*Int) GCD ¶
GCD sets z to the greatest common divisor of a and b, which both must be > 0, and returns z. If x and y are not nil, GCD sets x and y such that z = a*x + b*y. If either a or b is <= 0, GCD sets z = x = y = 0.
func (*Int) Int32 ¶ added in v1.0.2
Int32 returns the int32 representation of z, if z fits into a signed int32. If z is too big to fit in a int32 then the result is undefined.
NB This is not part of big.Int
func (*Int) Int64 ¶
Int64 returns the int64 representation of z. If z cannot be represented in an int64, the result is undefined.
func (*Int) MarshalJSON ¶
MarshalJSON implements the json.Marshaler interface.
func (*Int) Mod ¶
Mod sets z to the modulus x%y for y != 0 and returns z. If y == 0, a division-by-zero run-time panic occurs. Mod implements Euclidean modulus (unlike Go); see DivMod for more details.
func (*Int) ModInverse ¶
ModInverse sets z to the multiplicative inverse of g in the group ℤ/pℤ (where p is a prime) and returns z.
func (*Int) MulInt32 ¶ added in v1.0.2
MulInt32 sets z to the product x*y and returns z.
NB This is not part of big.Int
func (*Int) MulRange ¶
MulRange sets z to the product of all integers in the range [a, b] inclusively and returns z. If a > b (empty range), the result is 1.
func (*Int) MulUint32 ¶ added in v1.0.2
MulUint32 sets z to the product x*y and returns z.
NB This is not part of big.Int
func (*Int) ProbablyPrime ¶
ProbablyPrime performs n Miller-Rabin tests to check whether z is prime. If it returns true, z is prime with probability 1 - 1/4^n. If it returns false, z is not prime.
func (*Int) Quo ¶
Quo sets z to the quotient x/y for y != 0 and returns z. If y == 0, a division-by-zero run-time panic occurs. Quo implements truncated division (like Go); see QuoRem for more details.
func (*Int) QuoRem ¶
QuoRem sets z to the quotient x/y and r to the remainder x%y and returns the pair (z, r) for y != 0. If y == 0, a division-by-zero run-time panic occurs.
QuoRem implements T-division and modulus (like Go):
q = x/y with the result truncated to zero r = x - y*q
(See Daan Leijen, “Division and Modulus for Computer Scientists”.) See DivMod for Euclidean division and modulus (unlike Go).
func (*Int) Rem ¶
Rem sets z to the remainder x%y for y != 0 and returns z. If y == 0, a division-by-zero run-time panic occurs. Rem implements truncated modulus (like Go); see QuoRem for more details.
func (*Int) Scan ¶
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(Int)
_, err := fmt.Sscan("18446744073709551617", i)
if err != nil {
log.Println("error scanning value:", err)
} else {
fmt.Println(i)
}
Output: 18446744073709551617
func (*Int) SetBit ¶
SetBit sets z to x, with x's i'th bit set to b (0 or 1). That is, if b is 1 SetBit sets z = x | (1 << i); if b is 0 SetBit sets z = x &^ (1 << i). If b is not 0 or 1, SetBit will panic.
func (*Int) SetBytes ¶
SetBytes interprets buf as the bytes of a big-endian unsigned integer, sets z to that value, and returns z.
func (*Int) SetString ¶
SetString sets z to the value of s, interpreted in the given base, and returns z and a boolean indicating success. If SetString fails, the value of z is undefined but the returned value is nil.
The base argument must be 0 or a value from 2 through MaxBase. If the base is 0, the string prefix determines the actual conversion base. A prefix of “0x” or “0X” selects base 16; the “0” prefix selects base 8, and a “0b” or “0B” prefix selects base 2. Otherwise the selected base is 10.
Example ¶
i := new(Int)
i.SetString("644", 8) // octal
fmt.Println(i)
Output: 420
func (*Int) Sqrt ¶
Sqrt sets x to the truncated integer part of the square root of x
NB This is not part of big.Int
func (*Int) SubMul ¶ added in v1.0.2
SubMul sets z to z - x*y and returns z.
NB This is not part of big.Int
func (*Int) SubMulUint32 ¶ added in v1.0.2
SubMulUint32 sets z to z - x*y and returns z.
NB This is not part of big.Int
func (*Int) SubUint32 ¶ added in v1.0.2
SubUint32 sets z to the difference x-y and returns z.
NB This is not part of big.Int
func (*Int) Swap ¶ added in v1.0.2
Swap exchanges the values of z and x and returns the new z.
NB This is not part of big.Int
func (*Int) Uint32 ¶ added in v1.0.2
Uint32 returns the uint32 representation of z, if z fits into a uint32. If z is too big then the least significant bits that do fit are returned. The sign of z is ignored, only the absolute value is used.
NB This is not part of big.Int
func (*Int) Uint32Sub ¶ added in v1.0.2
Uint32Sub sets z to the difference x-y and returns z.
NB This is not part of big.Int
func (*Int) Uint64 ¶
Uint64 returns the uint64 representation of z. If z cannot be represented in a uint64, the result is undefined.
func (*Int) UnmarshalJSON ¶
UnmarshalJSON implements the json.Unmarshaler interface.
type Rat ¶
type Rat struct {
// contains filtered or unexported fields
}
A Rat represents a quotient a/b of arbitrary precision. The zero value for a Rat represents the value 0.
func (*Rat) Clear ¶
func (z *Rat) Clear()
Clear the allocated space used by the number
This normally happens on a runtime.SetFinalizer call, but if you want immediate deallocation you can call it.
NB This is not part of big.Rat
func (*Rat) Denom ¶
Denom returns the denominator of z; it is always > 0. The result is a copy of z's denominator; it won't change if a new value is assigned to z, and vice versa.
NB In math/big this is a reference to the denominator not a copy
func (*Rat) Float64 ¶
Float64 returns the nearest float64 value for z and a bool indicating whether f represents z exactly. If the magnitude of z 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 z, even if f == 0.
func (*Rat) Float64Gmp ¶
Float64Gmp returns the nearest float64 value for z and a bool indicating whether f represents z exactly. If the magnitude of z 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 z, even if f == 0.
NB This uses GMP which is fast but rounds differently to Float64
func (*Rat) FloatString ¶
FloatString returns a string representation of z in decimal form with prec digits of precision after the decimal point and the last digit rounded.
func (*Rat) Num ¶
Num returns the numerator of z; it may be <= 0. The result is a copy of z's numerator; it won't change if a new value is assigned to z, and vice versa. The sign of the numerator corresponds to the sign of z.
NB In math/big this is a reference to the numerator not a copy
func (*Rat) Quo ¶
Quo sets z to the quotient x/y and returns z. If y == 0, a division-by-zero run-time panic occurs.
func (*Rat) RatString ¶
RatString returns a string representation of z in the form "a/b" if b != 1, and in the form "a" if b == 1.
func (*Rat) Scan ¶
Scan is a support routine for fmt.Scanner. It accepts the formats 'e', 'E', 'f', 'F', 'g', 'G', and 'v'. All formats are equivalent.
func (*Rat) SetDenom ¶
SetDenom sets the numerator of z returning z
NB this isn't part of math/big which uses Num().Set() for this purpose. In gmp Num() returns a copy hence the need for a SetNum() method.
func (*Rat) SetFloat64 ¶
SetFloat64 sets z to exactly f and returns z. If f is not finite, SetFloat returns nil.
func (*Rat) SetNum ¶
SetNum sets the numerator of z returning z
NB this isn't part of math/big which uses Num().Set() for this purpose. In gmp Num() returns a copy hence the need for a SetNum() method.
func (*Rat) SetString ¶
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.
Source Files