Hi,<div>I just reply with the words of SICP, footnote 47 in the link below:</div><div><span class="Apple-style-span" style="font-family: 'Times New Roman'; font-size: 12px; ">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 <a name="%_idx_914"></a>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 <a name="%_idx_916"></a><a name="%_idx_918"></a>mathematics and engineering.</span><br>
<br></div><div>Bye</div><div>Enrico</div><div><br><div class="gmail_quote">On Thu, Dec 24, 2009 at 9:51 PM, Andres Valloud <span dir="ltr"><<a href="mailto:avalloud@smalltalk.comcastbiz.net">avalloud@smalltalk.comcastbiz.net</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">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.<br>
<br>
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).<br>
<br>
If anything, I'd rename isProbablyPrime to something like probabilisticPrimalityTestAlgorithmSuch.<br><font color="#888888">
<br>
Andres.</font><div class="im"><br>
<br>
On 12/19/2009 5:58 AM, Enrico Spinielli wrote:<br>
</div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div class="im">
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<br>
the wrong<br>
information about its input. This is less than one chance in a<br>
quadrillion; [...]<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<br>
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<br>
better one as well)<br>
you can also see "1.2.6 Example: Testing for Primality<br></div><div class="im">
<<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></div><div><div></div><div class="h5">
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<br>
into 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<br>
numbers 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<br>
communications, 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 <<a href="mailto:lewis@mail.msen.com" target="_blank">lewis@mail.msen.com</a><br></div></div><div><div></div><div class="h5">
<mailto:<a href="mailto:lewis@mail.msen.com" target="_blank">lewis@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<br>
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<br>
starting<br>
> from 3<br>
> and (correctly) stopping at self sqrtFloor.<br>
> This is IMHO a questionable/useless "improvement", not even<br>
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>
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)<br>
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<br>
square root of the receiver.<br>
> - renamed Integer >> #isPrime to #isProbablyPrime.<br>
> - added Integer >> #isPrime which is implemented as a<br>
deterministic primality test<br>
> - both #isPrime and #isProbablyPrime return false for receivers<br>
<= 1 instead of raising an error<br>
<br>
Is this a reasonable change?<br>
<br>
Dave<br>
<br>
<br>
<br>
<br>
<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></blockquote>
<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>