- Testing requirements after changes:
* Test all functions return either native or bigints. Functions that
return raw MPU::GMP results will return strings, which isn't right.
* Valgrind, coverage
* use: -O2 -g -Wall -Wextra -Wdeclaration-after-statement -fsigned-char
* Test on 32-bit Perl. Test on Win32.
- Move .c / .h files into separate directory.
version does it in a painful way. Something simpler to be had?
- finish test suite for bignum. Work on making it faster.
- An assembler version of mulmod for i386.
- More efficient Mertens. The current version has poor growth.
For 32-bit, consider doing XS followed by sum for remainder.
- It may be possible to have a more efficient ranged totient. We're using
the sieve up to n/2, which is better than most people seem to use, but I'm
not completely convinced we can't do better. The method at:
http://codegolf.stackexchange.com/a/26747/30069 ends up very similar. For
the monolithic results the main bottleneck seems to be the array return.
- Big features:
- QS factoring
- Figure out a way to make the internal FOR_EACH_PRIME macros use a segmented
sieve.
- Rewrite 23-primality-proofs.t for new format (keep some of the old tests?).
- Use Montgomery routines in more places: Factoring.
- Factoring in PP code is really wasteful -- we're calling _isprime7 before
we've done enough trial division, and later we're calling it on known
composites. Note how the XS code splits the factor code into the public
API (small factors, isprime, then call main code) and main code (just the
algorithm). The PP code isn't doing that, which means we're doing lots of
extra primality checks, which aren't cheap in PP.
- Consider using Test::Number::Delta for many tests
- More tweaking of LMO prime count.
- OpenMP. The step 7 inner loop is available.
- Convert to 32-bit+GMP to support large inputs, add to MPU::GMP.
- Try __int128.
- Variable sieve size
- look at sieve.c style prime walking
- Fenwick trees for prefix sums
- Iterators speedup:
1) config option for sieved next_prime. Very general, would make
next_prime run fast when called many times sequentially. Nasty
mixing with threads.
2) iterator, PrimeIterator, or PrimeArray in XS using segment sieve.
- Perhaps have main segment know the filled in range. That would allow
a sieved next_prime, and might speed up some counts and the like.
- Consider exporting is_bpsw_prime and inverse Li
- Benchmark simple SoEs, SoA. Include Sisyphus SoE hidden in Math::GMPz.
- Try using malloc/free for win32 cache memory. #define NO_XSLOCKS
- Investigate optree constant folding in PP compilation for performance.
Use B::Deparse to check.
- Ensure a fast path for Math::GMP from MPU -> MPU:GMP -> GMP, and back.
- We don't use legendre_phi for other functions any more, but it'd be nice
to speed it up using some ideas from the Ohana 2011 SAGE branch. For example
(10**13,10**5) takes 2.5x longer, albeit with 6x less memory.
- More Pari: parforprime
- znlog:
= GMP BSGS for znlog.
= Clean up znlog (PH, BSGS, Rho).
= Experiment with Wang/Zhang 2012 Rho cycle finding
- consider using Ramanujan Li for PP code.
- xt/pari-compare: add chinese, factorial, vecmin, vecmax,
bernfrac, bernreal, LambertW.
- In vecsum, we could create the string and call vecsum with 1 argument. The
trick is telling vecsum we only want one thing. Idea:
if (status != 0) {
dSP; ENTER; PUSHMARK(SP);
XPUSHs(sv_2mortal(newSVpvn("123456789012345678901234567890", 30)));
PUTBACK; _vcallsubn(aTHX_ G_SCALAR, VCALL_ROOT, "_to_bigint", 1); LEAVE;
return;
}
- Proth test using LLR. Change mersenne test file to test both.
Note: what does this mean? Both LLR and Proth are in GMP now.
- harmreal and harmfrac for general $k
- For PP, do something like the fibprime examples. At load time, look for
the best library (GMPz, GMP, Pari, BigInt) and set $BICLASS. Then we
should use that class for everything. Go ahead and return that type.
Make a config variable to allow get/set.
- Support FH for print_primes. PerlIO_write is giving me fits.
- Test for print_primes. Not as easy with filenos.