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


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!):


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.

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