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

> 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
>
>
>
>