■連分数の測度論(その36)

 ユークリッドの互除法の解析を続ける.

 ユークリッドの互除法が最悪の場合は隣接するフィボナッチ数である場合に生じることになる.その場合の除算ステップは高々

  [log(3−φ)N/logφ]

である.

(証)u=Fn+1,u=Fn (modv)

   Fn+1<N→φ^n+1/√5<N→φ^n<√5/φ・N=(3−φ)N

===================================

 除算ステップの回数は

  [log(3−φ)N/logφ]

=2.078lnN+.6723

=4.785log10N+.6723

=4.8log10N−0.32

を超えないのである.

===================================