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

0 / 217
karatsuba multiplication

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

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
            num1 = pad(num1, diffLen)
        } else {
            num2 = pad(num2, diffLen)
        }
    }
    
    // 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 ab_cd = karatsuba(add(a, b), add(c, d));
    var diff = subtract(subtract(ab_cd, a_c), b_d);
	// pad leading zeroes
    var s1 = pad(a_c,  (len-mid)*2);
    var s2 = pad(diff,  len-mid );
    var s = add(add(s1, s2), b_d);
    // 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;
}

// function to pad leading zeroes in numeric strings
function pad(num, len) {
    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"
}

function add(num1, num2) {
	// 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; 
        var temp = addend + adder + carry;
        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] === '-') {
        return add(num1, num2.slice(1))
    }
    if (num1[0] === '-') {
        return '-' + add(num1.slice(1), num2)
    }
    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.

 

Subscribe and follow Golibrary on Facebook and Linkedin to get all the updates.

 

Comments

comments


An avid reader, responsible for generating creative content ideas for golibrary.co. His interests include algorithms and programming languages. Blogging is a hobby and passion.

Related Posts