# [racket] Mutable state vs RAM on fire

 From: Jens Axel Søgaard (jensaxel at soegaard.net) Date: Wed May 2 17:09:02 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]

```I believe the problem is the representation, you have chosen
for polynomials in the first program.

I am interested in hearing if the following representation gives a
better results:

#lang racket
(require (only-in srfi/1 span))

;;;
;;; Dense polynomials 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 (degree p)
(poly-deg p))

(cond [(empty? xs) xs]
[(zero? (car xs)) (remove-leading-zeros (cdr xs))]
[else xs]))

(define (trim-trailing-zeros 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))))])
(+ c1 c2)))])
(poly (coef-length->degree cs) cs))))

(define (poly-mul p1 p2)
(define (sum-same-degree i dcs)
(if (empty? dcs)
'()
(let-values ([(deg-i deg-larger) (span (λ (dc) (= (car dc) i)) dcs)])
(cons (apply + (map cdr 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) (* c1 c2)))]
[dcs (sort dcs < #:key car)]
[cs (sum-same-degree 0 dcs)])
(poly (coef-length->degree cs) cs)))

/Jens Axel

2012/5/2  <joshua at anwu.org>:
>
> Hey all,
>
> Been playing around with some code to multiply polynomials to calculate dice probabilities.
> Is based on a paper by Doron Zeilberger that I read years ago and can't find at the moment.
>
> My first attempt represented polynomials as lists of coefficient/exponent pairs.
> I tried to make it completely functional, with no set! operations.  You can see it here:
>
> https://github.com/TurtleKitty/Dice/blob/2fff16e198cb84d725c786ecc624fb9b9468e778/dice.rkt
>
> It worked, but only to a point.  At 9 or 10 dice, it started blowing up the RAM in my machine.
> I swear I smelled smoke.  It grabbed like 4G and slowed to a crawl.
>
> Knowing that the Perl and Javascript versions of this program can calculate distributions for 300 dice in the space of a heartbeat,
> I rewrote the thing to use vectors instead, and altered the polynomial multiplication function to use (begin) and (vector-set!):
>
> https://github.com/TurtleKitty/Dice/blob/67c2b49707132395f73b43afe111e3904b3898f2/dice.rkt
>
> It too now calculates three hundred dice without breaking a sweat, but... I feel dirty.
> Can anyone recommend a functional approach that won't melt my motherboard?
> I'm considering hashes, since they have the immutable version of hash-set that vectors seem to lack, but I thought I'd ask the experts.
>
>
> Thanks,
> turtlekitty
> (There might be a library for this already. This is more of an exercise for me than a utility.)
> ____________________
>  Racket Users list:
>  http://lists.racket-lang.org/users

--
--
Jens Axel Søgaard

```

 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]