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

Enrico Spinielli enrico.spinielli at googlemail.com
Tue Dec 29 17:28:33 UTC 2009


That is exactly the point. Testing for primality these days is for things
like encryption
which works best for large integers.
I think a lot of this thread is about a misunderstanding of 'probabilistic
method'
in fact the probability is made so low that other factors, i.e. cosmic
radiation,
could factor in and mess things up, i.e. a bit of your computer memory...now
I do not see any evidence that we try to avoid the effects of cosmic
radiation, then I do not see why we should dismiss the primality testing
algorithm as 'non deterministic'...

The suggestion for Randal is fine for me, as anything else you want to do,
even keep current isPrime

Bye
Enrico

On Tue, Dec 29, 2009 at 1:31 PM, Juan Vuletich <juan at jvuletich.org> wrote:

> 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
>>
>>
> Hi.
>
> 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.
>
> Cheers,
> Juan Vuletich
>
>


-- 
Enrico Spinielli
"Do Androids dream of electric sheep?"— Philip K. Dick
"Hear and forget; see and remember;do and understand."—Mitchel Resnick
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.squeakfoundation.org/pipermail/squeak-dev/attachments/20091229/3a876950/attachment.htm


More information about the Squeak-dev mailing list