# 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);

// calculate final result
};
``````

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.