[racket] Function composition in Racket

I suppose I'm just stating the obvious here, but R[x, y] is naturally isomorphic to R[x][y]. That is, polynomials in x and y over the ring R have a natural interpretation as polynomials in y over the ring R[x] of polynomials over R. So, if you had a good library for working with polynomials (of one variable) you could just evaluate p(a, b) by evaluating Horner's rule twice. 

Sent from my iPhone

On Oct 15, 2012, at 10:15 AM, Neil Toronto <neil.toronto at gmail.com> wrote:

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