doubleの時とintの時での違い

Question

ゼロではない正の整数2個（n, r）を引数として与えられて，n個からr個を順に取り出す組み合わせの数（順列の数）を求める関数を作成し，それを利用して入力された2個の正整数の組から順列の数を求めるプログラムを作成したのですが、関数でint型を使った時とdouble型を使った時で答えが違っていました。僕は最初代入するのは整数だったので、int型でもオッケーだと思ったのでしたが、例えば、（20、5）や（99、3）を入れた時がダメでした。なぜでしょうか？

①正解を出せてるプログラム
#include <stdio.h>

int permutation (int n, int r)
{
double a, b, productn, productr, permutation;

productn = 1;
productr = 1;
permutation = 1;

for ( a = 1 ; a <= n ; a++ ){
productn *= a;
}
for ( b = 1 ; b <= n-r; b++){
productr *= b;
}
permutation = productn / productr;
return permutation;

}

int main(void)
{
int c, d;
scanf ("%d", &c);
scanf ("%d", &d);

printf("%d\n", permutation( c, d ));

return 0;

}

②誤っているプログラム

#include <stdio.h>

int permutation (int n, int r)
{
int a, b, productn, productr, permutation;

productn = 1;
productr = 1;
permutation = 1;

for ( a = 1 ; a <= n ; a++ ){
productn *= a;
}
for ( b = 1 ; b <= n-r; b++){
productr *= b;
}
permutation = productn / productr;
return permutation;

}

int main(void)
{
int c, d;
scanf ("%d", &c);
scanf ("%d", &d);

printf("%d\n", permutation( c, d ));

return 0;

}

Answer 1

int が４バイト（32bit）だと、オーバーフローするため、正しい結果が出ませんね
doubleになると、52bitの仮数部が使えるため、オーバーフローせずに算出することができます

Answer 2

int だとオーバーフローが発生するからです。
long long int にしてみてください。
変数のサイズは環境依存ですが、よくある環境では、intが4バイト、long long intが8バイトです。

Comments

[ryu72639]

もし、n>=100 じゃないと入力できないとしたり、n=100 r = 50など計算が膨大なものになってしまうときはどうしたらいいのでしょうか？

[otn]

long long で19桁くらいまで計算できますが、それで足りないときは多倍長計算ライブラリを使います。
https://ja.wikipedia.org/wiki/%E4%BB%BB%E6%84%8F%E7%B2%BE%E5%BA%A6%E6%BC%94%E7%AE%97#%E3%83%A9%E3%82%A4%E3%83%96%E3%83%A9%E3%83%AA