an:sicp: 問題1.26

オリジナルのexpmodにおいて、(evenp exp)が成り立つexpmodの呼び出しの数をaとすると、

$2^a \le n < 2^{a + 1}$

なので、

$a \le \log_2n < a + 1$

(oddp exp)が成り立つexpmodの呼び出しの数をbとすると、

$0 \le b \le a + 1$

であるから、

$0 \le b \le \log_2n + 1$

(zerop exp)が成り立つexpmodの呼び出しは一回限りなので、expmodの呼び出しの合計は、

$\log_2n < a + b + 1 \le 2\log_2n + 2$

であり、プロセスはΘ(log n)。

これに対し、Louisのexpmodでは、まず、(evenp exp)が成り立つexpmodの呼び出しの数は、

$\sum_{i=0}^{a - 1}2^i$

(evenp exp)が成り立つごとにプロセスが二方向に分岐するため。

次に、(oddp exp)が成り立つexpmodの呼び出しの数はn。プロセスの過程でexpが1/2になるごとに、(oddp exp)が成り立つ呼び出しの数が2倍になり、結果的にnと等しくなる。

最後に、(zerop exp)が成り立つexpmodの呼び出しの回数は2^a。本来プロセスの中で一回だけのものが、最終的に(evenp exp)が成り立つexpmodの呼び出しの数だけ2倍になる。

これより、Louisのexpmodでのexpmodの呼び出しの合計は、

$\sum_{i=0}^{a - 1}2^i + n + 2^a$

となり、nに比例し、プロセスはΘ(n)。

an:sicp