ruby - 为什么 Math.sqrt(i*i).floor == i？

Question

我想知道这是不是真的:当我对一个平方整数求平方根时，就像在

f = Math.sqrt(123*123)

我将得到一个非常接近 123 的 float 。由于浮点表示精度，这可能类似于 122.99999999999999999999 或 123.000000000000000000001。

因为 floor(122.999999999999999999) 是 122，我应该得到 122 而不是 123。所以我希望 floor(sqrt(i*i)) == i-1 在大约 50% 的情况下。奇怪的是，对于我测试过的所有数字，floor(sqrt(i*i) == i。这是一个用于测试前 1 亿个数字的小 ruby​​ 脚本:

100_000_000.times do |i|
  puts i if Math.sqrt(i*i).floor != i
end

上面的脚本从不打印任何东西。为什么？

更新:感谢您的快速回复，这似乎是解决方案:根据 wikipedia

Any integer with absolute value less than or equal to 2^24 can be exactly represented in the single precision format, and any integer with absolute value less than or equal to 2^53 can be exactly represented in the double precision format.

Math.sqrt(i*i) 从 i=9007199254740993 开始按照我的预期运行，即 2^53 + 1。

Answer 1

这是你困惑的本质:

Due to floating point representation precision, this could be something like 122.99999999999999999999 or 123.000000000000000000001.

这是错误的。在符合 IEEE-754 标准的系统上，它总是恰好是 123，这几乎是现代的所有系统。浮点运算没有“随机误差”或“噪声”。它具有精确的、确定性的舍入，许多简单的计算(比如这个)根本不会产生任何舍入。

123 可以精确表示为 float ，123*123 也是如此(所有 中等大小的整数也是如此)。因此当您将 123*123 转换为浮点类型时不会发生舍入错误。结果完全 15129。

根据 IEEE-754 标准，平方根是正确舍入的运算。这意味着如果有一个确切的答案，则需要平方根函数来产生它。由于您要对 exactly 15129 求平方根，即 exactly 123，因此 exactly 从平方根函数得到的结果。不进行舍入或近似。

现在，对于多大的整数，这将是正确的？

double 可以准确表示 2^53 以内的所有整数。因此，只要 i*i 小于 2^53，您的计算中就不会发生舍入，因此结果将是准确的。这意味着对于所有小于 94906265 的 i，我们知道计算是准确的。

但是你试过 i 比那个大!发生了什么事？

对于您尝试过的最大 i，i*i 仅略大于 2^53 (1.1102... * 2^53，实际上)。因为从整数到 double 的转换(或 double 乘法)也是正确舍入操作，i*i 将是最接近 i 精确平方的可表示值。在这种情况下，由于 i*i 是 54 位宽，舍入将发生在最低位。因此我们知道:

i*i as a double = the exact value of i*i + rounding

其中 rounding 是 -1,0 或 1。如果四舍五入为零，则平方是精确的，因此平方根是精确的，所以我们已经知道您得到了正确答案。让我们忽略这种情况。

现在我们要计算 i*i +/- 1 的平方根。使用泰勒级数展开，此平方根的无限精确(未四舍五入)值为:

i * (1 +/- 1/(2i^2) + O(1/i^4))

如果你以前没有做过任何浮点错误分析，现在这有点繁琐，但如果你使用 i^2 > 2^53 这个事实，你可以看到的:

1/(2i^2) + O(1/i^4)

term 小于 2^-54，这意味着(因为平方根被正确舍入，因此它的舍入误差必须小于 2^54)，舍入 sqrt 的结果函数正是 i。

事实证明(通过类似的分析)，对于任何可精确表示的 float x，sqrt(x*x) 正好是 x(假设 x*x 的中间计算没有不会溢出或下溢)，因此您遇到此类计算舍入的唯一方法是在 x 本身的表示中，这就是为什么您看到它从 2^53 开始+ 1(不可表示的最小整数)。