Polynomial power expansion

The calculator expands n-th power of a given polynomial.

This simple calculator expands a given power of a single variable polynomial. To expand the n-th power of the polynomial, the calculator performs several multiplications using Polynomial multiplication. The calculator supports real, rational, or complex polynomial coefficients. The algorithm description is just below the calculator.

PLANETCALC, N-th power of polynomial

N-th power of polynomial

Problem
 
Result
 
Power tree
 

Polynomial exponentiation algorithm

A number of algorithms are known for power evaluation, which reduces the number of multiplications required to produce a given degree. One of the most optimal is the tree power algorithm described in The Art of Computer Programming vol 2 1. According to the pre-built power tree, the algorithm multiplies the resulting value by the values obtained in previous steps ( see the Power tree in the calculator result).

For example to obtain x23 it perform only 6 multiplications:

# operation result
1 x*x x2
2 x2 * x x3
3 x3 * x2 x5
4 x5 * x5 x10
5 x10 * x3 x13
6 x13 * x10 x23

An algorithm implementation may have a pre-build power tree up to some reasonable level, enough for most real-life applications.
To build the power tree, the following algorithm can be employed.

  • for each exponent value on the last tree-level do the following:
  • save exponent value to e variable
  • for each element in power tree chain pi (including e and all its parents up to 1), do the following
  • add a child element with pi + e power value if it does not already exist in the power tree

Binary power expansion algorithm

The binary power expansion algorithm is also remarkable for its simplicity. It has the same performance as the power tree algorithm up to power 22.

  • represent an exponent in binary form
  • produce an operation string by substitution all binary 1 with SX
  • substitute all binary 0 with X
  • remove first SX from the obtained operation string
  • staring from left to right iterate through the operation string
  • multiply the result by x for each 'X'
  • square result for each 'S'

The algorithm performs 7 multiplications to obtain x23. 23 is 10111 in binary form, so the operation string is SXXSXSXSX. The multiplication steps are in the following table:

code operation result
X x * x x2
S (x2 )2 x4
X x4 * x x5
S (x5 )2 x10
X x10 * x x11
S (x11 )2 x22
X x22 * x x23

  1. D.Knuth The Art of Computer Programming vol 2, par. 4.6.3 Polynomial arithmetics, Evaluation of powers 

URL copiado para a área de transferência
PLANETCALC, Polynomial power expansion

Comentários