[racket] Mutable state vs RAM on fire

Dear Stephen,

   It turns out that the "fast" multiplication algorithm isn't so fast for 
polynomials.  See Norvig's Paradigms of AI Programming or Zippel's 
Effective Polynomial Computation.

-Arthur

==============================================================
Arthur Nunes-Harwitt
Computer Science Department, Rochester Institute of Technology
Room 70-3509
585-475-4916
==============================================================

"I don't know what the language of the future will be
called, but it will look like LISP."

This email is confidential and intended for the named recipient(s). In
the event the email is received by someone other than the recipient,
please notify the sender at anh at cs.rit.edu.

On Thu, 3 May 2012, Stephen Bloch wrote:

>
> 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
>