forked from danaj/Math-Prime-Util
-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathChanges
2173 lines (1442 loc) · 82.3 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
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
Revision history for Perl module Math::Prime::Util
0.74 ?
[API Changes]
- is_pseudoprime, is_euler_pseudoprime, and is_strong_pseudoprime will
use an implicit base of 2 rather than a missing base error. This also
means is_pseudoprime($n, @bases) works properly.
- is_strong_pseudoprime passes for bases equal to 0 mod n. This matches
what the GMP code always did, and means primes return 1 for any base.
- divisor_sum(0) returns 0. divisors(0) returns an empty list.
- divisors takes an optional second argument to prune the returned list.
- consecutive_integer_lcm(0) was returning 0. Now returns 1, matching
the original GMP API as well as the OEIS series.
[ADDED]
- powersum(n,k) sum of k-th powers of positive ints <= n
- sumpowerful(n[,k]) sum of k-powerful numbers <= n
- sumliouville(n) L(n), sum of liouville(1..n)
- sumtotient(n) sum of euler_phi(1..n)
- prime_bigomega(n) # of factors (with multiplicity)
- prime_omega(n) # of factors (distinct)
- powint(a, b) signed integer a^b
- mulint(a, b) signed integer a*b
- addint(a, b) signed integer a+b
- subint(a, b) signed integer a-b
- add1int(n) signed integer n+1
- sub1int(n) signed integer n-1
- divint(a, b) signed integer a/b (floor)
- modint(a, b) signed integer a%b (floor)
- cdivint(a, b) signed integer a/b (ceiling)
- divrem(a, b) Euclidean quotient and remainder
- fdivrem(a, b) Floored quotient and remainder
- cdivrem(a, b) Ceiling quotient and remainder
- tdivrem(a, b) Truncated quotient and remainder
- lshiftint(n, k) left shift n by k bits
- rshiftint(n, k) right shift n by k bits (truncating)
- rashiftint(n, k) right shift n by k bits (flooring)
- absint(n) integer absolute value
- negint(n) integer negation
- cmpint(a, b) integer comparison (like <=>)
- signint(a, b) integer sign (-1,0,1)
- random_safe_prime for n-bit safe primes
- is_gaussian_prime(a,b) is a+bi a Gaussian prime
- is_lucky(n) predicate for lucky number sieve
- is_smooth(n,k) is n a k-smooth number
- is_rough(n,k) is n a k-rough number
- is_practical(n) is n a practical number
- is_delicate_prime(n[,b]) is n a digitally delicate prime (base b)
- is_sum_of_squares(n[,k]) can n be a sum of k squares (dflt k=2)
- is_congruent_number(n) is n a "congruent number"
- is_perfect_number(n) is n equal to sum of its proper divisors
- is_omega_prime(k,n) is n divisible by exactly k primes
- is_almost_prime(k,n) does n have exactly k prime factors
- is_chen_prime(n) is n prime and n+2 prime or semiprime
- is_powerfree(n[,k]) is n a k-powerfree number (default k=2)
- is_powerful(n[,k]) is n a k-powerful number (default k=2)
- is_perfect_power(n) is n a perfect power (1,4,8,9,16,25,..)
- is_odd(n) is n an odd integer (not divisible by 2)
- is_even(n) is n an even integer (divisible by 2)
- is_divisible(n,d) is n exactly divisible by d
- is_congruent(n,c,d) is n congruent to c mod d
- is_qr(a,n) is a a quadratic non-residue mod n
- forsquarefreeint {} lo,hi loop over square-free integers
- almost_primes(k,[start,]end) array ref of k-almost-primes
- almost_prime_count(k,n) count of integers with exactly k factors
- almost_prime_count_approx(k,n) fast approximate k-almost-prime count
- almost_prime_count_lower(k,n) fast k-almost-prime count lower bound
- almost_prime_count_upper(k,n) fast k-almost-prime count upper bound
- nth_almost_prime(k,n) The nth number with exactly k factors
- nth_almost_prime_approx(k,n) fast approximate nth k-almost-prime
- nth_almost_prime_lower(k,n) fast nth k-almost-prime lower bound
- nth_almost_prime_upper(k,n) fast nth k-almost-prime upper bound
- foralmostprimes {} k,a,b loop over k-almost-primes
- omega_primes(k,[start,]end) array ref of k-omega-primes
- omega_prime_count(k,n) count nums divisible by exactly k primes
- nth_omega_prime(k,n) The nth number dvsbl by exactly k primes
- powerful_numbers([lo,]hi[,k]) array ref of k-powerful from lo to hi
- powerful_count(n[,k]) count of k-powerful numbers <= n
- nth_powerful(n[,k]) the nth k-powerful number (default k=2)
- powerfree_count(n[,k]) count of k-powerfree numbers <= n
- nth_powerfree(n[,k]) The nth k-powerfree number (default k=2)
- powerfree_sum(n[,k]) sum of k-powerfree numbers <= n
- powerfree_part(n[,k]) remove excess powers from n
- powerfree_part_sum(n[,k]) sum of k-powerfree parts for 1 to n
- squarefree_kernel(n) integer radical of |n|
- perfect_power_count([lo,] hi) count of perfect powers
- smooth_count(n,k) count of k-smooth numbers <= n
- rough_count(n,k) count of k-rough numbers <= n
- allsqrtmod(a,n) all square roots of a (mod n)
- qnr(n) least quadratic non-residue
- subfactorial(n) count of derangements of n objects
- fubini(n) Fubini (Ordered Bell) number
= falling_factorial(x,n) falling factorial
= rising_factorial(x,n) rising factorial
- binomialmod(n,k,m) fast binomial(n,k) mod m
- negmod(a, n) -a mod n
- submod(a, b, n) a - b mod n
- muladdmod(a, b, c, n) a * b + c mod n
- mulsubmod(a, b, c, n) a * b - c mod n
- rootmod(a, k, n) modular k-th root
- allrootmod(a,k,n) all k-th roots of a (mod n)
- cornacchia(d,n) find x,y for x^2 + d * y^2 = n
- vecequal(\@a, \@b) compare two arrays for equality
- tozeckendorf(n) Zeckendorf binary string from n
- fromzeckendorf(str) n from Zeckendorf binary string
- lucasu(p,q,k) U(p,q)_k
- lucasv(p,q,k) V(p,q)_k
- lucasuv(p,q,k) U(p,q)_k, V(p,q)_k
- lucasumod(p,q,k,n) U(p,q)_k mod n
- lucasvmod(p,q,k,n) V(p,q)_k mod n
- lucasuvmod(p,q,k,n) (U(p,q)_k mod n, V(p,q)_k mod n)
- pisano_period(n) period of modular Fibonacci sequence
- prime_powers([start,] end) array ref of prime powers
- next_prime_power(n) next prime power: p > n
- prev_prime_power(n) previous prime power: p < n
- prime_power_count([start,] end) count of prime powers
- prime_power_count_approx(n) fast approximate prime power count
- prime_power_count_lower(n) fast prime power count lower bound
- prime_power_count_upper(n) fast prime power count upper bound
- nth_prime_power(n) the nth prime power
- nth_prime_power_approx(n) fast approximate nth prime power
- nth_prime_power_lower(n) fast nth prime power lower bound
- nth_prime_power_upper(n) fast nth prime power upper bound
- next_perfect_power(n) next perfect power: p > n
- prev_perfect_power(n) previous perfect power: p < n
- perfect_power_count([beg,] end) count of perfect powers
- perfect_power_count_approx(n) fast approximate perfect power count
- perfect_power_count_lower(n) fast perfect power count lower bound
- perfect_power_count_upper(n) fast perfect power count upper bound
- nth_perfect_power(n) the nth perfect power
- nth_perfect_power_approx(n) fast approximate nth perfect power
- nth_perfect_power_lower(n) fast nth perfect power lower bound
- nth_perfect_power_upper(n) fast nth perfect power upper bound
- next_chen_prime(n) next Chen prime: p > n
- lucky_numbers([start],] end) array ref of lucky numbers
- lucky_count([start,] end) count of lucky numbers
- lucky_count_approx(n) fast approximate lucky count
- lucky_count_lower(n) fast lucky count lower bound
- lucky_count_upper(n) fast lucky count upper bound
- nth_lucky(n) the nth lucky number
- nth_lucky_approx(n) fast approximate nth lucky number
- nth_lucky_lower(n) fast nth lucky number lower bound
- nth_lucky_upper(n) fast nth lucky number upper bound
- chinese2([a1,m1],[a2,m2],...) CRT returning (solution,modulus)
- frobenius_number(...) Frobenius number of a set
- vecmex(...) least non-negative value not in list
- vecpmex(...) least positive value not in list
- vecuniq(...) remove duplicates from list of integers
- vecsort(@L) numerically sort integer list
- vecsortr(\@L) numerically sort integer list ref
- vecsortrr(\@L) as vecsortr but returns a list ref
- toset(\@A) convert to unique sorted integer list
- setinsert(\@A,$v) insert integer v into integer set A
- setinsert(\@A,\@B) insert list B into integer set A
- setremove(\@A,$v) remove integer v from integer set A
- setremove(\@A,\@B) remove list B values from integer set A
- setinvert(\@A,$v) if v is in set A, remove, otherwise add
- setinvert(\@A,\@B) invert for all values in integer list B
- setcontains(\@A,$v) is integer v in integer set A
- setcontains(\@A,\@B) is integer set B a subset of int set A
- setbinop {...} \@A[,\@B] apply op to cross product of set(s)
- sumset(\@A[,\@B]) new set from a+b {a:A,b:B}
- setunion(\@A,\@B) union of two integer lists
- setintersect(\@A,\@B) intersection of two integer lists
- setminus(\@A,\@B) difference of two integer lists
- setdelta(\@A,\@B) symmetric difference of two int lists
- is_sidon_set(\@L) is integer list L a Sidon set
- is_sumfree_set(\@L) is integer list L a sum-free set
- set_is_disjoint(\@A,\@B) is set B disjoint from set A
- set_is_equal(\@A,\@B) is set B equal to set A
- set_is_subset(\@A,\@B) is set B a subset of set A
- set_is_proper_subset(\@A,\@B) is set B a proper subset of set A
- set_is_superset(\@A,\@B) is set B a superet of set A
- set_is_proper_superset(\@A,\@B) is set B a proper superet of set A
- set_is_proper_intersection(\@A,\@B) "" a proper intersection ""
[FIXES]
- nth_ramanujan_* returns undef with input of 0.
- PP code for is_polygonal with n=0 was wrong. Fixed and refactored.
- Some large results that used GMP are properly objectified.
- When using GMP, native int results are no longer objectified.
- AKS was modding a with r, since 2012.
- is_totient(2^k) with k >= 33, found by Trizen in 2019.
- forsquarefree and forfactored were missing a destroy. From Trizen.
- todigitstring with non-standard bases and long strings. From Trizen.
- Fix v0.62 breaking extended precision long doubles on some machines.
Big difference in epsilon-level precision for LambertW, Li, Zeta.
- sieve_range documentation for depth didn't exactly match the XS code.
- is_extra_strong_lucas_pseudoprime(5) was returning 0.
- lucas_sequence wasn't right for some outlier cases. This did not
impact any primality tests or other internal code.
- gcd(-n) and lcd(-n) would return -n instead of n.
- All mod functions are more consistent. Like Pari, we use mod abs(n).
If n=0, we return undef. If n=1, we return 0.
- invmod(0,1) = 0 instead of undef. Both cases make sense, but
Pari, Mathematica, SAGE, and Math::BigInt all return 0.
- sqrtmod was not solving some cases, e.g. sqrtmod(4,8).
- chinese uses abs modulos, and values are all pre-modded.
This fixes negative inputs, e.g. chinese([-4,17],[17,-19])
- The 70-rt-bignum test was horrendously slow with bignum 0.60+.
It was bypassing the validation that sanitized the input.
- Fix logint for base > n. Github #75.
- lcm with empty list returns 1 instead of 0. Github #73.
- fix an XS stack issue with calling other routines inside forprimes
- is_pseudoprime and is_euler_pseudoprime have consistent XS, PP, and GMP
behaviour. Specifically, single digit inputs and bases a multiple of n.
- kronecker in XS with 63-bit signed a and 64-bit unsigned n fixed.
- forfactored and forsquarefree were incorrect near 64-bit boundary.
[FUNCTIONALITY AND PERFORMANCE]
- LMO prime count is 1.2-1.5x faster.
- refactor objectification. Doesn't force. Enable on Perl < 5.9.
- save a nanosecond or two in 32-bit primality testing.
- Rewrite Ramanujan prime bounds using Axler (2017). For large values
this is much improved. Big speedup for large exact nth/count.
- Approx Ramanujan prime nth and count are much more accurate.
- Internally, approx prime counts are faster, as we don't need
to compute RiemannR to extreme precision.
- Faster and tighter nth_prime_upper bounds.
- Rewritten C version of Mertens based on pseudocode from Trizen.
Over 100x faster at 2^32 and grows O(n^(2/3)) vs O(n).
- fromdigits for bigints uses subquadratic algorithm, thanks from Trizen.
It also will call GMP if possible. The large example runs 100x faster.
- ExponentialIntegral with quadmath is much more precise across the range.
- rewrote C factorialmod. 1.1-2x faster for small inputs, 3-4x for large.
The PP non-GMP version also has optimizations added.
- sum_primes faster for some inputs.
- Rewrote legendre_phi and removed code duplication. Much faster.
Also makes _legendre_pi(n) about 4x faster.
- Rewrote prime count caching and removed code duplication.
Uses less memory at large sizes and is faster.
- Error message "must be a positive integer" changed to
"must be a non-negative integer" when zero is allowed.
- More accurate semiprime_count_approx and nth_semiprime_approx.
- Switched from Kahan to Neumaier sum in some real computations.
- is_primitive_root faster. Much faster for p^k and 2p^k with k >= 2.
- znprimroot faster. 2-20x faster for p^k and 2p^k with k >= 2.
- native integer input parsing is a little faster. A big deal for fast
functions and long lists.
[OTHER]
- Legendre, Meissel, and Lehmer prime counting got rewritten to use our
common code. 3x less code. No longer buildable standalone. Included
by default, though still not called internally.
- lucas_sequence(n,p,q,k) deprecated. Use lucasuvmod(p,q,k,n) instead.
- Documentation more consistent with 'positive' vs 'non-negative'.
- valuation(n,k) now will error if k < 2. This follows Pari and SAGE.
undef is returned for n = 0. Arguable "Inf" would be preferable.
0.73 2018-11-15
[ADDED]
- inverse_totient(n) the image of euler_phi(n)
[FIXES]
- Try to work around 32-bit platforms in semiprime approximations.
Cannot reproduce on any of my 32-bit test platforms.
- Fix RT 127605, memory use in for... iterators.
0.72 2018-11-08
[ADDED]
- nth_semiprime(n) the nth semiprime
- nth_semiprime_approx(n) fast approximate nth semiprime
- semiprime_count_approx(n) fast approximate semiprime count
- semi_primes as primes but for semiprimes
- forsetproduct {...} \@a,\@b,... Cartesian product of list refs
[FIXES]
- Some platforms are extremely slow for is_pillai. Speed up tests.
- Ensure random_factored_integer factor list is sorted min->max.
- forcomposites didn't check lastfor on every callback.
- Sun's compilers, in a valid interpretation of the code, generated
divide by zero code for pillai testing.
[FUNCTIONALITY AND PERFORMANCE]
- chebyshev_theta and chebyshev_psi redone and uses a table.
Large inputs are significantly faster.
- Convert some FP functions to use quadmath if possible. Without
quadmath there should be no change. With quadmath functions like
LogarithmicIntegral and LambertW will be slower but more accurate.
- semiprime_count for non-trivial inputs uses a segmented sieve and
precalculates primes for larger values so can run 2-3x faster.
- forsemiprimes uses a sieve so large ranges are much faster.
- ranged moebius more efficient for small intervals.
- Thanks to GRAY for his module Set::Product which has clean and
clever XS code, which I used to improve my code.
- forfactored uses multicall. Up to 2x faster.
- forperm, forcomb, forderange uses multicall. 2-3x faster.
- Frobenius-Khashin algorithm changed from 2013 version to 2016/2018.
0.71 2018-08-28
[ADDED]
- forfactored { ... } a,b loop n=a..b setting $_=n, @_=factor(n)
- forsquarefree { ... } a,b as forfactored, but only square-free n
- forsemiprimes { ... } a,b as forcomposites, but only semiprimes
- random_factored_integer(n) random [1..n] w/ array ref of factors
- semiprime_count([lo],hi) counts semiprimes in range
[FIXES]
- Monolithic sieves beyond 30*2^32 (~ 1.2 * 10^11) overflowed.
- is_semiprime was wrong for five small values since 0.69. Fixed.
[FUNCTIONALITY AND PERFORMANCE]
- is_primitive_root much faster (doesn't need to calulate totient,
and faster rejection when n has no primitive root).
- znprimroot and znorder use Montgomery, 1.2x to 2x faster.
- slightly faster sieve_range for native size inputs (use factor_one).
- bin/primes.pl faster for palindromic primes and works for 10^17
[OTHER]
- Added ability to use -DBENCH_SEG for benchmarking sieves using
prime_count and ntheory::_segment_pi without table optimizations.
- Reorg of main factor loop. Should be identical from external view.
- Internal change to is_semiprime and is_catalan_pseudoprime.
0.70 2017-12-02
[FIXES]
- prime_count(a,b) incorrect for a={3..7} and b < 66000000.
First appeared in v0.65 (May 2017).
Reported by Trizen. Fixed.
- Also impacted were nth_ramanujan_prime and _lower/_upper for
small input values.
[FUNCTIONALITY AND PERFORMANCE]
- Some utility functions used prime counts. Unlink for more isolation.
- prime_count_approx uses full precision for bigint or string input.
- LogarithmicIntegral and ExponentialIntegral will try to use
our GMP backend if possible.
- Work around old Math::BigInt::FastCalc (as_int() doesn't work right).
- prime_memfree also calls GMP's memfree function. This will clear the
cached constants (e.g. Pi, Euler).
- Calling srand or csrand will also result in the GMP backend CSPRNG
functions being called. This gives more consistent behavior.
[OTHER]
- Turned off threads testing unless release or extended testing is used.
A few smokers seem to have threads lib that die before we event start.
- Removed all Math::MPFR code and references. The latest GMP backend
has everything we need.
- The MPU_NO_XS and MPU_NO_GMP environment variables are documented.
0.69 2017-11-08
[ADDED]
- is_totient(n) true if euler_phi(x) == n for some x
[FUNCTIONALITY AND PERFORMANCE]
- is_square_free uses abs(n), like Pari and moebius.
- is_primitive_root could be wrong with even n on some platforms.
- euler_phi and moebius with negative range inputs weren't consistent.
- factorialmod given a large n and m where m was a composite with
large square factors was incorrect. Fixed.
- numtoperm will accept negative k values (k is always mod n!)
- Split XS mapping of many primality tests. Makes more sense and
improves performance for some calls.
- Split final test in PP cluster sieve.
- Support some new Math::Prime::Util::GMP functions from 0.47.
- C spigot Pi is 30-60% faster on x86_64 by using 32-bit types.
- Reworked some factoring code.
- Remove ISAAC (Perl and C) since we use ChaCha.
- Each thread allocs a new const array again instead of sharing.
0.68 2017-10-19
[API Changes]
- forcomb with one argument iterates over the power set, so k=0..n
instead of k=n. The previous behavior was undocumented. The new
behavior matches Pari/GP (forsubset) and Perl6 (combinations).
[ADDED]
- factorialmod(n,m) n! mod m calculated efficiently
- is_fundamental(d) true if d a fundamental discriminant
[FUNCTIONALITY AND PERFORMANCE]
- Unknown bigint classes no longer return two values after objectify.
Thanks to Daniel Șuteu for finding this.
- Using lastfor inside a formultiperm works correctly now.
- randperm a little faster for k < n cases, and can handle big n
values without running out of memory as long as k << n.
E.g. 5000 random native ints without dups: @r = randperm(~0,5000);
- forpart with primes pulls min/max values in for a small speedup.
- forderange 10-20% faster.
- hammingweight for bigints 3-8x faster.
- Add Math::GMPq and Math::AnyNum as possible bigint classes. Inputs
of these types will be relied on to stringify correctly, and if this
results in an integer string, to intify correctly. This should give
a large speedup for these types.
- Factoring native integers is 1.2x - 2x faster. This is due to a
number of changes.
- Add Lehman factoring core. Since this is not exported or used by
default, the API for factor_lehman may change.
- All new Montgomery math. Uses mulredc asm from Ben Buhrow.
Faster and smaller. Most primality and factoring code 10% faster.
- Speedup for factoring by running more Pollard-Rho-Brent, revising
SQUFOF, updating HOLF, updating recipe.
0.67 2017-09-23
[ADDED]
- lastfor stops forprimes (etc.) iterations
- is_square(n) returns 1 if n is a perfect square
- is_polygonal(n,k) returns 1 if n is a k-gonal number
[FUNCTIONALITY AND PERFORMANCE]
- shuffle prototype is @ instead of ;@, so matches List::Util.
- On Perl 5.8 and earlier we will call PP instead of trying
direct-to-GMP. Works around a bug in XS trying to turn the
result into an object where 5.8.7 and earlier gets lost.
- We create more const integers, which speeds up common uses of
permutations.
- CSPRNG now stores context per-thread rather than using a single
mutex-protected context. This speeds up anything using random
numbers a fair amount, especially with threaded Perls.
- With the above two optimizations, randperm(144) is 2.5x faster.
- threading test has threaded srand/irand test added back in, showing
context is per-thread. Each thread gets its own sequence and calls
to srand/csrand and using randomness doesn't impact other threads.
0.66 2017-09-12
[ADDED]
- random_semiprime random n-bit semiprime (even split)
- random_unrestricted_semiprime random n-bit semiprime
- forderange { ... } n derangements iterator
- numtoperm(n,k) returns kth permutation of n elems
- permtonum([...]) returns rank of permutation array ref
- randperm(n[,k]) random permutation of n elements
- shuffle(...) random permutation of an array
[FUNCTIONALITY AND PERFORMANCE]
- Rewrite sieve marking based on Kim Walisch's new simple mod-30 sieve.
Similar in many ways to my old code, but this is simpler and faster.
- is_pseudoprime, is_euler_pseudoprime, is_strong_pseudoprime changed to
better handle the unusual case of base >= n.
- Speedup for is_carmichael.
- is_frobenius_underwood_pseudoprime checks for jacobi == 0. Faster.
- Updated Montgomery inverse from Robert Gerbicz.
- Tighter nth prime bounds for large inputs from Axler 2017-06.
Redo Ramanujan bounds since they're based on nth prime bounds.
- chinese objectifies result (i.e. big results are bigints).
- Internal support for Baillie-Wagstaff (pg 1402) extra Lucas tests.
- More standardized Lucas parameter selection. Like other tests and the
1980 paper, checks jacobi(D) in the loop, not gcd(D).
- entropy_bytes, srand, and csrand moved to XS.
- Add -secure import to disallow all manual seeding.
0.65 2017-05-03
[API Changes]
- Config options irand and primeinc are deprecated. They will carp if set.
[FUNCTIONALITY AND PERFORMANCE]
- Add Math::BigInt::Lite to list of known bigint objects.
- sum_primes fix for certain ranges with results near 2^64.
- is_prime, next_prime, prev_prime do a lock-free check for a find-in-cache
optimization. This is a big help on on some platforms with many threads.
- C versions of LogarithmicIntegral and inverse_li rewritten.
inverse_li honors the documentation promise within FP representation.
Thanks to Kim Walisch for motivation and discussion.
- Slightly faster XS nth_prime_approx.
- PP nth_prime_approx uses inverse_li past 1e12, which should run
at a reasonable speed now.
- Adjusted crossover points for segment vs. LMO interval prime_count.
- Slightly tighter prime_count_lower, nth_prime_upper, and Ramanujan bounds.
0.64 2017-04-17
[FUNCTIONALITY AND PERFORMANCE]
- inverse_li switched to Halley instead of binary search. Faster.
- Don't call pre-0.46 GMP backend directly for miller_rabin_random.
0.63 2017-04-16
[FUNCTIONALITY AND PERFORMANCE]
- Moved miller_rabin_random to separate interface.
Make catching of negative bases more explicit.
0.62 2017-04-16
[API Changes]
- The 'irand' config option is removed, as we now use our own CSPRNG.
It can be seeded with csrand() or srand(). The latter is not exported.
- The 'primeinc' config option is deprecated and will go away soon.
[ADDED]
- irand() Returns uniform random 32-bit integer
- irand64() Returns uniform random 64-bit integer
- drand([fmax]) Returns uniform random NV (floating point)
- urandomb(n) Returns uniform random integer less than 2^n
- urandomm(n) Returns uniform random integer in [0, n-1]
- random_bytes(nbytes) Return a string of CSPRNG bytes
- csrand(data) Seed the CSPRNG
- srand([UV]) Insecure seed for the CSPRNG (not exported)
- entropy_bytes(nbytes) Returns data from our entropy source
- :rand Exports srand, rand, irand, irand64
- nth_ramanujan_prime_upper(n) Upper limit of nth Ramanujan prime
- nth_ramanujan_prime_lower(n) Lower limit of nth Ramanujan prime
- nth_ramanujan_prime_approx(n) Approximate nth Ramanujan prime
- ramanujan_prime_count_upper(n) Upper limit of Ramanujan prime count
- ramanujan_prime_count_lower(n) Lower limit of Ramanujan prime count
- ramanujan_prime_count_approx(n) Approximate Ramanujan prime count
[FUNCTIONALITY AND PERFORMANCE]
- vecsum is faster when returning a bigint from native inputs (we
construct the 128-bit string in C, then call _to_bigint).
- Add a simple Legendre prime sum using uint128_t, which means only for
modern 64-bit compilers. It allows reasonably fast prime sums for
larger inputs, e.g. 10^12 in 10 seconds. Kim Walisch's primesum is
much more sophisticated and over 100x faster.
- is_pillai about 10x faster for composites.
- Much faster Ramanujan prime count and nth prime. These also now use
vastly less memory even with large inputs.
- small speed ups for cluster sieve.
- faster PP is_semiprime.
- Add prime option to forpart restrictions for all prime / non-prime.
- is_primitive_root needs two args, as documented.
- We do random seeding ourselves now, so remove dependency.
- Random primes functions moved to XS / GMP, 3-10x faster.
0.61 2017-03-12
[ADDED]
- is_semiprime(n) Returns 1 if n has exactly 2 prime factors
- is_pillai(p) Returns 0 or v wherev v! % n == n-1 and n % v != 1
- inverse_li(n) Integer inverse of Logarithmic Integral
[FUNCTIONALITY AND PERFORMANCE]
- is_power(-1,k) now returns true for odd k.
- RiemannZeta with GMP was not subtracting 1 from results > 9.
- PP Bernoulli algorithm changed to Seidel from Brent-Harvey. 2x speedup.
Math::BigNum is 10x faster, and our GMP code is 2000x faster.
- LambertW changes in C and PP. Much better initial approximation, and
switch iteration from Halley to Fritsch. 2 to 10x faster.
- Try to use GMP LambertW for bignums if it is available.
- Use Montgomery math in more places:
= sqrtmod. 1.2-1.7x faster.
= is_primitive_root. Up to 2x faster for some inputs.
= p-1 factoring stage 1.
- Tune AKS r/s selection above 32-bit.
- primes.pl uses twin_primes function for ~3x speedup.
- native chinese can handle some cases that used to overflow. Use Shell
sort on moduli to prevent pathological-but-reasonable test case.
- chinese directly to GMP
- Switch to Bytes::Random::Secure::Tiny -- fewer dependencies.
- PP nth_prime_approx has better MSE and uses inverse_li above 10^12.
- All random prime functions will use GMP versions if possible and
if a custom irand has not been configured.
They are much faster than the PP versions at smaller bit sizes.
- is_carmichael and is_pillai small speedups.
0.60 2016-10-09
[ADDED]
- vecfirstidx { expr } @n returns first index with expr true
[FUNCTIONALITY AND PERFORMANCE]
- Expanded and modified prime count sparse tables. Prime counts from 30k
to 90M are 1.2x to 2.5x faster. It has no appreciable effect on the
speed of prime counts larger than this size.
- fromdigits works with bigint first arg, no need to stringify.
Slightly faster for bigints, but slower than desired.
- Various speedups and changes for fromdigits, todigits, todigitstring.
- vecprod in PP for negative high-bit would return double not bigint.
- Lah numbers added as Stirling numbers of the third kind. They've been
in the GMP code for almost 2 years now. Also for big results, directly
call the GMP code and objectify the result.
- Small performance change to AKS (r,s) selection tuning.
- On x86_64, use Montgomery math for Pollard/Brent Rho. This speeds up
factoring significantly for large native inputs (e.g. 10-20 digits).
- Use new GMP zeta and riemannr functions if possible, making some of
our operations much faster without Math::MPFR.
- print_primes with large args will try GMP sieve for big speedup. E.g.
use bigint; print_primes(2e19,2e19+1e7);
goes from 37 minutes to 7 seconds. This also removes a mistaken blank
line at the end for certain ranges.
- PP primes tries to use GMP. Only for calls from other PP code.
- Slightly more accuracy in native ExponentialIntegral.
- Slightly more accuracy in twin_prime_count_approx.
- nth_twin_prime_approx was incorrect over 1e10 and over 2e16 would
infinite loop due to Perl double conversion.
- nth_twin_prime_approx a little faster and more accurate.
0.59 2016-08-03
[ADDED]
- is_euler_plumb_pseudoprime Plumb's Euler Criterion test.
- is_prime_power Returns k if n=p^k for p a prime.
- logint(n,b) Integer logarithm. Largest e s.t. b^e <= n.
- rootint(n,k) Integer k-th root.
- ramanujan_sum(k,n) Ramanujan's sum
[FUNCTIONALITY AND PERFORMANCE]
- Fixes for quadmath:
+ Fix "infinity" in t/11-primes.t.
+ Fix native Pi to use quads.
+ Trim some threading tests.
- Fix fromdigits memory error with large string.
- Remove 3 threading tests that were causing issues with Perl -DDEBUGGING.
- foroddcomposites with some odd start values could index incorrectly.
- is_primitive_root(1,0) returns 0 instead of fp exception.
- mertens() uses a little less memory.
- 2x speedup for znlog with bigint values.
- is_pseudoprime() and is_euler_pseudoprime() use Montgomery math so are
much faster. They seem to be ~5% faster than Miller-Rabin now.
- is_catalan_pseudoprime 1.1x to 1.4x faster.
- is_perrin_pseudoprime over 10x faster.
Uses Adams/Shanks doubling and Montgomery math.
Single core, odd composites: ~8M range/s.
- Add restricted Perrin pseudoprimes using an optional argument.
- Add bloom filters to reject non-perfect cubes, fifths, and sevenths.
is_power about 2-3x faster for native inputs.
- forcomposites / foroddcomposites about 1.2x faster past 64-bit.
- exp_mangoldt rewritten to use is_prime_power.
- Integer root code rewritten and now exported.
- We've been hacking around the problem of older Perls autovivifying
functions at compile time. This makes functions that don't exist
return true when asked if they're defined, which causes us distress.
Store the available GMP functions before loading the PP code.
XS code knows MPU::GMP version and calls as appropriate. This works
around the auto-vivication, and lets us choose to call the GMP
function based on version instead of just existence.
E.g. GMP's is_power was added in 0.19, but didn't support negative
powers until 0.28.
0.58 2016-05-21
[API Changes]
- prev_prime($n) where $n <= 2 now returns undef instead of 0. This
may enable catching range errors, and is technically more correct.
- nth_prime(0) now returns undef instead of 0. This should help catch
cases where the base wasn't understood. The change is similar for
all the nth_* functions (e.g. nth_twin_prime).
- sumdigits(n,base) will interpret n as a number in the given base,
rather than the Pari/GP method of converting decimal n to that base
then summing. This allows sumdigits to easily sum hex strings.
The old behavior is easily done with vecsum(todigits(n, base)).
- binary() was not intended to be released (todigits and todigitstring
are supersets), but the documentation got left in. Remove docs.
[ADDED]
- addmod(a, b, n) a + b mod n
- mulmod(a, b, n) a * b mod n
- divmod(a, b, n) a / b mod n
- powmod(a, b, n) a ^ b mod n
- sqrtmod(a, n) modular square root
- is_euler_pseudoprime(n,a[...]) Euler test to given bases
- is_primitive_root(r, n) is r a primitive root mod n
- is_quasi_carmichael(n) is n a Quasi-Carmichael number
- hclassno(n) Hurwitz class number H(n) * 12
- sieve_range(n, width, depth) sieve to given depth, return offsets
[FUNCTIONALITY AND PERFORMANCE]
- Fixed incorrect table entries for 2^16th Ramanujan prime count and
nth_ramanujan_prime(23744).
- foroddcomposites with certain arguments would start with 10 instead of 9.
- lucasu and lucasv should return bigint types.
- vecsum will handle 128-bit sums internally (performance increase).
- Speedup is_carmichael.
- Speedup znprimroot, 10% for small inputs, 10x for large composites.
- Speedup znlog ~2x. It is now Rho racing an interleaved BSGS.
- Change AKS to Bernstein 2003 theorem 4.1.
5-20x faster than Bornemann, 20000+x faster than V6.
- sum_primes now uses tables for native sizes (performance increase).
- ramanujan_tau uses Cohen's hclassno method instead of the sigma
calculation. This is 3-4x faster than the GMP code for inputs > 300k,
and much faster than the older PP code.
- fromdigits much faster for large base-10 arrays. Timing is better than
split plus join when output is a bigint.
0.57 2016-01-03
[ADDED]
- formultiperm { ... } \@n loop over multiset permutations
- todigits(n[,base[,len]]) convert n to digit array
- todigitstring(n[,base[,len]]) convert n to string
- fromdigits(\@d[,base]) convert digit array ref to number
- fromdigits(str[,base]) convert string to number
- ramanujan_prime_count counts Ramanujan primes in range
- vecany { expr } @n true if any expr is true
- vecall { expr } @n true if all expr are true
- vecnone { expr } @n true if no expr are true
- vecnotall { expr } @n true if not all expr are true
- vecfirst { expr } @n returns first element with expr true
[FUNCTIONALITY AND PERFORMANCE]
- nth_ramanujan_prime(997) was wrong. Fixed.
- Tighten Ramanujan prime bounds. Big speedups for large nth Rp.
0.56 2015-12-13
[ADDED]
- is_carmichael(n) Returns 1 if n is a Carmichael number
- forcomp { ... } n[,{...}] loop over compositions
[FUNCTIONALITY AND PERFORMANCE]
- Faster, nonrecursive divisors_from_factors routine.
- gcdext(0,0) returns (0,0,0) to match GMP and Pari/GP.
- Use better prime count lower/upper bounds from Büthe 2015.
- forpart and forcomp both use lexicographic order (was anti-lexico).
0.55 2015-10-19
- Fixed test that was using a 64-bit number on 32-bit machines.
[FUNCTIONALITY AND PERFORMANCE]
- Speed up PP versions of sieve_prime_cluster, twin_primes,
twin_prime_count, nth_twin_prime, primes.
0.54 2015-10-14
[ADDED]
- sieve_prime_cluster(low,high[,...]) find prime clusters
[Misc]
- Certain small primes used to return false with Frobenius and AES Lucas
tests when given extra arguments. Both are unusual cases never used
by the main system. Fixed.
0.53 2015-09-05
[ADDED]
- ramanujan_tau(n) Ramanujan's Tau function
- sumdigits(n[,base]) sum digits of n
[FUNCTIONALITY AND PERFORMANCE]
- Don't use Math::MPFR unless underlying MPFR library is at least 3.x.
- Use new Math::Prime::Util::GMP::sigma function for divisor_sum.
- Use new Math::Prime::Util::GMP::sieve_twin_primes(a,b).