Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Why is Math.sqrt(i*i).floor == i?

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.

like image 515
martinus Avatar asked Jan 13 '10 21:01

martinus


People also ask

Why do we use sqrt in math?

Math. sqrt() method returns a double value which is the square root of the given value and is a correctly rounded positive number. If the argument is NaN and negative number (or negative infinity) Math.

Does math sqrt return a double?

The sqrt function returns a double value (for natural reasons which I'm sure that you understand). This value is typically represented in 8 bytes, in floating-point format (as specified by the standard). It doesn't have decimal digits in the way that you see them.

How do you find square root without inbuilt function?

if you need to find square root without using sqrt() ,use root=pow(x,0.5) . Where x is value whose square root you need to find.

What is Floor value of square root?

Floor square root of a number is the greatest whole number which is less than or equal to its square root. Explanation: Square root of 25 = 5. Therefore 5 is the greatest whole number less than equal to Square root of 25.


2 Answers

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).

like image 97
Stephen Canon Avatar answered Oct 29 '22 01:10

Stephen Canon


For "small" integers, there is usually an exact floating-point representation.

like image 21
Anon. Avatar answered Oct 29 '22 01:10

Anon.