# arithmoi

Efficient basic number-theoretic functions. https://github.com/cartazio/arithmoi

 Version on this page: 0.9.0.0 LTS Haskell 13.25: 0.8.0.0 Stackage Nightly 2019-06-12: 0.9.0.0 Latest on Hackage: 0.9.0.0

See all snapshots `arithmoi` appears in

A library of basic functionality needed for number-theoretic calculations. The aim of this library is to provide efficient implementations of the functions. Primes and related things (totients, factorisation), powers (integer roots and tests, modular exponentiation).

## Changes

0.9.0.0
This release supports GHC 8.0, 8.2, 8.4 and 8.6.

Breaking changes:

Remove 'Prime' type family and introduce 'Prime' newtype. This newtype
is now used extensively in public API:

primes :: Integral a => [Prime a]
primeList :: Integral a => PrimeSieve -> [Prime a]
sieveFrom :: Integer -> [Prime Integer]
nthPrime :: Integer -> Prime Integer

'sbcFunctionOnPrimePower' now accepts 'Prime Word' instead of 'Word'.

'Math.NumberTheory.Primes.{Factorisation,Testing,Counting,Sieve}'
are no longer re-exported from 'Math.NumberTheory.Primes'.
Merge 'Math.NumberTheory.UniqueFactorisation' into
'Math.NumberTheory.Primes' (#135, #153).

From now on 'Math.NumberTheory.Primes.Factorisation.factorise'
and similar functions return [(Integer, Word)] instead of [(Integer, Int)].

Remove deprecated 'Math.NumberTheory.GCD' and 'Math.NumberTheory.GCD.LowLevel'.

Deprecate 'Math.NumberTheory.Recurrencies.*'.

New features:

New functions 'nextPrime' and 'precPrime'. Implement an instance of 'Enum' for primes (#153):

> [nextPrime 101 .. precPrime 130]
[Prime 101,Prime 103,Prime 107,Prime 109,Prime 113,Prime 127]

Support Gaussian and Eisenstein integers in smooth numbers (#138).

Add the Hurwitz zeta function on non-negative integer arguments (#126).

Implement efficient tests of n-freeness: pointwise and in interval. See 'isNFree' and 'nFreesBlock' (#145).

Generate preimages of the totient and the sum-of-divisors functions (#142):

> inverseTotient 120 :: [Integer]
[155,310,183,366,225,450,175,350,231,462,143,286,244,372,396,308,248]

Generate coefficients of Faulhaber polynomials 'faulhaberPoly' (#70).

Improvements:

Better precision for exact values of Riemann zeta and Dirichlet beta
functions (#123).

Speed up certain cases of modular multiplication (#160).

Extend Chinese theorem to non-coprime moduli (#71).

0.8.0.0
This release supports GHC 7.10, 8.0, 8.2, 8.4 and 8.6.

Breaking changes:

Stop reporting units (1, -1, i, -i) as a part of factorisation
for integers and Gaussian integers (#101). Now `factorise (-2)`
is `[(2, 1)]` and not `[(-1, 1), (2, 1)]`.

Deprecate an old interface of 'Math.NumberTheory.Moduli.Sqrt'
and roll out a new one, more robust and type safe (#87).

Deprecate 'Math.NumberTheory.GCD' and 'Math.NumberTheory.GCD.LowLevel' (#80).
Move 'splitIntoCoprimes' to 'Math.NumberTheory.Euclidean.Coprimes'.

Change types of 'splitIntoCoprimes', 'fromFactors' and 'prefFactors'
using newtype 'Coprimes' (#89).

Redesign API to modular square roots (#108)

Deprecate 'jacobi'' (#103).

Sort Gaussian primes by norm (#124).

Deprecate 'Math.NumberTheory.GaussianIntegers' in favor of

New features:

Implement Ramanujan tau function (#112):

> map ramanujan [1..10]
[1,-24,252,-1472,4830,-6048,-16744,84480,-113643,-115920]

Implement partition function (#115):

> take 10 partition
[1,1,2,3,5,7,11,15,22,30]

Add the Dirichlet beta function on non-negative integer arguments (#120).
E. g.,

> take 5 \$ Math.NumberTheory.Zeta.Dirichlet.betas 1e-15
[0.5,0.7853981633974483,0.9159655941772191,0.9689461462593693,0.9889445517411055]

Solve linear and quadratic congruences (#129).

Support Eisenstein integers (#121).

Implement discrete logarithm (#88).

Improvements:

Make return type of 'primes' and 'primeList' polymorphic instead of
being limited to 'Integer' only (#109).

Speed up factorisation of Gaussian integers (#116).

Speed up computation of primitive roots for prime powers (#127).

0.7.0.0
This release supports GHC 7.8, 7.10, 8.0, 8.2 and 8.4.

Breaking changes:

Remove 'Math.NumberTheory.Powers.Integer', deprecated in 0.5.0.0.

Deprecate 'Math.NumberTheory.Primes.Heap'.

Deprecate 'FactorSieve', 'TotientSieve', 'CarmichaelSieve' and
accompanying functions. Use new general approach for bulk evaluation

Now 'moebius' returns not a number, but a value of 'Moebius' type (#90).

New functions:

A general framework for bulk evaluation of arithmetic functions (#77):

> runFunctionOverBlock carmichaelA 1 10
[1,1,2,2,4,2,6,2,6,4]

Implement a sublinear algorithm for Mertens function (#90):

> map (mertens . (10 ^)) [0..9]
[1,-1,1,2,-23,-48,212,1037,1928,-222]

Add basic support for cyclic groups and primitive roots (#86).

Implement an efficient modular exponentiation (#86).

Write routines for lazy generation of smooth numbers (#91).

> smoothOverInRange (fromJust (fromList [3,5,7])) 1000 2000
[1029,1125,1215,1225,1323,1575,1701,1715,1875]

Improvements:

Now factorisation of large integers and Gaussian integers produces
factors as lazy as possible (#72, #76).

0.6.0.1:
Switch to smallcheck 1.1.3.

0.6.0.0:
This release supports GHC 7.8, 7.10, 8.0 and 8.2.

Breaking changes:

'Math.NumberTheory.Moduli' was split into
'Math.NumberTheory.Moduli.{Chinese,Class,Jacobi,Sqrt}'.

Functions 'jacobi' and 'jacobi'' return 'JacobiSymbol'

Functions 'invertMod', 'powerMod' and 'powerModInteger' were removed,
as well as their unchecked counterparts. Use new interface to
modular computations, provided by 'Math.NumberTheory.Moduli.Class'.

New functions:

Brand new 'Math.NumberTheory.Moduli.Class' (#56), providing
flexible and type safe modular arithmetic. Due to use of GMP built-ins
it is also significantly faster.

New function 'divisorsList', which is lazier than 'divisors' and
does not require 'Ord' constraint (#64). Thus, it can be used
for 'GaussianInteger'.

Improvements:

Speed up factorisation over elliptic curve up to 15x (#65).

Polymorphic 'fibonacci' and 'lucas' functions, which previously
were restricted to 'Integer' only (#63). This is especially useful
for modular computations, e. g., 'map fibonacci [1..10] :: [Mod 7]'.

Make 'totientSum' more robust and idiomatic (#58).

0.5.0.1:
Switch to QuickCheck 2.10.

0.5.0.0:
This release supports GHC 7.8, 7.10 and 8.0. GHC 7.6 is no longer supported.

Breaking changes:

Remove deprecated interface to arithmetic functions (divisors, tau,
sigma, totient, jordan, moebius, liouville, smallOmega, bigOmega,
carmichael, expMangoldt). New interface is exposed via
Math.NumberTheory.ArithmeticFunctions (#30).

Deprecate integerPower and integerWordPower from

Math.NumberTheory.Logarithms has been moved to the separate package
integer-logarithms (#51).

Rename Math.NumberTheory.Lucas to Math.NumberTheory.Recurrencies.Linear.

New functions:

Add basic combinatorial sequences: binomial coefficients, Stirling
numbers of both kinds, Eulerian numbers of both kinds, Bernoulli
numbers (#39). E. g.,

> take 10 \$ Math.NumberTheory.Recurrencies.Bilinear.bernoulli
[1 % 1,(-1) % 2,1 % 6,0 % 1,(-1) % 30,0 % 1,1 % 42,0 % 1,(-1) % 30,0 % 1]

Add the Riemann zeta function on non-negative integer arguments (#44).
E. g.,

> take 5 \$ Math.NumberTheory.Zeta.zetas 1e-15
[-0.5,Infinity,1.6449340668482262,1.2020569031595945,1.0823232337111381]

Improvements:

Speed up isPrime twice; rework millerRabinV and isStrongFermatPP (#22, #25).

0.4.3.0:
This release supports GHC 7.6, 7.8, 7.10 and 8.0.

for arithmetic functions: divisors, tau, sigma, totient, jordan,
moebius, liouville, smallOmega, bigOmega, carmichael, expMangoldt (#30).
Old implementations (exposed via Math.NumberTheory.Primes.Factorisation
and Math.NumberTheory.Powers.Integer) are deprecated and will be removed
in the next major release.

Add Karatsuba sqrt algorithm, improving performance on large integers (#6).

Fix incorrect indexing of FactorSieve (#35).

0.4.2.0:
This release supports GHC 7.6, 7.8, 7.10 and 8.0.

Add new cabal flag check-bounds, which replaces all unsafe array functions with safe ones.

Add basic functions on Gaussian integers.

Forbid non-positive moduli in Math.NumberTheory.Moduli.

Fix out-of-bounds error in Math.NumberTheory.Primes.Heap, Math.NumberTheory.Primes.Sieve and Math.NumberTheory.MoebiusInversion.
Fix 32-bit build.
Fix binaryGCD on negative numbers.
Fix highestPower (various issues).

0.4.1.0:
Add integerLog10 variants at Bas van Dijk's request and expose
0.4.0.4:
Update for GHC-7.8, the type of some primops changed, they return Int# now
Fixed bugs in modular square roots and factorisation.
0.4.0.3:
Relaxed dependencies on mtl and containers
Fixed warnings from GHC-7.5, Word(..) moved to GHC.Types
Removed SPECIALISE pragma from inline function (warning from 7.5, probably
pointless anyway)
0.4.0.2:
Sped up factor sieves. They need more space now, but the speedup is worth it, IMO.
Raised spec-constr limit in MoebiusInversion.Int
0.4.0.1:
0.4.0.0:
Added generalised Möbius inversion, to be continued
0.3.0.0:
Added modular square roots and Chinese remainder theorem
0.2.0.6:
Performance tweaks for powerModInteger (~10%) and
invertMod (~25%).
0.2.0.5:
Fix bug in psieveFrom
0.2.0.4:
Fix bug in nthPrime
0.2.0.3:
Fix bug in powerMod
0.2.0.2:
Relax bounds on array dependency for 7.4.*
0.2.0.1:
Fix copy-pasto (only relevant for 7.3.*)
Fix imports for ghc >= 7.3
0.2.0.0: