mathutil: github.com/cznic/mathutil Index | Files | Directories

package mathutil

import "github.com/cznic/mathutil"

Package mathutil provides utilities supplementing the standard 'math' and 'math/rand' packages.

Compatibility issues

2013-12-13: The following functions have been REMOVED

func Uint64ToBigInt(n uint64) *big.Int
func Uint64FromBigInt(n *big.Int) (uint64, bool)

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)

Index

Package Files

bits.go envelope.go mathutil.go permute.go primes.go rat.go rnd.go tables.go test_deps.go

Constants

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 Uses

func AddUint128_64(a, b uint64) (hi uint64, lo uint64)

AddUint128_64 returns the uint128 sum of uint64 a and b.

func BitLen Uses

func BitLen(n int) int

BitLen returns the bit width of the non zero part of n.

func BitLenByte Uses

func BitLenByte(n byte) int

BitLenByte returns the bit width of the non zero part of n.

func BitLenUint Uses

func BitLenUint(n uint) int

BitLenUint returns the bit width of the non zero part of n.

func BitLenUint16 Uses

func BitLenUint16(n uint16) int

BitLenUint16 returns the bit width of the non zero part of n.

func BitLenUint32 Uses

func BitLenUint32(n uint32) int

BitLenUint32 returns the bit width of the non zero part of n.

func BitLenUint64 Uses

func BitLenUint64(n uint64) int

BitLenUint64 returns the bit width of the non zero part of n.

func BitLenUintptr Uses

func BitLenUintptr(n uintptr) int

BitLenUintptr returns the bit width of the non zero part of n.

func Envelope Uses

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 Uses

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 Uses

func GCDUint16(a, b uint16) uint16

GCDUint16 returns the greatest common divisor of a and b.

func GCDUint32 Uses

func GCDUint32(a, b uint32) uint32

GCD returns the greatest common divisor of a and b.

func GCDUint64 Uses

func GCDUint64(a, b uint64) uint64

GCD64 returns the greatest common divisor of a and b.

func ISqrt Uses

func ISqrt(n uint32) (x uint32)

ISqrt returns floor(sqrt(n)). Typical run time is few hundreds of ns.

func IsPrime Uses

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 Uses

func IsPrimeUint16(n uint16) bool

IsPrimeUint16 returns true if n is prime. Typical run time is few ns.

func IsPrimeUint64 Uses

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 Uses

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 Uses

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 Uses

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 Uses

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 Uses

func Max(a, b int) int

Max returns the larger of a and b.

func MaxByte Uses

func MaxByte(a, b byte) byte

MaxByte returns the larger of a and b.

func MaxInt16 Uses

func MaxInt16(a, b int16) int16

MaxInt16 returns the larger of a and b.

func MaxInt32 Uses

func MaxInt32(a, b int32) int32

MaxInt32 returns the larger of a and b.

func MaxInt64 Uses

func MaxInt64(a, b int64) int64

MaxInt64 returns the larger of a and b.

func MaxInt8 Uses

func MaxInt8(a, b int8) int8

MaxInt8 returns the larger of a and b.

func MaxUint16 Uses

func MaxUint16(a, b uint16) uint16

MaxUint16 returns the larger of a and b.

func MaxUint32 Uses

func MaxUint32(a, b uint32) uint32

MaxUint32 returns the larger of a and b.

func MaxUint64 Uses

func MaxUint64(a, b uint64) uint64

MaxUint64 returns the larger of a and b.

func Min Uses

func Min(a, b int) int

Min returns the smaller of a and b.

func MinByte Uses

func MinByte(a, b byte) byte

MinByte returns the smaller of a and b.

func MinInt16 Uses

func MinInt16(a, b int16) int16

MinInt16 returns the smaller of a and b.

func MinInt32 Uses

func MinInt32(a, b int32) int32

MinInt32 returns the smaller of a and b.

func MinInt64 Uses

func MinInt64(a, b int64) int64

MinInt64 returns the smaller of a and b.

func MinInt8 Uses

func MinInt8(a, b int8) int8

MinInt8 returns the smaller of a and b.

func MinUint16 Uses

func MinUint16(a, b uint16) uint16

MinUint16 returns the smaller of a and b.

func MinUint32 Uses

func MinUint32(a, b uint32) uint32

MinUint32 returns the smaller of a and b.

func MinUint64 Uses

func MinUint64(a, b uint64) uint64

MinUint64 returns the smaller of a and b.

func ModPowBigInt Uses

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 Uses

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 Uses

func ModPowUint16(b, e, m uint16) uint16

ModPowByte computes (b^e)%m. It panics for m == 0 || b == e == 0.

func ModPowUint32 Uses

func ModPowUint32(b, e, m uint32) uint32

ModPowUint32 computes (b^e)%m. It panics for m == 0 || b == e == 0.

func ModPowUint64 Uses

func ModPowUint64(b, e, m uint64) (r uint64)

ModPowUint64 computes (b^e)%m. It panics for m == 0 || b == e == 0.

func MulUint128_64 Uses

func MulUint128_64(a, b uint64) (hi, lo uint64)

MulUint128_64 returns the uint128 bit product of uint64 a and b.

func NextPrime Uses

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 Uses

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 Uses

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 Uses

func PermutationFirst(data sort.Interface)

Generate the first permutation of data.

func PermutationNext Uses

func PermutationNext(data sort.Interface) bool

Generate the next permutation of data if possible and return true. Return false if there is no more permutation left. Based on the algorithm described here: http://en.wikipedia.org/wiki/Permutation#Generation_in_lexicographic_order

func PopCount Uses

func PopCount(n int) int

PopCount returns population count of n (number of bits set in n).

func PopCountBigInt Uses

func PopCountBigInt(n *big.Int) (r int)

PopCountBigInt returns population count of |n| (number of bits set in |n|).

func PopCountByte Uses

func PopCountByte(n byte) int

PopCountByte returns population count of n (number of bits set in n).

func PopCountUint Uses

func PopCountUint(n uint) int

PopCountUint returns population count of n (number of bits set in n).

func PopCountUint16 Uses

func PopCountUint16(n uint16) int

PopCountUint16 returns population count of n (number of bits set in n).

func PopCountUint32 Uses

func PopCountUint32(n uint32) int

PopCountUint32 returns population count of n (number of bits set in n).

func PopCountUint64 Uses

func PopCountUint64(n uint64) int

PopCountUint64 returns population count of n (number of bits set in n).

func PopCountUintptr Uses

func PopCountUintptr(n uintptr) int

PopCountUintptr returns population count of n (number of bits set in n).

func PowerizeBigInt Uses

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 Uses

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 Uses

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 Uses

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 Uses

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 Uses

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 additionally a fixed/non-random 'a'. Otherwise it's the same algorithm.

See also: http://mathworld.wolfram.com/Rabin-MillerStrongPseudoprimeTest.html

func ProbablyPrimeUint64_32 Uses

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 Uses

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 Uses

func QScaleUint32(b, c, d uint32) (a uint64)

QScaleUint32 returns a such that a/b >= c/d.

func SqrtBig Uses

func SqrtBig(n *big.Int) (x *big.Int)

SqrtBig returns floor(sqrt(n)). It panics on n < 0.

func SqrtUint64 Uses

func SqrtUint64(n uint64) (x uint64)

SqrtUint64 returns floor(sqrt(n)). Typical run time is about 0.5 µs.

func ToBase Uses

func ToBase(n *big.Int, b int) []int

ToBase produces n in base b. For example

ToBase(2047, 22) -> [1, 5, 4]

1 * 22^0           1
5 * 22^1         110
4 * 22^2        1936
                ----
                2047

ToBase panics for bases < 2.

func UMax Uses

func UMax(a, b uint) uint

UMax returns the larger of a and b.

func UMin Uses

func UMin(a, b uint) uint

UMin returns the smaller of a and b.

func UintptrBits Uses

func UintptrBits() int

UintptrBits returns the bit width of an uintptr at the executing machine.

type Approximation Uses

type Approximation int

Approximation type determines approximation methods used by e.g. Envelope.

const (
    Linear     Approximation // As named
    Sinusoidal               // Smooth for all derivations
)

Specific approximation method tags

type FC32 Uses

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 Uses

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 (*FC32) Cycle Uses

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 (*FC32) Next Uses

func (r *FC32) Next() int

Next returns the first PRN after Pos.

func (*FC32) Pos Uses

func (r *FC32) Pos() int64

Pos reports the current position within the inner cycle.

func (*FC32) Prev Uses

func (r *FC32) Prev() int

Prev return the first PRN before Pos.

func (*FC32) Seed Uses

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 (*FC32) Seek Uses

func (r *FC32) Seek(pos int64)

Seek sets Pos to |pos| % Cycle.

type FCBig Uses

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 Uses

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 (*FCBig) Cycle Uses

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 (*FCBig) Next Uses

func (r *FCBig) Next() *big.Int

Next returns the first PRN after Pos.

func (*FCBig) Pos Uses

func (r *FCBig) Pos() *big.Int

Pos reports the current position within the inner cycle.

func (*FCBig) Prev Uses

func (r *FCBig) Prev() *big.Int

Prev return the first PRN before Pos.

func (*FCBig) Seed Uses

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 (*FCBig) Seek Uses

func (r *FCBig) Seek(pos *big.Int)

Seek sets Pos to |pos| % Cycle.

type FactorTerm Uses

type FactorTerm struct {
    Prime uint32 // The divisor
    Power uint32 // Term == Prime^Power
}

FactorTerm is one term of an integer factorization.

type FactorTerms Uses

type FactorTerms []FactorTerm

FactorTerms represent a factorization of an integer

func FactorInt Uses

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.

Directories

PathSynopsis
mersennePackage mersenne collects utilities related to Mersenne numbers[1] and/or some of their properties.

Package mathutil imports 4 packages (graph) and is imported by 40 packages. Updated 2016-07-19. Refresh now. Tools for package owners.