Re: [squeak-dev] Integer>>isPrime why reverting Knuth's algorithm P (probabilistic primality test) with iteration over division with even numbers?
Locked
Re: [squeak-dev] Integer>>isPrime why reverting Knuth's algorithm P (probabilistic primality test) with iteration over division with even numbers?
 
|
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<<a href="http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.html#%_sec_1.2.6">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 > > > > |
|
|
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? On Sat, Jan 23, 2010 at 9:51 PM, David T. Lewis <[hidden email]> wrote: To follow up on this discussion from last month, I updated Squeak trunk -- Enrico Spinielli "Do Androids dream of electric sheep?"— Philip K. Dick "Hear and forget; see and remember;do and understand."—Mitchel Resnick |
Re: [squeak-dev] Integer>>isPrime why reverting Knuth's algorithm P (probabilistic primality test) with iteration over division with even numbers?
|
|
2010/1/24 Enrico Spinielli <[hidden email]>:
> 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 <[hidden email]> 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<<a href="http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.html#%_sec_1.2.6">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 > > > > |
Re: [squeak-dev] Integer>>isPrime why reverting Knuth's algorithm P (probabilistic primality test) with iteration over division with even numbers?
|
|
2010/1/24 Nicolas Cellier <[hidden email]>:
> 2010/1/24 Enrico Spinielli <[hidden email]>: >> 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 > Ah yes, I forgot, use a relevant version message when saving... >> On Sat, Jan 23, 2010 at 9:51 PM, David T. Lewis <[hidden email]> 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<<a href="http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.html#%_sec_1.2.6">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 >> >> >> >> > |
|
|
In reply to this post by Nicolas Cellier
Nicolas,
Thanks.
by the way why do I see "dirty" packages even if I did not touch them? For a little contribution I want to post HTTPSocket>>httpGetDocument:args:accept:request: I see hundreds of changes when I select 'Changes' in Monticello Browser after step 4) below Thanks in advance for your feedback (and eventually sorry if the question is silly)
Bye Enrico On Sun, Jan 24, 2010 at 4:10 PM, Nicolas Cellier <[hidden email]> wrote: 2010/1/24 Enrico Spinielli <[hidden email]>: -- Enrico Spinielli "Do Androids dream of electric sheep?"— Philip K. Dick "Hear and forget; see and remember;do and understand."—Mitchel Resnick |
Re: [squeak-dev] Integer>>isPrime why reverting Knuth's algorithm P (probabilistic primality test) with iteration over division with even numbers?
|
|
2010/1/25 Enrico Spinielli <[hidden email]>:
> Nicolas, > Thanks. > by the way why do I see "dirty" packages even if I did not touch them? > For a little contribution I want to post > > HTTPSocket>>httpGetDocument:args:accept:request: > > I see hundreds of changes when I select 'Changes' in Monticello Browser > after step 4) below > Thanks in advance for your feedback (and eventually sorry if the question is > silly) > Bye > Enrico > Open a MC browser select a dirty package in left pane, select http://source.squeak.org/trunk in right pane, press button changes You will get a list of changes between you image and latest trunk. Maybe some false positive occur sometimes (mark dirty but not really dirty) In my experience, running some tests tend to mark packages as dirty. >From time to time, the update mechanism produces false positives too. Or you did a lot of work in you image... You should publish only relevant changes (revert the non relevant ones...) Nicolas > On Sun, Jan 24, 2010 at 4:10 PM, Nicolas Cellier > <[hidden email]> wrote: >> >> 2010/1/24 Enrico Spinielli <[hidden email]>: >> > 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 <[hidden email]> >> > 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<<a href="http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.html#%_sec_1.2.6">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 >> > >> > >> > >> > >> > > > > -- > Enrico Spinielli > "Do Androids dream of electric sheep?"— Philip K. Dick > "Hear and forget; see and remember;do and understand."—Mitchel Resnick > > > > |
|
|
Nicolas,
yes, if I compare with the Trunk I only get my changes, but if I continue with step 5) I will end up with a saved version for the Trunk, not the Inbox, won't I? (and be blocked [correctly] because I have no write access)
What's next? Bye Enrico On Mon, Jan 25, 2010 at 12:06 PM, Nicolas Cellier <[hidden email]> wrote: 2010/1/25 Enrico Spinielli <[hidden email]>: -- Enrico Spinielli "Do Androids dream of electric sheep?"— Philip K. Dick "Hear and forget; see and remember;do and understand."—Mitchel Resnick |
Re: [squeak-dev] Integer>>isPrime why reverting Knuth's algorithm P (probabilistic primality test) with iteration over division with even numbers?
|
|
On Mon, Jan 25, 2010 at 12:31:04PM +0100, Enrico Spinielli wrote:
> Nicolas, > yes, if I compare with the Trunk I only get my changes, > but if I continue with step 5) I will end up with a saved version for the > Trunk, not the Inbox, won't I? > (and be blocked [correctly] because I have no write access) > This tells you that your image, relative to Trunk, has just the changes you made (which is good). Your image, relative to whatever is in the inbox, has lots of changes. That is OK, because the inbox probably just has some older save from someone else. You can point to back to Inbox again and save your changes, and all will be well. One more tip: If you are not confident that this is going to work right, you can do the save with a local repository on your own hard drive, such as the package-cache. Then you can use the Monticello browser to copy your new version from your local repository to the Inbox repository. But don't worry too much about it, nothing that you save to the inbox is going to do any harm. Dave |
|
|
Done,
seems my contribution is the only one in 'The Inbox' Bye Enrico
On Mon, Jan 25, 2010 at 12:52 PM, David T. Lewis <[hidden email]> wrote:
-- Enrico Spinielli "Do Androids dream of electric sheep?"— Philip K. Dick "Hear and forget; see and remember;do and understand."—Mitchel Resnick |
Re: [squeak-dev] Integer>>isPrime why reverting Knuth's algorithm P (probabilistic primality test) with iteration over division with even numbers?
|
|
On Mon, 25 Jan 2010, Enrico Spinielli wrote:
> Done, > seems my contribution is the only one in 'The > Inbox<http://source.squeak.org/inbox/> > ' Because the Inbox only contains new contributions. Whenever a contribution is accepted or rejected it's moved to the Treated Inbox (http://source.squeak.org/treated.html ). > > <http://source.squeak.org/inbox/>Will an email automatically sent to > squeak-dev (as it seems to be the case with 'The Trunk')? > No, because that would require the server to look for ancestors in other repositories. Levente > Bye > Enrico > > On Mon, Jan 25, 2010 at 12:52 PM, David T. Lewis <[hidden email]>wrote: > >> On Mon, Jan 25, 2010 at 12:31:04PM +0100, Enrico Spinielli wrote: >>> Nicolas, >>> yes, if I compare with the Trunk I only get my changes, >>> but if I continue with step 5) I will end up with a saved version for the >>> Trunk, not the Inbox, won't I? >>> (and be blocked [correctly] because I have no write access) >>> >> >> This tells you that your image, relative to Trunk, has just the changes >> you made (which is good). Your image, relative to whatever is in the >> inbox, has lots of changes. That is OK, because the inbox probably >> just has some older save from someone else. >> >> You can point to back to Inbox again and save your changes, and all >> will be well. >> >> One more tip: If you are not confident that this is going to work right, >> you can do the save with a local repository on your own hard drive, >> such as the package-cache. Then you can use the Monticello browser to >> copy your new version from your local repository to the Inbox repository. >> But don't worry too much about it, nothing that you save to the inbox >> is going to do any harm. >> >> Dave >> >> >> > > > -- > Enrico Spinielli > "Do Androids dream of electric sheep?"? Philip K. Dick > "Hear and forget; see and remember;do and understand."?Mitchel Resnick > |
«
Return to Squeak - Dev
|
1 view|%1 views
| Free forum by Nabble | Edit this page |