[Cuis-dev] Problems in class Number

[Agustín Sansone]

**

El mar., 8 oct. 2019 a las 23:17, Agustín Sansone (<
agustinsansone7 at gmail.com>) escribió:

> 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 (<
> cuis-dev at lists.cuis.st>) 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
>> www.cuis-smalltalk.org
>> https://github.com/Cuis-Smalltalk/Cuis-Smalltalk-Dev
>> https://github.com/jvuletich
>> https://www.linkedin.com/in/juan-vuletich-75611b3
>> @JuanVuletich
>>
>> --
>> Cuis-dev mailing list
>> Cuis-dev at lists.cuis.st
>> https://lists.cuis.st/mailman/listinfo/cuis-dev
>>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.cuis.st/mailman/archives/cuis-dev/attachments/20191008/29e675e2/attachment-0001.htm>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: Integer-isPrimeFast.st
Type: application/octet-stream
Size: 918 bytes
Desc: not available
URL: <http://lists.cuis.st/mailman/archives/cuis-dev/attachments/20191008/29e675e2/attachment-0001.obj>