每日算法 — 使用java实现高精度计算：大整数四则运算与阶乘求解

算法背景

高精度计算（Arbitrary-Precision Arithmetic）是处理超出原生数据类型范围数值的基础技术。Java的BigInteger和BigDecimal虽提供了现成支持，但理解其底层实现原理对于算法竞赛、密码学开发和数值分析至关重要。

本文将从零实现大整数的核心运算，揭示高精度计算的算法本质，并应用于超大数阶乘、斐波那契数列等经典问题。

核心思想

将大整数按固定基数（通常为 $10^4$ 或 $10^9$）分解为数组存储，模拟人工竖式运算：

• 加法: 逐位相加，处理进位
• 减法: 逐位相减，处理借位
• 乘法: 双重循环，$O(n^2)$ 复杂度
• 除法: 试商法或牛顿迭代法
• 进制转换: 短除法或快速幂分解

Java实现：大整数类

import java.util.*;

public class BigInt {
    // 每元素存储4位十进制数，平衡效率与实现复杂度
    private static final int BASE = 10000;
    private static final int WIDTH = 4;

    // 小端存储: digits[0]是最低位
    private final int[] digits;
    private final boolean negative;

    public BigInt(String s) {
        if (s.startsWith("-")) {
            this.negative = true;
            s = s.substring(1);
        } else {
            this.negative = false;
        }

        // 从字符串构建数字数组
        int len = s.length();
        int n = (len + WIDTH - 1) / WIDTH;
        digits = new int[n];

        for (int i = 0; i < n; i++) {
            int end = len - i * WIDTH;
            int start = Math.max(0, end - WIDTH);
            digits[i] = Integer.parseInt(s.substring(start, end));
        }

        trim();
    }

    private BigInt(int[] digits, boolean negative) {
        this.digits = digits;
        this.negative = negative;
        trim();
    }

    /** 去除前导零 */
    private void trim() {
        int n = digits.length;
        while (n > 1 && digits[n - 1] == 0) n--;
    }

    /** 判断是否为0 */
    public boolean isZero() {
        return digits.length == 1 && digits[0] == 0;
    }

    /** 取绝对值 */
    public BigInt abs() {
        return new BigInt(digits.clone(), false);
    }

    /** 比较绝对值大小: 返回 1, 0, -1 */
    private int compareAbs(BigInt other) {
        if (digits.length != other.digits.length) {
            return digits.length > other.digits.length ? 1 : -1;
        }
        for (int i = digits.length - 1; i >= 0; i--) {
            if (digits[i] != other.digits[i]) {
                return digits[i] > other.digits[i] ? 1 : -1;
            }
        }
        return 0;
    }

    /** 加法: 假设两数同号 */
    private BigInt addAbs(BigInt other) {
        int n = Math.max(digits.length, other.digits.length);
        int[] res = new int[n + 1];
        int carry = 0;

        for (int i = 0; i < n; i++) {
            int a = i < digits.length ? digits[i] : 0;
            int b = i < other.digits.length ? other.digits[i] : 0;
            int sum = a + b + carry;
            res[i] = sum % BASE;
            carry = sum / BASE;
        }
        if (carry > 0) res[n] = carry;

        return new BigInt(res, false);
    }

    /** 减法: 假设 |this| >= |other| */
    private BigInt subAbs(BigInt other) {
        int[] res = new int[digits.length];
        int borrow = 0;

        for (int i = 0; i < digits.length; i++) {
            int a = digits[i];
            int b = i < other.digits.length ? other.digits[i] : 0;
            int diff = a - b - borrow;
            if (diff < 0) {
                diff += BASE;
                borrow = 1;
            } else {
                borrow = 0;
            }
            res[i] = diff;
        }

        return new BigInt(res, false);
    }

    /** 公开加法 */
    public BigInt add(BigInt other) {
        if (negative == other.negative) {
            return new BigInt(addAbs(other).digits, negative);
        }
        // 异号相当于减法
        int cmp = compareAbs(other);
        if (cmp == 0) return new BigInt("0");
        if (cmp > 0) {
            return new BigInt(subAbs(other).digits, negative);
        } else {
            return new BigInt(other.subAbs(this).digits, other.negative);
        }
    }

    /** 公开减法 */
    public BigInt subtract(BigInt other) {
        return add(new BigInt(other.digits, !other.negative));
    }

    /** 乘法 */
    public BigInt multiply(BigInt other) {
        if (isZero() || other.isZero()) return new BigInt("0");

        int[] res = new int[digits.length + other.digits.length];

        for (int i = 0; i < digits.length; i++) {
            long carry = 0;
            for (int j = 0; j < other.digits.length || carry > 0; j++) {
                long cur = res[i + j] + (long)digits[i] * 
                           (j < other.digits.length ? other.digits[j] : 0) + carry;
                res[i + j] = (int)(cur % BASE);
                carry = cur / BASE;
            }
        }

        return new BigInt(res, negative != other.negative);
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        if (negative && !isZero()) sb.append('-');
        sb.append(digits[digits.length - 1]);
        for (int i = digits.length - 2; i >= 0; i--) {
            sb.append(String.format("%0" + WIDTH + "d", digits[i]));
        }
        return sb.toString();
    }

    public static void main(String[] args) {
        BigInt a = new BigInt("12345678901234567890");
        BigInt b = new BigInt("98765432109876543210");

        System.out.println("a = " + a);
        System.out.println("b = " + b);
        System.out.println("a + b = " + a.add(b));
        System.out.println("a - b = " + a.subtract(b));
        System.out.println("a * b = " + a.multiply(b));

        // 验证与Java BigInteger一致
        java.math.BigInteger ja = new java.math.BigInteger("12345678901234567890");
        java.math.BigInteger jb = new java.math.BigInteger("98765432109876543210");
        System.out.println("\nJava BigInteger verification:");
        System.out.println("a + b = " + ja.add(jb));
        System.out.println("a - b = " + ja.subtract(jb));
        System.out.println("a * b = " + ja.multiply(jb));
    }
}

应用：超大数阶乘计算

public class Factorial {

    /**
     * 计算n!的高精度结果
     * 使用递推: n! = (n-1)! * n
     * 时间复杂度: O(n^2 * log(n))
     */
    public static BigInt factorial(int n) {
        BigInt result = new BigInt("1");
        for (int i = 2; i <= n; i++) {
            result = result.multiply(new BigInt(String.valueOf(i)));
        }
        return result;
    }

    /**
     * 分治阶乘: 利用递归分解减少大数乘法次数
     * product(l, r) = l * (l+1) * ... * r
     */
    public static BigInt factorialDivideConquer(int n) {
        return product(1, n);
    }

    private static BigInt product(int l, int r) {
        if (l > r) return new BigInt("1");
        if (l == r) return new BigInt(String.valueOf(l));
        int mid = l + (r - l) / 2;
        return product(l, mid).multiply(product(mid + 1, r));
    }

    public static void main(String[] args) {
        // 计算100!
        BigInt fact100 = factorial(100);
        System.out.println("100! = " + fact100);
        System.out.println("Digits in 100!: " + fact100.toString().length());

        // 计算1000! (分治法)
        BigInt fact1000 = factorialDivideConquer(1000);
        String s = fact1000.toString();
        System.out.println("\n1000! digits: " + s.length());
        System.out.println("First 50 digits: " + s.substring(0, 50));
        System.out.println("Last 50 digits: " + s.substring(s.length() - 50));
    }
}

应用：高精度斐波那契数列

public class FibonacciBig {

    /**
     * 快速倍增法计算斐波那契数列
     * 利用恒等式:
     * F(2k) = F(k) * [2*F(k+1) - F(k)]
     * F(2k+1) = F(k+1)^2 + F(k)^2
     * 时间复杂度: O(log n) 次大数乘法
     */
    static class Pair {
        BigInt f, g; // F(k), F(k+1)
        Pair(BigInt f, BigInt g) { this.f = f; this.g = g; }
    }

    public static Pair fibDoubling(int n) {
        if (n == 0) return new Pair(new BigInt("0"), new BigInt("1"));

        Pair p = fibDoubling(n >> 1);
        BigInt a = p.f; // F(k)
        BigInt b = p.g; // F(k+1)

        // c = F(2k) = F(k) * [2*F(k+1) - F(k)]
        BigInt twoB = b.add(b);
        BigInt twoBMinusA = twoB.subtract(a);
        BigInt c = a.multiply(twoBMinusA);

        // d = F(2k+1) = F(k)^2 + F(k+1)^2
        BigInt d = a.multiply(a).add(b.multiply(b));

        if ((n & 1) == 0) {
            return new Pair(c, d);
        } else {
            // F(2k+1) = d, F(2k+2) = c + d
            return new Pair(d, c.add(d));
        }
    }

    public static void main(String[] args) {
        // 计算第1000个斐波那契数
        Pair p = fibDoubling(1000);
        String fib1000 = p.f.toString();
        System.out.println("F(1000) digits: " + fib1000.length());
        System.out.println("F(1000) = " + fib1000);

        // 对比Java BigInteger
        java.math.BigInteger a = java.math.BigInteger.ZERO;
        java.math.BigInteger b = java.math.BigInteger.ONE;
        for (int i = 2; i <= 1000; i++) {
            java.math.BigInteger c = a.add(b);
            a = b;
            b = c;
        }
        System.out.println("\nJava verification matches: " + fib1000.equals(a.toString()));
    }
}

应用：大数幂运算（快速幂）

public class BigIntPower {

    /**
     * 快速幂算法: 计算 base^exp
     * 时间复杂度: O(log exp) 次乘法
     */
    public static BigInt pow(BigInt base, int exp) {
        BigInt result = new BigInt("1");
        BigInt cur = base;

        while (exp > 0) {
            if ((exp & 1) == 1) {
                result = result.multiply(cur);
            }
            cur = cur.multiply(cur);
            exp >>= 1;
        }

        return result;
    }

    public static void main(String[] args) {
        // 计算 2^1000
        BigInt two = new BigInt("2");
        BigInt pow1000 = pow(two, 1000);
        System.out.println("2^1000 = " + pow1000);
        System.out.println("Digits: " + pow1000.toString().length());
    }
}

复杂度分析

其中 $n$ 为数字位数，$M(n)$ 为乘法复杂度。

工程实践建议

1. 生产环境: 优先使用Java标准库BigInteger，经过充分优化和测试
2. 算法竞赛: 理解底层实现有助于处理特殊进制或自定义运算
3. 密码学: 需使用蒙哥马利约减、Barrett约减等优化技术
4. GPU加速: 大整数运算可并行化，适合CUDA/OpenCL实现

高精度计算是连接理论数学与工程实现的桥梁，掌握其原理能够应对各类极端数值场景。