[squeak-dev] The Trunk: Collections-ul.450.mcz
leves at elte.hu
Thu Aug 4 00:54:23 UTC 2011
It's funny (or sad) that I didn't realize this method is not using
Horner's scheme... But noone else did, before you. :)
The reason I rewrote this code is to improve it's performance,
which seemed to be affecting DrGeoII's rendering (even if only a tiny
bit), so performance is important here.
I don't really like #revese here, because it creates a copy, neither
#inject:into:, because it's a bit too high level.
So, I came up with the following:
| index sum |
sum := self at: (index := self size).
[ (index := index - 1) >= 1 ] whileTrue: [
sum := sum * thisX + (self at: index) ].
Five lines instead of one, but it's still simple and fast (5.64x faster
than your nice and simple version, and 1.29x faster than the previous
implementation for a polynomial degree of 8).
Not using #inject:into: also allows us to keep the semantics.
On Thu, 4 Aug 2011, Enrico Spinielli wrote:
> 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  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
> so maybe a change of semantics could be proposed to get rid of reverse...)
> Hope it helps
>  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:
>> ==================== 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