C++ - 多桁計算（その２）！

以前、多桁（データ型を超える整数）の加減乗除アルゴリズムを C++ に実装してみました。

• C++ - 多桁計算！

今回は、少し改良してみました。

0. 前提条件

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

また、当方の環境で扱える int 型、 long 型の範囲は以下のとおり。

• int : -2,147,483,648 〜 2,147,483,647
• long : -9,223,372,036,854,775,808 〜 9,223,372,036,854,775,807

1. 多桁計算について

今回も「筆算方式」での計算アルゴリズムである。
基本的な考え方は過去記事に記載のとおりだが、今回は、

• 配列のインデックスを下位から取るようにしている。
• 汎用性を考えて、関数呼び出し時の引数には配列のポインタの他に配列のサイズを渡すようにしている。

また、乗算・除算時の乗数・除数は1つ（1個の配列）にしている。

ちなみに、乗算・除算が何万桁以上になる場合は、今回のような筆算形式ではなく別の高速に処理できるアルゴリズムを使用するようですが、今回は実装しない。

2. C++ ソース作成

例として、以下のようにソースを作成した。
なお、符号や除算時の小数点以下は考慮していない。
また、テストなので計算に使用する数値は乱数により生成している。

File: calc_big_digits_2.cpp

/*********************************************
 * 多桁計算
 * ( 符号は考慮しない。)
 *********************************************/
#include <cstdlib>   // for rand()
#include <iostream>  // for cout
#include <math.h>    // for pow()
#include <stdio.h>   // for printf()

#define N_A    1000                     // 計算桁数 ( 被加減乗除数 )
#define N_B     996                     // 計算桁数 ( 加減乗除数 )
#define LIMIT     4                     // 配列１つあたり桁数
#define SIZE_A ((N_A - 1) / LIMIT + 1)  // 配列サイズ
#define SIZE_B ((N_B - 1) / LIMIT + 1)  // 配列サイズ

using namespace std;

/*
 * 計算クラス
 */
class Calc
{
    int A[SIZE_A];  // 被加減乗除数配列
    int B[SIZE_B];  // 加減数配列
    int C;          // 乗除数

    public:
        Calc();                                    // コンストラクタ
        void calcAdd();                            // 計算 ( 加算 )
        void calcSub();                            // 計算 ( 減算 )
        void calcMul();                            // 計算 ( 乗算 )
        void calcDiv();                            // 計算 ( 除算 )
        void ladd(int *, int, int *, int, int *);  // ロング + ロング
        void lsub(int *, int, int *, int, int *);  // ロング - ロング
        void lmul(int *, int, int, int *);         // ロング * ショート
        void ldiv(int *, int, int, int *);         // ロング / ショート
        void display(int *, int);                  // 結果出力
};

/*
 * コンストラクタ
 */
Calc::Calc()
{
    // 使用する被加減乗除数・加減乗除数を設定（テストなので乱数を使用）
    for (int i = 0; i < SIZE_A; i++) A[i] = rand() % (int)pow(10, LIMIT);
    for (int i = 0; i < SIZE_B; i++) B[i] = rand() % (int)pow(10, LIMIT);
    C = rand() % (int)pow(10, LIMIT);
    printf("A =\n"); display(A, SIZE_A);
    printf("B =\n"); display(B, SIZE_B);
    printf("C =\n%d\n\n", C);
}

/*
 * 計算 ( 加算 )
 */
void Calc::calcAdd()
{
    // 各種宣言
    int a[SIZE_A];                         // 被加数配列
    int b[SIZE_B];                         // 加数配列
    int size_z = max(SIZE_A, SIZE_B) + 1;  // 結果格納配列サイズ
    int z[size_z];                         // 計算結果配列

    // 初期設定
    for (int i = 0; i < SIZE_A; i++) a[i] = A[i];  // 被加数配列
    for (int i = 0; i < SIZE_B; i++) b[i] = B[i];  // 加数配列
    for (int i = 0; i < size_z; i++) z[i] = 0;     // 計算結果配列

    // ロング + ロング
    ladd(a, SIZE_A, b, SIZE_B, z);

    // 結果出力
    printf("A + B =\n"); display(z, size_z);
}

/*
 * 計算 ( 減算 )
 */
void Calc::calcSub()
{
    // 各種宣言
    int a[SIZE_A];                     // 被減数配列
    int b[SIZE_B];                     // 減数配列
    int size_z = max(SIZE_A, SIZE_B);  // 結果格納配列サイズ
    int z[size_z];                     // 計算結果配列

    // 初期設定
    for (int i = 0; i < SIZE_A; i++) a[i] = A[i];  // 被減数配列
    for (int i = 0; i < SIZE_B; i++) b[i] = B[i];  // 減数配列
    for (int i = 0; i < size_z; i++) z[i] = 0;     // 計算結果配列

    // ロング - ロング
    lsub(a, SIZE_A, b, SIZE_B, z);

    // 結果出力
    printf("A - B =\n"); display(z, size_z);
}

/*
 * 計算 ( 乗算 )
 */
void Calc::calcMul()
{
    // 各種宣言
    int a[SIZE_A];            // 被乗数配列
    int c;                    // 乗数
    int size_z = SIZE_A + 1;  // 結果格納配列サイズ
    int z[size_z];            // 計算結果配列

    // 初期設定
    for (int i = 0; i < SIZE_A; i++) a[i] = A[i];  // 被乗数配列
    c = C;                                         // 乗数
    for (int i = 0; i < size_z; i++) z[i] = 0;     // 計算結果配列

    // ロング * ショート
    lmul(a, SIZE_A, c, z);

    // 結果出力
    printf("A * C =\n"); display(z, size_z);
}

/*
 * 計算 ( 除算 )
 */
void Calc::calcDiv()
{
    // 各種宣言
    int a[SIZE_A];        // 被除数配列
    int c;                // 除数配列
    int size_z = SIZE_A;  // 結果格納配列サイズ
    int z[size_z];        // 計算結果配列

    // 配列初期設定
    for (int i = 0; i < SIZE_A; i++) a[i] = A[i];  // 被除数配列
    c = C;                                         // 除数
    for (int i = 0; i < size_z; i++) z[i] = 0;     // 計算結果配列

    // ロング / ショート
    ldiv(a, SIZE_A, c, z);

    // 結果出力
    printf("A / C =\n"); display(z, size_z);
}

/*
 * ロング + ロング
 */
void Calc::ladd(int *a, int size_a, int *b, int size_b, int *z)
{
    for (int i = 0; i < size_a; i++) z[i] = a[i];
    for (int i = 0; i < size_b; i++) {
        z[i] += b[i];
        if (z[i] >= (int)pow(10, LIMIT)) {
            z[i] -= (int)pow(10, LIMIT);
            z[i + 1] += 1;
        }
    }
}

/*
 * ロング - ロング
 */
void Calc::lsub(int *a, int size_a, int *b, int size_b, int *z)
{
    for (int i = 0; i < size_a; i++) z[i] = a[i];
    for (int i = 0; i < size_b; i++) {
        z[i] -= b[i];
        if (z[i] < 0) {
            z[i] += (int)pow(10, LIMIT);
            z[i + 1] -= 1;
        }
    }
}

/*
 * ロング * ショート
 */
void Calc::lmul(int *a, int size_a, int c, int *z)
{
    for (int i = 0; i < size_a; i++) {
        z[i] += a[i] * c;
        if (z[i] >= (int)pow(10, LIMIT)) {
            z[i + 1] += z[i] / pow(10, LIMIT);
            z[i] %= (int)pow(10, LIMIT);
        }
    }
}

/*
 * ロング / ショート
 */
void Calc::ldiv(int *a, int size_a, int c, int *z)
{
    for (int i = size_a - 1; i >= 0; i--) {
        z[i] += a[i] / c;
        if (i > 0) a[i - 1] += (a[i] % c) * (int)pow(10, LIMIT);
    }
}

/*
 * 結果出力
 */
void Calc::display(int *s, int size)
{
    // 最上位で繰り上がりが無かった場合の処置
    if (s[size - 1] == 0) size--;

    // 1行に配列10個分出力
    for (int i = size - 1; i >= 0; i--) {
        printf("%04d ", s[i]);
        if ((size - i) % 10 == 0 && i != 0)
            printf("\n");
    }
    printf("\n\n");
}

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

        // 計算 ( 加算 )
        objCalc.calcAdd();

        // 計算 ( 減算 )
        objCalc.calcSub();

        // 計算 ( 乗算 )
        objCalc.calcMul();

        // 計算 ( 除算 )
        objCalc.calcDiv();
    }
    catch (...) {
        cout << "例外発生！" << endl;
        return -1;
    }

    // 正常終了
    return 0;
}

• Gist - C++ source code to compute big-digit values.(v2)

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

$ g++ calc_bit_digits_2.cpp -o calc_big_digits_2

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

4. 実行

A =
3810 3311 5422 4340 5568 5746 7343 9299 7828 3622 
8611 6348 8804 9355 9507 0197 8464 8542 8082 7669 
9786 2954 8139 7505 5590 5644 6725 9772 5499 8490 
2183 9470 7743 3324 6996 9917 7917 7369 0688 5128 
 ---< 途中省略 >---
8042 5011 8456 1393 8167 3069 3058 4022 9802 3929 
3135 4067 5123 2862 1530 5782 6429 2567 5368 5211 
5736 9172 3426 0540 3926 7763 0059 8690 0027 2362 
1421 6649 0492 5386 8335 7793 6915 2777 0886 9383 

B =
3826 0569 3541 5340 1682 8390 2829 3144 0743 5795 
2292 7988 5367 0289 6949 7971 5238 2900 3177 6335 
5343 6429 8285 0964 0049 5629 0504 6127 2215 1692 
4339 2134 2535 5151 6159 8538 7647 0681 4500 6403 
 ---< 途中省略 >---
8899 7981 7199 0163 8660 5894 8933 4930 3881 7131 
0973 0071 7468 5550 9379 1899 3452 2036 2600 5624 
2062 7637 2924 3258 8282 3416 6708 3465 8522 8626 
9444 8736 9320 1305 4878 3730 5661 1801 7605 

C =
4232

A + B =
3810 7137 5991 7882 0908 7429 5734 2129 0972 4366 
4406 8641 6793 4722 9796 7147 6436 3781 0983 0847 
6121 8298 4569 5790 6554 5694 2355 0277 1627 0705 
3876 3809 9877 5860 2148 6077 6456 5016 1369 9629 
 ---< 途中省略 >---
1039 3911 6437 8592 8331 1729 8953 2956 4732 7811 
0266 5040 5195 0330 7081 5161 8328 6019 7404 7812 
1361 1235 1063 3464 7185 6045 3476 5398 3493 0885 
0048 6093 9229 4706 9641 2672 0645 8438 2688 6988 

A - B =
3809 9485 4853 0799 0228 4063 8953 6470 4684 2879 
2816 4056 0816 3988 9217 3248 0493 3304 5182 4492 
3450 7611 1709 9220 4626 5595 1096 9267 9372 6275 
0491 5131 5609 0789 1845 3757 9378 9722 0007 0627 
 ---< 途中省略 >---
5045 6112 0474 4194 8003 4408 7163 5089 4872 0047 
6004 3094 5051 5393 5979 6403 4529 9115 3332 2611 
0112 7109 5788 7616 0667 9480 6643 1981 6561 3839 
2794 7204 1755 6066 7030 2915 3184 7115 9085 1778 

A * C =
1612 5321 4446 7740 9236 6208 0179 9511 6680 9629 
1948 4438 8462 2487 4383 3707 7286 3263 3164 6269 
9349 5602 4772 7424 3525 9268 8254 4335 7431 5361 
0604 2464 0316 9783 0129 1269 2094 7862 5899 3786 
 ---< 途中省略 >---
8854 9041 3712 1747 2631 7407 2144 8614 5815 9581 
5379 8633 7353 9060 6941 8117 3041 3365 6091 5263 
6585 6485 8776 4423 7079 7018 2902 5455 2639 3522 
8856 

A / C =
9003 6180 3928 2468 2345 4032 9262 5944 6664 3721 
3165 4888 6590 1124 6472 1639 5238 3135 1802 3794 
8455 3295 8742 3217 2945 5682 1186 1466 3279 4164 
0321 2360 0527 7232 2771 7197 0505 0494 0190 2477 
 ---< 途中省略 >---
2482 2806 8185 5845 5026 7176 9986 7729 1593 5560 
7597 8420 3977 5194 1234 8257 6628 6785 2950 1917 
7072 1106 6696 7250 4552 8740 5623 5089 7984 9626 
9899 9643 3110 9137 1303 8264 8665 5900 4931

---

前回より若干すっきりとしたソースにしましたが、今後他の場面で利用できるかと考えています。

多桁同士の乗算もこの筆算方式を応用すれば簡単に実装できますが、多桁同士の除算は筆算方式では少々手間がかかります。
ですから、多桁同士の乗算・除算は筆算方式ではなく別のアルゴリズムを使用することが多いようです。

以上。