The original implementation is was has been renamed by ul to isProbablyPrime<div>Note that the probability is according to Knuth's words</div><blockquote class="webkit-indent-blockquote" style="margin: 0 0 0 40px; border: none; padding: 0px;">
<div>...less than (1/4)^25 that such a 25-time-in-a-row procedure gives the wrong</div><div>information about its input. This is less than one chance in a quadrillion; [...]</div><div>It's much more likely that our computer has dropped a bit in its calculations,</div>
<div>due to hardware malfunctions or cosmic radiation, than that Algorithm P has</div><div>repeatedly guessed wrong!</div></blockquote>So 'probabilistic' in this case is very much deterministic!<div>For accessible rationale about the algoritm (and a non probabilistic better one as well)<br>
<div>you can also see "<a href="http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.html#%_sec_1.2.6">1.2.6 Example: Testing for Primality</a>" in SICP.</div><div>A possible improvement could have been to keep a list of the first N</div>
<div>prime numbers (i.e. N=1000 or whatever integrer where gain in performance</div><div>and or memory) and resort to the probabilistic test if self</div><div>is greater than the bigger in the list.</div><div><br></div><div>
The value of original algorithm is all research and reasoning that went into it from</div><div>Knuth et al. (note the order of growth is log(n), where n is the integer under scrutiny)</div><div>The problem with the new implementation is that it goes thru testing numbers which are</div>
<div>clearly not prime, 5, 15, 25, 35...just to mention multiples of 5.</div><div>It can possibly be faster for small integers hence the above possible</div><div>improvement suggestion...but for the rest it should be thrown away IMHO.</div>
<div><br></div><div>Primality testing is very important for modern electronic communications, i.e. encryption</div><div>and as such it has to be reliable and performant for big integers.</div><div><div><br></div><div>Hope this clarifies</div>
<div>Bye</div><div>Enrico<br>PS: the comment in the code was explicit enough to allow to research for</div><div> the rationale about the algorithm...we should not fix what works (well)</div><div> there are so many other fixes waiting...<br>
<div class="gmail_quote">On Sat, Dec 19, 2009 at 12:56 AM, 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;">
<div class="im">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 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>
</div>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: [^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 of the receiver.<br>
> - renamed Integer >> #isPrime to #isProbablyPrime.<br>
> - added Integer >> #isPrime which is implemented as a deterministic primality test<br>
> - both #isPrime and #isProbablyPrime return false for receivers <= 1 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></div>