File: TODO

package info (click to toggle)
libmath-prime-util-perl 0.46-1
  • links: PTS, VCS
  • area: main
  • in suites: jessie, jessie-kfreebsd
  • size: 2,044 kB
  • ctags: 1,933
  • sloc: perl: 19,450; ansic: 6,379; python: 24; makefile: 11
file content (102 lines) | stat: -rw-r--r-- 3,965 bytes parent folder | download
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
- 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

- is_power should take a third argument that gets set to the root

- znlog:
    = GMP BSGS for znlog.
    = Clean up znlog (PH, BSGS, Rho).
    = Experiment with Wang/Zhang 2012 Rho cycle finding

- Like gmpy:  lucasu, lucasv, lucasu_mod, lucasv_mod  e.g. lucasu_mod(p,q,k,n)
  See: http://joye.site88.net/papers/JQ96lucas.pdf to make sure we're being
  efficient.

- 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_PP, "vecsum", 1); LEAVE;
        return;
      }