Maths

maths includes mathematical functions not defined in the standard Go math package. Most functions support any primitive integer or float type through generics.

Installation

go get github.com/theriault/maths 

What's Included

Combinatorics

import "github.com/theriault/maths/combinatorics"

Factorial

Source | Tests | Wikipedia | OEIS

$\displaystyle n! \; = \; \prod_{i=1}^{n} i$

combinatorics.Factorial(10) // will return uint64(3628800)

Falling Factorial

Source | Tests | Wikipedia

$\displaystyle x^{\underline{n}} \; = \; \prod _{k=1}^{n}(x-k+1)$

combinatorics.FallingFactorial(8, 3) // will return uint64(336)
combinatorics.PartialPermutations(8, 3) // will return uint64(336)

Rising Factorial

Source | Tests | Wikipedia

$\displaystyle x^{\overline{n}} \; = \; \prod _{k=1}^{n}(x+k-1)$

combinatorics.RisingFactorial(2, 3) // will return uint64(24)

Number Theory

import "github.com/theriault/maths/numbertheory"

Aliquot Sum

Source | Tests | Wikipedia | OEIS

$\displaystyle s(n) = \sigma_1(n) - n = \sum_{\substack{i = 1 \\ i | n}}^{n-1} i$

numbertheory.AliquotSum(60) // will return uint64(108)

Coprime

Source | Tests | Wikipedia

$\displaystyle f(a,b) = \begin{cases}\text{true} &\text{if}\ \gcd(a,b) = 1 \\ \text{false} &\text{else} \end{cases}$

numbertheory.Coprime(3*5*7, 11*13*17) // will return true

Digit Sum

Source | Tests | Wikipedia

$\displaystyle f_b(n) = \sum_{i=0}^{\lfloor \log_b{n} \rfloor} \frac{n \bmod b^{i+1} - n \bmod b^i}{b^i}$

numbertheory.DigitSum(9045, 10) // will return int(18)

Digital Root

Source | Tests | Wikipedia

$\displaystyle f_{b}(n)={\begin{cases} 0 &\text{if}\ n=0\\ n\ \bmod (b-1)&{\text{if}}\ n\not \equiv 0{\pmod {b-1}} \\ b-1 &\text{else} \end{cases}}$

numbertheory.DigitalRoot(9045, 10) // will return int(9)

Divisors function

$\displaystyle \sigma_z(n) = \sum_{\substack{i = 1 \\ i | n}}^{n} i^{z}$

Number-of-divisors (z = 0)

Source | Tests | Wikipedia | OEIS

numbertheory.NumberOfDivisors(48) // will return uint64(10)

Sum-of-divisors (z = 1)

Source | Tests | Wikipedia | OEIS

numbertheory.SumOfDivisors(48) // will return uint64(124)

Greatest Common Divisor

Source | Tests | Wikipedia

numbertheory.GCD(48,18) // will return int(6)

Least Common Multiple

Source | Tests | Wikipedia

numbertheory.LCM(48,18) // will return int(144)

Möbius function

Source | Tests | Wikipedia | OEIS

$\displaystyle \mu(n) = \begin{cases} +1 & n \text{ is square-free with even number of prime factors} \\ -1 & n \text{ is square-free with odd number of prime factors} \\ 0 & n \text{ is not square-free} \end{cases}$

numbertheory.Mobius(70) // will return int8(-1)

Politeness

Source | Tests | Wikipedia | OEIS

$\displaystyle p(n) = \left( \prod_{\substack{p |n \\ p \neq 2}}^{n} v_p(n) + 1\right)-1$

where $v_p(n)$ is the $p$-adic order

numbertheory.Politeness(32) // will return uint64(0)

Polygonal Numbers

Source | Tests | Wikipedia

$\displaystyle p(s, n) = \frac{(s-2)n^2-(s-4)n}{2}$

numbertheory.PolygonalNumber(3, 4) // will return uint64(10)

Finding $n$:

$\displaystyle p(s, x) = \frac{\sqrt{8(s-2)x+(s-4)^2}+(s-4)}{2(s-2)}$

numbertheory.PolygonalRoot(3, 10) // will return float64(4)

Finding $s$:

$\displaystyle p(n, x) = 2+\frac{2}{n} \cdot \frac{x-n}{n-1}$

numbertheory.PolygonalSides(4, 10) // will return float64(3)

Prime Factorization

Source | Tests | Wikipedia

numbertheory.PrimeFactorization(184756) // will return []uint64{2, 2, 11, 13, 17, 19}

Primorial

Source | Tests | Wikipedia | OEIS

$\displaystyle n\# = \prod_{\substack{i=2 \\ i \in \mathbb{P}}}^{n} i$

numbertheory.Primorial(30) // will return uint64(6469693230)

Radical

Source | Tests | Wikipedia | OEIS

$\displaystyle rad(n) = \prod_{p | n}p$

numbertheory.Radical(60) // will return uint64(30)

Totient

Euler's Totient

Source | Tests | Wikipedia | OEIS

$\displaystyle \varphi(n) = n \prod_{p | n} \left(1 - \frac{1}{p}\right) $

numbertheory.Totient(68) // will return uint64(32)

Jordan's Totient

Source | Tests | Wikipedia

$\displaystyle J_k(n) = n^k \prod_{p | n} \left(1 - \frac{1}{p^k}\right) $

numbertheory.TotientK(60, 2) // will return uint64(2304)

Statistics

import "github.com/theriault/maths/statistics"

Average/Mean

Generalized Mean

Source | Tests | Wikipedia

statistics.GeneralizedMean([]float64{1, 1000}, 2) // will return float64(707.1071347398497)
statistics.RootMeanSquare(1, 1000)  // will return float64(707.1071347398497)

Arithmetic Mean

Source | Tests | Wikipedia

$\displaystyle \bar{x} = \frac{1}{n}\left (\sum_{i=1}^n{x_i}\right ) = \frac{x_1+x_2+\cdots +x_n}{n}$

statistics.Mean(1, 1000) // will return float64(500.5)

Geometric Mean

Source | Tests | Wikipedia

$\displaystyle \bar{x} = \left( \prod_{i=1}^n{x_i} \right )^\frac{1}{n} = \exp{\left( {\frac{1}{n}\sum\limits_{i=1}^{n}\ln x_i} \right)} = \left(x_1 x_2 \cdots x_n \right)^\frac{1}{n}$

statistics.GeometricMean(1, 1000) // will return float64(31.62...)

Harmonic Mean

Source | Tests | Wikipedia

$\displaystyle \bar{x} = n \left ( \sum_{i=1}^n \frac{1}{x_i} \right ) ^{-1}$

statistics.HarmonicMean(1, 1000) // will return float64(1.99...)

Central Moment

Source | Tests | Wikipedia

statistics.CentralMoment([]uint8{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, 2) // returns float64(8.25)

Interquartile Range (IQR)

Source | Tests | Wikipedia

statistics.InterquartileRange(3, 6, 7, 8, 8, 10, 13, 15, 16, 20) // returns float64(7.25)

Kurtosis

Population

Source | Tests | Wikipedia

statistics.Kurtosis(8, 3, 6, 2, 7, 1, 8, 3, 7, 4, 8) // returns float64(1.5133)

Sample

Source | Tests | Wikipedia

statistics.SampleKurtosis(8, 3, 6, 2, 7, 1, 8, 3, 7, 4, 8) // returns float64(2.522167)

Excess Sample Kurtosis

Source | Tests | Wikipedia

statistics.ExcessSampleKurtosis([]uint8{8, 3, 6, 2, 7, 1, 8, 3, 7, 4, 8}) // returns float64(-1.6445)

Logistic Function

Source | Tests | Wikipedia

$\displaystyle f(x) = \frac{L}{1+e^{-k(x-x_0)}}$

• $L$ - curve's max value
• $x_0$ - sigmoid's midpoint
• $k$ - logistic growth rate

maxValue := 1.0
midpoint := 0.0
growthRate := 1.0
fx := statistics.LogisticFunction(maxValue, midpoint, growthRate) // will return func (x float64) float64

Mode

Source | Tests | Wikipedia

statistics.Mode(8, 3, 6, 2, 7, 1, 8, 3, 7, 4, 8) // will return []float64{8}

Moving Averages

Simple Moving Average

Source | Tests | Wikipedia

$\displaystyle {\begin{aligned}{\textit {SMA}}{k}&={\frac{p{n-k+1}+p_{n-k+2}\cdots +p_{n}}{k}}\&={\frac{1}{k}}\sum_{i=n-k+1}^np_i\end{aligned}}$

statistics.SimpleMovingAverage(3, 1, 2, 3, 4, 5, 6, 7, 8, 9) // will return []float64{2, 3, 4, 5, 6, 7, 8}

Power Sum

Source | Tests | Wikipedia

$\displaystyle S_p(x_1, x_2, ..., x_n) = \sum_{i=1}^{n} x_i^p$

statistics.PowerSum([]float64{2, 3, 4}, 2) // will return float64(29)

Power Sum Around

Source | Wikipedia

$\displaystyle S_{p,y}(x_1, x_2, ..., x_n) = \sum_{i=1}^{n} (x_i - y)^p$

statistics.PowerSumAround([]float64{2, 3, 4}, 3, 2) // will return float64(29)

Quantiles (Median/Tertile/Quartile/.../Percentile)

Source | Tests | Wikipedia

n := []float64{3, 6, 7, 8, 8, 10, 13, 15, 16, 20}
statistics.Quantile(n, 2) // median: will return []float64{9}
statistics.Quantile(n, 3) // tertiles: will return []float64{8, 13}
statistics.Quantile(n, 4) // quartiles: will return []float64{7.25, 9, 14.5}
statistics.Quantile(n, 100) // percentile: will return []float64{3.27, 3.54, 3.81, 4.08, ...95 other values...}

// aliases
statistics.Tertile(n) // will return []float64{8, 13}
statistics.Quartile(n) // will return []float64{7.25, 9, 14.5}
statistics.Percentile(n) // will return []float64{3.27, 3.54, 3.81, 4.08, ...95 other values...}

Median (Source | Tests | Wikipedia)

n := []float64{3, 6, 7, 8, 8, 10, 13, 15, 16, 20}
statistics.Median(n) // will return float64(9)

Sample Extrema (Max/Min/Range)

Sample Maximum / Largest Observation

Source | Tests | Wikipedia

n := []uint8{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
statistics.Max(n...) // will return uint8(10)

Sample Minimum / Smallest Observation

Source | Tests | Wikipedia

n := []uint8{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
statistics.Min(n...) // will return uint8(1)

Range

Source | Tests | Wikipedia

n := []uint8{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
statistics.Range(n...) // will return uint8(9)

Skewness

Population

Source | Tests | Wikipedia

statistics.Skewness(8, 3, 6, 2, 7, 1, 8, 3, 7, 4, 8) // returns float64(-0.274241)

Sample

Source | Tests | Wikipedia

statistics.SampleSkewness(8, 3, 6, 2, 7, 1, 8, 3, 7, 4, 8) // returns float64(-0.319584)

Standard Deviation

Population

Source | Tests | Wikipedia

$\displaystyle \sigma = \sqrt{\left(\frac{1}{N} \sum_{i=1}^{N} x_{i}^{2} \right) - \mu^2}$

statistics.StandardDeviation(8, 3, 6, 2, 7, 1, 8, 3, 7, 4, 8) // will return []float64{8}

Sample

Source | Tests | Wikipedia

$\displaystyle s = \sqrt{\sigma^2 \frac{N}{N-1}}$

statistics.SampleStandardDeviation(8, 3, 6, 2, 7, 1, 8, 3, 7, 4, 8) // will return []float64{8}

Standard Error

Population

Source | Tests | Wikipedia

$\displaystyle \sigma_{\bar{x}} = \frac{\sigma}{\sqrt{n}}$

statistics.StandardError(8, 3, 6, 2, 7, 1, 8, 3, 7, 4, 8) // will return []float64{8}

Sample

Source | Tests | Wikipedia

$\displaystyle s_{\bar{x}} = \frac{s}{\sqrt{n}}$

statistics.SampleStandardError(8, 3, 6, 2, 7, 1, 8, 3, 7, 4, 8) // will return []float64{8}

Softmax

Source | Tests | Wikipedia

X := []float64{1, 2, 3, 4, 1, 2, 3}
statistics.Softmax(X) // will return []float64{0.0236405, 0.0642617, 0.1746813, 0.4748330, 0.0236405, 0.0642617, 0.1746813}
statistics.MutableSoftmax(X) // same as above, but will modify X and return X

X = []float64{1, 2, 3, 4, 1, 2, 3}
statistics.GeneralizedSoftmax(X, 0.5) // will return []float64{0.0018889, 0.0139573, 0.1031315, 0.7620445, 0.0018889, 0.0139573, 0.1031315}

Sum/Summation

Source | Tests | Wikipedia

$\displaystyle S(x_1, x_2, ..., x_n) = \sum_{i=1}^{n} x_i $

statistics.Sum(1.1, 1.2, 1.3) // will return float64(3.6)

Variance

Population

Source | Tests | Wikipedia

$\displaystyle \sigma^2 = \left(\frac{1}{N} \sum_{i=1}^{N} x_{i}^{2} \right) - \mu^2$

statistics.Variance(8, 3, 6, 2, 7, 1, 8, 3, 7, 4, 8) // will return []float64{8}

Sample

Source | Tests | Wikipedia

$\displaystyle s^2 = \sigma^2 \frac{N}{N-1}$

statistics.SampleVariance(8, 3, 6, 2, 7, 1, 8, 3, 7, 4, 8) // will return []float64{8}

Weighted Average/Mean

Weighted Generalized Mean

Source | Tests | Wikipedia

X := []uint8{8, 7, 3, 2, 6, 11, 6, 7, 2, 1, 7}
W := []uint8{1, 2, 1, 1, 2, 1, 2, 1, 2, 1, 2}
mean, err := statistics.WeightedGeneralizedMean(X, Y, 1) // will return float64(5.5)

Weighted Arithmetic Mean

Source | Tests | Wikipedia

X := []uint8{8, 7, 3, 2, 6, 11, 6, 7, 2, 1, 7}
W := []uint8{1, 2, 1, 1, 2, 1, 2, 1, 2, 1, 2}
mean, err := statistics.WeightedMean(X, Y) // will return float64(5.5)

Weighted Geometric Mean

Source | Tests | Wikipedia

X := []uint8{8, 7, 3, 2, 6, 11, 6, 7, 2, 1, 7}
W := []uint8{1, 2, 1, 1, 2, 1, 2, 1, 2, 1, 2}
mean, err := statistics.WeightedGeometricMean(X, Y) // will return float64(4.6)

Weighted Harmonic Mean

Source | Tests | Wikipedia

X := []uint8{8, 7, 3, 2, 6, 11, 6, 7, 2, 1, 7}
W := []uint8{1, 2, 1, 1, 2, 1, 2, 1, 2, 1, 2}
mean, err := statistics.WeightedHarmonicMean(X, Y) // will return float64(5.8)

Complexity

See docs/complexity.md for information on time complexity and space complexity.