The original implementation is was has been renamed by ul to isProbablyPrime
Note that the probability is according to Knuth's words

...less than (1/4)^25 that such a 25-time-in-a-row procedure gives the wrong
information about its input. This is less than one chance in a quadrillion;
[...]
It's much more likely that our computer has dropped a bit in its
calculations,
due to hardware malfunctions or cosmic radiation, than that Algorithm P has
repeatedly guessed wrong!

So 'probabilistic' in this case is very much deterministic!
For accessible rationale about the algoritm (and a non probabilistic better
one as well)
you can also see "1.2.6 Example: Testing for
Primality<http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.html#%_sec_1.2.6>"
in SICP.
A possible improvement could have been to keep a list of the first N
prime numbers (i.e. N=1000 or whatever integrer where gain in performance
and or memory) and resort to the probabilistic test if self
is greater than the bigger in the list.

The value of original algorithm is all research and reasoning that went into
it from
Knuth et al. (note the order of growth is log(n), where n is the integer
under scrutiny)
The problem with the new implementation is that it goes thru testing numbers
which are
clearly not prime, 5, 15, 25, 35...just to mention multiples of 5.
It can possibly be faster for small integers hence the above possible
improvement suggestion...but for the rest it should be thrown away IMHO.

Primality testing is very important for modern electronic communications,
i.e. encryption
and as such it has to be reliable and performant for big integers.

Hope this clarifies
Bye
Enrico
PS: the comment in the code was explicit enough to allow to research for
      the rationale about the algorithm...we should not fix what works
(well)
      there are so many other fixes waiting...
On Sat, Dec 19, 2009 at 12:56 AM, David T. Lewis <lewis at mail.msen.com>wrote:

> On Fri, Dec 18, 2009 at 05:25:45PM +0100, 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...!
> >
> > Again IMHO isPrime should be reverted back to what has been renamed
> > isProbablyPrime
> >
> > Not being anymore used to contribute I just signal it here...
> >
> > Hope it helps
> > Bye
> > --
> > Enrico Spinielli
>
> Enrico,
>
> Is this your original implementation?
>
>
>   isPrime
>        "See isProbablyPrimeWithK:andQ: for the algoritm description."
>        | k q |
>        self <= 1 ifTrue: [^self error: 'operation undefined'].
>        self even ifTrue: [^self = 2].
>        k := 1.
>
>        q := self - 1 bitShift: -1.
>        [q odd] whileFalse:
>                        [q := q bitShift: -1.
>                        k := k + 1].
>
>        25 timesRepeat: [(self isProbablyPrimeWithK: k andQ: q) ifFalse:
> [^false]].
>        ^true
>
> It was recently changed as follows:
>
> > Name: Kernel-ul.305
> > Author: ul
> > Time: 25 November 2009, 2:55:43.339 am
> > UUID: a95be01c-d87c-154b-bdc6-c582dafad80b
> > Ancestors: Kernel-nice.304
> >
> > - added Integer >> #sqrtFloor, which returns the floor of the square root
> of the receiver.
> > - renamed Integer >> #isPrime to #isProbablyPrime.
> > - added Integer >> #isPrime which is implemented as a deterministic
> primality test
> > - both #isPrime and #isProbablyPrime return false for receivers <= 1
> instead of raising an error
>
> Is this a reasonable change?
>
> Dave
>
>
>


-- 
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/20091219/e0e883b1/attachment.htm