Search code examples
pythonalgorithmmultiplicationkaratsuba

Karotsuba multiplication - cannot find the error


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 restricted myself to only use single-digit multiplication and padding numbers (adding zeros at the end, i.e. multiplying by 10 to some power), so there are 3 base cases
  • I also decided to convert the numbers into strings and take several numbers instead of dividing it by 10 to some power, but I tried the other way, it does not help
  • I also decided to generalise the algorithm, i.e. do not assume that number1 and number2 have similar length therefore I use both n1 and n2 (see the code)
  • Because of the point above, I also decided not to use the Gauss's trick

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

Solution

  • 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.