大数乘法的高效之道（基于分治思想的Go语言实现）

Karatsuba算法原理

假设我们将两个大数 X 和 Y 分别拆成两部分：

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

其中 m 是位数的一半（向下取整）。那么：

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

传统方法需要计算四次乘法：AC、AD、BC、BD。

但Karatsuba发现：(A + B)(C + D) = AC + AD + BC + BD，因此：

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

这样，我们只需三次乘法：AC、BD、(A+B)(C+D)，再做几次加减法即可。虽然增加了加法，但乘法次数减少了，整体效率更高！

Go语言实现大数乘法

Go语言标准库中的 math/big 包已经支持大数运算，但为了学习Karatsuba算法，我们手动实现一个简化版（仅处理非负整数字符串）。

// karatsuba.gopackage mainimport (	"fmt"	"strings")// addStrings 实现两个非负整数字符串相加func addStrings(a, b string) string {	i, j := len(a)-1, len(b)-1	carry := 0	res := []byte{}	for i >= 0 || j >= 0 || carry > 0 {		x, y := 0, 0		if i >= 0 {			x = int(a[i] - '0')			i--		}		if j >= 0 {			y = int(b[j] - '0')			j--		}		sum := x + y + carry		res = append([]byte{byte(sum%10 + '0')}, res...)		carry = sum / 10	}	return string(res)}// subtractStrings 实现 a - b（假设 a >= b）func subtractStrings(a, b string) string {	i, j := len(a)-1, len(b)-1	borrow := 0	res := []byte{}	for i >= 0 {		x := int(a[i] - '0') - borrow		borrow = 0		y := 0		if j >= 0 {			y = int(b[j] - '0')			j--		}		if x < y {			x += 10			borrow = 1		}		res = append([]byte{byte(x-y + '0')}, res...)		i--	}	// 去除前导零	result := strings.TrimLeft(string(res), "0")	if result == "" {		return "0"	}	return result}// multiplyByPowerOf10 在字符串后添加 n 个零func multiplyByPowerOf10(s string, n int) string {	if s == "0" {		return "0"	}	return s + strings.Repeat("0", n)}// karatsuba 实现 Karatsuba 大数乘法func karatsuba(x, y string) string {	// 去除前导零	x = strings.TrimLeft(x, "0")	y = strings.TrimLeft(y, "0")	if x == "" {		x = "0"	}	if y == "" {		y = "0"	}	// 基础情况：如果任一数为0，返回0	if x == "0" || y == "0" {		return "0"	}	// 如果数字较小，直接用内置方式（或简单循环）	if len(x) == 1 && len(y) == 1 {		return fmt.Sprintf("%d", (x[0]-'0')*(y[0]-'0'))	}	// 确保两个数长度一致，不足前面补0	n := len(x)	m := len(y)	maxLen := n	if m > maxLen {		maxLen = m	}	// 补齐到偶数长度便于分割	if maxLen%2 == 1 {		maxLen++	}	x = strings.Repeat("0", maxLen-len(x)) + x	y = strings.Repeat("0", maxLen-len(y)) + y	mid := maxLen / 2	A := strings.TrimLeft(x[:mid], "0")	if A == "" {		A = "0"	}	B := strings.TrimLeft(x[mid:], "0")	if B == "" {		B = "0"	}	C := strings.TrimLeft(y[:mid], "0")	if C == "" {		C = "0"	}	D := strings.TrimLeft(y[mid:], "0")	if D == "" {		D = "0"	}	// 三次递归乘法	AC := karatsuba(A, C)	BD := karatsuba(B, D)	APlusB := addStrings(A, B)	CPlusD := addStrings(C, D)	ABCD := karatsuba(APlusB, CPlusD)	// 计算 AD + BC = (A+B)(C+D) - AC - BD	ADPlusBC := subtractStrings(subtractStrings(ABCD, AC), BD)	// 合并结果	term1 := multiplyByPowerOf10(AC, 2*mid)	term2 := multiplyByPowerOf10(ADPlusBC, mid)	result := addStrings(addStrings(term1, term2), BD)	return strings.TrimLeft(result, "0")}func main() {	x := "123456789"	y := "987654321"	fmt.Println("Result:", karatsuba(x, y))	// 输出：121932631112635269}

代码说明

• addStrings 和 subtractStrings：用于处理大数加减法。
• multiplyByPowerOf10：模拟乘以10的幂（即在末尾加零）。
• karatsuba：核心递归函数，实现分治逻辑。
• 注意处理前导零和边界情况（如“0”）。

为什么选择Go语言实现？

Go语言语法简洁、并发模型优秀，且对字符串操作友好，非常适合教学和原型开发。虽然生产环境可直接使用 math/big.Int.Mul，但手写算法能加深对分治算法和大数乘法的理解。

总结

通过本文，你学会了：

• 分治算法的基本思想；
• Karatsuba算法如何优化大数乘法；
• 用Go语言从零实现该算法。

掌握这些知识后，你不仅能应对面试中的算法题，还能在实际项目中处理超大整数运算。快动手试试吧！

关键词回顾：分治算法、大数乘法、Go语言实现、Karatsuba算法。