問題解答

問1.15 a
(sine 12.15)
(sine 4.05)
:

と、sine が呼ばれる度に angle が 1/3 になり、それが 0.1 未満になるまで続くのだから

12.15*(1/3^n) < 0.1 が解ければよい。 121.5 < 3^n log(121.5) < n(log(3)) log(121.5)/log(3) < n 4.369 < n より、n は 5。 問1.15 b 反復的操作のため、スペースは O(1) ステップ数は n が三倍になると一つ増えるので O(log3(n))

本文

1.2.4 べき乗
再帰的プロセス、反復的プロセスを使用した場合のオーダーと、更に逐次平方を利用した場合のオーダーの比較。
O(log n) にできた場合の効果。

問題解答

問1.16
自分の書いたコードは以下。

(define (fast-expt b n)
  (define (even? v)
    (= (remainder v 2) 0))

  (define (expt-iter a b n)
    (cond ((= n 0) a)
          ((= n 1) (* a b))
          ((even? n) (square (expt-iter a b (/ n 2))))
          (else (* (expt-iter a b (- n 1)) b))))

  (expt-iter 1 b n))

答え合わせをして気づいたのだが、 even? が真だった場合に評価されるところが末尾最適化されないので解答としては不正解。