mathutil

package
v0.11.0 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Nov 13, 2015 License: BSD-3-Clause, Apache-2.0 Imports: 4 Imported by: 0

README 

This is a goinstall-able mirror of modified code already published at:
http://git.nic.cz/redmine/projects/gornd/repository

Packages in this repository:

Install: $ go get github.com/cznic/mathutil
Godocs:  http://godoc.org/github.com/cznic/mathutil

Install: $ go get github.com/cznic/mathutil/mersenne
Godocs:  http://godoc.org/github.com/cznic/mathutil/mersenne

Documentation

Overview

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

Constants

View Source 
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.

Variables

This section is empty.

Functions

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.

Types

type Approximation 

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 

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.

Source Files

View all Source files

Directories

Path Synopsis
Package mersenne collects utilities related to Mersenne numbers[1] and/or some of their properties.
 Package mersenne collects utilities related to Mersenne numbers[1] and/or some of their properties.

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.