EoPL reading (48) 2.1 Specifying Data via Interfaces

scheme

Exercise.2-1

  1. 引数の値の変化で処理時間はどのように変わるか
  2. 基数の値の (同上

との事なんですが、先日の報告によれば基数が 2 の時とそれ以外で相当違う。

  • N が 2 だと大体 real で 12sec 程度
  • N が 4 だと 9.5sec 程度
  • N が 16 だと 6 とか 7sec 程度
  • N が 8 だとこれも 8 とか 9.5sec とかなカンジ

ビットだと桁上がりが激しくて、なのかな。あと、引数の値については計算量をきちんと見切ってないので微妙です。ちょっとこれ、今日は無理だな。
現実トウヒな時間を確保したい。明日は可能かも。(何
# mul な手続き微妙スギ

む

基数が 2 だったら、って fact な手続きに致命的(?) なナニを発見。

(define (fact n)
  (if (iszero? (pred n))
      (succ zero)
      (mul n (fact (pred n)))))

これは let 使わんと微妙?

(define (fact n)
  (let ((p (pred n)))
    (if (iszero? p)
        (succ zero)
        (mul n (fact p)))))

うーん、これはこれで現実トウヒ。あと、mul の

            ((null? R0) rslt)

なケースも無いな。そりゃ良いが、計算量に影響している記述は mul 手続きの以下か。

            ((not (= 0 (car Acc))) (f (cons 0 R0) (cdr Acc) 
				      (let tmp ((x (car Acc)) (c 0) (rslt rslt)) 
					(if (= x c) 
					    rslt 
					    (tmp x (+ 1 c) (plus R0 rslt))))))

値の大きさ分加えている。これが 2 進だと必ず一発ですが、そうでない場合は何度か繰り返しが発生するな。って + って手続き使って良いんだっけ。いいのか。
あと、plus の計算量も直感的に見えない。あ、これって手続き毎に計算量はある程度見えるのか。plus は基数が大きい方が繰り返しが多いように見えるな。
やっぱこの件明日で勘弁して下さひ。