时间戳

首页 > 解决方案 > RecursionError：在 Karatsuba 乘法中超出了最大递归深度

python - RecursionError：在 Karatsuba 乘法中超出了最大递归深度

问题描述

我正在实现 karatsuba 乘法。在我的作业中，我必须计算 2 个 64 位数字的乘法。

但是在实施它时，我遇到了错误-

RecursionError: maximum recursion depth exceeded while calling a Python object

所以我的问题是由于我的笔记本电脑限制导致的错误还是 karatsuba 不适用于如此大的数字？

我的代码是-

def karatsuba(num1,num2):

    if (len(str(num1))==1 and len(str(num2))==1):
        return num1*num2

    else:
        print(num1,num2)
        a,b=int(str(num1)[:len(str(num1))//2]),int(str(num1)[len(str(num1))//2:])
        c,d=int(str(num2)[:len(str(num2))//2]),int(str(num2)[len(str(num2))//2:])
        #print(a,b,c,d)


        res1=karatsuba(a,c)
        res2=karatsuba(b,d)
        res3=karatsuba(a+b,c+d)
        res4=res3-res2-res1
        #print(res1,res2,res4)

        n=max(len(str(num1)),len(str(num2)))
        #print(n)
        final_result=math.pow(10,n)*res1+math.pow(10,n/2)*res4+res2
    return final_result

编辑-该代码适用于小数字，但对于大数字它会给出错误-

ValueError: invalid literal for int() with base 10: ''

标签： pythonalgorithm

解决方案

推荐阅读