import "github.com/cznic/mathutil"
Package mathutil provides utilities supplementing the standard 'math' and 'math/rand' packages.
2013-05-13: The following functions are now DEPRECATED
func Uint64ToBigInt(n uint64) *big.Int func Uint64FromBigInt(n *big.Int) (uint64, bool)
These functions will be REMOVED with Go release 1.1+1.
2013-01-21: The following functions have been REMOVED
func MaxInt() int func MinInt() int func MaxUint() uint func UintPtrBits() int
They are now replaced by untyped constants
MaxInt MinInt MaxUint UintPtrBits
Additionally one more untyped constant was added
IntBits
This change breaks any existing code depending on the above removed functions. They should have not been published in the first place, that was unfortunate. Instead, defining such architecture and/or implementation specific integer limits and bit widths as untyped constants improves performance and allows for static dead code elimination if it depends on these values. Thanks to minux for pointing it out in the mail list (https://groups.google.com/d/msg/golang-nuts/tlPpLW6aJw8/NT3mpToH-a4J).
2012-12-12: The following functions will be DEPRECATED with Go release 1.0.3+1 and REMOVED with Go release 1.0.3+2, b/c of http://code.google.com/p/go/source/detail?r=954a79ee3ea8
func Uint64ToBigInt(n uint64) *big.Int func Uint64FromBigInt(n *big.Int) (uint64, bool)
const (
Linear // As named
Sinusoidal // Smooth for all derivations
)Specific approximation method tags
const (
MaxInt = 1<<(IntBits-1) - 1
MinInt = -MaxInt - 1
MaxUint = 1<<IntBits - 1
IntBits = 1 << (^uint(0)>>32&1 + ^uint(0)>>16&1 + ^uint(0)>>8&1 + 3)
UintPtrBits = 1 << (^uintptr(0)>>32&1 + ^uintptr(0)>>16&1 + ^uintptr(0)>>8&1 + 3)
)Architecture and/or implementation specific integer limits and bit widths.
func AddUint128_64(a, b uint64) (hi uint64, lo uint64)
AddUint128_64 returns the uint128 sum of uint64 a and b.
func BitLen(n int) int
BitLen returns the bit width of the non zero part of n.
func BitLenByte(n byte) int
BitLenByte returns the bit width of the non zero part of n.
func BitLenUint(n uint) int
BitLenUint returns the bit width of the non zero part of n.
func BitLenUint16(n uint16) int
BitLenUint16 returns the bit width of the non zero part of n.
func BitLenUint32(n uint32) int
BitLenUint32 returns the bit width of the non zero part of n.
func BitLenUint64(n uint64) int
BitLenUint64 returns the bit width of the non zero part of n.
func BitLenUintptr(n uintptr) int
BitLenUintptr returns the bit width of the non zero part of n.
func Envelope(x float64, points []float64, approximation Approximation) float64
Envelope is an utility for defining simple curves using a small (usually) set of data points. Envelope returns a value defined by x, points and approximation. The value of x must be in [0,1) otherwise the result is undefined or the function may panic. Points are interpreted as dividing the [0,1) interval in len(points)-1 sections, so len(points) must be > 1 or the function may panic. According to the left and right points closing/adjacent to the section the resulting value is interpolated using the chosen approximation method. Unsupported values of approximation are silently interpreted as 'Linear'.
func GCDByte(a, b byte) byte
GCDByte returns the greatest common divisor of a and b. Based on: http://en.wikipedia.org/wiki/Euclidean_algorithm#Implementations
func GCDUint16(a, b uint16) uint16
GCDUint16 returns the greatest common divisor of a and b.
func GCDUint32(a, b uint32) uint32
GCD returns the greatest common divisor of a and b.
func GCDUint64(a, b uint64) uint64
GCD64 returns the greatest common divisor of a and b.
func ISqrt(n uint32) (x uint32)
ISqrt returns floor(sqrt(n)). Typical run time is few hundreds of ns.
func IsPrime(n uint32) bool
IsPrime returns true if n is prime. Typical run time is about 100 ns.
TODO rename to IsPrimeUint32
func IsPrimeUint16(n uint16) bool
IsPrimeUint16 returns true if n is prime. Typical run time is few ns.
func IsPrimeUint64(n uint64) bool
IsPrimeUint64 returns true if n is prime. Typical run time is few tens of µs.
SPRP bases: http://miller-rabin.appspot.com
func Log2Byte(n byte) int
Log2Byte returns log base 2 of n. It's the same as index of the highest bit set in n. For n == 0 -1 is returned.
func Log2Uint16(n uint16) int
Log2Uint16 returns log base 2 of n. It's the same as index of the highest bit set in n. For n == 0 -1 is returned.
func Log2Uint32(n uint32) int
Log2Uint32 returns log base 2 of n. It's the same as index of the highest bit set in n. For n == 0 -1 is returned.
func Log2Uint64(n uint64) int
Log2Uint64 returns log base 2 of n. It's the same as index of the highest bit set in n. For n == 0 -1 is returned.
func Max(a, b int) int
Max returns the larger of a and b.
func MaxByte(a, b byte) byte
MaxByte returns the larger of a and b.
func MaxInt16(a, b int16) int16
MaxInt16 returns the larger of a and b.
func MaxInt32(a, b int32) int32
MaxInt32 returns the larger of a and b.
func MaxInt64(a, b int64) int64
MaxInt64 returns the larger of a and b.
func MaxInt8(a, b int8) int8
MaxInt8 returns the larger of a and b.
func MaxUint16(a, b uint16) uint16
MaxUint16 returns the larger of a and b.
func MaxUint32(a, b uint32) uint32
MaxUint32 returns the larger of a and b.
func MaxUint64(a, b uint64) uint64
MaxUint64 returns the larger of a and b.
func Min(a, b int) int
Min returns the smaller of a and b.
func MinByte(a, b byte) byte
MinByte returns the smaller of a and b.
func MinInt16(a, b int16) int16
MinInt16 returns the smaller of a and b.
func MinInt32(a, b int32) int32
MinInt32 returns the smaller of a and b.
func MinInt64(a, b int64) int64
MinInt64 returns the smaller of a and b.
func MinInt8(a, b int8) int8
MinInt8 returns the smaller of a and b.
func MinUint16(a, b uint16) uint16
MinUint16 returns the smaller of a and b.
func MinUint32(a, b uint32) uint32
MinUint32 returns the smaller of a and b.
func MinUint64(a, b uint64) uint64
MinUint64 returns the smaller of a and b.
func ModPowBigInt(b, e, m *big.Int) (r *big.Int)
ModPowBigInt computes (b^e)%m. Returns nil for e < 0. It panics for m == 0 || b == e == 0.
func ModPowByte(b, e, m byte) byte
ModPowByte computes (b^e)%m. It panics for m == 0 || b == e == 0.
See also: http://en.wikipedia.org/wiki/Modular_exponentiation#Right-to-left_binary_method
func ModPowUint16(b, e, m uint16) uint16
ModPowByte computes (b^e)%m. It panics for m == 0 || b == e == 0.
func ModPowUint32(b, e, m uint32) uint32
ModPowUint32 computes (b^e)%m. It panics for m == 0 || b == e == 0.
func ModPowUint64(b, e, m uint64) (r uint64)
ModPowUint64 computes (b^e)%m. It panics for m == 0 || b == e == 0.
func MulUint128_64(a, b uint64) (hi, lo uint64)
MulUint128_64 returns the uint128 bit product of uint64 a and b.
func NextPrime(n uint32) (p uint32, ok bool)
NextPrime returns first prime > n and true if successful or an undefined value and false if there is no next prime in the uint32 limits. Typical run time is about 2 µs.
TODO rename to NextPrimeUint32
func NextPrimeUint16(n uint16) (p uint16, ok bool)
NextPrimeUint16 returns first prime > n and true if successful or an undefined value and false if there is no next prime in the uint16 limits. Typical run time is few ns.
func NextPrimeUint64(n uint64) (p uint64, ok bool)
NextPrimeUint64 returns first prime > n and true if successful or an undefined value and false if there is no next prime in the uint64 limits. Typical run time is in hundreds of µs.
func PermutationFirst(data sort.Interface)
Generate the first permutation of data.
func PermutationNext(data sort.Interface) bool
Generate the next permutation of data if possible and return true. If there is no more permutation left return false. Based on the algorithm described here: http://en.wikipedia.org/wiki/Permutation#Generation_in_lexicographic_order
func PopCount(n int) int
PopCount returns population count of n (number of bits set in n).
func PopCountBigInt(n *big.Int) (r int)
PopCountBigInt returns population count of |n| (number of bits set in |n|).
func PopCountByte(n byte) int
PopCountByte returns population count of n (number of bits set in n).
func PopCountUint(n uint) int
PopCountUint returns population count of n (number of bits set in n).
func PopCountUint16(n uint16) int
PopCountUint16 returns population count of n (number of bits set in n).
func PopCountUint32(n uint32) int
PopCountUint32 returns population count of n (number of bits set in n).
func PopCountUint64(n uint64) int
PopCountUint64 returns population count of n (number of bits set in n).
func PopCountUintptr(n uintptr) int
PopCountUintptr returns population count of n (number of bits set in n).
func PowerizeBigInt(b, n *big.Int) (e uint32, p *big.Int)
PowerizeBigInt returns (e, p) such that e is the smallest number for which p == b^e is greater or equal n. For n < 0 or b < 2 (0, nil) is returned.
NOTE: Run time for large values of n (above about 2^1e6 ~= 1e300000) can be significant and/or unacceptabe. For any smaller values of n the function typically performs in sub second time. For "small" values of n (cca bellow 2^1e3 ~= 1e300) the same can be easily below 10 µs.
A special (and trivial) case of b == 2 is handled separately and performs much faster.
func PowerizeUint32BigInt(b uint32, n *big.Int) (e uint32, p *big.Int)
PowerizeUint32BigInt returns (e, p) such that e is the smallest number for which p == b^e is greater or equal n. For n < 0 or b < 2 (0, nil) is returned.
More info: see PowerizeBigInt.
func PrimorialProductsUint32(lo, hi, max uint32) (r []uint32)
PrimorialProductsUint32 returns a slice of numbers in [lo, hi] which are a product of max 'max' primorials. The slice is not sorted.
See also: http://en.wikipedia.org/wiki/Primorial
func ProbablyPrimeBigInt(n, a *big.Int) bool
ProbablyPrimeBigInt returns true if n is prime or n is a pseudoprime to base a. It implements the Miller-Rabin primality test for one specific value of 'a' and k == 1. See also ProbablyPrimeUint32.
func ProbablyPrimeBigInt_32(n *big.Int, a uint32) bool
ProbablyPrimeBigInt_32 returns true if n is prime or n is a pseudoprime to base a. It implements the Miller-Rabin primality test for one specific value of 'a' and k == 1. See also ProbablyPrimeUint32.
func ProbablyPrimeUint32(n, a uint32) bool
ProbablyPrimeUint32 returns true if n is prime or n is a pseudoprime to base a. It implements the Miller-Rabin primality test for one specific value of 'a' and k == 1.
Wrt pseudocode shown at http://en.wikipedia.org/wiki/Miller-Rabin_primality_test#Algorithm_and_running_time
Input: n > 3, an odd integer to be tested for primality;
Input: k, a parameter that determines the accuracy of the test
Output: composite if n is composite, otherwise probably prime
write n − 1 as 2^s·d with d odd by factoring powers of 2 from n − 1
LOOP: repeat k times:
pick a random integer a in the range [2, n − 2]
x ← a^d mod n
if x = 1 or x = n − 1 then do next LOOP
for r = 1 .. s − 1
x ← x^2 mod n
if x = 1 then return composite
if x = n − 1 then do next LOOP
return composite
return probably prime
... this function behaves like passing 1 for 'k' and additionaly a fixed/non-random 'a'. Otherwise it's the same algorithm.
See also: http://mathworld.wolfram.com/Rabin-MillerStrongPseudoprimeTest.html
func ProbablyPrimeUint64_32(n uint64, a uint32) bool
ProbablyPrimeUint64_32 returns true if n is prime or n is a pseudoprime to base a. It implements the Miller-Rabin primality test for one specific value of 'a' and k == 1. See also ProbablyPrimeUint32.
func QCmpUint32(a, b, c, d uint32) int
QCmpUint32 compares a/b and c/d and returns:
-1 if a/b < c/d 0 if a/b == c/d +1 if a/b > c/d
func QScaleUint32(b, c, d uint32) (a uint64)
QScaleUint32 returns a such that a/b >= c/d.
func SqrtBig(n *big.Int) (x *big.Int)
SqrtBig returns floor(sqrt(n)). It panics on n < 0.
func SqrtUint64(n uint64) (x uint64)
SqrtUint64 returns floor(sqrt(n)). Typical run time is about 0.5 µs.
func UMax(a, b uint) uint
UMax returns the larger of a and b.
func UMin(a, b uint) uint
UMin returns the smaller of a and b.
func Uint64FromBigInt(n *big.Int) (uint64, bool)
Uint64FromBigInt returns (uint64 value of n, true) if 0 <= n <= math.MaxUint64. Otherwise it returns (undefined value, false).
NOTE: This function is DEPRECATED with Go release 1.1 and will be REMOVED with Go release 1.1+1, b/c of http://code.google.com/p/go/source/detail?r=954a79ee3ea8
func Uint64ToBigInt(n uint64) *big.Int
Uint64ToBigInt returns a big.Int set to n.
NOTE: This function is DEPRECATED with Go release 1.1 and will be REMOVED with Go release 1.1+1, b/c of http://code.google.com/p/go/source/detail?r=954a79ee3ea8
func UintptrBits() int
UintptrBits returns the bit width of an uintptr at the executing machine.
type Approximation int
Approximation type determines approximation methods used by e.g. Envelope.
type FC32 struct {
// contains filtered or unexported fields
}FC32 is a full cycle PRNG covering the 32 bit signed integer range. In contrast to full cycle generators shown at e.g. http://en.wikipedia.org/wiki/Full_cycle, this code doesn't produce values at constant delta (mod cycle length). The 32 bit limit is per this implementation, the algorithm used has no intrinsic limit on the cycle size. Properties include:
- Adjustable limits on creation (hi, lo). - Positionable/randomly accessible (Pos, Seek). - Repeatable (deterministic). - Can run forward or backward (Next, Prev). - For a billion numbers cycle the Next/Prev PRN can be produced in cca 100-150ns. That's like 5-10 times slower compared to PRNs generated using the (non FC) rand package.
func NewFC32(lo, hi int, hq bool) (r *FC32, err error)
NewFC32 returns a newly created FC32 adjusted for the closed interval [lo, hi] or an Error if any. If hq == true then trade some generation time for improved (pseudo)randomness.
func (r *FC32) Cycle() int64
Cycle reports the length of the inner FCPRNG cycle. Cycle is atmost the double (HQ: triple) of the generator period (hi - lo + 1).
func (r *FC32) Next() int
Next returns the first PRN after Pos.
func (r *FC32) Pos() int64
Pos reports the current position within the inner cycle.
func (r *FC32) Prev() int
Prev return the first PRN before Pos.
func (r *FC32) Seed(seed int64)
Seed uses the provided seed value to initialize the generator to a deterministic state. A zero seed produces a "canonical" generator with worse randomness than for most non zero seeds. Still, the FC property holds for any seed value.
func (r *FC32) Seek(pos int64)
Seek sets Pos to |pos| % Cycle.
type FCBig struct {
// contains filtered or unexported fields
}FCBig is a full cycle PRNG covering ranges outside of the int32 limits. For more info see the FC32 docs. Next/Prev PRN on a 1e15 cycle can be produced in about 2 µsec.
func NewFCBig(lo, hi *big.Int, hq bool) (r *FCBig, err error)
NewFCBig returns a newly created FCBig adjusted for the closed interval [lo, hi] or an Error if any. If hq == true then trade some generation time for improved (pseudo)randomness.
func (r *FCBig) Cycle() *big.Int
Cycle reports the length of the inner FCPRNG cycle. Cycle is atmost the double (HQ: triple) of the generator period (hi - lo + 1).
func (r *FCBig) Next() *big.Int
Next returns the first PRN after Pos.
func (r *FCBig) Pos() *big.Int
Pos reports the current position within the inner cycle.
func (r *FCBig) Prev() *big.Int
Prev return the first PRN before Pos.
func (r *FCBig) Seed(seed int64)
Seed uses the provided seed value to initialize the generator to a deterministic state. A zero seed produces a "canonical" generator with worse randomness than for most non zero seeds. Still, the FC property holds for any seed value.
func (r *FCBig) Seek(pos *big.Int)
Seek sets Pos to |pos| % Cycle.
type FactorTerm struct {
Prime uint32 // The divisor
Power uint32 // Term == Prime^Power
}FactorTerm is one term of an integer factorization.
type FactorTerms []FactorTerm
FactorTerms represent a factorization of an integer
func FactorInt(n uint32) (f FactorTerms)
FactorInt returns prime factorization of n > 1 or nil otherwise. Resulting factors are ordered by Prime. Typical run time is few µs.
bits.go rnd.go envelope.go mathutil.go permute.go primes.go rat.go tables.go test_deps.go
| Path | Synopsis |
|---|---|
| mersenne | Package mersenne collects utilities related to Mersenne numbers[1] and/or some of their properties. |