[racket] Mutable state vs RAM on fire

I believe the problem is the representation, you have chosen
for polynomials in the first program.

I am interested in hearing if the following representation gives a
better results:

#lang racket
(require (only-in srfi/1 span))

;;;
;;; Dense polynomials represented as lists.
;;;

(define-struct poly (deg coefs) #:transparent)
;   deg is the degree
;   coefs is a list of coeffecients.
;   p(x) = sum ci * x^i is represented as (poly n (list c0 c1 ... cn))

(define (degree p)
  (poly-deg p))

(define (remove-leading-zeros xs)
  (cond [(empty? xs) xs]
        [(zero? (car xs)) (remove-leading-zeros (cdr xs))]
        [else xs]))

(define (trim-trailing-zeros xs)
  (reverse (remove-leading-zeros (reverse xs))))

(define (coef-length->degree cs)
  (if (empty? cs)
      -inf.0
      (- (length cs) 1)))

(define (poly-add p1 p2)
  (if (< (degree p1) (degree p2))
      (poly-add p2 p1)
      (let* ([cs (trim-trailing-zeros
                  (for/list ([c1 (in-list (poly-coefs p1))]
                             [c2 (in-list (append (poly-coefs p2)
                                                  (build-list (-
(degree p1) (degree p2))
                                                              (λ (i) 0))))])
                    (+ c1 c2)))])
        (poly (coef-length->degree cs) cs))))

(define (poly-mul p1 p2)
  (define (sum-same-degree i dcs)
    (if (empty? dcs)
        '()
        (let-values ([(deg-i deg-larger) (span (λ (dc) (= (car dc) i)) dcs)])
          (cons (apply + (map cdr deg-i))
                (sum-same-degree (+ i 1) deg-larger)))))
  (let* ([dcs
          (for*/list ([(c1 i) (in-indexed (in-list (poly-coefs p1)))]
                      [(c2 j) (in-indexed (in-list (poly-coefs p2)))])
            (cons (+ i j) (* c1 c2)))]
         [dcs (sort dcs < #:key car)]
         [cs (sum-same-degree 0 dcs)])
    (poly (coef-length->degree cs) cs)))

/Jens Axel


2012/5/2  <joshua at anwu.org>:
>
> Hey all,
>
> Been playing around with some code to multiply polynomials to calculate dice probabilities.
> Is based on a paper by Doron Zeilberger that I read years ago and can't find at the moment.
>
> My first attempt represented polynomials as lists of coefficient/exponent pairs.
> I tried to make it completely functional, with no set! operations.  You can see it here:
>
> https://github.com/TurtleKitty/Dice/blob/2fff16e198cb84d725c786ecc624fb9b9468e778/dice.rkt
>
> It worked, but only to a point.  At 9 or 10 dice, it started blowing up the RAM in my machine.
> I swear I smelled smoke.  It grabbed like 4G and slowed to a crawl.
>
> Knowing that the Perl and Javascript versions of this program can calculate distributions for 300 dice in the space of a heartbeat,
> I rewrote the thing to use vectors instead, and altered the polynomial multiplication function to use (begin) and (vector-set!):
>
> https://github.com/TurtleKitty/Dice/blob/67c2b49707132395f73b43afe111e3904b3898f2/dice.rkt
>
> It too now calculates three hundred dice without breaking a sweat, but... I feel dirty.
> Can anyone recommend a functional approach that won't melt my motherboard?
> I'm considering hashes, since they have the immutable version of hash-set that vectors seem to lack, but I thought I'd ask the experts.
>
>
> Thanks,
> turtlekitty
> (There might be a library for this already. This is more of an exercise for me than a utility.)
> ____________________
>  Racket Users list:
>  http://lists.racket-lang.org/users



-- 
--
Jens Axel Søgaard