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++ ソース作成

File: compare_big_digits.cpp

/*********************************************
 * 多倍長整数の大小比較
 * ( 符号は考慮しない。１桁１配列 )
 *********************************************/
#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;
}

• Gist - C++ source code to compare big digits.

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

（-Wall は警告出力、-O2 最適化のオプション）

$ g++ -Wall -O2 -o compare_big_digits _compare_big_digits.cpp

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

4. 実行

以下は、1,000桁と1,001桁の整数の大小を比較したもの。

$ ./compare_big_digits
[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]

---

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

以上。