I am doing the Stanford's Algorithms MOOC and got stuck with Karatsuba multiplication algorithm programming assignment.
Karatsuba multiplication is simply an algorithm for multiplication of two integer that is asymptotically faster than usual multiplication.
RESTRICTIONS
I know, the restrictions might see meaningless, but I used it as a programming exercise rather than some practical solution, hence I am mainly interesting in spotting my mistake rather than finding some "simpler solution".
Here is my 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
This is not a Karatzuba algorithm. The point of Karatzuba is to make only 3 recursive invocations; you do 4 of them. The recursive invocations, in your notation, should be
karatzuba(a, c)
karatzuba(b, d)
karatzuba(a + b, c + d)
Besides that, there is a problem with base case 2: number1
does not participate in it at all.