Karatsuba algorithm in JavaScript

karatsuba.js

function add(a, b) {
  a = a.toString();
  b = b.toString();
  const re = /^-/;
  if (re.test(a) && re.test(b)) {
    a = a.substring(1);
    b = a.substring(1);
  } else if(re.test(a)) {
    a = a.substring(1);
    return subtract(b, a);
  } else if (re.test(b)) {
    b = b.substring(1);
    return subtract(a, b);
  }
  const alen = a.length;
  const blen = b.length;
  if (alen < blen) {
    a = a.padStart(blen, '0');
  } else if (alen > blen) {
    b = b.padStart(alen, '0');
  }
  const len = a.length;
  let carry = false;
  let result = "";
  for (let i=len-1; i >=0; i--) {
    const augend = parseInt(a.substring(i, i+1), 10);
    const addend = parseInt(b.substring(i, i+1), 10);
    let sum = augend + addend;
    sum += carry ? 1 : 0;
    carry = false;
    if (sum > 9) {
      carry = true;
      sum -= 10;
    }
    result = sum.toString() + result;
  }

  if (carry) {
    result = "1" + result;
  }

  return result;
}

function subtract(a, b) {
  a = a.toString();
  b = b.toString();
  const re = /^-/;
  if (re.test(a) && re.test(b)) {
    a = a.substring(1);
    b = a.substring(1);
    return subtract(b, a);
  } else if(re.test(a)) {
    a = a.substring(1);
    return "-" + add(a, b);
  } else if (re.test(b)) {
    b = b.substring(1);
    return add(a, b);
  }
  const alen = a.length;
  const blen = b.length;
  if (alen < blen) {
    a = a.padStart(blen, '0');
  } else if (alen > blen) {
    b = b.padStart(alen, '0');
  }
  const len = a.length;
  let carry = false;
  let result = "";
  for (let i=len-1; i >=0; i--) {
    const augend = parseInt(a.substring(i, i+1), 10);
    const addend = parseInt(b.substring(i, i+1), 10);
    let sum = augend - addend;
    sum -= carry ? 1 : 0;
    carry = false;
    if (sum < 0) {
      carry = true;
      sum += 10;
    }
    result = sum.toString() + result;
  }

  if (carry) {
    return "-" + subtract(b, a);
  }

  return result;
}

function karatsuba(x, y) {
  let xstr = x.toString();
  let ystr = y.toString();
  const re = /^-/;
  let minus = '';
  if (re.test(xstr) && re.test(ystr)) {
    xstr = xstr.substring(1);
    ystr = ystr.substring(1);
  } else if(re.test(xstr)) {
    xstr = xstr.substring(1);
    minus = true;
  } else if (re.test(ystr)) {
    ystr = ystr.substring(1);
    minus = true;
  }
  const xlen = xstr.length;
  const ylen = ystr.length;
  if (xlen === 1 && ylen === 1) {
    return (x * y).toString();
  }
  if (xlen < ylen) {
    xstr = xstr.padStart(ylen, '0');
  } else if(xlen > ylen) {
    ystr = ystr.padStart(xlen, '0');
  }

  const len = xstr.length;
  const b = Math.ceil(len / 2);

  const x1 = xstr.slice(0, b);
  const x0 = xstr.slice(b);
  const y1 = ystr.slice(0, b);
  const y0 = ystr.slice(b);

  const z2 = karatsuba(x1, y1);
  const z0 = karatsuba(x0, y0);
  const z1 = subtract(add(z2, z0), karatsuba(subtract(x1, x0), subtract(y1, y0)));
  const z1Pad = len - b;
  const z2Pad = z1Pad * 2;

  let z = add(z2.padEnd(z2.length + z2Pad, '0'), add(z1.padEnd(z1.length + z1Pad, '0'), z0));
  z = z.replace(/^[0]+/, '');

  if (minus) {
    z = "-" + z;
  }

  return z;
}

(rev1) It might be inaccurate when the return value is over Number.MAX_SAFE_INTEGER

(rev2) In order to calculate over Number.MAX_SAFE_INTEGER, treat an integer as a string.