# [racket] Mutable state vs RAM on fire

 From: Rüdiger Asche (rac at ruediger-asche.de) Date: Thu May 3 07:45:46 EDT 2012 Previous message: [racket] Mutable state vs RAM on fire Next message: [racket] Mutable state vs RAM on fire Messages sorted by: [date] [thread] [subject] [author]

```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
>
>
> ____________________
>   Racket Users list:
>   http://lists.racket-lang.org/users
>
>

```

 Posted on the users mailing list. Previous message: [racket] Mutable state vs RAM on fire Next message: [racket] Mutable state vs RAM on fire Messages sorted by: [date] [thread] [subject] [author]