CODEWITHSUNDEEP
pythonalgorithmrecursionmultiplication
Anmol Saksena
Anmol Saksena

Reputation: 91

Recursion Error encountered in Python while writing code for Karatsuba multiplication

I am new to algorithms and I am trying to write code for the Karatsuba Multiplication algorithm using recursive function calls.

I understand that karatsuba multiplication works with even n digit numbers by breaking them into 2 halves like this where the 2 numbers are 10^n/2 * a + b and 10^n/2 * c + d a b X c d

The product is obtained by calculating 10^n * ac + 10^n/2 * [(a+b)(c+d) - ac - bd] + b*d

This is my code with commented explanations.

    def multiplication_algorithm(num1, num2):
        length1 = len(str(num1))
        length2 = len(str(num2))
        length = max(length1, length2)
        if length == 1:
            return num1 * num2 #simply returns product if single digit inputs are encountered
        num1_str = str(num1)
        num2_str = str(num2)
        num1_str = '0' * (length - length1) + num1_str #makes the length of both strings the same by adding zeros to the beginning
        num2_str = '0' * (length - length2) + num2_str
        if length % 2 != 0:
            num1_str = "0" + num1_str #makes the length of strings even so they can be symmetrically split
            num2_str = "0" + num2_str
        mid = length//2
        num1_first_half = int(num1_str[:mid]) #next 4 lines break the 2 numbers in 4 halves
        num1_second_half = int(num1_str[mid:])
        num2_first_half = int(num2_str[:mid])
        num2_second_half = int(num2_str[mid:])
        part1 = multiplication_algorithm(num1_first_half, num2_first_half)
        part3 = multiplication_algorithm(num1_second_half, num2_second_half)
        part2 = multiplication_algorithm(num1_first_half + num1_second_half, num2_first_half + num2_second_half) - part1 - part3
        return (10 ** length) * part1 + (10 ** mid) * part2 + part3

    import random
    s=set()
    for i in range(10): #generating 10 pairs of random numbers in given range to check algorithm
        number1 = random.randint(1,999)
        number2 = random.randint(1,99)
        if multiplication_algorithm(number1, number2) == number1 * number2:
            print("Success")
        else:
            print("Failure")

When I run this code with both number1 and number2 calculated using random.randint(1,99), this code works perfectly but when I run this code using number1=random.randint(1,99) and number2=random.randint(1,999) as above, the code fails and generates a recursion depth error. I have copy pasted the error text here:

    Traceback (most recent call last):
      File "C:/Users/anura/AppData/Local/Programs/Python/Python38-32/multalgo.py", line 29, in <module>
        if multiplication_algorithm(number1, number2) == number1 * number2:
      File "C:/Users/anura/AppData/Local/Programs/Python/Python38-32/multalgo.py", line 20, in multiplication_algorithm
        part3 = multiplication_algorithm(num1_second_half, num2_second_half)
      File "C:/Users/anura/AppData/Local/Programs/Python/Python38-32/multalgo.py", line 20, in multiplication_algorithm
        part3 = multiplication_algorithm(num1_second_half, num2_second_half)
      File "C:/Users/anura/AppData/Local/Programs/Python/Python38-32/multalgo.py", line 20, in multiplication_algorithm
        part3 = multiplication_algorithm(num1_second_half, num2_second_half)
      [Previous line repeated 1018 more times]
      File "C:/Users/anura/AppData/Local/Programs/Python/Python38-32/multalgo.py", line 19, in multiplication_algorithm
        part1 = multiplication_algorithm(num1_first_half, num2_first_half)
      File "C:/Users/anura/AppData/Local/Programs/Python/Python38-32/multalgo.py", line 4, in multiplication_algorithm
        length = max(length1, length2)
    RecursionError: maximum recursion depth exceeded in comparison

The number of recursions is far more than it ought to be and I don't understand where in the code that is happening.

Upvotes: 0

Views: 99

Answers (2)

Wups
Wups

Reputation: 2569

After you extend the string to have an even length, you calculate the mid using the old length.

if length % 2 != 0:
    num1_str = "0" + num1_str
    num2_str = "0" + num2_str
    length += 1    # <-- this was missing

mid = length//2

Upvotes: 1

Frank Yellin
Frank Yellin

Reputation: 11285

At least one problem is with 4-digit numbers. You divide them into two two-digit numbers. num1_first_half + num2_second might give a 3-digit number, when you then add a 0 to the beginning, putting you right back at four digits.

The Wikipedia page suggests stopping the recursion when length=4.

Upvotes: 0

Related Questions