On 6 November 2010 10:37, Bill Hart <goodwillh...@googlemail.com> wrote: > David, do you mean compute prime_pi up to some huge bound (by doing > sieving in parallel), then make a giant table with "waypoints" which > Sage refers to.
The magic code apepars to be the "Meissel-Lehmer-Lagarias-Miller-Odlyzko algorithm" , which I think in later revisions is easily improved by making it work in parallel. I know in terms of prime_pi implementations to date, 1) Mathematica - fastest 2) Sage 3) Maple slowest But accroding to Robert Bradshaw: http://www.mail-archive.com/sage-devel@googlegroups.com/msg25853.html "I believe the fastest was some code sitting on Victor Miller's laptop, which blew Mathematica away, but I don't think that's hit Sage (or production) anywhere yet." Robert then went on to say "Actually, the clever algorithm is very parallelizable," A quick Google shows this http://www.mail-archive.com/sage-devel@googlegroups.com/msg23058.html so it appears to be the "Meissel-Lehmer-Lagarias-Miller-Odlyzko algorithm" with one Sage developer, Victor Miller, the author of the paper Also with a bit of Googling I found http://www.google.co.uk/url?sa=t&source=web&cd=1&ved=0CBgQFjAA&url=http%3A%2F%2Fciteseerx.ist.psu.edu%2Fviewdoc%2Fdownload%3Fdoi%3D10.1.1.144.6373%26rep%3Drep1%26type%3Dpdf&rct=j&q=Meissel-Lehmer-Lagarias-Miller-Odlyzko%20algorithm&ei=S5XVTJqIBoTu4gb53JDhBw&usg=AFQjCNEWvChbq-IRZXMp_p1bq92KDC01PQ&sig2=fRPneeGFWbS_ENRgbrEW1w&cad=rja >From what I can see, the basic algorithm has probably been improved over time. Anyway, I've no idea how hard this would be, but it certainly looks to be one possible project. Another project I've seen proposed is http://trac.sagemath.org/sage_trac/ticket/9758 which could rid sage of that code I made you aware of, which you said was virtualy obviscated. But there's nothing there to indicate that this is particularly CPU intensive or that it could be improved with a parallel version. I just happen to think the prime_pi would be nice. A long time ago I proposed we create a Sage benchmark based on that of Karl Unterkofler http://trac.sagemath.org/sage_trac/ticket/6808 which was designed for Mathematica. One of the tests in there is prime_pi, so if Sage could do this faster than MMA, where currently we are slower, it would be nice. -- To post to this group, send an email to sage-devel@googlegroups.com To unsubscribe from this group, send an email to sage-devel+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/sage-devel URL: http://www.sagemath.org
