Karatsuba Algorithm

This project implements the Karatsuba algorithm, a recursive method for multiplying large numbers more efficiently than the traditional approach. This was developed for the Foundations of Algorithm Design and Analysis course at the PUC Minas university, in the 5th period. My teacher is João Paulo Aramuni.

About

The Karatsuba algorithm is used by the system to perform fast multiplication on two n-digit numbers, i.e. the system compiler takes lesser time to compute the product than the time-taken by a normal multiplication.

Run

1. This project was developed in Python 3, so you need to have Python installed on your machine to run the code. You can follow this tutorial.

2. Clone this repository.

3. After that, to run the code, use the followind comand in the repository root:

python3 main.py

Structure

This repository contains two .py files:

• algorithm.py: Implements the Karatsuba multiplication algorithm.
• main.py: Contains the main function that runs the Karatsuba algorithm.

Explanation of the algorithm

Function Definition (algorithm.py)

def karatsuba(x, y):

• Defines the function karatsuba(x, y), which takes two numbers as input and returns their product using the Karatsuba multiplication method.

Base Case

    if x < 10 or y < 10:
        return x * y

• If either x or y is a single-digit number, the function directly returns their product.
• This serves as the base case for the recursion, stopping further breakdown of numbers.

Determining the Size of Numbers

    n = max(len(str(x)), len(str(y)))
    m = n // 2

• Converts x and y to strings to determine the number of digits.
• n stores the maximum number of digits between x and y.
• m represents half the size of the larger number, used for splitting.

Splitting the Numbers

    high_x, low_x = divmod(x, 10**m)
    high_y, low_y = divmod(y, 10**m)

• Uses divmod() to split both numbers into higher and lower parts based on m.
• This follows the principle:
  • x = high_x * 10^m + low_x
  • y = high_y * 10^m + low_y

Recursive Multiplications

    z0 = karatsuba(low_x, low_y)        
    z1 = karatsuba((low_x + high_x), (low_y + high_y)) 
    z2 = karatsuba(high_x, high_y)       

• Recursively computes three subproducts:
  1. z0 = karatsuba(low_x, low_y): Multiplication of the lower parts.
  2. z2 = karatsuba(high_x, high_y): Multiplication of the higher parts.
  3. z1 = karatsuba((low_x + high_x), (low_y + high_y)): Mixed multiplication of sum parts.

Combining the Results

   
    return (z2 * 10**(2*m)) + ((z1 - z2 - z0) * 10**m) + z0

• Uses the Karatsuba formula to reconstruct the final result:
  [ x \times y = (z2 \times 10^{2m}) + ((z1 - z2 - z0) \times 10^m) + z0 ]
• This efficiently calculates the product with fewer multiplications compared to the traditional method.

---

Main Function (main.py)

from algorithm import karatsuba

def main():
    
    num1 = int(input("Enter the first number: "))
    num2 = int(input("Enter the second number: "))

    result = karatsuba(num1, num2)

    print(f"The result of multiplying {num1} and {num2} using the Karatsuba algorithm is: {result}.")

if __name__ == "__main__":
    main()

Explanation

• Imports the karatsuba function from algorithm.py.
• Defines main(), which:
  1. Prompts the user to input two numbers.
  2. Calls the karatsuba function to compute their product.
  3. Prints the result in a formatted string.
• Runs main() when the script is executed.

Control flow graph

Source here.

Cyclomatic complexity

Using McCabe’s formula: M = E - N + 2P
E = 13, N = 11, P = 1
Cyclomatic Complexity (M) = 4

Asymptotic complexity

Case	Condition	Complexity
Best Case	One of the numbers is a single digit	O(1)
Average Case	Numbers of similar size, recursive splitting	O(n^{1.585})
Worst Case	Large numbers requiring full recursion depth	O(n^{1.585})

References

Knowing more about the Karatsuba Algorithm: Link1, Link2, Link3, Link4.

Understanding Python: Link1, Link2, Link3, Link4.