[squeak-dev] Integer>>isPrime why reverting Knuth's algorithm
P (probabilistic primality test) with iteration over division with even
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
> Not being anymore used to contribute I just signal it here...
> Hope it helps
> 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