1. 从“溢出”到“无限”为什么我们需要大数运算在编程的日常里我们习惯了int、long这些内置数据类型。它们就像我们熟悉的计算器处理日常的数字加减乘除得心应手。但当你尝试在代码里计算1000000000 * 1000000000或者处理一个长达数百位的质数时计算器会直接告诉你“溢出”了。这不是计算器坏了而是它内置的“寄存器”位数有限装不下那么大的数字。这就是大数运算要解决的核心问题突破硬件和标准数据类型对数字表示范围的限制实现对任意长度整数的精确计算。你可能觉得这离日常开发很远但实际上它的应用场景比你想象的更近。比如在密码学中RSA加密算法依赖的就是两个超大质数的乘积这个乘积可能长达2048位甚至4096位远超任何基本数据类型的表示范围。在金融领域高精度货币计算比如处理比特币的聪1 BTC 100,000,000 Satoshi容不得半点舍入误差。再比如科学计算、编译器对超大常量的处理甚至是某些在线判题系统OJ中的经典题目都离不开大数运算。所以大数运算不是炫技而是解决实际工程中“算不了”或“算不准”问题的必备工具。它不关心数字有多大只关心如何用有限的基础操作比如处理单个数字的加减去组合出处理无限大数字的能力。接下来我们就抛开那些复杂的库从最底层的原理开始手把手拆解如何实现大数的加、减、乘、除你会看到其中最核心的思想其实和我们小学列竖式一模一样。2. 基石如何用程序表示一个“大数”在实现运算之前首先要解决表示问题。计算机内存是线性的我们无法直接创造一个“无限长”的整数类型。最直观有效的策略就是模拟。2.1 字符串 vs. 整数数组通常有两种表示思路字符串表示将大数存成字符串如“12345678901234567890”。这很直观输入输出方便但进行运算时需要频繁地将字符‘0’转换成数字0效率较低且进位借位操作不够直接。整数数组表示这是更主流和高效的做法。我们用一个数组或列表来存储大数的每一位数字。这里又有一个关键选择高位在前还是低位在前2.2 低位优先让运算更自然的存储顺序让我们做个对比。假设要存储数字12345。高位优先人类阅读顺序数组 [1, 2, 3, 4, 5]索引0是最高位万位。低位优先运算友好顺序数组 [5, 4, 3, 2, 1]索引0是最低位个位。强烈建议使用低位优先存储。原因在于我们进行加减乘除时都是从最低位开始的。低位优先存储使得数组的索引增长方向与计算方向自然一致进位/借位时只需要向数组的后一个位置索引1操作。结果的长度增长时只需要在数组末尾追加新元素。这大大简化了代码逻辑。在后续的所有算法中我们均默认采用这种存储方式。因此一个核心的数据结构可以这样定义以Python列表为例其他语言类似class BigInt: def __init__(self, num_str): # 假设传入的 num_str 是合法的数字字符串如 12345 # 转换为低位优先的整数列表同时处理可能的负号 self.sign 1 # 1 表示正 -1 表示负 if num_str[0] -: self.sign -1 num_str num_str[1:] # 反转字符串并逐个字符转换为整数 self.digits [int(ch) for ch in reversed(num_str)] # 清理可能存在的前导零在低位优先表示中前导零在列表尾部 self._trim() def _trim(self): # 移除高位的零但至少保留一位如果是0的话 while len(self.digits) 1 and self.digits[-1] 0: self.digits.pop() if len(self.digits) 1 and self.digits[0] 0: self.sign 1 # 统一0的符号为正 def __str__(self): if not self.digits: return 0 # 反转 digits 得到正常顺序并拼接 num_str .join(str(d) for d in reversed(self.digits)) return (- if self.sign -1 else ) num_str这个简单的类包含了存储、清理前导零和基本输出功能是我们所有运算的基础。_trim方法很重要它能保证像[0, 0, 5]表示500这样的表示被规范化为[5]避免运算中产生不必要的复杂度。3. 大数加法与减法重温列竖式有了表示法我们就可以开始实现最基本的运算了。加法和减法的核心就是模拟我们小学学的竖式计算从低位到高位逐位计算并处理进位或借位。3.1 加法实现逐位相加与进位传递算法步骤非常直接从最低位索引0开始将两个数对应位相加再加上来自低位的进位值初始为0。当前位的结果是(和) % 10新的进位是(和) // 10。继续处理下一位直到处理完较长的那个数的所有位。如果最后还有进位大于0则在结果最高位添加一位。这里有一个关键细节如何处理符号不同的加法比如(A) (-B)。这本质上变成了A - B的减法问题。因此一个完整的加法函数需要先判断符号。为了清晰我们先实现一个不考虑符号的、针对两个正数数组的底层加法通常称为_add_absolute。def _add_absolute(a_digits, b_digits): 低位优先列表的绝对值加法返回结果列表 result [] carry 0 i 0 max_len max(len(a_digits), len(b_digits)) while i max_len or carry: digit_a a_digits[i] if i len(a_digits) else 0 digit_b b_digits[i] if i len(b_digits) else 0 total digit_a digit_b carry result.append(total % 10) # 当前位 carry total // 10 # 进位 i 1 return result然后在完整的add方法中处理符号逻辑同号相加绝对值相加符号不变。异号相加转化为绝对值相减结果的符号由绝对值大的数决定。3.2 减法实现借位的艺术减法是加法的逆运算但借位处理稍微麻烦一点。我们同样先实现一个不考虑符号的、保证a b的底层减法_subtract_absolute。算法步骤从最低位开始计算a[i] - b[i] - borrowborrow初始为0。如果差diff小于0则需要向高位借位令diff 10并设置borrow 1。如果差diff大于等于0则borrow 0。将diff存入结果。循环结束后需要清理结果中的前导零。def _subtract_absolute(a_digits, b_digits): 假设 a_digits 表示的绝对值 b_digits返回绝对值差的结果列表 result [] borrow 0 for i in range(len(a_digits)): digit_a a_digits[i] digit_b b_digits[i] if i len(b_digits) else 0 diff digit_a - digit_b - borrow if diff 0: diff 10 borrow 1 else: borrow 0 result.append(diff) # 移除结果中的前导零在低位优先表示中是从列表末尾移除 while len(result) 1 and result[-1] 0: result.pop() return result完整的减法subtract(a, b)则需要处理各种符号情况它可以基于加法和绝对值减法来实现a - b等价于a (-b)。所以我们可以先处理b的符号取反然后调用加法逻辑。在底层(A) - (B)转化为比较A和B的绝对值大小然后用_subtract_absolute计算并决定最终符号。(-A) - (-B)等价于(-A) (B)又回到了异号加法。实操心得比较函数的必要性在实现减法和处理符号时一个关键的辅助函数是比较两个大数绝对值的大小。这个函数需要从高位到低位注意我们的存储是低位优先所以要从列表末尾开始比较逐位比较。实现一个高效的_compare_absolute(a, b)函数返回 1 if ab, 0 if ab, -1 if ab能极大简化加减法中的符号和流程判断逻辑。这是很多初学者容易忽略但实际编码中必不可少的一环。4. 大数乘法从 O(n²) 到优化乘法是复杂度提升的第一个台阶。最直观的方法依然是模拟竖式乘法但这里有不同的优化层次。4.1 朴素竖式乘法O(n²)对于两个大数Am位和Bn位朴素算法是将B的每一位与整个A相乘得到一个中间结果然后将所有中间结果错位相加。123 (A) x 456 (B) -------- 738 (B[0]6 * A) 615 (B[1]5 * A左移一位) 492 (B[2]4 * A左移两位) -------- 56088在程序中“左移一位”对应在中间结果列表前面补零因为我们是低位优先存储所以是在末尾补零。这个算法的时间复杂度是 O(m*n)对于位数很大的数比如10万位效率很低。def _multiply_naive(a_digits, b_digits): m, n len(a_digits), len(b_digits) # 结果最多有 mn 位 result [0] * (m n) for i in range(m): # 遍历乘数A的每一位 carry 0 for j in range(n): # 遍历乘数B的每一位 # 当前位的结果是 A[i]*B[j] 之前的结果 进位 product a_digits[i] * b_digits[j] result[i j] carry result[i j] product % 10 carry product // 10 # 处理每一轮乘完B后剩余的进位 if carry: result[i n] carry # 注意这里可能是累加需要进一步处理进位 # 统一处理整个结果的进位因为上面 result[in] 可能大于9 carry 0 for k in range(len(result)): temp result[k] carry result[k] temp % 10 carry temp // 10 # 清理前导零 while len(result) 1 and result[-1] 0: result.pop() return result4.2 Karatsuba 算法分治的威力当数字非常大时我们可以使用更快的算法比如Karatsuba 算法。它的核心思想是分治将两个大数x和y各自分成两半 设x a * 10^(n/2) b,y c * 10^(n/2) d这里假设x和y位数相同为n且n是偶数。 那么x * y ac * 10^n (ad bc) * 10^(n/2) bd。 直接计算需要4次乘法ac,ad,bc,bd。Karatsuba 的巧妙之处在于它发现(ab)(cd) ac ad bc bd。 所以ad bc (ab)(cd) - ac - bd。 这样我们只需要计算三次乘法ac、bd和(ab)(cd)然后用它们组合出结果。这能将时间复杂度从 O(n²) 降低到约 O(n^1.585)。对于位数上千的大数优势非常明显。实现注意点递归基当数字位数小于某个阈值比如32或64时直接调用朴素乘法因为递归开销可能超过其收益。分割点确保分割后两部分位数接近并且处理奇数位数的情况。合并结果需要处理大数的加法和移位即乘以10的幂次在低位优先表示中就是在数组前面补零。def _multiply_karatsuba(x, y): 递归实现Karatsuba乘法x, y为低位优先列表 # 递归基当数字较小时使用朴素乘法 if len(x) 32 or len(y) 32: return _multiply_naive(x, y) # 确保 x 和 y 位数相同不足的补零 n max(len(x), len(y)) while len(x) n: x.append(0) while len(y) n: y.append(0) # 如果 n 是奇数补成偶数方便分割 if n % 2 1: n 1 x.append(0) if len(x) n-1 else None y.append(0) if len(y) n-1 else None mid n // 2 # 分割高位部分和低位部分 high1, low1 x[mid:], x[:mid] high2, low2 y[mid:], y[:mid] # 递归计算三个乘积 z0 _multiply_karatsuba(low1, low2) # bd z2 _multiply_karatsuba(high1, high2) # ac # 计算 (ab) 和 (cd) sum1 _add_absolute(low1, high1) # ab sum2 _add_absolute(low2, high2) # cd z1 _multiply_karatsuba(sum1, sum2) # (ab)(cd) # 计算 z1 z1 - z2 - z0即 adbc z1 _subtract_absolute(z1, z2) z1 _subtract_absolute(z1, z0) # 合并结果: z2 * 10^n z1 * 10^(n/2) z0 # 在低位优先表示中“左移”k位即在列表前添加k个零也就是在末尾补零因为低位在前 # 所以乘以 10^(n/2) 就是在 z1 后面补 mid 个零乘以 10^n 就是在 z2 后面补 n 个零。 result z0 # 加上 z1 * 10^mid z1_shifted z1 [0] * mid result _add_absolute(result, z1_shifted) # 加上 z2 * 10^n z2_shifted z2 [0] * n result _add_absolute(result, z2_shifted) return result踩坑提醒符号与零值处理在乘法的主函数中需要先处理符号结果的符号由两个乘数的符号异或决定同号得正异号得负。然后调用绝对值乘法。最后务必记得处理乘数为0的情况否则在Karatsuba递归中可能出现无限递归或错误。这就是为什么我们之前BigInt类中_trim方法非常重要的原因它能确保参与运算的数都是规范化的。5. 大数除法最复杂的运算除法是大数运算中最复杂的一环因为它涉及到试商、乘法和减法。常见的算法有模拟竖式除法长除法和牛顿迭代法。5.1 模拟竖式长除法这是最符合我们直觉的方法。给定被除数A和除数B我们试图找到商Q和余数R使得A B * Q R(0 R B)。算法思路从被除数A的高位开始取足够多的位使其组成的数大于或等于除数B。这部分称为“当前余数”。通过试商法估算当前余数 // B的商。这是一个关键难点因为这里除数和被除数都很大不能直接用编程语言的除法。常用的试商策略是取除数的前两位或一位如果除数是一位数和被除数的前三位或两位来估算一个“试商值”。由于估算可能偏大需要用一个循环去校正试商值减1直到B * 试商值 当前余数。将确定的商的一位写入结果。计算当前余数 当前余数 - B * 试商值。将被除数A的下一位移下来附加到当前余数后面形成新的“当前余数”回到步骤2。重复直到被除数的所有位都处理完毕。由于我们的存储是低位优先而除法从高位开始所以操作上需要一些转换。一个常见的技巧是将整个数组反转变为高位优先进行除法运算最后再将结果反转回来。或者我们直接在高位优先的视角下操作数组。def _divide_knuth(dividend, divisor): Knuth算法D的简化版用于大数除法返回 (商 余数) # 先处理一些简单情况 if _compare_absolute(dividend, divisor) 0: return ([0], dividend[:]) # 商为0余数为被除数 if len(divisor) 1: # 一位数除法可以简化 return _divide_by_single_digit(dividend, divisor[0]) # 规范化让除数的最高位足够大以简化试商 # 计算一个缩放因子 d使得 divisor[-1] (最高位) 基数/2 (这里基数是10) d 10 // (divisor[-1] 1) # 一个简单的估算 if d ! 1: dividend _multiply_by_single_digit(dividend, d) divisor _multiply_by_single_digit(divisor, d) # 注意这里乘法可能会增加位数需要trim m len(dividend) n len(divisor) # 初始化商长度为 m - n 1 quotient [0] * (m - n 1) # 将被除数复制一份作为当前余数多留一位空间 remainder dividend[:] [0] # 从高位到低位计算商 for j in range(m - n, -1, -1): # j 是商的位置 # 估算试商 q_hat # 取余数的前三位r2, r1, r0 (对应高位到低位) r2 remainder[j n] if j n len(remainder) else 0 r1 remainder[j n - 1] r0 remainder[j n - 2] if j n - 2 len(remainder) else 0 base 10 # 我们的基数是10 # 一个简单的试商公式 q_hat min((r2 * base r1) // divisor[-1], base - 1) # 校正试商 while True: # 计算 divisor * q_hat product _multiply_by_single_digit(divisor, q_hat) # 比较 product 和 remainder[j: jn1] # 这里需要实现一个切片比较的函数 _compare_slice if _compare_slice(remainder, j, jn1, product) 0: break q_hat - 1 if q_hat 0: break # 记录商 quotient[j] q_hat # 做减法remainder[j: jn1] - divisor * q_hat if q_hat 0: product _multiply_by_single_digit(divisor, q_hat) borrow 0 for i in range(n 1): idx j i sub product[i] if i len(product) else 0 diff remainder[idx] - sub - borrow if diff 0: diff base borrow 1 else: borrow 0 remainder[idx] diff # 如果最后还有借位说明试商还是大了理论上经过校正不会发生 if borrow: # 需要进一步处理这里简化通常不会发生 pass # 移除余数中可能产生的前导零在对应范围内 # 清理商和余数的前导零 quotient _trim_list(quotient) remainder _trim_list(remainder[:n]) # 余数有效位最多n位 return (quotient, remainder)这段代码是Knuth算法D的一个高度简化和示意版本真实实现需要考虑更多边界条件和优化。它清晰地展示了试商、乘减的核心循环。对于初学者实现一个支持除数是一位数的长除法已经是很好的起点。5.2 牛顿迭代法优化除法对于特别大的数模拟竖式除法的 O(n²) 复杂度可能成为瓶颈。牛顿迭代法提供了一种将除法转化为乘法的思路通过迭代快速逼近倒数即1/B然后用A * (1/B)来得到商。这通常用于高精度计算库中因为可以利用快速乘法如Karatsuba或更快的FFT乘法来加速。基本思想是为了计算Q A / B我们先计算X ≈ 1 / B。迭代公式为X_{n1} X_n * (2 - B * X_n)这个公式平方收敛意味着每次迭代正确的位数大约翻倍。当X足够精确后计算Q A * X然后做一些舍入调整得到最终商和余数。注意事项需要选取一个合适的初始近似值X0。迭代过程中需要的工作精度要逐步提高以节省计算量。最终需要通过A - B*Q来得到余数R并校正Q和R使得0 R B。牛顿迭代法的实现比长除法复杂得多但它与快速乘法结合后对于超大数数万位以上的除法性能优势巨大。这也是网络热词中 “newton reciprocal优化高精度除法” 所指的技术。6. 实战中的挑战与进阶优化实现基本功能只是第一步。在实际使用中我们会遇到更多挑战。6.1 性能瓶颈与更快的乘法当数字达到数万甚至百万位时Karatsuba算法也会显得吃力。此时业界标准是使用快速傅里叶变换FFT或数论变换NTT来将大数乘法的时间复杂度降至 O(n log n)。其核心思想是将大数看成多项式多项式的乘法可以通过FFT在频域中转化为O(n)的逐点相乘再逆变换回来。这需要较多的数学知识和底层优化是像GMPGNU多精度算术库这类顶级库的核心。6.2 内存管理与进制选择我们一直以10进制为例因为这样输入输出直观。但在内存中使用10进制是极其浪费的。一个int可以存储远大于9的值。因此实际的高精度库会使用更高的进制比如2^32或2^64进制依赖于机器的字长。这样数组中的每个元素称为“肢”limb可以存储一个很大的数极大地减少了数组长度和运算次数。进位和借位也变成了对2^32或2^64的模运算和除法。例如在2^32进制下数字12345678901234567890可能被表示为[低32位, 高32位]。所有的加减乘除运算都需要在基数为2^32的体系下重新实现这涉及到大量的位操作和溢出处理但性能提升是数量级的。6.3 符号、零与异常处理一个健壮的大数库必须细致处理符号定义清晰的规则例如0的符号通常为正。在加减乘除中符号逻辑要与绝对值运算正确结合。零值除法中除数为零要抛出异常。乘法中有一个乘数为零要快速返回零。前导零每次运算后都要调用_trim清理保证内部表示的简洁和正确性否则在比较或后续运算中会出错。输入验证确保输入的字符串只包含数字和可能的正负号。6.4 测试如何验证你的实现编写测试用例至关重要可以从简单到复杂边界测试0、1、-1、极大数、极小数。随机测试生成随机的大数用你的大数运算结果与Python自带的大整数int类型在Python中本身就是高精度运算结果进行对比。这是最有效的验证方法。压力测试进行连续的复杂运算检查内存是否正常释放结果是否始终正确。我在最初实现时就曾因为减法函数中借位处理的一个边界条件错误导致某些特定数字相减时结果多了一位。正是通过大量的随机对比测试才发现了这个隐蔽的Bug。从理解“为什么需要大数运算”开始到用数组模拟竖式实现加减乘除再到探讨Karatsuba、牛顿迭代等优化算法最后触及FFT和进制选择的进阶话题这正是一个功能从可用到高效、从玩具到工业级的演进过程。实现一个大数运算库是对编程基本功和算法思维的绝佳锻炼。它没有神秘的黑魔法所有的技巧都源于对基本运算原理的深刻理解和精巧的组织。当你亲手实现并能正确处理999999999999999999999999 ** 100这样的计算时那种对计算机如何“创造”无限精度的理解会比使用任何现成库都来得深刻。