#40 next_prime speed improvement

closed
nobody
None
5
2009-10-24
2009-08-21
SuRaMoN
No

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

Discussion

  • SuRaMoN

    SuRaMoN - 2009-08-21

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

     
  • SuRaMoN

    SuRaMoN - 2009-08-21

    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

    SuRaMoN - 2009-08-24

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

     
  • SuRaMoN

    SuRaMoN - 2009-08-24

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

     
  • SuRaMoN

    SuRaMoN - 2009-08-24

    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

    • status: open --> closed
     
  • Andrej Vodopivec

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

     

Log in to post a comment.

Get latest updates about Open Source Projects, Conferences and News.

Sign up for the SourceForge newsletter:

JavaScript is required for this form.





No, thanks