私がどう納得しているかも書いておく必要があろう. xiが次々と置かれていく様子を添字だけで再掲する.
i | T0 | 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 |
i | T0 | 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 |
TAOCPでは演習問題3.1-7にこの話があり, その解答には
xnが表Tρnに格納されると, それはその後xn+1, xn+2, ..., xn+2ρn+1と比較される.
と記載してあるが, 上の説明の方が分り易いと私は思っている.
Gosperの元の記事はHAKMEM 132 (