<div dir="ltr">Okay, this should work faster.</div> <div class="gmail_quote"><div dir="ltr" class="gmail_attr">El mié., 9 oct. 2019 a las 1:22, Andres Valloud via Cuis-dev (<<a href="mailto:cuis-dev@lists.cuis.st">cuis-dev@lists.cuis.st</a>>) escribió: </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">In the larger slicer test, slicer := 1024. thickness := 255. maxK := 1 bitShift: 32. integers := 1 to: maxK by: maxK // slicer :: inject: OrderedCollection new into: [:t :x | t add: x. thickness timesRepeat: [t add: t last + 1]. t yourself] :: asArray. Time millisecondsToRun: [1 to: integers size do: [:x | (integers at: x) isPrimeFast2e]] I get 2627 vs 2430, or about 7.5% faster. On 10/8/19 21:19, Andres Valloud via Cuis-dev wrote: > "The latest code you sent" > Time millisecondsToRun: > [10000 timesRepeat: [1 to: 1000 do: [:x | x isPrimeFast1b]]] 767 > > "The code from my last email" > Time millisecondsToRun: > [10000 timesRepeat: [1 to: 1000 do: [:x | x isPrimeFast2e]]] 704 > > The observation is that the boundary of 31 is arbitrary, so we might as > well tune it according to the break even point. > > On 10/8/19 21:11, Agustín Sansone via Cuis-dev wrote: >> I don't think there will be any difference by making optimizations for >> small numbers. This runs just as fast as the original approach. >> >> El mié., 9 oct. 2019 a las 1:01, Andres Valloud via Cuis-dev >> (<<a href="mailto:cuis-dev@lists.cuis.st" target="_blank">cuis-dev@lists.cuis.st</a> <mailto:<a href="mailto:cuis-dev@lists.cuis.st" target="_blank">cuis-dev@lists.cuis.st</a>>>) escribió: >> >> Expanding on the idea to treat tiny integers as special cases, >> approximating sqrtFloor for tiny integers wins. >> >> On 10/8/19 20:49, Andres Valloud via Cuis-dev wrote: >> > See attached hybrid. >> > >> > On 10/8/19 20:44, Andres Valloud via Cuis-dev wrote: >> >> Right, that won't work. I had tried to avoid doing something >> like this, >> >> >> >> | mod30Index | >> >> self < 3 ifTrue: [^self = 2]. >> >> self < 32 ifTrue: [ >> >> ^#(false true true false true false true false false >> false >> >> true false true false false false true false true >> false >> >> false false true false false false false false true >> false >> >> true) at: self]. >> >> mod30Index := self \\ 30 + 1. >> >> #(false true false false false false false true false false >> >> false true false true false false false true false true >> >> false false false true false false false false false >> true) >> >> at: mod30Index :: ifFalse: [^false]. >> >> >> >> >> >> but alas it's not as simple as I thought. >> >> >> >> Andres. >> >> >> >> On 10/8/19 20:40, Agustín Sansone via Cuis-dev wrote: >> >>> Sorry, I think this does not work for the numbers 3, 5, 7, >> 11, 13, >> >>> 17, 19, 23, 29 and 31. >> >>> >> >>> El mié., 9 oct. 2019 a las 0:34, Andres Valloud via Cuis-dev >> >>> (<<a href="mailto:cuis-dev@lists.cuis.st" target="_blank">cuis-dev@lists.cuis.st</a> <mailto:<a href="mailto:cuis-dev@lists.cuis.st" target="_blank">cuis-dev@lists.cuis.st</a>> >> <mailto:<a href="mailto:cuis-dev@lists.cuis.st" target="_blank">cuis-dev@lists.cuis.st</a> <mailto:<a href="mailto:cuis-dev@lists.cuis.st" target="_blank">cuis-dev@lists.cuis.st</a>>>>) >> escribió: >> >>> >> >>> I played a bit with the guard clauses and found the >> attached one is >> >>> simpler yet just as fast. >> >>> >> >>> On 10/8/19 20:11, Andres Valloud via Cuis-dev wrote: >> >>> > Regarding each+31, sure, 30*k+1 comes first, except when >> k = 0 >> >>> because >> >>> > why would anyone try dividing by 1. So this is why that >> case is >> >>> shifted >> >>> > by 30. However, when written this way, the actual >> divisor >> >>> evaluation >> >>> > order is 31, 7, 11, and so on. It's more likely that a >> random >> >>> integer >> >>> > is 0 mod 7 than 0 mod 31, and the sooner one detects >> exact >> >>> division, the >> >>> > sooner the computation can stop. Because of that, I >> think the >> >>> each+31 >> >>> > case should be the last one in the division loop. >> >>> > >> >>> > On 10/8/19 19:17, Agustín Sansone via Cuis-dev wrote: >> >>> >> Hello! >> >>> >> >> >>> >> I agree with you. I don't think isPrime should send >> >>> isProbablyPrime >> >>> >> because it could fail in the future. >> >>> >> I leave you here the implementation with this >> taken care of. >> >>> >> I wrote the (each+31) case first in the trial division >> loop, >> >>> because >> >>> >> it is testing the 30*k+1 case, wich I also wrote first >> in the >> >>> comment. >> >>> >> >> >>> >> Thanks, >> >>> >> Agustín >> >>> >> >> >>> >> El mar., 8 oct. 2019 a las 8:11, Juan Vuletich via >> Cuis-dev >> >>> >> (<<a href="mailto:cuis-dev@lists.cuis.st" target="_blank">cuis-dev@lists.cuis.st</a> >> <mailto:<a href="mailto:cuis-dev@lists.cuis.st" target="_blank">cuis-dev@lists.cuis.st</a>> <mailto:<a href="mailto:cuis-dev@lists.cuis.st" target="_blank">cuis-dev@lists.cuis.st</a> >> <mailto:<a href="mailto:cuis-dev@lists.cuis.st" target="_blank">cuis-dev@lists.cuis.st</a>>> >> >>> <mailto:<a href="mailto:cuis-dev@lists.cuis.st" target="_blank">cuis-dev@lists.cuis.st</a> >> <mailto:<a href="mailto:cuis-dev@lists.cuis.st" target="_blank">cuis-dev@lists.cuis.st</a>> <mailto:<a href="mailto:cuis-dev@lists.cuis.st" target="_blank">cuis-dev@lists.cuis.st</a> >> <mailto:<a href="mailto:cuis-dev@lists.cuis.st" target="_blank">cuis-dev@lists.cuis.st</a>>>>>) >> >>> escribió: >> >>> >> >> >>> >> Hi Folks, >> >>> >> >> >>> >> I agree with Andrés comments, and will just >> focusing on the >> >>> proposed >> >>> >> changes. >> >>> >> (snip) >> >>> >> >> >>> >> On 10/8/2019 2:20 AM, Andres Valloud via Cuis-dev >> wrote: >> >>> >> > Agustin, nice to see someone looking into these >> kinds of >> >>> things >> >>> >> :). >> >>> >> > ... >> >>> >> >> * The *raisedToInteger: exp modulo: m >> *method**in >> >>> Integer has >> >>> >> a very >> >>> >> >> big problem. If we compute, for example, /"5 >> >>> raisedTo: 0 >> >>> >> modulo: >> >>> >> >> 0"/, this returns 1. This means, that >> according to >> >>> >> Smalltalk, the >> >>> >> >> rest of the division by 0 of 1(=5^0) is >> equal to >> >>> 1 (Yes, >> >>> >> division by >> >>> >> >> zero!!). I think you can see the problem. >> This is >> >>> due the >> >>> >> first line >> >>> >> >> of the method, that says /"(exp = 0) >> ifTrue: [^ >> >>> 1].", /does >> >>> >> >> not check anything else. This problem can >> be easily >> >>> fixed by >> >>> >> >> checking if m=0 just before. >> >>> >> > >> >>> >> > I agree, the current code appears to be >> wrong. The >> >>> initials on >> >>> >> the >> >>> >> > code belong to Juan Vuletich and Nicolas >> Cellier. Guys, >> >>> is there >> >>> >> > reason why e.g. 5 raisedTo: 0 modulo: 0 should >> answer 1 >> >>> rather >> >>> >> than >> >>> >> > fail? I don't see any, but... >> >>> >> > >> >>> >> > Assuming the code is broken and needs to be >> fixed, >> >>> >> alternatively one >> >>> >> > could also write the initial guard clause like >> this: >> >>> >> > >> >>> >> > n = 0 ifTrue: [^1 \\ m]. >> >>> >> > >> >>> >> > because the case m = 0 will fail. >> >>> >> > ... >> >>> >> >> >>> >> Just added this suggestion as an update to GitHub. >> Andrés, I >> >>> did it >> >>> >> with >> >>> >> your author initials, it's your code! >> >>> >> >> >>> >> > ... >> >>> >> >> * The *isPrime *method in Integer makes some >> >>> optimization in >> >>> >> order to >> >>> >> >> run the algorithm in O(sqrt(self)) instead >> of the >> >>> naive >> >>> >> way in >> >>> >> >> O(self). This is very intelligent, but the >> constant >> >>> factor >> >>> >> of this >> >>> >> >> method can be still improved significantly. >> I share >> >>> with >> >>> >> you my >> >>> >> >> implementation of *isPrimeFast *with a small >> >>> explanation. >> >>> >> This >> >>> >> >> implementation runs in general more than 3 >> times >> >>> faster >> >>> >> than the >> >>> >> >> actual one. I leave you a test that >> checks the >> >>> correctness >> >>> >> of it as >> >>> >> >> well, and some other tests that check this >> >>> complexity I >> >>> >> mentioned. >> >>> >> > >> >>> >> > I see what you did there, but I do not know >> how to >> >>> reproduce the >> >>> >> time >> >>> >> > tests you mention. I built a sample of integers >> between >> >>> 1 and >> >>> >> 2^32 (I >> >>> >> > didn't go up to 2^64 because that would require >> O(2^32) >> >>> operations >> >>> >> > each, and I want that to finish in reasonable >> time), and >> >>> I get >> >>> >> > something like a 2x performance improvement >> rather than >> >>> 3x. This >> >>> >> > seems to make sense because the approach you >> propose >> >>> halves the \\ >> >>> >> > operations (8 remain out of the 16 the current >> code is >> >>> doing, for >> >>> >> > every batch of 30 potential divisors). >> >>> >> > >> >>> >> > slicer := 1024. >> >>> >> > thickness := 255. >> >>> >> > maxK := 1 bitShift: 32. >> >>> >> > integers := 1 to: maxK by: maxK // slicer >> >>> >> > :: inject: OrderedCollection new >> >>> >> > into: [:t :x | >> >>> >> > t add: x. >> >>> >> > thickness timesRepeat: [t add: t >> last + 1]. >> >>> >> > t yourself] >> >>> >> > :: asArray. >> >>> >> > Time millisecondsToRun: >> >>> >> > [1 to: integers size do: >> >>> >> > [:x | (integers at: x) isPrime]] >> >>> >> > >> >>> >> > Using the above code (which I could not format >> more >> >>> nicely in this >> >>> >> > email), I get about 4.8s for isPrime, and about >> 2.4s for >> >>> >> isPrimeFast. >> >>> >> > >> >>> >> > Generally, isPrime shouldn't send >> isProbablyPrime because >> >>> >> isPrime is >> >>> >> > meant to be deterministic, and one shouldn't >> assume >> >>> that the >> >>> >> > probabilistic algorithm today will happen to >> provide the >> >>> correct >> >>> >> > deterministic answer tomorrow. >> >>> >> > >> >>> >> > Why is the (each+31) case first in the trial >> division >> >>> loop? >> >>> >> > >> >>> >> > Andres. >> >>> >> >> >>> >> I'll wait for your consensus on what to do here. >> Making >> >>> isPrime not >> >>> >> send >> >>> >> isProbablyPrime sounds reasonable to me, but folks, >> I prefer >> >>> to wait >> >>> >> for >> >>> >> your suggestion. >> >>> >> >> >>> >> Thanks, >> >>> >> >> >>> >> -- Juan Vuletich >> >>> >> <a href="http://www.cuis-smalltalk.org" rel="noreferrer" target="_blank">www.cuis-smalltalk.org</a> <<a href="http://www.cuis-smalltalk.org" rel="noreferrer" target="_blank">http://www.cuis-smalltalk.org</a>> >> <<a href="http://www.cuis-smalltalk.org" rel="noreferrer" target="_blank">http://www.cuis-smalltalk.org</a>> >> >>> <<a href="http://www.cuis-smalltalk.org" rel="noreferrer" target="_blank">http://www.cuis-smalltalk.org</a>> >> >>> >> <a href="https://github.com/Cuis-Smalltalk/Cuis-Smalltalk-Dev" rel="noreferrer" target="_blank">https://github.com/Cuis-Smalltalk/Cuis-Smalltalk-Dev</a> >> >>> >> <a href="https://github.com/jvuletich" rel="noreferrer" target="_blank">https://github.com/jvuletich</a> >> >>> >> <a href="https://www.linkedin.com/in/juan-vuletich-75611b3" rel="noreferrer" target="_blank">https://www.linkedin.com/in/juan-vuletich-75611b3</a> >> >>> >> @JuanVuletich >> >>> >> >> >>> >> -- Cuis-dev mailing list >> >>> >> <a href="mailto:Cuis-dev@lists.cuis.st" target="_blank">Cuis-dev@lists.cuis.st</a> <mailto:<a href="mailto:Cuis-dev@lists.cuis.st" target="_blank">Cuis-dev@lists.cuis.st</a>> >> <mailto:<a href="mailto:Cuis-dev@lists.cuis.st" target="_blank">Cuis-dev@lists.cuis.st</a> <mailto:<a href="mailto:Cuis-dev@lists.cuis.st" target="_blank">Cuis-dev@lists.cuis.st</a>>> >> >>> <mailto:<a href="mailto:Cuis-dev@lists.cuis.st" target="_blank">Cuis-dev@lists.cuis.st</a> >> <mailto:<a href="mailto:Cuis-dev@lists.cuis.st" target="_blank">Cuis-dev@lists.cuis.st</a>> <mailto:<a href="mailto:Cuis-dev@lists.cuis.st" target="_blank">Cuis-dev@lists.cuis.st</a> >> <mailto:<a href="mailto:Cuis-dev@lists.cuis.st" target="_blank">Cuis-dev@lists.cuis.st</a>>>> >> >>> >> <a href="https://lists.cuis.st/mailman/listinfo/cuis-dev" rel="noreferrer" target="_blank">https://lists.cuis.st/mailman/listinfo/cuis-dev</a> >> >>> >> >> >>> >> >> >>> -- Cuis-dev mailing list >> >>> <a href="mailto:Cuis-dev@lists.cuis.st" target="_blank">Cuis-dev@lists.cuis.st</a> <mailto:<a href="mailto:Cuis-dev@lists.cuis.st" target="_blank">Cuis-dev@lists.cuis.st</a>> >> <mailto:<a href="mailto:Cuis-dev@lists.cuis.st" target="_blank">Cuis-dev@lists.cuis.st</a> <mailto:<a href="mailto:Cuis-dev@lists.cuis.st" target="_blank">Cuis-dev@lists.cuis.st</a>>> >> >>> <a href="https://lists.cuis.st/mailman/listinfo/cuis-dev" rel="noreferrer" target="_blank">https://lists.cuis.st/mailman/listinfo/cuis-dev</a> >> >>> >> >>> >> > >> -- Cuis-dev mailing list >> <a href="mailto:Cuis-dev@lists.cuis.st" target="_blank">Cuis-dev@lists.cuis.st</a> <mailto:<a href="mailto:Cuis-dev@lists.cuis.st" target="_blank">Cuis-dev@lists.cuis.st</a>> >> <a href="https://lists.cuis.st/mailman/listinfo/cuis-dev" rel="noreferrer" target="_blank">https://lists.cuis.st/mailman/listinfo/cuis-dev</a> >> >> -- Cuis-dev mailing list <a href="mailto:Cuis-dev@lists.cuis.st" target="_blank">Cuis-dev@lists.cuis.st</a> <a href="https://lists.cuis.st/mailman/listinfo/cuis-dev" rel="noreferrer" target="_blank">https://lists.cuis.st/mailman/listinfo/cuis-dev</a> </blockquote></div>