How to calculate coefficients of polynomial expansion in javascript

Question

Suppose I have the following factors:

(1+3x)(1+x)(1+2x)

Expanded to a polynomial, it looks like:

1 + 6x + 11x^2 + 6x^3

The coefficients of this polynomial would be

c0 = 1
c1 = 6
c2 = 11
c3 = 6

I'm trying to figure out how to calculate these rapidly (for any set of factors). The ideal output would be an array of the coefficients, like

var coeff = [c0,c1,c2,c3];

What I'm trying to do is find a way to quickly go from the factors to the array of coefficients. Any suggestions on how to rapidly handle this in javascript? And for the sake of clarity, I'm trying to figure out how to do this for any set of n factors, not just this particular scenario.

Answer 1

You could use the factors as vector and use a cross product for the result.

function multiply(a1, a2) {
    var result = [];
    a1.forEach(function (a, i) {
        a2.forEach(function (b, j) {
            result[i + j] = (result[i + j] || 0) + a * b;
        });
    });
    return result;
}

var data = [[1, 3], [1, 1], [1, 2]], // (1+3x)(1+x)(1+2x)
    result = data.reduce(multiply);
    
console.log(result);                 // [1, 6, 11, 6] = 1x^0 + 6x^1 + 11x^2 + 6x^3

Answer 2

Well I found a method to do what you want from start to finish even without the need for any treatment in the original factors. Although I had to use a Math library. I found there is at least a library that does what you want: Nerdamer

As you can see from the code below the coeficients are correctly calculated from the factors you gave.

var factors = '(1+3x)(1+x)(1+2x)';
console.log('original factors: ' + factors);
var y = nerdamer('expand(' + factors + ')');
var polynomialform = y.toString();
console.log('polynomial form: ' + polynomialform);
var coef = polynomialform.split('+').map(v=>v.trim()).map(v=>v.split('x')[0]).map(v=>v.replace(/^\*+|\*+$/g, ''));
console.log('coeficients: ' + coef);

<script src="http://nerdamer.com/js/nerdamer.core.js"></script>

Notice that coefs var is an array.

Obviously, by the way I otained the coeficients, the operation may fail in different factor cases. This has to be adapted for minus characters and edge cases. You can create some kind of loop and put failed calculations in an array to check for edge cases to adapt the code for the full dataset. I can improve the answer if you provide a larger test dataset.

Hope it helps you.

Answer 3

Here's my take based on the fact that when you multiply (1+ax) by (1+b_1*x+b_2*x^2+...+b_nx^n), in the resulting polynomial (of degree n+1), the first term's coefficient will be one and its last term's coefficient will be a*b_n.

I think it is a bit simpler than the accepted answer, but still quadratic in time. To make this more efficient, you will need more advanced techniques.

function multOne(a, b) {
  var n = b.length;
  var r = [1];  //The first term is always 1
  r[n] = a * b[n - 1]; //The last term is always a*b_n-1
  for (var i = 1; i < n; i++)
    r[i] = b[i] + a * b[i - 1];
  return r;
}

function solve(c) {
  var result = [1, c[0]];  //use result as an accumulator
  for (var j = 1; j < c.length; j++)
    result = multOne(c[j], result);
  return result;
}

console.log(solve([3, 1, 2]));  //You don't need to pass 1s either. Just pass the varying coefficients

Answer 4

I needed something similar (to calculate permutations via exponential generating functions) so I wrote a version that works when some terms missing, by using objects as the base instead. I also needed it not not calculate anything over a certain power, so that's also an option

/**
 * Calculates the result of multiplying many polynomials together
 * @example 
 *   polynomials = [{0: 1, 1: 10, 2:1}, {0: 0, 1: 5, 2: 0, 3: 0.5}]
 *   limit = 4;
 *   polynomialMultiplication(polynomials, limit);
 * @param {Array.<Object.<number,number>>} polynomials an array of polynomials,
 * each expressed as an array of term coefficients
 * @param {number} limit the maximum term to calculate
 * @returns the resultant polynomial from multiplying all polynomials together
 */
function polynomialMultiplication(polynomials, limit) {
  const length = limit ?? polynomials.reduce((sum, poly) => sum += Math.max(...Object.keys(poly)), 0)
  // make an object to hold the result in
  // which is prepopulated by zeros
  const template = { ...Array.from({
      length
    }).fill(0)
  };
  return polynomials.reduce((memo, poly, polyIndex) => {
    const tempCopy = { ...template};
    if (polyIndex === 0) return { ...poly };
    for (let termIndex = 0; termIndex < length && termIndex <= Math.max(...Object.keys(poly)); termIndex++) {
      for (let memoIndex = 0;
        (memoIndex + termIndex) <= length && memoIndex <= Math.max(...Object.keys(memo)); memoIndex++) {
        const addition = (memo[memoIndex] ?? 0) * (poly[termIndex] ?? 0);
        const copyIndex = memoIndex + termIndex;
        tempCopy[copyIndex] = (tempCopy[copyIndex] ?? 0) + addition;
      }
    }
    return tempCopy;
  }, template)
}

console.log('(1+3x)(1+x)(1+2x)');
const polynomials = [{
  0: 1,
  1: 3
}, {
  0: 1,
  1: 1
}, {
  0: 1,
  1: 2
}];
console.log(polynomialMultiplication(polynomials));

const morePolynomials = [{
  0: 1,
  1: 0,
  2: 5
}, {
  0: 0,
  1: 6
}, {
  0: 1,
  1: 2,
  2: 0
}];
console.log('(1+5x^2)(6x)(1+2x) up to x^2')
console.log(polynomialMultiplication(morePolynomials, 2));