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 the 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
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 prebuilt 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 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 a prebuild power tree up to some reasonable level, enough for most reallife applications.
To build the power tree, the following algorithm can be employed.
 for each exponent value on the last treelevel 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
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 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