<p>我正在做斯坦福大学的算法MOOC,却被卡拉通巴乘法算法编程作业困住了。<br/>
Karatsuba乘法是一种简单的两个整数的乘法算法,其速度比通常的乘法快</p>
<p><strong>限制</strong></p>
<ul>
<li>我限制自己只使用单位数乘法和填充数(在末尾加零,即乘以10的幂),因此有3种基本情况</li>
<li>我还决定将数字转换成字符串,并取几个数字,而不是将其除以10的幂,但我尝试了另一种方法,它没有帮助</li>
<li>我还决定推广该算法,即不要假设number1和number2具有相似的长度,因此我同时使用n1和n2(参见代码)</li>
<li>由于上述原因,我也决定不使用高斯技巧</li>
</ul>
<p>我知道,这些限制可能看起来毫无意义,但我将其用作编程练习,而不是一些实际的解决方案,因此我主要感兴趣的是发现我的错误,而不是找到一些“更简单的解决方案”</p>
<p>这是我的密码:</p>
<pre><code> def karatsuba(number1, number2):
n1 = len(str(number1)) # number of digits in the first number
n2 = len(str(number2)) # number of digits in the second number
if n1 == 1 and n2 == 1: # base case number 1 - both numbers are single-digit
kara = number1*number2
return kara
elif n1 == 1: # base case number 2 - only one number is single-digit
c = int(str(number2)[:(n2//2)])
d = int(str(number2)[(n2//2):])
kara = 10**((n2+1)//2)*c*number2 + d*number2
return kara
elif n2 == 1: # base case number 3 - only one number is single digit
a = int(str(number1)[:(n1//2)])
b = int(str(number1)[(n1//2):])
kara = 10**((n2+1)//2)*a*number2 + b*number2
return kara
elif n1 != 1 and n2 != 1: # loop
a = int(str(number1)[:(n1 // 2)])
b = int(str(number1)[(n1 // 2):])
c = int(str(number2)[:(n2 // 2)])
d = int(str(number2)[(n2 // 2):])
z1 = karatsuba(a, c)
z2 = karatsuba(a, d)
z3 = karatsuba(b, c)
z4 = karatsuba(b, d)
kara = 10**((n1+1)//2+(n2+1)//2)*z1 + 10**((n1+1)//2)*z2 + 10**((n2+1)//2)*z3 + z4
return kara
</code></pre>