Polynomial power expansion
The calculator expands nth power of a given polynomial.
This simple calculator expands a given power of a single variable polynomial. To expand nth 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.
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 prebuilt power tree ( see the Power tree in the calculator result).
For example to obtain x^{23} it perform only 6 multiplications:
#  operation  result 

1  x*x  x^{2} 
2  x^{2} * x  x^{3} 
3  x^{3} * x^{2}  x^{5} 
4  x^{5} * x^{5}  x^{10} 
5  x^{10} * x^{3}  x^{13} 
6  x^{13} * x^{10}  x^{23} 
An algorithm implementation may have prebuild 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 p_{i}, (including e and all its parents up to 1) do the following
 add a child element with p_{i} + 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 x^{23}. 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  x^{2} 
S  (x^{2} )^{2}  x^{4} 
X  x^{4} * x  x^{5} 
S  (x^{5} )^{2}  x^{10} 
X  x^{10} * x  x^{11} 
S  (x^{11} )^{2}  x^{22} 
X  x^{22} * x  x^{23} 

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