No need to thank me, I just enjoyed to implement an algorithm in Squeak and signed for MIT license:<div>so use/abuse/misuse/... freely.<div>We all have to thank you and the others for looking after contributions and make them available</div>
<div>in Trunk or images.</div><div><br></div><div>I think that what Levente discovered from DigitalSignatureAlgorithm>>isProbablyPrime:</div><div>is worth some thoughts in terms of cleanup and rationalisation...from the version info this</div>
<div>piece of code seems to precede mine...and confirm the need of primality testing for encryption</div><div>(hence big integers)</div><div><br></div><div>Bye</div><div>Enrico</div><div>PS: I tried to see how to contribute, i.e. in the inbox but did not find too much of instructions</div>
<div>(something in Squeak board blog but not too clear for me at least). Any suggestion? URL?<br><br><div class="gmail_quote">On Sat, Jan 23, 2010 at 9:51 PM, David T. Lewis <span dir="ltr"><<a href="mailto:lewis@mail.msen.com">lewis@mail.msen.com</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">To follow up on this discussion from last month, I updated Squeak trunk<br>
such that LargePositiveInteger uses the probabilistic algorithm for<br>
#isPrime, and added method comments to explain. A couple of folks suggested<br>
this change, and Enrico concurred.<br>
<br>
It turns out that SmallInteger maxVal is a reasonable point at which<br>
to switch from use of #isPrime to #isProbablyPrime. On my system before<br>
the change:<br>
<br>
count := 1000.<br>
largeMin := SmallInteger maxVal + 1.<br>
<br>
"SmallInteger values up to maxVal"<br>
Time millisecondsToRun: [(SmallInteger maxVal - count to: SmallInteger maxVal) do: [:e | e isPrime]]. ==> 120<br>
Time millisecondsToRun: [(SmallInteger maxVal - count to: SmallInteger maxVal) do: [:e | e isProbablyPrime]]. ==> 984<br>
<br>
"LargePositiveInteger values just above SmallInteger maxVal"<br>
Time millisecondsToRun: [(largeMin to: largeMin + count) do: [:e | e isPrime]]. ==> 6599<br>
Time millisecondsToRun: [(largeMin to: largeMin + count) do: [:e | e isProbablyPrime]]. ==> 714<br>
<br>
After changing LargePositiveInteger>>isPrime, we have:<br>
<br>
"LargePositiveInteger values just above SmallInteger maxVal"<br>
Time millisecondsToRun: [(largeMin to: largeMin + count) do: [:e | e isPrime]]. ==> 719<br>
<br>
So the implementation of LargePositiveInteger>>isPrime is now this:<br>
<br>
isPrime<br>
"Answer true if the receiver is a prime number. Use a probabilistic implementation that<br>
is much faster for large integers, and that is correct to an extremely high statistical<br>
level of confidence (effectively deterministic)."<br>
<br>
^ self isProbablyPrime<br>
<br>
Thanks to Enrico for his patience ;-)<br>
<br>
Dave<br>
<br>
<br>
On Sat Dec 19 13:58:16 UTC 2009, Enrico Spinielli wrote:<br>
><br>
> The original implementation is was has been renamed by ul to isProbablyPrime<br>
> Note that the probability is according to Knuth's words<br>
><br>
> ...less than (1/4)^25 that such a 25-time-in-a-row procedure gives the wrong<br>
> information about its input. This is less than one chance in a quadrillion;<br>
> [...]<br>
> It's much more likely that our computer has dropped a bit in its<br>
> calculations,<br>
> due to hardware malfunctions or cosmic radiation, than that Algorithm P has<br>
> repeatedly guessed wrong!<br>
><br>
> So 'probabilistic' in this case is very much deterministic!<br>
> For accessible rationale about the algoritm (and a non probabilistic better<br>
> one as well)<br>
> you can also see "1.2.6 Example: Testing for<br>
> 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</a>>"<br>
> in SICP.<br>
> A possible improvement could have been to keep a list of the first N<br>
> prime numbers (i.e. N=1000 or whatever integrer where gain in performance<br>
> and or memory) and resort to the probabilistic test if self<br>
> is greater than the bigger in the list.<br>
><br>
> The value of original algorithm is all research and reasoning that went into<br>
> it from<br>
> Knuth et al. (note the order of growth is log(n), where n is the integer<br>
> under scrutiny)<br>
> The problem with the new implementation is that it goes thru testing numbers<br>
> which are<br>
> clearly not prime, 5, 15, 25, 35...just to mention multiples of 5.<br>
> It can possibly be faster for small integers hence the above possible<br>
> improvement suggestion...but for the rest it should be thrown away IMHO.<br>
><br>
> Primality testing is very important for modern electronic communications,<br>
> i.e. encryption<br>
> and as such it has to be reliable and performant for big integers.<br>
><br>
> Hope this clarifies<br>
> Bye<br>
> Enrico<br>
> PS: the comment in the code was explicit enough to allow to research for<br>
> the rationale about the algorithm...we should not fix what works<br>
> (well)<br>
> there are so many other fixes waiting...<br>
> On Sat, Dec 19, 2009 at 12:56 AM, David T. Lewis <lewis at <a href="http://mail.msen.com" target="_blank">mail.msen.com</a>>wrote:<br>
><br>
> > On Fri, Dec 18, 2009 at 05:25:45PM +0100, Enrico Spinielli wrote:<br>
> > > Hi all,<br>
> > > I am back to checking Squeak after quite a while and got latest trunk.<br>
> > > I looked after one of my contributions Integer>>isPrime<br>
> > > and I found my implementation of Algorithm P from Knuth's AOCP vol 2<br>
> > > substituted by an iteration of dividing self by all even numbers starting<br>
> > > from 3<br>
> > > and (correctly) stopping at self sqrtFloor.<br>
> > > This is IMHO a questionable/useless "improvement", not even looking to<br>
> > try<br>
> > > to implement the Sieve of Eratostene...!<br>
> > ><br>
> > > Again IMHO isPrime should be reverted back to what has been renamed<br>
> > > isProbablyPrime<br>
> > ><br>
> > > Not being anymore used to contribute I just signal it here...<br>
> > ><br>
> > > Hope it helps<br>
> > > Bye<br>
> > > --<br>
> > > Enrico Spinielli<br>
> ><br>
> > Enrico,<br>
> ><br>
> > Is this your original implementation?<br>
> ><br>
> ><br>
> > isPrime<br>
> > "See isProbablyPrimeWithK:andQ: for the algoritm description."<br>
> > | k q |<br>
> > self <= 1 ifTrue: [^self error: 'operation undefined'].<br>
> > self even ifTrue: [^self = 2].<br>
> > k := 1.<br>
> ><br>
> > q := self - 1 bitShift: -1.<br>
> > [q odd] whileFalse:<br>
> > [q := q bitShift: -1.<br>
> > k := k + 1].<br>
> ><br>
> > 25 timesRepeat: [(self isProbablyPrimeWithK: k andQ: q) ifFalse:<br>
> > [^false]].<br>
> > ^true<br>
> ><br>
> > It was recently changed as follows:<br>
> ><br>
> > > Name: Kernel-ul.305<br>
> > > Author: ul<br>
> > > Time: 25 November 2009, 2:55:43.339 am<br>
> > > UUID: a95be01c-d87c-154b-bdc6-c582dafad80b<br>
> > > Ancestors: Kernel-nice.304<br>
> > ><br>
> > > - added Integer >> #sqrtFloor, which returns the floor of the square root<br>
> > of the receiver.<br>
> > > - renamed Integer >> #isPrime to #isProbablyPrime.<br>
> > > - added Integer >> #isPrime which is implemented as a deterministic<br>
> > primality test<br>
> > > - both #isPrime and #isProbablyPrime return false for receivers <= 1<br>
> > instead of raising an error<br>
> ><br>
> > Is this a reasonable change?<br>
> ><br>
> > Dave<br>
> ><br>
> ><br>
</blockquote></div><br><br clear="all"><br>-- <br>Enrico Spinielli<br>"Do Androids dream of electric sheep?"— Philip K. Dick<br>"Hear and forget; see and remember;do and understand."—Mitchel Resnick<br>
</div></div>