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