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

Question

我想知道这是否属实:当我取平方整数的平方根时,就像在

f = Math.sqrt(123*123)

我会得到一个非常接近的浮点数123.由于浮点表示精度,这可能类似于122.99999999999999999999或123.000000000000000000001.

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

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

上面的脚本从不打印任何内容.为什么会这样？

更新:感谢快速回复,这似乎是解决方案:根据维基百科

绝对值小于或等于2 ^ 24的任何整数都可以用单精度格式精确表示,绝对值小于或等于2 ^ 53的任何整数都可以用双精度格式精确表示.

Math.sqrt(i*i)开始表现得像我预期的那样从i = 9007199254740993开始,即2 ^ 53 + 1.

Answer 1

这是你困惑的本质:

由于浮点表示精度,这可能类似于122.99999999999999999999或123.000000000000000000001.

这是错误的.在符合IEEE-754标准的系统上,它总是正好是123,这几乎是现代的所有系统.浮点运算没有"随机错误"或"噪音".它具有精确的,确定性的舍入,并且许多简单的计算(像这一个)根本不会产生任何舍入.

123在浮点中是完全可表示的,所以123*123(所有中等大小的整数都是如此).因此,转换123*123为浮点类型时不会发生舍入错误.结果是完全正确的 15129.

根据IEEE-754标准,平方根是正确的舍入操作.这意味着如果有确切的答案,则需要平方根函数来生成它.既然你正在服用的平方根准确 15129,这是确切 123,这正是你的平方根函数得到的结果.不会发生舍入或近似.

现在,这个整数有多大？

双精度可以精确地表示最多2 ^ 53的所有整数.因此,只要i*i小于2 ^ 53,计算中就不会出现舍入,因此结果将是准确的.这意味着对于所有i小于94906265,我们知道计算将是精确的.

但是你试过i比这更大!发生了什么？

对于i你尝试过的最大的,i*i只是勉强大于2 ^ 53(1.1102... * 2^53实际上).因为从整数到双精度的转换(或双倍乘法)也是正确的舍入运算,所以i*i将是最接近精确平方的可表示值i.在这种情况下,由于i*i是54位宽,所以舍入将发生在最低位.因此我们知道:

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

其中,rounding要么是-1,0, or 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.

事实证明(对于类似的分析),对于任何可精确表示的浮点数x,sqrt(x*x)正好是x(假设中间计算x*x不会过度或下溢),所以唯一的方法就是你可以遇到这种类型的计算的舍入是在其x自身的表示中,这就是为什么你看到它开始于2^53 + 1(最小的不可表示的整数).

Answer 2

对于"小"整数,通常有一个精确的浮点表示.

Answer 3

找到像你期望的那样崩溃的情况并不难:

Math.sqrt(94949493295293425**2).floor
# => 94949493295293424
Math.sqrt(94949493295293426**2).floor
# => 94949493295293424
Math.sqrt(94949493295293427**2).floor
# => 94949493295293424