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
[email protected]
____________________
Racket Users list:
http://lists.racket-lang.org/users
