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

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

<<a href="http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.html#%_sec_1.2.6" target="_blank">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 <[hidden email]

<mailto:[hidden email]>> 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

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