[Tutor] pickle problems

[Steven D'Aprano]

On Wed, Aug 22, 2012 at 11:39:46PM -0400, Dave Angel wrote:
> On 08/22/2012 07:32 PM, Richard D. Moores wrote:
> > <snip>
> >
> > My code uses gmpy2.is_prime()  (lines 79 and 89). is_prime() is VERY fast.
> 
> You do know that this gmpy2 function is only statistically correct ?  it
> can false positive.  I don't know what the probs are, but it uses
> Miller-Rabin, with a default factor of 25.

What Dave means is:

- If gmpy2.is_prime says a number is not prime, then that is 
  certainly true;

- but if it says that a number is prime, then that is only 
  probably true.

With 25 Miller-Rabin tests, the probability of a false positive is (if I 
remember correctly) 1 time in 4**25 or about 1 time in a million 
billion. (That's American billion, 10**9, not old-style English 
billion.) If you tested a thousand prime numbers a second for thirty 
thousand years, you would expect perhaps one false positive.

The odds are much higher that a hardware fault or stray cosmic ray 
hitting the CPU or memory chip will cause the computer to calculate the 
wrong answer.


For anyone interested, here is my pyprimes module:

http://pypi.python.org/pypi/pyprimes/

which is written in pure Python (no reliance on gmpy2), so you can 
actually see how the algorithms work, although it is correspondingly 
much slower.

Source code can be found here:

http://code.google.com/p/pyprimes/source/browse/src/pyprimes.py

It is *extensively* documented. The API is alpha-quality and subject to 
change.


-- 
Steven