閉じる

C#で巨大な整数を扱う：BigInteger型の基本とパフォーマンスを最適化する実践テクニック

広告

C#を用いたアプリケーション開発において、標準的な整数型であるint（32ビット）やlong（64ビット）の許容範囲を超える数値を扱わなければならない場面は少なくありません。

暗号化処理、ブロックチェーンのスマートコントラクト、あるいは天文学的な数値を扱う科学計算など、その用途は多岐にわたります。

本記事では、.NETのSystem.Numerics名前空間に用意されている「BigInteger型」の基礎から、パフォーマンスを最大限に引き出すための最適化手法までを詳しくご紹介します。

目次 [ close ]
  1. BigInteger型とは：巨大整数を扱うための基本
    1. BigIntegerの初期化と基本的な使い方
  2. BigIntegerのパフォーマンス特性と注意点
    1. メモリ消費量の見積もり
  3. パフォーマンスを最適化する実践テクニック
    1. Span<T>を利用した効率的な変換
    2. Generic Math（ジェネリック数学）の活用
    3. ビット演算の活用
  4. 実践的なユースケース：巨大な素数判定
  5. BigInteger使用時のアンチパターン
  6. まとめ

BigInteger型とは：巨大整数を扱うための基本

C#のBigIntegerは、メモリの許す限り理論上無限の大きさの整数を保持できる構造体です。

通常のlong型が最大で約922京（9.22 × 10^18）までの値しか扱えないのに対し、BigIntegerはそれ以上の桁数を持つ数値を正確に表現できます。

まず、基本的なデータ型との違いを以下の比較表で確認しましょう。

型名ビット幅最大値（概数）主な用途
int32bit約21億一般的なループカウンタなど
long64bit約922京大きなIDやファイルサイズなど
decimal128bit約7.9 × 10^28財務計算（小数精度が必要な場合）
BigInteger可変メモリの限界まで巨大な整数、暗号計算など

BigIntegerは構造体（struct）として定義されていますが、内部的には符号付きのバイト配列を管理しています。

そのため、非常に大きな数値を代入すると、それに応じたヒープメモリを消費することを理解しておく必要があります。

BigIntegerの初期化と基本的な使い方

BigIntegerを使用するには、ソースコードの先頭でusing System.Numerics;を宣言します。

初期化には、リテラルからの変換や、文字列からのパースなど、いくつかの方法が用意されています。

C#
using System;
using System.Numerics;

public class Program
{
    public static void Main()
    {
        // long型の範囲を超える数値を文字列からパース
        BigInteger bigNum1 = BigInteger.Parse("123456789012345678901234567890");

        // 階乗計算のような急激に大きくなる計算
        BigInteger result = 1;
        for (int i = 1; i <= 50; i++)
        {
            result *= i;
        }

        Console.WriteLine($"50の階乗: {result}");
    }
}
実行結果
50の階乗: 30414093201713378043612608166064768844377641568960512000000000000

このように、従来の数値型ではオーバーフローしてしまう計算も、BigIntegerなら正確に処理することが可能です。

BigIntegerのパフォーマンス特性と注意点

BigIntegerは非常に強力ですが、パフォーマンスの観点からは「不変（Immutable）」であるという性質に注意が必要です。

BigIntegerに対するすべての算術演算（加算、減算、乗算など）は、既存のインスタンスを変更するのではなく、計算結果を保持する新しいインスタンスを生成します。

この挙動はstring型と似ており、ループ内で頻繁に計算を行うと、大量のオブジェクトがヒープに割り当てられ、ガベージコレクション（GC）の負荷を高める要因となります。

例えば、1万回の累積加算を行う場合でも、内部的には1万個の新しい配列が作成される可能性があるのです。

そのため、速度が重要視されるアプリケーションでは、安易に演算を繰り返すのではなく、アルゴリズムの改善を検討すべきです。

メモリ消費量の見積もり

BigIntegerが消費するメモリは、保持する値の大きさに比例します。

内部的には符号を管理するためのフィールドと、数値を表現するためのuint[]配列で構成されています。

数百万桁におよぶような数値を扱う場合、1つのインスタンスだけで数メガバイトのメモリを消費することもあります。

メモリ制約の厳しい環境や、大量のインスタンスを同時に保持する設計では、このメモリ消費がボトルネックになりかねません。

パフォーマンスを最適化する実践テクニック

大規模な計算を行う際に、BigIntegerのオーバーヘッドを最小限に抑えるためのテクニックをいくつか紹介します。

Span<T>を利用した効率的な変換

.NETの比較的新しいバージョンでは、BigIntegerとバイト配列の相互変換において、Span<byte>やReadOnlySpan<byte>を利用できるようになりました。

従来のToByteArray()メソッドは、呼び出すたびに新しい配列を割り当ててしまいます。

対して、TryWriteBytesメソッドを使用すれば、スタック上に確保したバッファや既存のメモリ領域を再利用できるため、アロケーションを劇的に削減できます。

C#
// 推奨される効率的な変換方法
Span<byte> buffer = stackalloc byte[64];
if (bigNum.TryWriteBytes(buffer, out int bytesWritten))
{
    // bufferを使用した処理
}

このように、スタックメモリ（stackalloc）を活用する手法は、高頻度で実行されるロジックにおいて非常に有効です。

Generic Math（ジェネリック数学）の活用

C# 11以降で導入された「Generic Math」により、数値型を抽象化して扱うことが可能になりました。

INumber<TSelf>などのインターフェースを活用することで、特定の型に依存しない柔軟な計算ロジックを記述できます。

これにより、BigIntegerが必要な場合と、longで十分な場合を共通のコードで扱いながら、最適な型を選択する設計が容易になります。

C#
public T Sum<T>(IEnumerable<T> numbers) where T : INumber<T>
{
    T total = T.Zero;
    foreach (var n in numbers)
    {
        total += n;
    }
    return total;
}

この手法を用いれば、パフォーマンス特性の異なる複数の数値型を、型安全かつ効率的に切り替えることができます。

ビット演算の活用

特定の計算においては、乗算や除算を行うよりも、ビットシフト演算（<<、>>）を行うほうが高速です。

2のべき乗による乗除算を行う場合は、積極的にビット演算を利用しましょう。

また、IsEvenプロパティ（偶数判定）やIsPowerOfTwoプロパティ（2のべき乗判定）など、BigIntegerに備わっている最適化されたプロパティを活用することも重要です。

実践的なユースケース：巨大な素数判定

BigIntegerの真価が発揮される例として、素数判定アルゴリズム（ミラー・ラビン素数判定法など）の実装が挙げられます。

標準の数値型では到底扱えない数百ビット、数千ビットの数値を扱う際、BigInteger.ModPowメソッドは非常に強力な味方となります。

ModPowは「(底 ^ 指数) % 法」という計算を、巨大な中間結果を生成せずに効率的に実行します。

C#
// (base ^ exponent) % modulus を高速に計算
BigInteger result = BigInteger.ModPow(value, exponent, modulus);

このメソッドは、内部的に「バイナリ法」などの最適化されたアルゴリズムを使用しているため、自前で計算式を書くよりも圧倒的に高速です。

暗号の実装などで「べき剰余」が必要な場合は、必ずこの専用メソッドを使用するようにしましょう。

BigInteger使用時のアンチパターン

初心者が陥りやすいミスとして、BigIntegerを浮動小数点数（doubleやdecimal）と安易に混在させることが挙げられます。

BigIntegerからdoubleへ変換すると、当然ながら精度が失われます。

一度精度を失った数値から元のBigIntegerに戻すことはできないため、計算過程で型変換が発生しないよう、一貫したデータ型で設計することが重要です。

また、巨大なBigIntegerに対してToString()を呼び出す処理も、非常にコストがかかります。

数万桁の数値を文字列化する場合、計算そのものよりも文字列変換のほうが時間を要するケースがあることを覚えておきましょう。

デバッグ目的以外で、頻繁に巨大な数値を文字列に出力するのは避けるべきです。

まとめ

C#のBigInteger型は、標準の数値型の限界を超えて巨大な整数を自在に操ることができる、非常に強力なツールです。

暗号計算や高度な数学的シミュレーションにおいて、その正確性は他に代えがたい価値を持っています。

一方で、不変型であることによるメモリ消費や、ヒープアロケーションといった特性を正しく理解しておく必要があります。

Span<T>の活用や、ModPowなどの専用メソッドの選択といった最適化手法を組み合わせることで、パフォーマンスと柔軟性を両立させることが可能です。

最新の.NETが提供するGeneric Mathなどの新機能も取り入れながら、効率的な数値処理の実装を目指しましょう。

本記事で解説したテクニックを活用し、C#での巨大整数処理をマスターしてください。

URLをコピーしました！