math

Documentation

Index

• func Abs[T constraints.Integer | constraints.Float](a T) T
• func Diff[T constraints.Integer | constraints.Float](a, b T) T
• func EulerTotient(n int) int
• func Factorial[T constraints.Integer](x T, mod T) T
• func FastFourierTransform(p []complex128, inverse bool) []complex128
• func GCD[T constraints.Integer](a, b T) T
• func Hash(data any) uint
• func LCM[T constraints.Integer](a, b T) T
• func Max[T constraints.Ordered](elements ...T) T
• func Min[T constraints.Ordered](elements ...T) T
• func ModularInverse[T constraints.Integer](x T, mod T) T
• func MultiplyPolynomials(p1, p2 []int) []int
• func Pow[B constraints.Float | constraints.Integer, P constraints.Integer](base B, power P) B
• func Pow2[B constraints.Float | constraints.Integer](base B) B
• func PowGeneric[B any, P constraints.Integer](base B, power P, identity B, mul func(a, b B) B) B
• func PowMod[B constraints.Integer, P constraints.Integer](base B, power P, mod B) B
• func PrimesUpTo(n int) []bool

Functions

func Abs

func Abs[T constraints.Integer | constraints.Float](a T) T

func Diff

func Diff[T constraints.Integer | constraints.Float](a, b T) T

func EulerTotient

func EulerTotient(n int) int

Using code from: cp-algorithms.com/algebra/phi-function.html Assumptions: - n >= 1

func Factorial

func Factorial[T constraints.Integer](x T, mod T) T

Assumption: - x >= 0

func FastFourierTransform

func FastFourierTransform(p []complex128, inverse bool) []complex128

func GCD

func GCD[T constraints.Integer](a, b T) T

Euclidean algorithm It returns the positive solution Assumptions: - At least one != 0

func Hash

func Hash(data any) uint

Non-cryptographic hash (FNV-1a)

func LCM

func LCM[T constraints.Integer](a, b T) T

It returns the positive solution If one is 0, returns 0 Assumptions: - Both != 0

func Max

func Max[T constraints.Ordered](elements ...T) T

Assumptions: len(elements) > 0

func Min

func Min[T constraints.Ordered](elements ...T) T

Assumptions: len(elements) > 0

func ModularInverse

func ModularInverse[T constraints.Integer](x T, mod T) T

Assumption: - x and mod are coprimes

func MultiplyPolynomials

func MultiplyPolynomials(p1, p2 []int) []int

func Pow

func Pow[B constraints.Float | constraints.Integer, P constraints.Integer](base B, power P) B

Pow to an integer using binary exponentiation Assumption: - Multiplication is associative

func Pow2

func Pow2[B constraints.Float | constraints.Integer](base B) B

Assumption: - Multiplication is associative

func PowGeneric

func PowGeneric[B any, P constraints.Integer](base B, power P, identity B, mul func(a, b B) B) B

Pow to an integer using binary exponentiation Assumption: - Multiplication is associative

func PowMod

func PowMod[B constraints.Integer, P constraints.Integer](base B, power P, mod B) B

Pow to an integer using binary exponentiation Assumption: - Multiplication is associative

func PrimesUpTo

func PrimesUpTo(n int) []bool

Time complexity: O(n)

Optimized version of the following:

func genPrimesBest(n int) []bool {
	isPrime := make([]bool, n+1)
	for i := 2; i <= n; i++ {
		isPrime[i] = true
	}
	primes := make([]int, 0)
	var f func(int, int)
	f = func(i int, prod int) {
		for j := 0; j <= i && primes[j]*prod <= n; j++ {
			isPrime[primes[j]*prod] = false
			f(j, primes[j]*prod)
		}
	}
	lastIndex := 0
	for i := 2; i < n; i++ {
		if isPrime[i] {
			primes = append(primes, i)
			f(lastIndex, i)
			lastIndex++
		}
	}
	return isPrime
}