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 <bl...@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 > sbl...@adelphi.edu > > > ____________________ > Racket Users list: > http://lists.racket-lang.org/users ____________________ Racket Users list: http://lists.racket-lang.org/users
