# arithmoi

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

Version on this page: | 0.8.0.0 |

LTS Haskell 12.22: | 0.7.0.0 |

Stackage Nightly 2018-12-12: | 0.8.0.0 |

Latest on Hackage: | 0.8.0.0 |

MIT licensed by

**Daniel Fischer**Maintained by

**Carter Schonwald carter at wellposed dot com, Andrew Lelechenko andrew dot lelechenko at gmail dot com**#### Module documentation for 0.8.0.0

There are no documented modules for this package.

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.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).

Use 'Math.NumberTheory.Euclidean' instead (#128).

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

'Math.NumberTheory.Quadratic.GaussianIntegers'.

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'.

Use 'Math.NumberTheory.Primes.Sieve' instead.

Deprecate 'FactorSieve', 'TotientSieve', 'CarmichaelSieve' and

accompanying functions. Use new general approach for bulk evaluation

of arithmetic functions instead (#77).

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'

instead of 'Int'.

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.Powers.Integer. Use (^) instead (#51).

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.

Add Math.NumberTheory.ArithmeticFunctions with brand-new machinery

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.

Add Möbius mu-function.

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

Math.NumberTheory.Powers.Integer, with an added integerWordPower.

0.4.0.4:

Update for GHC-7.8, the type of some primops changed, they return Int# now

instead of Bool.

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:

Fixed Haddock bug

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:

Added certificates and certified testing/factorisation

0.1.0.2:

Fixed doc bugs

0.1.0.1:

Elaborate on overflow, work more on native Ints in Eratosthenes

0.1.0.0:

First release

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).

Use 'Math.NumberTheory.Euclidean' instead (#128).

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

'Math.NumberTheory.Quadratic.GaussianIntegers'.

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'.

Use 'Math.NumberTheory.Primes.Sieve' instead.

Deprecate 'FactorSieve', 'TotientSieve', 'CarmichaelSieve' and

accompanying functions. Use new general approach for bulk evaluation

of arithmetic functions instead (#77).

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'

instead of 'Int'.

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.Powers.Integer. Use (^) instead (#51).

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.

Add Math.NumberTheory.ArithmeticFunctions with brand-new machinery

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.

Add Möbius mu-function.

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

Math.NumberTheory.Powers.Integer, with an added integerWordPower.

0.4.0.4:

Update for GHC-7.8, the type of some primops changed, they return Int# now

instead of Bool.

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:

Fixed Haddock bug

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:

Added certificates and certified testing/factorisation

0.1.0.2:

Fixed doc bugs

0.1.0.1:

Elaborate on overflow, work more on native Ints in Eratosthenes

0.1.0.0:

First release

Depends on 11 packages:

Used by 13 packages:

comments powered byDisqus

A service provided by
FP Complete