On 16 November 2010 06:57, William Stein <wst...@gmail.com> wrote: > > > On Mon, Nov 15, 2010 at 5:45 PM, Dr. David Kirkby <david.kir...@onetel.net> > wrote: >> >> I've noticed two issues with random_prime() in Sage. >> >> 1) Whilst Sage's random_prime() looks as though it will work for numbers >> to at least 10^100000000, if one specifies a lower bound, then the upper >> bound reduces to 2^40, which is about 10^12. >> >> This situation does *not* change if one specifies one only wants a pseudo >> prime. >> >> sage: random_prime(10^13,proof=False, lbound=12) >> <snip> >> NotImplementedError: computation of prime_pi() greater 2**40 not >> implemented >> >> http://trac.sagemath.org/sage_trac/ticket/10277 >> >> Mathematica 7.0.1 has no such limitation. One can set a lower bound, and >> still have an upper bound to at least 10^100000000 > > What version of Sage are you using, and on what computer?
4.6.1.alpha1 with the two patches at http://trac.sagemath.org/sage_trac/ticket/10112 which are both related to random_prime(). This is a 32-bit build on OpenSolaris. I had previously given those patches positive review, but I've now set it to 'needs info' just in case they are the cause of this, but I somewhat doubt it. > sage: random_prime(10^13,proof=False, lbound=12) > 7461989010461 > I do not get NotImplementedError. Moreover, reading the source for > random_prime in sage-4.6, this function doesn't even call prime_pi. Well, that's odd. Three likely issues are: * There has been some change in 4.6.1.alpha1 * http://trac.sagemath.org/sage_trac/ticket/10112 is the cause, which I highly doubt. * Something is wrong with my setup. >> 2) The Sage implementation is incredibly slow compared to Mathematica. >> >> On my machine (a 3.33 GHz Sun with !OpenSolaris) using a 32-bit build of >> Sage, it took 1455 seconds to generate a random prime up to 10^1000. >> >> Mathematica 7.01 does this in 7 seconds. >> >> http://trac.sagemath.org/sage_trac/ticket/10278 > > For me Sage is 10 times faster than Mathematica: > sage: time p = random_prime(10^1000,proof=False) > CPU times: user 0.98 s, sys: 0.00 s, total: 0.99 s > Wall time: 0.99 s > sage: time p = random_prime(10^1000,proof=False) > CPU times: user 0.98 s, sys: 0.00 s, total: 0.99 s > Wall time: 0.99 s > sage: !math > Mathematica 7.0 for Mac OS X x86 (64-bit) > Copyright 1988-2009 Wolfram Research, Inc. > In[1]:= Timing[RandomPrime[10^1000]] > Out[1]= {8.14694, 593... >> If Mathematica does use a pseudo prime test, it is not documented. >> >> http://reference.wolfram.com/mathematica/ref/RandomPrime.html > > It is completely clear from the documentation above Mathematica *only* uses > a pseudo prime test. It says right there "gives a pseudorandom prime number > in the range". > William I was interpreting that as a prime generated by a pseudo random number generator, whereas you are interpreting it as a random pseudoprime. If Mathematica is not proving the number is prime, then perhaps it should say its a pseudorandom pseudoprime, wihch is a bit of a mouthful! That would obviously account for the differences seen. Dave -- 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
