お詫び - フィボナッチ数列と繰り返し回数の評価
申し訳ないことをしたのでフィボナッチ数列で一ネタ書きます.
計算量解析の基礎で良く出てくる問題なので知っている人はスルーしてください. フィボナッチ数列でユークリッドの互除法の繰り返し回数を評価するネタです.
以下, , , (i=3,4,...)とします.
一般項はdankogaiのところにある通り,
です.
とおきます.
ユークリッドの互除法とフィボナッチ数列の関係について
自然数の最大公約数を求めるためにユークリッドの互除法があります. 皆さんご存知の通り, 以下のように計算を行います.
まず, とします.
- ...
と割り切れるようになるまで続けて, gcd(a,b)=です.
さて, がgcdだったとしましょう. 何回割り算を行うと割り切れるようになるのでしょうか?
, に注意すると, が言えます.
を踏まえて漸化式を考えると,
- ...
よってが示せました.
さて, フィボナッチ数列の一般項は上に書いたとおりで,
Wikipediaから引くと, が言えます.
よってが成立し, ある正の定数cについて. 以上よりaの2進表記時の桁数をkとしたときに, 繰り返しの回数は高々O(k)回であることが分かります.
補遺
"Euclid's GCD algorithm is not optimal"という論文があった筈なのだが見当たらない.