TAOCP 4.6.3 Exercise 25

Let y=(.

taocpmathematicsalgorithmsvolume-2medium

Section 4.6.3: Evaluation of Powers

Exercise 25. [20] Let $y$ be a fraction, $0 < y < 1$, expressed in the binary number system as $y = (.d_1 \ldots d_k)_2$. Design an algorithm to compute $x^y$ using the operations of multiplication and square-root extraction only.

Verified: yes
Solve time: 1m26s

Solution

Let

$$ y=(.d_1d_2\cdots d_k)_2, \qquad d_j\in{0,1}, $$

so that

$$ y=\sum_{j=1}^{k} d_j2^{-j}. $$

Define

$$ r_j=x^{(.d_1d_2\cdots d_j)_2}, \qquad 1\le j\le k. $$

Since

$$ (.d_1d_2\cdots d_j)2 = \frac12(.d_1d_2\cdots d{j-1})_2+\frac{d_j}{2}, $$

we have

$$ r_j = x^{\frac12(.d_1d_2\cdots d_{j-1})2} x^{d_j/2} = \sqrt{r{j-1}},( \sqrt{x})^{,d_j}. $$

This recurrence suggests a left-to-right analogue of the binary method.

Let

$$ S=\sqrt{x}. $$

Initialize

$$ R= \begin{cases} S,&d_1=1,\[2mm] 1,&d_1=0. \end{cases} $$

For $j=2,3,\ldots,k$, perform:

  1. Replace $R$ by $\sqrt{R}$.
  2. If $d_j=1$, replace $R$ by $RS$.

After the $j$th digit has been processed, induction on $j$ shows that

$$ R=x^{(.d_1d_2\cdots d_j)_2}. $$

For $j=1$ the claim holds by initialization. If it holds for $j-1$, then after taking a square root,

$$ R=x^{\frac12(.d_1d_2\cdots d_{j-1})_2}, $$

and multiplication by $S=x^{1/2}$ when $d_j=1$ gives

$$ R = x^{\frac12(.d_1d_2\cdots d_{j-1})_2+d_j/2} = x^{(.d_1d_2\cdots d_j)_2}. $$

If $d_j=0$, the same formula holds without the multiplication.

After the final digit $d_k$ has been processed,

$$ R=x^{(.d_1d_2\cdots d_k)_2}=x^y. $$

Hence the algorithm computes $x^y$ using only multiplication and square-root extraction.

In compact form:

$$ \begin{aligned} &\text{Set }S\leftarrow\sqrt{x},\ &R\leftarrow \begin{cases} S,&d_1=1,\ 1,&d_1=0; \end{cases}\ &\text{for }j=2,\ldots,k:\ &\qquad R\leftarrow\sqrt{R};\ &\qquad\text{if }d_j=1,\ \ R\leftarrow RS;\ &\text{output }R. \end{aligned} $$

The result is $R=x^y$.

$$ \boxed{x^y} $$