My benchmarks agree. The gap between primes is so small as to make my communication point moot. Even checking some of the record setting prime gaps, the pure pari method was never more than 20% faster, and I think asymptotically it is likely they are equal speed (gaps don't get big enough fast enough for iterating through the gap to be a nontrivial cost compared to a primality proof). I still think the patch is wise since pari's number theory is likely to be better maintained and optimized over the long term and I believe writing SAGE's own nextprime is "reinventing the wheel, not building the car" but there is not much difference to the average user and maintenance on such a simple function is not terribly costly.
Before I forget, I had a couple of other comments on the inconsistency question: (1) Previous_prime has no proof option (2) The documentation for "primes" in sage/rings/arith.py line 660 claims next_prime has proof=true by default, but the documentation for next_prime itself has the opposite, same file line 728. On Jun 8, 12:55 am, Michel <[EMAIL PROTECTED]> wrote: > Well I did some benchmarks and sage's provable next_prime seems > to be about the same speed as a combination of pari next_prime > with is_prime. I agree that this is a bit counterintuitive. > > sage: time next_prime(2^1024, proof=False) > CPU times: user 0.69 s, sys: 0.01 s, total: 0.70 s > Wall time: 0.92 > 179769313486231590772930519078902473361797697894230657273430081157732675805500963132708477322407536021120113879871393357658789768814416622492847430639474124377767893424865485276302219601246094119453082952085005768838150682342462881473913110540827237163350510684586298239947245938479716304835356329624224137859 > sage: time is_prime(_) > CPU times: user 29.81 s, sys: 0.10 s, total: 29.91 s > Wall time: 38.23 > True > sage: time next_prime(2^1024, proof=True) > CPU times: user 30.66 s, sys: 0.04 s, total: 30.70 s > Wall time: 38.98 > 179769313486231590772930519078902473361797697894230657273430081157732675805500963132708477322407536021120113879871393357658789768814416622492847430639474124377767893424865485276302219601246094119453082952085005768838150682342462881473913110540827237163350510684586298239947245938479716304835356329624224137859 > > Michel > On Jun 8, 3:48 am, Jack Schmidt <[EMAIL PROTECTED]> > wrote: > > > Pari uses the Baillie-Pomerance-Selfridge-Wagstaff primality test, > > which at its heart is the observation that very few numbers are both > > (Fermat) strong pseudoprimes base 2 and Lucas pseudoprimes for x^2+P*x > > +1 where P is the smallest positive integer such that P^2 - 4 is not a > > quadratic residue (for the specific number being tested). There are > > no such pseudoprimes less than 10^13 which can be verified by > > consulting the list of fermat strong pseudoprimes base 2 at: > > http://www.chalcedon.demon.co.uk/rgep/spsp-13.gz > > > In some sense this is not a probabilistic test as described in > > textbooks since the (unknown) probability is fixed. One could > > supplement BPSW with Rabin-Miller, but tests during the GAP > > implementation showed that even a single trial of Rabin-Miller was > > ridiculously slow given the fact that not a single composite BPSW > > pseudoprime has ever been found. > > > The pari implementation contains speedups for small integers and > > integers with small factors. It also contains a clever optimization > > to use GCD instead of trial division to handle testing many factors at > > once. There is a relatively simple calculation to show when GCD is > > faster than trial division. > > > The pari implementation is in basemath/ifactor1.c lines 390-508 in the > > functions BSW_psp and the machine integer version uisprime. > > > Pari does allow calling Rabin-Miller using the ispseudoprime(N,1) > > function, but this is not done in nextprime() which uses direct calls > > to BSW_psp(N) and a simple stepping procedure similar to the one in > > SAGE, but using prime residues mod 210 instead of mod 2. This is line > > 637-675 of the same file. > > > I recommend patching SAGE to increment using nextprime rather than n > > +=2, partially because pari's code is currently more optimizied and > > more likely to continue to be optimized, and partially because there > > is less I/O between the two processes; let pari have the entire tight > > loop, don't communicate during the tight loop. > > > On Jun 7, 3:28 pm, "William Stein" <[EMAIL PROTECTED]> wrote: > > > > On 6/7/07, Michel <[EMAIL PROTECTED]> wrote: > > > > > I guess you mean the opposite. > > > > Yes, I meant the opposite -- I wrote that in an extreme hurry > > > before getting to lunch. > > > > > The pseudoprimetest > > > > used internally by pari should never declare a prime number > > > > to be composite. Most likely they use Miller Rabin which > > > > has this property. I will check. > > > > Yes, please do. > > > > William --~--~---------~--~----~------------~-------~--~----~ To post to this group, send email to sage-devel@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/sage-devel URLs: http://sage.scipy.org/sage/ and http://modular.math.washington.edu/sage/ -~----------~----~----~----~------~----~------~--~---
