On May 2, 2012, at 3:05 PM, jos...@anwu.org wrote:
>
> 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.
poly-deg, addterms, and poly-simp can be replaced with one function like this:
(define (poly-simp p)
(define-values (a n q)
(for/fold ((a 0) (n 0) (q '())) ((x (sort p < #:key cdr)))
(define b (car x))
(define k (cdr x))
(if (= n k)
(values (+ a b) n q)
(values b k (cons (cons a n) q)))))
(cons (cons a n) q))
I don't know how to run your stress test, so I will leave this to you. I am not
sure it will cut the time.
> 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.
It's also wrong and stylistically bad:
(define (poly-mul p1 p2)
(define deg1 (poly-deg p1))
(define deg2 (poly-deg p2))
(define noob (make-vector (- (+ deg1 deg2) 1)))
;; MF: bug, these were 1s:
(for* ([i (in-range 0 deg1)] [j (in-range 0 deg2)])
(define k (+ i j))
(define a (* (vector-ref p1 i) (vector-ref p2 j)))
(vector-set! noob k (+ (vector-ref noob k) a)))
noob)
> 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.
Do try hash and for/hash. I think you will be pleased with the performance. --
Matthias
p.s. Do report back.
____________________
Racket Users list:
http://lists.racket-lang.org/users
