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

Nicolas Cellier nicolas.cellier.aka.nice at gmail.com
Sun Jan 24 15:12:17 UTC 2010


2010/1/24 Nicolas Cellier <nicolas.cellier.aka.nice at gmail.com>:
> 2010/1/24 Enrico Spinielli <enrico.spinielli at googlemail.com>:
>> No need to thank me, I just enjoyed to implement an algorithm in Squeak and
>> signed for MIT license:
>> so use/abuse/misuse/... freely.
>> We all have to thank you and the others for looking after contributions and
>> make them available
>> in Trunk or images.
>> I think that what Levente discovered from
>> DigitalSignatureAlgorithm>>isProbablyPrime:
>> is worth some thoughts in terms of cleanup and rationalisation...from the
>> version info this
>> piece of code seems to precede mine...and confirm the need of primality
>> testing for encryption
>> (hence big integers)
>> Bye
>> Enrico
>> PS: I tried to see how to contribute, i.e. in the inbox but did not find too
>> much of instructions
>> (something in Squeak board blog but not too clear for me at least). Any
>> suggestion? URL?
>>
>
> The preferred way:
> 1) make your changes to the image
> 2) open a Monticello browser,
> 3) select one dirty packages in left pane (marked with *)
>   presumably, it's Kernel here.
> 4) select http://source.squeak.org/inbox in right pane
> 5) press save button
> 6) repeat step 3 for each dirty package
> 7) post a message to this list indicating which set of .mcz solves which problem
>
> If http://source.squeak.org/inbox does not appear for a specific package:
> a) unselect package in left pane
> b) select  http://source.squeak.org/inbox in right pane
> c) choose pop up menu option 'add to package...'
> d) go to step 3
>
> Hope I did not forget anything; maybe ask for a free beer to next
> Squeak smalltalk event ?
>
> cheers
>
> Nicolas
>

Ah yes, I forgot, use a relevant version message when saving...

>> On Sat, Jan 23, 2010 at 9:51 PM, David T. Lewis <lewis at mail.msen.com> wrote:
>>>
>>> To follow up on this discussion from last month, I updated Squeak trunk
>>> such that LargePositiveInteger uses the probabilistic algorithm for
>>> #isPrime, and added method comments to explain. A couple of folks
>>> suggested
>>> this change, and Enrico concurred.
>>>
>>> It turns out that SmallInteger maxVal is a reasonable point at which
>>> to switch from use of #isPrime to #isProbablyPrime. On my system before
>>> the change:
>>>
>>>  count := 1000.
>>>  largeMin := SmallInteger maxVal + 1.
>>>
>>>  "SmallInteger values up to maxVal"
>>>  Time millisecondsToRun: [(SmallInteger maxVal - count to: SmallInteger
>>> maxVal) do: [:e | e isPrime]]. ==> 120
>>>  Time millisecondsToRun: [(SmallInteger maxVal - count to: SmallInteger
>>> maxVal) do: [:e | e isProbablyPrime]]. ==> 984
>>>
>>>  "LargePositiveInteger values just above SmallInteger maxVal"
>>>  Time millisecondsToRun: [(largeMin to: largeMin + count) do: [:e | e
>>> isPrime]]. ==> 6599
>>>  Time millisecondsToRun: [(largeMin to: largeMin + count) do: [:e | e
>>> isProbablyPrime]]. ==> 714
>>>
>>> After changing LargePositiveInteger>>isPrime, we have:
>>>
>>>  "LargePositiveInteger values just above SmallInteger maxVal"
>>>  Time millisecondsToRun: [(largeMin to: largeMin + count) do: [:e | e
>>> isPrime]]. ==> 719
>>>
>>> So the implementation of LargePositiveInteger>>isPrime is now this:
>>>
>>> isPrime
>>>        "Answer true if the receiver is a prime number. Use a probabilistic
>>> implementation       that
>>>        is much faster for large integers, and that is correct to an
>>> extremely high statistical
>>>        level of confidence (effectively deterministic)."
>>>
>>>        ^ self isProbablyPrime
>>>
>>> Thanks to Enrico for his patience ;-)
>>>
>>> Dave
>>>
>>>
>>> On Sat Dec 19 13:58:16 UTC 2009, 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>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