Nicolas,<div>Thanks.<div>by the way why do I see "dirty" packages even if I did not touch them?</div><div><br></div><div>For a little contribution I want to post </div><div><blockquote class="webkit-indent-blockquote" style="margin: 0 0 0 40px; border: none; padding: 0px;">
HTTPSocket>>httpGetDocument:args:accept:request:</blockquote></div><div>I see hundreds of changes when I select 'Changes' in Monticello Browser</div><div>after step 4) below</div><div><br></div><div>Thanks in advance for your feedback (and eventually sorry if the question is silly)</div>
<div>Bye</div><div>Enrico<br><br><div class="gmail_quote">On Sun, Jan 24, 2010 at 4:10 PM, Nicolas Cellier <span dir="ltr"><<a href="mailto:nicolas.cellier.aka.nice@gmail.com">nicolas.cellier.aka.nice@gmail.com</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">2010/1/24 Enrico Spinielli <<a href="mailto:enrico.spinielli@googlemail.com">enrico.spinielli@googlemail.com</a>>:<br>
<div class="im">> No need to thank me, I just enjoyed to implement an algorithm in Squeak and<br>
> signed for MIT license:<br>
> so use/abuse/misuse/... freely.<br>
> We all have to thank you and the others for looking after contributions and<br>
> make them available<br>
> in Trunk or images.<br>
> I think that what Levente discovered from<br>
> DigitalSignatureAlgorithm>>isProbablyPrime:<br>
> is worth some thoughts in terms of cleanup and rationalisation...from the<br>
> version info this<br>
> piece of code seems to precede mine...and confirm the need of primality<br>
> testing for encryption<br>
> (hence big integers)<br>
> Bye<br>
> Enrico<br>
> PS: I tried to see how to contribute, i.e. in the inbox but did not find too<br>
> much of instructions<br>
> (something in Squeak board blog but not too clear for me at least). Any<br>
> suggestion? URL?<br>
><br>
<br>
</div>The preferred way:<br>
1) make your changes to the image<br>
2) open a Monticello browser,<br>
3) select one dirty packages in left pane (marked with *)<br>
presumably, it's Kernel here.<br>
4) select <a href="http://source.squeak.org/inbox" target="_blank">http://source.squeak.org/inbox</a> in right pane<br>
5) press save button<br>
6) repeat step 3 for each dirty package<br>
7) post a message to this list indicating which set of .mcz solves which problem<br>
<br>
If <a href="http://source.squeak.org/inbox" target="_blank">http://source.squeak.org/inbox</a> does not appear for a specific package:<br>
a) unselect package in left pane<br>
b) select <a href="http://source.squeak.org/inbox" target="_blank">http://source.squeak.org/inbox</a> in right pane<br>
c) choose pop up menu option 'add to package...'<br>
d) go to step 3<br>
<br>
Hope I did not forget anything; maybe ask for a free beer to next<br>
Squeak smalltalk event ?<br>
<br>
cheers<br>
<font color="#888888"><br>
Nicolas<br>
</font><div><div></div><div class="h5"><br>
> On Sat, Jan 23, 2010 at 9:51 PM, David T. Lewis <<a href="mailto:lewis@mail.msen.com">lewis@mail.msen.com</a>> wrote:<br>
>><br>
>> 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<br>
>> 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<br>
>> maxVal) do: [:e | e isPrime]]. ==> 120<br>
>> Time millisecondsToRun: [(SmallInteger maxVal - count to: SmallInteger<br>
>> maxVal) do: [:e | e isProbablyPrime]]. ==> 984<br>
>><br>
>> "LargePositiveInteger values just above SmallInteger maxVal"<br>
>> Time millisecondsToRun: [(largeMin to: largeMin + count) do: [:e | e<br>
>> isPrime]]. ==> 6599<br>
>> Time millisecondsToRun: [(largeMin to: largeMin + count) do: [:e | e<br>
>> 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<br>
>> 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<br>
>> implementation that<br>
>> is much faster for large integers, and that is correct to an<br>
>> 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<br>
>> > 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<br>
>> > wrong<br>
>> > information about its input. This is less than one chance in a<br>
>> > 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<br>
>> > 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<br>
>> > one as well)<br>
>> > you can also see "1.2.6 Example: Testing for<br>
>> ><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<br>
>> > 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<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<br>
>> > 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<br>
>> > 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<br>
>> > <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<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 looking<br>
>> > > > 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)<br>
>> > > 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<br>
>> > > > 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>
><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>
><br>
><br>
><br>
><br>
<br>
</div></div></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>