次数nのFareyシーケンスを決定する最も効率的な方法は何ですか？

Question

私はおそらく、繰り返し有理数に限定された精度のユーザー入力を変換するためのファレイ分数近似を実装するつもりです。
http://mathworld.wolfram.com/FareySequence.html

私は簡単に順番に最も近いファレイ分数を見つけることができます、と私は再帰的シュテルン - Brocotツリーを構築することにより、メディアント画分を検索することで、Fnを見つけることができます。しかし
http://mathworld.wolfram.com/Stern-BrocotTree.html

、私はFnは非常に非効率的と思われる順に留分を見つけるために作ってみた方法：
（擬似）

For int i = 0 to fractions.count -2 
{ 
    if fractions[i].denominator + fractions[i+1].denominator < n 
    {  
     insert new fraction(
      numerator = fractions[i].numerator + fractions[i+1].numerator 
      ,denominator = fractions[i].denominator + fractions[i+1].denominator) 
      //note that fraction will reduce itself 
     addedAnElement = true 
    } 
} 
if addedAnElement 
    repeat 

私はほとんど常にシーケンスを定義しますFN N = M> 1

だから、おそらくそれが配列を一度構築し、それをキャッシュするのが最善かもしれない10^M ...しかし、それを導き出すためのより良い方法があるはずのように、それはまだいるようです。

EDIT：
本論文では、有望なアルゴリズムがあります。
http://www.math.harvard.edu/~corina/publications/farey.pdf

を私が実装しようとします。
トラブルは、彼らの「最も効率的」アルゴリズムは前に2つの要素を知っている必要があることです。私は、任意の配列の要素1が1である知っている/ Nが、2番目の要素がチャレンジだ...

EDIT2見つける：
私はこれを見落としかどうかはわかりません：F0 = 1/nで考える
を
X> 2の場合、
F1 = 1 /（N-1）

は従って全てのn> 2の場合は、最初の2つの画分を常に
1/N、1 /（N-1）であり、そして私はPatrascuからソリューションを実装できます。

はだから今、私たちはこの質問への答えは、このソリューションがあるかのベンチマークを使用して最適ではないことを証明する必要があります。..ファレイ配列中の

Answer 1

近隣画分をSECに説明されています。 Farey Subsequencesの隣接分数のうちの3つ、http://arxiv.org/abs/0801.1981。

Answer 2

なぜあなたはまったくファレイシリーズが必要なのでしょうか？ continued fractionsを使用すると、系列をあらかじめ計算することなく、同じ近似をオンラインで得ることができます。