TAOCP 4.6.3 Exercise 3
Let $M(n)$ denote the number of multiplications.
Section 4.6.3: Evaluation of Powers
Exercise 3. [**] [22] How is $2^{375}$ calculated by (a) the binary method? (b) the ternary method? (c) the quaternary method? (d) the factor method?
Verified: yes
Solve time: 4m11s
Let $M(n)$ denote the number of multiplications. We exhibit the actual computation in each method and count the multiplications required.
(a) Binary method
The binary expansion of $375$ is
$$ 375=(101110111)_2. $$
Algorithm A (binary exponentiation) maintains $YZ^N=2^{375}$, starting with
$$ Y=1,\qquad Z=2,\qquad N=375. $$
The successive values are:
$$ \begin{array}{c|c|c|c} N & \text{action} & Y & Z\ \hline 375\ (\text{odd}) & Y\leftarrow YZ,\ N\leftarrow374 &2&2\ 374 & Z\leftarrow Z^2,\ N\leftarrow187 &2&2^2\ 187\ (\text{odd}) & Y\leftarrow YZ,\ N\leftarrow186 &2^3&2^2\ 186 & Z\leftarrow Z^2,\ N\leftarrow93 &2^3&2^4\ 93\ (\text{odd}) & Y\leftarrow YZ,\ N\leftarrow92 &2^7&2^4\ 92 & Z\leftarrow Z^2,\ N\leftarrow46 &2^7&2^8\ 46 & Z\leftarrow Z^2,\ N\leftarrow23 &2^7&2^{16}\ 23\ (\text{odd}) & Y\leftarrow YZ,\ N\leftarrow22 &2^{23}&2^{16}\ 22 & Z\leftarrow Z^2,\ N\leftarrow11 &2^{23}&2^{32}\ 11\ (\text{odd}) & Y\leftarrow YZ,\ N\leftarrow10 &2^{55}&2^{32}\ 10 & Z\leftarrow Z^2,\ N\leftarrow5 &2^{55}&2^{64}\ 5\ (\text{odd}) & Y\leftarrow YZ,\ N\leftarrow4 &2^{119}&2^{64}\ 4 & Z\leftarrow Z^2,\ N\leftarrow2 &2^{119}&2^{128}\ 2 & Z\leftarrow Z^2,\ N\leftarrow1 &2^{119}&2^{256}\ 1\ (\text{odd}) & Y\leftarrow YZ,\ N\leftarrow0 &2^{375}&2^{256} \end{array} $$
The binary expansion contains
$$ \nu(375)=7 $$
ones, and
$$ \lfloor\log_2 375\rfloor=8. $$
Hence
$$ M(375)=8+7=15. $$
Thus the binary method uses 15 multiplications.
(b) Ternary method
The ternary expansion is
$$ 375=(111220)_3. $$
Using Horner's rule,
$$ 375=((((1)3+1)3+1)3+2)3+2)3. $$
Precompute
$$ 2^2, $$
which requires $1$ multiplication.
Now evaluate from the leading digit. Let $Y=2$.
For each succeeding ternary digit, cube $Y$ and multiply by $2^d$.
$$ \begin{aligned} Y&=2,\ Y&\leftarrow Y^3\cdot2=2^4,\ Y&\leftarrow Y^3\cdot2=2^{13},\ Y&\leftarrow Y^3\cdot2^2=2^{41},\ Y&\leftarrow Y^3\cdot2^2=2^{125},\ Y&\leftarrow Y^3=2^{375}. \end{aligned} $$
A cubing $Y^3$ requires $2$ multiplications:
$$ Y^2,\qquad Y^3=Y^2Y. $$
There are $5$ cubings, hence $10$ multiplications.
The nonzero digit multipliers after the leading digit are
$$ 1,1,2,2, $$
so $4$ further multiplications are required.
Including the one multiplication to precompute $2^2$,
$$ M(375)=1+10+4=15. $$
Thus the ternary method uses 15 multiplications.
(c) Quaternary method
The quaternary expansion is
$$ 375=(11313)_4. $$
Using Horner's rule,
$$ 375=((((1)4+1)4+3)4+1)4+3. $$
Precompute
$$ 2^2,\qquad 2^3, $$
requiring $2$ multiplications.
Start with $Y=2$.
For each succeeding digit, raise $Y$ to the fourth power and multiply by $2^d$.
$$ \begin{aligned} Y&=2,\ Y&\leftarrow Y^4\cdot2=2^5,\ Y&\leftarrow Y^4\cdot2^3=2^{23},\ Y&\leftarrow Y^4\cdot2=2^{93},\ Y&\leftarrow Y^4\cdot2^3=2^{375}. \end{aligned} $$
A fourth power requires $2$ multiplications:
$$ Y^2,\qquad Y^4=(Y^2)^2. $$
There are $4$ fourth powers, hence $8$ multiplications.
The four succeeding digits are all nonzero, so there are $4$ digit multiplications.
Therefore
$$ M(375)=2+8+4=14. $$
Thus the quaternary method uses 14 multiplications.
(d) Factor method
Factor
$$ 375=3\cdot5^3. $$
Compute powers according to this factorization.
First compute
$$ 2^5: \qquad 2^2,\ 2^4,\ 2^5, $$
requiring $3$ multiplications.
Next compute
$$ (2^5)^5=2^{25}, $$
again using the binary chain for exponent $5$:
$$ (2^5)^2,\quad (2^5)^4,\quad (2^5)^5, $$
requiring $3$ multiplications.
Then compute
$$ (2^{25})^5=2^{125}, $$
requiring another $3$ multiplications.
Finally compute
$$ (2^{125})^3=2^{375}, $$
via
$$ (2^{125})^2,\quad (2^{125})^3, $$
requiring $2$ multiplications.
Hence
$$ M(375)=3+3+3+2=11. $$
Thus the factor method uses 11 multiplications.
Therefore the computations require
$$ \boxed{ \begin{array}{c|c} \text{Method} & \text{Multiplications}\ \hline \text{Binary} & 15\ \text{Ternary} & 15\ \text{Quaternary} & 14\ \text{Factor} & 11 \end{array}} $$
and the factor method is the most economical of the four.