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 <jos...@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
____________________
Racket Users list:
http://lists.racket-lang.org/users
