Function expandPower

src/compute-engine/boxed-expression/expand.ts:68–117

Use the multinomial theorem (https://en.wikipedia.org/wiki/Multinomial_theorem) to expand the expression. * The expression must be a power of a sum of terms. * The power must be a positive integer. * - expr = '(a + b)^2' * -> 'a^2 + 2ab + b^2' * - expr = '(a + b)^3' * -> 'a^3 + 3a^2b +

(base: Expression, exp: number)

 *    -> 'a^3 + 3a^2b + 3ab^2 + b^3'
 */

function expandPower(base: Expression, exp: number): Expression | null {
  const ce = base.engine;
  if (exp < 0) {
    const expr = expandPower(base, -exp);
    return expr ? expr.inv() : null;
  }
  if (exp === 0) return ce.One;
  if (exp === 1) return expand(base);
  if (isFunction(base, 'Negate')) {
    if (Number.isInteger(exp)) {
      const sign = exp % 2 === 0 ? 1 : -1;
      const result = expandPower(base.op1, exp);
      if (result === null) return null;
      return sign > 0 ? result : result.neg();
    }
  }

  // Subtract is non-canonical, so we don't expect to see it here.
  console.assert(base.operator !== 'Subtract');

  // We can expand only if the expression is a power of a sum.
  if (!isFunction(base, 'Add')) return null;

  // Apply the multinomial theorem
  // https://en.wikipedia.org/wiki/Multinomial_theorem
  // (a + b + c)^n = sum_{k1 + k2 + ... + km = n} (n choose k1, k2, ..., km) a^k1 b^k2 ... c^km
  // where the sum is over all non-negative integers k1, k2, ..., km such that k1 + k2 + ... + km = n
  // and (n choose k1, k2, ..., km) = n! / (k1! k2! ... km!)
  // For example, (a + b)^3 = (a + b)^2 (a + b) = (a^2 + 2ab + b^2) (a + b) = a^3 + 3a^2b + 3ab^2 + b^3
  // The multinomial theorem is a generalization of the binomial theorem.
  // For example, (a + b)^2 = a^2 + 2ab + b^2
  // (a + b + c)^2 = (a + b + c) (a + b + c) = a^2 + b^2 + c^2 + 2ab + 2ac + 2bc
  // (a + b + c)^3 = (a + b + c) (a + b + c) (a + b + c) = a^3 + b^3 + c^3 + 3a^2b + 3a^2c + 3b^2a + 3b^2c + 3c^2a + 3c^2b + 6abc

  const terms = base.ops;
  const it = powers(terms.length, exp);

  const result: Expression[] = [];
  const deadline = ce._deadline;
  let count = 0;
  for (const val of it) {
    // A high power of a sum enumerates a multinomial with `C(exp+m-1, m-1)`
    // terms — e.g. `(a+b+c)^350` is ~6·10⁴ — so this loop can run for many
    // seconds. Checkpoint the engine deadline (stride-amortized) so a runaway
    // expansion honors `ce.timeLimit` instead of stalling (e.g. the compiler's
    // symbolic-antiderivative attempt on `(trinomial)^p`).
    if ((++count & 0xff) === 0) checkDeadline(deadline);
    const product = [ce.number(multinomialCoefficient(val))];
    for (let i = 0; i < val.length; i += 1) {
      if (val[i] !== 0) {
        if (val[i] === 1) product.push(terms[i]);
        else product.push(terms[i].pow(val[i]));