おやすみSICP

問題文を読めばよい

;;;q1.16 冪乗
;;; $Id$

;;;線形
(define (beki n c)
  (if (= c 0)
    1
    (* n (beki n (- c 1)))
  )
)

;;(even? 2)
;;even?はあるらしい。
;;(remainder hoge hoge)を使用せよとSICPにはあるが。

;;;even?で省力するタイプ
(define (square n)
  (* n n)
)
(define (bekiH n c)
  (if (= c 0)
    1
    (if (even? c)
      (square (bekiH  n (/ c 2)))
      (* n (bekiH n (- c 1)))
    )
  )
)

;;;反復 productを持つタイプ
(define (bekiP n c)
  (beki-itr n c 1)
  )
(define (beki-itr n c p)
  (if (= c 0)
      p
      (beki-itr n (- c 1) (* n p))
      )
  )
(bekiP 2 3)

;;;反復+even?省力
(define (bekiHP n c)
  (beki-itr2 n c 1)
  )
(define (beki-itr2 n c p)
  (cond
       ((= c 0) p)
       ((even? c) (beki-itr2 (* n n) (/ c 2)  p)) ;b**n == (b*b)**(n/2)
       (else (beki-itr2 n (- c 1) (* n p))))
  )

(require (lib "trace.ss"))
(trace beki)
(trace bekiH)
(trace bekiP)
(trace bekiHP)
(trace beki-itr)
(trace beki-itr2)

(- (+ (beki 2 16) (bekiHP 2 16))
   (+ (bekiH 2 16) (bekiHP 2 16)))

(beki 2 16)
(beki 2 15)
	(beki 2 14)
	(beki 2 13)
		(beki 2 12)
		(beki 2 11)
			(beki 2 10)
			(beki 2 9)
				(beki 2 8)
				(beki 2 7)
			[10](beki 2 6)
			[11](beki 2 5)
			[12](beki 2 4)
			[13](beki 2 3)
			[14](beki 2 2)
			[15](beki 2 1)
			[16](beki 2 0)
			[16]1
			[15]2
			[14]4
			[13]8
			[12]16
			[11]32
			[10]64
				128
				256
			512
			1024
		2048
		4096
	8192
	16384
32768
65536
(bekiHP 2 16)
(beki-itr2 2 16 1)
(beki-itr2 4 8 1)
(beki-itr2 16 4 1)
(beki-itr2 256 2 1)
(beki-itr2 65536 1 1)
(beki-itr2 65536 0 65536)
65536
(bekiH 2 16)
(bekiH 2 8)
	(bekiH 2 4)
	(bekiH 2 2)
		(bekiH 2 1)
		(bekiH 2 0)
		1
		2
	4
	16
256
65536
(bekiHP 2 16)
(beki-itr2 2 16 1)
(beki-itr2 4 8 1)
(beki-itr2 16 4 1)
(beki-itr2 256 2 1)
(beki-itr2 65536 1 1)
(beki-itr2 65536 0 65536)
65536

わりと一目瞭然