Skip to content

Algebra and number theory: API index

Find an operation by its purpose. Entries link to the complete signature and contract.

HMath.Algebra

API Purpose
Semiring Commutative addition, associative multiplication, distributivity, additive identity and absorbing zero.
zero Additive identity.
one Additive identity.
plus Additive identity.
times Additive identity.
Ring A semiring whose additive monoid is an abelian group.
negateRing Additive inverse.
Field A commutative ring in which each nonzero element has an inverse.
inverseField Multiplicative inverse; zero returns a domain error.
Group An associative operation with identity and inverse.
groupIdentity Group identity.
groupCombine Group identity.
groupInverse Group identity.
Additive A ring viewed as its additive group.
Additive Declaration and type contract below.
getAdditive Recover the underlying ring element.
Module A left module with checked addition for runtime vector shapes.
moduleScale Scalar action.
moduleAdd Scalar action.
VectorSpace A module over a field.
linearCombination Checked linear combination.
semiringLaws Exhaustive semiring identities on the supplied finite sample.
ringLaws Semiring laws plus additive inverses on a finite sample.
fieldLaws Ring laws, commutative multiplication and nonzero inverses.
groupLaws Group identities on a finite sample.
moduleLaws Check module scalar identity, composition, and both distributive laws.
Modular A canonical residue in Z/mZ, retaining its runtime modulus.
modular Construct a residue, requiring m>1; arbitrary signed values are reduced.
modularValue Canonical value in [0,m).
modularModulus Modulus greater than one.
addModular Checked residue addition.
subtractModular Checked residue subtraction.
multiplyModular Checked residue multiplication.
inverseModular Invert a unit; zero and nonunits are domain errors.
powerModular Integer power, with negative powers supported for units.
FiniteField An irreducible monic modulus over the proven prime field F_p.
finiteField Construct GF(p^n) from an irreducible polynomial of positive degree.
primeField Prime field GF(p), represented as F_p[x]/(x).
fieldCharacteristic Prime characteristic p.
fieldDegree Extension degree n.
fieldCardinality Exact carrier size p^n.
fieldModulus Ascending coefficients of the monic irreducible defining polynomial.
FieldElement A canonical residue polynomial of degree smaller than its field degree.
fieldElement Reduce an arbitrary integer polynomial into a finite field.
fieldElementCoefficients Canonical ascending residue coefficients (trailing zeros removed).
fieldElements Enumerate the complete carrier, rejecting sizes above an explicit storage budget.
addField Addition; different defining fields are rejected even if isomorphic.
negateField Additive inverse in the same field.
subtractField Checked field subtraction.
multiplyField Checked field multiplication, reduced modulo the defining polynomial.
inverseFieldElement Nonzero inverse via the finite-field identity a^(q-2).
powerField Binary exponentiation, with inverses for negative exponents.
finiteFieldLaws Exhaustive carrier checks for small fields, including distributivity, associativity, identities and every nonzero inverse.

HMath.Algorithms

API Purpose
lowerBound Given a target and ascending list, return the first zero-based insertion index whose value is >= target, or length at the end.
upperBound Given a target and ascending list, return the first insertion index whose value is > target.
binarySearch Given target and ascending list, return Just the first matching zero-based index or Nothing if absent.
interpolationSearch Search ascending Integer values using value-based interpolation, returning the first matching index or Nothing.
exponentialSearch Given a target and ascending finite list, grow a search range then find a matching index or Nothing.
ternarySearch Fixed-iteration minimization of a unimodal finite function on [lo,hi].
quickselect Given a zero-based order-statistic index and list, return the element at that position in ascending order without returning a sorted list.
introselect Like quickselect, but bound pivot depth and fall back to heap sorting.
partialSort Given k in [0,length] and a list, return the k smallest values in ascending order, retaining duplicates.
mergeSort Stable ascending merge sort under a lawful total Ord; accepts empty lists.
quicksort Ascending reference quicksort preserving equal values, using the head as pivot.
heapsort In-place-style array max heap with persistent updates.
introsort Ascending comparison sort with bounded quickselect-style partition depth and heap-sort fallback.
countingSort Given a nonnegative value-range budget then an Int list, return ascending counting sort.
radixSort Sort unbounded Integers in ascending order by radix digits, separating negative and nonnegative magnitudes.
bucketSort Given bucket count in [1,65536] and finite Doubles in [0,1], sort ascending using buckets and merge sort.
argsort Return original zero-based indices in stable ascending value order.
topK Alias of partialSort: return the k smallest values in ascending order, not the k largest. k outside [0,length] fails.
quantileSelect Given finite q in [0,1] and a nonempty finite Double list, linearly interpolate the ascending order statistics at q*(n-1).
deduplicate Sort ascending and keep one representative of each equal value.
numericGroups Sort ascending and return each distinct value paired with its frequency.
runLengthEncode Encode adjacent equal runs as (value,count), preserving run order without sorting.
runLengthDecode Given maximum output length then (value,count) runs, expand runs.
prefixSums Return cumulative sums including a leading zero; output length is n+1.
suffixSums Return suffix sums including a final zero; output length is n+1.
differenceArray Return first differences relative to a leading zero, preserving length.
applyDifferences Reconstruct values from first differences by inclusive cumulative sum.
coordinateCompression Return sorted unique keys and zero-based ranks for the original input order.
intervalSweep Half-open interval union length and peak overlap; zero-length intervals contribute neither.
divideConquerDP One DP layer next[j] = min_{0<=k<j} previous[k]+cost k j.
tabulateDP Bottom-up bounded DAG recurrence; dependencies must have lower indices.
memoizedDP Top-down memoization with a node budget.
binaryLift K-fold application of a total finite successor map, by repeated squaring.
integerMatrixPower Given square Integer rows and a nonnegative exponent, return exact matrix exponentiation by squaring; exponent zero returns identity.
polynomialHash Given base, modulus >1, then Integer sequence, fold h=(h*base+x) mod modulus from zero.
rollingHashes Noncryptographic polynomial rolling hash; equal hashes can collide.

HMath.Combinatorics

API Purpose
permutationsCount Given n,k in [0,4096], return n!/(n-k)! exactly, or zero when k>n.
combinationsCount Given n,k in [0,4096], return the exact binomial coefficient, or zero when k>n.
multinomial Given nonnegative group sizes whose sum is <=4096, return factorial(total)product(factorial sizes).
permutationsOf Distinct positions, including when values compare equal.
combinationsOf Given output budget, selection length k, then list, enumerate position-distinct k-element combinations in source order.
rankPermutation A permutation of [0,n), in lexicographic Lehmer order.
unrankPermutation Given size n in [0,4096] then zero-based rank in [0,n!), return the lexicographic permutation of [0..n-1].
rankCombination Given universe size n then strictly increasing distinct indices in [0,n), return the zero-based lexicographic combination rank.
unrankCombination Given universe size n, selection size k, then zero-based rank, return the increasing index list.
derangementCount Return exact number of permutations of n elements having no fixed points.
derangements Enumeration uses the factorial upper bound, so a request may be rejected even if its filtered derangement output would fit.
integerPartitions Nonincreasing positive parts.
setPartitions Set partitions of [0,n), using restricted-growth order of block labels.
stirlingFirst Signed first-kind Stirling numbers, coefficients of the falling factorial.
stirlingSecond Given n,k, return the exact number of partitions into k nonempty unlabeled blocks.
bellNumber Return the exact number of set partitions of n labeled objects, summing second-kind Stirling numbers.
eulerianNumber Given n,k, return the Eulerian recurrence counting permutations by ascents.
lahNumber Given n,k in [0,4096], return unsigned Lah number n!/k!*choose(n-1,k-1), with (0,0)=1 and impossible positive-size partitions giving zero.
catalanNumber Return exact Catalan number choose(2*n,n)/(n+1), requiring n in [0,4096].
fibonacci Return exact zero-based Fibonacci number by fast doubling for n in [0,4096].
lucas Return zero-based Lucas number using neighboring Fibonacci numbers. n and n+1 must both satisfy the [0,4096] bound, so n<=4095.
pascalTriangle Return Pascal rows zero through n inclusive, starting [[1]]. n must lie in [0,512]; invalid orders fail.
inclusionExclusion Union cardinality from all nonempty intersection sizes, indexed by subset bit mask 1 through 2^n-1.
subsets Given maximum output count then list, enumerate its position-based powerset.
cartesianProduct Given output budget then a list of lists, return all ordered choices using sequence.
multisetPermutations Given budget then ordered values, enumerate distinct multiset permutations in ascending lexicographic order.
multisetCount Return the multinomial count of distinct permutations of a list, grouping equal values in sorted order.
linearRecurrence a[n] = sum c[i]*a[n-i-1]; initial values have the same length as coefficients.
generatingCoefficients Formal power-series division P(x)/Q(x) around zero, exact rationals.
convolveSeries Given output length n then two coefficient lists, return the first n exact Integer convolution coefficients, treating absent coefficients as zero. n must lie in [0,4096].
finiteDifferences Return successive forward-difference rows beginning with the original list and ending at the last singleton.
finiteSum Sum a finite list using its Num arithmetic.

HMath.Complex

API Purpose
Complex A data type representing complex numbers.
complex Construct a finite number from real and imaginary parts.
realPart Extracts the real part of a complex number.
imagPart Extracts the imaginary part of a complex number.
magnitude The non-negative magnitude of a complex number.
phase The phase of a complex number, in the range (-pi, pi].
conjugate The conjugate of a complex number.
reciprocal Reciprocal using scaled division to avoid squaring a large norm.
add Checked sum.
subtractComplex Checked difference.
multiply Checked product.
divide Smith scaled division.
power Principal complex power. 0^0 is 1; other zero-base exponents must be positive real.
Elementary Elementary functions with principal inverse-function branches.
Exp Declaration and type contract below.
Log Declaration and type contract below.
Sqrt Declaration and type contract below.
Sin Declaration and type contract below.
Cos Declaration and type contract below.
Tan Declaration and type contract below.
Sinh Declaration and type contract below.
Cosh Declaration and type contract below.
Tanh Declaration and type contract below.
Asin Declaration and type contract below.
Acos Declaration and type contract below.
Atan Declaration and type contract below.
Asinh Declaration and type contract below.
Acosh Declaration and type contract below.
Atanh Declaration and type contract below.
elementary Apply an elementary function, rejecting poles and nonfinite results.
fromPolar Polar construction with nonnegative finite radius.
toPolar Radius and principal phase; the phase of zero is defined by Data.Complex.
rotate Counterclockwise rotation in the complex plane.
complexMatrix Checked finite complex matrix, at most 256 rows and columns.
multiplyMatrices Matrix multiplication with finite-result validation.
conjugateTranspose Hermitian transpose with finite-input validation.
complexFFT Existing checked mixed-radix/Bluestein forward FFT.
complexIFFT Existing checked inverse FFT, normalized by sample count.

HMath.NumberTheory

API Purpose
gcdInteger Nonnegative greatest common divisor; gcdInteger 0 0 = 0.
lcmInteger Nonnegative least common multiple; zero if either argument is zero.
extendedGCD (g,x,y) with ax+by=g>=0, also for negative inputs and zero.
bezout Bezout coefficients only; see extendedGCD.
modPow Binary modular exponentiation.
modInverse Canonical inverse residue in [0,m).
chineseRemainder Generalized CRT for (residue,positive modulus) pairs.
linearDiophantine One solution and a direction: (x,y,dx,dy) represents every solution (x+kdx,y+kdy) of ax+by=c.
integerSquareRoot Floor of the square root, computed by exact integer Newton iteration.
perfectPower Find a representation n = base^exponent with exponent greater than one.
isPrimeExact Proven primality using trial division.
nextPrime First proven prime at least the requested integer.
millerRabin Strong Miller--Rabin for explicitly supplied bases (each >=2).
bailliePSW Baillie--PSW: base-2 strong Miller--Rabin plus strong Lucas--Selfridge.
sieveEratosthenes Eratosthenes sieve through an inclusive nonnegative upper bound.
sieveAtkin Atkin quadratic-residue sieve, followed by removal of prime-square multiples.
segmentedSieve Segmented sieve on the inclusive interval [lo,hi].
primeFactorization Exact trial factorization of a positive integer.
pollardRho Pollard rho with Floyd cycle detection, explicit seed and iteration budget.
pollardPMinusOne Pollard p-1 stage one with a smoothness bound >=2 and base.
fermatFactor Fermat difference-of-squares factorization, with an explicit step budget.
divisors All positive divisors in increasing order, under a factorization budget.
divisorSum Sum of positive divisors.
divisorCount Number of positive divisors.
eulerTotient Euler totient, including phi(1)=1.
carmichael Carmichael's exponent of the multiplicative unit group.
mobius Mobius function on positive integers.
liouville Liouville function, counting prime factors with multiplicity.
multiplicativeOrder Multiplicative order of a unit modulo a modulus >1.
primitiveRoot Smallest generator of the units modulo m, if that group is cyclic.
discreteLog Baby-step giant-step discrete logarithm of a unit.
legendreSymbol Legendre symbol for a proven odd prime modulus, with proof budget.
jacobiSymbol Jacobi symbol for a positive odd denominator.
kroneckerSymbol Kronecker symbol, extending Jacobi to every integer denominator.
tonelliShanks Tonelli--Shanks modular square root for a proven prime modulus.
continuedFraction Finite simple continued fraction of a rational, using floor division.
fromContinuedFraction Evaluate a finite continued fraction.
convergents Successive convergents, rejecting invalid finite prefixes.
farey Farey sequence of positive order, including zero and one.
pellFundamental Minimal positive solution to x^2-d*y^2=1 via continued fractions of sqrt d.
isPerfectNumber Perfect-number predicate on positive integers.
areAmicable Amicable-number predicate; equal numbers are not an amicable pair.
partitions Integer partitions in descending part order.
partitionCount Partition count by exact dynamic programming, O(n^2) work and O(n) storage.
fibonacciFast Signed-index Fibonacci by fast doubling; F(-n)=(-1)^(n+1)F(n).

HMath.Polynomial

API Purpose
Polynomial Canonical, finite ascending coefficient sequence.
polynomial Construct a polynomial, deleting trailing exact zeros (no floating tolerance).
coefficients Ascending coefficients, with no trailing zero; zero gives an empty list.
polynomialDegree Degree of a nonzero polynomial; zero has no degree.
evaluatePolynomial Horner evaluation, with the constant coefficient first in storage.
addPolynomial Coefficientwise addition with canonical exact-zero normalization.
subtractPolynomial Coefficientwise subtraction.
scalePolynomial Multiply every coefficient by a scalar.
multiplyPolynomial Exact schoolbook convolution, including zero polynomials.
composePolynomial Composition p(q(x)) by polynomial Horner evaluation.
dividePolynomial Long division over a field.
monicPolynomial Normalize a nonzero polynomial to leading coefficient one; zero remains zero.
gcdPolynomial Monic Euclidean GCD over an exact field; gcd(0,0)=0.
differentiatePolynomial Formal derivative.
integratePolynomial Formal integral with the supplied integration constant.
squareFreeFactors Monic square-free factors with positive multiplicities over Rational.
rationalRoots Rational roots with exact multiplicities using the rational-root theorem.
factorRationalPolynomial Complete rational factorization by bounded Kronecker interpolation.
sturmSequence Sturm chain over exact rationals, after removing the derivative GCD.
countRealRoots Number of distinct real roots in (a,b].
isolateRealRoots Isolate every distinct real root in rational intervals with disjoint interiors and width at most tolerance.
durandKerner Durand--Kerner simultaneous complex root iteration.
aberthEhrlich Aberth--Ehrlich simultaneous iteration, combining Newton corrections with mutual-root repulsion.
companionMatrix Frobenius companion matrix of a nonconstant polynomial, with ones on the subdiagonal and negated monic coefficients in the last column.
lagrangeInterpolation Exact Lagrange interpolating polynomial.
newtonInterpolation Newton divided differences, returned in the standard power basis.
chebyshevPolynomial Chebyshev T_n, normalized by T_0=1, T_1=x.
legendrePolynomial Legendre P_n, normalized by P_n(1)=1.
hermitePolynomial Physicists' Hermite H_n: H_0=1, H_1=2x.
laguerrePolynomial Ordinary Laguerre L_n with alpha=0 and L_n(0)=1.
bernsteinPolynomial Bernstein basis binomial(n,k)x^k(1-x)^(n-k) for 0<=k<=n.
polynomialRegression Least-squares power-basis regression using column-pivoted Householder QR.
chebyshevApproximation Truncated Chebyshev interpolation at first-kind nodes on [-1,1], returned in power basis.
PowerSeries A finite Taylor jet, coefficients ascending and zeros retained.
powerSeries Construct a jet with explicit coefficients, including trailing zeros.
seriesCoefficients Stored Taylor coefficients; coefficient n multiplies x^n, not x^n/n!.
addSeries Add jets to their common truncation order.
multiplySeries Multiply jets by truncated convolution.
reciprocalSeries Reciprocal jet from coefficient recurrence; constant term must be nonzero.
divideSeries Divide jets to their common order; denominator constant must be nonzero.
composeSeries Formal composition to the inner jet's order.
differentiateSeries Derivative jet has one fewer coefficient.
integrateSeries Integral jet with supplied constant, one coefficient longer.
expSeries Exponential of a finite jet from b'=a'b; constant uses the coefficient type's exp.
logSeries Formal log through derivativedivisionintegration.
RationalFunction Reduced exact rational function with monic denominator.
rationalFunction Normalize by polynomial GCD and reject a zero denominator.
rationalNumerator Reduced numerator.
rationalDenominator Monic reduced denominator.
evaluateRationalFunction Exact evaluation, rejecting poles.
addRationalFunction Exact rational-function addition with cancellation.
multiplyRationalFunction Exact rational-function multiplication with cancellation.
partialFractions Exact partial fractions over Q.

HMath.Special

API Purpose
SFResult Finite value and estimated absolute numerical error.
SFResult Declaration and type contract below.
sfValue Returned special-function numerical estimate.
sfError Absolute numerical error estimate accompanying sfValue.
gamma Real gamma using C99 libm; rejects nonfinite arguments and nonpositive integer poles.
logGamma Natural logarithm of gamma for strictly positive finite arguments; avoids overflow of gamma itself.
gammaP Regularized lower incomplete gamma.
gammaQ Regularized upper gamma Q(a,x); the upper-tail continued fraction is evaluated directly when x>=a+1.
incompleteGamma Unregularized lower gamma gamma(a,x)=Gamma(a)*P(a,x).
beta Beta function for strictly positive parameters, evaluated through log gamma.
logBeta Log beta for strictly positive finite parameters.
betaI Regularized lower incomplete beta I_x(a,b), positive parameters and x in [0,1], via reflected Lentz continued fraction.
incompleteBeta Unregularized lower incomplete beta B_x(a,b).
digamma Log-gamma derivative for x>0, using recurrence to x>=12 and an inverse-power asymptotic expansion.
trigamma First polygamma derivative for x>0, using the Hurwitz-zeta identity.
polygamma Derivative order 0..32 of digamma for x>0; higher orders use signed factorial times Hurwitz zeta.
erf Real error function from C99 libm; finite arguments required.
erfc Real complementary error function from C99 libm; upper tails avoid subtracting erf from one.
inverseErf Real inverse error function for -1<x<1, using the normal inverse identity.
erfcx exp(x^2)*erfc(x), with a large-positive-x inverse-power asymptotic expansion to avoid overflow.
normalCDF Standard-normal CDF through erfc, with stable small lower tails.
normalQuantile Standard-normal inverse CDF for 0<p<1.
dawson Dawson integral for |x|<=100; scaled quadrature below |x|=10, inverse-power asymptotics above.
exponentialIntegral E_n(x), integer n=0..100000,x>0.
logarithmicIntegral Real principal-value Ei for x>0; logarithmic integral li(x)=Ei(log x), with the real PV continuation on 0<x<1.
sineIntegral Real Si(x) on |x|<=1000, with its removable singularity explicitly filled at zero.
cosineIntegral Real Ci(x) on 0<x<=1000, using phase-resolved quadrature near zero and inverse-power oscillatory asymptotics above x=50.
fresnel Fresnel (C,S), phase pi*t^2/2, |x|<=100.
ellipticF Legendre incomplete elliptic integrals, parameter m (not modulus k), real branch |phi|<=pi/2, m<1; Pi additionally n<1.
ellipticE Legendre incomplete second-kind elliptic integral with the same amplitude/parameter convention.
ellipticPi Legendre third-kind integral with arguments characteristic n, amplitude phi, parameter m; n<1, m<1, |phi|<=pi/2.
jacobiElliptic Real (sn,cn,dn), |u|<=10^6 and 0<=m<1, using periodic amplitude inversion.
besselJ Integer-order J_n(x) from libm, |n|<=100000 and finite real x.
besselY Integer-order Y_n(x) from libm, |n|<=100000 and x>0.
besselI Modified Bessel I_n(x) via its convergent series, integer order 0..100 and |x|<=700.
besselK Modified Bessel K_n(x)=exp(-x)*scaledBesselK(n,x), integer order 0..100,x>0.
sphericalBesselJ Spherical j_n(x), order 0..100; uses a series for small x relative to order and upward recurrence otherwise.
sphericalBesselY Spherical y_n(x), integer order 0..100,x>0, by upward recurrence.
hankel Complex H_n^(kind)(x)=J_n(x)+/-iY_n(x), kind 1 or 2, integer order and x>0.
airy Airy Ai,Bi and derivatives solve y''=x y by convergent Maclaurin series.
struve Real Struve H_nu(x) by a convergent series; nu>-3/2 and 0<=x<=30.
hypergeometric Generalized pFq power series.
hypergeometric1F1 Kummer confluent hypergeometric 1F1(a;b;z), real power-series evaluation with denominator-pole rejection.
hypergeometric2F1 Gauss 2F1(a,b;c;z) in the real power-series disk |z|<1.
complex1F1 Complex Kummer 1F1 in its entire z plane, rejecting denominator poles and nonfinite arithmetic; cancellation can limit accuracy for large imaginary z.
legendre Legendre P_n(x), n=0..1000 and |x|<=1.
associatedLegendre Associated P_l^m(x) with Condon--Shortley phase, 0<=m<=l<=1000 and |x|<=1.
sphericalHarmonic Orthonormal complex spherical harmonic Y_l^m(theta,phi), theta in [0,pi], including negative-m conjugation symmetry.
riemannZeta Real zeta: Euler--Maclaurin for s>1, Euler-transformed eta for 0<s<1 and reflection for -170<s<0.
hurwitzZeta Hurwitz zeta for s>1,q>0 using 64 explicit terms plus seven Euler--Maclaurin corrections.
polylogarithm Real polylog Li_s(z) in the convergent power-series disk |z|<1; no cross-cut continuation is implied.
dilogarithm Real Li_2(x) for x<=1, with reflection and negative-axis transformations for convergent evaluation.
lambertW Real Lambert W branch 0 or -1, x>=-1/e and x<0 on branch -1, using bounded Halley iteration.
debye Normalized Debye D_n(x), integer n=1..16,x>=0, with D_n(0)=1.
clausen Periodic Clausen Cl_2(theta) from an integral with a squared-variable substitution at its logarithmic endpoint.
fermiDirac Complete normalized Fermi--Dirac integral F_order(eta), 0<=order<=20, |eta|<=100.
boseEinstein Complete normalized Bose--Einstein integral, same order range, -100<=eta<=0 and positive order at eta=0.
coulombWave Regular and irregular Coulomb waves F_l,G_l.
gegenbauer Gegenbauer C_n^alpha(x), degree 0..10000 and alpha>-12, alpha=0, by three-term recurrence.
parabolicCylinder Real D_nu(x) via Kummer's representation; reference |x|<=6, |nu|<=10.
mathieu Mathieu ce_n (even=True) or se_n, from a 32-term Fourier Galerkin eigenproblem. ce(0)=1 or se'(0)=1.
bernoulliPolynomial Exact rational Bernoulli/Euler coefficients evaluated as Double.
eulerPolynomial Euler E_n(x), n=0..100, from the Bernoulli duplication identity.
wigner3j Angular momenta and projections are encoded as doubled integers, allowing half-integers exactly.
wigner6j Racah factorial sum for a Wigner 6j symbol; each angular momentum is a doubled integer in 0..60.
wigner9j Wigner 9j as a finite sum of three 6j symbols; accepts nine row-major doubled angular momenta in 0..30.
clebschGordan Clebsch--Gordan coefficient <j1 m1,j2 m2|j m> through the Condon--Shortley 3j convention; all arguments doubled integers.
scaledBesselI exp(-|x|)*I_n(x).
scaledBesselK exp(x)*K_n(x) from its cosh integral, integer order 0..100,x>0; scaling is inside the integrand.