最新閲覧日:

階乗の多桁計算をしたいのですが、プログラムの仕方を教えてください。
具体的には、217!とかを計算したいです。普通にやると桁が溢れてしまいます。
できれば、CかPerlでお願いします。

A 回答 (3件)

UNIX の C なら、GNU の MP (または GMP)というライブラリがあります。


ソースは参考URLにあります。
Windows にも移植されているかもしれませんし、もしかするとコンパイル
すればそのまま動くかもしれません。

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

参考URL:http://www.vector.co.jp/soft/solaris/sources/se0 …
    • good
    • 0

そういうライブラリがあればいいんですが、


私も知りません。

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

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

手元の環境では、unsigned shortが0~65535、unsigned
intがその2乗の桁を持ってるんで、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;

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

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

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

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

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

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

さもなくば浮動小数点で十分なんでは?
    • good
    • 0

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



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

お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!

このQ&Aを見た人が検索しているワード


このカテゴリの人気Q&Aランキング

おすすめ情報

カテゴリ