近似分数の生成アルゴリズム

本節では無理数wの範囲に制限はしない．無理数w で定まる格子Λ(w, c)の近似格子点を生成していくアルゴリズムをヒントとして，wの近似既約分数を生成するアルゴリズムが考えられる．

■ファレイ対

これまでのように既約分数の分母は正とする．このとき任意の有理数は一意的に既約分数の形に表すことができる．ただし整数の分母は1とする．

二つの有理数r1, r2 (r2 < r1)がある．r1, r2を既約分数の形に表

13.4. 近似分数の生成アルゴリズム 55

しそれを

r1 = a

b, r2 = c d

とする．ad−bc = 1となるとき，有理数の順序対(r2, r1)をファ

レイ対(Farey pair) と言うことにする．ただしこれは一般に使わ

れている用語ではない．またファレイ対(r₂, r₁)と無理数wがあり r₂< w < r₁となるとき，(r₂, r₁)をwを挟むファレイ対という．

ファレイ対(r₂, r₁)よりつくられる有理数M(r₂, r₁)を次のよう定める．すなわち

M(r2, r1) = a+c b+d

と定め，これをファレイ対(r₂, r₁)の中間数(mediant)という．

a(b+d)−b(a+c) = 1よりa+c

b+dもまた既約分数である．

r₂< M(r₂, r₁)< r₁ であり，

(r₂, M(r₂, r₁)), (M(r₂, r₁), r₁) はともにファレイ対となる．

■無理数の近似分数列を作る．

無理数wに対して

α₀ = [w], α₁= [w]−1

とおく．(α1,α0)はwを挟むファレイ対である．次に α₂ =M(α₁,α₀)

とおく．ファレイ対(α₁,α₀)のα₀またはα₁をα₂で置き換えて新たなwを挟むファレイ対を作る．この新たなファレイ対の中間数を

56 第13章四つの連分数 α3とおく．このα3を最後に作ったファレイ対の両端のどちらかに置きかえて，さらに区間の幅の狭いwを挟むファレイ対を作る．

以下同様にして有理数の列

α₀,α₁,α₂,· · ·

ができるが，これがwの近似分数全体となる．実際，第8章定義 8.1でΛ(w, c) の近似格子点の列

Y₀, Y₁, Y₂, · · ·

を定義したが，このY_iに対応する近似分数がα_iである．

なおα_iは右端のファレイ対の数と入れ換え，α_i+1は左端の数と入れ換える，というように入れかえる数の左右が変わるとき，α_iは主近似分数である．したがって順に作られていくwを挟むファレイ対の右端あるいは左端の少なくとも一方は主近似分数である．即ち順に作られていくファレイ対の両端を既約分数で表したとき，分母が小さい方はwの主近似分数である．最初に考えたファレイ対 (α₁,α₀)の分母は共に1で，小さいほうは無いがこのときはα= [w]

が0次の主近似分数である．

■無理数を挟む任意のファレイ対無理数wを挟むファレイ対³c

d,a b

´があったとする．d > bのとき

c−a d−b < c

d < a b であるが，

µc−a d−b,a

はまたwを挟むファレイ対である．同様に d < bのときは

µc d,a−c

b−d

がwを挟むファレイ対である．このようにwを挟むファレイ対から始めて，その区間の幅を拡げて新たなファレイ対を作っていくことができる．これは前項で考えたファレ

13.4. 近似分数の生成アルゴリズム 57

イ対の区間の幅を狭めていくアルゴリズムの丁度逆となっている．

この区間の幅を拡げる操作を行っていくと，いつかはファレイ対の両端の既約分数の分母がともに1となり，それは([w]−1,[w])というファレイ対になる．よって無理数wを挟む任意のファレイ対

³c d,a

´は，前項で考えた近似既約分数を作っていくアルゴリズムの途中に出てくるファレイ対である．したがって c

d,a

b ^はwの近似既約分数であり，少なくとも一方は(分母の小さい方は) wの主近似既約分数である．

関連図書