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