一种最小化伪丢番图方程的快速算法

Question

我们正在寻找一种算法来在 O(N) 内解决这个问题。

给定两个实数 a 和 b （不失一般性，你可以假设它们都在 0 和 1 之间） 找到 -N 和 N 之间的整数 n，使表达式最小化：

|an - b - round(an - b)|

我们认为欧几里得算法可能对此很有效，但无法弄清楚。看起来确实应该有比通过对整数 n 进行穷举搜索更快的方法来做到这一点。

注意：在我们的情况下，a 和 b 可能经常变化，因此可以为查找表修复 a 和 b，但它会变得有点难看，因为 N 也可能变化。还没有详细研究查找表，看看我们能将它作为 N 的函数得到多小。

Answer 1

听起来您可能正在寻找类似连续分数之类的东西......

它们有何关系？假设您可以用有理数 b1/b2 代替 b。现在您正在寻找整数 n 和 m，使得 an-b1/b2 近似为 m。换句话说，您正在寻找 n 和 m，使得 (m+(b1/b2))/n = (mb2+b1)/nb1（一个有理数）近似为 a。设 a1 = mb2+b1 且 a2 = nb1。从连分数近似中找到 a1 和 a2 的值并求解 n 和 m。

另一种方法可能是这样的：

1. 找到 a 和 b 的良好有理近似值：a ~ a1/a2 和 b ~ b1/b2。
2. 求解 n(a1/a2)-(b1/b2) = m，得到 n 和 m。

但我不太确定它会起作用。 a 所需的精度取决于 n 和 b。

Answer 2

您正在有效地搜索整数 N，使表达式 aN - b 尽可能接近整数。 a 和 b 是否固定？如果是，您可以预先计算一个查找表并具有 O(1) :-)

如果不是，请考虑寻找使所有 aN 接近 I + b 的 N整数I。

Answer 3

您可以计算比率 a/b 的连分数。当分母大于 N 或当您的近似值足够好时，您可以停止。

// Initialize:
double ratio = a / b;
int ak = (int)(ratio);
double remainder = ratio - ak;

int n0 = 1;
int d0 = 0;

int n1 = ak;
int d1 = 1;

do {
    ratio = 1 / remainder;
    ak = (int)ratio;
    int n2 = ak * n1 + n0;
    int d2 = ak * d1 + d0;
    n0 = n1;
    d0 = d1;
    n1 = n2;
    d1 = d2;
    remainder = ratio - ak;
} while (d1 < N);

您要查找的 n 值为 d0（如果仍小于 N，则为 d1） 。

这不一定会给您最小的解决方案，但它可能是一个非常好的近似值。

Answer 4

首先，让我们考虑一个更简单的情况，其中b=0且0＜0。一个< 1. F(a,n) = |一轮(an)|

让step_size = 1

Step 1. Let v=a
Step 2. Let period size p = upper_round( 1/v ).
Step 3. Now, for n=1..p, there must be a number i such that F(v,i) < v.
Step 4. v = F(v,i), step_size = stepsize * i
Step 5. Go to step 2

如您所见，您可以将F(v, *) 减少到您想要的任何级别。最终解决方案 n = step_size。