<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>