package mathutil
Import Path
modernc.org/mathutil (on go.dev)
Dependency Relation
imports 5 packages, and imported by one package
Involved Source Files
binarylog.go
bits.go
envelope.go
int.go
Package mathutil provides utilities supplementing the standard 'math' and
'math/rand' packages.
Release history and compatibility issues
2020-12-20 v1.2.1 fixes MulOverflowInt64.
2020-12-19 Added {Add,Sub,Mul}OverflowInt{8,16,32,64}
2018-10-21 Added BinaryLog
2018-04-25: New functions for determining Max/Min of nullable values. Ex:
func MaxPtr(a, b *int) *int {
func MinPtr(a, b *int) *int {
func MaxBytePtr(a, b *byte) *byte {
func MinBytePtr(a, b *byte) *byte {
...
2017-10-14: New variadic functions for Max/Min. Ex:
func MaxVal(val int, vals ...int) int {
func MinVal(val int, vals ...int) int {
func MaxByteVal(val byte, vals ...byte) byte {
func MinByteVal(val byte, vals ...byte) byte {
...
2016-10-10: New functions QuadPolyDiscriminant and QuadPolyFactors.
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)
permute.go
poly.go
primes.go
rat.go
rnd.go
tables.go
test_deps.go
Package-Level Type Names (total 10, in which 9 are exported)
Approximation type determines approximation methods used by e.g. Envelope.
func Envelope(x float64, points []float64, approximation Approximation) float64
const Linear
const Sinusoidal
FactorTerm is one term of an integer factorization.
// Term == Prime^Power
// The divisor
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.
// On average: 3 * delta / 2, (HQ: 2 * delta)
// hi - lo
// This trades some space for hopefully a bit of speed (multiple adding vs multiplying).
lo int
// pos % set
// Within cycle.
// Ordered. ∏ primes == cycle.
// Reordered primes (magnitude order bases) according to seed.
Cycle reports the length of the inner FCPRNG cycle.
Cycle is atmost the double (HQ: triple) of the generator period (hi - lo + 1).
Next returns the first PRN after Pos.
Pos reports the current position within the inner cycle.
Prev return the first PRN before Pos.
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.
Seek sets Pos to |pos| % Cycle.
(*T) step(dir int) int
func NewFC32(lo, hi int, hq bool) (r *FC32, err error)
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.
// On average: 3 * delta / 2, (HQ: 2 * delta)
// hi - lo
// This trades some space for hopefully a bit of speed (multiple adding vs multiplying).
lo *big.Int
// pos % set
// Within cycle.
// Ordered. ∏ primes == cycle.
// Reordered primes (magnitude order bases) according to seed.
Cycle reports the length of the inner FCPRNG cycle.
Cycle is atmost the double (HQ: triple) of the generator period (hi - lo + 1).
Next returns the first PRN after Pos.
Pos reports the current position within the inner cycle.
Prev return the first PRN before Pos.
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.
Seek sets Pos to |pos| % Cycle.
(*T) step(dir int) (y *big.Int)
func NewFCBig(lo, hi *big.Int, hq bool) (r *FCBig, err error)
Int128 is an 128 bit signed integer.
// Bits 127..64.
// Bits 63..0.
Add returns the sum of x and y and a carry indication.
BigInt returns x in the form of a big.Int.
Cmp compares x and y and returns:
-1 if x < y
0 if x == y
+1 if x > y
Neg returns -x and an indication that x was not equal to MinInt128.
SetBigInt sets x to y, returns x and an error, if any.
SetInt64 sets x to y and returns x.
SetUint64 sets x to y and returns x.
Sign returns:
-1 if x < 0
0 if x == 0
+1 if x > 0
String implements fmt.Stringer()
T : fmt.Stringer
T : context.stringer
T : os/signal.stringer
T : runtime.stringer
func NewInt128FromFloat32(n float32) (r Int128)
func NewInt128FromFloat64(n float64) (r Int128)
func NewInt128FromInt64(n int64) (r Int128)
func NewInt128FromUint64(n uint64) (r Int128)
func Int128.Add(y Int128) (r Int128, cy bool)
func Int128.Neg() (r Int128, ok bool)
func (*Int128).SetBigInt(y *big.Int) (r Int128, err error)
func (*Int128).SetInt64(y int64) (r Int128)
func (*Int128).SetUint64(y uint64) (r Int128)
func Int128.Add(y Int128) (r Int128, cy bool)
func Int128.Cmp(y Int128) int
PolyFactor describes an irreducible factor of a polynomial in one variable
with integer coefficients P, Q of the form P*x+Q.
P int
Q int
func QuadPolyFactors(a, b, c int) (content int, primitivePart []PolyFactor, _ error)
PolyFactorBig describes an irreducible factor of a polynomial in one
variable with integer coefficients P, Q of the form P*x+Q.
P *big.Int
Q *big.Int
func QuadPolyFactorsBig(a, b, c *big.Int) (content *big.Int, primitivePart []PolyFactorBig)
Uint128 is an 128 bit unsigned integer.
// Bits 127..64.
// Bits 63..0.
SetBigInt sets x to y, returns x and an error, if any.
func NewUint128FromFloat32(n float32) (r Uint128)
func NewUint128FromFloat64(n float64) (r Uint128)
func NewUint128FromInt64(n int64) (r Uint128)
func NewUint128FromUint64(n uint64) (r Uint128)
func (*Uint128).SetBigInt(y *big.Int) (r Uint128, err error)
Package-Level Functions (total 171, in which 153 are exported)
AddOverflowInt16 returns a + b and an indication whether the addition
overflowed the int16 range.
AddOverflowInt32 returns a + b and an indication whether the addition
overflowed the int32 range.
AddOverflowInt64 returns a + b and an indication whether the addition
overflowed the int64 range.
AddOverflowInt8 returns a + b and an indication whether the addition
overflowed the int8 range.
AddUint128_64 returns the uint128 sum of uint64 a and b.
BinaryLog computes the binary logarithm of n. The result consists of a
characteristic and a mantissa having precision mantissaBits. The value of
the binary logarithm is
characteristic + mantissa*(2^-mantissaBits)
BinaryLog panics for n <= 0 or mantissaBits < 0.
BitLen returns the bit width of the non zero part of n.
BitLenByte returns the bit width of the non zero part of n.
BitLenUint returns the bit width of the non zero part of n.
BitLenUint16 returns the bit width of the non zero part of n.
BitLenUint32 returns the bit width of the non zero part of n.
BitLenUint64 returns the bit width of the non zero part of n.
BitLenUintptr returns the bit width of the non zero part of n.
CheckAddInt64 returns the a+b and an indicator that the result is greater
than math.MaxInt64.
CheckSubInt64 returns a-b and an indicator that the result is less than than
math.MinInt64.
Clamp returns a value restricted between lo and hi.
ClampByte returns a value restricted between lo and hi.
ClampInt16 returns a value restricted between lo and hi.
ClampInt32 returns a value restricted between lo and hi.
ClampInt64 returns a value restricted between lo and hi.
ClampInt8 returns a value restricted between lo and hi.
ClampUint16 returns a value restricted between lo and hi.
ClampUint32 returns a value restricted between lo and hi.
ClampUint64 returns a value restricted between lo and hi.
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'.
FactorInt returns prime factorization of n > 1 or nil otherwise.
Resulting factors are ordered by Prime. Typical run time is few µs.
GCDByte returns the greatest common divisor of a and b. Based on:
http://en.wikipedia.org/wiki/Euclidean_algorithm#Implementations
GCDUint16 returns the greatest common divisor of a and b.
GCDUint32 returns the greatest common divisor of a and b.
GCDUint64 returns the greatest common divisor of a and b.
IsPrime returns true if n is prime. Typical run time is about 100 ns.
IsPrimeUint16 returns true if n is prime. Typical run time is few ns.
IsPrimeUint64 returns true if n is prime. Typical run time is few tens of µs.
SPRP bases: http://miller-rabin.appspot.com
ISqrt returns floor(sqrt(n)). Typical run time is few hundreds of ns.
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.
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.
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.
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.
Max returns the larger of a and b.
MaxByte returns the larger of a and b.
MaxBytePtr returns a pointer to the larger of a and b, or nil.
MaxByteVal returns the largest argument passed.
MaxInt16 returns the larger of a and b.
MaxInt16Ptr returns a pointer to the larger of a and b, or nil.
MaxInt16Val returns the largest argument passed.
MaxInt32 returns the larger of a and b.
MaxInt32Ptr returns a pointer to the larger of a and b, or nil.
MaxInt32Val returns the largest argument passed.
MaxInt64 returns the larger of a and b.
MaxInt64Ptr returns a pointer to the larger of a and b, or nil.
MaxInt64Val returns the largest argument passed.
MaxInt8 returns the larger of a and b.
MaxInt8Ptr returns a pointer to the larger of a and b, or nil.
MaxInt8Val returns the largest argument passed.
MaxPtr returns a pointer to the larger of a and b, or nil.
MaxUint16 returns the larger of a and b.
MaxUint16Ptr returns a pointer to the larger of a and b, or nil.
MaxUint16Val returns the largest argument passed.
MaxUint32 returns the larger of a and b.
MaxUint32Ptr returns a pointer to the larger of a and b, or nil.
MaxUint32Val returns the largest argument passed.
MaxUint64 returns the larger of a and b.
MaxUint64Ptr returns a pointer to the larger of a and b, or nil.
MaxUint64Val returns the largest argument passed.
MaxVal returns the largest argument passed.
Min returns the smaller of a and b.
MinByte returns the smaller of a and b.
MinBytePtr returns a pointer to the smaller of a and b, or nil.
MinByteVal returns the smallest argument passed.
MinInt16 returns the smaller of a and b.
MinInt16Ptr returns a pointer to the smaller of a and b, or nil.
MinInt16Val returns the smallest argument passed.
MinInt32 returns the smaller of a and b.
MinInt32Ptr returns a pointer to the smaller of a and b, or nil.
MinInt32Val returns the smallest argument passed.
MinInt64 returns the smaller of a and b.
MinInt64Ptr returns a pointer to the smaller of a and b, or nil.
MinInt64Val returns the smallest argument passed.
MinInt8 returns the smaller of a and b.
MinInt8Ptr returns a pointer to the smaller of a and b, or nil.
MinInt8Val returns the smallest argument passed.
MinPtr returns a pointer to the smaller of a and b, or nil.
MinUint16 returns the smaller of a and b.
MinUint16Ptr returns a pointer to the smaller of a and b, or nil.
MinUint16Val returns the smallest argument passed.
MinUint32 returns the smaller of a and b.
MinUint32Ptr returns a pointer to the smaller of a and b, or nil.
MinUint32Val returns the smallest argument passed.
MinUint64 returns the smaller of a and b.
MinUint64Ptr returns a pointer to the smaller of a and b, or nil.
MinUint64Val returns the smallest argument passed.
MinVal returns the smallest argument passed.
ModPowBigInt computes (b^e)%m. Returns nil for e < 0. It panics for m == 0 || b == e == 0.
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
ModPowUint16 computes (b^e)%m. It panics for m == 0 || b == e == 0.
ModPowUint32 computes (b^e)%m. It panics for m == 0 || b == e == 0.
ModPowUint64 computes (b^e)%m. It panics for m == 0 || b == e == 0.
MulOverflowInt16 returns a * b and an indication whether the product
overflowed the int16 range.
MulOverflowInt32 returns a * b and an indication whether the product
overflowed the int32 range.
MulOverflowInt64 returns a * b and an indication whether the product
overflowed the int64 range.
MulOverflowInt8 returns a * b and an indication whether the product
overflowed the int8 range.
MulUint128_64 returns the uint128 bit product of uint64 a and b.
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.
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.
NewInt128FromFloat32 returns a new Int128 value initialized to n. Result is
not specified in n does not represent a number within the range of Int128
values.
NewInt128FromFloat64 returns a new Int128 value initialized to n. Result is
not specified in n does not represent a number within the range of Int128
values.
NewInt128FromInt64 return a new Int128 value initialized to n.
NewInt128FromUint64 return a new Int128 value initialized to n.
NewUint128FromFloat32 returns a new Uint128 value initialized to n. Result is
not specified in n does not represent a number within the range of Uint128
values.
NewUint128FromFloat64 returns a new Uint128 value initialized to n. Result is
not specified in n does not represent a number within the range of Uint128
values.
NewUint128FromInt64 return a new Uint128 value initialized to n.
NewUint128FromUint64 return a new Uint128 value initialized to n.
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.
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.
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.
PermutationFirst generates the first permutation of data.
PermutationNext generates 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
PopCount returns population count of n (number of bits set in n).
PopCountBigInt returns population count of |n| (number of bits set in |n|).
PopCountByte returns population count of n (number of bits set in n).
PopCountUint returns population count of n (number of bits set in n).
PopCountUint16 returns population count of n (number of bits set in n).
PopCountUint32 returns population count of n (number of bits set in n).
PopCountUint64 returns population count of n (number of bits set in n).
PopCountUintptr returns population count of n (number of bits set in n).
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.
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.
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
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.
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.
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
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.
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
QScaleUint32 returns a such that a/b >= c/d.
QuadPolyDiscriminant returns the discriminant of a quadratic polynomial in
one variable of the form a*x^2+b*x+c with integer coefficients a, b, c, or
an error on overflow.
ds is the square of the discriminant. If |ds| is a square number, d is set
to sqrt(|ds|), otherwise d is < 0.
QuadPolyDiscriminantBig returns the discriminant of a quadratic polynomial
in one variable of the form a*x^2+b*x+c with integer coefficients a, b, c.
ds is the square of the discriminant. If |ds| is a square number, d is set
to sqrt(|ds|), otherwise d is nil.
QuadPolyFactors returns the content and the irreducible factors of the
primitive part of a quadratic polynomial in one variable with integer
coefficients a, b, c of the form a*x^2+b*x+c in integers, or an error on
overflow.
If the factorization in integers does not exists, the return value is (0,
nil, nil).
See also:
https://en.wikipedia.org/wiki/Factorization_of_polynomials#Primitive_part.E2.80.93content_factorization
QuadPolyFactorsBig returns the content and the irreducible factors of the
primitive part of a quadratic polynomial in one variable with integer
coefficients a, b, c of the form a*x^2+b*x+c in integers.
If the factorization in integers does not exists, the return value is (nil,
nil).
See also:
https://en.wikipedia.org/wiki/Factorization_of_polynomials#Primitive_part.E2.80.93content_factorization
SqrtBig returns floor(sqrt(n)). It panics on n < 0.
SqrtUint64 returns floor(sqrt(n)). Typical run time is about 0.5 µs.
SubOverflowInt16 returns a - b and an indication whether the subtraction
overflowed the int16 range.
SubOverflowInt32 returns a - b and an indication whether the subtraction
overflowed the int32 range.
SubOverflowInt64 returns a - b and an indication whether the subtraction
overflowed the int64 range.
SubOverflowInt8 returns a - b and an indication whether the subtraction
overflowed the int8 range.
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.
UClamp returns a value restricted between lo and hi.
UintptrBits returns the bit width of an uintptr at the executing machine.
UMax returns the larger of a and b.
UMaxPtr returns a pointer to the larger of a and b, or nil.
UMaxVal returns the largest argument passed.
UMin returns the smaller of a and b.
UMinPtr returns a pointer to the smaller of a and b, or nil.
UMinVal returns the smallest argument passed.
Package-Level Variables (total 12, in which 3 are exported)
MaxInt128 represents the maximun Int128 value as big.Int
MaxUint128 represents the maximun Uint128 value as big.Int
MinInt128 represents the minimun Int128 value as big.Int
Package-Level Constants (total 10, in which 7 are exported)
Architecture and/or implementation specific integer limits and bit widths.
Specific approximation method tags
Architecture and/or implementation specific integer limits and bit widths.
Architecture and/or implementation specific integer limits and bit widths.
Architecture and/or implementation specific integer limits and bit widths.
Specific approximation method tags
Architecture and/or implementation specific integer limits and bit widths.
 |
The pages are generated with Golds v0.3.6. (GOOS=darwin GOARCH=amd64) Golds is a Go 101 project developed by Tapir Liu. PR and bug reports are welcome and can be submitted to the issue list. Please follow @Go100and1 (reachable from the left QR code) to get the latest news of Golds. |