Floating point exception: 8のエラー

[hogged]

コード:

#include <stdio.h>

int main(void)
{
	int W, H;
	int num;
	int i, j, k;
	int WH = 0; //初期化
	int resultW = 1;
	int resultH = 1;
	int resultWH = 1;
	
	scanf("%d", &W);
	scanf("%d", &H);

	WH = (W + H) - 2;

	for (i = 1; i <= W - 1; i++)
	{
		resultW *= i;
	}
	
	for (j = 1; j <= H - 1; j++)
	{
		resultH *= j;
	}

	for (k = 1; k <= WH; k++)
	{
		resultWH *= k;
	}

	num = resultWH / (resultW * resultH);
	
	printf("%d\n", num % 1000000007);

	return 0;
}

このプログラムで出たエラーなのですが、W＝３、H＝４の時などは正常な回答がでるのですが、W＝１２３、H＝４５６などではエラーが出てしまいます。なぜですか？

[box]

このプログラムで出たエラーなのですが、W＝３、H＝４の時などは正常な回答がでるのですが、W＝１２３、H＝４５６などではエラーが出てしまいます。なぜですか？

123!とか456!とかが、お使いの処理系で表わせる浮動小数点数の範囲を超えているからでしょう。

[hogged]

このプログラムで出たエラーなのですが、W＝３、H＝４の時などは正常な回答がでるのですが、W＝１２３、H＝４５６などではエラーが出てしまいます。なぜですか？

123!とか456!とかが、お使いの処理系で表わせる浮動小数点数の範囲を超えているからでしょう。

このプログラムのどこを修正すれば正常に動きますか？　変数の型を変えればいいのでしょうか？

[みけCAT]

このプログラムで出たエラーなのですが、W＝３、H＝４の時などは正常な回答がでるのですが、W＝１２３、H＝４５６などではエラーが出てしまいます。なぜですか？

122の階乗はおよそ10の203乗であり、このような巨大な数はほとんどのC言語の処理系でint型には入らないでしょう。
符号付き整数のオーバーフローはundefined behaviorになります。
おそらくたまたま計算結果が0になり、33行目でゼロ除算が発生したのでしょう。

123!とか456!とかが、お使いの処理系で表わせる浮動小数点数の範囲を超えているからでしょう。

このプログラムでは浮動小数点数は使われていないので、これは誤りでしょう。

[みけCAT]

このプログラムのどこを修正すれば正常に動きますか？　変数の型を変えればいいのでしょうか？

ライセンスが受け入れられるのであれば、The GNU MP Bignum Libraryなど多倍長計算ライブラリを使うのが簡単でしょう。
もちろん多倍長計算を自前で実装したり、Pythonなどの多倍長計算が標準でサポートされた言語に切り替えるという方法もあります。
また、1000000007は素数なので、この環境のint型が0から2の31乗-1までの整数を保持できるのであれば、有限体上で計算することで多倍長計算を用いずに実装することもできるでしょう。

[hogged]

このプログラムのどこを修正すれば正常に動きますか？　変数の型を変えればいいのでしょうか？

ライセンスが受け入れられるのであれば、The GNU MP Bignum Libraryなど多倍長計算ライブラリを使うのが簡単でしょう。
もちろん多倍長計算を自前で実装したり、Pythonなどの多倍長計算が標準でサポートされた言語に切り替えるという方法もあります。
また、1000000007は素数なので、この環境のint型が0から2の31乗-1までの整数を保持できるのであれば、有限体上で計算することで多倍長計算を用いずに実装することもできるでしょう。

unsigned long int にしてみたのですが、結果は同じでした。　

コード:

#include <stdio.h>

int main(void)
{
	int W, H;
	unsigned long num;
	int i, j, k;
	int WH = 0; //初期化
	unsigned long resultW = 1;
	unsigned long resultH = 1;
	unsigned long resultWH = 1;
	
	scanf("%d", &W);
	scanf("%d", &H);

	WH = (W + H) - 2;

	for (i = 1; i <= W - 1; i++)
	{
		resultW *= i;
	}
	
	for (j = 1; j <= H - 1; j++)
	{
		resultH *= j;
	}

	for (k = 1; k <= WH; k++)
	{
		resultWH *= k;
	}

	num = resultWH / (resultW * resultH);
	
	printf("%ld\n", num % 1000000007);

	return 0;
}

unsigned long は0~4294967295でもダメみたいですね。
やはり多倍長整数の型を作らないといけないようですね。

[box]

おっと失礼。間違った回答をしてしまいました。
さておき、unsigned long intにしたところで、状況が改善されるとは思えません。
30!でも10^32のオーダーになってしまいますから。
122!とかの厳密な値がほしければ、Wolframあたりにお任せするとか。

[みけCAT]

やはり多倍長整数の型を作らないといけないようですね。

いいえ。この計算なら、各計算ごとにmodをとれば多倍長整数は必要ありません。

コード:

#include <stdio.h>
#include <inttypes.h>

#define MOD_BY UINT32_C(1000000007)

/* a * b mod MOD_BY を計算する */
uint32_t mul(uint32_t a, uint32_t b) {
	uint32_t result = 0;
	while (b > 0) {
		/* 今の掛ける数が奇数なら、掛けられる数を結果に足す */
		if ((b & 1) != 0) {
			result += a;
			if (result >= MOD_BY) result -= MOD_BY;
		}
		/* 掛ける数を2で割る */
		b >>= 1;
		/* 掛けられる数を2倍にする */
		a <<= 1;
		if (a >= MOD_BY) a -= MOD_BY;
	}
	return result;
}

/* pow(a, n) mod MOD_BY を計算する */
uint32_t powint(uint32_t a, uint32_t n) {
	uint32_t result = 1;
	while (n > 0) {
		if ((n & 1) != 0) result = mul(result, a);
		n >>= 1;
		a = mul(a, a);
	}
	return result;
}

/* a / b mod MOD_BY を計算する */
uint32_t div(uint32_t a, uint32_t b) {
	/* フェルマーの小定理より、MOD_BYが素数の時bの逆元はpow(b, MOD_BY - 2) */
	return mul(a, powint(b, MOD_BY - 2));
}

int main(void)
{
	int W, H;
	uint32_t num;
	int i, j, k;
	int WH = 0; //初期化
	uint32_t resultW = 1;
	uint32_t resultH = 1;
	uint32_t resultWH = 1;
	
	if (scanf("%d", &W) != 1) return 1;
	if (scanf("%d", &H) != 1) return 1;

	WH = (W + H) - 2;

	for (i = 1; i <= W - 1; i++)
	{
		resultW = mul(resultW, i);
	}
	
	for (j = 1; j <= H - 1; j++)
	{
		resultH = mul(resultH, j);
	}

	for (k = 1; k <= WH; k++)
	{
		resultWH = mul(resultWH, k);
	}

	num = div(resultWH, mul(resultW, resultH));
	
	printf("%"PRIu32"\n", num);

	return 0;
}

WolframAlphaで(W, H) = (123, 456), (12345, 67890), (123456, 789012)について検算しました。

[box]

また変な回答をしてしまったみたいであるが、気にしないことにする。

[hogged]

やはり多倍長整数の型を作らないといけないようですね。

いいえ。この計算なら、各計算ごとにmodをとれば多倍長整数は必要ありません。

コード:

#include <stdio.h>
#include <inttypes.h>

#define MOD_BY UINT32_C(1000000007)

/* a * b mod MOD_BY を計算する */
uint32_t mul(uint32_t a, uint32_t b) {
	uint32_t result = 0;
	while (b > 0) {
		/* 今の掛ける数が奇数なら、掛けられる数を結果に足す */
		if ((b & 1) != 0) {
			result += a;
			if (result >= MOD_BY) result -= MOD_BY;
		}
		/* 掛ける数を2で割る */
		b >>= 1;
		/* 掛けられる数を2倍にする */
		a <<= 1;
		if (a >= MOD_BY) a -= MOD_BY;
	}
	return result;
}

/* pow(a, n) mod MOD_BY を計算する */
uint32_t powint(uint32_t a, uint32_t n) {
	uint32_t result = 1;
	while (n > 0) {
		if ((n & 1) != 0) result = mul(result, a);
		n >>= 1;
		a = mul(a, a);
	}
	return result;
}

/* a / b mod MOD_BY を計算する */
uint32_t div(uint32_t a, uint32_t b) {
	/* フェルマーの小定理より、MOD_BYが素数の時bの逆元はpow(b, MOD_BY - 2) */
	return mul(a, powint(b, MOD_BY - 2));
}

int main(void)
{
	int W, H;
	uint32_t num;
	int i, j, k;
	int WH = 0; //初期化
	uint32_t resultW = 1;
	uint32_t resultH = 1;
	uint32_t resultWH = 1;
	
	if (scanf("%d", &W) != 1) return 1;
	if (scanf("%d", &H) != 1) return 1;

	WH = (W + H) - 2;

	for (i = 1; i <= W - 1; i++)
	{
		resultW = mul(resultW, i);
	}
	
	for (j = 1; j <= H - 1; j++)
	{
		resultH = mul(resultH, j);
	}

	for (k = 1; k <= WH; k++)
	{
		resultWH = mul(resultWH, k);
	}

	num = div(resultWH, mul(resultW, resultH));
	
	printf("%"PRIu32"\n", num);

	return 0;
}

WolframAlphaで(W, H) = (123, 456), (12345, 67890), (123456, 789012)について検算しました。

なるほど。modを使えば桁数が減らせますね。　ありがとうございました。