【C#アルゴリズム】繰り返し二乗法

はじめに

paiza　で繰り返し二乗法にまつわる問題が出てきたのでこれについてまとめました。

繰り返し二乗法とは

繰り返し二乗法（または「二分累乗法」）は、効率的に累乗を計算するアルゴリズムです。特に、非常に大きな累乗を計算する場合や、モジュロ演算（mod）と組み合わせて使用する場面で有用です。

基本の考え方

通常の累乗計算は次のように行います：

$$a^b = a \cdot a \cdot a \cdots \text{（b回の掛け算）}$$

これには $O(b)$ の計算ステップが必要で、$b$ が大きい場合には計算量が非常に多くなります。

繰り返し二乗法では、指数 $b$ を2進法で分割することで、計算量を大幅に削減し、$O(\log b)$ の計算量で累乗を求めることができます。

繰り返し二乗法の原理

累乗の基本性質

1. 加法的性質：
   $a^{x+y} = a^x \cdot a^y$

2. 乗法的性質：
   $a^{2x} = (a^x)^2$

これらの性質を使って、指数を分割しつつ累乗計算を効率化します。

指数の二進法分解

指数 $b$ を二進法で表すと次のようになります：
$b = b_k \cdot 2^k + b_{k-1} \cdot 2^{k-1} + \cdots + b_1 \cdot 2^1 + b_0 \cdot 2^0$
ここで $b_i \in \{0, 1\}$ は二進数の各ビットを表します。

これを用いると、次のように指数 $b$ の累乗を展開できます：
$a^b = a^{b_k \cdot 2^k} \cdot a^{b_{k-1} \cdot 2^{k-1}} \cdots a^{b_1 \cdot 2^1} \cdot a^{b_0 \cdot 2^0}$

この展開では、ビット $b_i$ が $1$ の項だけ計算すれば良いため、計算量が削減されます。

アルゴリズムの手順

1. 初期化
   初期値として、結果 $\text{ans} = 1$ 、底 $\text{base} = a$ 、指数 $b$ を用意します。

2. 繰り返し処理
   指数 $b$ を二進法で右から順に処理します：

   • $b$ の最下位ビットが $1$ の場合、現在の底 $\text{base}$ を結果に掛けます：
     $\text{ans} = \text{ans} \cdot \text{base}$
   • 現在の底を二乗します：
     $\text{base} = \text{base}^2$
   • 指数を右にシフトして次のビットを処理します（または整数除算 $b \div 2$ を行います）。

3. 終了条件
   $b = 0$ になるまで繰り返します。

例： $a = 3, b = 13$ の場合

1. 指数を二進法で分解
   $b = 1101_2$ なので：
   $3^{13} = 3^{2^3} \cdot 3^{2^2} \cdot 3^{2^0}$

2. 計算手順

   • 初期値：$\text{ans} = 1, \text{base} = 3, b = 13$
   • $b = 1101_2$ の各ビットを処理：
     • ビット 1（最下位）：$\text{ans} = 1 \cdot 3 = 3$、$\text{base} = 3^2 = 9$、$b = 6$
     • ビット 0：スキップ、$\text{base} = 9^2 = 81$、$b = 3$
     • ビット 1：$\text{ans} = 3 \cdot 81 = 243$、$\text{base} = 81^2 = 6561$、$b = 1$
     • ビット 1（最上位）：$\text{ans} = 243 \cdot 6561 = 1594323$、終了

3. 結果
   $3^{13} = 1594323%$

モジュロ演算との組み合わせ

繰り返し二乗法は、特に以下の形式の計算に使用されます：

$$a^b \bmod m$$

モジュロを掛け算の各ステップで適用することで、巨大な数の計算を防ぎます。

具体例

例1: $3^{13} \bmod 7$

1. 13を2進数に変換: $13 = 1101_2$
2. 累乗を計算（偶数部分は二乗、奇数部分は掛け算）：
   • $3^1 \bmod 7 = 3$
   • $3^2 \bmod 7 = (3 \cdot 3) \bmod 7 = 9 \bmod 7 = 2$
   • $3^4 \bmod 7 = (2 \cdot 2) \bmod 7 = 4$
   • $3^8 \bmod 7 = (4 \cdot 4) \bmod 7 = 16 \bmod 7 = 2$
3. 必要な部分だけ掛ける（$3^{8+4+1} = 3^8 \cdot 3^4 \cdot 3^1$）：
   
   $$3^{13} \bmod 7 = (2 \cdot 4 \cdot 3) \bmod 7 = 24 \bmod 7 = 3$$

C#コード

繰り返し二乗法を使用して $a^b \bmod m$ を計算するコードを示します。

using System;

class Program
{
    static void Main()
    {
        int a = 3;  // 底
        int b = 13; // 指数
        int m = 7;  // モジュロ

        int result = ModPow(a, b, m);
        Console.WriteLine($"({a}^{b}) % {m} = {result}");
    }

    private static int ModPow(int baseNum, int exponent, int mod)
    {
        long result = 1;             // 初期値
        long baseMod = baseNum % mod; // modを取った初期の底

        while (exponent > 0)
        {
            // 指数が奇数なら結果に底を掛ける
            if ((exponent & 1) == 1) 
            {
                result = (result * baseMod) % mod;
            }
            // 底を二乗し、指数を半分にする
            baseMod = (baseMod * baseMod) % mod;
            exponent >>= 1; // 指数を右シフト（2で割る）
        }
        return (int)result;
    }
}

アルゴリズムの特徴

1. 高速性: $O(\log b)$ の時間計算量。
2. 省メモリ: 繰り返し二乗法は通常、一定のメモリで動作。
3. 実用性: 暗号理論（RSA暗号など）、競技プログラミング、大規模な数値計算で頻繁に利用されます。

応用例

• 暗号理論：大きな素数を扱う場合の高速計算。
• 競技プログラミング：巨大な数の演算が必要な問題に対応。

おすすめ・参考書籍

問題解決力を鍛える！アルゴリズムとデータ構造 (ＫＳ情報科学専門書)
https://amzn.to/3YFmdH5

データ構造とアルゴリズム[第2版] (新・情報/通信システム工学)
https://amzn.to/3YtOnpz