[Cuis-dev] Problems in class Number
Agustín Sansone
agustinsansone7 at gmail.com
Tue Oct 8 21:44:20 PDT 2019
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>) 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>>) 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>>>)
> >> 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>>>>)
> >> >>> 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>
> >> >>> >> 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>>>
> >> >>> >> 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/522a6c71/attachment-0001.htm>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: Integer-isPrimeFast.st
Type: application/octet-stream
Size: 3131 bytes
Desc: not available
URL: <http://lists.cuis.st/mailman/archives/cuis-dev/attachments/20191009/522a6c71/attachment-0001.obj>
More information about the Cuis-dev
mailing list