100の階乗が0となる

Question

聞きたいこと

100の階乗を計算したいのだが、途中から値が負となり、80ごろから0になります。
どうすれば正しい値を計算できますか？
コード

#include <stdio.h>
#include <math.h>
#define N 100

int main(void){
  long int num = 1,i;
  for(i = 1; i <= 100 ; i++ ){
    num = num * i;
    printf("%ld\n",num);
  }
  //printf("%d", num);
  return 0;

}

Comments

[Zuishin]

答えは 93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000 です。long int では足りません。

Answer 1

doubleとかではなく、多倍長計算でなければ正確に計算できません。

GMP(GNU Multi-Precision Library)を使った例

#include <gmp.h>
#include <stdio.h>

int main(void)
{
  // 入力&チェック
  long long n;
  scanf("%lld", &n);
  if (n < 0) {
    printf("n must be positive or 0.\n");
    return 0;
  }

  // n!を計算
  mpz_t x;
  mpz_init(x);
  mpz_set_ui(x, 1);
  for (long long i = 2; i <= n; i++) {
    mpz_mul_ui(x, x, i);
  }

  // 結果
  gmp_printf("%Zd\n", x);

  // 解放
  mpz_clear(x);
  return 0;
}

実行結果

(入力)100
(出力)93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000

Answer 2

環境が不明ですが、オーバーフローです。
long で表現できる範囲を越えています。

それ以上は、多倍長計算とか、別の方法を検討してください。

Comments

[naka]

回答ありがとうございます！
解決しました。

Answer 3

あなたが使っているC言語の処理系のlong intが扱える整数の範囲を調べましょう。32ビット符号付き整数だとすると、12の階乗までしか保持できません。

long long intが64ビット符号付き整数なら20の階乗までは保持できますが、いずれにしろ100の階乗は無理ですね。

追加分:
いや、doubleにしても有効桁数の制限があるので、正確な値は出ませんよ。

(多倍長整数を扱える)Pythonでやってみると、どのくらいの桁数かわかります。

n = 1
for i in range(1, 101):
    n *= i
    print(n)

1
2
6
24
120
(中略)
933262154439441526816992388562667004907159682643816214685929638952175999932299156089414639761565182862536979208272237582511852109168640000000000000000000000
93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000

Comments

[naka]

範囲を考えていませんでした。
double型でフォーマットを%eにしたところうまくいきました。
ありがとうございます。