Project Euler 問題25（1000桁のフィボナッチ数）を解いてみる

Project Euler で紹介されている問題25を解いてみました。1000桁の数を扱うため、大きな整数を使える言語を利用します。また、C と Python の実行時間の差も測定してみました。

Project Euler 問題25（1000桁のフィボナッチ数）

解答例

1000桁の数を扱うため、整数の長さに制約がない Python で実装してみます。フィボナッチ数列の定義に従い、素直に実装します。プログラムは以下です。注意としては、4桁になる最小の数は 1000 です。これは 10³ となり、指数の数がひとつ小さくなります。

"""Project Euler Problem025"""

f1 = 1
f2 = 1
f3 = f1 + f2
term = 3
while f3 < 10 ** 999:
    f1 = f2
    f2 = f3
    f3 = f1 + f2
    term = term + 1

print("Problem025: " + str(term))

1000桁の数であれば、Python 版でも待ち時間なく動作します。

GMP ライブラリを使って、C言語でも記述しました。Python 版と同じロジックを C として記述しました。それぞれの演算は、GMP ライブラリの関数呼び出しになるため、プログラムが読みにくいかもしれません。関数呼び出しが実行する機能を演算子に書き直したプログラムをコメントに記しました。

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

int main(void)
{
	mpz_t f1, f2, f3, limit;
	int term;

	mpz_init_set_si(f1, 1);             /* f1 = 1 */
	mpz_init_set_si(f2, 1);             /* f2 = 1 */
	mpz_init(f3);
	mpz_add(f3, f1, f2);                /* f3 = f1 + f2 */
	term = 3;
	mpz_init(limit);
	mpz_ui_pow_ui(limit, 10, 999);      /* limit = 10**999 */

	while (mpz_cmp(f3, limit) < 0) {    /* f3 < limit */
		mpz_set(f1, f2);                /* f1 = f2 */
		mpz_set(f2, f3);                /* f2 = f3 */
		mpz_add(f3, f1, f2);            /* f3 = f1 + f2) */
		++term;
	}

	printf("Problem025: %d\n", term);
	mpz_clear(f1);
	mpz_clear(f2);
	mpz_clear(f3);
	mpz_clear(limit);

	return 0;
}

GMP ライブラリを使っているため、コンパイル時（リンク時）には、「-lgmp」オプションが必要となります。また多くのオンライン実行環境では、コンパイルできません。

同じロジックを Python と C で表現しているだけですが、多倍長整数の場合、Python の方が、すっきりとロジックが書けていることが分かります。

性能測定

1000桁になるフィボナッチ数列の項を求める場合は、記述の簡潔さで Python の良さがでました。それでは、もっと大きな数を扱う場合を紹介します。

問題の1000桁を1万桁、10万桁と増やして、Python と C の実行時間を調べました。私の個人PC（プロセッサ：Intel Core i7-10700 @2.90GHz、メモリ 32GB）での測定結果です。測定環境は、cygwin コンソールの time コマンドで測定した user time です。

1万桁になる最初の項を求める場合、Python 版は計算時間が約550倍になっています。10万桁になると、その差が、約3350倍にまで広がっています。任意長の整数処理の時間差だと思われます。GMP ライブラリが優秀なのもあり、C の実行速度での優秀さが際立つ結果となりました。

一番右に記した結果をみると、桁を10倍にすると、項もほぼ10倍になっていることが分かります。フィボナッチ数列の $N$ 項目を求める計算量は、$O(N)$ です。一般的に計算量が $O(N)$ であれば、悪くないと考えられています。今回の問題は、求める $N$ 項目が指数的に増えていくため、計算時間が大きくなります。

最後に

記述がしやすい Python、性能が高い C とプログラミング言語がもっている特性を説明する記事となりました。プログラミング言語は、万能なものはなく、用途によって使い分けることが重要だと考えています。

次回は、この問題を別のアプローチで解く方法を紹介します。