プログラミングに関してなのですが、、、 n=x*xとして、このnを平方根を使わずに2乗だとチェックできる方法ってありませんか?

C言語関連 | 数学98閲覧

ベストアンサー

0

ThanksImg質問者からのお礼コメント

整数を1桁目で判断するという考え方は非常に参考になりました。 ありがとうございました

お礼日時:5/7 9:15

その他の回答(3件)

1

1. mohrus buffaloさんに同感です。 平方根の計算はCPU命令なんで早くならないと思います。 アイデアが面白いので作ってみました。 ただし10進数でなく2進数で考える必要があります。 下位8ビットを判定しています。 整数全体のだいたい3/4を?判定できます。 //---ここから #include <stdio.h> #include <math.h> #include <limits.h> #include <time.h> #include <stdbool.h> bool is_sqnum_n(int n) {     static const char a[256] = {         1,1,0,0, 1,0,0,0, 0,1,0,0, 0,0,0,0,         1,1,0,0, 0,0,0,0, 0,1,0,0, 0,0,0,0,         0,1,0,0, 1,0,0,0, 0,1,0,0, 0,0,0,0,         0,1,0,0, 0,0,0,0, 0,1,0,0, 0,0,0,0,         1,1,0,0, 1,0,0,0, 0,1,0,0, 0,0,0,0,         0,1,0,0, 0,0,0,0, 0,1,0,0, 0,0,0,0,         0,1,0,0, 1,0,0,0, 0,1,0,0, 0,0,0,0,         0,1,0,0, 0,0,0,0, 0,1,0,0, 0,0,0,0,         0,1,0,0, 1,0,0,0, 0,1,0,0, 0,0,0,0,         1,1,0,0, 0,0,0,0, 0,1,0,0, 0,0,0,0,         0,1,0,0, 1,0,0,0, 0,1,0,0, 0,0,0,0,         0,1,0,0, 0,0,0,0, 0,1,0,0, 0,0,0,0,         0,1,0,0, 1,0,0,0, 0,1,0,0, 0,0,0,0,         0,1,0,0, 0,0,0,0, 0,1,0,0, 0,0,0,0,         0,1,0,0, 1,0,0,0, 0,1,0,0, 0,0,0,0,         0,1,0,0, 0,0,0,0, 0,1,0,0, 0,0,0,0,     };     if (!a[n & 0xff]) return false;     int nt = (int)round(sqrt(n));     return nt*nt == n; } bool is_sqnum_o(int n) {     int nt = (int)round(sqrt(n));     return nt*nt == n; } void tst1() {     for (unsigned i = 0; i <= INT_MAX; ++i) {         if (is_sqnum_n(i) != is_sqnum_o(i)) {             printf("バグです: %d\n", i);             break;         }     }     printf("OK\n"); } void chk_time() {     int cnto = 0, cntn = 0;     clock_t tob = clock();     for (unsigned i = 0; i <= INT_MAX; ++i)         if (is_sqnum_o(i))             ++cnto;     clock_t toe = clock();     clock_t tnb = clock();     for (unsigned i = 0; i <= INT_MAX; ++i)         if (is_sqnum_n(i))             ++cntn;     clock_t tne = clock();     printf("旧: %d個 %f\n", cnto, (double)(toe - tob) / CLOCKS_PER_SEC);     printf("新: %d個 %f\n", cntn, (double)(tne - tnb) / CLOCKS_PER_SEC); } int main() {     // tst1();     chk_time(); } //---ここまで --- 結果 旧: 46341個 50.003000 新: 46341個 11.328000 --- 2. 配列aはこのプログラムで作りました。 stdoutへ出るのでリダイレクトして使ってください。 //---ここから #include <stdio.h> #include <stdbool.h> void to_2bs(unsigned n) {     unsigned b = 0x80;     for (; b; b >>= 1u)         printf("%c", n & b ? '1' : '0');     printf("\n"); } void bin_sort() {     bool has[0x100] = {0};     for (unsigned i = 0; i <= 0xff; ++i)         has[i*i & 0xff] = true; /* 以下の配列を作る     char a[256] = { 1,1,0,0, 1,0,0,0, 0,1,0,0, 0,0,0,0,         ...     } */     printf("\tstatic const char a[256] = {\n");     for (unsigned i = 0; i <= 0xff; ++i)         printf("%s%c,%s", i%16 == 0 ? "\t\t" : ""             , has[i] ? '1' : '0'             , i%16 == 15 ? "\n" : i%4 == 3 ? " " : "");     printf("\t};\n"); } int main() {     bin_sort(); } //---ここまで

1人がナイス!しています

1

n の最大値が決まっているのであれば、予め、その最大値以下の平方根のリストを作っておき、与えられた n に対して、2分探索でこの n を探索することでチェックできます。 計算量は log(n の最大値) になります。 これと平方根を求めるアルゴリズムの計算量を比べたときにどっちが速いかですね。 平方根の計算量がどの程度か知りませんが、多分かなり速い方なんじゃないかと思いますよ。

1人がナイス!しています