forked from Bodigrim/arithmoi
/
Changes
310 lines (211 loc) · 10.5 KB
/
Changes
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
0.9.0.0
This release supports GHC 8.0, 8.2, 8.4 and 8.6.
Breaking changes:
Remove 'Prime' type family and 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
'sbcFunctionOnPrimePower' now accepts 'Prime Word' instead of 'Word'.
'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)].
Remove deprecated 'Math.NumberTheory.GCD' and 'Math.NumberTheory.GCD.LowLevel'.
Deprecate 'Math.NumberTheory.Recurrencies.*'.
Use 'Math.NumberTheory.Recurrences.*' instead (#146).
New features:
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]
Support Gaussian and Eisenstein integers in smooth numbers (#138).
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).
Improvements:
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).
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