[racket] Mutable state vs RAM on fire

From: Stephen Bloch (bloch at adelphi.edu)
Date: Thu May 3 06:50:08 EDT 2012

On May 2, 2012, at 11:50 PM, Deren Dohoda wrote:

> Well I am sure it will try to use all the memory it can. Anyway, my
> functional code can raise the polynomial you gave '(1 1 1 1 1 1 0) to
> the 300th power in about four seconds on my machine, with half a
> second of garbage collection....
> But you can factor '(1 1 1 1 1 1 0) into '((1 0) (1 1) (1 0 1 0 1))....

Are we trying to multiply a bunch of arbitrary polynomials, or raise a single one to a large power?

If the latter, you can probably get a much more dramatic speed improvement by using "fast exponentiation":
(define (fast-expt p n)
   (cond [(= n 1) p]
              [(even? n)
                (let [(p2 (mult p p))]
                       (fast-expt p2 (quotient n 2)))]
              [(odd? n)
               (let [(p2 (mult p p))]
                      (mult p (fast-expt p2 (quotient n 2))))]))
This reduces O(n) many multiplications to O(log(n)) many multiplications, which will dwarf most of the other optimizations people have mentioned.

Stephen Bloch
sbloch at adelphi.edu

Posted on the users mailing list.