Karatsuba Algorithm

The Karatsuba algorithm is a fast multiplication algorithm. It use the divide and conquer techinque to speed up the multiplication process. In this article, let's dig into its details to see how it works.

Say we want to multiply 2 number: x and y.

The first step is to split each number into 2 half. For example, 12345 can be split into 123 and 45 and expressed as 123 * 100 + 45. So, in this way, we can express the x and y in below. n is the max length between x and y.

x = a * 10^(n/2) + b
y = c * 10^(n/2) + d

Now let's try to multiply these 2 parts.

x * y
  = (a * 10^(n/2) + b) * (c * 10 ^(n/2) + d)
  = (a * 10^(n/2)) * (c * 10 ^(n/2)) + ad*(10^(n/2)) + bc*(10^(n/2)) + bd
  = ac * 10^(2*(n/2)) + (ad + bc)*10^(n/2) + bd

So to get the result of x * y, we need to get ac, bd and ad+bc first.

And ad+bc can be expressed as:

ad + bc = (a + b)*(c + d) - ac - bd

So, in the end, what we only need to know is ac and bd.

Now, how can we get ac and bd? Well, since it is still multiplication, we can calculate these using the same process recursively, until we find x or y is 1 digit number, then we can stop the recursion and do the multiplication in the normal way.

As you can see, this whole process is what the divide and conquer means. Big x and y are divided into small a,b,c,d, which can be divided recursively further.

With all this in mind, let see them in code.

function multiply(x: string, y: string): string {
    if (x.length === 0) return y;
    if (y.length === 0) return x;

    // 1 digit number, use normal multiply
    if (x.length === 1) return singleMultiply(y, x);
    if (y.length === 1) return singleMultiply(x, y);

    // divide each into 2 parts
    const half = Math.floor(Math.max(x.toString().length, y.toString().length) / 2);

    const xMid = x.length - half;
    const a = xMid <= 0 ? "0" : x.slice(0, xMid);
    const b = x.slice(xMid < 0 ? 0 : xMid);

    const yMid = y.length - half;
    const c = yMid <= 0 ? "0" : y.slice(0, yMid);
    const d = y.slice(yMid < 0 ? 0 : yMid);

    // calculate key elements
    const ac = multiply(a, c);
    const bd = multiply(b, d);
    const ad_plus_bc = subtract(subtract(multiply(add(a, b), add(c, d)), ac), bd);

    // calculate final result
    return add(add(pow10(ac, 2 * half), pow10(ad_plus_bc, half)), bd);
};

Since I want to avoid converting input number string into number directly, so I prepare the string version of add, subtract and pow10 functions, which use the standard operations we learn from elementary school to do each operations.

// x * 10^y
function pow10(x: string, y: number): string {
    while (y-- > 0) {
        x += "0";
    }
    return x;
}

// y: 1 digit
function singleMultiply(x: string, y: string): string {
    const res: number[] = [];
    let carry = 0;
    const base = "0".charCodeAt(0);
    const yv = y.charCodeAt(0) - base;
    for (let i = x.length - 1; i >= 0; i--) {
        const v = (x.charCodeAt(i) - base) * yv + carry;
        res.push(v % 10);
        carry = Math.trunc(v / 10);
    }
    if (carry > 0) {
        res.push(carry);
    }
    res.reverse();
    return trimStart0(res.join(""));
}

function add(x: string, y: string): string {
    const res: number[] = [];
    let carry = 0;
    const base = "0".charCodeAt(0);
    for (let i = x.length - 1, j = y.length - 1; i >= 0 || j >= 0; i--, j--) {
        const v1 = i >= 0 ? x.charCodeAt(i) - base : 0;
        const v2 = j >= 0 ? y.charCodeAt(j) - base : 0;
        const v = v1 + v2 + carry;
        res.push(v % 10);
        carry = Math.trunc(v / 10);
    }
    if (carry > 0) {
        res.push(carry);
    }
    res.reverse();
    return res.join("");
}

// value of x >= value of y
function subtract(x: string, y: string): string {
    const res: number[] = [];
    let carry = 0;
    const base = "0".charCodeAt(0);
    for (let i = x.length - 1, j = y.length - 1; i >= 0 || j >= 0; i--, j--) {
        const v1 = i >= 0 ? x.charCodeAt(i) - base : 0;
        const v2 = j >= 0 ? y.charCodeAt(j) - base : 0;
        const v = v1 - v2 - carry;
        res.push(v < 0 ? v + 10 : v);
        carry = v < 0 ? 1 : 0;
    }
    if (carry > 0) {
        res.push(carry);
    }
    res.reverse();
    return trimStart0(res.join(""));
}

function trimStart0(x: string): string {
    return x.replace(/^0+(?=\d)/, "");
}

In the end, don't forget to use the leetcode problem Multiply Strings to test the code.