使用浮点数/双精度除法比较可约分分数

Question

假设我有两个分数：a/b 和 c/d，其中 a、b、c、d 都是大于 0 的整数。使用以下函数检查它们的相等性是否安全？：

bool are_equal_fractions(int a, int b, int c, int d) {  
   return (static_cast<double>(a) / b == static_cast<double>(c) / d);
}

根据另一个问题：如果两个分母均为2的幂次方，我能否比较两个分数，在两个分母均为2的幂次方时可以使用该方法，但在更一般的情况下呢？

- mechatroner

---

从那个问题中得出： "所有IEE754浮点数都表示为M * 2 ^ E，其中M和E都是整数（可能为负）。因此，3 / 4.0和6 / 8.0都恰好等于3 * 2 ^ -2，并且在IEE754格式中完全可表示。" 任意数字都不会很好地适应该方案。为什么不缩小分数，然后直接比较整数或类似的操作呢？ - Matthew Read

你为什么不在整数运算中检查 a*d == b*c？ - Oliver Charlesworth

@OliverCharlesworth，那可能导致整数溢出。 - R Sahu

@RSahu/Christophe - 通过使用宽类型可以避免这个问题（如果不存在相应的宽类型，您可以模拟实现）。 - Oliver Charlesworth

这里是否可以使用std::ratio有所帮助？ - πάντα ῥεῖ

Answer 1

尽管每个整数都可以表示为双精度浮点数，但许多整数比例无法被准确地表示，并且非常相似但略有不同的分数可能会舍入为相同的双精度浮点数。

考虑a=2147483647，b=2147483646，c=2147483646，d=2147483645。即使在最简形式下，2147483646/2147483645的分母也将是5的倍数。2147483647/2147483646的分母不是5的倍数，因此它们不相等。

cout << are_equal_fractions(2147483647, 2147483646, 2147483646, 
        2147483645) << endl; 

输出结果为“1”。

通常，此模式中相等的分数意味着：

(i+2)/(i+1) == (i+1)/i
i*(i+2) == (i+1)*(i+1)
i^2 + 2*i == i^2 + 2*i + 1
0 == 1

这个问题没有解决方案。

按照这种模式，最小的反例是are_equal_fractions(67114658,67114657,67114657,67114656)。我认为没有其他模式能够得到更接近非等比例的比率，所以对于小于此情况的值来说，应该是安全的。

- Patricia Shanahan

---

谢谢，这真的很有用。你是怎么想出这个下限的？ - mechatroner

@mechatroner 暴力破解。我运行了一个程序，测试are_equal_fractions(i + 2, i + 1, i + 1, i)在从一开始的每个值的情况下，直到获得真实结果。 - Patricia Shanahan

我在 https://dev59.com/AcXsa4cB1Zd3GeqPOgX7#73394324 上提供了证明，证明你的例子是最坏（最好？）情况：对于绝对值被限制在 67114657 的 a、b、c 和 d，由于 IEEE 754 binary64 双精度浮点数保证 a/b == c/d 作为分数，因此 a/b == c/d。 - Mark Dickinson