大整数运算 BigInteger class 的 Python 实现

本文档为 SJTU《计算导论》课程的个人作业

BigInteger 类 技术报告

综述

• 模块目的: 实现一个支持任意长度整数的类 BigInteger，提供加、减、乘、整除、幂运算以及若干辅助函数，避免 Python 内置整型在教学场景中不可见的实现细节。

• 实现语言/文件: Python, 文件 lab3.py。

“BigInteger 类”详述

• 说明: 用字符串表示大整数的数位并记录符号，支持通过字符串或另一个 BigInteger 构造对象，重载了常见算术运算符。

• 内部表示:

  • self.digits: 字符串形式的非负数部分。
  • self.sgn: 符号，取值 1 或 -1，但当 digits == '0' 时固定为 1（即零为非负）。

主要方法与函数说明：

• __init__(self, val)

  • 功能: 构造函数，可接受 str 或另一个 BigInteger。
  • 参数:
    • val: 若为 str，可以以可选前导 - 表示负数；若为 BigInteger，则按值拷贝。
  • 行为: 去除前导零（调用 formalizeDigits），设置 sgn（若数值为零则强制为正号）。

• __getitem__(self, key)

  • 功能: 支持下标访问 bigint[i] 返回 self.digits[key]，直接映射到内部字符串。
  • 返回: 单个字符（数位字符）。

• __len__(self)

  • 功能: 返回 self.digits 的长度（即数位数）。

• __str__(self)

  • 功能: 将 BigInteger 转换为常见字符串表示，零返回 '0'，否则根据 sgn 添加 - 前缀并拼接 digits。

• __add__(self, other)

  • 功能: 重载加法运算 +。
  • 算法: 根据符号决定是执行绝对值相加（调用 myPlus）还是绝对值相减（调用 mySub）。
  • 行为细节: 创建新的 BigInteger，设置结果符号并在结果为零时将符号设回正。

• __sub__(self, other)

  • 功能: 重载减法运算 -。
  • 算法: 将 other 取反后调用 __add__。

• __mul__(self, other)

  • 功能: 重载乘法 *。
  • 算法: 使用 myMul 对数位字符串做逐位乘法累加，结果符号为两个操作数符号的乘积；若结果为零设符号为正。

• __pow__(self, other)

  • 功能: 重载幂运算 **（注：other 是 Python 整数，不是 BigInteger）。
  • 算法: 使用快速幂算法：按位遍历 other 的二进制位，若当前位为 1，把 ans 乘以当前 tmp，每次把 tmp 平方，other 逐位右移。

• __floordiv__(self, other)

  • 功能: 重载整除 //。
  • 算法: 调用 myDiv，并根据符号设置结果，若结果为零则设为正。

辅助方法（内部实现）:

• compareAbs(self, other)

  • 功能: 比较两个 BigInteger 的绝对值大小。
  • 返回: 1 表示 self 的绝对值 >= other，0 表示小于。

• myPlus(num1, num2)

  • 功能: 计算两个非负 BigInteger 的绝对值之和，返回字符串形式的数位（已格式化）。
  • 算法: 将两个数位反向遍历，用整数列表保存逐位和与进位，然后反转并转为字符串，最后调用 formalizeDigits 去除前导零。
  • 时间复杂度: $\mathcal O(n)$。

• mySub(num1, num2)

  • 功能: 计算 num1 - num2（假设 |num1| >= |num2|），返回格式化的数位字符串。
  • 算法: 逐位做减法并处理借位，最后格式化字符串。
  • 时间复杂度: $\mathcal O(n)$。

• myMul(num1, num2)

  • 功能: 计算两个非负 BigInteger 的乘积，返回格式化的数位字符串。
  • 算法: 使用类似小学乘法的竖式运算：先把每一位数值放到倒序数组 ans 的合适位置，再做一次进位运算，最后拼接并格式化。
  • 时间复杂度: $\mathcal O(n^2)$。

• myDiv(num1, num2)

  • 功能: 计算 num1 // num2 的绝对值结果字符串（假设 num2 != 0）。
  • 算法: 模拟长除法：逐位把被除数的数位加入 remainder（一个 BigInteger），然后在内层循环中反复用 remainder -= num2 来计数当前位商值，直到 remainder < num2。
  • 错误处理: 若 num2.digits == '0' 抛出 ZeroDivisionError。

• formalizeDigits(str)

  • 功能: 去除字符串中的前导零，若所有位均为零则返回 '0'。
  • 用途: 用于输入规范化和算术结果的最终格式化。

不足与展望

• BigInteger 类中使用字符数组表示每一位数字，计算时要经常调用 ord(c) - ord('0') 获取对应的 0-9 数字，在运算量较大时时间开销较大，在进行 pow 运算时尤为明显。
• 有些地方不用进行前导零的判断和删除，但由于本人懒惰便统一加上，函数效率有待提高。
• 为了操作简便，除法运算每一步均先化为 BigInteger ，再计算。若直接用 list 模拟可能会更快。

代码实现

class BigInteger:

	def __init__(self, val):  # 可以通过传入一个 str 或另一个 BigInteger 来创建对象
		if isinstance(val, str):
			if val[0] == '-':
				sgn = -1  # sgn > 0 表示非负
				self.digits = BigInteger.formalizeDigits(val[1:])
			else:
				sgn = 1
				self.digits = BigInteger.formalizeDigits(val)
			self.sgn = 1 if self.digits == '0' else sgn
		else:
			self.digits = val.digits
			self.sgn = val.sgn

	def __getitem__(self, key):  # 定义 BigInteger[...] 的行为，取出对应的数位
		return self.digits[key]

	def __len__(self):  # len(BigInteger)
		return len(self.digits)

	def __str__(self):  # 加上正负号并转换为字符串
		if self.digits == '0':
			return '0'
		resultStr = ""
		if self.sgn < 0:
			resultStr += '-'
		resultStr += self.digits
		return resultStr

	def __add__(self, other):  # '+'
		ans = BigInteger('0')
		if self.sgn * other.sgn > 0:
			ans.sgn = self.sgn
			ans.digits = BigInteger.myPlus(self, other)
		elif BigInteger.compareAbs(self, other):
			ans.sgn = self.sgn
			ans.digits = BigInteger.mySub(self, other)
		else:
			ans.sgn = other.sgn
			ans.digits = BigInteger.mySub(other, self)
		if ans.digits == '0':
			ans.sgn = 1
		return ans

	def __sub__(self, other):  # '-'
		other_neg = BigInteger(other)
		other_neg.sgn *= -1
		return self + other_neg

	def __mul__(self, other): # '*'
		ans = BigInteger('0')
		ans.sgn = self.sgn * other.sgn
		ans.digits = BigInteger.myMul(self, other)
		if ans.digits == '0':
			ans.sgn = 1
		return ans

	def __pow__(self, other):  # '**'
		ans = BigInteger('1')
		tmp = BigInteger(self)
		while other > 0:
			if other & 1:
				ans = ans * tmp
			tmp = tmp * tmp
			other >>= 1
		return ans

	def __floordiv__(self, other):  # '//'
		ans = BigInteger('0')
		ans.sgn = self.sgn * other.sgn
		ans.digits = BigInteger.myDiv(self, other)
		if ans.digits == '0':
			ans.sgn = 1
		return ans

	# 以下为辅助函数

	def compareAbs(self, other):   # 比较两个 BigInteger 的绝对值大小, 返回 1 表示前者大
		if len(self.digits) != len(other.digits):
			return 1 if len(self.digits) > len(other.digits) else 0
		return 1 if self.digits >= other.digits else 0

	def myPlus(num1, num2):
		maxLen = max(len(num1), len(num2))
		ans = [0] * (maxLen + 1)
		d1 = num1.digits[::-1]  # 数位翻转
		d2 = num2.digits[::-1]
		for i in range(maxLen):
			if i < len(d1):
				ans[i] += ord(d1[i]) - ord('0')
			if i < len(d2):
				ans[i] += ord(d2[i]) - ord('0')
			if ans[i] >= 10:
				ans[i + 1] += 1
				ans[i] -= 10
		resultStr = "".join(map(str, ans[::-1]))
		return BigInteger.formalizeDigits(resultStr)

	def mySub(num1, num2):
		maxLen = len(num1)
		ans = [0] * (maxLen + 1)
		d1 = num1.digits[::-1]
		d2 = num2.digits[::-1]
		for i in range(maxLen):
			if i < len(d1):
				ans[i] += ord(d1[i]) - ord('0')
			if i < len(d2):
				ans[i] -= ord(d2[i]) - ord('0')
			if ans[i] < 0:
				ans[i + 1] -= 1
				ans[i] += 10
		resultStr = "".join(map(str, ans[::-1]))
		return BigInteger.formalizeDigits(resultStr)

	def myMul(num1, num2):
		maxLen = len(num1) + len(num2)
		ans = [0] * (maxLen + 1)
		d1 = num1.digits[::-1]
		d2 = num2.digits[::-1]
		len1, len2 = len(d1), len(d2)
		for i in range(len2):
			for j in range(len1):
				ans[i + j] += (ord(d2[i]) - ord('0')) * (ord(d1[j]) - ord('0'))
		for i in range(maxLen - 1):
			if ans[i] >= 10:
				ans[i + 1] += ans[i] // 10
				ans[i] %= 10
		resultStr = "".join(map(str, ans[::-1]))
		return BigInteger.formalizeDigits(resultStr)

	def myDiv(num1, num2):
		if num2.digits == '0':
			raise ZeroDivisionError(">_< 除数不能为零")
		if not BigInteger.compareAbs(num1, num2):
			return '0'
		result_str = ""
		remainder = BigInteger('0')
		for digit in num1.digits:
			if remainder.digits == '0':
				remainder.digits = digit
			else:
				remainder.digits += digit
			current_digit = 0
			while BigInteger.compareAbs(remainder, num2):
				remainder -= num2
				current_digit += 1
			result_str += str(current_digit)
		return BigInteger.formalizeDigits(result_str)

	def formalizeDigits(str):   # 去除输入、输出中可能存在的前导零
		i = 0
		while i < len(str) and str[i] == '0':
			i += 1
		return '0' if i == len(str) else str[i::]