Wikibooks

プログラミング/多倍長整数

< プログラミング

コンピュータで扱う標準的な整数型は、通常、32ビットや64ビットなど固定のビット幅で制限されています。しかし、大規模な科学計算や暗号処理、非常に大きな数を扱う金融アプリケーションなどでは、これらの制限を超える範囲の整数が必要になります。これを実現するために、多倍長整数（arbitrary-precision integer、big integer）が使われます。この章では、多倍長整数の基礎概念、実装方法、応用例について解説します。

多倍長整数とは

編集

多倍長整数とは、コンピュータのネイティブな整数型で表現できる範囲を超える数値を扱うために設計されたデータ構造です。通常の整数型（例えば、32ビットや64ビット）は、表現できる範囲が決まっていますが、多倍長整数は必要に応じて任意のビット数で表現できるため、理論上は無限に大きな整数を扱うことが可能です。

固定長整数との違い

編集

固定長整数は、定義されたビット幅の範囲内でしか数値を表現できません。例えば、64ビット符号付き整数の最大値は約 9.2 × 10^18 ですが、多倍長整数はこの制限がなく、任意の大きさの数値を保持できます。

  • 固定長整数の制限：32ビットや64ビットの整数型には限界があり、これを超えるとオーバーフローが発生します。
  • 多倍長整数の柔軟性：多倍長整数は、必要に応じてビット数を増やして数値を表現するため、非常に大きな数値を扱うことができます。

多倍長整数の基本構造

編集

多倍長整数の実装は、通常の整数型を利用してビット列を分割して表現します。基本的な考え方は、数値を複数の固定長の「チャンク（部分）」に分け、それらを連結して一つの大きな数値として扱うことです。

  • 基数：多倍長整数は、通常、大きな基数（例えば、2^32 や 2^64）を基にして数値を分割します。それぞれのチャンクをこの基数で表現し、数値全体を複数のチャンクとして管理します。
  • キャリーの処理：加算や乗算などの演算を行う際に、各チャンクでの演算結果が次のチャンクにキャリーとして持ち越されることがあるため、キャリー処理が重要です。

多倍長整数のデータ構造は、典型的には以下のようになります。 

typedef struct {
    uint32_t *digits; // 各チャンクを保持する配列
    size_t length;    // チャンクの数（数値全体の長さ）
} BigInt;

ここで、digits は固定長の整数型（例えば、32ビットの uint32_t）の配列で、これにより任意の大きさの整数を表現します。

多倍長整数の基本演算

編集

多倍長整数に対する基本的な算術演算には、加算、減算、乗算、除算が含まれます。それぞれの演算において、通常の整数型とは異なる特別な手続きが必要です。

加算と減算

編集

多倍長整数の加算は、最下位のチャンクから順に行い、キャリーが発生した場合は次のチャンクに持ち越す必要があります。減算も同様に、繰り下がりが発生した場合は次のチャンクに影響を与えます。 

void addBigInt(BigInt *a, BigInt *b, BigInt *result) {
    uint64_t carry = 0;
    for (size_t i = 0; i < a->length; i++) {
        uint64_t sum = (uint64_t)a->digits[i] + b->digits[i] + carry;
        result->digits[i] = (uint32_t)(sum & 0xFFFFFFFF); // 下位32ビットを取り出す
        carry = sum >> 32; // 上位ビットをキャリーとして保持
    }
}

乗算

編集

多倍長整数の乗算は、通常の整数の筆算方式に似た手法で実装されます。各チャンク同士の積を求め、それを累積していく必要があります。 

void multiplyBigInt(BigInt *a, BigInt *b, BigInt *result) {
    for (size_t i = 0; i < a->length; i++) {
        uint64_t carry = 0;
        for (size_t j = 0; j < b->length; j++) {
            uint64_t product = (uint64_t)a->digits[i] * b->digits[j] + result->digits[i + j] + carry;
            result->digits[i + j] = (uint32_t)(product & 0xFFFFFFFF);
            carry = product >> 32;
        }
        result->digits[i + b->length] = carry;
    }
}

除算

編集

多倍長整数の除算は、基本的に「手計算」の割り算アルゴリズムを拡張して行います。複雑な実装になるため、しばしば既存のライブラリを利用することが推奨されます。

多倍長整数の応用例

編集

多倍長整数は、特に次のような分野で広く使用されます。

  • 暗号学：RSA暗号などの公開鍵暗号では、数百桁にも及ぶ大きな素数の演算が必要です。これに多倍長整数が用いられます。
  • 大規模計算：科学計算やシミュレーションでは、極めて大きな整数を扱うことが求められることがあります。多倍長整数はそのような場面で役立ちます。
  • 金融アプリケーション：正確な計算が求められる分野では、小数点以下を含む大きな数値の計算が必要であり、これに多倍長整数が応用されます。

多倍長整数ライブラリ

編集

C言語では、標準的な多倍長整数型は提供されていませんが、以下のようなライブラリを利用することで、簡単に多倍長整数を扱うことができます。

  • GNU MP (GMP)：最も有名な多倍長整数ライブラリで、加算、乗算、除算、モジュラー演算など、高度な数論的演算をサポートしています。
  • OpenSSL BIGNUM：OpenSSLライブラリには、暗号処理向けに最適化された多倍長整数型 BIGNUM が用意されています。

例として、GMPを使った多倍長整数の加算のコードを示します。

example-gmp.c
#include <gmp.h>
#include <stdio.h>

int main() {
    mpz_t a, b, result;

    // 変数の初期化
    mpz_init(a);
    mpz_init(b);
    mpz_init(result);

    // 値を設定
    mpz_set_str(a, "12345678901234567890", 10);
    mpz_set_str(b, "98765432109876543210", 10);

    // 加算
    mpz_add(result, a, b);

    // 結果を出力
    gmp_printf("結果: %Zd\n", result);

    // メモリの解放
    mpz_clear(a);
    mpz_clear(b);
    mpz_clear(result);

    return 0;
}
ビルドと実行
% cc -I/usr/local/include -L/usr/local/lib example-gmp.c -o example-gmp -lgmp
% ./example-gmp 
結果: 111111111011111111100

このコマンドは、cc（Cコンパイラ）を使ってCプログラムをコンパイルし、GMP（GNU Multiple Precision Arithmetic Library）ライブラリをリンクするためのものです。各オプションの意味を解説します。

  1. cc
    • 意味: C言語のコンパイラを指定しています。ccは一般的なCコンパイラの呼び出しコマンドで、システムによってはclangやgccのエイリアスになっています。
  2. -I/usr/local/include
    • 意味: コンパイル時に使用するヘッダファイルの追加ディレクトリを指定しています。
    • 詳細: -Iオプションはインクルードディレクトリを指定します。この場合、GMPのヘッダファイル（gmp.hなど）が/usr/local/includeにあることを示しています。コンパイラはこのディレクトリでヘッダファイルを探します。
  3. -L/usr/local/lib
    • 意味: リンク時に使用するライブラリの追加ディレクトリを指定しています。
    • 詳細: -Lオプションはライブラリディレクトリを指定します。この場合、GMPのライブラリ（libgmp.soやlibgmp.aなど）が/usr/local/libにあることを示しています。リンク時にこのディレクトリからライブラリを探します。
  4. example-gmp.c
    • 意味: コンパイルするソースコードファイルの名前です。
    • 詳細: example-gmp.cは、GMPライブラリを使用して書かれたCプログラムのソースファイルです。このファイルがコンパイル対象となります。
  5. -o example-gmp
    • 意味: 出力ファイルの名前を指定しています。
    • 詳細: -oオプションはコンパイルの結果として生成される実行ファイルの名前を指定します。この場合、example-gmpという実行ファイルが作成されます。
  6. -lgmp
    • 意味: GMPライブラリをリンクします。
    • 詳細: -lオプションはリンクするライブラリを指定します。-lgmpは、GMPライブラリ（libgmp.soまたはlibgmp.a）をリンクするように指示しています。このライブラリは多倍長整数（大きな数）や浮動小数点数などを効率的に扱うためのものです。

GMPにはC++バインディングもあります。

example-gmp.cc
#include <gmpxx.h>
#include <iostream>

int main() {
    // mpz_classを使用して変数を宣言
    mpz_class a, b, result;

    // 値を設定
    a = "12345678901234567890";
    b = "98765432109876543210";

    // 加算
    result = a + b;

    // 結果を出力
    std::cout << "結果: " << result << std::endl;

    // メモリの解放は自動的に行われるため、明示的なクリアは不要

    return 0;
}
ビルドと実行
% c++ -I/usr/local/include -L/usr/local/lib example-gmp.cc -o example-gmp2 -lgmp -lgmpxx
% ./example-gmp2
結果: 111111111011111111100

C++バインディングでは、演算子オーバーロードやストリーミングをサポートし、メモリ管理はRAIIに任せられるのでよりロジックの本質に集中してプログラミングができます。

まとめ

編集

多倍長整数は、非常に大きな数値を扱う際に不可欠なデータ型です。この章では、基本的な多倍長整数の構造、演算方法、そしてその応用例を説明しました。C言語では、GMPのようなライブラリを活用することで、多倍長整数を効率的に処理できます。多倍長整数の概念は、特に暗号学や高精度計算など、実世界の多くの分野で重要な役割を果たしています。

"https://ja.wikibooks.org/w/index.php?title=プログラミング/多倍長整数&oldid=262206" より作成