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

Levente Uzonyi leves at elte.hu
Sat Dec 19 02:18:39 UTC 2009


On Fri, 18 Dec 2009, Enrico Spinielli wrote:

> Hi all,
> I am back to checking Squeak after quite a while and got latest trunk.
> I looked after one of my contributions Integer>>isPrime
> and I found my implementation of Algorithm P from Knuth's AOCP vol 2
> substituted by an iteration of dividing self by all even numbers starting
> from 3
> and (correctly) stopping at self sqrtFloor.
> This is IMHO a questionable/useless "improvement", not even looking to try
> to implement the Sieve of Eratostene...!

What's the problem with the current #isPrime implementation? How could a 
sieve based primality test be faster?

>
> Again IMHO isPrime should be reverted back to what has been renamed
> isProbablyPrime
>

Why?


Levente

> Not being anymore used to contribute I just signal it here...
>
> Hope it helps
> Bye
> -- 
> Enrico Spinielli
> "Do Androids dream of electric sheep?"? Philip K. Dick
> "Hear and forget; see and remember;do and understand."?Mitchel Resnick
>



More information about the Squeak-dev mailing list