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

Andres Valloud avalloud at smalltalk.comcastbiz.net
Thu Dec 24 20:51:09 UTC 2009


IMO, "probabilistic" should never be confused with "deterministic".  I 
also read that section of Knuth's book and, if anything, the feeling was 
that you could be pragmatic if you wanted to with really large numbers 
and use the probabilistic test.  However, you never know for sure, so 
that's why he also discusses several deterministic tests.

Note that if probabilistic tests were all that mattered, then why bother 
figuring out the AKS family of primality tests, right?  The earlier 
versions of Knuth's books certainly could not assume that the complexity 
of checking an integer's primality was in P, because that was found with 
the AKS tests.  So, if anything, the existence of deterministic tests in 
P should be taken into account when reading Knuth's books (particularly 
the editions before AKS was known).

If anything, I'd rename isProbablyPrime to something like 
probabilisticPrimalityTestAlgorithmSuch.

Andres.

On 12/19/2009 5:58 AM, Enrico Spinielli wrote:
> 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
> <mailto: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



More information about the Squeak-dev mailing list