Java 大數運算：計算 2 的 100 萬次方（百萬位數）完整實作

挑戰分析

2^1,000,000 約有 301,030 位十進位數字，遠超 long、BigInteger 預設效能範圍。需自行實現大整數乘法，採用陣列/列表儲存每一位，模擬手算進位。

核心演算法：以 10 為基底的陣列乘 2

• 用 ArrayList 低位在前儲存數字。
• 每輪迴圈遍歷列表，將每位乘 2 加上進位，取模 10 存回，進位帶入下一位。
• 迴圈執行 1,000,000 次（或先乘 2^3 再迴圈 999,997 次優化）。

完整可執行代碼

import java.util.ArrayList;

public class PowerOfTwoMillion {
    static ArrayList doubleIt(ArrayList num) {
        int carry = 0;
        for (int i = 0; i < num.size(); i++) {
            int val = num.get(i) * 2 + carry;
            num.set(i, val % 10);
            carry = val / 10;
        }
        if (carry > 0) num.add(carry);
        return num;
    }

    public static void main(String[] args) {
        ArrayList num = new ArrayList<>();
        num.add(1); // 2^0 = 1
        // 先算 2^3 = 8
        for (int i = 0; i < 3; i++) doubleIt(num);
        // 再乘 999,997 次得到 2^1,000,000
        for (int i = 0; i < 999_997; i++) doubleIt(num);

        // 高位在前輸出
        StringBuilder sb = new StringBuilder();
        for (int i = num.size() - 1; i >= 0; i--) sb.append(num.get(i));
        System.out.println(sb.toString());
        System.out.println("總位數: " + num.size());
    }
}

執行時間與記憶體

在現代筆電上約需 10-30 秒，記憶體佔用約 300 KB（30 萬位整數）。若需更快，可改用 BigInteger.shiftLeft(1_000_000)（內部採用 FFT 大整數乘法，毫秒級完成），但題目限制不得使用系統函數。

進階優化方向

• 以 10^9 為基底（int 陣列）減少迴圈次數 9 倍。
• 採用 Karatsuba 或 FFT 乘法將複雜度從 O(n²) 降至 O(n log n)。
• 多執行緒分段計算再合併。