Skip to content

Latest commit

 

History

History
594 lines (351 loc) · 18.1 KB

changelog.md

File metadata and controls

594 lines (351 loc) · 18.1 KB

Changelog

0.13.0.0

Changed

  • Migrate functions under Math.NumberTheory.Recurrences and Math.NumberTheory.Zeta, which operate on infinite lists, to use Infinite from infinite-list package.
  • Migrate functions under Math.NumberTheory.Quadratic to return an Infinite 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) and toPrimeIntegral 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, use Data.Mod or Data.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 also binomialRotated, binomialLine and binomialDiagonal (#151). There are also factoriseFactorial and factoriseBinomial (#152).

  • Add Semiring instance of SomeMod (#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, use Data.Euclidean instead.

  • Deprecate chineseRemainder, chineseRemainder2, chineseCoprime, use chinese instead. Deprecate chineseCoprimeSomeMod, use chineseSomeMod.

  • Deprecate Math.NumberTheory.Powers except Math.NumberTheory.Powers.Modular. Use Math.NumberTheory.Roots instead.

  • Deprecate Math.NumberTheory.Moduli.Jacobi, use Math.NumberTheory.Moduli.Sqrt instead.

  • Deprecate Math.NumberTheory.Moduli.{DiscreteLogarithm,PrimitiveRoot}, use Math.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 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):

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

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

  • 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 to Math.NumberTheory.Euclidean.Coprimes.

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

  • Sort Gaussian primes by norm (#124).

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

Deprecated

  • Deprecate an old interface of Math.NumberTheory.Moduli.Sqrt.

  • Deprecate Math.NumberTheory.GCD and Math.NumberTheory.GCD.LowLevel (#80). Use Math.NumberTheory.Euclidean instead (#128).

  • Deprecate jacobi' (#103).

  • Deprecate Math.NumberTheory.GaussianIntegers in favor of Math.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 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].

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

Removed

  • 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.,

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

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 and Math.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 expose Math.NumberTheory.Powers.Integer, with an added integerWordPower.

0.4.0.4

Fixed

  • 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

Changed

  • Relaxed dependencies on mtl and containers.

Fixed

  • Fixed warnings from GHC 7.5, Word(..) moved to GHC.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%) and invertMod (~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.