[racket] Mutable state vs RAM on fire

From: Danny Yoo (dyoo at cs.wpi.edu)
Date: Wed May 2 21:14:04 EDT 2012

>> In the functional version of poly-mul, why doesn't it call poly-simp?
>> I'm concerned that if you leave the simplification up to the very end,
>> it might not be as effective as if it were being done all the time.

The reason I brought this up is because, intuitively, here is where
I'd expect the choice of representation really matters.  Since terms
with the same power don't coalese until poly-simp gets called, and
since poly-simp gets called only after mega-mul, I can imagine the
representation exploding exponentially right here.

How large is the input that you've been feeding to this?  That gives
us a better sense of the scope of the problem.

I did a quick scan for "sparse polynomial multiplication" and came across:


which may apply to this problem; I haven't read through the paper to
see how friendly it is to functional implementation.

Posted on the users mailing list.