[squeak-dev] Integer>>isPrime why reverting Knuth's algorithm P
(probabilistic primality test) with iteration over division with even
numbers?
Enrico Spinielli
enrico.spinielli at googlemail.com
Tue Dec 29 09:31:28 UTC 2009
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
On Thu, Dec 24, 2009 at 9:51 PM, Andres Valloud <
avalloud at smalltalk.comcastbiz.net> wrote:
> 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
>>
>
>
--
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/20091229/248de6ca/attachment.htm
More information about the Squeak-dev
mailing list
|