(herald trivial)


(define (p* x y)

  (define (ip* x y)
    (if (null? x)
	'()
	(p+ (pc* (car x) y)
	    (cons 0 (ip* (cdr x) y)))))

  (define (pc* c y)
    (if (null? y)
	'()
	(cons (* c (car y))
	      (pc* c (cdr y)))))

  (define (p+ x y)
    (cond ((null? x) y)
	  ((null? y) x)
	  (else (cons (+ (car x) (car y))
		      (p+ (cdr x) (cdr y))))))

  (ip* x y))


(define (fp* x y)

  (define (ifp* x y)
    (if (null? x)
	'()
	(fp+ (future (fpc* (car x) y))
	     (cons 0 (future (ifp* (cdr x) y))))))

  (define (fpc* c y)
    (if (null? y)
	'()
	(cons (* c (car y))
	      (future (fpc* c (cdr y))))))

  (define (fp+ x y)
    (cond ((null? x) y)
	  ((null? y) x)
	  (else (cons (+ (car x) (car y))
		      (future (fp+ (cdr x) (cdr y)))))))

  (ifp* x y))


(define (bp* x y)

  (define (ifp* x y)
    (if (null? x)
	'()
	(fp+ (future (fpc* (car x) y))
	     (cons 0 (future (ifp* (cdr x) y))))))

  (define (fpc* c y)
    (if (null? y)
	'()
	(cons (* c (car y))
	      (fpc* c (cdr y)))))

  (define (fp+ x y)
    (cond ((null? x) y)
	  ((null? y) x)
	  (else (cons (+ (car x) (car y))
		      (fp+ (cdr x) (cdr y))))))

  (ifp* x y))


(define x+1 '(1 1))

(define (walk-poly p)
  (length p))

(define (poly-expt p e)
  (if (< e 2)
      (cond ((= e 0) '(1))
	    ((= e 1) p))
      (let ((psq (poly-expt (p* p p) (quotient e 2))))
	(if (= (remainder e 2) 0)
	    psq
	    (p* p psq)))))

(define (big-poly e)
  (let ((p (poly-expt x+1 e)))
    (walk-poly p)
    p))

(define p50 (big-poly 50))

(define q50 (poly-expt '(1 1 0 0 1 0 0 0 0 1 1) 5))

(define q100 (poly-expt '(1 1 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 1) 5))

(define (test . args)
  (let ((p p50))
    (if (not (null? args))
	(set! p (car args)))
    (let ((p100 (time (p* p p))))
      (time (walk-poly p100))
      (time (walk-poly (fp* p p)))
      (time (walk-poly (bp* p p))))))

(define (ptest . args)
  (let ((p p50)
	(p100 '()))
    (if (not (null? args))
	(set! p (car args)))
    (time (begin (set! p100 (fp* p p))
		 (walk-poly p100)))
    (time (walk-poly p100))))