多倍長整数

アバター
GRAM
記事: 164
登録日時: 14年前
住所: 大阪

多倍長整数

投稿記事 by GRAM » 13年前

多倍長整数はJavaなんかではおなじみのようですが、残念なことにC++では標準で用意されていない。
ライブラリは世の中にたくさんあるんですけれど、簡単なアルゴリズムなら自分にも実装できるなと思い、作ってみた今日この頃。
► スポイラーを表示
こんな感じで使える

CODE:

#include "BigInteger.h"
#include 
using namespace std;
using namespace Numeric;

int main(){
	BigInteger i(1);
	for( int j = 1; j <= 1000; ++j )
	{
		i *= BigInteger(j);
	}
	cout << "1000! = " << i << endl;
}
実行結果:
► スポイラーを表示

実行してみてわかるのだが、掛け算自体は一瞬で終わってる。
問題は文字列に直すときに10で割っていくという操作。ここにもんっのっすごい時間がかかっているみたい。

たぶんもっと快適に行うアルゴリズムがあるだろう。
(日記を書いているときに思ったけど10じゃなくて100000000とかで割ればよくね?てかそうだよねw)

ホントはフーリエ変換とか使えばもっともっと高速にできるみたいですが、理解する気力もないのでパスっす。
取りあえず自分の欲求は十分満たせたもん
最後に編集したユーザー GRAM on 2012年8月20日(月) 18:20 [ 編集 1 回目 ]

コメントはまだありません。