[racket] Mutable state vs RAM on fire

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