2012/10/15 Stephen Bloch <bl...@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 ____________________ Racket Users list: http://lists.racket-lang.org/users
