Algorithm X.1(a): Calculating $x$ raised to a non-negative integer power

Input: a real number $x$ and a non-negative integer $n$.
Output: a real number.

Describe an algorithm for calculating $x^n$ for an integer $n \ge 0$.

Algorithm X.1(b): Calculating $x$ raised to an integer power

Input: a real number $x$ and an integer $n$.
Output: a real number.

Describe an algorithm for calculating $x^n$ for an arbitrary integer $n$.

Efficient calculation of powers

Suppose you wanted to calculate $1.06^{57}$. You note that $57 = 2\cdot28 + 1$, and you know that $x^{57} = x^{2\cdot 28 + 1} = x^{2\cdot 28}\cdot x = (x^{28})^2\cdot x$. Thus, if you were able to calculate $x^28$, you need only square this number and multiply that result by $x$. In this case, suppose we determined that $1.06^{28} = 5.1116866971460040$, so $1.06^{57} = 5.1116866971460040^2 \cdot 1.06 = 27.6971013431661888$.

Now, how do you calculate $1.06^28$? You use the same approach: $28 = 2\cdot 14$, and $x^{28} = x^{2\cdot 14} = (x^{14})^2$, so if you can calculate $x^{14}$, you only need to square this result to find $x^{28}$.

Algorithm X.1: Calculating $x$ raised to an integer power

Input: a real number $x$ and an integer $n$.
Output: a real number.

Describe an algorithm for calculating $x^n$ for an arbitrary integer $n$ using this more efficient means of calculating powers.