平方根の切り捨てで精度が足りなくなったときのための回避策
この問題を解いていたら精度ゲーにハメられた
code:text
Python 3.9.12 (main, Mar 26 2022, 15:44:31)
Type "help", "copyright", "credits" or "license" for more information.
>> import math
>> math.sqrt(9000000000000000000)
3000000000.0
>> math.sqrt(8999999999999999999)
3000000000.0
>>
ので、怒りを込めて平方根の切り捨てを正確に求める方法を書き留めておく。
結論というか、何というかわからないが、とりあえず二分探索を書く。
一応 C++ でもオーバーフローしないので通用する。ただしかなり遅い。
r = sqrt(x) + 2とすることでstd::sqrtの$ 3倍程度の速度にはなる。
一応計算量は$ \Omicron(\log X)なのだが、そもそも$ X \leq 9 \times 10^{18}においては定数倍込みで額面$ 30ステップになるのでかなり重い部類に当たるだろう。
code:cpp
ll sqrtint_binary(ll x){
ll l = -1, r = 3000000001;
while(r - 1 > l){
ll m = l + (r - l) / 2;
if(m * m > x){
r = m;
}else{
l = m;
}
}
return l;
}
code:py
def sqrtint_binary(x):
l = -1
r = 3000000001
while r - 1 > l:
m = l + (r - l) // 2
if m * m > x:
r = m
else:
l = m
return l
追記
nok0先生「もしかして：std::sqrtl」
ぼく「？？？？？？？？？」