[racket] Mutable state vs RAM on fire

From: joshua at anwu.org (joshua at anwu.org)
Date: Wed May 2 15:05:23 EDT 2012

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

Posted on the users mailing list.