C++中John Kennedy迭代算法实现小数转分数的类型转换问题

问题背景 #

我正在进行个人练习项目，目标是实现John Kennedy迭代算法完成小数转分数功能，需要创建Fraction(long, long)类和Fraction doubleToFraction(double)函数。当前核心问题是：迭代中z为double类型实数，分母D、分子N为long类型整数，频繁遇到溢出和类型转换误差问题。

现有实现尝试 #

基础迭代代码 #

最初的核心迭代逻辑：

do
{
    z = 1.0 / (z - floor(z));
    Di = denominator;
    denominator = Di * floor(z) + previousDenominator;

    previousNumerator = numerator;
    numerator = round(value * denominator);

    previousDenominator = Di;

    diff = abs(numerator / denominator - value);
    zdiff = abs(z - floor(z));
}
while (diff > maxError && zdiff > maxError);

首次溢出处理尝试 #

针对类型转换和溢出问题，我将分子/分母设为long类型并添加溢出检查，但仅在首次迭代未失败且Di * floor(z)未溢出时有效：

double z = value;
long previousDenominator = 0, previousNumerator = 0;
long denominator = 1;
long numerator = 0, Di = 0;
double diff, zdiff;

do
{
    z = 1.0 / (z - floor(z));
    Di = denominator;
    denominator = Di * floor(z) + previousDenominator;

    previousNumerator = numerator;
    numerator = round(value * denominator);

    if(numerator < 0){  // 通过负数判断溢出（long溢出后可能变为负数）
        numerator = previousNumerator;
        denominator = Di;
        break;
    }

    previousDenominator = Di;

    diff = abs(numerator / denominator - value);
    zdiff = abs(z - floor(z));
}
while (diff > maxError && zdiff > maxError);

全程double计算的末尾处理尝试 #

尝试全程用double类型计算，把溢出问题留到算法末尾处理，但返回的分数与预期误差极大：

}
while (diff > maxError && zdiff > maxError);

if(max(numerator,denominator) > LONG_MAX){
    double comm = floor(max(numerator,denominator) / LONG_MAX);
    numerator = floor(numerator/comm);
    denominator = ceil(denominator/comm);
}

return Fraction((long)numerator * sign, (long)denominator);

具体测试问题 #

• 测试值944.00000000351042：首次迭代中z为284866021.83457476，分母计算为284866021，分子268913523825超过LONG_MAX，导致首次迭代失败，返回Fraction(0,1)。即使将maxError设为≤1e-8，仍会遇到其他首次迭代就分子溢出的数值，我希望尽可能把maxError设得更小。
• 测试值4865998.0002105972：同样存在问题，要规避需将maxError设到1e-3以下，这显然不符合需求。

优化思路 #

1. 提前预判溢出，终止无效迭代 #

在计算denominator = Di * floor(z) + previousDenominator前，先做溢出检查：

• 提取floor(z)的整数部分k，若k > 0，检查Di > LONG_MAX / k，若成立则乘法会溢出，直接终止迭代，返回当前最接近的有效分数。
• 再检查加法溢出：Di * k > LONG_MAX - previousDenominator，避免加法导致的溢出。

2. 改用高精度中间类型，最后约分转换 #

中间计算时用long long存储分子分母（若环境中long long范围大于long），最后转换为long前：

• 先计算分子分母的最大公约数（GCD），约分后再判断是否在LONG_MAX范围内。
• 若仍超出范围，可尝试逐步缩小分母（同时按比例调整分子），直到符合long类型范围，同时保证误差在maxError内。

3. 调整迭代终止条件，优先控制数值范围 #

在循环条件中加入对分母大小的限制，预留足够空间避免后续溢出：

while (diff > maxError && zdiff > maxError && denominator < LONG_MAX / 2)

当分母接近LONG_MAX的一半时提前终止，避免后续乘法直接溢出。

4. 用连分数递推公式计算分子，避免浮点数误差 #

不要用round(value * denominator)计算分子，改用连分数的整数递推公式：

// 对应分母递推：denominator = k * previousDenominator + previousPreviousDenominator
numerator = k * previousNumerator + previousPreviousNumerator;

用整数递推精度更高，也更容易提前检查溢出。

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