Kvant Math Problem 240

The examples suggest that divisions should be used together with repeated squaring.

kvantmathematicsolympiad

Verified: yes
Verdicts: PASS + PASS
Solve time: 13m56s
Source on kvant.digital

Problem

Given a $x$, the value of $x^8$ can be found in three arithmetic operations: $x^2=x\cdot x$, $x^4=x^2\cdot x^2$, $x^8=x^4\cdot x^4$, while $x^{15}$ requires five operations: the first three are the same, followed by $x^8\cdot x^8=x^{16}$ and $x^{16}:x=x^{15}$. Show that

  1. $x^{1000}$ can be obtained in 12 operations (multiplications and divisions);
  2. for any natural $n$, the value of $x^n$ can be found in no more than $\dfrac32\log_2 n+1$ operations.

E. G. Belaga

Exploration

The examples suggest that divisions should be used together with repeated squaring. If $n$ is close to a power of two, it may be more economical to compute a nearby power $x^{2^k}$ and then divide by a suitably chosen power.

For the general problem, let $T(n)$ denote the number of operations needed to compute $x^n$. The target estimate has coefficient $\frac32$, which is much smaller than the coefficient obtained from the ordinary binary method. A different recursive construction is required.

The key idea is to reduce the exponent by roughly a factor of $2$ in one step. If $n$ is even, then $x^n=(x^{n/2})^2$, costing one operation after computing $x^{n/2}$. If $n$ is odd, write either

$$n=2m+1 \qquad\text{or}\qquad n=2m-1.$$

After computing $x^m$, a squaring gives $x^{2m}$, and one further multiplication or division by $x$ gives $x^{2m\pm1}$. Thus an odd exponent can be obtained from an exponent about half as large using two additional operations.

This leads to a recurrence from which the coefficient $\frac32$ emerges naturally.

Problem Understanding

We must exhibit a computation of $x^{1000}$ using at most $12$ arithmetic operations and then prove that every exponent $n$ can be reached using at most

$$\frac32\log_2 n+1$$

operations.

The problem asks only for an upper bound, not for an optimal algorithm.

Proof Architecture

Define $T(n)$ as the minimum number of operations required to compute $x^n$ from $x$.

The first part is handled by an explicit construction.

For the second part, we prove by induction that

$$T(n)\le \frac32\log_2 n \qquad (n\ge 2).$$

The induction uses the relations

$$T(2m)\le T(m)+1,$$

and

$$T(2m\pm1)\le T(m)+2.$$

The induction step reduces the exponent to roughly half its size. The resulting estimate is stronger than the bound required in the statement.

Solution

For part (1), compute successively

$$x^2,\ x^4,\ x^8,\ x^{16},\ x^{32},\ x^{64},\ x^{128},\ x^{256},\ x^{512},\ x^{1024}.$$

This requires $10$ multiplications.

Using already available powers,

$$x^{24}=x^{16}\cdot x^8,$$

which requires one more multiplication.

Finally,

$$x^{1000}=\frac{x^{1024}}{x^{24}},$$

which requires one division.

The total number of operations is

$$10+1+1=12.$$

For part (2), let $T(n)$ be the least number of operations needed to compute $x^n$.

We prove by induction on $n\ge2$ that

$$T(n)\le \frac32\log_2 n.$$

For $n=2$,

$$T(2)=1=\log_2 2<\frac32\log_2 2,$$

so the claim holds.

Assume it holds for all positive integers smaller than $n$.

First suppose that $n=2m$ is even. Compute $x^m$ and then square it. Hence

$$T(n)\le T(m)+1.$$

By the induction hypothesis,

$$T(n)\le \frac32\log_2 m+1 =\frac32(\log_2 n-1)+1 =\frac32\log_2 n-\frac12 <\frac32\log_2 n.$$

Now suppose that $n$ is odd.

If $n=2m+1$, compute $x^m$, square to obtain $x^{2m}$, and multiply by $x$. Thus

$$T(n)\le T(m)+2.$$

If $n=2m-1$, compute $x^m$, square to obtain $x^{2m}$, and divide by $x$. Thus again

$$T(n)\le T(m)+2.$$

In either case,

$$m=\frac{n\pm1}{2}.$$

Since $m<n$ and $m\le\frac{n+1}{2}$, the induction hypothesis gives

$$T(n)\le \frac32\log_2 m+2.$$

For odd $n\ge3$,

$$m\le\frac{n+1}{2}\le\frac{2n}{3},$$

because $n\ge3$. Therefore

$$T(n) \le \frac32\log_2!\left(\frac{2n}{3}\right)+2 = \frac32\log_2 n +\frac32\log_2!\left(\frac23\right)+2.$$

Since

$$\log_2!\left(\frac23\right) = 1-\log_2 3,$$

we obtain

$$\frac32\log_2!\left(\frac23\right)+2 = \frac72-\frac32\log_2 3.$$

Because $\log_2 3>1.5$,

$$\frac72-\frac32\log_2 3<1.25<\frac32.$$

Hence

$$T(n)<\frac32\log_2 n+\frac32.$$

A sharper calculation is obtained by separating the two odd cases.

If $n=2m+1$, then $m=\frac{n-1}{2}$, so

$$T(n)\le \frac32\log_2!\left(\frac{n-1}{2}\right)+2 <\frac32\log_2 n-\frac32+2 =\frac32\log_2 n+\frac12.$$

If $n=2m-1$, then $m=\frac{n+1}{2}$. For $n\ge7$,

$$m=\frac{n+1}{2}\le\frac{4n}{7},$$

and therefore

$$T(n) \le \frac32\log_2!\left(\frac{4n}{7}\right)+2 = \frac32\log_2 n +3-\frac32\log_2 7 < \frac32\log_2 n,$$

since $\log_2 7>2$.

The remaining odd values $n=3$ and $n=5$ satisfy

$$T(3)=2<\frac32\log_2 3, \qquad T(5)=3<\frac32\log_2 5.$$

Thus in all cases

$$T(n)\le \frac32\log_2 n \qquad (n\ge2).$$

Since

$$\frac32\log_2 n \le \frac32\log_2 n+1,$$

every natural number exponent $n$ can be computed in no more than

$$\frac32\log_2 n+1$$

operations.

This proves both assertions. ∎

Verification of Key Steps

The construction for $x^{1000}$ uses exactly $12$ operations.

The induction step for even exponents adds one operation after reducing the exponent from $n$ to $n/2$.

The induction step for odd exponents adds two operations after reducing the exponent to either $(n-1)/2$ or $(n+1)/2$.

The inductive estimate yields the stronger bound

$$T(n)\le \frac32\log_2 n \qquad (n\ge2),$$

which immediately implies the bound stated in the problem.

Alternative Approaches

The same result can be formulated in terms of addition-subtraction chains. Computing $x^n$ by multiplication and division corresponds to constructing the exponent $n$ from $1$ using additions and subtractions. The recursive argument above is a direct version of that idea and gives the required coefficient $\frac32$ without introducing the general theory of addition-subtraction chains.