[squeak-dev] Integer>>isPrime why reverting Knuth's algorithm P (probabilistic primality test) with iteration over division with even numbers?

Juan Vuletich juan at jvuletich.org
Tue Dec 29 12:31:16 UTC 2009

Enrico Spinielli wrote:
> Hi,
> I just reply with the words of SICP, footnote 47 in the link below:
> In testing primality of very large numbers chosen at random, the 
> chance of stumbling upon a value that fools the Fermat test is less 
> than the chance that cosmic radiation will cause the computer to make 
> an error in carrying out a ``correct'' algorithm. Considering an 
> algorithm to be inadequate for the first reason but not for the second 
> illustrates the difference between mathematics and engineering.
> Bye
> Enrico


That's assuming that you're testing very large numbers chosen at random. 
That's not always the case! And also assuming that the computer is not 
fail-proof. For example, a typical setup for critical applications is to 
have 3 computers do the same calculation, and vote on the correct result.

A routine should not assume much about how it is going to be used. 
Instead, it should make clear its assumptions and limitations so callers 
will know. #isProbablyPrime or such, and a method comment with exactly 
the text you quote is the best.

Juan Vuletich

More information about the Squeak-dev mailing list