Karatsuba’s Multiplication

I am taking the Divide and Conquer, Sorting and Searching, and Randomized Algorithms course from Coursera. The problem assignment for week 1 is to implement the integer multiplication algorithm using Karatsuba’ multiplication method. As a result, you can multiply two 64-digit numbers:

Try multiply these two numbers you will get

It is the correct result, but it loses a lot of precision because the largest integer JavaScript can display is 2⁵³-1 (MDN).

To solve this problem, we could use Karatsuba’s algorithm and BigInt prosal from JavaScript T39 committee.

In Karatsuba’s algorithm, we recursively break down each integer in half until it is less than 10 which consists of one single digit. Then we multiply two single digits together. n is the number of digits for each integer.

Effectively, at each recursive call, the program will try to break each number into a, b, c, d to compute the multiplication based on the formula we have. Instead of truncating the result with a regular integer, BigInt has enough precision to display the complete result as

Hope you find it helpful!