# [racket] Function composition in Racket

On 10/15/2012 11:49 AM, Jens Axel Søgaard wrote:
>* 2012/10/15 Stephen Bloch <bloch at adelphi.edu>:
*>*
*>>* 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 ⊥