Name: Anonymous 2013-01-20 22:03
because why? because lel
(define (rverse lis acc)
(if (null? lis)
acc
(rverse (cdr lis) (cons (car lis) acc))))
;; A polynomial is a list of coefficients, from power zero to the highest power.
;; (list 1 2 3 4) represents f(x) = 1 + 2x + 3x^2 + 4x^3
(define poly-zero '())
(define poly-one '(1))
(define (poly-eval poly x)
(let loop ((poly poly) (xn 1.0) (acc 0))
(if (null? poly)
acc
(loop (cdr poly) (* xn x) (+ (* xn (car poly)) acc)))))
(define (poly-scale poly t)
(map (lambda (c) (* c t)) poly))
(define (poly-add poly1 poly2)
(let loop ((poly1 poly1) (poly2 poly2) (acc '()))
(cond ((null? poly1) (rverse acc poly2))
((null? poly2) (rverse acc poly1))
(else (loop (cdr poly1) (cdr poly2) (cons (apply + (map car (list poly1 poly2))) acc))))))
(define (poly-sub poly1 poly2)
(poly-add poly1 (poly-scale poly2 -1.0)))
(define (poly-shift poly n)
(if (= n 0)
poly
(poly-shift (cons 0 poly) (- n 1))))
(define (poly-multiply-term term-c term-power poly)
(poly-shift (poly-scale poly term-c) term-power))
(define (poly-mul poly1 poly2)
(let loop ((poly2 poly2) (term-power 0) (acc poly-zero))
(if (null? poly2)
acc
(loop (cdr poly2) (+ term-power 1) (poly-add acc (poly-multiply-term (car poly2) term-power poly1))))))
(define (poly-square poly)
(poly-mul poly poly))
(define (poly-expt poly n)
(cond ((= n 0) poly-one)
((= n 1) poly)
((even? n) (poly-expt (poly-square poly) (/ n 2)))
(else (poly-mul poly (poly-expt poly (- n 1))))))
(define (poly-compose-term term-c term-power poly)
(poly-scale (poly-expt poly term-power) term-c))
(define (poly-compose poly1 poly2)
(let loop ((poly1 poly1) (term-power 0) (acc poly-zero))
(if (null? poly1)
acc
(loop (cdr poly1) (+ 1 term-power) (poly-add acc (poly-compose-term (car poly1) term-power poly2))))))
(define (poly-compose poly1 poly2)
(let loop ((poly1 poly1) (poly2n poly-one) (acc poly-zero))
(if (null? poly1)
acc
(loop (cdr poly1) (poly-mul poly2n poly2) (poly-add (poly-scale poly2n (car poly1)) acc)))))