## Algorithm to multiply very large numeric strings with 10k digits or more

0 / 217

Introduction and problem statement:

Multiply ultra large strings represented as numbers (numeric strings) with 10,000 or more characters in an optimal way. The strings may have all non zero numbers in them.

The numeric string sizes are between 1 to 20000.

Limitations and fast multiplication strategies:

The main issue here is none of the programming languages have primitive data types to handle numbers of this size, so we will have to store the numbers as strings and then process them character by character during atomic arithmetic operations to compute the final result. One of the fastest such multiplication algorithms is called “Karatsuba algorithm” named after a Russian mathematician Anatoly Karatsuba. It uses divide and conquer strategy to optimize the algorithm and obtain the result in fewer digit multiplications and hence additions.

Below is the explanation of the karatsuba algorithm taken from brilliant.org

The Karatsuba algorithm decreases the number of subproblems to three and ends up calculating the product of two -bit numbers in O(n log23) time–a vast improvement over the naive algorithm.

To multiply two n-bit numbers, x and y, the Karatsuba algorithm performs three multiplications and a few additions, and shifts on smaller numbers that are roughly half the size of the original x and y.

Here’s how the Karatsuba method works to multiply two n-bit numbers x and y which are in base b.

karatsuba explanation

Below are the javascript code snippets for different components of the algorithm with their respective explanations

<script>

function karatsuba(num1, num2) {
if (num1.length == 1 || num2.length == 1) {
// Step 1 - base simplest case if number is between 0 to 9
var s = multiply2(num1, num2);

return s
}

var old1 = num1,
old2 = num2

// Step 2 - calculate difference in size of numbers and pad leading zeroes to the shorter number
var diffLen = num1.length - num2.length
if (diffLen !== 0) {
if (diffLen < 0) {
diffLen = -1 * diffLen
} else {
}
}

// computation for dividing the numeric strings into smaller parts for karatsuba algorithm

// If the length of num1 or num2 is an odd number, then ensure that the length of a, c is greater than b, d
var len = num1.length;
var mid = len >> 1
mid = len % 2 == 1 ? mid + 1 : mid;
var a = num1.slice(0, mid)
var b = trimZero(num1.slice(mid))
var c = num2.slice(0, mid)
var d = trimZero(num2.slice(mid))

// recursive divide and conquer karatsuba algorithm call
var a_c = karatsuba(a, c);
var b_d = karatsuba(b, d);
var diff = subtract(subtract(ab_cd, a_c), b_d);
var s2 = pad(diff,  len-mid );
// Remove the zeroes padded to the string in the beginning on step 2
if (diffLen) {
s = s.slice(0, s.length - diffLen)
}

// console.log("karatsuba", old1, '*', old2, '=', s, s === old1 * old2 + "");
return s
}

function splitNumber(str) {
// If it is odd, then we have to add 1 to ensure that the value of the first element of the returned array is greater than
// Let's not return negative numbers in the following subtraction operation
var len = str.length;
var mid = len >> 1
mid = len % 2 == 1 ? mid + 1 : mid;
// The beginning of the second number may be zero, illegal hence slice that
return [str.slice(0, mid), trimZero(str.slice(mid)), len - mid];
}

// simple multiplication on smaller number strings that can be handled directly
function multiply2(num1, num2) {
if ("0" === num1 || "0" === num2) {
return "0";
}
if ("1" === num1) {
return num2;
}
if ("1" === num2) {
return num1;
}
var longNumber, shortNumber;
if (num1.length == 1) {
longNumber = num2;
shortNumber = num1 * 1;
} else {
longNumber = num1;
shortNumber = num2 * 1;
}
var ret = "",
carry = 0;
for (var i = longNumber.length - 1; i >= 0; i--) {
var num = longNumber[i] * 1
var temp = num * shortNumber + carry
ret = temp % 10 + '' + ret;
carry = Math.trunc(temp / 10);
}
if (carry > 0) {
ret = carry + '' + ret;
}
return ret;
}

if (num == "0") {
return num;
}
for (var i = 0; i < len; i++) {
num += "0";
}
return num;
}

// trim/ignore if string has a leading zero
function trimZero(str) {
while (str[0] === '0') {
str = str.slice(1)
}
return str || "0"
}

// addition - check if number string is negative may not be needed if numbers are positive only
if (num2[0] === '-') {
return subtract(num1, num2.slice(1))
}
var a, b;
if (num1.length >= num2.length) {
a = num1;
b = num2;
} else {
a = num2;
b = num1;
}

var ret = '',
carry = 0,
diff = a.length - b.length;
for (var i = a.length - 1; i >= 0; i--) {
var addend = a.charAt(i) * 1;
var adder = i - diff < 0 ? 0 : b.charAt(i - diff) * 1;
ret = temp % 10 + '' + ret;
carry = Math.trunc(temp / 10);
}
if (carry > 0) {
ret = carry + '' + ret;
}

return ret;
}

function subtract(num1, num2) {
// subtraction - check if number string is negative may not be needed if numbers are positive only
if (num2[0] === '-') {
}
if (num1[0] === '-') {
}
var len1 = num1.length;
var len2 = num2.length;
var negative = false;

if (num1 == num2) {
return "0";
}
var a = null, //bigNumber
b = null; //smallNumber

if (len1 > len2) {
a = num1;
b = num2;
} else if (len1 < len2) {
a = num2;
b = num1;
negative = true
} else {
for (var i = 0; i < len1; i++) {
if (num1[i] * 1 > num2[i] * 1) {
a = num1;
b = num2;
break;
} else if (num2[i] * 1 > num1[i] * 1) {
a = num2;
b = num1;
negative = true
break;
}
}
}
var carry = 0,
ret = '',
diff = a.length - b.length;
for (var i = a.length - 1; i >= 0; i--) {
var subtrahend = a.charAt(i) * 1;
var subtractor = i - diff < 0 ? 0 : b.charAt(i - diff) * 1;
var temp = subtrahend - subtractor - carry;
if (temp < 0) {
temp += 10;
carry = 1;
} else {
carry = 0;
}
ret = temp + '' + ret;
}
while (ret[0] === '0') {
ret = ret.slice(1)
}
ret = trimZero(ret)
if (negative) {
ret = '-' + ret;
}

return ret
}

document.write("Multiplication of large strings 123456789 & 987654321 = "+karatsuba('123456789', '987654321'));
</script>

The above algorithm works quite fast for large strings of about 10000-20000 digits, but still isn’t fast enough. The Schönhage–Strassen algorithm is faster than Karatsuba and we will cover this in another blog. Please give the above code a go on golibrary code playground at http://code.golibrary.co using numerous other large string multiplication examples.