桁数の大きな計算ができずに困っています

Question

###前提・実現したいこと
c言語で円周率を出すためのプログラムを作成しています。

###発生している問題・エラーメッセージ

コマンドライン引数の値から円周率出す（＝値が大きいいほど円周率に近くなる）のですが200000ほどの数になると計算せずに停止してしまいます。

Segmentation fault: 11

###該当のソースコード

/*これは円周率を出すプログラムですF2*/

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

double woris(double i);

int main(int argc, char *argv[]) {
    double a = atof(argv[1]);
    printf("%.3f\n",woris(a)*2);
    return 0;
}

double woris(double i){
    double answer = 0.0;
    double dumper = i;
    while(i>(double)0){
        if(dumper == (double)0){
            break;
        }else if((int)i == 1){
            answer = (4*i*i)/(4*i*i-1);
            return answer;
            break;
        }else{
        dumper = dumper -1;
        answer = (4*i*i)/(4*i*i-1) * woris(dumper);
        return answer;
        }
        }
    return answer;
}

###試したこと
float型だったものをdouble型にするなどをして徐々に桁の大きいものを計算することができるようになりました。しかし、

###補足情報(言語/FW/ツール等のバージョンなど)
macでxcodeをつかって入れたgccです。

Answer 1

こんにちは。

再帰定義を使っているようですね。
再帰定義は再帰呼び出しする度にスタックを消費します。
最大スタック・サイズを増やすことは可能ですが、いくら増やしても無限にはふやせませんのでいつかスタックオーバーフローします。
深い再帰呼び出しをするケースでは、再帰定義ではなくループで処理するのが好ましいです。

Comments

[kaeruarc]

回答ありがとうございます。再帰ではなくforループを使うことで、無事に自分の手で問題を解決することのできるコードを書くことができました。

Answer 2

woris関数内でworis関数を呼び出す再帰関数になっていますが、引数が200000であれば呼出しも200000回になるため、スタックオーバフローが発生していると思われます。解決する方法は二つです。

1. 再帰呼び出しを止める。

woris関数内でworis関数を再帰的に呼び出さないように書き換えてください。

1. 末尾再帰にする。

末尾再帰になるようにコードを修正し、十分な最適化オプションを付ければ、スタックを消費しないループの形に組み替えてコンパイルしてくれます。大きな数であってもスタックオーバーフローは発生しません。

末尾再帰に組み替えた場合の例を載せておきます。同時に無駄そうな処理も無くしています。

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

double woris_tail(double i, double pre);
double woris(double i);

int main(int argc, char *argv[])
{
	double a = atof(argv[1]);
	printf("%.3f\n", woris(a) * 2);
	return 0;
}

double woris_tail(double i, double pre)
{
	if (i <= 0) {
		return 0.0;
	}
	if ((int)i == 1) {
		return (4 * i * i) / (4 * i * i - 1) * pre;
	}
	return woris_tail(i - 1, (4 * i * i) / (4 * i * i - 1) * pre);
}

double woris(double i) { return woris_tail(i, 1.0); }

コンパイラは賢いため、他のパターンでも末尾再帰とみなされる場合があります。ただ、確実に末尾再帰の最適化が反映されるようにしたい場合は、最後のreturn文がその関数の呼出しのみになるような形にしてください。

なお、末尾再帰最適化はC言語の必須要件ではありません。最適化を無効にしている場合、十分な最適化ができないコンパイラを使っている場合等は、末尾再帰にしてもスタックが消費させる形でコンパイルされますので、ご注意ください。GCCであれば-O2以上の最適化をすれば問題ありません。

Comments

[kaeruarc]

回答ありがとうございます。末尾再帰最適化といったことを知ることができて非常に参考になりました。

Answer 3

オリジナルは無駄が多くていろいろ酷い

double woris(double i) {
	double answer = 0.0;
	double dumper = i;
	// (double)0は0.0か単に0と書くべき
	while (i>(double)0) {
		// 下のif文にはelse節があるので必ずどれかに一致するが
		// どこに一致してもbreakかreturnするのでそもそもループになっていない
		// つまりiがゼロより大きいときに一回実行されるだけ

		// 最大で一回しか実行されない以上、下のdumperは必ずiと同じになる
		// i>0なんだからdumper>0に決まっているので下のif文は無意味
		if (dumper == (double)0) {
			break;
		} else if ((int)i == 1) {
			// わざわざanswerに代入する必要もなさそう
			answer = (4 * i*i) / (4 * i*i - 1);
			return answer;
			// 既にreturnして関数の外なので下のbreakは無意味
			break;
		} else {
			// わざわざdumperやanswerに代入する必要もなさそう
			// doubleなので1ではなく1.0
			dumper = dumper - 1;
			// dumper=iなのだから、woris(dumper)はworis(i - 1.0)でいい
			answer = (4 * i*i) / (4 * i*i - 1) * woris(dumper);
			return answer;
		}
	}
	// ここにくるときはwhileの中は実行されていないのだからanswerは必ず0.0
	// return 0.0でいい
	return answer;
	// ここまで読んでみると変数のanswerとdumperはなくてもいい
}

簡潔に書くと

double woris(double i) {
	if (i > 0.0) {
		if ((int)i == 1) {
			return (4 * i*i) / (4 * i*i - 1);
		} else {
			return (4 * i*i) / (4 * i*i - 1) * woris(i - 1.0);
		}
	}
	return 0.0;
}

上のコードにすればループに直すのは簡単
引数のiはintでも良さそう

double woris(int i) {
	double pi, d;
	if (i < 1) return 0.0; // エラー
	for (pi = 1.0; i >= 1; --i) {
		d = (double)i;
		pi *= (4.0 * d * d) / (4.0 * d * d - 1.0);
	}
	return pi;
}

つまり分数の掛け算を繰り返しているのならば
掛け算一回ごとにループさせればいいのです

解決したようなので返事はいりません^^