[squeak-dev] The Trunk: Collections-ul.450.mcz

Enrico Spinielli enrico.spinielli at googlemail.com
Wed Aug 3 23:38:17 UTC 2011


Levente (and all),
what do you think about implementing SequenceableCollection>>polynomialEval:
as follows:

SequenceableCollection>>polynomialEval: thisX
   self reverse inject: 0 into: [:sum :each | thisX * sum + each]


The above version uses Horner's rule [1] and reads simpler IMHO.
Of course reverse is needed only because the convention is to have
the constant term as first in the list, should it be the other way around
we could save a copy of the collection.
(In my image (little more than trunk) there are only 2 senders of
   polynomialEval:
so maybe a change of semantics could be proposed to get rid of reverse...)

Hope it helps
Bye
Enrico

[1] Horner's rule/scheme http://en.wikipedia.org/wiki/Horner_scheme


On Mon, Jul 25, 2011 at 11:21,  <commits at source.squeak.org> wrote:
> Levente Uzonyi uploaded a new version of Collections to project The Trunk:
> http://source.squeak.org/trunk/Collections-ul.450.mcz
>
> ==================== Summary ====================
>
> Name: Collections-ul.450
> Author: ul
> Time: 25 July 2011, 1:37:20.234 am
> UUID: 2d09bd44-bfdf-1840-87cb-81ced69f9948
> Ancestors: Collections-nice.449
>
> Avoid a multiplication, use low level methods in
> SequenceableCollection >> #polynomialEval: for better performance.
>
> =============== Diff against Collections-nice.449 ===============
>
> Item was changed:
>  ----- Method: SequenceableCollection>>polynomialEval: (in category 'enumerating') -----
>  polynomialEval: thisX
> -       | sum valToPower |
>        "Treat myself as the coeficients of a polynomial in X.  Evaluate it with thisX.  First element is the constant and last is the coeficient for the highest power."
>        "  #(1 2 3) polynomialEval: 2   "   "is 3*X^2 + 2*X + 1 with X = 2"
>
> +       | size sum valToPower |
> +       sum := self at: 1.
> +       (size := self size) = 1 ifTrue: [ ^sum ].
> -       sum := self first.
>        valToPower := thisX.
> +       2 to: size - 1 do: [ :ind |
> -       2 to: self size do: [:ind |
>                sum := sum + ((self at: ind) * valToPower).
> +               valToPower := valToPower * thisX ].
> +       ^sum + ((self at: size) * valToPower)!
> -               valToPower := valToPower * thisX].
> -       ^ sum!
>
>
>



-- 
Enrico Spinielli
"Do Androids dream of electric sheep?"— Philip K. Dick
"Hear and forget; see and remember;do and understand."—Mitchel Resnick



More information about the Squeak-dev mailing list