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

发布于 2024-08-17 23:09:06 字数 917 浏览 2 评论 0原文

我想知道这是否属实：当我取平方整数的平方根时，就像在中一样，

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）开始按照我的预期运行。

原文

I am wondering if this is true: When I take the square root of a squared integer, like in

f = Math.sqrt(123*123)

I will get a floating point number very close to 123. Due to floating point representation precision, this could be something like 122.99999999999999999999 or 123.000000000000000000001.

Since floor(122.999999999999999999) is 122, I should get 122 instead of 123. So I expect that floor(sqrt(i*i)) == i-1 in about 50% of the cases. Strangely, for all the numbers I have tested, floor(sqrt(i*i) == i. Here is a small ruby script to test the first 100 million numbers:

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

The above script never prints anything. Why is that so?

UPDATE: Thanks for the quick reply, this seems to be the solution: According to 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) starts to behave as I've expected it starting from i=9007199254740993, which is 2^53 + 1.

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

情丝乱 2024-08-24 23:09:06

这是您困惑的本质：

由于浮点表示
精度，这可能是某事
例如 122.99999999999999999999 或
123.000000000000000000001。

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

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

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

现在，对于多大的整数来说，这才成立呢？

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

但你尝试了比这更大的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

其中舍入是-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)

项小于2^-54，这意味着（由于平方根被正确舍入，因此其舍入误差必须小于2^54），< sqrt 函数的舍入结果恰好是 i。

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

Here's the essence of your confusion:

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

This is false. It will always be exactly 123 on a IEEE-754 compliant system, which is almost all systems in these modern times. Floating-point arithmetic does not have "random error" or "noise". It has precise, deterministic rounding, and many simple computations (like this one) do not incur any rounding at all.

123 is exactly representable in floating-point, and so is 123*123 (so are all modest-sized integers). So no rounding error occurs when you convert 123*123 to a floating-point type. The result is exactly 15129.

Square root is a correctly rounded operation, per the IEEE-754 standard. This means that if there is an exact answer, the square root function is required to produce it. Since you are taking the square root of exactly 15129, which is exactly 123, that's exactly the result you get from the square root function. No rounding or approximation occurs.

Now, for how large of an integer will this be true?

Double precision can exactly represent all integers up to 2^53. So as long as i*i is less than 2^53, no rounding will occur in your computation, and the result will be exact for that reason. This means that for all i smaller than 94906265, we know the computation will be exact.

But you tried i larger than that! What's happening?

For the largest i that you tried, i*i is just barely larger than 2^53 (1.1102... * 2^53, actually). Because conversions from integer to double (or multiplication in double) are also correctly rounded operations, i*i will be the representable value closest to the exact square of i. In this case, since i*i is 54 bits wide, the rounding will happen in the very lowest bit. Thus we know that:

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

where rounding is either -1,0, or 1. If rounding is zero, then the square is exact, so the square root is exact, so we already know you get the right answer. Let's ignore that case.

So now we're looking at the square root of i*i +/- 1. Using a Taylor series expansion, the infinitely precise (unrounded) value of this square root is:

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

Now this is a bit fiddly to see if you haven't done any floating point error analysis before, but if you use the fact that i^2 > 2^53, you can see that the:

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

term is smaller than 2^-54, which means that (since square root is correctly rounded, and hence its rounding error must be smaller than 2^54), the rounded result of the sqrt function is exactly i.

It turns out that (with a similar analysis), for any exactly representable floating point number x, sqrt(x*x) is exactly x (assuming that the intermediate computation of x*x doesn't over- or underflow), so the only way you can encounter rounding for this type of computation is in the representation of x itself, which is why you see it starting at 2^53 + 1 (the smallest unrepresentable integer).

回复收藏 0 原文

似梦非梦 2024-08-24 23:09:06

对于“小”整数，通常有精确的浮点表示。

回复收藏 0 原文

执笔绘流年 2024-08-24 23:09:06

找到像您所期望的那样崩溃的案例并不难：

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

It's not too hard to find cases where this breaks down as you'd expect:

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

回复收藏 0 原文