arithmoi
Efficient basic number-theoretic functions.
https://github.com/Bodigrim/arithmoi
LTS Haskell 22.33: | 0.13.0.0@rev:4 |
Stackage Nightly 2024-09-07: | 0.13.0.0@rev:4 |
Latest on Hackage: | 0.13.0.0@rev:4 |
arithmoi-0.13.0.0@sha256:58e8fb7ebcaf63e0207fbdd0b4317b36d9bc2dcf3f01e312079d68b6865bb5b6,7818
Module documentation for 0.13.0.0
- Math
- Math.NumberTheory
- Math.NumberTheory.ArithmeticFunctions
- Math.NumberTheory.Curves
- Math.NumberTheory.Curves.Montgomery
- Math.NumberTheory.Diophantine
- Math.NumberTheory.DirichletCharacters
- Math.NumberTheory.Euclidean
- Math.NumberTheory.Moduli
- Math.NumberTheory.MoebiusInversion
- Math.NumberTheory.Prefactored
- Math.NumberTheory.Primes
- Math.NumberTheory.Quadratic
- Math.NumberTheory.Recurrences
- Math.NumberTheory.SmoothNumbers
- Math.NumberTheory.Zeta
- Math.NumberTheory
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
Changelog
0.13.0.0
Changed
- Migrate functions under
Math.NumberTheory.Recurrences
andMath.NumberTheory.Zeta
, which operate on infinite lists, to useInfinite
frominfinite-list
package. - Migrate functions under
Math.NumberTheory.Quadratic
to return anInfinite
list of quadratic primes.
Removed
- Remove deprecated
Math.NumberTheory.Powers.Modular
.
0.12.1.0
Fixed
- Fix a grave bug in prime factorisation, lurking since
arithmoi-0.7.0.0
.
0.12.0.2
Fixed
- Compatibility patches for GHC 9.4.
0.12.0.1
Fixed
- Compatibility patches for GHC 9.2.
0.12.0.0
Added
- Define cubic symbol (#194).
- Add
instance Unbox (Prime a)
andtoPrimeIntegral
helper (#201). - Implement Cornacchia’s algorithm for Diophantine equations (#195).
- Define a wrapper
PrimeIntSet
for sets of primes (#205).
Deprecated
- Deprecate
Math.NumberTheory.Powers.Modular
, useData.Mod
orData.Mod.Word
instead.
Removed
- Remove modules and functions, deprecated in the previous release.
0.11.0.1
Changed
- Switch to
smallcheck-1.2.0
.
0.11.0.0
Added
-
Brand new machinery to deal with Dirichlet characters (#180).
-
Generate preimages of the Jordan and the sum-of-powers-of-divisors functions (#148).
-
More flexible interface for Pascal triangle: in addition to
binomial
we now provide alsobinomialRotated
,binomialLine
andbinomialDiagonal
(#151). There are alsofactoriseFactorial
andfactoriseBinomial
(#152). -
Add
Semiring
instance ofSomeMod
(#174). -
Generate divisors in range (#183).
Changed
-
Speed up
partition
, using better container for memoization (#176). -
Speed up
integerRoot
, using better starting approximation (#177).
Deprecated
-
Deprecate
Math.NumberTheory.Euclidean
, useData.Euclidean
instead. -
Deprecate
chineseRemainder
,chineseRemainder2
,chineseCoprime
, usechinese
instead. DeprecatechineseCoprimeSomeMod
, usechineseSomeMod
. -
Deprecate
Math.NumberTheory.Powers
exceptMath.NumberTheory.Powers.Modular
. UseMath.NumberTheory.Roots
instead. -
Deprecate
Math.NumberTheory.Moduli.Jacobi
, useMath.NumberTheory.Moduli.Sqrt
instead. -
Deprecate
Math.NumberTheory.Moduli.{DiscreteLogarithm,PrimitiveRoot}
, useMath.NumberTheory.Moduli.Multiplicative
instead.
Removed
- Remove modules and functions, deprecated in the previous release.
Fixed
- Fix subtraction of
SomeMod
(#174).
0.10.0.0
Added
-
The machinery of cyclic groups, primitive roots and discrete logarithms has been completely overhauled and rewritten using singleton types (#169).
There is also a new singleton type, linking a type-level modulo with a term-level factorisation. It allows both to have a nicely-typed API of
Mod m
and avoid repeating factorisations (#169).Refer to a brand new module
Math.NumberTheory.Moduli.Singleton
for details. -
Add a new function
factorBack
. -
Add
Ord SomeMod
instance (#165). -
Add
Semiring
andRing
instances for Eisenstein and Gaussian integers.
Changed
-
Embrace the new
Semiring -> GcdDomain -> Euclidean
hierarchy of classes, refiningNum
andIntegral
constraints. -
Reshuffle exports from
Math.NumberTheory.Zeta
, do not advertise its submodules as available to import. -
Add a proxy argument storing vector’s flavor to
Math.NumberTheory.MoebiusInversion.{generalInversion,totientSum}
. -
solveQuadratic
andsqrtsMod
require an additional argument: a singleton linking a type-level modulo with a term-level factorisation (#169). -
Generalize
sieveBlock
to handle any flavor ofVector
(#164).
Deprecated
-
Deprecate
Math.NumberTheory.Primes.Factorisation
, useMath.NumberTheory.Primes.factorise
instead. DeprecateMath.NumberTheory.Primes.Sieve
, useEnum
instance instead. -
Deprecate
Math.NumberTheory.Primes.Factorisation.Certified
andMath.NumberTheory.Primes.Testing.Certificates
. -
Deprecate
Math.NumberTheory.MoebiusInversion.Int
. -
Deprecate
Math.NumberTheory.SmoothNumbers.{fromSet,fromSmoothUpperBound}
. UseMath.NumberTheory.SmoothNumbers.fromList
instead. -
Deprecate
Math.NumberTheory.SmoothNumbers.smoothOverInRange
in favor ofsmoothOver
andMath.NumberTheory.SmoothNumbers.smoothOverInRange
in favor ofisSmooth
.
Removed
-
Move
Euclidean
type class tosemirings
package (#168). -
Remove deprecated earlier
Math.NumberTheory.Recurrencies.*
andMath.NumberTheory.UniqueFactorisation
modules. UseMath.NumberTheory.Recurrences.*
andMath.NumberTheory.Primes
instead. -
Remove deprecated earlier an old interface of
Math.NumberTheory.Moduli.Sqrt
.
0.9.0.0
Added
-
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
-
New functions
nextPrime
andprecPrime
. Implement an instance ofEnum
for primes (#153):> [nextPrime 101 .. precPrime 130] [Prime 101,Prime 103,Prime 107,Prime 109,Prime 113,Prime 127]
-
Add the Hurwitz zeta function on non-negative integer arguments (#126).
-
Implement efficient tests of n-freeness: pointwise and in interval. See
isNFree
andnFreesBlock
(#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).
Changed
-
Support Gaussian and Eisenstein integers in smooth numbers (#138).
-
Change types of
primes
,primeList
,sieveFrom
,nthPrime
, etc., to usePrime
newtype. -
Math.NumberTheory.Primes.{Factorisation,Testing,Counting,Sieve}
are no longer re-exported fromMath.NumberTheory.Primes
. MergeMath.NumberTheory.UniqueFactorisation
intoMath.NumberTheory.Primes
(#135, #153). -
From now on
Math.NumberTheory.Primes.Factorisation.factorise
and similar functions return[(Integer, Word)]
instead of[(Integer, Int)]
. -
sbcFunctionOnPrimePower
now acceptsPrime Word
instead ofWord
. -
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).
Deprecated
- Deprecate
Math.NumberTheory.Recurrencies.*
. UseMath.NumberTheory.Recurrences.*
instead (#146).
Removed
-
Remove
Prime
type family. -
Remove deprecated
Math.NumberTheory.GCD
andMath.NumberTheory.GCD.LowLevel
.
0.8.0.0
Added
-
A new interface for
Math.NumberTheory.Moduli.Sqrt
, more robust and type safe (#87, #108). -
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).
Changed
-
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)]
. -
Move
splitIntoCoprimes
toMath.NumberTheory.Euclidean.Coprimes
. -
Change types of
splitIntoCoprimes
,fromFactors
andprefFactors
using newtypeCoprimes
(#89). -
Sort Gaussian primes by norm (#124).
-
Make return type of
primes
andprimeList
polymorphic instead of being limited toInteger
only (#109). -
Speed up factorisation of Gaussian integers (#116).
-
Speed up computation of primitive roots for prime powers (#127).
Deprecated
-
Deprecate an old interface of
Math.NumberTheory.Moduli.Sqrt
. -
Deprecate
Math.NumberTheory.GCD
andMath.NumberTheory.GCD.LowLevel
(#80). UseMath.NumberTheory.Euclidean
instead (#128). -
Deprecate
jacobi'
(#103). -
Deprecate
Math.NumberTheory.GaussianIntegers
in favor ofMath.NumberTheory.Quadratic.GaussianIntegers
.
0.7.0.0
Added
-
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]
Changed
-
Now
moebius
returns not a number, but a value ofMoebius
type (#90). -
Now factorisation of large integers and Gaussian integers produces factors as lazy as possible (#72, #76).
Deprecated
-
Deprecate
Math.NumberTheory.Primes.Heap
. UseMath.NumberTheory.Primes.Sieve
instead. -
Deprecate
FactorSieve
,TotientSieve
,CarmichaelSieve
and accompanying functions. Use new general approach for bulk evaluation of arithmetic functions instead (#77).
Removed
- Remove
Math.NumberTheory.Powers.Integer
, deprecated in 0.5.0.0.
0.6.0.1
Changed
- Switch to
smallcheck-1.1.3
.
0.6.0.0
Added
-
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 thandivisors
and does not requireOrd
constraint (#64). Thus, it can be used forGaussianInteger
.
Changed
-
Math.NumberTheory.Moduli
was split intoMath.NumberTheory.Moduli.{Chinese,Class,Jacobi,Sqrt}
. -
Functions
jacobi
andjacobi'
returnJacobiSymbol
instead ofInt
. -
Speed up factorisation over elliptic curve up to 15x (#65).
-
Polymorphic
fibonacci
andlucas
functions, which previously were restricted toInteger
only (#63). This is especially useful for modular computations, e. g.,map fibonacci [1..10] :: [Mod 7]
. -
Make
totientSum
more robust and idiomatic (#58).
Removed
- Functions
invertMod
,powerMod
andpowerModInteger
were removed, as well as their unchecked counterparts. Use new interface to modular computations, provided byMath.NumberTheory.Moduli.Class
.
0.5.0.1
Changed
Switch to QuickCheck-2.10
.
0.5.0.0
Added
-
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]
Changed
-
Rename
Math.NumberTheory.Lucas
toMath.NumberTheory.Recurrencies.Linear
. -
Speed up
isPrime
twice; reworkmillerRabinV
andisStrongFermatPP
(#22, #25).
Deprecated
- Deprecate
integerPower
andintegerWordPower
fromMath.NumberTheory.Powers.Integer
. Use(^)
instead (#51).
Removed
-
Remove deprecated interface to arithmetic functions (
divisors
,tau
,sigma
,totient
,jordan
,moebius
,liouville
,smallOmega
,bigOmega
,carmichael
,expMangoldt
). New interface is exposed viaMath.NumberTheory.ArithmeticFunctions
(#30). -
Math.NumberTheory.Logarithms
has been moved to the separate packageinteger-logarithms
(#51).
0.4.3.0
Added
-
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 viaMath.NumberTheory.Primes.Factorisation
andMath.NumberTheory.Powers.Integer
) are deprecated and will be removed in the next major release. -
Add Karatsuba sqrt algorithm, improving performance on large integers (#6).
Fixed
- Fix incorrect indexing of
FactorSieve
(#35).
0.4.2.0
Added
-
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.
Changed
- Forbid non-positive moduli in
Math.NumberTheory.Moduli
.
Fixed
-
Fix out-of-bounds errors in
Math.NumberTheory.Primes.Heap
,Math.NumberTheory.Primes.Sieve
andMath.NumberTheory.MoebiusInversion
. -
Fix 32-bit build.
-
Fix
binaryGCD
on negative numbers. -
Fix
highestPower
(various issues).
0.4.1.0
Added
- Add
integerLog10
variants at Bas van Dijk’s request and exposeMath.NumberTheory.Powers.Integer
, with an addedintegerWordPower
.
0.4.0.4
Fixed
-
Update for GHC 7.8, the type of some primops changed, they return
Int#
now instead ofBool
. -
Fixed bugs in modular square roots and factorisation.
0.4.0.3
Changed
- Relaxed dependencies on mtl and containers.
Fixed
-
Fixed warnings from GHC 7.5,
Word(..)
moved toGHC.Types
. -
Removed
SPECIALISE
pragma from inline function (warning from GHC 7.5, probably pointless anyway).
0.4.0.2
Changed
-
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
- Fixed Haddock bug.
0.4.0.0
Added
- Added generalised Möbius inversion, to be continued.
0.3.0.0
Added
- Added modular square roots and Chinese remainder theorem.
0.2.0.6
Changed
- Performance tweaks for
powerModInteger
(~10%) andinvertMod
(~25%).
0.2.0.5
Fixed
- Fix bug in
psieveFrom
.
0.2.0.4
Fixed
- Fix bug in
nthPrime
.
0.2.0.3
Fixed
- Fix bug in
powerMod
.
0.2.0.2
Changed
- Relax bounds on
array
dependency for GHC 7.4.
0.2.0.1
Fixed
-
Fix copy-pasto (only relevant for GHC 7.3).
-
Fix imports for GHC 7.3.
0.2.0.0
Added
- Added certificates and certified testing/factorisation
0.1.0.2
Fixed
- Fixed doc bugs
0.1.0.1
Changed
- Elaborate on overflow, work more on native
Ints
in Eratosthenes.
0.1.0.0
Added
- First release.