[Cuis-dev] Problems in class Number
Agustín Sansone
agustinsansone7 at gmail.com
Wed Oct 9 13:03:54 PDT 2019
**
El mié., 9 oct. 2019 a las 16:52, Agustín Sansone (<
agustinsansone7 at gmail.com>) escribió:
> The next step of this idea will be for self of the form 2310*k+{1, 13, 17,
> ..., 2309} (344 cases !!).
> I wouldn't make that step, but it is okay if you want to add any other
> optimization.
> I leave you again the implementation, because there was a redundant check
> in the last one.
> Besides that, I don't see any reason to have a slower implementation of
> isPrime in the base image.
>
> El mié., 9 oct. 2019 a las 2:18, Andres Valloud via Cuis-dev (<
> cuis-dev at lists.cuis.st>) escribió:
>
>> If you are happy with the code, then we can queue it for integration.
>> Is there anything else you'd like to do to isPrime? At one point I
>> thought it might be possible to merge the small factor loop by letting
>> it evaluate even for large receivers (on the grounds that chances are
>> the faster loop that does not send sqrtFloor is likely to find small
>> factors quickly), but if no factor is found then the rounds of 30 could
>> start at 30 or 60. I couldn't quite find a way to do that and make it
>> run faster.
>>
>> On 10/8/19 21:44, Agustín Sansone via Cuis-dev wrote:
>> > Okay, this should work faster.
>> >
>> > El mié., 9 oct. 2019 a las 1:22, Andres Valloud via Cuis-dev
>> > (<cuis-dev at lists.cuis.st <mailto:cuis-dev at lists.cuis.st>>) escribió:
>> >
>> > 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
>> > >> (<cuis-dev at lists.cuis.st <mailto:cuis-dev at lists.cuis.st>
>> > <mailto:cuis-dev at lists.cuis.st <mailto:cuis-dev at lists.cuis.st>>>)
>> > 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
>> > >> >>> (<cuis-dev at lists.cuis.st
>> > <mailto:cuis-dev at lists.cuis.st> <mailto:cuis-dev at lists.cuis.st
>> > <mailto:cuis-dev at lists.cuis.st>>
>> > >> <mailto:cuis-dev at lists.cuis.st
>> > <mailto:cuis-dev at lists.cuis.st> <mailto:cuis-dev at lists.cuis.st
>> > <mailto:cuis-dev at lists.cuis.st>>>>)
>> > >> 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
>> > >> >>> >> (<cuis-dev at lists.cuis.st
>> > <mailto:cuis-dev at lists.cuis.st>
>> > >> <mailto:cuis-dev at lists.cuis.st
>> > <mailto:cuis-dev at lists.cuis.st>> <mailto:cuis-dev at lists.cuis.st
>> > <mailto:cuis-dev at lists.cuis.st>
>> > >> <mailto:cuis-dev at lists.cuis.st <mailto:
>> cuis-dev at lists.cuis.st>>>
>> > >> >>> <mailto:cuis-dev at lists.cuis.st
>> > <mailto:cuis-dev at lists.cuis.st>
>> > >> <mailto:cuis-dev at lists.cuis.st
>> > <mailto:cuis-dev at lists.cuis.st>> <mailto:cuis-dev at lists.cuis.st
>> > <mailto:cuis-dev at lists.cuis.st>
>> > >> <mailto:cuis-dev at lists.cuis.st
>> > <mailto: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
>> > <http://www.cuis-smalltalk.org> <http://www.cuis-smalltalk.org>
>> > >> <http://www.cuis-smalltalk.org>
>> > >> >>> <http://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
>> > <mailto:Cuis-dev at lists.cuis.st> <mailto:Cuis-dev at lists.cuis.st
>> > <mailto:Cuis-dev at lists.cuis.st>>
>> > >> <mailto:Cuis-dev at lists.cuis.st
>> > <mailto:Cuis-dev at lists.cuis.st> <mailto:Cuis-dev at lists.cuis.st
>> > <mailto:Cuis-dev at lists.cuis.st>>>
>> > >> >>> <mailto:Cuis-dev at lists.cuis.st
>> > <mailto:Cuis-dev at lists.cuis.st>
>> > >> <mailto:Cuis-dev at lists.cuis.st
>> > <mailto:Cuis-dev at lists.cuis.st>> <mailto:Cuis-dev at lists.cuis.st
>> > <mailto:Cuis-dev at lists.cuis.st>
>> > >> <mailto:Cuis-dev at lists.cuis.st
>> > <mailto:Cuis-dev at lists.cuis.st>>>>
>> > >> >>> >>
>> https://lists.cuis.st/mailman/listinfo/cuis-dev
>> > >> >>> >>
>> > >> >>> >>
>> > >> >>> -- Cuis-dev mailing list
>> > >> >>> Cuis-dev at lists.cuis.st <mailto:Cuis-dev at lists.cuis.st>
>> > <mailto:Cuis-dev at lists.cuis.st <mailto:Cuis-dev at lists.cuis.st>>
>> > >> <mailto:Cuis-dev at lists.cuis.st
>> > <mailto:Cuis-dev at lists.cuis.st> <mailto:Cuis-dev at lists.cuis.st
>> > <mailto:Cuis-dev at lists.cuis.st>>>
>> > >> >>> https://lists.cuis.st/mailman/listinfo/cuis-dev
>> > >> >>>
>> > >> >>>
>> > >> >
>> > >> -- Cuis-dev mailing list
>> > >> Cuis-dev at lists.cuis.st <mailto:Cuis-dev at lists.cuis.st>
>> > <mailto:Cuis-dev at lists.cuis.st <mailto:Cuis-dev at lists.cuis.st>>
>> > >> https://lists.cuis.st/mailman/listinfo/cuis-dev
>> > >>
>> > >>
>> > --
>> > Cuis-dev mailing list
>> > Cuis-dev at lists.cuis.st <mailto:Cuis-dev at lists.cuis.st>
>> > https://lists.cuis.st/mailman/listinfo/cuis-dev
>> >
>> >
>> --
>> 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/20191009/63e28bde/attachment-0001.htm>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: Integer-isPrimeFast.st
Type: application/octet-stream
Size: 2824 bytes
Desc: not available
URL: <http://lists.cuis.st/mailman/archives/cuis-dev/attachments/20191009/63e28bde/attachment-0001.obj>
More information about the Cuis-dev
mailing list