[squeak-dev] Integer>>isPrime why reverting Knuth's algorithm
P (probabilistic primality test) with iteration over division with even
juan at jvuletich.org
Tue Dec 29 12:31:16 UTC 2009
Enrico Spinielli wrote:
> 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.
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.
More information about the Squeak-dev