polynomial multiplication

multiply.js

var LEFT = 0;
var RIGHT = 1;

function getZeros(length) {
  return (new Array(length)).join('a').split('a').map(function() { return 0; });
}

function padTo(array, length, direction) {
  var result = array.slice(0);
  var args = getZeros(length);

  if (array.length < length) {
    if (direction === LEFT) {
      args = getZeros(length - array.length + 2);
    } else {
      args = [array.length].concat(getZeros(length - array.length + 1));
    }

    result.splice.apply(result, args);    
  } else if (array.length > length) {
    result = result.slice(0, length);
  }

  return result;
}

function padWith(array, length) {
  var result = array.slice(0);
  var args = getZeros(length);

  return result.concat(args);
}

function multiplyPoly(a, b, n) {
  // base case: calculate
  if (n === 1) {
    return [a[0] * b[0]];
  }

  // recursive case
  var half = Math.ceil(n / 2);

  // padTo even number of terms
  a = padTo(a, half * 2, LEFT);
  b = padTo(b, half * 2, LEFT);

  // slice into equal halves
  var halves = [
    [
      a.slice(0, half),
      a.slice(half),
    ],
    [
      b.slice(0, half),
      b.slice(half),
    ]
  ];

  // different terms
  var terms = [
    padWith(multiplyPoly(halves[0][0], halves[1][0], half), half * 2),
    padWith(multiplyPoly(halves[0][0], halves[1][1], half), half),
    padWith(multiplyPoly(halves[0][1], halves[1][0], half), half),
    multiplyPoly(halves[0][1], halves[1][1], half),
  ];

  var length = terms[0].length;
  var result = [];

  for (var i = 0; i < length; i++) {
    result[length - 1 - i] = terms.reduce(function(total, curr) {
      return total + (curr[curr.length - 1 - i] || 0);
    }, 0);
  }

  // trim leading 0s
  while (result[0] === 0 && result.length) {
    result.splice(0, 1);
  }

  return result;
}