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? 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. > > 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... However, note that this algorithm will have *highly* nondeterministic runtime! sage: time p = random_prime(10^1000,proof=False) CPU times: user 4.19 s, sys: 0.00 s, total: 4.20 s Wall time: 4.20 s sage: time p = random_prime(10^1000,proof=False) CPU times: user 7.79 s, sys: 0.01 s, total: 7.80 s Wall time: 7.80 s OH, I see, you mean that you get slow results with proof=True. That I could believe, since proving numbers are prime quickly is really hard. > 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 > > > > 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<sage-devel%2bunsubscr...@googlegroups.com> > For more options, visit this group at > http://groups.google.com/group/sage-devel > URL: http://www.sagemath.org > -- William Stein Professor of Mathematics University of Washington http://wstein.org -- 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
