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$
1

2 Answers 2

10
$\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$
1
  • $\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$ Mar 3, 2014 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$
1
  • $\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$ Mar 3, 2014 at 10:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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