2

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 が正しい値をかえさないことを
次のコードを実行して見つけました。

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
}

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

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]

出力結果
[4503599761588224, 67108865]

0

3 件の回答 3

4

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

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

(2^26-1)^2 = 4503599493152769

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

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

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

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

0
2

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

67108864.999999992549419514098472

が得られます。
まずMath.sqrtですが実数Floatを返すとありその有効精度はせいぜい15桁です。16桁目を四捨五入すれば

67108865.0000000

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

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


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

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

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

1
  • 3599999999999999 (< 4503599761588224) はルートをとると、 59,999,999.9999999916666666666…となり16桁目が四捨五入され 60,000,000がかえってきそうですが、59,999,999 がかえってきます。
    – TOM
    2015年11月5日 14:19
0

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型を調べる)

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

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なら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がi - 1でないのでアウト

# 上記までだと4503599627370496までしか確認できていない
num = Math.sqrt(i * i - 2).to_i
p [i * i - 2, i, num] # numがi - 1となりOK

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

この質問に回答するには、ログインする必要があります。

求めていた回答ではありませんか? のタグが付いた他の質問を参照する。