On 10/15/2012 11:49 AM, Jens Axel Søgaard wrote:
2012/10/15 Stephen Bloch <[email protected]>:
But probably slower, at least for exact numbers. If "expt" were implemented naively as "for i
= 1 to num", the total number of multiplications would be quadratic in degree; if it were implemented by
repeated squaring, the total number of multiplications would be O(n log(n)); with Horner's algorithm or your
"values" approach, it's linear.
Horner's algorithm gives us
(lambda (poly x)
(for/fold ([sum 0])
([c (polynomial-coeffs poly)])
(+ c (* sum x))))
If I recall correctly, Horner's algorithm also gives more precise results,
when used with pseudo real numbers.
Especially true when coefficients alternate signs, producing massive
cancellation. That's the main reason to use it, since floating-point
exponentiation runs in constant time. (It's also a tad faster, requiring
at least 1-2 fewer flops per coefficient... but probably many more,
because hardware `pow' is usually broken for non-rational inputs and
implementations have to work around that.)
What I'd really like, by the time the math library has polynomials, is a
Horner-like algorithm for sparse polynomials of the form
c0 + ... + cn * x^(i_n) * y^(j_n) + ...
The sequence of (i_n,j_n) can only be partially ordered, which makes it
tricky.
Neil ⊥
____________________
Racket Users list:
http://lists.racket-lang.org/users
