在给定的分子和分母范围内找到0..1之间给定随机实数的最接近整数分数

Question

给定两个正整数范围x: [1 ... n]和y: [1 ... m]从0到1的随机实数R,我需要从x和y找到元素对(i,j),使得x_i/y_j最接近R.

找到这对的最有效方法是什么？

Answer 1

从a = 0开始,b = 1,A = {最接近a,b到R}.
令c为a和b之间的下一个Farey分数,由c =(num(a)+ num(b))/(denom(a)+ denom(b))给出(确保除以num(c)和denom (c)通过gcd(num(c),denom(c))):
如果c的分子或分母超出输入范围,则输出A并停止.
如果c比A更接近R,则将A设置为c.
如果R在[a,c]中,则设置b = c,否则设置a = c.
转到2.

这在O(1)空间,O(M)时间最差情况和O(log M)平均值中找到最佳近似值.

@John:x = [5],y = [8],R = 3/5.这输出1并停止(在步骤3中),这甚至不是可行的解决方案. (2认同)
@DrXorile：显然仅使用farey 序列不会给您正确的答案。您还需要正确使用算法。文章中的代码不正确。只需运行我的伪代码并获得 17/28。欢迎您找出不同之处。 (2认同)
@Echsecutor：因为两者都是单调增加的，所以当它们中的第一个超出界限时，就没有必要再进一步观察了。 (2认同)

Answer 2

用有理数逼近实数的标准方法是计算连续分数序列(见[1]).在计算系列的部分时限制分母和分母,并且在打破限制之前的最后一个值是非常接近实数的分数.

这将非常快速地找到非常好的近似值,但我不确定这总是会找到最接近的近似值.众所周知

任何收敛[连续分数展开的部分值]比分母小于收敛分数的任何其他分数更接近连续分数

但是可能存在较大分母(仍然低于极限)的近似值,它们是更好的近似值,但不是收敛值.