[racket] Function composition in Racket

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.

-- 
Jens Axel Søgaard