How long does Math.sqrt(n).to_i return the correct value for n value?

I'm using Ruby 2.2.1.

when n=1,2,…, Math.sqrt(n).to_i returns the correct value
(i.e., the value of Math.sqrt(m).to_i is [ mm] for all m from 1 to n.)
How much is n?

By the way
When n = 4503599761588224,
Make sure Math.sqrt(n).to_i does not return the correct value.
I ran the following code to find it.

require'bigdecimal/math'
include BigMath

67000000.upto (68000000) {|i|
  n=i*i-1
  if!((BigDecimal.new(n.to_s).sqrt(10)).to_i==Math.sqrt(n).to_i)
    p[n, i, (BigDecimal.new(n.to_s).sqrt(10)).to_i, Math.sqrt(n).to_i]
    break
  end
}

(Additional)
If you're looking for all n=i*i-1 types, the following code is better.

i=2
num = Math.sqrt(i*i-1).to_i
while num==i-1
  i+=1
  num = Math.sqrt(i*i-1).to_i
end
p[i*i-1,i]

Output Results
[4503599761588224,67108865]

ruby

2022-09-29 21:39

3 Answers

I have considered the error before.Since (n+ ^)^2=n^2+2n ++ ^^2, if the (2n ++ 2^2) part is no longer a valid floating-point number compared to the n^2, the result of taking sqrt is n.

Assuming an IEEE double-precision floating-point number, the maximum number to get the correct integer value is:

(2^26-1)^2 = 4503599493152769

Browse: http://blog.practical-scheme.net/gauche/20130319-inexact-sqrt

(However, I don't know exactly what Ruby's to_i specifications are, so I might need to use a different evaluation method.)

Note: You may have misunderstood the conditions of the problem.The number above is "the largest square number in the range where sqrt is taken as an IEEE floating point number does not result in an integer even though it is not originally a square number."

If the problem is to find the largest n such as (1) converting it to a floating point number for a square number n^2 and (2) taking sqrt and (3) rounding up an integer becomes n, then the error may cancel well and have a larger number.I will calculate and add it later.

2022-09-29 21:39

If you calculate 354503599761588224 on a Windows calculator,

67108864.999999992549419514098472

is obtained.
First, Math.sqrt, but return the real number Float, and its effective accuracy is 15 digits at most.Rounding off the 16th digit

67108865.0000000

I guess the price is about the same.That's why it has been rounded up.
BigDecimal is not rounded up because it is more accurate than Float.

Floating-point numbers are approximate numbers, and this is what happens when you perform more accurate operations.

Manyama-san and Shirok-san's numbers are not clear in decimal notation, but in binary notation

4503599493152769 | 0000111111111111111111111000000000000000000000000001
4503599761588223 | 0001000000000000000000000000000001111111111111111111111111
4503599761588224 | 000100000000000000000000000000000000000000000000000

Therefore, I think there will be an error in this area (the leftmost 1 is 52 bits).
I wish someone could give me a mathematical explanation.

2022-09-29 21:39

It takes too long to check everything from 1 to 4503599761588224.

So, what about the next idea?

Verify that type n=i*i is Math.sqrt(n).to_i=i.
If we can confirm this, we can see that when j is not that large, the n=i*i+j type is Math.sqrt(n).to_i=i.
Therefore, you can check if the n=i*i-j type is Math.sqrt(n).to_i=i, but
Math.sqrt(i*i-j-1)<Math.sqrt(i*i-j), so
All you have to do is examine the type n=i*i-1.
(For example, if n=i*i-1 doesn't work, check n=i*i-2)

The code is as follows:

i=1
num = Math.sqrt(i*i).to_i
while num==i&i<67108864
  i+=1
  num = Math.sqrt(i*i).to_i
end
p[i*i,i,num] If #num is i, then OK

i = 2
num = Math.sqrt(i*i-1).to_i
while num==i-1
  i+=1
  num = Math.sqrt(i*i-1).to_i
end
p[i*i-1, i, num]#num is not i-1, so out

# Up to the above, only 4503599627370496 has been confirmed.
num = Math.sqrt(i*i-2).to_i
p[i*i-2,i,num]#num becomes i-1 and OK

Run Results
[4503599627370496,67108864,67108864]
[4503599761588224,67108865,67108865]
[4503599761588223,67108865,67108864]

2022-09-29 21:39

How long does Math.sqrt(n).to_i return the correct value for n value?

3 Answers

If you have any answers or tips