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