# [racket] Function composition in Racket

 From: Neil Toronto (neil.toronto at gmail.com) Date: Mon Oct 15 13:15:50 EDT 2012 Previous message: [racket] Function composition in Racket Next message: [racket] Function composition in Racket Messages sorted by: [date] [thread] [subject] [author]

```On 10/15/2012 11:49 AM, Jens Axel Søgaard wrote:
> 2012/10/15 Stephen Bloch <bloch at 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.

Especially true when coefficients alternate signs, producing massive
cancellation. That's the main reason to use it, since floating-point
exponentiation runs in constant time. (It's also a tad faster, requiring
at least 1-2 fewer flops per coefficient... but probably many more,
because hardware `pow' is usually broken for non-rational inputs and
implementations have to work around that.)

What I'd really like, by the time the math library has polynomials, is a
Horner-like algorithm for sparse polynomials of the form

c0 + ... + cn * x^(i_n) * y^(j_n) + ...

The sequence of (i_n,j_n) can only be partially ordered, which makes it
tricky.

Neil ⊥

```

 Posted on the users mailing list. Previous message: [racket] Function composition in Racket Next message: [racket] Function composition in Racket Messages sorted by: [date] [thread] [subject] [author]