1-Karatsuba-Multiplication

README

Karatsuba Multiplication

Complexity Analysis:

• Time complexity: O(n^{log₂ 3}).
• Space complexity: O(n).

Programming Assignment #1

In this programming assignment you will implement one or more of the integer multiplication algorithms described in lecture.

To get the most out of this assignment, your program should restrict itself to multiplying only pairs of single-digit numbers. You can implement the grade-school algorithm if you want, but to get the most out of the assignment you'll want to implement recursive integer multiplication and/or Karatsuba's algorithm.

So: what's the product of the following two 64-digit numbers?

Input

The file has two lines, each with a different number. For example:

5
4

Output

The output must be the integer multiplication of the two numbers from the input file. For example:

20