[racket] Mutable state vs RAM on fire
From: Chris Stephenson (cs at csl.tc)
Date: Thu May 3 01:47:44 EDT 2012 

Isn't this just a question of choice of data representation?
Once you drop the explicit powers from the representation and store
least significant coefficient first, then the racket program becomes
extremely simple.
One reason Racket goes slower is that it use big ints while perl and
javascript will both operate mod 2^32. A thousand polynomials multiplied
together makes for some really *big* ints.
Here is my stab at it. I made it so I wouldn't be ashamed to show it to
my students (apart from the lack of tests)
It does 1000 6 degree polynomials in 67 seconds on my little netbook.
If I do the arithmetic modulo 1000, despite the large overhead of
replacing multiply with a function that does the modulo operation, this
time drops to under 20 seconds. And this is a really slow little computer.
#lang racket
(define (*mod x y) (modulo (* x y) 1000))
;;data definition
;; a polynomial is represented by a list of its coefficients, starting
with the least significant
;; polyeval polynomial number > number
;; evaluate a polynomial, for a given value of its variable, using
Horners rule
(define (polyeval p x) (foldr (lambda (l r) (+ l (* x r))) 0 p))
;; polyadd polynomial polynomial > polynomial
;; add two polynomials together, allowing for polynomials
;; of different length
(define (polyadd p1 p2)
(cond
((empty? p1) p2)
((empty? p2) p1)
(else (cons (+ (first p1) (first p2)) (polyadd (rest p1) (rest p2))))))
;; polymul polynomial polynomial > polynomial
;; multiply two polynomials together, allowing for polynomials
;; of different length
;; * is the multiply function to be used
(define (polymul * p1 p2)
(foldr (lambda (l r) (polyadd (map (curry * l) p1) (cons 0 r))) empty
p2))
;; make a degree n polynomial with coeffs from 1 to k
(define (makepoly n k) (buildlist n (lambda (x) (add1 (random k)))))
;; make m degree n polynomials with coeffs up to k
(define (makepolys m n k) (buildlist m (lambda (x) (makepoly n k))))
;; do the tests
(time (foldr (curry polymul *) (list 1) (makepolys 1000 6 10)))
(time (foldr (curry polymul *mod) (list 1) (makepolys 1000 6 10)))

Chris Stephenson
cs at csl.tc