階乗

Cで、結果が大きな数値になる階乗を計算する例がいくつかあった。

• 階乗 n! の計算　factorial
• 階乗の計算を行う(C言語)

しばらくにらめっこして、自分なりに書き直してみる。

#include <stdio.h>
#include <stdlib.h>

#define SUPREMUM 10000

void multi_bignum(int *bignum, int *len, int n) {
  int carry = 0, i;

  for (i = 0; i < *len; i++) {
    // 配列には４桁ずつ格納される
    long tmp = bignum[i];

    // ４桁の値 × n ＋ 桁上がり
    tmp = tmp * n + carry;

    // 下位４桁を配列に格納
    bignum[i] = tmp % SUPREMUM;

    // 桁上がりを計算
    carry = tmp / SUPREMUM;
  }

  if (carry > 0) {
    bignum[i] = carry;
    (*len)++;
  }
}

void factorial(int *bignum, int *len, int n) {
  int i;
  bignum[0] = 1;

  for (i = 1; i <= n; i++) {
    multi_bignum(bignum, len, i);
  }
}

void puts_bignum(int *bignum, int len) {
  int i;
  char *fmt = "%d";

  for (i = len - 1; i >= 0; i--) {
    printf(fmt, bignum[i]);
    fmt = "%04d";
  }

  printf("\n");
}

int main(int argc, char *argv[]) {
  int n;
  int bignum[256];
  int len = 1;

  if (argc != 2) {
    exit(1);
  }

  n = atoi(argv[1]);
  factorial(bignum, &len, n);
  puts_bignum(bignum, len);

  return 0;
}

~/work$ gcc ex.c -o ex && ./ex 30

265252859812191058636308480000000