[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)))