On Sat, Nov 6, 2010 at 11:05 AM, David Kirkby <david.kir...@onetel.net> wrote: > 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" [...] > > 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. > > I just happen to think the prime_pi would be nice. A long time ago I
I think it would be wonderful to have a fast implementation of computing the number primes up to x, which is freely available, especially given the central role that the Riemann Hypothesis (which is a statement about pi(x)) has in mathematics. It's sad that there seem not to be any free modern fast implementations available (?). That said, I've advised two strong math students on projects to implement code to compute pi(x), and I would not be optimistic about an undergrad doing this as a project, unless they have a really unusually strong mathematical background, and excellent C/Cython programming skills. -- William -- 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
