C#分治算法实现大数乘法（从零开始掌握高效大整数乘法技巧）

什么是分治算法？

分治法（Divide and Conquer） 是一种经典算法设计策略，其核心思想是将一个复杂问题分解为若干个规模更小、结构相同的子问题，递归求解后再合并结果。典型的例子包括归并排序、快速排序和本文要讲的大数乘法。

为什么普通乘法不够用？

在 C# 中，int 最大只能表示约 21 亿，long 也仅支持 19 位十进制数。而实际应用中（如密码学、高精度计算），我们经常需要处理成百上千位的数字。此时，必须将数字以字符串或数组形式存储，并手动实现乘法逻辑。

传统 vs 分治：效率对比

最朴素的大数乘法是模拟手算，时间复杂度为 O(n²)。而使用分治法实现大数相乘（如 Karatsuba 算法），可将复杂度降低到约 O(n^1.585)，显著提升性能。

Karatsuba 算法原理（简化版）

假设我们要计算两个 n 位大数 X 和 Y 的乘积。我们可以将它们拆分为高低两部分：

• X = A × 10^(m) + B
• Y = C × 10^(m) + D

其中 m = n/2（向下取整）。那么：

X × Y = AC × 10^(2m) + (AD + BC) × 10^m + BD

传统方法需要 4 次乘法（AC, AD, BC, BD），但 Karatsuba 发现：

(A + B)(C + D) = AC + AD + BC + BD
⇒ AD + BC = (A + B)(C + D) − AC − BD

因此只需 3 次递归乘法即可完成！这就是分治优化的关键。

C# 实现步骤详解

我们将用字符串表示大数，并实现以下辅助函数：

1. 字符串补零对齐
2. 大数加法
3. 大数减法（用于处理负中间结果）
4. Karatsuba 递归乘法

1. 辅助函数：字符串对齐与加减法

private static string AddStrings(string num1, string num2){    if (num1 == "0") return num2;    if (num2 == "0") return num1;    int i = num1.Length - 1, j = num2.Length - 1;    int carry = 0;    var result = new System.Text.StringBuilder();    while (i >= 0 || j >= 0 || carry > 0)    {        int d1 = i >= 0 ? num1[i--] - '0' : 0;        int d2 = j >= 0 ? num2[j--] - '0' : 0;        int sum = d1 + d2 + carry;        carry = sum / 10;        result.Insert(0, sum % 10);    }    return result.ToString();}private static string SubtractStrings(string num1, string num2){    // 简化：假设 num1 >= num2    int i = num1.Length - 1, j = num2.Length - 1;    int borrow = 0;    var result = new System.Text.StringBuilder();    while (i >= 0)    {        int d1 = num1[i--] - '0' - borrow;        int d2 = j >= 0 ? num2[j--] - '0' : 0;        borrow = 0;        if (d1 < d2)        {            d1 += 10;            borrow = 1;        }        result.Insert(0, d1 - d2);    }    // 去除前导零    string res = result.ToString().TrimStart('0');    return res == "" ? "0" : res;}private static string PadLeft(string s, int len, char c = '0'){    return s.PadLeft(len, c);}

2. 核心：Karatsuba 递归乘法

public static string Multiply(string num1, string num2){    // 处理边界情况    if (num1 == "0" || num2 == "0") return "0";    int n = Math.Max(num1.Length, num2.Length);    // 如果数字很小，直接用普通乘法（避免递归开销）    if (n <= 4)    {        return (long.Parse(num1) * long.Parse(num2)).ToString();    }    // 补零使长度为偶数    if (n % 2 == 1) n++;    num1 = PadLeft(num1, n);    num2 = PadLeft(num2, n);    int m = n / 2;    // 拆分    string a = num1.Substring(0, m);    string b = num1.Substring(m);    string c = num2.Substring(0, m);    string d = num2.Substring(m);    // 三次递归调用    string ac = Multiply(a, c);    string bd = Multiply(b, d);    string ab_cd = Multiply(AddStrings(a, b), AddStrings(c, d));    // 计算 ad + bc = (a+b)(c+d) - ac - bd    string ad_bc = SubtractStrings(SubtractStrings(ab_cd, ac), bd);    // 组合结果：ac * 10^(2m) + ad_bc * 10^m + bd    string result = ac;    result = PadLeft(result, result.Length + 2 * m, '0'); // ac << 2m    string mid = ad_bc;    mid = PadLeft(mid, mid.Length + m, '0'); // ad_bc << m    result = AddStrings(result, mid);    result = AddStrings(result, bd);    return result.TrimStart('0') == "" ? "0" : result.TrimStart('0');}

完整使用示例

class Program{    static void Main()    {        string x = "12345678901234567890";        string y = "98765432109876543210";        string product = Multiply(x, y);        Console.WriteLine($"{x} × {y} = {product}");        // 输出：12345678901234567890 × 98765432109876543210 = 1219326311370217952237463801111263526900    }}

总结

通过本教程，你已经掌握了如何在 C# 中使用分治算法高效实现大数乘法。这种方法不仅提升了计算效率，还加深了对递归和算法优化的理解。无论你是学习算法的小白，还是正在开发高精度计算模块的开发者，这套C#大整数乘法方案都值得收藏。

记住，关键在于理解 Karatsuba 的“三乘变四乘”思想。多练习几次，你也能轻松写出高性能的分治法实现大数相乘代码！