Oops, Patch contains stupid typo. The docstring for precprime(gen self) should be
precprime(x): *largest* pseudoprime <= x Michel On Jun 9, 9:06 pm, Michel <[EMAIL PROTECTED]> wrote: > Hi, > > Attached is a patch that fixes these inconsistencies. It also > introduces previous_probable_prime() to be consistent > with next_probable_prime() > > next/previous_prime with proof True now call pari.nextprime, > pari.precprime. This is not much faster but it does make for more > elegant code. > > http://emis.uhasselt.be/sage_patches/next_prime_inconsistencies.patch > > Michel > > On Jun 8, 5:49 pm, Jack Schmidt <[EMAIL PROTECTED]> > wrote: > > > 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/ -~----------~----~----~----~------~----~------~--~---
