-PR-
解決済み

多桁計算

  • 困ってます
  • 質問No.92562
  • 閲覧数372
  • ありがとう数0
  • 気になる数0
  • 回答数3
  • コメント数0

お礼率 47% (19/40)

階乗の多桁計算をしたいのですが、プログラムの仕方を教えてください。
具体的には、217!とかを計算したいです。普通にやると桁が溢れてしまいます。
できれば、CかPerlでお願いします。
通報する
  • 回答数3
  • 気になる
    質問をブックマークします。
    マイページでまとめて確認できます。

質問者が選んだベストアンサー

  • 回答No.2
レベル9

ベストアンサー率 71% (59/82)

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

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

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

手元の環境では、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!の厳密解が欲しいという状況が理解できないんですが…。
そんなものを眺めて何か分かるんでしょうか?整数論の最先端では
そういうことをやってるんでしょうか?暗号理論?

さもなくば浮動小数点で十分なんでは?
-PR-
-PR-

その他の回答 (全2件)

  • 回答No.1
レベル11

ベストアンサー率 46% (145/312)

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

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


  • 回答No.3
レベル11

ベストアンサー率 55% (155/280)

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

あと、Perl ではなく、Ruby なら、最初から多倍長精度演算が可能です。
このQ&Aで解決しましたか?
AIエージェント「あい」

こんにちは。AIエージェントの「あい」です。
あなたの悩みに、OKWAVE 3,500万件のQ&Aを分析して最適な回答をご提案します。

関連するQ&A
-PR-
-PR-
こんな書き方もあるよ!この情報は知ってる?あなたの知識を教えて!
このQ&Aにはまだコメントがありません。
あなたの思ったこと、知っていることをここにコメントしてみましょう。

その他の関連するQ&A、テーマをキーワードで探す

キーワードでQ&A、テーマを検索する
-PR-
-PR-
-PR-

特集


専門家があなたの悩みに回答!

-PR-

ピックアップ

-PR-
ページ先頭へ