确定n级Farey序列的最有效方法是什么？

我将实现一个Farey分数近似值，用于将有限精度的用户输入转换为可能重复的有理数。
http://mathworld.wolfram.com/FareySequence.html 确定n级Farey序列的最有效方法是什么？

我可以轻松地找到最近的法里分数的顺序，我可以通过建立斯特恩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 = 10^m其中m> 1

所以也许最好是一次构建序列并缓存它......但似乎应该有更好的方法来推导它。

编辑：
本文有前途的算法：
http://www.math.harvard.edu/~corina/publications/farey.pdf

我会努力实现。
麻烦的是，他们的“最有效”的算法需要知道前两个元素。我知道任何序列的元素之一是1/n，而是找到第二个元素似乎是一个挑战......

EDIT2：
我不知道我怎么忽略了这一点：
鉴于F0 = 1/N
如果x> 2然后
F1 = 1 /（N-1）

因此对于所有的n> 2，前两个级分将总是
1/N，1 /（N-1）和我可以从Patrascu实施解决方案。

所以，现在，我们在这个问题的答案应该证明，这种解决方案或使用基准测试是不是最佳..

来源

2011-11-04 Matthew

在法里数列周边馏分二段描述。 Farey子序列中的邻近分数的3个，http://arxiv.org/abs/0801.1981。

来源

2011-11-07 11:38:11 Rory

确定邻居已在我发布的论文中解决。这个问题是关于确定整个集合的方法的效率。确定这个集合的数学是微不足道的，我对这个方法的效率感兴趣。虽然良好的联系！ – Matthew

为什么你需要Farey系列呢？使用continued fractions可以在不预先计算系列的情况下在线提供相同的近似值。

来源

2011-11-13 12:00:54 Vlad

你能用这种方法向我展示一个有理近似的实现吗？ – Matthew

那么，我没有_implementation_那个。但是它可以很容易地做到这一点：（1）你计算输入数的连续分数（在这里描述）（http://en.wikipedia.org/wiki/Continued_fraction#Calculating_continued_fraction_representations），对于理性输入，算法是有限）; （2）你截断连续分数（[here]（http：//en.wikipedia。org/wiki/Continued_fraction＃Best_rational_approximations）有更多细节和算法：不是每个截断都是合适的），并将其扩展为有理数。 – Vlad

或者您可以将用户输入解释为一个时间间隔，然后查看[部分]（http://en.wikipedia.org/wiki/Continued_fraction#Best_rational_within_an_interval）中的实现。该算法描述的是细节。 – Vlad

确定n级Farey序列的最有效方法是什么？

回答

相关问题