SICP 問題 5.46 - (wat-aro)

5.45と同様に今度はフィボナッチ数列の計算でそれぞれ比べる．

gosh> (define fib  ;;一回目以外は省略
        (make-machine
         (list (list '< <)
               (list '- -)
               (list '+ +))
         '(controller
           (assign continue (label fib-done))
           fib-loop
           (test (op <) (reg n) (const 2))
           (branch (label immediate-answer))
           ;; Fib(n-1)を計算するよう設定
           (save continue)
           (assign continue (label afterfib-n-1))
           (save n)                      ;n の昔の値を退避
           (assign n (op -) (reg n) (const 1))   ;n を n-1 に変える
           (goto (label fib-loop))               ;再帰呼び出しを実行
           afterfib-n-1                ;戻った時 Fib(n-1) は val にある
           (restore n)
           (restore continue)
           ;; Fib(n-2)を計算するよう設定
           (assign n (op -) (reg n) (const 2))
           (save continue)
           (assign continue (label afterfib-n-2))
           (save val)                    ;Fib(n-1) を退避
           (goto (label fib-loop))
           afterfib-n-2            ;戻った時 Fib(n-2) の値は val にある
           (assign n (reg val))    ;n には Fib(n-2) がある
           (restore val)           ;val には Fib(n-1) がある
           (restore continue)
           (assign val                   ;Fib(n-1) + Fib(n-2)
                   (op +) (reg val) (reg n))
           (goto (reg continue))   ;呼び出し側に戻る．答えは val にある
           immediate-answer
           (assign val (reg n))          ;基底の場合: Fib(n)=n
           (goto (reg continue))
           fib-done
           (perform (op print-stack-statistics)))))

fib
gosh> (set-register-contents! fib 'n 1)
done
gosh> (start fib)

(total-pushes = 0 maximum-depth = 0)done
gosh> (get-register-contents fib 'val)
1

gosh> (set-register-contents! fib 'n 2)
done
gosh> (start fib)

(total-pushes = 4 maximum-depth = 2)done
gosh> (get-register-contents fib 'val)
1
gosh> (set-register-contents! fib 'n 3)
done
gosh> (start fib)

(total-pushes = 8 maximum-depth = 4)done
gosh> (get-register-contents fib 'val)
2
gosh> (set-register-contents! fib 'n 4)
done
gosh> (start fib)

(total-pushes = 16 maximum-depth = 6)done
gosh> (get-register-contents fib 'val)
3
gosh> (set-register-contents! fib 'n 5)
done
gosh> (start fib)

(total-pushes = 28 maximum-depth = 8)done
gosh> (get-register-contents fib 'val)
5
gosh> (set-register-contents! fib 'n 5)
done
gosh> (start fib)

(total-pushes = 28 maximum-depth = 8)done
gosh> (get-register-contents fib 'val)
5
gosh> (set-register-contents! fib 'n 6)
done
gosh> (start fib)

(total-pushes = 48 maximum-depth = 10)done
gosh> (get-register-contents fib 'val)
8
gosh> (set-register-contents! fib 'n 7)
done
gosh> (start fib)

(total-pushes = 80 maximum-depth = 12)done
gosh> (get-register-contents fib 'val)
13
gosh> (set-register-contents! fib 'n 8)
done
gosh> (start fib)

(total-pushes = 132 maximum-depth = 14)done
gosh> (get-register-contents fib 'val)
21
gosh> (set-register-contents! fib 'n 9)
done
gosh> (start fib)

(total-pushes = 216 maximum-depth = 16)done
gosh> (get-register-contents fib 'val)
34
gosh> (set-register-contents! fib 'n 10)
done
gosh> (start fib)

(total-pushes = 352 maximum-depth = 18)done
gosh> (get-register-contents fib 'val)
55

　
翻訳系

gosh> (compile-and-go
       '(define (fib n)
          (if (< n 2)
              n
              (+ (fib (- n 1)) (fib (- n 2))))))

(total-pushes = 0 maximum-depth = 0)
;;; EC-Eval value:
ok

;;; EC-Eval input:
(fib 1)

(total-pushes = 7 maximum-depth = 3)
;;; EC-Eval value:
1

;;; EC-Eval input:
(fib 2)

(total-pushes = 15 maximum-depth = 5)
;;; EC-Eval value:
1

;;; EC-Eval input:
(fib 3)

(total-pushes = 23 maximum-depth = 7)
;;; EC-Eval value:
2

;;; EC-Eval input:
(fib 4)

(total-pushes = 39 maximum-depth = 9)
;;; EC-Eval value:
3

;;; EC-Eval input:
(fib 5)

(total-pushes = 63 maximum-depth = 11)
;;; EC-Eval value:
5

;;; EC-Eval input:
(fib 6)

(total-pushes = 103 maximum-depth = 13)
;;; EC-Eval value:
8

;;; EC-Eval input:
(fib 7)

(total-pushes = 167 maximum-depth = 15)
;;; EC-Eval value:
13

;;; EC-Eval input:
(fib 8)

(total-pushes = 271 maximum-depth = 17)
;;; EC-Eval value:
21

;;; EC-Eval input:
(fib 9)

(total-pushes = 439 maximum-depth = 19)
;;; EC-Eval value:
34

;;; EC-Eval input:
(fib 10)

(total-pushes = 711 maximum-depth = 21)
;;; EC-Eval value:
55

　
積極制御評価器

;;; EC-Eval input:
(define (ec-fib n)
  (if (< n 2)
      n
      (+ (ec-fib (- n 1)) (ec-fib (- n 2)))))

(total-pushes = 3 maximum-depth = 3)
;;; EC-Eval value:
ok

;;; EC-Eval input:
(ec-fib 1)

(total-pushes = 16 maximum-depth = 8)
;;; EC-Eval value:
1

;;; EC-Eval input:
(ec-fib 2)

(total-pushes = 72 maximum-depth = 13)
;;; EC-Eval value:
1

;;; EC-Eval input:
(ec-fib 3)

(total-pushes = 128 maximum-depth = 18)
;;; EC-Eval value:
2

;;; EC-Eval input:
(ec-fib 4)

(total-pushes = 240 maximum-depth = 23)
;;; EC-Eval value:
3

;;; EC-Eval input:
(ec-fib 5)

(total-pushes = 408 maximum-depth = 28)
;;; EC-Eval value:
5

;;; EC-Eval input:
(ec-fib 6)

(total-pushes = 688 maximum-depth = 33)
;;; EC-Eval value:
8

;;; EC-Eval input:
(ec-fib 7)

(total-pushes = 1136 maximum-depth = 38)
;;; EC-Eval value:
13

;;; EC-Eval input:
(ec-fib 8)

(total-pushes = 1864 maximum-depth = 43)
;;; EC-Eval value:
21

;;; EC-Eval input:
(ec-fib 9)

(total-pushes = 3040 maximum-depth = 48)
;;; EC-Eval value:
34

;;; EC-Eval input:
(ec-fib 10)

(total-pushes = 4944 maximum-depth = 53)
;;; EC-Eval value:
55

プッシュ数

n	計算機	翻訳系	評価器	評/機	翻/機
3	8	23	128	16.0	2.87
4	16	39	240	15.0	2.43
5	28	63	408	14.57	2.25
6	48	103	688	14.33	2.14
7	80	167	1136	14.2	2.08
8	132	271	1864	14.12	2.05
9	216	439	3040	14.07	2.03
10	352	711	4944	14.04	2.01\|
20	43780	87567	612936	14.0	2.0

　
最大スタック深さ

計算機	翻訳系	評価器	評/機	翻/機
2n-2	2n+1	5n+3	2.500	1.00