[racket] Mutable state vs RAM on fire

2012/5/3 Chris Stephenson <cs at csl.tc>:
> Isn't this just a question of choice of data representation?
>
> Once you drop the explicit powers from the representation and store
> least significant coefficient first, then the racket program becomes
> extremely simple.
>
> One reason Racket goes slower is that it use big ints while perl and
> javascript will both operate mod 2^32. A thousand polynomials multiplied
> together makes for some really *big* ints.

This is a very good point.

I modified my code to represent the coeffecients using floating point numbers.
At the same time I switched to unsafe floating point operations, and
added contracts to prevent disasters.

/Jens Axel

#lang racket
(require (only-in srfi/1 span drop-while)
         racket/unsafe/ops
         (planet williams/science/unsafe-ops-utils))

(provide
 (rename-out [poly-coefs coeffecients])
 (contract-out
  (rename Poly poly (-> fixnum? (listof real?) poly?))
  [poly-add (-> poly? poly? poly?)]
  [poly-mult (-> poly? poly? poly?)]
  [degree (-> poly? number?)]))

;;;
;;; Dense polynomials with floating number coeffecients represented as lists.
;;;

(define-struct poly (deg coefs) #:transparent)
;   deg is the degree
;   coefs is a list of coeffecients.
;   p(x) = sum ci * x^i is represented as (poly n (list c0 c1 ... cn))

(define (Poly d cs)
  (poly d (map real->float cs)))

(define (degree p)
  (poly-deg p))

(define (trim-trailing-zeros xs)
  (reverse (drop-while (λ (x) (unsafe-fl= x 0.0)) (reverse xs))))

(define (coef-length->degree cs)
  (if (empty? cs)
      -inf.0
      (- (length cs) 1)))

(define (poly-add p1 p2)
  (if (< (degree p1) (degree p2))
      (poly-add p2 p1)
      (let* ([cs (trim-trailing-zeros
                  (for/list ([c1 (in-list (poly-coefs p1))]
                             [c2 (in-list (append (poly-coefs p2)
                                                  (build-list (-
(degree p1) (degree p2))
                                                              (λ (i) 0.0))))])
                    (unsafe-fl+ c1 c2)))])
        (poly (coef-length->degree cs) cs))))

(define (poly-mult p1 p2)
  (define (sum-same-degree i dcs)
    (if (empty? dcs)
        '()
        (let-values ([(deg-i deg-larger) (span (λ (dc) (unsafe-fx=
(car dc) i)) dcs)])
          (cons (foldl (λ (p sum) (unsafe-fl+ (cdr p) sum)) 0.0 deg-i)
                (sum-same-degree (+ i 1) deg-larger)))))
  (let* ([dcs
          (for*/list ([(c1 i) (in-indexed (in-list (poly-coefs p1)))]
                      [(c2 j) (in-indexed (in-list (poly-coefs p2)))])
            (cons (+ i j) (unsafe-fl* c1 c2)))]
         [dcs (sort dcs < #:key car)]
         [cs (sum-same-degree 0 dcs)])
    (poly (coef-length->degree cs) cs)))