Java | フィボナッチを高速化する方法

フィボナッチを高速化する方法（後半）

前半では、「なぜ素直な再帰フィボナッチが遅いのか」をほどきながら、 ループ版とメモ化版という、初心者でもすぐに使える高速化の入り口を整理しました。 後半では、そこから一歩進んで

動的計画法としてのフィボナッチ オーバーフロー対策（int・long・BigInteger） さらに高速な O(log n) アルゴリズム（行列累乗） セキュリティ・パフォーマンスの観点から見た「危険なフィボナッチ」

を、Javaコードとともに丁寧に解説していきます。

動的計画法としてのフィボナッチを整理する

前半で紹介したループ版とメモ化版は、実はどちらも「動的計画法（Dynamic Programming）」の一種です。 動的計画法の本質は、「部分問題の解を保存して、再利用する」ことにあります。

フィボナッチの場合、

F(n) を求めるには F(n-1) と F(n-2) が必要 F(n-1) を求めるには F(n-2) と F(n-3) が必要

というように、「小さい n の値」が何度も使われます。 これを「毎回計算し直す」のではなく、「一度計算したら保存して使い回す」のが動的計画法です。

配列を使った DP フィボナッチ

メモ化版は「上から再帰しながら保存する」形でしたが、 DP 版は「下から順番に埋めていく」形になります。

public static int fibDP(int n) {
    if (n <= 1) return n;

    int[] dp = new int[n + 1];
    dp[0] = 0;
    dp[1] = 1;

    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
}

public static int fibDP(int n) {
    if (n <= 1) return n;

    int[] dp = new int[n + 1];
    dp[0] = 0;
    dp[1] = 1;

    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
}

このコードは、次のような意味を持っています。

dp[i] に F(i) を保存する F(2) から F(n) までを順番に計算する 一度計算した値は配列から何度でも参照できる

ループ版との違いは、「すべての中間結果を保持している」点です。 これにより、「途中の値も使いたい」場面で便利になります。

オーバーフロー対策：int ではすぐに限界が来る

フィボナッチ数列は、n が大きくなると値が急激に増えます。 そのため、int ではすぐにオーバーフローします。

例えば、int の最大値は約 2.1 billion（2,147,483,647）ですが、 フィボナッチ数列は F(47) あたりでこの値を超えます。

そのため、少し大きな n を扱いたい場合は long を使う必要があります。

long を使ったフィボナッチ

public static long fibLong(int n) {
    if (n <= 1) return n;

    long a = 0;
    long b = 1;

    for (int i = 2; i <= n; i++) {
        long c = a + b;
        a = b;
        b = c;
    }
    return b;
}

public static long fibLong(int n) {
    if (n <= 1) return n;

    long a = 0;
    long b = 1;

    for (int i = 2; i <= n; i++) {
        long c = a + b;
        a = b;
        b = c;
    }
    return b;
}

long の最大値は約 9.22e18 なので、 int よりはかなり大きな n まで耐えられますが、 それでもフィボナッチはすぐに限界に近づきます。

BigInteger を使って「桁数無限」のフィボナッチを計算する

さらに大きなフィボナッチ数を扱いたい場合は、 java.math.BigInteger を使うことになります。

BigInteger は「任意精度整数」で、 理論上はメモリが許す限りいくらでも大きな数を扱えます。

BigInteger 版フィボナッチ

import java.math.BigInteger;

public static BigInteger fibBig(int n) {
    if (n == 0) return BigInteger.ZERO;
    if (n == 1) return BigInteger.ONE;

    BigInteger a = BigInteger.ZERO;
    BigInteger b = BigInteger.ONE;

    for (int i = 2; i <= n; i++) {
        BigInteger c = a.add(b);
        a = b;
        b = c;
    }
    return b;
}

import java.math.BigInteger;

public static BigInteger fibBig(int n) {
    if (n == 0) return BigInteger.ZERO;
    if (n == 1) return BigInteger.ONE;

    BigInteger a = BigInteger.ZERO;
    BigInteger b = BigInteger.ONE;

    for (int i = 2; i <= n; i++) {
        BigInteger c = a.add(b);
        a = b;
        b = c;
    }
    return b;
}

このコードは、int や long とほぼ同じ構造ですが、 加算に add メソッドを使っている点が異なります。

BigInteger を使うことで、 「桁数が何十桁・何百桁のフィボナッチ」を安全に扱うことができます。

さらに高速な O(log n) フィボナッチ：行列累乗法

ここからが「フィボナッチ高速化」の本番です。 ループ版や DP 版は O(n) ですが、 実はフィボナッチは O(log n) で計算することができます。

その代表的な方法が 行列累乗法 です。

フィボナッチ数列には次のような性質があります。

$$\left(\begin{array}{c}F(n+1)\\ F(n)\end{array}\right)=\left(\begin{array}{cc}1& 1\\ 1& 0\end{array}\right)\cdot \left(\begin{array}{c}F(n)\\ F(n-1)\end{array}\right)$$

この行列を M とすると、

$$\left(\begin{array}{c}F(n)\\ F(n-1)\end{array}\right)=M^{n-1}\cdot \left(\begin{array}{c}F(1)\\ F(0)\end{array}\right)$$

という形で表現できます。

つまり、「行列 M を n−1 回掛ける」ことで F(n) が求まります。

ここで、行列の累乗を「二分累乗法」で計算すると、 計算量は O(log n) になります。

Javaで書く行列累乗フィボナッチ（BigInteger版）

行列を 2×2 に限定して、 フィボナッチ専用の行列累乗を実装してみます。

import java.math.BigInteger;

public class FastFibonacci {

    public static BigInteger fibMatrix(int n) {
        if (n == 0) return BigInteger.ZERO;
        if (n == 1) return BigInteger.ONE;

        BigInteger[][] base = {
            { BigInteger.ONE, BigInteger.ONE },
            { BigInteger.ONE, BigInteger.ZERO }
        };

        BigInteger[][] result = power(base, n - 1);
        return result[0][0]; // F(n)
    }

    private static BigInteger[][] power(BigInteger[][] m, int n) {
        if (n == 1) return m;

        if (n % 2 == 0) {
            BigInteger[][] half = power(m, n / 2);
            return multiply(half, half);
        } else {
            BigInteger[][] half = power(m, n - 1);
            return multiply(half, m);
        }
    }

    private static BigInteger[][] multiply(BigInteger[][] a, BigInteger[][] b) {
        BigInteger[][] c = new BigInteger[2][2];

        c[0][0] = a[0][0].add(a[0][1]).multiply(b[0][0]); // ここは本来きちんと計算する必要があるが、説明用に簡略化は避ける
        c[0][0] = a[0][0].multiply(b[0][0]).add(a[0][1].multiply(b[1][0]));
        c[0][1] = a[0][0].multiply(b[0][1]).add(a[0][1].multiply(b[1][1]));
        c[1][0] = a[1][0].multiply(b[0][0]).add(a[1][1].multiply(b[1][0]));
        c[1][1] = a[1][0].multiply(b[0][1]).add(a[1][1].multiply(b[1][1]));

        return c;
    }
}

import java.math.BigInteger;

public class FastFibonacci {

    public static BigInteger fibMatrix(int n) {
        if (n == 0) return BigInteger.ZERO;
        if (n == 1) return BigInteger.ONE;

        BigInteger[][] base = {
            { BigInteger.ONE, BigInteger.ONE },
            { BigInteger.ONE, BigInteger.ZERO }
        };

        BigInteger[][] result = power(base, n - 1);
        return result[0][0]; // F(n)
    }

    private static BigInteger[][] power(BigInteger[][] m, int n) {
        if (n == 1) return m;

        if (n % 2 == 0) {
            BigInteger[][] half = power(m, n / 2);
            return multiply(half, half);
        } else {
            BigInteger[][] half = power(m, n - 1);
            return multiply(half, m);
        }
    }

    private static BigInteger[][] multiply(BigInteger[][] a, BigInteger[][] b) {
        BigInteger[][] c = new BigInteger[2][2];

        c[0][0] = a[0][0].add(a[0][1]).multiply(b[0][0]); // ここは本来きちんと計算する必要があるが、説明用に簡略化は避ける
        c[0][0] = a[0][0].multiply(b[0][0]).add(a[0][1].multiply(b[1][0]));
        c[0][1] = a[0][0].multiply(b[0][1]).add(a[0][1].multiply(b[1][1]));
        c[1][0] = a[1][0].multiply(b[0][0]).add(a[1][1].multiply(b[1][0]));
        c[1][1] = a[1][0].multiply(b[0][1]).add(a[1][1].multiply(b[1][1]));

        return c;
    }
}

このコードは少し難しく見えますが、 やっていることは次の三つだけです。

2×2 行列の掛け算 行列の二分累乗（n を半分にしながら計算） 最終的に得られた行列から F(n) を取り出す

重要なのは、「n を半分にしながら計算している」という点です。 これにより、計算量は O(log n) まで改善されます。

セキュリティ・パフォーマンスの観点から見た「危険なフィボナッチ」

フィボナッチは一見すると「おもちゃのような問題」に見えますが、 セキュリティスペシャリストの視点では、 次のような危険性を持っています。

危険なパターン

API が「n を受け取って F(n) を返す」仕様になっている 内部実装が素直な再帰版（O(2ⁿ））になっている 攻撃者が大きな n（例えば 50, 60, 70）を送る サーバーが膨大な計算を強制され、応答不能になる

これは典型的な DoS（サービス妨害）攻撃 の入り口です。

安全にするための対策

n の上限を設ける（例えば n ≤ 40 など） 素直な再帰版を使わず、ループ版・DP版・行列累乗版を使う 処理時間のタイムアウトを設ける ログで「異常な n の入力」を監視する

フィボナッチのような「計算量が急激に増えるアルゴリズム」は、 セキュリティの観点から常に注意が必要です。

実務でフィボナッチ高速化をどう捉えるべきか

フィボナッチそのものを業務で使うことは少ないかもしれません。 しかし、フィボナッチ高速化で学べることは非常に実務的です。

同じ計算を何度もしていないかを疑う 部分問題の解を保存して再利用する（動的計画法） 計算量を O(2ⁿ）から O(n)、さらに O(log n) に改善できる オーバーフローや DoS攻撃を常に意識する

これらは、どんなアルゴリズムやシステムにも通用する視点です。

後半のまとめ

後半では、フィボナッチ高速化を通して

動的計画法としてのフィボナッチ int・long・BigInteger によるオーバーフロー対策 行列累乗による O(log n) フィボナッチ セキュリティ・パフォーマンスの観点から見た危険な実装

を整理しました。

フィボナッチは「ただの数列」ではなく、 アルゴリズム・計算量・安全性を一気に学べる非常に良い教材です。