平方根の計算 入力 出力

Question

実現したいこと

非負整数 n ( 0 ≦ n ＜ 2^63 )を読み取り、n の整数平方根(√nを超えない最大の整数)を計算し、1行出力するプログラムの作成。

###前提
与えられる整数値は、0 または正であり、2^63 未満。

###質問したいこと
2の平方根は下記のように作ってみましたが今回の範囲n ( 0 ≦ n ＜ 2^63 )はどうすれば良いか教えて頂きたいです。

#include <stdio.h>
#include <math.h>

int main(void)
{
    double x = 2.0;
    double y = 0; 
    // xの平方根を計算
    y = sqrt(x);
    // 計算結果の表示
    printf("%f", y);
  
    return 0;
}

Comments

[y_waiwai]

今のコードではどういう不具合があるんでしょうか

Answer 1

100000000(1億)の2乗は、10000000000000000(1京)。
したがって、(1京 - 1) の 9999999999999999 の平方根は 100000000より小さく、
整数平方根は 99999999 のはず。
ところが、sqrt(9999999999999999) は 100000000 になってしまいます。

なぜかというと次のコードを実行すると分かります。

#include <stdio.h>

int main(void)
{
	for (long long n = 9999999999999995; n <= 10000000000000005; n++) {
		double d = n;
		printf("%17lld, %llx, %.13a, %19.1f\n", n, n, d, d);
	}
}

実行結果

 9999999999999995, 2386f26fc0fffb, 0x1.1c37937e07ffep+53,  9999999999999996.0
 9999999999999996, 2386f26fc0fffc, 0x1.1c37937e07ffep+53,  9999999999999996.0
 9999999999999997, 2386f26fc0fffd, 0x1.1c37937e07ffep+53,  9999999999999996.0
 9999999999999998, 2386f26fc0fffe, 0x1.1c37937e07fffp+53,  9999999999999998.0
 9999999999999999, 2386f26fc0ffff, 0x1.1c37937e08000p+53, 10000000000000000.0
10000000000000000, 2386f26fc10000, 0x1.1c37937e08000p+53, 10000000000000000.0
10000000000000001, 2386f26fc10001, 0x1.1c37937e08000p+53, 10000000000000000.0
10000000000000002, 2386f26fc10002, 0x1.1c37937e08001p+53, 10000000000000002.0
10000000000000003, 2386f26fc10003, 0x1.1c37937e08002p+53, 10000000000000004.0
10000000000000004, 2386f26fc10004, 0x1.1c37937e08002p+53, 10000000000000004.0
10000000000000005, 2386f26fc10005, 0x1.1c37937e08002p+53, 10000000000000004.0

long long は 63ビットの精度があります。10000000000000000 は 54ビットです。
double は 53ビットの精度しかありません。
9999999999999999～10000000000000001 の 3つの値が 10000000000000000.0 という
一つの値になってしまいます。
9999999999999999の平方根を double の sqrt で求められないのはこのためです。

Comments

[ta-9]

ご回答有難うございます。
ベストアンサーにさせて頂きます。

Answer 2

同じ質問をYahoo知恵袋で見ました。質問者は「回答だけを知りたいわけじゃない」とか言ってましたけど、回答が得られたら質問削除して消えましたね。同じ問題なので、きっとあなたの周りの誰かなんでしょう。

で。

今回の範囲n ( 0 ≦ n ＜ 2^63 )はどうすれば良いか教えて頂きたいです。

「範囲をどうすればよいか」というのはちょっと解釈が難しいです。どういう意味でしょうか。

もし、「範囲のチェックはどうしたらよいのか」という話であれば、
あなたが質問に書いているように与えられる値の「前提」なのですからチェックは必要ではありません。

「その範囲の値を正しく扱うためにはどうしたらよいのか」という話であれば...
まず、今の方針ではダメだ、ということを確認して下さい。これでどんな結果が得られますか?

#include <math.h>
#include <stdio.h>

int main(void) {
//2147483647即ち0x7fffffff<2^31なのでこの2乗は2^63より小さいので、
//2147483647*2147483647を与えたら解は2147483647になるはず
  double x = 2147483647ull * 2147483647ull - 1;//1を引いたので、解は2147483646にならなきゃいけない
  double y = 0;
  // xの平方根を計算
  y = sqrt(x);
  // 計算結果の表示
  printf("%f", y);//いくつになりましたか?

  return 0;
}

なにはともあれ2^63以下の整数をちゃんと扱えるunsigned long long型を使う必要があるでしょう。コンパイラによってはその時点で「ダメ」かも知れません。(つまり、どんなCコンパイラでも出来なきゃいけない、という問題であれば「不可能」で終わりにすればいいです)
また、sqrtみたいな便利な関数はないので、実際にある数の2乗を計算して、与えられた数と比較して「与えられた数を超えない最大の'ある数'」を探していくことになると思います。

他の方からもっといい方法がでてくるかも知れませんが、

Comments

[thkana]

http://www001.upp.so-net.ne.jp/y_yutaka/labo/math_algo/math_algo.html に整数での平方根の計算方法を見つけました。
「なんでそうなるのか」「それで本当に大丈夫なのか」を気にする出題者だったりすると、理解しないままに使っちゃうと面倒なことになるかも知れませんが。