mk-mode BLOG

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

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

C++ - 多倍長整数の大小比較!

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

こんばんは。

多桁(多倍長)整数同士の大小の比較についてです。
もちろん、プログラミング言語の整数型に収まるような大きさの整数ではなく、整数型で扱えないような大きな整数での話です。
多桁(多倍長)演算する場合、大抵は配列を使用します。今回も配列を使用した(よくある)方法を試してみました。

0. 前提条件

  • Linux Mint 14 Nadia (64bit) での作業を想定。
  • g++ (Ubuntu/Linaro 4.7.2-2ubuntu1) 4.7.2

1. 考え方

  • 整数の1桁を1個の配列をみなして考える。
  • 今回は、符号は考慮しない。
  • 通常、2つの整数のうち桁数が大きい方が大きな整数ではあるが、配列を使用しているため最上位の桁にゼロが格納されることもある。よって、それも考慮する。
    つまり、9桁の 234567890 と10桁の 0123456789 の場合は、234567890 > 0123456789 と判定できるようにするということ。

2. C++ ソース作成

例として、以下のようにソースを作成した。

CompareBigDigits.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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
/*********************************************
 * 多倍長整数の大小比較
 * ( 符号は考慮しない。1桁1配列 )
 *********************************************/
#include <cstdlib>   // for rand()
#include <iostream>  // for cout
#include <stdio.h>   // for printf()
#include <time.h>    // for time()

#define D_L 1000  // 多倍長整数桁数 ( 左辺 )
#define D_R 1001  // 多倍長整数桁数 ( 右辺 )

using namespace std;

/*
 * 計算クラス
 */
class Calc
{
    int L[D_L];  // 多倍長整数(左辺)配列
    int R[D_R];  // 多倍長整数(右辺)配列

    public:
        Calc();                                // コンストラクタ
        void procMain();                       // 主処理

    private:
        int  compare(int *, int, int *, int);  // 大小比較
        void display(int *, int *, int);       // 結果出力
};

/*
 * コンストラクタ
 */
Calc::Calc()
{
    // 使用する被加減乗除数・加減乗除数を設定(テストなので乱数を使用)
    srand((unsigned int)time(NULL));  // 乱数の種を初期化
    for (int i = 0; i < D_L; i++) L[i] = rand() % 10;
    for (int i = 0; i < D_R; i++) R[i] = rand() % 10;
}

/*
 * 主処理
 */
void Calc::procMain()
{
    // 各種宣言
    int l[D_L];  // 多倍長整数 ( 左辺 )
    int r[D_R];  // 多倍長整数 ( 右辺 )
    int s;       // 不等号

    // 初期設定
    // ( コンストラクタで設定した値をセット )
    for (int i = 0; i < D_L; i++) l[i] = L[i];
    for (int i = 0; i < D_R; i++) r[i] = R[i];

    // 大小比較
    s = compare(l, D_L, r, D_R);

    // 結果出力
    display(l, r, s);
}

/*
 * 大小比較
 *
 * - 引数   : a(多倍長整数・左辺), b(多倍長整数・右辺)
 * - 返り値 : 1: l > r
 *            0: l = r
 *           -1: l < r
 */
int Calc::compare(int *l, int size_l, int *r, int size_r)
{
    int i;  // LOOPインデックス

    // 左辺の右辺より大きい部分
    if (size_l > size_r) {
        for (i = size_l - 1; i >= size_r; i--) {
            if (l[i] != 0) return 1;
        }
    }
    // 右辺の左辺より大きい部分
    if (size_l < size_r) {
        for (i = size_r - 1; i >= size_l; i--) {
            if (r[i] != 0) return -1;
        }
    }

    // 桁数が同じ場合か、桁数が異なる場合の桁がダブる部分
    for (i = min(size_l, size_r) - 1; i >= 0; i--) {
        if (l[i] > r[i]) return 1;
        if (l[i] < r[i]) return -1;
    }

    // 等しい場合
    return 0;
}

/*
 * 結果出力
 */
void Calc::display(int *l, int *r, int s)
{
    int i;  // LOOPインデックス

    // 左辺
    printf("[LEFT] =\n");
    for (i = D_L - 1; i >= 0; i--) {
        printf("%d", l[i]);
        if ((D_L - i) % 10 == 0) printf(" ");
        if ((D_L - i) % 50 == 0) printf("\n");
    }
    printf("\n");

    // 右辺
    printf("[RIGHT] =\n");
    for (i = D_R - 1; i >= 0; i--) {
        printf("%d", r[i]);
        if ((D_R - i) % 10 == 0) printf(" ");
        if ((D_R - i) % 50 == 0) printf("\n");
    }
    printf("\n");

    // 大小比較結果
    printf("[LEFT] %s [RIGHT]\n", s == 0 ? "=" : (s > 0 ? ">" : "<"));
}

/*
 * メイン処理
 */
int main()
{
    try
    {
        // 計算クラスインスタンス化
        Calc objCalc;

        // 主処理
        objCalc.procMain();
    }
    catch (...) {
        cout << "例外発生!" << endl;
        return -1;
    }

    // 正常終了
    return 0;
}

3. C++ ソースコンパイル

以下のコマンドで C++ ソースをコンパイルする。 (-Wall は警告出力、-O2 最適化のオプション)

1
$ g++ -Wall -O2 -o CompareBigDigits CompareBigDigits.cpp

何も出力されなければ成功です。

4. 実行

実際に実行して検証してみる。
以下は、1,000桁と1,001桁の整数の大小を比較したもの。

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
$ ./CompareBigDigits
[LEFT] =
8583534943 3569297107 1993376235 5305946859 5216919009
7542714858 5024608711 5930591712 5583674333 4931579520
6534786825 2071702193 9344285775 6255894849 8935761894
7516728015 7126993284 6107386592 3158579300 1192179867
2872169205 7468725999 0772330968 0059075256 9771151390
2834224096 0878482726 8640076011 7749892809 9047446494
0656104514 5774707198 4050103920 9355046004 4887759759
2475496108 5119783252 3793698030 0785839637 5640543176
0880464683 0294608087 2518727416 8840366135 4648642973
6257011960 2655121167 9677477613 6924614048 3540406190
8090084482 1138037457 4302419539 9699567237 9097148702
7067397945 8903033010 5175742688 3775014093 5577999130
3021183219 1873102954 5536886753 5262575213 1557113527
9775983301 4359416213 8443267342 0487048076 6572020145
9296679310 4322807021 9233297390 3160615988 6040566500
6401370776 1353572506 4436496674 0393167444 1665905416
2602060064 3513370116 8356847923 3862180659 2012124407
9230790431 5178031145 7897750738 2853814992 2784597635
4892782224 2982792142 2809594105 4218836773 6897064094
2139519978 3426205019 4671306866 8142064151 4591129443

[RIGHT] =
0225925621 3347901359 2871925293 7508818117 5631565095
2993451254 0757849065 4405435070 4743028796 7398878442
3675024560 5050333286 7839843696 2663156495 2352703639
1589613541 0950456114 8865905136 1295417252 6930431033
5366065700 7487724363 9439620820 5910815504 0964146110
0050788013 7410311930 8562801409 2815067536 2597746017
2656929990 8752753136 5285961985 2550573712 3408942648
8939288663 8087786927 2543518484 3753161366 2008964977
0671313491 9938268505 4292499578 9916890229 5175856116
4078272156 5100366141 2010754979 7478512444 5264420374
0914678301 1984695899 6183213607 2432635791 0517680605
1295848636 2869772142 8373506257 6343500215 7397532811
3556733669 3262328338 3854550955 6682184434 1074479083
1910140536 7130673013 4748449478 0965761289 3554536042
6420885928 2517436991 4600837237 9462575767 4396144530
1485049007 1786781801 6824959429 0411304263 9300576792
9276551718 8781712831 3771267465 3369362292 8795778854
4059368093 9378516722 3180662442 7277115515 3866268449
2249802752 5015040790 9748881790 5142714005 9084305882
4996616908 6013879790 5457752228 1538059639 5304298712
5
[LEFT] > [RIGHT]

簡単な内容ですが、多倍長演算を行う際に必要になることもあるでしょう。

以上。

Comments