[racket] Mutable state vs RAM on fire

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

;; poly-eval polynomial number -> number
;; evaluate a polynomial, for a given value of its variable, using
Horners rule
(define (poly-eval p x) (foldr (lambda (l r) (+ l (* x r))) 0 p))

;; poly-add polynomial polynomial -> polynomial
;; add two polynomials together, allowing for polynomials
;; of different length
(define (poly-add p1 p2)
  (cond
    ((empty? p1) p2)
    ((empty? p2) p1)
    (else (cons (+ (first p1) (first p2)) (poly-add (rest p1) (rest p2))))))

;; poly-mul polynomial polynomial -> polynomial
;; multiply two polynomials together, allowing for polynomials
;; of different length
;; * is the multiply function to be used
(define (poly-mul * p1 p2)
  (foldr (lambda (l r) (poly-add (map (curry * l) p1) (cons 0 r))) empty
p2))
 
;; make a degree n polynomial with coeffs from 1 to k
(define (make-poly n k) (build-list n (lambda (x) (add1 (random k)))))

;; make m degree n polynomials with coeffs up to k
(define (make-polys m n k) (build-list m (lambda (x) (make-poly n k))))

;; do the tests
(time (foldr (curry poly-mul *) (list 1) (make-polys 1000 6 10)))

(time (foldr (curry poly-mul *mod) (list 1) (make-polys 1000 6 10)))

-- 
Chris Stephenson
cs at csl.tc