平方根関数を自作しています。Over flow errorがLeetCode内で出ます。

Question

inputされたxの値の平方根をreturnする関数を作成しています。sqrt()や、**0.5は使えません。
LeetCode内で、Overflowエラーになります。アドバイスをいただきたいです。

問題のリンク(leetcode)

int mySqrt(int x){

    int answer=0;
    
    if(x<2)return x;
    
    
    for(int i=1; i<x; i++){
        
        if(i*i>x){
            i=x;
        }else{
            answer=i;  
        }
    }  
    return answer;
}

Line 29: Char 13: runtime error: signed integer overflow: 46341 * 46341 cannot be represented in type 'int' [solution.c]

//このコードではなぜoverflowが起きないのでしょうか？

int mySqrt(int x){
    
     double xn;
      int i,n;

      n=10;
      xn=0;

      do { /* 平方根に最も近い大きい方の整数を探す */

          xn+=1;

      } while (xn*xn<x);

      for (i=0;i<n;i++) {
          xn=(xn+x/xn)/2; /* 交点のx 座標を求める */
      }
      return xn; /* 求めた近似値を返す */
}

Answer 1

アドバイスをいただきたいです。

スピード不問なら奇数列(1,3,5,7...)を引いていくのが単純かしら...

Comments

[fana]

恥ずかしながら，
数分間ほど「これ何の話？」ってなっちゃいました…

[rubato6809]

> スピード不問なら
質問者の方法と比較すると、ループ回数はほぼ同じでも、足し算・引き算だけで済むから、毎回二乗するより速いはずです。

[alizona]

ピタゴラ数ですね。勉強になりました。

Answer 2

※見間違いによる不要部分を取り消しています。

32ビットint型の最大値は2147483647です。
その上で、forループ内では解が出た後もx*xの計算が不必要に行われてしまうので、
46341以上の数値を引数xに渡すと、46341*46341が行われた時点でて2147488281となりint型の最大値を超えてしまいオーバーフローが発生してしまいます。

xの最大値を制限する必要もありますが、
そもそも解が出た時点でbreakでループを終了して無駄な計算をさせないようにすべきです。

    for(int i=1; i<x; i++){
        if(i*i>x){
            break;
        }
        answer = i;
    }

（訂正による追記）エラーとならないようにxの最大値を制限するすべきと思いますが、
このアルゴリズムのままLeetCodeで通すためにはiをlong longなどの型にして巨大な数値を扱えるようにする必要があると思います。

ちなみに効率良く平方根の近似値を求める方法の一つとしてニュートン法というのもありますので、ご参考ください。

Comments

[fana]

> forループ内では解が出た後もx*xの計算が不必要に行われてしまう…
> そもそも解が出た時点でbreakでループを終了して無駄な計算をさせないようにすべき

質問者のコードでの
i=x;
というのは，breakの意味合いで書かれている（iの値を，forの繰り返し条件を満たさない値にする）のだと見えます．
（まぁ，だったら break って書けよ，とは思いますが）

[surface_0]

そうでした。
すいません、ちょっと見当違いの回答書いてました。

[alizona]

breakの使い方あやふやだったので、わざわざ代入させてました。break;でいいんですね。
ありがとうございます。
binary treeでやってるとこなんですが、どちらにせよx*xでオーバーフローしてるので、オーバーフローさせないアルゴリズムがニュートン法ということでしょうか？

[fana]

i=x;
の後は，
for(int i=1; i<x; i++){ ... }　の i++ によって iの値が x+1 になりますね．
で，この時点で繰り返し条件 i<x を満たさないので，{...} のところはもはや実行されません．

なので，素直に break と書いた場合との差としては，
x++
i<x の判定
の２つを余計にやることになる，くらいでしょう．

[surface_0]

不等号の見間違えというアホなことででちょっと回答内容がズレてしまいました。失礼しました。
すでに削除リクエストしてしまっているので、コメント消えてしまうかもしれません。。。

ニュートン法だとxより大きな値は出てこないので、オーバーフローの心配が無いですが、割り算で少数を扱うことになるので、どちらが効率がいいかは場合によりけりです。

[fana]

> どちらにせよx*xでオーバーフローしてるので

素朴な疑問なのですが，
「２乗計算がフローするなら，しなきゃいいんじゃないの？」っていう話が既に別の方の回答に書かれているわけですが，それでは何かがダメなんでしょうか？

[alizona]

数値Aを２乗しないで、どうやって数値Aがxの平方根だと証明するのですか？

[fana]

素人考えですが，
if( i*i >x ){ ... }
っていうのがやりたいけども i*i がフローする，という話であれば，例えば
if( i > (x/i) ){ ... }
とか
if( 1 > ((x/i)/i) ){ ... }
とかにしたらダメなのか？（それだと支障が出ることがあるのか？）　という．

[alizona]

普通にleetcodeにsubmit したら通りましたw。ありがとうございます。
ニュートン法とか、バイナリーツリーとかの使用を意図して作られた問題かどうかは知らないですが、そっちも把握したいので勉強してみます。

[alizona]

Runtime: 68 ms, faster than 5.29% of C online submissions for Sqrt(x).
Memory Usage: 5.5 MB, less than 92.12% of C online submissions for Sqrt(x).

[fana]

昔，平方根を求める手続きの話をどこかで見たよなぁ…　と思って探したら
Babylonian Method　という名前で，
手続きはニュートン法と完全一致だった．

[surface_0]

> if( 1 > ((x/i)/i) ){ ... }
とかにしたらダメなのか？

割り算で絞り込んでいくというのはまさにニュートン法に近い考え方ですね。

回答削除は却下されましたので、ノイズになってしまう部分は取り消し編集しておきました。
お騒がせ致しましたが、今後の参考になれば幸いです。

[alizona]

ニュートン法でもやったのですが、ニュートン法では } while (xn*xn<x); を使ってもover flowにな離ませんでした。
whileで xnがxを超えるまでループしてるので、overflowになると思ったのですが。なぜなんでしょうか？
codeは質問文の最後に載せました。

[rubato6809]

> 数値Aを２乗しないで、どうやって数値Aがxの平方根だと証明する

たとえば「平方数 奇数の和」で検索してみるとか。

[surface_0]

引数のxが上限となっているため、xn*xnは最大でもその付近の値で終了するので、大抵はオーバーフローしません。
逆に言えばxがint最大値に近いとオーバーフローになることはあり得ます。

[alizona]

while (xn*xn<x); この文では、while(xn*(xn < x)); つまり、xnとxの比較が先に行われてますか？

[surface_0]

優先度は < より * の方が高いので while((xn*xn) < x)と同等です。
逆に while(xn*(xn < x)) だと意味が分からなくなると思います。

[alizona]

変なこと言いました。
while(xn*xn<x){ で xn*xn が x よりも大きい場合には、whileループを抜けますが、whileループを抜けるかどうかを判断した時にover flowが起こっているのではないですか？

最初に質問を投稿した時のコードでは、if(i*i>x){ break; としているのですが、何が違うのですか？

[fana]

> int型の最大値を超えてしまいオーバーフローが発生してしまいます

っていう話をしてたのに

> double xn;

って，型が変わってるやん，っていう．

[alizona]

最初の質問した時点のコードをdouble にしたらover flow なしに提出できました。

[alizona]

みなさんありがとうございました。
２乗せずに平方根を見つける方法、ニュートン法、ピタゴラ数、int doubleの最大値と色々勉強になりました。

[fana]

「そもそもの問題が何だったのか？」をちゃんと把握できてるんですかね？

「intとintとで計算した結果値の型はintってことにするぜ！」っていうルールがまずあって，
なんだけども，あなたのコードを実行したら計算した結果の値がintで表せる範囲を超えちゃったから，
これどうなん？　やばくね？　マジムリ　って話になってたわけね．

int型であることをやめちゃったら当然この話は変わってくるよね．

---

で，
・型自体を変えたら？
・フローしちゃう掛け算自体をやめたら？
の両方が maisumakun 氏によって真っ先に回答されてるわけで．

[alizona]

フローしちゃう掛け算自体をやめたら？こっちを先に解決しようとしてて、型を変えたら？というアドバイスを忘れていました。returnする型がint ってこと以外は決まりはありませんでした(leet code内で)

[surface_0]

> 最初に質問を投稿した時のコードでは、if(i*i>x){ break; としているのですが、何が違うのですか？

このコードだと整数部に関してはやってることはまったく同じだと思います。
型がdoubleになって許容値が大きくなったのでオーバーフローしなくなりました。
すいません、自分も的外れな事言って失礼しました。

結局今回の問題では整数部だけ返せばいいようなので、小数部を計算する後半は必要ではないと思います。
ただ、自分が想像していたニュートン法は2乗する式が出てこないものだったので、そのあたりの区別まで考えていませんでした。

[alizona]

Since the return type is an integer, the decimal digits are truncated, and only the integer part of the result is returned.

return も doubleで良かったみたいです。ただ、２乗せずに平方根を見つける方法、ニュートン法、ピタゴラ数などと教えていただいたことを理解したかったので、どちらも理解できて良かったです。

Answer 3

エラーメッセージのとおりです。このままでは、2**31-1のような巨大な数を引数とした場合に、intからオーバーフローします。

対策としては、

• 途中の計算にlong longを使って、溢れないように変数の幅を広げておく
• i*i>xの条件判定を変えて、掛け算せずにループ範囲に収まるかをチェックする

Comments

[alizona]

ありがとうございます。やってみます。

[maisumakun]

> このコードではなぜoverflowが起きないのでしょうか？

一般に、doubleの値の範囲はintより大きいです。

[alizona]

ありがとうございました。