Python 实现大整数乘法算法的示例代码
我们平时接触的长乘法，按位相乘，是一种时间复杂度为O(n^2)的算法。今天，我们来介绍一种时间复杂度为O(n^log3)的大整数乘法(log表示以2为底的对数)。
介绍原理
karatsuba算法要求乘数与被乘数要满足以下几个条件，第一，乘数与被乘数的位数相同；第二，乘数与被乘数的位数应为 2次幂，即为2^2, 2^3,2^4，2^n等数值。
下面我们先来看几个简单的例子，并以此来了解karatsuba算法的使用方法。
两位数相乘
我们设被乘数A=85，乘数B=41。下面来看我们的操作步骤：
将A,B一分为二，令p=A的前半部分=8，q=A的后半部分=5，r=B的前半部分=4，s=B的后半部分= 1，n=2。通过简单的数学运算：
A*B=pq*rs =(p*10+q)*(r*10+s) = p*r*10^2+(p*s+q*r)*10+q*s。
令u=p*r，v=（p-q)*(s-r)，w=q*s。所以A*B= u*10^2+(u+v+w)*10+w。
换成数值求解的过程如下：
A*B=85*41=(8*10+5)*(4*10+1)=8*4*10*10+(8*1+5*4)*10+5*1。
其中u=8*4=32，v=(8-5)(1-4)=-9，w=5*1=5。
所以，A*B=32*100+(32-9+5)*10+5=3485。与长乘法所得结果一致。
四位数相乘
我们设被乘数A=8537，乘数B=4123。下面来看我们的操作步骤：
将A,B一分为二，令p=A的前半部分=85，q=A的后半部分=37，r=B的前半部分=41，s=B的后半部分= 23，n=4。
==>其中，u=85*41,v=(85-37)*(23-41),w=37*23。
==>A*B=8537*4123=u*10^4+(u+v+w)*10^2+w= 3485_0000+34_7200+851=35198051。
在我们计算u，v, w的过程中又会涉及两位数的乘法，我们继续使用Karatsuba算法得出两位数相乘的结果。
N位数相乘
我们令n为乘数与被乘数的位数，令p=A的前半部分，q=A的后半部分，r=B的前半部分，s=B的后半部分。
==>其中，u=p*r，v=(p-q)*(s-r)，w=q*s。
所以A*B= u*10^n+(u+v+w)*10^(n/2)+w。
而u,v,w则是两个n/2位的乘法运算。我们继续调用Karatsuba算法计算u,v,w的数值。接着，我们在计算n/2乘法的过程中又会遇到n/4位的乘法运算……以此类推，直到我们遇到两个个位数的乘法，我们就直接返回这两个个位数乘法的结果。层层返回，最终得到N位数的乘法结果。
时间复杂度
我们平常使用的长乘法，是O(n^2)的时间复杂度。比如两个N位数相乘，我们需要将每一位按规则相乘，所以需要计算 N*N次乘法。而使用 Karatsuba算法每层需要计算三次乘法，两次加法，以及若干次加法，每使用一次karatsuba算法，乘法规模就下降一半。
所以，对于两个n= 2^K位数乘法运算，我们需要计算3^k次乘法运算。而K=logn(底数为2)，3^K=3^logn=2 ^(log3*logn)=2^(logn*log3)=n^log3（底数为2）。
代码实现
frommathimportlog2,ceil
defpad(string:str,real_len:int,max_len:int)->str:
pad_len:int=max_len-real_len
returnf"{'0'*pad_len}{string}"
defkara(n1:int,n2:int)->int:
ifn1<10orn2<10:
returnn1*n2
n1_str:str=str(n1)
n2_str:str=str(n2)
n1_len:int=len(n1_str)
n2_len:int=len(n2_str)
real_len:int=max(n1_len,n2_len)
max_len:int=2**ceil(log2(real_len))
mid_len:int=max_len>>1
n1_pad:str=pad(n1_str,n1_len,max_len)
n2_pad:str=pad(n2_str,n2_len,max_len)
p:int=int(n1_pad[:mid_len])
q:int=int(n1_pad[mid_len:])
r:int=int(n2_pad[:mid_len])
s:int=int(n2_pad[mid_len:])
u:int=kara(p,r)
v:int=kara(q-p,r-s)
w:int=kara(q,s)
returnu*10**max_len+(u+v+w)*10**mid_len+w
输出结果：
==>kara(123456,9734)==123456*9734
==>kara(1234233456756,32459734)==1234233456756*32459734
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持毛票票。