C++中基于int分子分母的double有理逼近误差界咨询

问题结论 #

首先可以明确给出扩展欧几里得算法（你这里本质是用扩展欧几里得求解连分数收敛子）的逼近误差上界，相关结论都是数论中已经严格证明的：

1. 通用绝对误差上界：对于算法输出的有理逼近 p/q，其与原数值 d 的误差满足 |d - p/q| < 1/(q²)，该上界不依赖暴力法的结果。
2. 相对于暴力法最优解的上界：如果暴力法得到的最优解分母 q_opt 不超过你代码中int类型的最大允许分母，那么扩展欧几里得算法输出的收敛子误差满足 r_euclid ≤ 2*r_opt，这正是你示例中提到的误差界形式，可以被严格证明。

原理说明 #

你用扩展欧几里得算法对 round(d*2^30) 和 2^30 求公约数的过程，本质上就是在计算 d 的连分数展开的收敛子：

• 所有连分数收敛子本身就是「最佳有理逼近」：即对于收敛子 p/q，不存在任何分母小于等于 q 的有理分数，能比它更接近原数 d。
• 暴力枚举法得到的全局最优解，要么是连分数的收敛子，要么是两个相邻收敛子之间的半收敛子（中间分数）。

你代码里的实现因为在系数超过int上限时提前终止，所以少数情况下会跳过部分半收敛子，导致和暴力法结果有差异，比如你的测试用例中数值为416934.79214075的情况，欧几里得返回的分母967是收敛子，而暴力法得到的4657是后续的半收敛子。

优化建议 #

你可以对现有扩展欧几里得实现做很小的改动，就能得到和暴力法完全一致的结果，同时保持远高于暴力法的性能：

1. 不要只取最后一个收敛子，把迭代过程中产生的所有收敛子、半收敛子都暂存下来
2. 遍历所有暂存的结果，选出误差最小的一个输出即可
   改动后算法时间复杂度仍然是O(log(max_denominator))，远低于暴力法的O(max_denominator)，在小数值场景下优势会非常明显。

内容的提问来源于stack exchange，提问作者CplusPuzzle