c++で多倍長演算を実装したらこうなった

c++で多倍長演算を実装したらこうなった


c/c++などは型による数値の限界があります。

普通にプログラミングするだけなら特に気にすることはないのですが、
暗号など数百桁もある数値を計算する場合通常の方法では実装できません。

PythonやRubyとかはプログラミング言語そのものに多倍長演算が組み込まれているようなので、
数値の限界について意識する必要はありません。

c/c++で多倍長演算をしたいのなら自分で実装する必要があります。
ライブラリーがあるそうですがそれは今はなしでおねがいします。


c言語での最大値


c言語では以下のように数値の最大値を調べることができます。


表示させているのはlong型の符号付きの数値と符号なしの数値です。

大きいことには大きいですがRSAなど300桁必要とするアルゴリズムには圧倒的に足りません。

大きい桁を扱う方法


数十桁、数百桁の数値を扱う方法を考える必要があります。
どうやら配列を使うことが定石のようです。

Pythonで簡単なサンプルを書きました。


これは多倍長の加算です。

配列を使う場合は要素をひとつずつ計算しています。
繰り上がりがある場合は次の要素の計算時に1を足します。
この実装が作法的に正しいかどうかはわかりませんが、加算はそんなに難しくはないようです。

いずれにしてもPythonでは初めから多倍長演算が可能なので、
Pythonで実装してもあまり意味がないかなと思います。

そこで今回はc++で多倍長演算を実装したいと思います。

実装


頑張って書いたソースコードです。
変数と関数は一先ずパブリックにしてます。
きちんと設計せずに行き当たりばったりで作成しましたが、粗方問題なく動きます。
これから洗練させていければいいですね。

まずはクラスの定義です。
メンバ変数に数値の長さと数字を格納する配列をもちます。
コンストラクタで初期化します。


次からはメンバ関数です。
まずは加算処理からいきましょう。
やっていることはシンプルで数値の大きい方の配列の長さでループし、
ひとけたずつ加算していきます。
桁上がりがあれば次の桁へ1加算します。
特に何でもないような処理で、加算はたいていこんな実装になるかと思います。


次は乗算処理です。
僕が実装した乗算処理は総当りで計算していくというものです。
掛け算の筆算の動きをプログラムにした感じです。
バイナリ法で加算したほうがいいのかもしれません。
様々な方法で試していきたいですね。


減算処理被減数でループして減算を行います。
繰り下がりがあれば次の桁から1引きます。
処理自体は加算に似ています。


次はいよいよ除算です。
これは正直良い方法が思いつきませんでした。
ですので乗算と同じように除算の筆算の動きをプログラムで再現するかたちになりました。
商と剰余を求めることができるようになっています。
動かしてみたところ 300桁の数 / 2 とかだと一瞬ですが終了まで間がありました。
作りながらもわかっていたことですがこれが最適なアルゴリズムではないようですね。


残りは諸々の用途に用いられる関数たちです。
そういえばoperator=を実装してませんでした。


加算、減算、乗算は割とスムーズに実装できたと思ってはいます。

先述の通り除算に関してはあまり釈然しません。
簡単でいい感じの方法ないかなと考えたのですが、思い浮かばなかったのでこのような実装になりました。

大きな整数を計算するための効率のいいアルゴリズムがいろいろとあるみたいなので、それも試してみたいと思います。

ちなみに符号なしです。
減算で結果が負の場合0にしています。
この辺りも順次改良していきたいと思います。

以下使用例です。

まとめ


今回は簡単な多倍長演算のプログラムを作りました。

作成にあたり書籍やネットで情報を収集したのですが、
計算のパフォーマンスをソフトウェアで向上させようとするのであればどうしても数学的に思考を凝らす必要があるようです。

例えばべき乗剰余計算を高速化させる手段としてバイナリー法や中国剰余定理を用いた計算方法があります。
RSAでは指数がかなり大きな数になり単純な方法では時間がかかりますから上記のような方法を使う必要があります。
pythonならpow()に渡せば一瞬ですが、自分で実装するとなるといろいろ考えることが多いですね。

コメントする