计算最大公约数

Question

我写了以下函数来计算浮点数的最大公约数，但当我使用输入(111.6, 46.5)运行时，函数中fmod(a,b)的计算在递归调用2次后开始给出错误结果。我无法找到错误所在。有人能发现这里出了什么问题吗？

float gcd(float a, float b){
if (a>b) {
    if(b==0){
        return a;
    }
    else {
        return gcd(b, fmod(a,b));
    }
}
else {
    if (a==0) {
        return b;
    }
    else {
        return gcd(fmod(b,a), a);
    }
}

}

- G K

---

欢迎来到Stack Overflow！请求他人寻找代码错误是不够有效的。你应该使用调试器（或添加打印语句）来分离问题，然后构建一个最小测试案例。 - Oliver Charlesworth

浮点数的gcd是什么意思？我认为这个算法只适用于整数，即使它适用于有理数，也不认为它适用于浮点数。请问您需要翻译哪些内容？ - zch

你期望gcd（111.6，46.5）的值是多少？ - user1055604

@zch：当然，该算法适用于有理数和浮点数。欧几里得最初是针对实数编写的，以线段的形式呈现（《几何原本》第七卷，公元前300年左右：命题1和2）。 - Eric Postpischil

@zch 浮点数是精确的有理数，扩展了无穷大和NaN，即使它们不能表示任何有理数。 - plasmacel

Answer 1

由于浮点数的表示方式，源文本“111.6”被转换为111.599999999999994315658113919198513031005859375，而源文本“46.5”则转换为46.5。然后您的gcd函数返回7.62939453125e-06。这是两个输入值的正确GCD。

请注意，第一个值为14627635/131072。所有浮点数都是某个整数（在一定范围内）乘以或除以2的幂。无法用二进制浮点数精确表示111.6。既然您无法准确表示111.6，那么就无法进行精确算术运算。浮点数主要设计用于近似算术。进行精确算术需要非常小心。

引用：

“谈论实数的最大公约数（而不是整数），这意味着什么？” a和b的最大公约数是最大的数字c，使得a/c和b/c是整数。

- Eric Postpischil

---

@OliCharlesworth：那又怎样？你会因为整数除法中通常不存在两个整数的商（例如1/0）而提出投诉吗？我谈论实数的最大公约数和整数的商一样自在。 - Eric Postpischil

虽然我认为在浮点实现的情况下，a和b必须是有理数，因此最大公约数确实存在... - Oliver Charlesworth

在整数中通常不存在这样的商，这是正确的。但是让我担心的是，对于实数情况的GCD算法几乎完全没有任何实际用途。 - Oliver Charlesworth

@thkala: 不能在浮点数中进行相等性测试的概念是错误的。更正确的说法是，您无法准确计算不精确输入的函数。相等性只是最臭名昭着的例子（“这里有一些接近a和一些接近b的东西。a和b相等吗？”），但其他函数也存在问题（“这里有一些接近a的东西。它可能大于1，即使a不是。a的反正弦是多少？”）。在这种情况下，“gcd”内部的所有数学都是精确的，因此没有不准确性和“==”的问题。 - Eric Postpischil

@thkala：是的，fmod 是精确的，除非它有错误。 fmod 的数学结果始终具有最高位（MSB），不高于其输入中较小值的 MSB，以及最低位（LSB）不低于其输入中较小值的 LSB，因此精确结果始终适合浮点类型。由于可以表示精确结果，因此应返回它。 - Eric Postpischil

Answer 2

float gcd(float a, float b){
    printf("a=%f b=%f\n",a,b);
if (a>b) {
    if(b==0){
        return a;
    }
    else {
        return gcd(b, fmod(a,b));
    }
}
else {
    if (a==0) {
        return b;
    }
    else {
        return gcd(fmod(b,a), a);
    }
}
}
main(){
    printf("%f\ndddeellliiimmiitteerr\n",gcd(1116,465));
    printf("%f\n",gcd(111.6,46.5));
}

所以你可以看到，浮点数并不是那么准确。
你可以尝试使用双精度（但它也有缺陷: ) 或者...了解一下浮点数的存储方式。

- qulinxao