改善すべき点を教えてください。

Question

趣味で最近Ｃを始めたのですが、ある本で「0を除く2種類の数字のみで構成された平方数」は、81619の二乗（6661661161）より大きいものはないらしい。
と書かれていたので、確かめたくなり色々調べながらプログラミングしてみました。

なんとか動くようになったのですが、いまいちスピードが遅いように感じるのです。
そこで、こうすればスピードを速くできる、ここが不自然な書き方になっているなど、どこか改善すべき点があれば教えて欲しく質問しました。

あと、char型からint型に数字を変換する時に恐らく不自然な方法でやっているので、正規の方法がありましたらそれも教えていただけると助かります。
よろしくおねがいします。

ここから―――――――――――――――――――――――
#include <stdio.h>
#include <string.h>
int main(void){
　　double i;　　　　//平方根
　　int m;　　　　//整数（for用）
　　double x;　　//平方数
　　char str[100];　　//文字列（途中作業用）
　　int mono[100];　　//１桁の数字（途中作業用）
　　int len;　　//桁数
　　int num;　　//二つ目の数の置場
　　
　　for( i=1; i<=10000000000; i++){
　　　　x=i*i;　　　　　　　　　　　　　　//二乗
　　　　sprintf(str,"%.0f",x);　　　　　　//文字列に平方数を変換
　　　　len=strlen(str);　　　　　　　　　//桁数を求める
　　　　
　　　　if(len<=1)
　　　　　　goto PRINT;　　　　　　　　　 //平方数が一桁ならPRINTへ
　　　　
　　　　for( m=0; m<len; m++){
　　　　　　mono[m]=str[m]-48;　　　　　　//一桁ずつint型に収納＋実際の数に調整。
　　　　}
　　　　
　　　　m=(int)i;
　　　　if( m%2000000==0)
　　　　　　printf("i=%32.0f:ok - ",i);　 //進行状況
　　　　
　　　　for( m=0; m<len; m++)
　　　　　　if( mono[m]==0)
　　　　　　　　goto OUT;　　　　　　　　 //0が含まれていたらOUTへ
　　　　for( m=1; m<len; m++){
　　　　　　if( mono[m]==mono[0])
　　　　　　　　goto WHENSAME;　　　　　　//mono[0]と同じ数字だったらWHENSAMEへ
　　　　　　num=m;　　　　　　　　　　　　//違う数字の一回目の登場場所をnumに代入
　　　　　　break;　　　　　　　　　　　　// →脱出
　　　　　　WHENSAME:　　　　　　　　　　 //ラベル WHENSAME
　　　　}
　　　　for( m=num+1; m<len; m++){
　　　　　　if( mono[m]==mono[0]);
　　　　　　else if( mono[m]==mono[num]);
　　　　　　else
　　　　　　　　goto OUT;
　　　　　　}
　　　　PRINT:　　　　　　　　　　　　　　//ラベル PRINT
　　　　printf("%5.0f => %26.0f\n", i, x);
　　　　OUT:　　　　　　　　　　　　　　　//ラベル OUT
　　}
　　return 0;
}

Oh-Orange · Accepted Answer

★アドバイス
＞なんとか動くようになったのですが、いまいちスピードが遅いように感じるのです。
＞そこで、こうすればスピードを速くできる、ここが不自然な書き方になっているなど、
＞どこか改善すべき点があれば教えて欲しく質問しました。
　↑
　回答者 No.1 さんのアドバイス以外にも
　(1)キャストをつけて見る
　　修正前⇒len=strlen(str);　　　　　//桁数を求める
　　修正後⇒len=(int)strlen(str);　　//桁数を求める
　※strlen() 関数の戻り値は size_t 型なので int 型に結果を代入するときはキャストする。
　(2)ラベルの『:』文字の次に空文『;』を追加
　　修正前⇒WHENSAME:　　　　　　　　　　 //ラベル WHENSAME
　　修正後⇒WHENSAME:;　　　　　　　　　　 //ラベル WHENSAME
　　
　　修正前⇒OUT:　　　　　　　　　　　　　　　//ラベル OUT
　　修正後⇒OUT:;　　　　　　　　　　　　　　　//ラベル OUT
　※ラベルの後に『文』がない場合はエラーとなります。そのため空文の『;』を挿入する。
　(3)WHENSAME ラベルは continue でも代用できます。
　　修正後のみ
　　for ( m = 1 ; m < len ; m++ ){
　　　　if ( mono[m] == mono[0] )
　　　　　　continue;　　　　　　//mono[0]と同じ数字だったらWHENSAMEへ
　　　　num = m;　　　　　　　　　//違う数字の一回目の登場場所をnumに代入
　　　　break;　　　　　　　　　　// →脱出
　　}
　　または
　　for ( m = 1 ; m < len ; m++ ){
　　　if ( mono[m] != mono[0] ){　　//mono[0]と同じ数字だったらWHENSAMEへ
　　　　num = m;　　　　　　　　　　//違う数字の一回目の登場場所をnumに代入
　　　　break;　　　　　　　　　　// →脱出
　　　}
　　}
　　としてみる。
　(4)ちょっと細かいが定数値 48 よりも '0' で記述
　　修正前⇒mono[m]=str[m]-48;　　　　　　//一桁ずつint型に収納＋実際の数に調整。
　　修正後⇒mono[m]=str[m]-'0';　　　　　　//一桁ずつint型に収納＋実際の数に調整。
　※分かりやすく文字定数で記述してみる。48 よりも '0' が分かりやすいはず。
　(5)double 型は使わずにすべてを整数型で処理
　　i カウンタが 1～10^10 ですが二乗すると 10^20 となります。
　　64ビット整数(long long型)を使ってもオーバーフローを起こすため最大でも 10^9 乗に
　　抑えてから計算します。どんなコンパイラを使っているのか分かりませんが、64ビットの
　　整数型(long long型)が利用できるのならば double x; ではなくて long long x; として
　　処理してみて下さい。
・計算量が多いのであまり高速にならない気がします。パソコンの限界？かと。
・以上。整数型(longか long long 型など)で処理するように書き換えてみて下さい。

Oh-Orange · Answer

★質問者さんと MASA_H さんへ。・いろいろと調べたらテーブル参照の方が遅かったです。　もう一つテーブルを用意して２段階にしても MASA_H さんのとほぼ同じ速度でした。　よって素直に回答者 No.9(MASA_H)さんの一つ一つ確認版が最終版ですかね。・下にそのソースを載せておきます。最終版: #include #include // 2種類の数字のみで構成(MASA_Hより) int check_num( char ntmp[], int len ) { 　char num[ 2 ]; 　int j; 　num[ 0 ] = ntmp[ 0 ]; 　　for ( j = 1 ; j < len ; j++ ){ 　　num[ 1 ] = ntmp[ j ]; 　　　　if ( num[0] != num[1] ){ 　　　break; 　　} 　} 　if ( num[0] == num[1] ){ 　　return -1; 　} 　for ( j = 0 ; j < len ; j++ ){ 　　if ( ntmp[j] == '0' || (ntmp[j] != num[0] && ntmp[j] != num[1]) ){ 　　　return (j + 1); 　　} 　} 　return 0; } // メイン関数 int main( void ) { 　unsigned long long i, x;　// 平方根　char str[ 100 ];　　　// 文字列(途中作業用) 　int len, m, h, l;　　　// 桁数,ワーク変数　clock_t t;　　　　　// 計測用　clock_t start = clock();　// スタート用　　for ( i = 1 ; i <= 1000000000 ; i++ ){ 　　x = i * i;　　　　　　　　// 二乗　　len = sprintf( str, "%I64u", x );　　// 文字列に平方数を変換　　　　if ( (len == 1) || !check_num(str,len) ){ 　　　printf( "%5I64u => %20I64u ", i, x ); 　　} 　　// 進行状況　　if ( !(i & 0x1FFFFF) ){ 　　　m = (int)(i / 100000); 　　　h = (m / 100); 　　　l = (m % 100); 　　　t = (clock() - start); 　　　printf( "i = %I64u(%d.%02d%%)%u.%03u秒 ", i, h, l, (t / 1000), (t % 1000) ); 　　} 　} 　printf( "-- 終了 -- " ); 　return 0; } 以上。

MASA_H · Answer

gcc+gprofで計測したところ、2種類の数字のみかどうかの判別はテーブルを使ったもの(Oh-Orangeさんのもの)より、一つ一つ確認していくもののほうが速かったです。
比較コード(これ以外は同じして比較した)
テーブル版(table[1024]はグローバルにしてmain()内で初期化)
int check_num(char ntmp[],int len){
      int chk,m;
      for(chk=m=0;m<len;m++){
              chk|=0x1<<(ntmp[m]-'0');
      }
      if(!(chk&0x1)){                 // 0が含まれない数を処理
              if(table[chk]==2){      // 2種類の数字のみで構成
                      return(0);
              }
      }
      return(-1);
}
一つ一つ確認版
int check_num(char ntmp[],int len){
        char num[2];
        int j;
        num[0]=ntmp[0];
        for(j=1;j<len;j++){
                num[1]=ntmp[j];
                if(num[0]!=num[1])break;
        }
        if(num[0]==num[1])return(-1);
        for(j=0;j<len;j++){
                if(ntmp[j]=='0'||(ntmp[j]!=num[0]&&ntmp[j]!=num[1])){
                        return(j+1);
                }
        }
        return(0);
}
比較結果
テーブル版
  %   cumulative   self              self     total           
 time   seconds   seconds    calls  ns/call  ns/call  name    
 45.86      0.22     0.22  2147484   102.49   181.70  main_loop
 35.43      0.39     0.17  2147484    79.20    79.20  check_num
 18.76      0.48     0.09                             main
  0.00      0.48     0.00        1     0.00     0.00  init_table
一つ一つ確認版
  %   cumulative   self              self     total           
 time   seconds   seconds    calls  ns/call  ns/call  name    
 52.97      0.18     0.18  2147484    83.86   125.79  main_loop
 26.48      0.27     0.09  2147484    41.93    41.93  check_num
 20.60      0.34     0.07                             main

Oh-Orange · Answer

★回答者 No.2、No.6、No.7 です。
＞試してみたところ、（１）ではエラーが出ましたが他は出ませんでした。
　↑
　(2)、(3)が使えるのならコンパイラを変える必要はないです。
＞ちなみに、No.6で作って頂いたサンプルのi,xの宣言を
＞ULONG64 かULONGLONG にすればコンパイルでき、動作しました＾＾
　↑
　実行結果も正しかったですか？
　52行目の『x = i * i;』と
　53行目の『len = sprintf( str, "%I64u", x );』
　が正しかったら 64 ビット整数として計算できるため速度はどうですか。
　double 型よりも早くなりましたか？
　※printf() の書式制御文字で64 ビット整数の『%I64u』が正しく使えるか調査。
＞32行目：'value'に代入した値は使われていない
＞と警告が出るのですが、これは正常なのでしょうか？
　↑
　この警告はおかしいですね。
　initTable() 関数の for() 内で『value = i;』と代入して
＞table[ i ] = bit4count[ value & 0xF ]; value >>= 4;
＞table[ i ] += bit4count[ value & 0xF ]; value >>= 4;
＞table[ i ] += bit4count[ value & 0xF ]; value >>= 4;
　として参照しているので警告が出るのはおかしい。
　もし、警告が出るとすると上記の３行が記述されていないことになるが…。
　記述していますよね？
・でも記述しているのならこの手の警告は無視して良いです。
　無駄な変数が見つかったよ。とコンパイラさんが教えてくれているだけなので。
　また、この警告が出るということはオプションで一番高く設定されていますね。
　特に警告メッセージに問題はないです。
・あと clock() 関数で時間を計測していますが表示とかに問題はありませんか？
　特に問題が無ければ double 型や多倍長整数演算のものよりは早く計算できると
　思います。私の環境では最初の『進行状況』が表示されるのに約3.1秒かかります。
　この速度で終了するまで実行すると約36分かかりました。
・あと main() 関数の for() 処理後に１行『printf( "-- 終了 --
" );』を
　追加しておいて下さい。追加しても、追加しなくてもどちらでも良いですけど。
　その他、調べる数を『100000000(8個)』にすれば 200 秒ぐらいで終了しました。
・以上。いろいろと試して見て下さい。

実行結果:
    1 =>                    1
    2 =>                    4
    3 =>                    9
    4 =>                   16
    5 =>                   25
    6 =>                   36
    7 =>                   49
    8 =>                   64
    9 =>                   81
   11 =>                  121
   12 =>                  144
   15 =>                  225
   21 =>                  441
   22 =>                  484
   26 =>                  676
   38 =>                 1444
   88 =>                 7744
  109 =>                11881
  173 =>                29929
  212 =>                44944
  235 =>                55225
  264 =>                69696
 3114 =>              9696996
81619 =>           6661661161
i = 2097152(0.20%)3.108秒
i = 4194304(0.41%)6.451秒
i = 6291456(0.62%)9.826秒
i = 8388608(0.83%)13.341秒
i = 10485760(1.04%)16.715秒
　：
i = 98566144(9.85%)196.918秒
-- 終了 --

Oh-Orange · Answer

★追記。回答者 No.6 です。
・簡単な多倍長整数演算を組み込んで試してみましたが double 型とほとんど速度に
　変化が出ませんでした。どうやら double 型を使ったり、多倍長整数演算も含めて
　速度に変化はあまり出ませんでした。
・もし、もっと速度を上げて試したいのならば 64 ビット整数の long long 型が使える
　コンパイラで実行して下さい。
＞コンパイラですが、Borland C++Compiler 5.5.1 を使っています。
　↑
　このコンパイラでは long long 型でエラーが出るため使えません。
　よって マイクロソフト社の VC++2005 無料版をダウンロードして試せば long long 型が
　使えるため回答 No.6 で速度を上げることが出来ます。
　ただし、インストールなどの手間が増えますが…。

結果報告:
・回答 No.6 のソースで試した限りでは 1～100000000 で 81619 より大きいものは確かに
　発見できませんでした。
・実行時間はなんと 36 分もかかりました。→CPU使用率100% × 36分です。
　『NEC ValueStar VL570/6 2.0GHz』
　という環境です。
・aniline さんの最初のソースでは 2000000 まで実行時間が約10秒かかりますが、
　回答 No.6 のソースでは 2000000 まで実行時間が約2.9秒でした。
　double 型や多倍長整数演算の場合も 2000000 まで実行時間が約10秒かかります。
　※ちなにみ clock() 関数で計測しました。

結論:
＞改善すべき点を教えてください。
　↑
　いろいろソースをいじくるよりも単純に 64 ビット整数が利用できるコンパイラで
　試した方が良さそうです。あるいはインライン・アセンブラを使って 64 ビットの
　整数で計算させるとかします。
・試しに次の型が利用できるか調べて見て下さい。
　(1)__int64 型
　(2)ULONG64 型
　(3)ULONGLONG 型
　(2)、(3)は windows.h をインクルードして下さい。
　これらのデータ型が利用できるなら 64 ビット整数で試せます。
　特に ULONGLONG 型が利用できるのならば UInt32x32To64() 関数が利用できます。
　この関数は 32ビット整数×32ビット整数＝64ビット整数の乗算を計算してくれます。
・これを利用すれば
　ULONGLONG x = UInt32x32To64( i, i );
　として 64 ビット整数の乗算を行い
　len = sprintf( str, "%I64u", x );
　として文字列に変換すればよい。
　
・以上。いろいろと試すか、コンパイラを変えるように。

Oh-Orange · Answer

★回答者 No.2 です。私も作ってみました。・テーブルを用いて２種類の数字かどうかを判定しています。　下の『全角文字』を一括して『タブ文字』に変換するとコメントが揃います。・あと long long 型が利用できないとエラーとなります。　この場合は x を double 型にして for のループを 10000000(10の7乗)にします。　その他 x 変数に関わる printf() の書式制御文字などを修正すればコンパイルが　可能になると思います。・それでは下にサンプルを載せておきます。サンプル: #include #include #include /* 10Bit(0～1023)のビットカウンタ数を初期化 */ void initTable( int table[] ) { 　static int bit4count[] = { 　　0,　// 0000 　　1,　// 0001 　　1,　// 0010 　　2,　// 0011 　　1,　// 0100 　　2,　// 0101 　　2,　// 0110 　　3,　// 0111 　　1,　// 1000 　　2,　// 1001 　　2,　// 1010 　　3,　// 1011 　　2,　// 1100 　　3,　// 1101 　　3,　// 1110 　　4,　// 1111 　}; int i, value; 　　for ( i = 0 ; i < 1024 ; i++ ){ 　　value = i; 　　table[ i ] = bit4count[ value & 0xF ]; value >>= 4; 　　table[ i ] += bit4count[ value & 0xF ]; value >>= 4; 　　table[ i ] += bit4count[ value & 0xF ]; value >>= 4; 　} } // メイン関数 int main( void ) { 　char str[ 100 ];　　　　//文字列（途中作業用）　unsigned long long i, x;　　//平方根　int chk;　　　　　　//チェック用　int len;　　　　　　//桁数　int m;　　　　　　　//整数（for用）　int h, l;　　　　　　//パーセント用　int table[ 1024 ];　　　　//テーブル　clock_t start, t;　　　　//計測用　　// 初期化　initTable( table ); 　start = clock(); 　　for ( i = 1 ; i <= 1000000000 ; i++ ){ 　　x = i * i;　　　　　　　　//二乗　　len = sprintf( str, "%I64u", x );　　//文字列に平方数を変換　　if ( len == 1 ) goto PRINT; 　　　　// 数字の種類(0～9)を 10Bit に変換　　for ( chk = m = 0 ; m < len ; m++ ){ 　　　chk |= 0x1 << (str[m] - '0'); 　　} 　　if ( !(chk & 0x1) ){　　　　　// 0が含まれない数を処理　　　if ( table[chk] == 2 ){　　　　// 2種類の数字のみで構成 PRINT:　　　printf( "%5I64u => %20I64u ", i, x ); 　　　} 　　} 　　if ( !(i & 0x1FFFFF) ){　　　　　//進行状況　　　m = (int)(i / 100000);　　　　//パーセント値(100.00%) 　　　h = (m / 100); 　　　l = (m % 100); 　　　t = (clock() - start); 　　　printf( "i = %I64u(%d.%02d%%)%d.%03d秒 ", i, h, l, (t / 1000), (t % 1000) ); 　　} 　} 　return 0; } 以上。

zwi · Answer

回答 No.3です。 gccで動作試してみましたが高速化してません。速度のネックは、やはりdoubleの計算と文字列に変換しているところにありそうです。それとOUTのgotoは外さない方が高速化できそうなので残しました。高速化のポイントは、for文のループ回数を出来るだけ減らすこと、if文の回数を減らすことなのですが、それ以外の部分で重いとさほど効果はありません。 clock()関数はgccなら問題ありませんが、bccで問題がある場合は外してください。 #include #include #include int main(void){ 　　double i;　　//平方根　　int m;　　　　//整数（for用）　　double x;　　//平方数　　char str[100];　　//文字列（途中作業用）　　int mono[100];　　//１桁の数字（途中作業用）　　int len;　　//桁数　　int num;　　//二つ目の数の置場　　unsigned long t0,t1; 　　　　t0 = clock(); 　　　　for( i=1; i<=10000000000; i++){ 　　　　x=i*i;　　　　　　　　　　　　　　//二乗　　　　sprintf(str,"%.0f",x);　　　　　　//文字列に平方数を変換　　　　len=strlen(str);　　　　　　　　//桁数を求める　　　　 //※ この処理が無いほうが高速化できると思います。 //　　　　if(len<=1) //　　　　　　goto PRINT;　　　　　　　　 //平方数が一桁ならPRINTへ　　　　for( m=0; m %26.0f time=%d ", i, x, t1-t0); OUT:; 　　} 　　return 0; }

MASA_H · Answer

気分転換にGMPを使ったものを書いたので貼っときます。最適化も何も考えてないのでceleron2.6GHzで21474836個の探索をするのに12秒程度かかります。 #include #include #include #include #include #define SMAX INT_MAX/100 int main(void) { mpz_t x,y; char num[2],ntmp[32],ptmp[16]; int i,j,len,flag; mpz_init(x); mpz_init(y); mpz_set_ui(x,81619); for(i=0;i<=SMAX;i++){ flag=0; mpz_mul(y,x,x); mpz_get_str(ntmp,10,y); len=strlen(ntmp); num[0]=ntmp[0]; j=1; num[1]=ntmp[j]; while(1){ j++; if(j>=len){ flag=1; break; } if(num[0]!=num[1])break; num[1]=ntmp[j]; } if(flag==0){ for(j=0;j %s ",ptmp,ntmp); } mpz_add_ui(y,x,1); mpz_set(x,y); if((i%2000000)==0)printf("(%d/%d) ",i,SMAX); } mpz_clear(x); mpz_clear(y); return(0); }

zwi · Answer

プログラムの問題点がいくつかあるので上げます。
・gotoが多すぎます。if文の工夫やforループのcontinue文の導入で、全部のgoto文を一掃できます。
・高速化のためにはループを減らしてください。下３つのfor文は１つにできると思います。
・mono[num]は変数に値を代入して、それ以外の部分も添え字で配列を扱うよりもポインタに変えたほうが高速化できます。

根本的な問題の件は、gmp(GNU Multi Precision - 任意精度数演算ライブラリ)を使えば解決できると思えますが、自力で調べて導入する必要があります。
http://www001.upp.so-net.ne.jp/tklab/linux/sci1a.html
windowsでの導入方法。
http://taylor.gotdns.org/gmp.html

sha-girl · Answer

>x=i*i;　　　　　　　　　　　　　　//二乗
まずこれが破綻しています。

doubleは10進数で考えると有効桁数がせいぜい１５桁の精度です。
10000000000.0 * 10000000000.0は有効桁数を確実にオーバーしていますよね？

m=(int)i;
これも環境にもよりますが通常intは32bitです。
(少なくともVC++2005では64bit用コンパイルであってもintは32bit)
signedで-2,147,483,648～2,147,483,647
unsignedで0～4,294,967,295
ですので10000000000.0はint(32bit)には収まりません。

今回の場合だと64bit型のunsigned 整数型(0～18,446,744,073,709,551,615)を明示的に使うか
それより大きな桁数の数値を扱う場合は
多倍長演算を考慮しなければなりません。
実装方法は色々とありますが、まずこの部分を考慮した
プログラムを実装する必要があると思います。

改善すべき点を教えてください。

★アドバイス

★質問者さんと MASA_H さんへ。

この回答への補足

gcc+gprofで計測したところ、2種類の数字のみかどうかの判別はテーブルを使ったもの(Oh-Orangeさんのもの)より、一つ一つ確認していくもののほうが速かったです。

★回答者 No.2、No.6、No.7 です。

★追記。

★回答者 No.2 です。

回答 No.3です。

気分転換にGMPを使ったものを書いたので貼っときます。

プログラムの問題点がいくつかあるので上げます。

>x=i*i; //二乗

似たような質問が見つかりました

関連するカテゴリからQ&Aを探す

デイリーランキングこのカテゴリの人気デイリーQ&Aランキング

マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング

>x=i*i;　　　　　　　　　　　　　　//二乗