[racket] Mutable state vs RAM on fire

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. Not fast, I admit. It's not a very good
implementation.

But you can factor '(1 1 1 1 1 1 0) into '((1 0) (1 1) (1 0 1 0 1)).
The first of these to the nth power just tacks n zeros to the end of
your result (representing sums that are impossible in n rolls I
suppose). Either just ignore it or tack the zeros on at the end. The
second of these can be expanded directly by using the binomial
theorem. The last can't be trivially generated as far as I can tell
(there's probably some way using the multinomial theorem but I
couldn't figure it out quickly) but anyway you can split these up to
save the big multiplication last:

Welcome to DrRacket, version 5.2 [3m].
Language: Determine language from source; memory limit: 1024 MB.
> (require user/polynomials user/prob-and-stat)
> (define-syntax-rule (my-time exp)
    (begin (displayln (quote exp))
           (collect-garbage)(collect-garbage)(collect-garbage)
           (time exp)))
> (let ((a (my-time (poly-expt '(1 0 1 0 1) 300)))
        (b (my-time (cons 1 (map (λ(i) (combination 300 i)) (reverse
(build-list 300 values)))))))
    (my-time (poly* a b))
    (void))
(poly-expt '(1 0 1 0 1) 300)
cpu time: 1031 real time: 1032 gc time: 109
(cons 1 (map (λ (i) (combination 300 i)) (reverse (build-list 300 values))))
cpu time: 234 real time: 234 gc time: 78
(poly* a b)
cpu time: 547 real time: 547 gc time: 47
>

Around half of the numbers from the '(1 0 1 0 1) exponentiation will
require bignums, which you start hitting fairly early on in the
multiplication process. (Around the 21st power for 32 bit machine.)
'(1 0 1 0 1) can also be factored into '(1 1 1) x '(1 -1 1) but I
didn't find it helped speed up anything at all.

I was curious as to why you stored the exponents at all. If your
polynomials aren't sparse (mostly zero coefficients) then just store
the list of coefficients in ascending or descending order and have the
exponents implied. The only time I needed to keep track of exponents
was shifting the origin and composing polynomials.

Deren

On Wed, May 2, 2012 at 9:25 PM,  <joshua at anwu.org> wrote:
>
>
> Heh... I guess that information would be relevant. :)
>
> Not looking for any particular performance numbers, just that it could finish
> without sucking up all the RAM and thrashing about the swap.  I've been
> feeding it up to 1000 deg-6 polynomials to multiply as tests.  The imperative
> versions (Perl, JS, and Racket) all handle this fine.  The first Racket
> version I wrote using a-lists blew up to 4G of memory at 10 polynomials.
>
> I suspect it's related to what DY said about needing to simplify polynomaials
> between multiplications.
>
> I just finished a third iteration, this one using hash tables.
> This one has no mutable state, and runs much faster than my alist version.
> Is not as fast as the mutable vector version, or even the Perl version,
> but one can't have everything... it's at least in the same order of magnitude, now.
>
> https://github.com/TurtleKitty/Dice/blob/e69dc696f4d36a7dfdb6ec28676f5c002f5de6b1/dice.rkt
>
> This process has been educational.
>
>
> tk
> (Also fixed a couple of bugs and added a histogram.)
>
>
> On Wed, May 02, 2012 at 08:52:25PM -0400, Deren Dohoda wrote:
>> What sort of time are you looking for for it to be "handled"?
>>
>> Deren
>>