Python递归乘法程序处理超大数字时崩溃无输出问题求助

你的递归乘法程序在处理大数时崩溃，核心原因有两个：

1. 递归深度超限：multiply函数通过递归累加实现乘法，递归深度等于第二个参数y的数值。当y是125位大数时，递归深度达到10^{125级别，哪怕手动设置递归限制为10}9，操作系统的栈内存也无法支撑这么深的调用，直接导致栈溢出崩溃。
2. 时间复杂度爆炸：累加式乘法的时间复杂度是O(y)，对于125位的数，需要执行10^125次加法运算，这在现实中完全无法完成，程序会直接卡死或崩溃。

修复方案 #

方案1：使用Python原生乘法（推荐） #

Python原生支持任意精度整数运算，直接用*运算符就能高效处理大数乘法，无需自己实现递归累加：

import sys
import random as rt

class recursionlimit:
    def __init__(self, limit):
        self.limit = limit

    def __enter__(self):
        self.old_limit = sys.getrecursionlimit()
        sys.setrecursionlimit(self.limit)

    def __exit__(self, type, value, tb):
        sys.setrecursionlimit(self.old_limit)

def multiply(x,y):
    # 直接用Python原生乘法，高效支持大数
    return x * y

def random_number():
    # 生成125位数字：范围是10^124到10^125-1
    number = rt.randint(pow(10,124), pow(10,125)-1)
    return number

def main():
    x = random_number()
    y = random_number()
    
    # 原生乘法无递归，无需修改递归限制
    output = multiply(x,y)
    print(output)

main()

方案2：实现高效的大数乘法算法（学习用） #

如果是为了学习算法，可以实现Karatsuba算法（分治法，时间复杂度O(n^{log₂3)≈O(n}1.585)），比累加式高效得多：

def karatsuba(x, y):
    if x < 10 or y < 10:
        return x * y
    
    # 计算数字的位数
    n = max(len(str(x)), len(str(y)))
    half = n // 2
    
    # 分割数字
    a = x // (10 ** half)
    b = x % (10 ** half)
    c = y // (10 ** half)
    d = y % (10 ** half)
    
    # 递归计算三个子问题
    ac = karatsuba(a, c)
    bd = karatsuba(b, d)
    ad_bc = karatsuba(a + b, c + d) - ac - bd
    
    # 合并结果
    return ac * (10 ** (2 * half)) + ad_bc * (10 ** half) + bd

# 替换multiply函数为karatsuba即可
def multiply(x,y):
    return karatsuba(x,y)

额外说明 #

原代码中random_number函数生成的是129位数字（pow(10,128)到pow(10,129)），如果目标是生成125位数字，应该改成pow(10,124)到pow(10,125)-1，已在修复代码中修正。

内容的提问来源于stack exchange，提问作者Vedik Agarwal