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.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 also binomialRotated, binomialLine and binomialDiagonal
(#151). There are also factoriseFactorial and factoriseBinomial (#152).
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 Semiring and Ring instances for Eisenstein and Gaussian integers.
Changed
Embrace the new Semiring -> GcdDomain -> Euclidean hierarchy
of classes, refining Num and Integral 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 and sqrtsMod require an additional argument: a singleton
linking a type-level modulo with a term-level factorisation (#169).
Generalize sieveBlock to handle any flavor of Vector (#164).
Deprecated
Deprecate Math.NumberTheory.Primes.Factorisation, use
Math.NumberTheory.Primes.factorise instead. Deprecate
Math.NumberTheory.Primes.Sieve, use Enum instance instead.
Deprecate Math.NumberTheory.Primes.Factorisation.Certified and
Math.NumberTheory.Primes.Testing.Certificates.
Deprecate Math.NumberTheory.MoebiusInversion.Int.
Deprecate Math.NumberTheory.SmoothNumbers.{fromSet,fromSmoothUpperBound}.
Use Math.NumberTheory.SmoothNumbers.fromList instead.
Deprecate Math.NumberTheory.SmoothNumbers.smoothOverInRange in favor
of smoothOver and Math.NumberTheory.SmoothNumbers.smoothOverInRange
in favor of isSmooth.
Removed
Move Euclidean type class to semirings package (#168).
Remove deprecated earlier Math.NumberTheory.Recurrencies.*
and Math.NumberTheory.UniqueFactorisation modules.
Use Math.NumberTheory.Recurrences.* and Math.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 and precPrime. Implement an instance of Enum for primes (#153):
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 use Prime newtype.
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)].
sbcFunctionOnPrimePower now accepts Prime Word instead of Word.
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.*.
Use Math.NumberTheory.Recurrences.* instead (#146).
Removed
Remove Prime type family.
Remove deprecated Math.NumberTheory.GCD and Math.NumberTheory.GCD.LowLevel.
0.8.0.0
Added
A new interface for Math.NumberTheory.Moduli.Sqrt, more robust and type safe (#87, #108).
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 to Math.NumberTheory.Euclidean.Coprimes.
Change types of splitIntoCoprimes, fromFactors and prefFactors
using newtype Coprimes (#89).
Now moebius returns not a number, but a value of Moebius type (#90).
Now factorisation of large integers and Gaussian integers produces
factors as lazy as possible (#72, #76).
Deprecated
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).
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 than divisors and
does not require Ord constraint (#64). Thus, it can be used
for GaussianInteger.
Changed
Math.NumberTheory.Moduli was split into
Math.NumberTheory.Moduli.{Chinese,Class,Jacobi,Sqrt}.
Functions jacobi and jacobi' return JacobiSymbol
instead of Int.
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].
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.
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.,
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 to Math.NumberTheory.Recurrencies.Linear.
Speed up isPrime twice; rework millerRabinV and isStrongFermatPP (#22, #25).
Deprecated
Deprecate integerPower and integerWordPower from
Math.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 via
Math.NumberTheory.ArithmeticFunctions (#30).
Math.NumberTheory.Logarithms has been moved to the separate package
integer-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 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).