#40 next_prime speed improvement

[SuRaMoN]

next_prime is very slow (in comparisation with for example GMP)

I included a small and simple fix that uses the same "algorithm" as GMP

speed improvement:
next_prime(2^1200);
old execution time: 8s
with fix: 3s

Any interest in including this fix? If so, i'm willing to improve it a lot more (and improve prev_prime also).

this is a patch for "maxima/src/ifactor.lisp": cd maxima/src/ && patch < ifactor.diff

[SuRaMoN]

next_prime speed improvement patch for "maxima/src/ifactor.lisp"

[SuRaMoN]

forget to mention patch is for Maxima 5.19.0

[Andrej Vodopivec]

I looked at the patch and it seems OK (I didn't check all numbers though). I can commit it to cvs when you are done with it. Please include some copyright statement.

Thanks for working on this.

[SuRaMoN]

Aug-24-2009 second patch for "maxima/src/ifactor.lisp" for maxima 5.19.0

[SuRaMoN]

Aug-24-2009 third patch for "maxima/src/ifactor.lisp" for maxima 5.19.0

[SuRaMoN]

All right

The first patch was just a "proof of concept"
In he last patch i uploaded (still for maxima 5.19.0) I improved the algorithm even more by calculating gcd with product of primes. I also changed prev_prime to use the new algorithm.

I have done some benchmarks and for small numbers, my version is about twice as fast. For big numbers, the speed gain can be much greater:

next_prime(2^3000):
my version: 30s
GMP: 20s
old version: 210s

for numbers in [2...10^5] there is also a speed gain (twice as fast)

i have renamed the old "next_prime" to "next_prime_old". idem for prev_prime

There are still some functions in maxima that use the old algorithm (eg "primes") because they call a helper function ("next-prime") directly.

I included a copyright in the patch (i just copied it from some patch i found on this forum, i hope it suffices)

[Andrej Vodopivec]

The patch (with minor changes) has been applied to cvs. Thank you for your contribution.