Karatsuba Multiplication Javascript: Mastering Algorithms

Karatsuba Multiplication in JavaScript

Multiplication is a fundamental operation in mathematics and computer science. When dealing with large numbers, standard multiplication algorithms can be time-consuming. Enter Karatsuba multiplication: a fast multiplication algorithm that uses divide-and-conquer to reduce the number of basic multiplications required.

The algorithm is based on the observation that two n-digit numbers can be represented in the following way:

A = 10^(n/2) * x + y 
B = 10^(n/2) * z + w

Their product can be represented as:

A * B = 10^n * x * z + 10^(n/2) * (x * z + y * w) + y * w

However, instead of computing these three multiplications directly, the Karatsuba algorithm only requires the following three:

1. a1 = x * z
2. a2 = y * w
3. a3 = (x + y) * (z + w)

With these three multiplications, we can determine the result using:

A * B = 10^n * a1 + 10^(n/2) * (a3 — a1 — a2) + a2

Implementation in Modern JavaScript

Let’s translate the Karatsuba algorithm into JavaScript:

function karatsuba(x, y) {
    // Base case: if x or y is a single-digit number, return their product.
    if (x < 10 || y < 10) return x * y;

    // Determine the number of digits of the smaller number.
    const n = Math.min(String(x).length, String(y).length);
    // Calculate the position to split the number.
    const half = Math.floor(n / 2);

    // Split the numbers x and y.
    const [a, b] = splitAt(x, half);
    const [c, d] = splitAt(y, half);

    // Recursive multiplications using Karatsuba's approach.
    const ac = karatsuba(a, c);
    const bd = karatsuba(b, d);
    const abcd = karatsuba(a + b, c + d);

    // Combine the results to get the final product.
    return ac * 10 ** (2 * half) + (abcd - ac - bd) * 10 ** half + bd;
}

function splitAt(number, position) {
    // Convert the number to a string for easy splitting.
    const str = String(number);
    // Extract the left and right parts based on the given position.
    const left = Number(str.substring(0, str.length - position) || '0');
    const right = Number(str.substring(str.length - position));
    return [left, right];
}

// Example usage:
const result = karatsuba(1234, 5678);
console.log(result);  // Outputs: 7006652

In the above code:

• The karatsuba function is the core algorithm.
• The splitAt function breaks a number into two parts at a given position.

Example

Let’s understand the algorithm with the multiplication of 1234 and 5678.

1. Split 1234 into a=12 and b=34.
2. Split 5678 into c=56 and d=78.
3. Calculate a1 = 12 * 56 = 672.
4. Calculate a2 = 34 * 78 = 2652.
5. Calculate (a+b) * (c+d) = 46 * 134 = 6164.
6. The final result is calculated as 672 * 10⁴ + (6164–672–2652) * 10² + 2652 = 7006652.

The algorithm provides a recursive approach to multiplication, significantly decreasing the number of basic multiplications as the numbers grow large. This efficiency boost becomes evident with bigger number inputs.

In summary, the Karatsuba multiplication offers an elegant and efficient solution for multiplying large numbers, leveraging the power of the divide-and-conquer paradigm. With this JavaScript implementation, developers can harness this efficiency in modern applications.