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 (
    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

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

AddUint128_64 returns the uint128 sum of uint64 a and b.

func BitLen

func BitLen(n int) int

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

func BitLenByte

func BitLenByte(n byte) int

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

func BitLenUint

func BitLenUint(n uint) int

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

func BitLenUint16

func BitLenUint16(n uint16) int

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

func BitLenUint32

func BitLenUint32(n uint32) int

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

func BitLenUint64

func BitLenUint64(n uint64) int

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

func BitLenUintptr

func BitLenUintptr(n uintptr) int

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

func Envelope

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

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

func GCDUint16(a, b uint16) uint16

GCDUint16 returns the greatest common divisor of a and b.

func GCDUint32

func GCDUint32(a, b uint32) uint32

GCD returns the greatest common divisor of a and b.

func GCDUint64

func GCDUint64(a, b uint64) uint64

GCD64 returns the greatest common divisor of a and b.

func ISqrt

func ISqrt(n uint32) (x uint32)

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

func IsPrime

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

func IsPrimeUint16(n uint16) bool

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

func IsPrimeUint64

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

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

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

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

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

func Max(a, b int) int

Max returns the larger of a and b.

func MaxByte

func MaxByte(a, b byte) byte

MaxByte returns the larger of a and b.

func MaxInt16

func MaxInt16(a, b int16) int16

MaxInt16 returns the larger of a and b.

func MaxInt32

func MaxInt32(a, b int32) int32

MaxInt32 returns the larger of a and b.

func MaxInt64

func MaxInt64(a, b int64) int64

MaxInt64 returns the larger of a and b.

func MaxInt8

func MaxInt8(a, b int8) int8

MaxInt8 returns the larger of a and b.

func MaxUint16

func MaxUint16(a, b uint16) uint16

MaxUint16 returns the larger of a and b.

func MaxUint32

func MaxUint32(a, b uint32) uint32

MaxUint32 returns the larger of a and b.

func MaxUint64

func MaxUint64(a, b uint64) uint64

MaxUint64 returns the larger of a and b.

func Min

func Min(a, b int) int

Min returns the smaller of a and b.

func MinByte

func MinByte(a, b byte) byte

MinByte returns the smaller of a and b.

func MinInt16

func MinInt16(a, b int16) int16

MinInt16 returns the smaller of a and b.

func MinInt32

func MinInt32(a, b int32) int32

MinInt32 returns the smaller of a and b.

func MinInt64

func MinInt64(a, b int64) int64

MinInt64 returns the smaller of a and b.

func MinInt8

func MinInt8(a, b int8) int8

MinInt8 returns the smaller of a and b.

func MinUint16

func MinUint16(a, b uint16) uint16

MinUint16 returns the smaller of a and b.

func MinUint32

func MinUint32(a, b uint32) uint32

MinUint32 returns the smaller of a and b.

func MinUint64

func MinUint64(a, b uint64) uint64

MinUint64 returns the smaller of a and b.

func ModPowBigInt

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

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

func ModPowUint16(b, e, m uint16) uint16

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

func ModPowUint32

func ModPowUint32(b, e, m uint32) uint32

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

func ModPowUint64

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

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

func MulUint128_64

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

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

func NextPrime

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

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

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

func PermutationFirst(data sort.Interface)

Generate the first permutation of data.

func PermutationNext

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

func PopCount(n int) int

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

func PopCountBigInt

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

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

func PopCountByte

func PopCountByte(n byte) int

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

func PopCountUint

func PopCountUint(n uint) int

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

func PopCountUint16

func PopCountUint16(n uint16) int

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

func PopCountUint32

func PopCountUint32(n uint32) int

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

func PopCountUint64

func PopCountUint64(n uint64) int

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

func PopCountUintptr

func PopCountUintptr(n uintptr) int

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

func PowerizeBigInt

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

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

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

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

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

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

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

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

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

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

func SqrtBig

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

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

func SqrtUint64

func SqrtUint64(n uint64) (x uint64)

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

func ToBase

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

func UMax(a, b uint) uint

UMax returns the larger of a and b.

func UMin

func UMin(a, b uint) uint

UMin returns the smaller of a and b.

func UintptrBits

func UintptrBits() int

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

type Approximation

type Approximation int

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

type FC32

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

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

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

func (r *FC32) Next() int

Next returns the first PRN after Pos.

func (*FC32) Pos

func (r *FC32) Pos() int64

Pos reports the current position within the inner cycle.

func (*FC32) Prev

func (r *FC32) Prev() int

Prev return the first PRN before Pos.

func (*FC32) Seed

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

func (r *FC32) Seek(pos int64)

Seek sets Pos to |pos| % Cycle.

type FCBig

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

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

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

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

Next returns the first PRN after Pos.

func (*FCBig) Pos

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

Pos reports the current position within the inner cycle.

func (*FCBig) Prev

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

Prev return the first PRN before Pos.

func (*FCBig) Seed

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

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

Seek sets Pos to |pos| % Cycle.

type FactorTerm

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

FactorTerm is one term of an integer factorization.

type FactorTerms

type FactorTerms []FactorTerm

FactorTerms represent a factorization of an integer

func FactorInt

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
example4Let QRN be the number of quadratic residues of N.
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 17 packages. Updated 2014-03-24. Refresh now. Tools for package owners.