2016年10月5日水曜日

ループ検出

前回のこのタイトルのブログで, Gosper流のループ検出法の説明をしたが, これでループが発見できる理由があれだけではいまいちである.

私がどう納得しているかも書いておく必要があろう. xiが次々と置かれていく様子を添字だけで再掲する.

iT0 T1 T2 T3
1 1
2 1  2
3 3  2
4 3  2 4
5 5  2 4
6 5  6 4
7 7  6 4
8 7  6 4  8
9 9  6 4  8
10 9 10 4  8
これらの表中のxiに, 次のxがあるかどうかを調べるのだが, そこで添字の差だけの表にすると
iT0 T1 T2 T3
1 -1
2 -2  -1
3 -1  -2
4 -2  -3 -1
5 -1  -4 -2
6 -2  -1 -3
7 -1  -2 -4
8 -2  -3 -5  -1
9 -1  -4 -6  -2
10 -2  -1 -7  -3
つまり1つ前2つ前に同じものがあると, それらはT0で見付かり, 3つ前4つ前にあると, それらはT1で見付かり,...というわけだ. Tの添字が大きいほど, 繰り返し開始時のμの値の曖昧さが大きいことがこの表から判明する.

TAOCPでは演習問題3.1-7にこの話があり, その解答には

xnが表Tρnに格納されると, それはその後xn+1, xn+2, ..., xn+2ρn+1と比較される.

と記載してあるが, 上の説明の方が分り易いと私は思っている.

Gosperの元の記事はHAKMEM 132 (http://home.pipeline.com/~hbaker1/hakmem/flows.html#item132)にある.