# How is this problem related to the study of algorithms and big O notation?

I'm taking a graduate computer science course on algorithms and analysis. The current subject is big O notation and recursion. How is the following problem related to the study of algorithms, recursion, and big O notation? I know and understand the solution to the problem, but I just don't see how this is relevant to the subject matter.

Given an $x$, show that $x^{62}$ can be computed with only eight multiplications (A general algorithm can not accomplish it).

## 2 Answers

You need to be more patient. This problem is hinting at the repeated squaring algorithm for powering. The more general question is: How long does it take to compute $x^n$? Naively, you might think that it takes $n$ multiplications, but the repeated squaring algorithm can do it using $O(\log n)$ multiplications.

Repeated squaring is very important for cryptographic applications. Many cryptographic algorithms rely on computing modular powers: $x^p \pmod{n}$, where in general $p$ and $n$ could be very large (say roughly $2^{1024}$). It makes a huge difference whether you do it in $O(p)$ or in $O(\log p)$ time.

• I'm not sure this is just hinting at exponentiation by squaring. After all, exponentiation by squaring takes 9 multiplications to do this, not 7. I think it's showing that exponentiation by squaring isn't quite optimal in terms of number of multiplications, and it's hinting at addition-chain exponentiation. – user2357112 supports Monica Mar 3 '14 at 10:47

let's first take x now:

 x^2 = x * x
x^4 = x^2 * x^2
x^8 = x^4 * x^4
x^16 = x^8 * x^8
x^32 = x^16 * x^16
x^64 = x^32 * x^32
x^62 = x^64 / x^2


Seems like you can do this in 7 steps actually if you use multiplication and division. The trick relies on the mathematical equation of $x^a*x^b=x^{(a+b)}$ and $x^a/x^b=x^{(a-b)}$. As such it shows that once can compute $x^n$ in $O(\log n)$ multiplications and divisions.

• Repeatedly doubling the exponent gets you to exponent $n$ after $i$ steps, where $i$ is the smallest integer such that $2^i\ge n$. That's $\log n$, not $\sqrt{n}$. – David Richerby Mar 3 '14 at 10:59