# [racket] Mutable state vs RAM on fire

 From: Jens Axel Søgaard (jensaxel at soegaard.net) Date: Thu May 3 06:00:39 EDT 2012 Previous message: [racket] Mutable state vs RAM on fire Next message: [racket] Mutable state vs RAM on fire Messages sorted by: [date] [thread] [subject] [author]

```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

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

(if (< (degree p1) (degree p2))
(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)))

```

 Posted on the users mailing list. Previous message: [racket] Mutable state vs RAM on fire Next message: [racket] Mutable state vs RAM on fire Messages sorted by: [date] [thread] [subject] [author]