多桁計算

質問

階乗の多桁計算をしたいのですが、プログラムの仕方を教えてください。
具体的には、２１７！とかを計算したいです。普通にやると桁が溢れてしまいます。
できれば、ＣかＰｅｒｌでお願いします。

回答No.2

Fooky · ベストアンサー

そういうライブラリがあればいいんですが、
私も知りません。

要は筆算の手順をプログラムに実装すればいいんじゃ
ないでしょうか。

たとえば、多桁×多桁の計算を筆算風にやってみます。

手元の環境では、unsigned shortが0～65535、unsigned
intがその２乗の桁を持ってるんで、unsigned shortの
配列s[KETA]、t[KETA]、r[KETA]を使って、（KETA：定数）
s[0]、t[0]、r[0]には千の位まで、s[1]等には千万の位まで
入ってる、という風に多桁の十進数を表現すると、

[初期値] unsigned int carry = 0, i = 0, j = 0;

[ステップ１]
unsigned int result
= (unsigned int)s[i] * (unsigned int)t[j] + carry;

[ステップ２]
r[i+j] += (unsigned short)(result % 10000);
carry = r[i+j] / 10000;

[ステップ３]
if( s[++i] > 0 )
　　ステップ１へ
else if( t[++j] > 0 )
　　if( carry > 0 )
　　　　r[i+j-1] += carry;
　　carry = i = 0;
　　ステップ１へ
else
　　ステップ４へ

[ステップ４]
rの要素を添え字の大きいものから順に横に並べて表示

多分どこか間違えてますが、こんな感じで多桁×多桁の
掛け算はできませんかね。217!に必要なのは多桁×少桁（？）
ですが、そっちはもう少しシンプルですね。

ところで、217!の厳密解が欲しいという状況が理解できないんですが…。
そんなものを眺めて何か分かるんでしょうか？整数論の最先端では
そういうことをやってるんでしょうか？暗号理論？

さもなくば浮動小数点で十分なんでは？

回答No.3

punchan_jp

UNIX の C なら、GNU の MP （または GMP）というライブラリがあります。
ソースは参考URLにあります。
Windows にも移植されているかもしれませんし、もしかするとコンパイル
すればそのまま動くかもしれません。

あと、Perl ではなく、Ruby なら、最初から多倍長精度演算が可能です。

参考URL：

http://www.vector.co.jp/soft/solaris/sources/se045593.html?y

回答No.1

KojiS

アルゴリズムは考えていますか？

ただ標準の数値を使うのではなく、パック形式でやるとか、自分で１０進構造を作ってやれば桁あふれはおこりませんよ。
ライブラリでそういう関数があるかもしれません。
無ければ自分でそういう関数を作ればいいのです。