[Cuis-dev] Problems in class Number
Andres Valloud
ten at smallinteger.com
Wed Oct 9 22:30:12 PDT 2019
Yeah, looking at potential divisors mod 2310 seems excessive. Besides,
the sqrt algorithm is great for relatively small integers, and yet
O(sqrt(n)) is just inadequate for larger (and thus more interesting)
integers. In that regime, one could start with Dixon's method --- but
that absolutely does not belong in Integer>>isPrime.
Here's something really important: doing too much micro-optimization
detracts from the motivation to implement better things. I'd say we
leave things with the round of 30.
On 10/9/19 12:52, Agustín Sansone via Cuis-dev wrote:
> 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 <mailto: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>
> <mailto: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>>
> > <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ó:
> > >>
> > >> 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>>>
> > >> <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ó:
> > >> >>>
> > >> >>> 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>>>>
> > >> >>> <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
> <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>
> > >> >>> <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>>>>
> > >> >>> <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
> <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>>>
> > >> <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
>
>
More information about the Cuis-dev
mailing list