mk-mode BLOG

このブログは自作の自宅サーバに構築した Debian GNU/Linux で運用しています。
PC・サーバ構築等の話題を中心に公開しております。(クローンサイト: GitHub Pages

ブログ開設日2009-01-05
サーバ連続稼働時間
Reading...
Page View 合計
Reading...
今日
Reading...
昨日
Reading...

C++ - べき剰余アルゴリズムの実装!

[ プログラミング, 数学 ] [ C言語 ]

こんにちは。

C++ に「べき剰余アルゴリズム」を実装したい事案があったので、記録しておきます。

0. 前提条件

  • Linux Mint 17.1(64bit) での作業を想定。
  • G++ 4.8.2, 4.9.1 での作業を想定。(特別なことはしていないので、他のバージョンでも問題ないはず)

1. べき剰余について

その名のとおり、べき乗の剰余のことである。

底を 、べき指数を 、剰余を とすると、べき剰余 は次のように表される。

2. べき剰余演算アルゴリズムについて

当然単純にべき乗後に剰余を計算してもよいが、計算機ではべき乗時にすぐにオーバーフローしてしまうことは目に見えている。(この場合の計算量は、 回の乗算と最後の剰余1回となる)
そこで、計算機での計算に都合のいいように計算しなければならない。

たとえば、 があるとき、

と変形できる。このアルゴリズムを使用すると、剰余計算が回に増えるが乗算それぞれの計算コストは低くなるため、計算機にとってはパフォーマンスが良くなる。

また、プログラミングで実装する際、

であることを再帰的に利用するとパフォーマンスがよくなるだろう。

3. C++ ソースコードの作成

まず、比較のために非再帰的な記述方法で作成。

ModularExponentiation1.cpp
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
/***************************************************************
 * Modular Exponentiation (iterative).
 **************************************************************/
#include <iostream>
#include <stdlib.h>

using namespace std;

class ModularExponentiation
{
    int ans;                    // Answer
public:
    int compME(int, int, int);  // Compute Modular Exponentiation
};

/*
 * Compute Modular Exponentiation
 */
int ModularExponentiation::compME(int b, int e, int m)
{
    ans = 1;

    while (e > 0) {
       if ((e & 1) == 1) ans = (ans * b) % m;
       e >>= 1;
       b = (b * b) % m;
    }

    return ans;
}

int main()
{
    try
    {
        // Declaration
        int b, e, m, me;  // me = b^e mod m
        b = 12345; e = 6789; m = 4567;

        // Instantiation
        ModularExponentiation objMain;

        // Modular Exponentiation Computation
        me = objMain.compME(b, e, m);

        // Display
        cout << b << "^" << e << " mod " << m << " = "
             << me << endl;
    }
    catch (...) {
        cout << "ERROR!" << endl;
        return EXIT_FAILURE;
    }

    return EXIT_SUCCESS;
}

次に、再帰的な記述方法で作成。(compME 関数の内容が異なるだけ)

ModularExponentiation2.cpp
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
/***************************************************************
 * Modular Exponentiation (recursive).
 **************************************************************/
#include <iostream>
#include <stdlib.h>

using namespace std;

class ModularExponentiation
{
    int ans;                    // Answer
public:
    int compME(int, int, int);  // Compute Modular Exponentiation
};

/*
 * Compute Modular Exponentiation
 */
int ModularExponentiation::compME(int b, int e, int m)
{
    if (e == 0) return 1;

    ans = compME(b, e / 2, m);
    ans = (ans * ans) % m;
    if (e % 2 == 1) ans = (ans * b) % m;

    return ans;
}

int main()
{
    try
    {
        int b, e, m, me;  // me = b^e mod m
        b = 12345; e = 6789; m = 4567;

        // Instantiation
        ModularExponentiation objMain;

        // Compute Modular Exponentiation
        me = objMain.compME(b, e, m);

        // Display
        cout << b << "^" << e << " mod " << m << " = "
             << me << endl;
    }
    catch (...) {
        cout << "ERROR!" << endl;
        return EXIT_FAILURE;
    }

    return EXIT_SUCCESS;
}

4. C++ ソースコードのコンパイル

作成した C++ ソースコードを以下のようにコンパイル。
-Wall 警告も出力するオプション、-O2 最適化のオプション)

1
2
$ g++ -Wall -O2 -o ModularExponentiation1 ModularExponentiation1.cpp
$ g++ -Wall -O2 -o ModularExponentiation2 ModularExponentiation2.cpp

5. 動作確認

1
2
3
4
5
$ ./ModularExponentiation1
12345^6789 mod 4567 = 62

$ ./ModularExponentiation2
12345^6789 mod 4567 = 62

6. 参考サイト


べき乗の計算だけで莫大な桁数になるものが、整数型の範囲内でコストをかけずに瞬時に計算できるのはよいですね。

プログラミングで実装する際のアルゴリズム考察は重要であると再認識した次第です。

以上。

Comments