Polynomial power expansion

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.

N-th power of polynomial

Polynomial coefficients

Exponent

Calculation precision

Exact

Rounded

Digits after the decimal point: 2

Calculate

Problem

 

Result

 

Power tree

 

 Link  Save  Widget

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 ¹. 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 x²³ it perform only 6 multiplications:

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 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 is 10111 in binary form, so the operation string is SXXSXSXSX. The multiplication steps are in the following table: