# [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
*