Integer Multiplication

Input

• Two n digit numbers x and y.

Output

• $x * y$;product.

Algorithm Space

• In grade school we've been taught well defined set of rules to follow for integer multiplication.

• Time complexity analysis of grade-school algorithm:

  • Given number A with n digits, and number B with y digits, for each number in y, we multiply with n. Then we add the numbers together.

  • This gives us a total of $O(|A| * |B| + c)$

  • Or $O(n^2)$

Karatsubu Multiplication

• Algorithm is not exactly intuitive so I wont go through it.

• But the main idea is that the algorithm space is large, and there are different design methods to solve a problem.

• Can be optimized to remove one recursive call, and increase its running time performance.