;;; -*- Lisp -*-
;;; msort5.lisp multiplication of polyns based on
;;; sortx+y.lisp msort2-5 uses heaps implemented as lisp lists. seems
;;; like a loser, 4X slower than hash, somewhat slower than arrays.
;;; msort5 uses lisp lists to construct a heap, each internal node n
;;; is, in this design (here . (left . right)) where here is a leaf
;;; node, and left/right may either be nil or an internal node or a
;;; leaf node. A leaf node looks like a dotted pair consisting of
;;; (number . number). They represent an exponent . coefficient pair.
;;; An empty heap looks like this: (nil)
(eval-when (compile load) (declaim (optimize (speed 3)(safety 0))))
;; sort X+Y various ways.
(defun make-rlc(n d)
;;make random list of length n with spacing k, with 0 msort5
(time (mulheap2 x y)) in msort4. x is 1000 terms, y is 500 terms
; cpu time (non-gc) 982 msec user, 0 msec system
; cpu time (gc) 111 msec user, 15 msec system
; cpu time (total) 1,093 msec user, 15 msec system
; real time 1,125 msec
; space allocation:
; 2,005,460 cons cells, 64 other bytes, 0 static bytes
((4 . 12) (5 . 26) (6 . 10) (8 . 9) (9 . 23) (10 . 4) (11 . 9)
(12 . 18) (13 . 11) (14 . 12) ...)
......
(time (mulheap2 x y)) in msort5
; cpu time (non-gc) 968 msec user, 0 msec system
; cpu time (gc) 16 msec user, 0 msec system
; cpu time (total) 984 msec user, 0 msec system
; real time 985 msec
; space allocation:
; 1,754,760 cons cells, 0 other bytes, 0 static bytes <<<<<< note less memory
((4 . 12) (5 . 26) (6 . 10) (8 . 9) (9 . 23) (10 . 4) (11 . 9)
(12 . 18) (13 . 11) (14 . 12) ...)
|#