algorithm - 最大的除数使得两个数除以它四舍五入到相同的值？

Question

我有一个算法可以解释为将数字线分成相等数量的 block 。为简单起见，我将坚持 [0,1)，它将像这样划分:

0|----|----|----|----|1

我需要做的是获取一系列数字 [j,k) 并找到最大个 block ，N，直到某个最大 M，这将划分数字行[j,k) 仍然都属于同一个“bin”。这比听起来更棘手，因为范围可以像这样跨越垃圾桶:

    j|-|k
0|----|----|----|----|1

因此在完全包含范围之前，您可能必须达到相当低的数字。更重要的是，随着 bin 数量的增加，范围可能会移入和移出单个 bin，因此存在局部最小值。

显而易见的答案是从 M 个 bin 开始，然后减少数量直到范围落入一个 bin 中。但是，我想知道是否有比枚举所有可能的除法更快的方法，因为我的最大数目可以相当大(8000 万左右)。

有更好的算法吗？

Answer 1

在这里我想给出另一个启发式，它不同于 btilly 的。

任务是找到整数 m和 n这样 m / n <= j < k <= (m + 1) / n , 与 n尽可能大(但仍低于 M )。

直觉上，分数 m / n 更可取靠近j .这导致了使用 continued fractions 的想法.

我提出的算法非常简单:

1. 计算j的所有连分数使用减号(这样分数总是从上面接近j)，直到分母超过M ;
2. 对于每个这样的分数m / n , 找出最大的整数 i >= 0这样 k <= (m * i + 1) / (n * i)和 n * i <= M , 并替换分数 m / n与 (m * i) / (n * i) ;
3. 在 2 的所有分数中，找出分母最大的分数。

算法在j 中不对称和 k .因此有一个类似的 k -version，一般情况下不应该给出相同的答案，以便您可以从两个结果中选择较大的一个。

---

例子:这里我以btilly的例子:j = 0.6和 k = 0.65 , 但我会选择 M = 10 .

我将首先浏览 j -程序。计算 j 的连分数展开式，我们计算:

  0.6
= 0 + 0.6
= 0 + 1 / (2 - 0.3333)
= 0 + 1 / (2 - 1 / (3 - 0))

自 0.6是有理数，展开会在无穷多步后终止。相应的分数是:

0 = 0 / 1
0 + 1 / 2 = 1 / 2
0 + 1 / (2 - 1 / 3) = 3 / 5

计算对应的i在第 2 步中，我们将三个派系替换为:

0 / 1 = 0 / 1
1 / 2 = 3 / 6
3 / 5 = 6 / 10

最大分母由 6 / 10 给出.

---

继续上面的例子，对应的k -程序如下:

  0.65
= 1 - 0.35
= 1 - 1 / (3 - 0.1429)
= 1 - 1 / (3 - 1 / (7 - 0))

因此相应的分数:

1 = 1 / 1
1 - 1 / 3 = 2 / 3
1 - 1 / (3 - 1 / 7) = 13 / 20

通过第 2 步，我们得到:

1 / 1 = 2 / 2
2 / 3 = 6 / 9
13 / 20 = 0 / 0 (this is because 20 is already bigger than M = 10)

最大分母由 6 / 9 给出.

---

编辑:实验结果。

令我惊讶的是，该算法的效果比我想象的要好。

我用绑定(bind) M 做了下面的实验忽略(等效地，一个人可以取 M 足够大)。

在每一轮中，我都会生成一对 (j, k)区间内均匀分布的随机数 [0, 1)与 j < k .如有差异k - j小于 1e-4 ，我丢弃了这对，使这一轮无效。否则我计算出真正的结果 trueN使用朴素算法，并计算启发式结果heurN使用我的算法，并将它们添加到统计数据中。这适用于 1e6 轮。

结果如下:

effective round     =  999789
sum of trueN        =  14013312
sum of heurN        =  13907575
correct percentage  =  99.2262 %
average quotient    =  0.999415

correct percentage是有效回合的百分比 trueN等于heurN , 和 average quotient是商的平均值 heurN / trueN对于所有有效回合。

因此该方法在 99% 以上的情况下给出了正确答案。

我还用较小的 M 做了实验值，结果相似。