SICP 1.2.4 Exponentiation - プログラミング再入門

ノート

冪乗。
b⁸を計算するのにb×b×b×b×b×b×b×bと計算するより、b²=b×b、b⁴=b²×b²、b⁸=b⁴×b⁴とした方が効率的。
nが偶数の時、bⁿ=(b^n/2)²、
nが奇数の時、bⁿ=b×b^n-1
とするとかけ算の回数を減らせる。

Exercise 1.16

bⁿを求める。
iterative procedureの引数として基数b、冪乗n、答えa（途中結果）の３つを渡す。aの初期値は1。
各呼び出しでabⁿが常に一定になる様に、繰り返し毎に次の関数に渡す引数を以下の様にする。

nが偶数の時、b²、n/2、a
nが奇数の時、b、n-1、a×b
nが0になったらaが最終的な答え。

nの部分は最終的には2の冪乗に落ちて、2、1、0となって計算が終わる。
プログラムにすると

実行結果

> (fast-expt 2 8)
256
> (fast-expt 11 11)
285311670611
> (fast-expt 2 16)
65536
> (fast-expt 3 3)
27
> (fast-expt 3 4)
81
>

Exercise 1.17

つまり、a × bを計算するのに、

bが偶数であれば、a×b = 2a×b/2
bが奇数であれば、a×b = a + a×(b-1)

として、bが1になるまで繰り返す。渡される二つに引数の積を一定に保ちながら、片方の引数が1になる様に変換して行く。

実行結果

> (fast-multi 0 0)
0
> (fast-multi 1 0)
0
> (fast-multi 0 1)
0
> (fast-multi 1 10)
10
> (fast-multi 10 1)
10
> (fast-multi 7 9)
63
> (fast-multi 9 9)
81
> (fast-multi 123 2)
246
> (fast-multi 2 123)
246
>

Exercise 1.18

iterative processにすると言う事は状態変数を使って実装する。状態変数をx、その初期値を0とすると、常にa×b+xが一定となる様に変換する。

aかbが0であればx=0
b=1の時はx=a
bが偶数であればaを２倍に、bを半分にして再び計算する
bが奇数であれば、aはそのまま、bから1引いて、xにaを足して再び計算する。

実行結果

> (fast-multi2 0 0)
0
> (fast-multi2 1 0)
0
> (fast-multi2 0 1)
0
> (fast-multi2 1 1)
1
> (fast-multi2 3 9)
27
> (fast-multi2 9 9)
81
>

Exercise 1.19

フィボナッチ数列をf(n)とf(n+1)のペアにして、f(n+1)とf(n+2)を行列演算で求める。調べてみると基本的にはFibonacci Q-matrixと呼ばれている手法らしい。ただし普通はFibonacci Q-matrixはフィボナッチ数を行列だけで表現されている。なかなか面白い演算なのでメモ。

フィボナッチ数の演算を行列で表現すると：
$\left[ f(n+1) \\ f(n)\right] =\left[\begin{array}{cc} 1 & 1 \\ 1 & 0\end{array} \right]\left[ f(n) \\ f(n-1)\right]$
この変換に用いる行列をTと表す。任意のフィボナッチ数を計算するにはこの変換を繰り返す事になるのでTを繰り返し掛ける事に等しい。フィボナッチ数を表す行列をFib(n)で表すと、
Fib(2) = T Fib(1)
Fib(n+1) = Tⁿ Fib(1)
と書ける。ここでFib(1) = (1 0)と言うベクトル。

ここでどこから持って来たのか分からない行列T_pqが登場。
$T_{pq}=\left[ \begin{array}{cc} p+q & q \\ q & p \end{array}\right]$
TはT_pqの特殊形：p = 0、q=1のケースであると言う。確かに。

このT_pqがなかなか面白い。T_pq²を考えると
${\left[ \begin{array}{cc} p+q & q \\ q & p \end{array}\right]}^2 = \left[ \begin{array}{cc} (p+q)^2+q^2 & (p+q)\times q+pq \\ (p+q)\times q+pq & q^2+p^2 \end{array}\right] =\left[ \begin{array}{cc} p^2+2pq+2q^2 & q^2+2pq\\ q^2+2pq& p^2+q^2\end{array}\right]$
元のqの位置（右上と左下）は共にq²+2pqとなっているので、取り敢えずこれをq'とする。また、右下のpの位置であるp²+q²を取り敢えずp'とすると、何と左上はp'+q'になっている。つまり
p' = p²+q²
q' = q^>2+2pq
と言う計算を繰り返せばT_pqの２の冪乗乗（？：つまり２乗、４乗、１６乗…）が計算出来る事になる。きっとこの行列には何か名前が付いていたりするのだろうけど。。。

T_pqⁿを計算するのに、nが偶数だと仮定するとT_pq²が計算出来れば
T_pqⁿ=(T_pq²)^n/2
で計算出来るので掛け算の回数はn回からn/2回に半減する。T_pq⁴が計算出来れば更に半分。

nが奇数の時は仕方ないのでT_pqを１回だけ掛けて残りの掛け算の回数nをひとつ減らすと、次は必ず偶数なのでまた計算回数を半分に出来る。

この計算をプログラムにしたのが問題文に書かれている。

フィボナッチの行列のそれぞれをa、bとして、p、qの初期値はそれぞれ0、1。T_pq^countで計算する。countを減らして0になったら計算終了。nが奇数の場合はT_pqを掛けてa'、b'を計算してcountをひとつ減らす、nが偶数の時はa'、b'を計算する変わりに(T_pq?)2（?の部分は既にT_pqの何乗かになっているかもしれない）を計算してcountを半分にする。
なので穴の部分を埋めると

実行してみても実に高速！
Mac Book Air / DrRacketでこんなのが実に高速に計算される。

> (fib 0)
0
> (fib 1)
1
> (fib 2)
1
> (fib 3)
2
> (fib 4)
3
> (fib 5)
5
> (fib 6)
8
> (fib 7)
13
> (fib 100)
354224848179261915075
> (fib 200)
280571172992510140037611932413038677189525
> (fib 300)
222232244629420445529739893461909967206666939096499764990979600
> (fib 400)
176023680645013966468226945392411250770384383304492191886725992896575345044216019675
> (fib 500)
139423224561697880139724382870407283950070256587697307264108962948325571622863290691557658876222521294125
> (fib 600)
110433070572952242346432246767718285942590237357555606380008891875277701705731473925618404421867819924194229142447517901959200
> (fib 700)
87470814955752846203978413017571327342367240967697381074230432592527501911290377655628227150878427331693193369109193672330777527943718169105124275
> (fib 800)
69283081864224717136290077681328518273399124385204820718966040597691435587278383112277161967532530675374170857404743017623467220361778016172106855838975759985190398725
> (fib 900)
54877108839480000051413673948383714443800519309123592724494953427039811201064341234954387521525390615504949092187441218246679104731442473022013980160407007017175697317900483275246652938800
> (fib 1000)
43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875
>

答えが出るのに全く待たない。これ凄い。