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! --~--~---------~--~----~------------~-------~--~----~ 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 -~----------~----~----~----~------~----~------~--~---
