こんにちはゲストさん。会員登録(無料)して質問・回答してみよう!

解決済みの質問

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

趣味で最近Cを始めたのですが、ある本で「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];  //1桁の数字(途中作業用)
  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;
}

投稿日時 - 2007-07-17 16:44:32

QNo.3175796

暇なときに回答ください

質問者が選んだベストアンサー

★アドバイス
>なんとか動くようになったのですが、いまいちスピードが遅いように感じるのです。
>そこで、こうすればスピードを速くできる、ここが不自然な書き方になっているなど、
>どこか改善すべき点があれば教えて欲しく質問しました。
 ↑
 回答者 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 型など)で処理するように書き換えてみて下さい。

投稿日時 - 2007-07-17 22:00:54

お礼

> (1)(2)(3)(4)
なるほど…勉強になります。
ありがとうございます。

> (5)
> 64ビットの整数型(long long型)が利用できるのならば double x; ではなくて long long x; として処理
long long x; という風に使うんですね;;
今やってみましたが「宣言に型が多すぎる(関数 main())」とエラーが出ます。。
これは使えないということなのでしょうか…?

コンパイラですが、Borland C++Compiler 5.5.1 を使っています。

投稿日時 - 2007-07-18 05:05:56

このQ&Aは役に立ちましたか?

0人が「このQ&Aが役に立った」と投票しています

回答(10)

ANo.10

★質問者さんと MASA_H さんへ。
・いろいろと調べたらテーブル参照の方が遅かったです。
 もう一つテーブルを用意して2段階にしても MASA_H さんのとほぼ同じ速度でした。
 よって素直に回答者 No.9(MASA_H)さんの一つ一つ確認版が最終版ですかね。
・下にそのソースを載せておきます。

最終版:
#include <time.h>
#include <stdio.h>

// 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\n", 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秒\n", i, h, l, (t / 1000), (t % 1000) );
  }
 }
 printf( "-- 終了 --\n" );
 return 0;
}
以上。

投稿日時 - 2007-07-21 15:53:32

補足

欄が逆になってしまいますが、ここで最後のお礼をさせていただきます。
計測の結果はやはり質問時の方が早かったです…。
ただ、これから忙しくなり、お礼ができなくなると思いますので、勝手ながらここで締め切らせて頂きます。

最後に、回答してくれた皆様にお礼申し上げます。
ありがとうございました^^

投稿日時 - 2007-07-23 04:35:35

お礼

後で10^8の時間を比較してみようかと思います^^
unsigned long long は ULONGLONG で置き換えると遅くなるとかいう事はないですよね。

投稿日時 - 2007-07-22 08:20:27

ANo.9

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

投稿日時 - 2007-07-21 06:31:06

お礼

計測していただきありがとうございました。
テーブルはここで初めて知ったので…これを機会に調べてみようかと思います^^

投稿日時 - 2007-07-22 08:14:12

ANo.8

★回答者 No.2、No.6、No.7 です。
>試してみたところ、(1)ではエラーが出ましたが他は出ませんでした。
 ↑
 (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;
 として参照しているので警告が出るのはおかしい。
 もし、警告が出るとすると上記の3行が記述されていないことになるが…。
 記述していますよね?
・でも記述しているのならこの手の警告は無視して良いです。
 無駄な変数が見つかったよ。とコンパイラさんが教えてくれているだけなので。
 また、この警告が出るということはオプションで一番高く設定されていますね。
 特に警告メッセージに問題はないです。
・あと clock() 関数で時間を計測していますが表示とかに問題はありませんか?
 特に問題が無ければ double 型や多倍長整数演算のものよりは早く計算できると
 思います。私の環境では最初の『進行状況』が表示されるのに約3.1秒かかります。
 この速度で終了するまで実行すると約36分かかりました。
・あと main() 関数の for() 処理後に1行『printf( "-- 終了 --\n" );』を
 追加しておいて下さい。追加しても、追加しなくてもどちらでも良いですけど。
 その他、調べる数を『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秒
-- 終了 --

投稿日時 - 2007-07-20 06:24:51

お礼

計算結果は正しく出ました。
ただ、速度は10^8個を調べるのに1100秒かかりました。
clock()は動作していたので、質問時のものにclock()を付け加えて10^8個を計測したところ133秒でした…;;
64 ビット整数として計算できていないのでしょうか…。

投稿日時 - 2007-07-20 09:51:04

ANo.7

★追記。回答者 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 );
 として文字列に変換すればよい。
 
・以上。いろいろと試すか、コンパイラを変えるように。

投稿日時 - 2007-07-19 12:47:18

お礼

> 試しに次の型が利用できるか調べて見て下さい。
試してみたところ、(1)ではエラーが出ましたが他は出ませんでした。
初めて見たものなのでよくわからないのですが…新しいコンパイラに変える必要はないでしょうか…?

ちなみに、No.6で作って頂いたサンプルのi,xの宣言をULONG64 かULONGLONG にすればコンパイルでき、動作しました^^
ただ、、
32行目:'value'に代入した値は使われていない
と警告が出るのですが、これは正常なのでしょうか?

投稿日時 - 2007-07-20 02:10:14

ANo.6

★回答者 No.2 です。私も作ってみました。
・テーブルを用いて2種類の数字かどうかを判定しています。
 下の『全角文字』を一括して『タブ文字』に変換するとコメントが揃います。
・あと long long 型が利用できないとエラーとなります。
 この場合は x を double 型にして for のループを 10000000(10の7乗)にします。
 その他 x 変数に関わる printf() の書式制御文字などを修正すればコンパイルが
 可能になると思います。
・それでは下にサンプルを載せておきます。

サンプル:
#include <time.h>
#include <stdio.h>
#include <string.h>

/* 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\n", 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秒\n", i, h, l, (t / 1000), (t % 1000) );
  }
 }
 return 0;
}
以上。

投稿日時 - 2007-07-18 23:10:41

ANo.5

zwi

回答 No.3です。
gccで動作試してみましたが高速化してません。速度のネックは、やはりdoubleの計算と文字列に変換しているところにありそうです。
それとOUTのgotoは外さない方が高速化できそうなので残しました。
高速化のポイントは、for文のループ回数を出来るだけ減らすこと、if文の回数を減らすことなのですが、それ以外の部分で重いとさほど効果はありません。
clock()関数はgccなら問題ありませんが、bccで問題がある場合は外してください。

#include <stdio.h>
#include <string.h>
#include <time.h>
int main(void){
  double i;  //平方根
  int m;    //整数(for用)
  double x;  //平方数
  char str[100];  //文字列(途中作業用)
  int mono[100];  //1桁の数字(途中作業用)
  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<len; m++) {
      mono[m]=str[m]-48;      //一桁ずつint型に収納+実際の数に調整。
    }
      
    m=(int)i;
//※ {}を書かないif文やfor文はプログラムの可読性が下がるので避けたほうがバグが減ります。
    if( m%2000000==0) {
      printf("i=%32.0f:ok - ",i);  //進行状況
    }
      
    num=0;
    for( m=1; m<len; m++){
//※ 無理にひとつにまとめる必要も無いと思います。
      if( mono[m]==0 ) {
        goto OUT;//ループを抜けます。
      }
//※ num == 0を先の条件にした方が早くなります。条件不成立の場合は、後ろの条件をチェックしないため。
      if( num==0 && mono[m]!=mono[0] ) {
        num=m;
      }
      if( mono[m]!=mono[0] && mono[m]!=mono[num] ) {
        goto OUT;//ループを抜けます。
      }
    }
    t1 = clock();
    printf("%5.0f => %26.0f time=%d \n", i, x, t1-t0);
OUT:;
  }
  return 0;
}

投稿日時 - 2007-07-18 21:07:27

お礼

> {}を書かないif文やfor文はプログラムの可読性が下がるので避けたほうがバグが減ります。
以後気をつけようと思います^^

> num == 0を先の条件にした方が早くなります。条件不成立の場合は、後ろの条件をチェックしないため。
なるほど…、ためになります。
こういうところも注意して書かないとだめですね。

参考にしてまた見直してみようかと思います。
ありがとうございました。

投稿日時 - 2007-07-20 01:02:16

ANo.4

気分転換にGMPを使ったものを書いたので貼っときます。最適化も何も考えてないのでceleron2.6GHzで21474836個の探索をするのに12秒程度かかります。

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include <string.h>
#include <gmp.h>
#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<len;j++){
if(ntmp[j]=='0'||(ntmp[j]!=num[0]&&ntmp[j]!=num[1])){
flag=j;
break;
}
}
}

if(flag==0){
mpz_get_str(ptmp,10,x);
printf("%s -> %s\n",ptmp,ntmp);
}
mpz_add_ui(y,x,1);
mpz_set(x,y);
if((i%2000000)==0)printf("(%d/%d)\n",i,SMAX);
}
mpz_clear(x);
mpz_clear(y);
return(0);
}

投稿日時 - 2007-07-18 02:13:30

お礼

>最適化も何も考えてないのでceleron2.6GHzで21474836個の探索をするのに12秒程度かかります。
皆さんの意見を参考に色々変えてみましたが、celeron1.6GHzで21474836個の探索が26秒かかりました。
質問時は35秒程度かかっていたので大分早くなりました^^

GMPはまだわかりませんが、導入したらまず参考にさせて頂きます。
回答ありがとうございました。

投稿日時 - 2007-07-18 18:46:48

ANo.3

zwi

プログラムの問題点がいくつかあるので上げます。
・gotoが多すぎます。if文の工夫やforループのcontinue文の導入で、全部のgoto文を一掃できます。
・高速化のためにはループを減らしてください。下3つのfor文は1つにできると思います。
・mono[num]は変数に値を代入して、それ以外の部分も添え字で配列を扱うよりもポインタに変えたほうが高速化できます。

根本的な問題の件は、gmp(GNU Multi Precision - 任意精度数演算ライブラリ)を使えば解決できると思えますが、自力で調べて導入する必要があります。
http://www001.upp.so-net.ne.jp/tklab/linux/sci1a.html
windowsでの導入方法。
http://taylor.gotdns.org/gmp.html

投稿日時 - 2007-07-17 22:22:38

お礼

> gotoが多すぎます。if文の工夫やforループのcontinue文の導入で、全部のgoto文を一掃できます。
WHENSAME と PRINT は消せました。
ただ、あと一つのgoto OUT; の消し方が思いつきませんでした…。
何か良い方法があれば教えてください。

> 高速化のためにはループを減らしてください。下3つのfor文は1つにできると思います。
num=0;
for( m=1; m<len; m++){
  if( mono[m]!=mono[0] && num==0)
    num=m;
  if( mono[m]!=mono[0] && mono[m]!=mono[num] || mono[m]==0)
    goto OUT;
}
なんとか一つにまとめる事ができました。
これから気を付けていこうと思います。

> mono[num]は変数に値を代入して、それ以外の部分も添え字で配列を扱うよりもポインタに変えたほうが高速化できます。
ポインタはまだどういうものなのか調べただけで使った事がないので、できるかどうかわかりませんが…、色々試してみようかと思います^^

> 任意精度数演算ライブラリ
こういうものもあるんですね。
小さい桁数をマスターできたら導入してみようかと思います。
ありがとうございました。

投稿日時 - 2007-07-18 18:22:00

ANo.1

>x=i*i;              //二乗
まずこれが破綻しています。

doubleは10進数で考えると有効桁数がせいぜい15桁の精度です。
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)を明示的に使うか
それより大きな桁数の数値を扱う場合は
多倍長演算を考慮しなければなりません。
実装方法は色々とありますが、まずこの部分を考慮した
プログラムを実装する必要があると思います。

投稿日時 - 2007-07-17 18:46:16

お礼

> 64bit型のunsigned 整数型(0~18,446,744,073,709,551,615)を明示的に使う
調べてみましたが、unsined long long int の事でしょうか?
どのように使えばいいのかわからないのですが…教えていただけると助かります。
普通にint等と同じように使おうとするとエラーが出てしまって…;;

多倍長演算は、とりあえずそれ以下の桁数を使いこなせるようになってから詳しく調べてみようかと思います^^

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

投稿日時 - 2007-07-18 04:46:26