[求助] 无理数的近似替代问题

这是一个Brute force的算法，虽然能用但是实在太慢了。诚心求问更好的算法
（这里的n = 262136，r = log10(2)）

不懂，问了下gpt
综述：
数列{a_n}和{b_n}采用如下表示但根据问题描述，这里还需使用floor函数对结果向下取整：
a_n = {floor(i * r)}
b_n = {floor(i * p / q)}
其中，r是一个无理数，0 < r < 1；i是正整数，满足1 ≤ i ≤ n；p和q是非负整数。
问题是寻找一种方法使得通过调整p和q能使得数列a_n和b_n完全相同。求一种快速算法找到满足条件的最小值q。
回答：
本问题没有已知的通用快速算法来可靠地找到使两数列完全相同的最小q值。所涉及的约束和条件意味着需要进行一定程度的穷举或试错方法来找到可能的p和q值，这将使时间复杂度增加。
一种可能的非通用启发式算法是从q = 1开始，不断递增q。对于每个q值，尝试找到使数列完全相同的非负整数p。当找到这样的值时，返回当前的q。
然而请注意，此启发式算法可能无法保证找到正确的最小q，并且时间复杂度可能相当高。对于某些数列和r值，可能需要尝试大量的q值才能找到合适的p和q。这意味着对于某些特定数量级的问题，此算法可能不具备实用性。

已经开始连题目都看不懂了
我猜你要找的是实数r满足特定条件的最佳分数表示？
可以展开成连分数

大概是这样
然后找到边界迭代次数，使得第i次迭代的分数形式不满足条件，而第i+1次迭代满足
那么q就在这二者之间，接下来想办法牛顿迭代或者二分去找

p 可表示成 q*r 吧

不懂这块，但是我在arxiv上找到一篇论文可能有点帮助网页链接 标题是 无理数的最佳有理逼近

暴力计算好像也不是很慢吧

虽然不是问题的答案，不过还是想提一下，如果不考虑 r 的性质、精度等，只把 r 当作一个 double 来看的话，完全可以用位操作手动模拟浮点数乘法，这样会比直接用浮点数计算稍微快一点（且可以避免由浮点乘法的"误差"导致值的向上舍入），如图：
这里用了乘法+右移来代替除法，因为整数除法实在是太慢了（某些情况下甚至比浮点数除法还慢），基准测试如图：

如果 p/q 是以r 为基准，或者说：
p/q = r
那么，可不可以把r截断？
截断前n位，翻译一个 p/q ？

也许你可以考虑用一个数学软件来计算，我这里摸了一个暴力穷举的代码来求 q，时间复杂度是线性的，但是常数非常大（毕竟基于具有无限精度的符号系统来计算是有代价的），你图中的例子结果如下：虽然这样能得出理论最优结果，但实际是没什么用的，因为太容易引入误差，从而导致计算得到的 Beatty sequence 出错。