お詫び - フィボナッチ数列と繰り返し回数の評価

申し訳ないことをしたのでフィボナッチ数列で一ネタ書きます.
計算量解析の基礎で良く出てくる問題なので知っている人はスルーしてください. フィボナッチ数列ユークリッドの互除法の繰り返し回数を評価するネタです.

以下, F_1=1, F_2=1, F_i=F_{i-1}+F_{i-2} (i=3,4,...)とします.
一般項はdankogaiのところにある通り,
F_n=\frac{1}{\sqrt{5}} \left(\left(\frac{1+\sqrt{5}}{2}\right)^n-\left(\frac{1-\sqrt{5}}{2}\right)^n\right)
です.
\phi=\frac{1+\sqrt{5}}{2}とおきます.

ユークリッドの互除法フィボナッチ数列の関係について

自然数a>bの最大公約数を求めるためにユークリッドの互除法があります. 皆さんご存知の通り, 以下のように計算を行います.
まずr_1=a, r_2=bとします.

  • r_1 = q_1 * r_2 + r_3
  • r_2 = q_2 * r_3 + r_4
  • ...
  • r_{k-1}=q_{k-1}*r_k + r_{k+1}
  • r_k = q_k * r_{k+1}+0

と割り切れるようになるまで続けて, gcd(a,b)=r_{k+1}です.
さて, r_{k+1}がgcdだったとしましょう. 何回割り算を行うと割り切れるようになるのでしょうか?

r_k\geq 2, r_{k+1}\geq 1に注意すると, a\geq F_{k}が言えます.
q_i \geq 1を踏まえて漸化式を考えると,

  • a=r_1 = q_1 * r_2 + r_3 \geq F_{k}=F_{k-1}+F_{k-2}
  • r_2 = q_2 * r_3 + r_4 \geq F_{k-1}=F_{k-2}+F_{k-3}
  • ...
  • r_{k-1}=q_{k-1}*r_k + r_{k+1} \geq F_4=F_3+F_2
  • r_k = q_{k} * r_{k+1}+0 \geq F_3=F_2+F_1=2
  • r_{k+1} \geq 1 = F_2

よってa=r_1\geq F_{k}が示せました.

さて, フィボナッチ数列の一般項は上に書いたとおりで,
Wikipediaから引くと, F_i=\lfloor \frac{\phi^i}{\sqrt{5}} + \frac{1}{2} \rfloor \geq \frac{\phi^i}{\sqrt{5}}-1が言えます.
よってa \geq {\phi}^{k}/\sqrt{5}-1が成立し, ある正の定数cについて\log_2{a} \geq c k. 以上よりaの2進表記時の桁数をkとしたときに, 繰り返しの回数は高々O(k)回であることが分かります.

補遺

"Euclid's GCD algorithm is not optimal"という論文があった筈なのだが見当たらない.