掲示板利用宣言

 次のフォームをすべてチェックしてからご利用ください。

 私は

 題名と投稿者名は具体的に書きます。
 課題の丸投げはしません。
 ソースの添付は「HTML変換ツール」で字下げします。
 返信の引用は最小限にします。
 環境(OSとコンパイラ)や症状は具体的に詳しく書きます。
 返信の付いた投稿は削除しません。
 マルチポスト(多重投稿)はしません。

掲示板2

管理者用メニュー    ツリーに戻る    携帯用URL    ホームページ    ログ    タグ一覧

No.28269

多倍長整数クラスについて
投稿者---ななしXP(2006/09/28 22:04:28)


多倍長整数クラスが2つあるとします。
HugeIntegerClassAは内部で10進数を保持します。一桁ごとにSTL::vector<char>で管理します。
HugeIntegerClassBは内部でINT_MAX進数を保持します。INT_MAX数ごとにSTL::vector<int>で管理します。
HugeIntegerClassAとHugeIntegerClassBを比べるとどちらが高速でしょうか?
HugeIntegerClassAは単純に一桁づつ保持していくだけなので高速ですが、
メモリ管理で低速な気がします。
HugeIntegerClassBは逆にINTMAXづつ保持していき、内部計算が大変ですが
メモリ管理で一桁ごとでないので高速な気がします。
HugeIntegerClassAは未熟ですが出来ていますが、
HugeIntegerClassBは出来ていませんので、比較できません。
予測でかまいませんので、どちらが高速かお答えくださると助かります。
計算する対象は、100000の階乗です。


この投稿にコメントする

削除パスワード

発言に関する情報 題名 投稿番号 投稿者名 投稿日時
<子記事> Re:多倍長整数クラスについて 28272 yoh2 2006/09/29 00:37:59


No.28272

Re:多倍長整数クラスについて
投稿者---yoh2(2006/09/29 00:37:59)


>HugeIntegerClassAは単純に一桁づつ保持していくだけなので高速ですが、

HugeIntegerClassAが高速になる可能性があるのは、10進文字列との相互変換だけだと思います。
肝心の内部計算は、複雑でもトータルの演算回数が少なくなるHugeIntegerClassBに分があります。
(対象のアーキテクチャによって逆転もあり得るかもしれませんが)
A、B両方の方法で、123456789012の2乗あたりを手計算してみると分かると思います。

Bで面倒なのは一桁 (vectorの要素ひとつ) 同士の乗算でしょう。
(階乗の計算に不要な除算に関しては無視しています)
といっても、実はそれほど難しくもないのですが。それでも面倒に感じたら、
vectorの要素をunsigned intとして、その半分のビット数で表せる整数までを
格納するようにしたクラスHugeIntegerClassCを考えるという手もあります。
これは、内部計算方法はAと同様で、さらに計算回数も少なくなります。
ただし、インスタンスのメモリはBの2倍食います。Aよりは若干少ないと思いますが。

# BとCのどっちが高速かまでは考察していません。

実際に多倍長整数を扱えるソフトのソースを見て勉強するのもいいかも。
例えば以下のようなものがあります。

GMP (任意精度の数値計算ライブラリ)
clisp (Common Lisp)
python (スクリプト言語)


この投稿にコメントする

削除パスワード

No.28273

Re:多倍長整数クラスについて
投稿者---ななしXP(2006/09/29 11:29:39)


回答ありがとうございます。
Bのほうが高速ですか、
つまずいて作れなかったのですが、
これをきに作成してみようと思います。
Aは作れたのですが、遅いなぁとは思いました。
ありがとうございました。


この投稿にコメントする

削除パスワード

管理者用メニュー    ツリーに戻る    携帯用URL    ホームページ    ログ    タグ一覧