c++で多倍長演算を実装したらこうなった
c/c++などは型による数値の限界があります。
普通にプログラミングするだけなら特に気にすることはないのですが、
暗号など数百桁もある数値を計算する場合通常の方法では実装できません。
PythonやRubyとかはプログラミング言語そのものに多倍長演算が組み込まれているようなので、
数値の限界について意識する必要はありません。
c/c++で多倍長演算をしたいのなら自分で実装する必要があります。
ライブラリーがあるそうですがそれは今はなしでおねがいします。
c言語での最大値
c言語では以下のように数値の最大値を調べることができます。
|
1 2 3 4 5 6 7 8 |
#include <limits.h> #include <stdio.h> int main() { printf("%ld\n",LONG_MAX); //9223372036854775807 printf("%lu\n",ULONG_MAX); // 18446744073709551615 return 0; } |
表示させているのはlong型の符号付きの数値と符号なしの数値です。
大きいことには大きいですがRSAなど300桁必要とするアルゴリズムには圧倒的に足りません。
大きい桁を扱う方法
数十桁、数百桁の数値を扱う方法を考える必要があります。
どうやら配列を使うことが定石のようです。
Pythonで簡単なサンプルを書きました。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
def add(num,val): num1 = num num2 = val ans = [] t = 0 if len(num) < len(val): num1 = val num2 = num t = 0 for i in range(len(num1)): n2 = 0 if len(num2) > i: n2 = num2[i] a = n2 + num1[i] + t t = 0 if a > 9: a -= 10 t= 1 ans.append(a) if t != 0: ans.append(t) return ans |
これは多倍長の加算です。
配列を使う場合は要素をひとつずつ計算しています。
繰り上がりがある場合は次の要素の計算時に1を足します。
この実装が作法的に正しいかどうかはわかりませんが、加算はそんなに難しくはないようです。
いずれにしてもPythonでは初めから多倍長演算が可能なので、
Pythonで実装してもあまり意味がないかなと思います。
そこで今回はc++で多倍長演算を実装したいと思います。
実装
頑張って書いたソースコードです。
変数と関数は一先ずパブリックにしてます。
きちんと設計せずに行き当たりばったりで作成しましたが、粗方問題なく動きます。
これから洗練させていければいいですね。
まずはクラスの定義です。
メンバ変数に数値の長さと数字を格納する配列をもちます。
コンストラクタで初期化します。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
#define BIG_MAX_NUM 700 #define REMAINDER 1 #define QUOTIENT 2 #include <stdio.h> #include <string.h> #include <stdint.h> class BigNumber { public: // 数値の長さ int len; // 実際の値 uint8_t num[BIG_MAX_NUM]; BigNumber() { this->len = 0; memset(num, 0, BIG_MAX_NUM); } } |
次からはメンバ関数です。
まずは加算処理からいきましょう。
やっていることはシンプルで数値の大きい方の配列の長さでループし、
ひとけたずつ加算していきます。
桁上がりがあれば次の桁へ1加算します。
特に何でもないような処理で、加算はたいていこんな実装になるかと思います。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 |
// 加算演算子をオーバロード BigNumber operator+(BigNumber bn) { if (len < bn.len) { BigNumber reBn = this->add(&bn, this); return reBn; } return this->add(this, &bn); } // 加算処理 BigNumber add(BigNumber *bn1, BigNumber *bn2) { BigNumber reBn; char t = 0; int i=0; for (i=0; i<bn1->len; i++) { char num2 = 0; if (bn2->len > i) { num2 = bn2->num[i]; } reBn.num[i] = bn1->num[i] + num2 + t; t = 0; if (reBn.num[i] > 9) { t = 1; reBn.num[i] -= 10; } reBn.len++; } if (t != 0 && i < BIG_MAX_NUM) { reBn.num[i] = t; reBn.len++; } return reBn; } |
次は乗算処理です。
僕が実装した乗算処理は総当りで計算していくというものです。
掛け算の筆算の動きをプログラムにした感じです。
バイナリ法で加算したほうがいいのかもしれません。
様々な方法で試していきたいですね。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
// 乗算演算子のオーバーロード BigNumber operator*(BigNumber bn) { return mul(this, &bn); } // 乗算処理 BigNumber mul(BigNumber *bn1, BigNumber *bn2) { BigNumber reBn; for (int i=0; i<bn2->len; i++) { for (int j=0; j<bn1->len; j++) { char res = bn1->num[j] * bn2->num[i]; if (res > 9) { char c = res / 10; res -= c * 10; reBn.num[j+i+1] += c; } reBn.num[i+j] += res; if (reBn.num[i+j] > 9) { char c = reBn.num[i+j] / 10; reBn.num[i+j] -= c * 10; reBn.num[i+j+1] += c; } } } reBn.len = BIG_MAX_NUM; reBn.lzStrip(); return reBn; } |
減算処理被減数でループして減算を行います。
繰り下がりがあれば次の桁から1引きます。
処理自体は加算に似ています。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 |
// 減算演算子のオーバーロード BigNumber operator-(BigNumber bn) { return this->sub(this, &bn); } // 減算処理 BigNumber sub(BigNumber *bn1, BigNumber *bn2) { BigNumber reBn; char t = 0; for (int i=0; i<bn1->len; i++) { char num = 0; if (bn2->len > i) num = bn2->num[i]; char ans = bn1->num[i] - t - num; t = 0; if (ans < 0) { ans = ans+10; t = 1; } reBn.num[i] = (uint8_t)ans; reBn.len++; } if (reBn.len > 1) { for (int i=reBn.len-1; i>0; i--) { if (reBn.num[i] == 0) { reBn.len--; continue; } break; } } return reBn; } |
次はいよいよ除算です。
これは正直良い方法が思いつきませんでした。
ですので乗算と同じように除算の筆算の動きをプログラムで再現するかたちになりました。
商と剰余を求めることができるようになっています。
動かしてみたところ 300桁の数 / 2 とかだと一瞬ですが終了まで間がありました。
作りながらもわかっていたことですがこれが最適なアルゴリズムではないようですね。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 |
// 除算処理 BigNumber div(BigNumber *bn1, BigNumber *bn2, int type) { BigNumber reBn; BigNumber temp; BigNumber odd; int index = bn1->len-1; int cnt = 1; char ans[BIG_MAX_NUM]; memset(ans, '\0', BIG_MAX_NUM); for (;;) { if (index < 0) { break; } char buf[BIG_MAX_NUM]; memset(buf, '\0', BIG_MAX_NUM); if (odd.len > 1 || (odd.len == 1 && odd.num[0] > 0)) { for (int i=temp.len-1; i>-1; i--) { snprintf(&buf[strlen(buf)], 4, "%d", odd.num[i]); } } for (int i=0; i<cnt; i++) { snprintf(&buf[strlen(buf)], 4, "%d", bn1->num[index-i]); } temp.set(buf); int res = temp.checkGt(bn2); if (res == 1 || res == 2) { int subCnt = 0; for (;;) { temp = sub(&temp, bn2); subCnt += 1; if (temp.checkGt(bn2) == 0) { index -= cnt; cnt = 1; break; } } odd = temp; snprintf(&ans[strlen(ans)], 4, "%d", subCnt); } else { snprintf(&ans[strlen(ans)], 4, "%d", 0); if (temp.len == 1 && temp.num[0] == 0) { index -= 1; cnt = 1; continue; } if (index - cnt < 0) { odd = temp; break; } cnt += 1; } } if (type == REMAINDER) { return odd; } reBn.set(ans); return reBn; } |
残りは諸々の用途に用いられる関数たちです。
そういえばoperator=を実装してませんでした。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 |
// 大きさ比べ // 第一引数が第二引数より大きいか調べる 0:小さい 1:大きい 2:同じ int checkGt(BigNumber *bn2) { if (len > bn2->len) { return 1; } if (bn2->len > len) { return 0; } if (len == bn2->len) { for (int i=len-1; i>-1; i--) { if (num[i] > bn2->num[i]) { return 1; } else if (num[i] < bn2->num[i]) { return 0; } } } return 2; } // 数値を文字列で受け取りそれを１文字ずつ配列に格納 void set(char *num) { len = 0; uint8_t temp[BIG_MAX_NUM]; for (int i=0; i<BIG_MAX_NUM; i++) { temp[i] = (*(uint8_t *)num++) - 48; len++; if (*(char *)num == '\0') { break; } } for (int i=len-1; i>-1; i--) { this->num[len-1-i] = temp[i]; } if (this->len == 1) { return; } for (int i=this->len-1; i>-1; i--) { if (this->num[i] == 0) { this->len -= 1; continue; } break; } } // 0以外の数値が現れるまで、左にある0を消す void lzStrip() { for (int i=len-1; i>-1; i--) { if (num[i] == 0) { len -= 1; continue; } break; } } // 数値を出力 void print() { for (int i=len-1; i>-1; i--) { printf("%d",num[i]); } printf("\n"); } |
加算、減算、乗算は割とスムーズに実装できたと思ってはいます。
先述の通り除算に関してはあまり釈然しません。
簡単でいい感じの方法ないかなと考えたのですが、思い浮かばなかったのでこのような実装になりました。
大きな整数を計算するための効率のいいアルゴリズムがいろいろとあるみたいなので、それも試してみたいと思います。
ちなみに符号なしです。
減算で結果が負の場合0にしています。
この辺りも順次改良していきたいと思います。
以下使用例です。
|
1 2 3 4 5 |
BigNumber bn1; BigNumber bn2; bn1.set("345097123484512412930571023236234623462") bn2.set("923405981346234098149852349861462345631") (bn1+bn2).print() |
まとめ
今回は簡単な多倍長演算のプログラムを作りました。
作成にあたり書籍やネットで情報を収集したのですが、
計算のパフォーマンスをソフトウェアで向上させようとするのであればどうしても数学的に思考を凝らす必要があるようです。
例えばべき乗剰余計算を高速化させる手段としてバイナリー法や中国剰余定理を用いた計算方法があります。
RSAでは指数がかなり大きな数になり単純な方法では時間がかかりますから上記のような方法を使う必要があります。
pythonならpow()に渡せば一瞬ですが、自分で実装するとなるといろいろ考えることが多いですね。