在给定分子和分母的范围内，在 0..1 之间找到与给定随机实数最接近的整数分数 [英] Finding the closest integer fraction to a given random real between 0..1, given ranges of numerator and denominator

问题描述

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

Given two ranges of positive integers x: [1 ... n] and y: [1 ... m] and random real R from 0 to 1, I need to find the pair of elements (i,j) from x and y such that x_i / y_j is closest to R.

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

What is the most efficient way to find this pair?

推荐答案

使用 Farey 序列

这是一个简单且数学上漂亮的算法来解决这个问题:运行二分搜索，在每次迭代中，下一个数字由中位数公式(如下)给出.根据法里数列的性质，该数是该区间内分母最小的数.因此，这个序列将始终收敛并且永远不会错过"一个有效的解决方案.

Using Farey sequence

This is a simple and mathematically beautiful algorithm to solve this: run a binary search, where on each iteration the next number is given by the mediant formula (below). By the properties of the Farey sequence that number is the one with the smallest denominator within that interval. Consequently this sequence will always converge and never 'miss' a valid solution.

在伪代码中:

input: m, n, R

a_num = 0, a_denom = 1
b_num = 1, b_denom = 1

repeat:
    -- interestingly c_num/c_denom is already in reduced form
    c_num = a_num + b_num
    c_denom = a_denom + b_denom

    -- if the numbers are too big, return the closest of a and b
    if c_num > n or c_denom > m then
        if R - a_num/a_denom < b_num/b_denom - R then
            return a_num, a_denom
        else
            return b_num, b_denom

    -- adjust the interval:
    if c_num/c_denom < R then
        a_num = c_num, a_denom = c_denom
    else
        b_num = c_num, b_denom = c_denom

goto repeat

即使它的平均速度很快(我有根据的猜测它是 O(log max(m,n)))，但如果 R​​ 接近具有小分母的分数，它仍然会很慢.例如，使用 m = n = 1000000 找到 1/1000000 的近似值将需要一百万次迭代.

Even though it's fast on average (my educated guess that it's O(log max(m,n))), it can still be slow if R is close to a fraction with a small denominator. For example finding an approximation to 1/1000000 with m = n = 1000000 will take a million iterations.

这篇关于在给定分子和分母的范围内，在 0..1 之间找到与给定随机实数最接近的整数分数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！