# [racket] Function composition in Racket

What degree of polynomial, I wonder, would it take to find a
noticeable difference between these?
On Mon, Oct 15, 2012 at 9:57 AM, Stephen Bloch <bloch at adelphi.edu> wrote:
>*
*>* On Oct 15, 2012, at 10:44 AM, Justin R. Slepak wrote:
*>*
*>>* Ah, I forgot about for/sum. This version is probably clearer:
*>>*
*>>* (struct polynomial (coeffs)
*>>* #:transparent
*>>* #:property prop:procedure
*>>* (lambda (poly num)
*>>* (for/sum ([x (length (polynomial-coeffs poly))]
*>>* [c (polynomial-coeffs poly)])
*>>* (* c (expt num x)))))
*>*
*>* 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))))
*>*
*>*
*>*
*>* Stephen Bloch
*>* sbloch at adelphi.edu
*>*
*>*
*>* ____________________
*>* Racket Users list:
*>* http://lists.racket-lang.org/users
*