I made a tail recursion improvement (using mutation, as Christian suggested), and Brad Lucier's conjecture of Feb 6, 2005 becomes true. Now, on a machine with 2GB memory, I can "differentiate" my polynomial of length 75299 in 8.2 minutes, with essentially *no* garbage collection:

(time (pretty-print (Poly-first (D X)))) 495310 ms real time, 8.2 minutes 495314 ms cpu time (494923 user, 391 system) 35 collections accounting for 2568 ms real time, 0.0 minutes 1193260824 bytes allocated 10180 minor faults no major faults

Brad replied to me on Feb 6:

(time (pretty-print (Poly-first (D X)))) 998093 ms real time, 16.6 minutes 997940 ms cpu time (997840 user, 100 system) 3204 collections accounting for 365525 ms real time (365690 user, 30 system) 112648202368 bytes allocated 13318 minor faults 3 major faults

Did I really use 112.6 gB? My machine "only" has 1 gB of memory.

Probably, yes. Each of the 3204 garbage collections collected on average about 30+ megabytes of data, which it could reuse until the next GC, etc. My guess is that if you doubled the amount of real memory to 2GB the number of collections would drop to a few hundred.

The improvement I made was to replace this non-tail recursive merge function

;; merge-1 : (listof X)^2 (X X -> boolean) -> (listof X) ;; to merge two sorted lists into a longer sorted list, deleting ;; repetitions, using less-than?. (define (merge-1 shortlist longlist less-than?) (cond [(empty? shortlist) longlist] [(empty? longlist) shortlist] [else (let ([a (first shortlist)] [x (first longlist)]) (cond [(equal? a x) (merge-1 (rest shortlist) (rest longlist) less-than?)] [(less-than? a x) (cons a (merge-1 (rest shortlist) longlist less-than?))] [else (cons x (merge-1 shortlist (rest longlist) less-than?))]))]))

with this tail-recursive merge function (which I then renamed):

;; merge-sort : (listof X)^2 (X X -> boolean) -> (listof X) ;; to merge two sorted lists into a longer sorted list, deleting ;; repetitions, using less-than?. ;; Tail recursive with mutation. (define (merge-sort shortlist longlist less-than?) (let ([M (cons 'start longlist)]) ;; we need a kludge because when we consume longlist, ;; there's no pointer left to attach shortlist to. (let loop ([shortlist shortlist] [p M]) (cond [(empty? shortlist) (rest M)] [(empty? (rest p)) (and (set-rest! p shortlist) (rest M))] [else (let* ([a (first shortlist)] [R (rest p)] [x (first R)] [RR (rest R)]) (cond [(equal? a x) ;; delete x by replacing R by RR (and (set-rest! p RR) (loop (rest shortlist) p))] [(less-than? a x) (and (set-first! R a) (set-rest! R (cons x RR)) (loop (rest shortlist) R))] [else (loop shortlist (rest p))]))]))))

I feel like there ought to be a more elegant way to code this...