1. 项目概述为什么我们需要自己实现大整数在Python里写一个超大数字比如2**10000然后打印出来一切看起来都那么理所当然。Python的int类型似乎无所不能从负无穷大到正无穷大只要你内存够它就能存。这背后就是Python的“大整数”实现。但作为一个对底层有好奇心的开发者你有没有想过如果Python没有提供这个功能我们该如何自己实现一个能处理任意长度整数的数据类型呢这不仅仅是学术练习更是深入理解计算机如何表示和处理数字、内存管理以及算法效率的绝佳机会。模拟Python底层的大整数实现本质上是在构建一个“高精度整数”计算库。计算机的CPU原生支持的操作如加法、乘法是针对固定位宽如32位、64位的整数。一旦数字超出了这个范围就需要我们用软件来模拟多位数的算术运算这就像我们用纸笔计算多位数加减乘除一样只不过规则要交给计算机来执行。通过这个项目你将亲手揭开Pythonint神秘面纱的一角理解其“任意精度”背后的核心数据结构与算法比如如何用数组表示一个超长数字如何实现进位和借位以及如何处理负数和零。这对于深入理解数据结构、算法优化乃至密码学、科学计算等领域的基础设施都大有裨益。2. 核心思路与数据结构设计2.1 数字的表示从十进制到“基数为2^30”我们人类习惯用十进制每一位是0-9。计算机内部用二进制每一位是0或1。但在软件实现大整数时直接使用二进制位bit作为基本单位效率太低因为每次操作都要处理大量的位。Python的CPython实现采用了一种更高效的方法它使用一个数组在C中是digit数组在Python层面我们通常用列表模拟数组中的每个元素称为“数位”digit并不是一个十进制位而是一个能存储更大数值的“块”。一个常见的选择是让每个“数位”存储0到(2^30 - 1)之间的整数。为什么是2^30因为2^30约等于10.7亿小于2^31约21.4亿。在32位系统上这样选择可以确保两个这样的“数位”相乘最大约1.15e18的结果仍然能用一个64位的整数最大约1.84e19来安全地存储中间计算而不会溢出。这简化了乘法的实现。我们称这个“块”的大小为基数BASE这里BASE 2**30。因此一个数字被表示为一个列表列表的每个元素是一个介于0和BASE-1之间的整数。列表的第0个元素索引为0代表数字的最低有效位Least Significant Digit, LSD这与我们手写数字时从右向左个位、十位...的习惯一致。例如十进制数字12345678901234567890用基数为BASE的数组表示需要将其转换为BASE进制。此外我们还需要一个单独的符号位sign来表示正负通常用1表示正-1表示负0特殊表示数字零。2.2 类结构设计我们将设计一个BigInt类来封装这个大整数。class BigInt: # 定义基数每个“数位”能表示的最大值1 BASE 2 ** 30 def __init__(self, value0): 初始化一个大整数。 支持从普通整数(int)、字符串、或者另一个BigInt对象构造。 self.sign 1 # 符号1 正 -1 负 self.digits [] # 数字数组digits[0]是最低位 if isinstance(value, int): self._from_int(value) elif isinstance(value, str): self._from_str(value) elif isinstance(value, BigInt): self.sign value.sign self.digits value.digits[:] # 深拷贝数位数组 else: raise TypeError(Unsupported type for BigInt initialization) def _from_int(self, n): 从Python内置int初始化 if n 0: self.digits [0] self.sign 1 # 统一规定0的符号为正 return self.sign 1 if n 0 else -1 n abs(n) self.digits [] while n 0: # 不断除以BASE取余数作为低位 self.digits.append(n % self.BASE) n // self.BASE # 如果n本身就是0上面的循环不会执行需要额外处理 if not self.digits: self.digits [0] def _from_str(self, s): 从十进制数字字符串初始化如 123456789 s s.strip() if not s: raise ValueError(Empty string) if s[0] -: self.sign -1 s s[1:] elif s[0] : self.sign 1 s s[1:] else: self.sign 1 # 处理前导零 s s.lstrip(0) if s : # 字符串全是0 self.digits [0] self.sign 1 return self.digits [] # 这是一个低效但直观的转换方法模拟手工除法 # 更高效的方法是用较大的基数块直接转换但实现复杂 for ch in s: if not ch.isdigit(): raise ValueError(fInvalid character in number string: {ch}) # 我们将字符串s视为一个整体不断除以BASE # 这里用一个临时列表存储字符串的每位数字 temp_digits [int(ch) for ch in s] while temp_digits: # 当temp_digits表示的十进制数大于0时 remainder 0 new_digits [] for digit in temp_digits: current remainder * 10 digit new_digits.append(current // self.BASE) remainder current % self.BASE self.digits.append(remainder) # 本次循环的余数就是BASE进制下的一个低位 # 移除前导零准备下一轮除法 while new_digits and new_digits[0] 0: new_digits.pop(0) temp_digits new_digits # 如果转换后digits为空理论上不会因为s不为空且非零则设为[0] if not self.digits: self.digits [0]注意上面_from_str的实现采用了“手工除法”算法将整个十进制字符串反复除以BASE来得到BASE进制的表示。这个方法对于教学来说清晰但效率并非最优。在实际的高性能库中会采用更复杂的算法如使用更大的中间基数如10^9进行分块转换或者直接调用底层C函数。2.3 规范化Normalization在进行算术运算后数位数组self.digits中可能会产生前导零即高位是0或者出现数位值大于等于BASE的情况需要进位。我们需要一个_normalize方法来清理这些状态确保数字表示是规范化的即最高位非零除非数字本身就是0且所有数位都在[0, BASE)范围内。def _normalize(self): 规范化数位数组去除高位的零并处理进位确保每个数位在[0, BASE)内 # 1. 处理进位从低位到高位确保每位都小于BASE carry 0 for i in range(len(self.digits)): val self.digits[i] carry self.digits[i] val % self.BASE carry val // self.BASE # 如果最后还有进位需要添加新的高位 while carry 0: self.digits.append(carry % self.BASE) carry // self.BASE # 2. 去除高位的零从列表末尾开始去除 while len(self.digits) 1 and self.digits[-1] 0: self.digits.pop() # 3. 特殊处理零如果所有数位都是0则表示为[0]符号为正 if len(self.digits) 1 and self.digits[0] 0: self.digits [0] self.sign 1这个方法会在每次可能修改digits数组的运算如加法、乘法后被调用。3. 核心算术运算的实现3.1 比较运算在实现加减法之前我们需要先实现大小比较。这有助于我们判断两个数的绝对值大小从而决定加法和减法的具体流程。def _compare_abs(self, other): 比较两个大整数的绝对值大小。 返回: 如果 self的绝对值 other的绝对值返回1 如果 self的绝对值 other的绝对值返回-1 如果相等返回0。 # 先比较位数 len_self len(self.digits) len_other len(other.digits) if len_self ! len_other: return 1 if len_self len_other else -1 # 位数相同从最高位列表末尾开始逐位比较 for i in range(len_self - 1, -1, -1): if self.digits[i] ! other.digits[i]: return 1 if self.digits[i] other.digits[i] else -1 return 0 def __eq__(self, other): if not isinstance(other, BigInt): return False return self.sign other.sign and self.digits other.digits def __lt__(self, other): if not isinstance(other, BigInt): raise TypeError(f not supported between instances of BigInt and {type(other).__name__}) if self.sign ! other.sign: return self.sign other.sign # 负数 正数 # 符号相同比较绝对值 abs_cmp self._compare_abs(other) if self.sign 1: # 正数 return abs_cmp 0 # self绝对值小则self小 else: # 负数 return abs_cmp 0 # self绝对值小则self大负得少其他比较操作符,,,!可以基于__eq__和__lt__自动生成或者类似实现。3.2 加法与减法加法和减法是互逆的并且都需要考虑符号。核心思路是先实现无符号的加法和减法即操作两个正数的绝对值然后再根据操作数的符号组合来决定调用哪个以及结果的符号。无符号加法 (_uadd)模拟竖式加法从最低位开始逐位相加并处理进位。def _uadd(self, other): 返回 self绝对值 other绝对值 的结果一个新的BigInt符号为正 # 保证self的位数不少于other方便计算 a_digits self.digits b_digits other.digits if len(a_digits) len(b_digits): a_digits, b_digits b_digits, a_digits result_digits a_digits[:] # 拷贝较长的数字 carry 0 for i in range(len(b_digits)): s result_digits[i] b_digits[i] carry result_digits[i] s % self.BASE carry s // self.BASE # 处理剩余进位 i len(b_digits) while carry and i len(result_digits): s result_digits[i] carry result_digits[i] s % self.BASE carry s // self.BASE i 1 if carry: result_digits.append(carry) result BigInt(0) result.digits result_digits result.sign 1 result._normalize() return result无符号减法 (_usub)假设self的绝对值大于等于other的绝对值。模拟竖式减法处理借位。def _usub(self, other): 返回 self绝对值 - other绝对值 的结果一个新的BigInt符号为正。 前提self的绝对值 other的绝对值。 result_digits self.digits[:] borrow 0 for i in range(len(other.digits)): sub result_digits[i] - borrow - other.digits[i] if sub 0: sub self.BASE borrow 1 else: borrow 0 result_digits[i] sub # 处理向更高位的借位 i len(other.digits) while borrow and i len(result_digits): if result_digits[i] 1: result_digits[i] - 1 borrow 0 else: result_digits[i] self.BASE - 1 borrow 1 i 1 # 注意根据前提最终borrow应该为0 result BigInt(0) result.digits result_digits result.sign 1 result._normalize() # 这一步会去除结果的高位零 return result完整的带符号加法 (__add__)根据两数符号的四种情况正正、正负、负正、负负来组合调用上述无符号运算。def __add__(self, other): if not isinstance(other, BigInt): other BigInt(other) # 尝试将other转换为BigInt # 情况1: 同号绝对值相加符号不变 if self.sign other.sign: result self._uadd(other) result.sign self.sign return result # 情况2: 异号转换为绝对值相减 cmp self._compare_abs(other) if cmp 0: # 绝对值相等结果为0 return BigInt(0) elif cmp 0: # |self| |other| result self._usub(other) result.sign self.sign else: # |self| |other| result other._usub(self) result.sign other.sign return result完整的带符号减法 (__sub__)a - b等价于a (-b)。我们可以利用已经实现的加法和取负操作。def __neg__(self): 取负 result BigInt(self) if not self.is_zero(): # 零的符号保持为正 result.sign -self.sign return result def __sub__(self, other): if not isinstance(other, BigInt): other BigInt(other) # a - b a (-b) return self (-other)3.3 乘法运算乘法相对复杂最直观的方法是模拟我们小学学的竖式乘法也称为“笔算乘法”或“朴素乘法”。对于两个大整数am位和bn位其时间复杂度为O(m*n)。虽然存在更快的算法如Karatsuba算法、FFT-based算法但朴素乘法实现简单对于理解原理足够了。朴素乘法算法思路初始化一个长度为mn的结果数组res全部置0因为两个最大为m位和n位的数相乘结果最多有mn位。双层循环外层遍历乘数a的每一位i内层遍历被乘数b的每一位j。计算temp a[i] * b[j] res[ij]res[ij]是之前计算可能产生的进位或部分和。res[ij] temp % BASE计算进位carry temp // BASE。将进位加到res[ij1]上可能需要连续处理进位。循环结束后对res进行规范化去除前导零并确定符号同号得正异号得负。def __mul__(self, other): if not isinstance(other, BigInt): other BigInt(other) # 处理乘数为0的情况 if self.is_zero() or other.is_zero(): return BigInt(0) m, n len(self.digits), len(other.digits) # 结果最多有 mn 位 res_digits [0] * (m n) # 双层循环模拟竖式乘法 for i in range(m): carry 0 a_digit self.digits[i] # 如果当前位是0可以跳过内层循环优化这里为了清晰不跳过 for j in range(n): # 计算当前位的乘积加上之前的进位和当前结果位 k i j temp res_digits[k] a_digit * other.digits[j] carry res_digits[k] temp % self.BASE carry temp // self.BASE # 处理内层循环结束后剩余的进位 if carry: res_digits[i n] carry # 注意是因为可能已经有值 result BigInt(0) result.digits res_digits result.sign self.sign * other.sign # 符号规则 result._normalize() return result实操心得乘法优化上面的朴素乘法在a_digit为0时可以跳过内层循环这是一个简单的优化。对于真正的高性能库当数字规模较大时比如超过几百位会切换到Karatsuba算法其时间复杂度约为O(n^1.585)比O(n^2)快得多。Karatsuba算法的核心思想是分治将大数拆分成两部分用三次较小规模的乘法和一些加减法来代替一次大规模乘法。3.4 除法与取模运算除法是最复杂的运算我们实现整数除法返回商和余数。我们采用经典的“长除法”算法类似于手工计算。这里我们实现__floordiv__整除和__mod__取模它们可以同时计算。算法思路无符号长除法 假设被除数u和除数v都是正数且v不为零。规范化如果除数v的最高位小于BASE/2我们可以通过同时将被除数和除数乘以一个缩放因子d来让除数的最高位足够大这可以简化后续的估商过程。d BASE // (v.digits[-1] 1)。初始化余数r为0商q的各位初始为0。从被除数的最高位开始逐位“拉下来”与当前余数结合形成临时的被除数current。估商用current的高两位因为我们的digit小于BASE来估算商q_hat。q_hat min((current // v.digits[-1]), BASE-1)。然后需要调整q_hat确保它不会过大通过检查q_hat * v是否大于current。乘减计算current current - q_hat * v。如果结果为负说明估商过大将q_hat减1重新计算current。将正确的q_hat作为商的一位记录下来。将current作为新的余数继续处理下一位。循环结束后对商和余数进行规范化并处理符号。由于完整的长除法实现代码较长这里给出一个高度简化版的思路它适用于教学但效率不如上述规范化版本高。简化版直接模拟手工减法试商。def _udivmod(self, other): 无符号除法返回 (商, 余数) 两个新的BigInt对象。 假设 self 和 other 的符号都为正且 other 不为零。 这是一个简化实现效率较低但易于理解。 if other.is_zero(): raise ZeroDivisionError(integer division or modulo by zero) # 如果被除数小于除数商为0余数为被除数 cmp self._compare_abs(other) if cmp 0: return BigInt(0), BigInt(self) # 商0余数self if cmp 0: return BigInt(1), BigInt(0) # 商1余数0 # 将被除数和除数转换为便于操作的列表最高位在最后 u self.digits[:] # 被除数 v other.digits[:] # 除数 m, n len(u), len(v) # 初始化商长度为 m-n1 q_digits [0] * (m - n 1) # 制作一个除数v的副本用于计算 # 从被除数的高位开始逐位处理 # 这里我们采用一个更直观但低效的方法构造当前的被除数片段 # 实际上高效算法会操作整个数组这里为了清晰我们用一个临时BigInt来模拟 # 更实用的简化实现使用减法循环 # 让被除数不断减去除数直到小于除数减的次数就是商 # 注意这只适用于教学对于大数效率极低O(商)的时间复杂度 remainder BigInt(self) # 余数初始为被除数 divisor BigInt(other) quotient BigInt(0) while remainder._compare_abs(divisor) 0: remainder remainder._usub(divisor) # 无符号减法 quotient quotient._uadd(BigInt(1)) # 商加1 return quotient, remainder重要提示上面_udivmod的减法循环实现仅用于演示算法原理绝对不可用于实际计算因为当商很大时例如10^1000除以2它需要进行10^1000次减法这是天文数字。实际Python的int除法使用的是高度优化的算法如Knuth的“算法D”。在你自己实现时应该参考《计算机程序设计艺术》TAOCP中的经典长除法算法。基于_udivmod我们可以实现带符号的除法和取模def __floordiv__(self, other): if not isinstance(other, BigInt): other BigInt(other) q, r self._udivmod(other) # 符号规则商向负无穷取整。Python的规则是 (a // b) floor(a / b) # 简单规则如果两数符号不同且余数不为零则商需要减1向负无穷调整 # 但我们的_udivmod返回的是绝对值相除的结果。 # 商的符号同号为正异号为负。 q.sign self.sign * other.sign # 余数的符号与被除数self相同。 r.sign self.sign # Python整除规则商是代数商向负无穷取整。 # 如果被除数和除数异号且余数不为0则商需要减1因为我们的_udivmod是向下取整的除法 if self.sign * other.sign -1 and not r.is_zero(): # 例如 -7 // 3 -3 (因为 -2.333... 向负无穷取整是 -3) # 我们的_udivmod(7,3)得到 q2, r1。 # 我们需要 q - (21) -3 q q._uadd(BigInt(1)) # 给商的绝对值加1 q.sign -1 # 符号为负 # 同时需要调整余数 r self - q * other # 对于 -7 // 3: r -7 - (-3)*3 -7 9 2 # 但Python中 -7 % 3 2。余数符号与除数相同不Python规定余数符号与除数相同。 # 实际上关系式是 a b * q r 且 0 |r| |b| 并且 r 的符号与 b 相同。 # 所以我们需要重新计算余数 r self - other * q r self - other * q return q def __mod__(self, other): if not isinstance(other, BigInt): other BigInt(other) q, r self._udivmod(other) r.sign self.sign # 应用Python的取模规则余数符号与除数相同且 0 abs(r) abs(other) # 如果余数符号与除数不同需要调整 if not r.is_zero() and r.sign ! other.sign: # 将余数向除数的方向调整 # 如果除数为正余数应为正如果除数为负余数应为负。 # 调整方法 r r other同时商q减1但这里我们只关心r # 更简单直接计算 r self - other * (self // other) q_floordiv self // other r self - other * q_floordiv return r4. 辅助方法、性能考量与扩展4.1 字符串表示与输出我们需要实现__str__方法将内部的BASE进制表示转换回人类可读的十进制字符串。这是_from_str的逆过程。一个简单但低效的方法是不断除以10取余。更高效的方法是使用除法但这次是除以10。def __str__(self): if self.is_zero(): return 0 # 复制一份数位避免修改原数据 digits_copy self.digits[:] decimal_digits [] # 当数字用digits_copy表示不为0时 while not (len(digits_copy) 1 and digits_copy[0] 0): remainder 0 # 从最高位开始模拟除以10 for i in range(len(digits_copy)-1, -1, -1): current remainder * self.BASE digits_copy[i] digits_copy[i] current // 10 remainder current % 10 decimal_digits.append(str(remainder)) # 去除digits_copy中可能产生的高位零 while len(digits_copy) 1 and digits_digits_copy[-1] 0: digits_copy.pop() # 得到的decimal_digits是从低位到高位的余数需要反转 decimal_str .join(reversed(decimal_digits)) return - decimal_str if self.sign -1 else decimal_str4.2 性能瓶颈与优化方向我们实现的这个BigInt是一个教学模型其性能与Python原生的int相比有巨大差距。主要的性能瓶颈在于算法复杂度我们使用的都是最朴素的O(n^2)量级的算法乘法、除法。Python的int使用了Karatsuba、Toom-Cook甚至FFT等高级算法来加速大数乘法。Python开销每个digit都是一个Pythonint对象列表的每个元素也是一个对象内存开销和操作开销巨大。CPython的int是用C数组实现的每个digit是C的uint32_t或uint64_t存储在连续内存中效率极高。内存管理频繁创建新的列表和BigInt对象会产生大量内存分配和垃圾回收开销。优化方向使用内置int作为digit我们已经做了但Python的int本身也有开销。在C扩展中可以使用C原生类型。实现更快的乘法当数字位数超过一定阈值如70位时切换到Karatsuba算法。实现更快的除法实现完整的、带规范化的Knuth算法D。内存池对于频繁创建销毁的临时大整数对象可以实现一个对象池来复用内存。使用PyPy或C扩展PyPy的JIT编译器可能优化我们的Python代码。终极方案是像CPython一样用C语言重写核心运算部分。4.3 测试与常见问题编写全面的测试用例至关重要。def test_bigint(): # 测试初始化 assert str(BigInt(12345)) 12345 assert str(BigInt(-67890)) -67890 assert str(BigInt(BigInt(42))) 42 # 测试比较 assert BigInt(100) BigInt(50) assert BigInt(-100) BigInt(50) assert BigInt(0) BigInt(0) # 测试加法 a BigInt(12345678901234567890) b BigInt(98765432109876543210) assert str(a b) 111111111011111111100 assert str(a (-b)) -86419753208641975320 assert str(BigInt(0) a) str(a) # 测试减法 assert str(b - a) 86419753208641975320 assert str(a - b) -86419753208641975320 assert str(a - a) 0 # 测试乘法 x BigInt(123456789) y BigInt(987654321) # 123456789 * 987654321 121932631112635269 (可以用计算器验证) assert str(x * y) 121932631112635269 assert str(x * BigInt(0)) 0 assert str(x * BigInt(1)) str(x) # 测试除法和取模 p BigInt(100000000000000000000) q BigInt(3) div, mod p // q, p % q assert str(div) 33333333333333333333 assert str(mod) 1 # 测试负数除法 assert str(BigInt(-7) // BigInt(3)) -3 assert str(BigInt(-7) % BigInt(3)) 2 assert str(BigInt(7) // BigInt(-3)) -3 assert str(BigInt(7) % BigInt(-3)) -2 print(All tests passed!) if __name__ __main__: test_bigint()常见问题与排查结果错误或无限循环首先检查_normalize函数是否正确处理了进位和去零。这是许多运算错误的根源。确保在每次修改digits数组后都调用_normalize。性能极慢检查是否在循环中频繁创建新的BigInt对象。对于内部运算可以考虑使用原地操作修改现有对象来减少对象创建但要注意不可变性带来的便利与性能的权衡。除法结果不对长除法的实现非常容易出错尤其是估商和调整步骤。务必用大量随机测试数据与Python原生int的运算结果进行对比测试。内存占用过大确保_normalize函数去除了高位零。一个未规范化的数字如[1, 0, 0, 0]表示1会浪费大量空间。4.4 扩展功能一个完整的BigInt实现还可以考虑位运算实现,|,^,,。对于大整数左移相当于乘以2的幂右移相当于除以2的幂向下取整可以基于乘除法高效实现。幂运算实现**运算符使用快速幂算法Exponentiation by Squaring时间复杂度O(log n)。与其他类型的转换完善__int__方法注意可能溢出实现__float__。哈希支持实现__hash__使得BigInt对象可以作为字典的键。格式化输出实现__format__方法支持二进制、八进制、十六进制输出。通过这个从零开始模拟Python大整数的项目你不仅构建了一个可用的高精度整数类型更重要的是深入理解了计算机进行大数运算的底层逻辑、算法设计与性能权衡的考量。这为你后续学习密码学、编译器设计、数值计算等领域的底层知识打下了坚实的基础。