# [racket] Mutable state vs RAM on fire

uhm... am I mistaken, or is there one recursive call to fast-expt in a
non tail recursive position? Schouldn't that be unwound?
Quoting Stephen Bloch <bloch at adelphi.edu>:
>*
*>* 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
*>*
*>*
*>* ____________________
*>* Racket Users list:
*>* http://lists.racket-lang.org/users
*>*
*>*
*