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
