半径が非常に大きいときに整数の格子点から円周率を近似する

Question

質問内容

タイトルの通りにはなるのですが，半径が最大で1億(100000000)の円が内部に含む格子点の数から円周率を近似するときに半径が10000まではしっかり出来ているのですが100000になると-214294.212864207070000というようにあり得ない数値が出てしまいます．なぜこのような負の数が出てしまうのかということと，計算時間が短縮するための工夫を教えていただきたいです．よろしくお願いいたします．

コード

#include<stdio.h> 
#include<math.h> 
double count(int m){ 
    long long check=0;
    double answer;
    for(int i=1;i<=m;i++){
        check+=(int)sqrt(m*m-i*i);
    }
    answer=((double)(check*4+m*4+1)/(double)(m*m));   
    return answer; 
} 
int main(void){    
    int n; 
    scanf("%d",&n); 
    printf("%d:%.15f\n",n,count(n)); 
    return 0; 
}

Answer 1

100000になると-214294.212864207070000というようにあり得ない数値が出てしまいます．

m*mがintで計算できる範囲を超えている、ということかと思います。

Comments

[grape_ll]

ご指摘いただいた通り，intの範囲を超えていたみたいでlong longにしてみたのですが，100000000ではマイナスにならないのに50000,1000000ではマイナスになるといったことが起きてしまいました．これはより大きい数字で出来ているのでlong long で足りないなどの話では解決できなさそうと考えたのですが，対処法などはありますでしょうか．
また本来半径が大きくなれば円周率の精度もよくなるはずなのですが，100000では精度が落ちていました．このことについてもぜひ教えていただければと思います．

コードは以下のようにしました．
#include<stdio.h>
#include<math.h>
double count(int m){
long long check=0;
double answer;
for(int i=1;i<=m;i++){
check+=(long long)sqrt(m*m-i*i);
}
answer=((double)(check*4+m*4+1)/(double)(m*m));
return answer;
}
int main(void){
int n;
scanf("%d",&n);
printf("%d:%.15f\n",n,count(n));
return 0;
}

[maisumakun]

> long longにしてみたのですが

なっていません。依然としてm*mはintで計算されます。

[maisumakun]

（引数のmもlong longで受け取るようにしてしまうのが、手抜きですがいちばん確実です）

[grape_ll]

#include<stdio.h>
#include<math.h>
double count(long long m){
long long check=0;
double answer;
for(int i=1;i<=m;i++){
check+=(long long)sqrt(m*m-i*i);
}
answer=((double)(check*4+m*4+1)/(double)(m*m));
return answer;
}
int main(void){
long long n;
scanf("%lld",&n);
printf("%lld:%.15f\n",n,count(n));
return 0;
}
このようなコードにしてみたのですが．1000000あたりから精度が悪くなり4.0付近になってしま運みたいなのですが，どうすればよいでしょうか．よろしくお願いいたします．

[maisumakun]

iがintなので、i*iがオーバーフローしています。これもlong longにするか、(long long)i*iのようにしてintでの乗算を回避してください。

[grape_ll]

46000を超えたあたりから精度が悪くなっているようです

PS C:\Users\rokok\pro\proc\01> ./try
35000:3.141592360000000
40000
40000:3.141592205625000
45000
45000:3.141592322469136
50000
50000:3.459391803600000
47500
PS C:\Users\rokok\pro\proc\01> ./try
47500
47500:3.262891079002770
PS C:\Users\rokok\pro\proc\01> ./try
47000
47000:3.213940438660027
PS C:\Users\rokok\pro\proc\01> ./try
46000
46000:3.141592223534972
PS C:\Users\rokok\pro\proc\01> ./try
46500
46500:3.160249821713493

[grape_ll]

ご指摘いただいた通り，iについてもlong long にしたところ計算はうまくいったように思われます．
ありがとうございます．
計算時間も問題ないみたいです．
ただ，1億のときの精度が少し足りないようなのですが工夫するところはありますでしょうか．よろしくお願いいたします．

自分
100000000:3.141592653586803

例
100000000:3.141592653586796

#include<stdio.h>
#include<math.h>
double count(long long m){
long long check=0;
double answer;
for(long long i=1;i<=m;i++){
check+=(long long)sqrt(m*m-i*i);
}
answer=((double)(check*4+m*4+1)/(double)(m*m));
return answer;
}
int main(void){
long long n;
scanf("%lld",&n);
printf("%lld:%.15f\n",n,count(n));
return 0;
}

Answer 2

「m * m - i * i」とか「m * m」とか、int同士の掛け算をしているところがありますね。
おそらくお使いの処理系ではintが32ビット長で、符号付きなので±21億ちょっとまでしか扱えません。
100000 * 100000で100億になるので、範囲を超えてしまっていおり、正しい値になりません。
なぜ負の値になるのかは、「2の補数」で検索してみてください。

Comments

[grape_ll]

おっしゃる通り，intでは足りないようでしたのでlong long でやらせていただいたのですが，100000000ではマイナスにならないのに50000,1000000ではマイナスになるといったことが起きてしまいました．これはより大きい数字で出来ているのでlong long で足りないなどの話では解決できなさそうと考えたのですが，対処法などはありますでしょうか．
また本来半径が大きくなれば円周率の精度もよくなるはずなのですが，100000では精度が落ちていました．このことについてもぜひ教えていただければと思います．

コードは以下のようにしました．
#include<stdio.h>
#include<math.h>
double count(long long m){
long long check=0;
double answer;
for(int i=1;i<=m;i++){
check+=(long long)sqrt(m*m-i*i);
}
answer=((double)(check*4+m*4+1)/(double)(m*m));
return answer;
}
int main(void){
long long n;
scanf("%lld",&n);
printf("%lld:%.15f\n",n,count(n));
return 0;
}

[Daregada]

キャストの使い方を確認してみてください。sqrtの「返り値」を long long int にキャストしていますが(これはやらなくても暗黙の型変換で long long int になります)、やらなくてはいけないのは、「掛け算をする前に m を long long int にキャストする」ことです。

[grape_ll]

他の方にもご指摘いただいたので訂正させていただきました．
勉強不足で申し訳ございません．
お手数かとは思いますがご確認お願い致します。
#include<stdio.h>
#include<math.h>
double count(long long m){
long long check=0;
double answer;
for(int i=1;i<=m;i++){
check+=(long long)sqrt(m*m-i*i);
}
answer=((double)(check*4+m*4+1)/(double)(m*m));
return answer;
}
int main(void){
long long n;
scanf("%lld",&n);
printf("%lld:%.15f\n",n,count(n));
return 0;
}

[Daregada]

いやなんで確認まですることになってるのさ。