[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