math

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
}