6
$\begingroup$

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).

$\endgroup$
11
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – user2357112 supports Monica Mar 3 '14 at 10:47
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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}$. $\endgroup$ – David Richerby Mar 3 '14 at 10:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.