homechevron_rightStudychevron_rightMathchevron_rightAlgebra

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 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

There are number algorithms known for power evaluation, which reduce number of multiplications required to produce a given degree. One of most optimal is the tree power algorithm described in The Art of Computer Programming vol 2 1. The algorithm multiplies resulting value by the values obtained on previous steps according to pre-built power tree ( 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 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

Binary power expansion algorithm is also remarkable for its simplicity. It has the same to power tree algorithm performance 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 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 

Creative Commons Attribution/Share-Alike License 3.0 (Unported) PLANETCALC, Polynomial power expansion

Comments