C言語での大きな数の出力：エクセルに似たようなことをしたい

Question

以下のような、順列nPrと組み合わせnCrを、n、rを0～100の範囲で変化させて計算して結果をCSVファイルに出力するプログラムを、C言語で作成してみました。

該当のソースコード

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

void procedure(int i);
unsigned long long int permutation(int n, int r);
unsigned long long int combination(int n, int r);

int main(void)
{
	int i;
	
	for (i = 0; i < 2; i++)
		procedure(i);
	
	return EXIT_SUCCESS;
}

void procedure(int i)
{
	int j, k;
	FILE *fp1, *fp2;
	unsigned long long int ans;
	
	switch (i) {
	 case 0:
		fp1 = fopen("output1.csv", "a");
		if (fp1 == NULL) {
			printf("ファイルを開けません。処理を中断します。\n");
			return;
		}
		for (j = 0; j <= 100; j++)
			for (k = 0; k <= j; k++) {
				ans = permutation(j, k);
				fprintf(fp1, "%dP%d,%llu\n", j, k, ans);
			}
		fclose(fp1);
		break;
	 case 1:
		fp2 = fopen("output2.csv", "a");
		if (fp2 == NULL) {
			printf("ファイルを開けません。処理を中断します。\n");
			return;
		}
		for (j = 0; j <= 100; j++)
			for (k = 0; k <= j; k++) {
				ans = combination(j, k);
				fprintf(fp2, "%dC%d,%llu\n", j, k, ans);
			}
		fclose(fp2);
		break;
	 default:
		break;
	}
}

/* 順列 */
unsigned long long int permutation(int n, int r)
{
	int i;
	unsigned long long int ans = 1;
	
	if ((n == 0) || (r == 0))
		;
	else
		for (i = 0; i < r; i++)
			ans *= (n - i);
	
	return ans;
}

/* 組み合わせ */
unsigned long long int combination(int n, int r)
{
	int i;
	unsigned long long int ans = 1;
	
	if (r > n - r)
		r = n - r;
	
	if ((n == 0) || (r == 0))
		;
	else
		for (i = 1; i <= r; i++) {
			ans *= (n - r + i);
			ans /= i;
		}
	
	return ans;
}

結果、当然と言えば当然ですが、大きな数値に対しては、出力がおかしくなりました。値のオーバーフローによるものだと思います。

エクセルのPERMUT関数とCOMBIN関数の結果と照合している途中に気付き、少し調べてみたら、エクセルでは

「値がある程度大きくなったら、『●●E▲▲』(●●掛ける10の▲▲乗)の形で出力し、エクセルの処理できる正の最大値9.99999999999999E+307を超えたら、#NUM!と出力する」

ことが分かりました。

そこで、エクセルとは値の範囲が異なりますが、エクセルに似たことができるように改変したいのですが、どのように変えればよいか、見当が付きません。

実際に、「60種のうちから5種を選ぶ組み合わせ(60C5)」を計算する必要があり(計算結果は5,461,512通り)、実用に耐えるものを作りたい、というのが、そもそもの作成動機です。

お助けください。

Comments

[maisumakun]

> 実際に、「60種のうちから5種を選ぶ組み合わせ(60C5)」を計算する必要があり(計算結果は5,461,512通り)、実用に耐えるものを作りたい、というのが、そもそもの作成動機です。

それぐらいの値なら、このコードで正常動作します。

https://paiza.io/projects/JMfHBy67z8r0IWyahxnvGw

[sanshirou]

コメントありがとうございます。nPrまたはnCrのn、rを、固定ではなく可変にしたいのです。キーボードからn、rを入力を受け付けるが、さまざまなn、rの値に対して、エクセルに似たような出力ができるようにしたい、というのが希望です。

[melian]

GNU MP の様な多倍長整数演算ライブラリを利用してみてはどうでしょうか。

The GNU MP Bignum Library
https://gmplib.org/

[utm.]

そもそもとして100の階乗ですら桁数がとんでもなくなるので、大きい数値を扱えるようにするしかないのでは無いでしょうか

Answer 1

質問のコメントで言及した The GNU MP Bignum Library を利用する場合です。

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

void procedure(int i);
void permutation(uint j, uint k, mpz_t *r);
void combination(uint j, uint k, mpz_t *r);
void save_result_to_file(void (*func)(uint, uint, mpz_t*), char *file_name);

#define LIMIT 1e9

int main(void)
{
  save_result_to_file(&permutation, "output1.csv");
  save_result_to_file(&combination, "output2.csv");
}

void save_result_to_file(void (*func)(uint, uint, mpz_t*), char *file_name) {
	FILE *fp = fopen(file_name, "w");
  if (fp == NULL) {
    fprintf(stderr, "ファイルを開けません。処理を中断します。\n");
    return;
  }

	uint j, k;
  mpz_t result, overflow;
  mpf_t tmp_float;
  char result_type = (func == &permutation) ? 'P' : 'C';
  char *result_str;

  mpz_init(result);	
  mpf_init(tmp_float);
  mpz_set_d(overflow, DBL_MAX);
  for (j = 0; j <= 100; j++)
    for (k = 0; k <= j; k++) {
      (*func)(j, k, &result);
      if (mpz_cmp(result, overflow) > 0) {
        result_str = NULL;
      } else if (mpz_cmp_ui(result, LIMIT) > 0) {
        mpf_set_z(tmp_float, result);
        gmp_asprintf(&result_str, "%.4FE", tmp_float);
      } else {
        result_str = mpz_get_str(NULL, 10, result);
      }
      fprintf(fp, "%d%c%d,%s\n", j, result_type, k,
              result_str ? result_str : "#NUM!");
      free(result_str);
    }
  fclose(fp);
  mpz_clear(result);
  mpz_clear(overflow);
  mpf_clear(tmp_float);
}

void permutation(uint m, uint n, mpz_t *r) {
  if (m == 0 || n == 0) {
    mpz_set_ui(*r, 1);
    return;
  }
  mpz_init(*r);
  for(mpz_init_set_ui(*r,m);n>1;m--,n--,mpz_mul_ui(*r,*r,m));
  return;
}

void combination(uint m, uint n, mpz_t *r) {
  if (m == 0 || n == 0) {
    mpz_set_ui(*r, 1);
    return;
  }
  mpz_init(*r);
  mpz_t r1, r2;
  mpz_init(r1); mpz_init(r2);
  permutation(m, n, &r1); permutation(n, n, &r2);
  mpz_cdiv_q(*r, r1, r2);
  mpz_clear(r1); mpz_clear(r2);
  return;
}

Answer 2

・結果が10億以上の場合は、double型にキャストして、指数形式で出力する。
・結果がオーバーフローしたかどうかの関数を作って判定し、その場合は「#NUM!」と出力する。
という風にしました。ご回答ありがとうございました。

Comments

[PingHermit]

エクセルは、double を使っているようですので、
下位桁の誤差も同様に出ますから、
必要であればそれの確認も必要かと思います。
誤差程度であれば問題ないならdoubleでも大丈夫ですが。

Answer 3

必ずしも1の位まで完全に正しい結果が出なくていいのであれば、浮動小数点数（double）を使って計算する、という手段は考えられます。

Comments

[sanshirou]

ありがとうございます。検討してみます。