C++で複素数のn乗をO(log n)の計算量で求めるプログラム

複素数 x+yi と整数 n が与えられたとき、その複素数を n 乗した値を計算して出力するのがこの記事の目的です。

複素数とは？

複素数とは、a + bi という形で表すことができる数のことです。ここで a と b は実数、i は虚数単位（i² = −1 を満たす数）を指します。簡単に言えば、複素数は実数部と虚数部を組み合わせた数だと考えることができます。

複素数のべき乗の計算方法

複素数同士の積を求めるには、次の公式を使用します。

(a+bi)(c+di) = (ac − bd) + (ad + bc)i

たとえば、複素数 2+3i を 5 乗する場合は、次のように表されます。

(2+3i)⁵ = (2+3i)(2+3i)(2+3i)(2+3i)(2+3i)

上記の公式を繰り返し適用することで、最終的な答えが得られます。

入出力例

Input: x[0] = 10, x[1] = 11 /* x[0] が最初の実数、11 が 2 番目の実数 */
n = 4
Output: -47959 + i(9240)

Input: x[0] = 2, x[1] = 3
n = 5
Output: 122 + i(597)

問題を解くためのアプローチ

この問題は反復処理でも簡単に解けますが、その場合の計算量は O(n) になります。今回は O(log n) の時間で解く必要があるため、再帰的な分割統治法を利用します。手順は以下の通りです。

• まず、入力を実部と虚部を格納する配列として受け取ります。
• 関数 power() で xⁿ を計算します。
  • n が 1 なら x をそのまま返します。
  • x と n/2 を渡して power() を再帰的に呼び出し、その結果を変数 sq に保存します。
  • n を 2 で割った余りが 0 の場合：cmul(sq, sq) の結果を返します。
  • n を 2 で割った余りが 0 でない場合：cmul(x, cmul(sq, sq)) の結果を返します。
• 関数 cmul() では、x1 = a+bi、x2 = c+di とすると、x1 × x2 = (ac − bd) + (bc + da)i を計算します。
• 得られた結果を返して出力します。

アルゴリズム

開始
ステップ 1 → 2つの複素数の積を計算する関数を宣言
    long long* complex(long long* part1, long long* part2)
    long long* ans = new long long[2] を宣言
    ans[0] = (part1[0] * part2[0]) - (part1[1] * part2[1]) を設定
    ans[1] = (part1[1] * part2[0]) + part1[0] * part2[1] を設定
    ans を返す
ステップ 2 → 複素数の n 乗を返す関数を宣言
    long long* power(long long* x, long long n)
    long long* temp = new long long[2] を宣言
    IF n = 0
        temp[0] = 0 を設定
        temp[1] = 0 を設定
        temp を返す
    End
    IF n = 1
        x を返す
    End
    long long* part = power(x, n / 2) を宣言
    IF n % 2 = 0
        complex(part, part) を返す
    End
    complex(x, complex(part, part)) を返す
ステップ 3 → main() 内で
    int n を宣言
    long long* x = new long long[2] を宣言・設定
    x[0] = 10 を設定
    x[1] = -11 を設定
    n = 4 を設定
    long long* a = power(x, n) を呼び出す
終了

C++ 実装例

#include <bits/stdc++.h>
using namespace std;
// 2つの複素数の積を計算する
long long* complex(long long* part1, long long* part2) {
    long long* ans = new long long[2];
    ans[0] = (part1[0] * part2[0]) - (part1[1] * part2[1]);
    ans[1] = (part1[1] * part2[0]) + part1[0] * part2[1];
    return ans;
}
// 複素数の n 乗を返す関数
long long* power(long long* x, long long n) {
    long long* temp = new long long[2];
    if (n == 0) {
        temp[0] = 0;
        temp[1] = 0;
        return temp;
    }
    if (n == 1)
        return x;
    long long* part = power(x, n / 2);
    if (n % 2 == 0)
        return complex(part, part);
    return complex(x, complex(part, part));
}
int main() {
    int n;
    long long* x = new long long[2];
    x[0] = 10;
    x[1] = -11;
    n = 4;
    long long* a = power(x, n);
    cout << a[0] << " + i ( " << a[1] << " )" << endl;
    return 0;
}

出力

power of complex number in O(Log n) : -47959 + i ( 9240 )

計算量について

このアルゴリズムでは、再帰呼び出しごとに指数 n が半分になっていくため、再帰の深さは O(log n) となります。各段階で行われる複素数の掛け算は定数回であるため、全体の時間計算量は O(log n) です。これは、単純に n 回の掛け算を繰り返す O(n) の反復法と比較して、大きな n に対して大幅に高速に動作します。

なお、数学的には任意の複素数の 0 乗は 1（実部 1、虚部 0）となるため、厳密には n = 0 のケースで temp[0] = 1、temp[1] = 0 を返すように実装すると、より正確な動作になります。