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.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 Moebius 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 Moebius 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
comments powered byDisqus