[Cuis-dev] Problems in class Number
Agustín Sansone
agustinsansone7 at gmail.com
Wed Oct 9 19:18:47 PDT 2019
Sorry, I forgot a case. This version works fine.
El mié., 9 oct. 2019 a las 17:03, Agustín Sansone (<
agustinsansone7 at gmail.com>) escribió:
> **
>
> 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/ea6e88ac/attachment-0001.htm>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: Integer-isPrimeFast.st
Type: application/octet-stream
Size: 3078 bytes
Desc: not available
URL: <http://lists.cuis.st/mailman/archives/cuis-dev/attachments/20191009/ea6e88ac/attachment-0001.obj>
More information about the Cuis-dev
mailing list