実行例
フィボナッチ数列を拡張ユークリッドアルゴリズムに入力します。
N = 10
r[0] = f[10] = 89
r[1] = f[9] = 55
(r[ 0], x[ 0], y[ 0]) = ( 89, 1, 0)
(r[ 1], x[ 1], y[ 1]) = ( 55, 0, 1)
(r[ 2], x[ 2], y[ 2]) = ( 34, 1, -1)
(r[ 3], x[ 3], y[ 3]) = ( 21, -1, 2)
(r[ 4], x[ 4], y[ 4]) = ( 13, 2, -3)
(r[ 5], x[ 5], y[ 5]) = ( 8, -3, 5)
(r[ 6], x[ 6], y[ 6]) = ( 5, 5, -8)
(r[ 7], x[ 7], y[ 7]) = ( 3, -8, 13)
(r[ 8], x[ 8], y[ 8]) = ( 2, 13, -21)
(r[ 9], x[ 9], y[ 9]) = ( 1, -21, 34)
(r[10], x[10], y[10]) = ( 0, 55, -89)
(89) * (-21) + (55) * (34) = 1
N = 11
r[0] = f[11] = 144
r[1] = f[10] = 89
(r[ 0], x[ 0], y[ 0]) = ( 144, 1, 0)
(r[ 1], x[ 1], y[ 1]) = ( 89, 0, 1)
(r[ 2], x[ 2], y[ 2]) = ( 55, 1, -1)
(r[ 3], x[ 3], y[ 3]) = ( 34, -1, 2)
(r[ 4], x[ 4], y[ 4]) = ( 21, 2, -3)
(r[ 5], x[ 5], y[ 5]) = ( 13, -3, 5)
(r[ 6], x[ 6], y[ 6]) = ( 8, 5, -8)
(r[ 7], x[ 7], y[ 7]) = ( 5, -8, 13)
(r[ 8], x[ 8], y[ 8]) = ( 3, 13, -21)
(r[ 9], x[ 9], y[ 9]) = ( 2, -21, 34)
(r[10], x[10], y[10]) = ( 1, 34, -55)
(r[11], x[11], y[11]) = ( 0, -89, 144)
(144) * (34) + (89) * (-55) = 1
に改良できたように、
まだ改良の余地があることもあるのですが、
ユークリッドのアルゴリズムは入力がフィボナッチ数列だと本当に計算量が $O(\log^2 a)$ になりますので、
これが最良ということになります。