Debian Codegraph @

TODO

raw
1
2 For new functions:
3 .h, .c, XS, export, t/02, Changes, doc, test
4
5 - prime_count - needs the pc(#) option as well as pc(#,#)
6
7 - Do a GMP version of LMO prime_count. Possible versions:
8 - 32-bit main, 16-bit support
9 - 64-bit main, 32-bit support (using __uint64_t if necessary)
10 - 128-bit main, 64-bit support (gcc only)
11 - GMP main, 32-bit support (portable)
12 - GMP main, 64-bit support (mostly portable)
13
14 - nth_prime
15
16 - GMP SQUFOF could use a better implementation, though low priority since it
17 just isn't going to be the right algorithm for numbers > 2^64. Mainly what
18 it needs is to pay attention to the rounds argument. Perhaps race.
19
20 - Tune and improve SIMPQS for our uses. Check FLINT 2.3 for improvements.
21
22 - Write our own QS.
23
24 - The statics in ecm and QS won't play well with threading.
25
26 - ECPP: Perhaps more HCPs/WCPs could be loaded if needed?
27
28 - ECPP: Another idea is related to Atkin/Morain's EAS. When we have a large
29 number, we can process more Ds, delaying the downrun. We then use the
30 smallest q we found. Combine with lightened stage 1 factoring as above.
31 This drops our q sizes faster, at the expense of more up-front time.
32 I have this running, but for small numbers it doesn't matter much, and for
33 large numbers it just highlights how much nicer FAS would be.
34
35 - ECPP: All discriminants with D % 8 != 3 have been converted to Weber. We're
36 still left with lots of those D values. Figure out a different invariant
37 that will make smaller polynomials, along with a root conversion.
38
39 - ECPP: Add a fast BLS5 to downrun?
40
41 - Add BLS17 proof. Merge into BLS5 code since the end is the same.
42
43 - Add tests for proofs, similar to MPU t/23.
44
45 - Handle objects of type:
46 Math::GMP
47 Math::GMP::Fast
48 Math::GMPz
49 We should parse their mpz_t directly, do our processing, and output the
50 result as one of these types.
51
52 - Recognize Math::BigInt / Math::Pari objects. Shortcut validation.
53 Create results as new objects of their type.
54
55 - These functions should be added:
56 legendre_phi
57 znlog
58
59 - Any fast primality pretest would be nice. I've tested:
60 - Colin Plumb's Euler Criterion test
61 - Fermat base 210, which is done in GMP's internal millerrabin.c.
62 - Fermat base 2 also no faster than SPRP-2, though some claim it is.
63 mpz_t e, r; int composite;
64 mpz_init(e);
65 mpz_init_set_ui(r, 2); mpz_sub_ui(e, n, 1); mpz_powm(r, r, e, n);
66 composite = mpz_cmp_ui(r, 1) != 0;
67 mpz_clear(r); mpz_clear(e);
68 if (composite) return 0;
69 None of these are faster on average than just doing BPSW.
70
71 - merge the two frobenius tests. cp is faster, needs the deterministic
72 version, we should switch to the two input version (allow GMP), etc.
73
74 - tests for sieve_primes.
75
76 - speed up range sieving.
77
78 - fast prime printing routine. The following could be trivially 2x faster:
79 $n = 10**20; say for Math::Prime::Util::GMP::sieve_primes($n,$n+8e9,0);
80 About 3 minutes vs. 7-8 just by using gmp_printf.
81 Using sieve_range doesn't help, as the issue is the massive return array.
82
83 - Consider ranged ramanujan_tau. See:
84 https://cs.uwaterloo.ca/journals/JIS/VOL13/Lygeros/lygeros5.pdf
85 Where we could compute a number of hclassno values, then generate the
86 tau values. This might be more efficient.
87
88 - We could do LLR and Proth in prob_prime and return 1 instead of 2, leaving
89 certs possible.
90
91 - consider probabilistic is_primitive_root for large inputs
92 [2024: what does this mean?]
93
94 - Verify speed and memory use of GMP's two binomials for various versions
95 and compare. Looks like Luschny sent his changes after 5.0.0.
96 https://gmplib.org/list-archives/gmp-discuss/2010-February/004036.html
97
98 - Identify places where 32-bit GMP on 64-bit Perl will trip us up.
99
100 - BLS75 methods: check if we can return 0 instead of 1 in many cases.
101
102 - Make a trial factor routine that returns all factors. This can be done
103 with a single treesieve. ECPP could make use of this (since it is doing
104 many calls, keeping the product tree around would be useful).
105 All current calls are testing primality, so don't need multiple returns.
106 Changing the XS call to return multiple values might be useful.
107
108 - zeta below -20 or so is increasingly wrong. We should use reflection
109 formula, but that requires some new functions. The MPU interface doesn't
110 even allow negative inputs at all so it isn't critical.
111
112 - random prime should be more efficient (use A2 instead of A1).
113
114 - gamma, lngamma
115 See http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.527.8519
116 https://www.researchgate.net/publication/272039164_A_new_fast_asymptotic_series_for_the_gamma_function
117 https://arxiv.org/pdf/2301.09699.pdf
118
119 - Euler using:
120 = binary splitting
121 = B3 from Brent/McMillan (1980)
122 = FLINT's B3 (b6ebd880cea55e6e6cf99d6c454607a5872b2c96)
123
124 - Functions used in MPU that were MPFR.
125 = (++) Pi is about 2x faster than MPFR
126 = (--) li(10^17) is 2x slower than MPFR
127 = (--) ei(0.5) is much slower than MPFR (20x and worse exponent)
128 = (--) Euler is much slower than MPFR (10x and worse exponent)
129 = (--) zeta is much slower than MPFR (10x and worse exponent)
130 = harmreal, riemannr, prime_count_lower, prime_count_upper
131
132 - tinyqs needs a destroy to clear all the init vars
133
134 - clean up dependencies links. We now have to include *every* C file to
135 compile SIMPQS standalone. Completely unnecessary, but some utility
136 functions are pulling in other things.
137
138 - add sumliouville
139 almost_prime_count(k,n)
140 nth_almost_prime(k,n)
141 smooth_count
142 rough_count
143 qnr
144
145 - make the Bernoulli number cache incremental
146
147 - fromdigits input digit array arguably should be signed bigints.
148
149 - optimize prime_omega, prime_bigomega
150
151 - Rademacher partitions
152
153 - overpartitions
154 https://arxiv.org/pdf/2303.15895
155
156 - rootmod, rootmodp
157 - allsqrtmod
158 - allrootmod
159
160 - znlog is needed by rootmod
161 simple rho
162 distinguished point rho
163
164 - next_perfect_power, prev_perfect_power
165 https://github.com/trizen/sidef/commit/81af8f018cca4ab7813d4cfaa46fd2e45796a52d
166
167 - make is_carmichael deterministic test go faster
168
169 - have trial factor use treesieve static function.
170
171 - the 2021 BPSW test
172 https://arxiv.org/pdf/2006.14425
173 https://community.wolfram.com/groups/-/m/t/2344199?p_p_auth=UZ0BHnEu
174
175 - Look into FLINT's poly ramanujan tau method by Fredrik Johansson.
176
177 - Fubini
178
179 - subfactorial for large enough n should use floor((n!+1)/e). See Sidef.
180
181 - factorial_valuation. See MPU's util.c and
182 https://github.com/trizen/sidef/commit/e25e9b8429837fb32642bb77275592700f577829
183
184 - Look at Sidef's factor_upto(n,limit)
185
186 - better hclassno
187
188 - consider exporting a sieve segment or sieve from/to routine. Then our
189 trial iterator can sieve segments, vecprod them, do gcd. Maybe a
190 prime_iterator_next64 to get 64 values.
191
192 - many files cache small primes. Do it once. primes under 64k.
193
194 - faster next/prev perfect power, look for odd powers, no loop needed.
195
196 - addmod, mulmod, powmod, divmod -- work with GMP version 36 if n > 0
197
198 - finish looking at all mp*_ui functions to check for UV/IV vs long use.
199
200 - check overflow in prime iterator / trial division for 32-bit unsigned long.
201
202 - binomialmod better using factorialmod:
203 factorial_valuation and _binoval, then use factorialmod
204 also maybe better factorialmod
205
206 - real functions should have a settable default precision