<div dir="ltr">Hello!<div> </div><div>I agree with you. I don't think isPrime should send isProbablyPrime because it could fail in the future.</div><div>I leave you here the implementation with this taken care of.</div><div>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. </div><div> </div><div>Thanks,</div><div>Agustín</div></div> <div class="gmail_quote"><div dir="ltr" class="gmail_attr">El mar., 8 oct. 2019 a las 8:11, Juan Vuletich 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">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="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> <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>