

Ruby 2.2.1 を使っているのですが、  
n = 1, 2, … , のとき  
Math.sqrt(n).to_i が正しい値をかえす  
（すなわち、1 からn までの全てのm に対して、Math.sqrt(m).to_i の値が [√m] となる）  
のはn がどれくらいまででしょうか？

ちなみに  
n = 4503599761588224 のとき、  
Math.sqrt(n).to_i が正しい値をかえさないことを  
次のコードを実行して見つけました。

[code]

    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
    }
    
[/code]

（追記）  
n = i * i - 1型を全て調べるなら、次のコードの方がよい。

[code]

    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]
    
[/code]

出力結果  
[4503599761588224, 67108865]


CC BY-SA 3.0
2015-11-03T05:36:42.080
18349
2015-11-06T22:35:33.370
2015-11-04T15:27:49.637
5363
5363
question
ruby
Math.sqrt(n).to_i が正しい値をかえすのはnがどれくらいまででしょうか？


Windowsの電卓などで√4503599761588224を計算しますと

> 67108864.999999992549419514098472

が得られます。  
まず[Math.sqrt](http://docs.ruby-
lang.org/ja/2.2.0/method/Math/m/sqrt.html)ですが実数[Float](http://docs.ruby-
lang.org/ja/2.2.0/class/Float.html)を返すとありその有効精度はせいぜい15桁です。16桁目を四捨五入すれば

> 67108865.0000000

ぐらいの値が返っているのでしょう。そのため切り上げられてしまっています。  
BigDecimalはFloat以上の精度を持つため切り上げを受けていません。

浮動小数点数とは概数であり、精度以上の演算を行えばこのようなことになります。

* * *

Manyamaさん、shirokさんの挙げられた数値は１０進表記ではとりとめもないですが、２進表記すると

> 4503599493152769 |
> 0000‭1111111111111111111111111000000000000000000000000001‬  
>  4503599761588223 ‭|
> 00010000000000000000000000000111111111111111111111111111‬  
>  4503599761588224 ‭|
> 00010000000000000000000000001000000000000000000000000000‬

となり、この辺りで誤差による繰り上がりが発生してくるんだろうな、とは思っています。（一番左の１が52bitです。）  
どなたか数学的な説明をしていただけたらと。


CC BY-SA 3.0
2015-11-03T21:32:23.943
18379
2015-11-06T22:35:33.370
2015-11-06T22:35:33.370
4236
4236
18349
answer


以前誤差を検討したことがあります。(n+ε)^2 = n^2 + 2nε + ε^2 ですから、(2nε +
ε^2)部分がn^2部分に比べ浮動小数点数の有効数字に収まらなくなると、sqrtを取った結果がnになってしまいます。

IEEE倍精度浮動小数点数を仮定した場合、正しい整数値が得られる最大の数は次の数、となりました。

[code]

    (2^26-1)^2 = 4503599493152769
    
[/code]

参照: <http://blog.practical-scheme.net/gauche/20130319-inexact-sqrt>

(ただし、Rubyのto_iの仕様を正確に把握していないので、もしかすると違う評価方法を使う必要があるかもしれません。)

追記:
問題の条件を勘違いしていたかもしれません。上の数字は、「IEEE浮動小数点数でsqrtを取った場合、本来平方数でないのに結果が整数になってしまう、ということが起きない範囲での最大の平方数」です。

もし、ある平方数n^2に対して(1)それを浮動小数点数に変換し(2)sqrtを取り(3)整数丸めしたものがnになる、ような最大のnを求める問題でしたら、誤差が上手い具合に打ち消しあってより大きな数があり得るかもしれません。後ほど計算して追記します。


CC BY-SA 3.0
2015-11-03T22:13:40.920
18381
2015-11-03T23:12:32.877
2015-11-03T23:12:32.877
5258
5258
18349
answer


1 から4503599761588224 まで全て調べるのは、Ruby では時間がかかりすぎます。

そこで、次の考え方はどうでしょうか？

n = i * i 型はMath.sqrt(n).to_i = i となることを確認する。  
このことが確認できれば、j がそんなに大きくないとき、n = i * i + j 型はMath.sqrt(n).to_i = i となることがわかる。  
よって、n = i * i - j 型がMath.sqrt(n).to_i = i とならないかチェックしていけばよいが、  
Math.sqrt(i * i - j - 1) < Math.sqrt(i * i - j) なので、  
n = i * i - 1型を調べるだけでよい。  
（仮に、n = i * i - 1型がダメなら、n = i * i - 2型を調べる）

コードは以下の通りです。

[code]

    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] # numがiならＯＫ
    
    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がi - 1でないのでアウト
    
    # 上記までだと4503599627370496までしか確認できていない
    num = Math.sqrt(i * i - 2).to_i
    p [i * i - 2, i, num] # numがi - 1となりＯＫ
    
[/code]

実行結果  
[4503599627370496, 67108864, 67108864]  
[4503599761588224, 67108865, 67108865]  
[4503599761588223, 67108865, 67108864]


CC BY-SA 3.0
2015-11-06T12:26:07.003
18483
2015-11-06T16:42:58.797
2015-11-06T16:42:58.797
5363
5363
18349
answer