<div dir="ltr">I don't know if one less iteration will make much difference, however I also agree the each+31 case should be the last one.</div> <div class="gmail_quote"><div dir="ltr" class="gmail_attr">El mié., 9 oct. 2019 a las 0:11, Andres Valloud via Cuis-dev (<<a href="mailto:cuis-dev@lists.cuis.st" target="_blank">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">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>>>) 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="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>> > <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>