On Sat, May 2, 2009 at 11:42 PM, Dr. David Kirkby <david.kir...@onetel.net> wrote: > > mabshoff wrote: > >>> He told me Mathematica can go up to about 2^45 or so, but not beyond. >> >> At least for MMA 6.0 on linux x86-64 the limit seems to be around >> 2^47: > > As I said in the other post, the limit is PrimePi[249999999999999]. > >> MMA Sage >> >> 2^44: 18.04 110.88 (597116381732) >> 2^45: 29.98 207.61 (1166746786182) >> 2^46: 47.59 389.98 (2280998753949) >> 2^47: 89.25 728.84 (4461632979717) >> 2^48: NA :) about an hour - correct? >> >> According to Alex's numbers at least on his laptop 2^46 was correct on >> 32 bits, but given the length of the test (~6 minutes on sage.math >> this isn't really doctestable). >> >>> The algorithm in Mathematica is completely different (and better) than >>> what Andrew implemented for Sage. As far as I know the situation for >>> computing pi(X) using general purpose math software is thus: > > One (admitidly unlikely) possibility is that Wolfram have used the same > algorithm, but used assembly code. I think they claim the kernel is > C/C++, but that permits bits of inline assembly. > > >>> * Mathematica -- has the best implementation available >>> >>> * Sage -- now has the second best implementation available >> >> Yep, the old implementation was about 1000 times slower than Andrew's >> which is about 5 times slower than MMA 6.0 - so great job from >> catching us up from 5000 times to only 5 times :). > > I gather you have managed to get a SPARC version of Sage running. It > would be interesting to compare the performance on SPARC of Mathematica > and Sage. I very much doubt Wolfram would have used hand-optimised > assembly code on SPARC, so if the timings still show Mathematica to be > 5x quicker, then yes, I would agree it's a better algorithm. But if the > timings are very similar, it suggests to me that perhaps the better > performance of Mathematica is due to writing assembly code, rather than > using a high-level language. > >>> * Pari, Maple, Matlab -- "stupid" implementations, which all simply >>> enumerate all primes up to x and see how many there are. Useless, and >>> can't come close to what Sage or Mathematica do. > >> Well, what should we pick as upper bound? 2^40 seems to be what Andrew >> suggests, but maybe 2^42 or 2^43? In that range we can actually add >> #long doctests and I would be much more comfortable that we would at >> least catch potential issues. > > Personally, if Sage can go to 249999999999999, then I would use that as > an upper bound. If the algorithm in Sage gives the same answer as > Mathematica > > In[95]:= PrimePi[249999999999999] > Out[95]= 7783516108362 > > then why not use Sage to there? The poor SPARC I used for this was very > heavily loaded and quite old, but it only took 20 minutes or so. Even an > algorithm that is 5x slower should be able to compute > primepi(249999999999999) in under an hour on any half-decent modern > machine. > > Of course, a search of the literature for a better algorithm might have > some millage. Unfortunately, I no longer have access to a university > account and so can't search journals without paying for access to > individual ones, which clearly I can't justify. Neither am I > particularly good at maths, having never maths studied beyond that > needed for an engineering degree > > > One unfortunate side-effect of the closed-source vs open-source code is > the fact that if open-source code (e.g. Sage) has a faster algorithm > than Mathematica, then it's relatively easy for WRI to look at the > algorithm in Sage and use the same one, to bring Mathematica and Sage to > similar performances. The converse is not true of course - it is not > possibly for Sage developers to find out the algorithm Mathematica uses. > However, a look at > > http://mathworld.wolfram.com/PrimeCountingFunction.html > > might give some clues as to the algorithm Mathematica uses. Although the > algorithm Mathematica is not stated in that Mathworld page, there are a > number of references. Two look interesting: > > Mapes, D. C. "Fast Method for Computing the Number of Primes Less than a > Given Limit." Math. Comput. 17, 179-185, 1963. > > Gourdon, X. "New Record Computation for pi(x), x=10^21." 27 Oct 2000. > http://listserv.nodak.edu/scripts/wa.exe?A2=ind0010&L=nmbrthry&P=2988 > > The link > http://listserv.nodak.edu/cgi-bin/wa.exe?A2=ind0010&L=nmbrthry&P=2988 > states the algorithm used, but in a way I don't understand. It says: > > "This value has been checked by computing pi(10^21+10^8) with > a different parameter y used in the algorithm" > > but y is not defined!
This page: http://reference.wolfram.com/mathematica/note/SomeNotesOnInternalImplementation.html#12788 says what algorithm is used in Mathematica to compute PrimePi, and it is definitely *not* the one used in Sage. It is a completely different harder-to-implement algorithm with better asymptotic complexity. In any case, we definitely do intend to install Mathematica on our new Sparc T5240 box, since UW has a site license for Mathematica which includes a Sparc Solaris version. -- William --~--~---------~--~----~------------~-------~--~----~ To post to this group, send email to sage-devel@googlegroups.com To unsubscribe from this group, send email to sage-devel-unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/sage-devel URLs: http://www.sagemath.org -~----------~----~----~----~------~----~------~--~---
