[squeak-dev] Integer>>isPrime why reverting Knuth's algorithm
P (probabilistic primality test) with iteration over division with even
avalloud at smalltalk.comcastbiz.net
Wed Dec 30 23:43:22 UTC 2009
On 12/29/2009 4:31 AM, Juan Vuletich wrote:
> 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.
> Juan Vuletich
More information about the Squeak-dev