Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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

share|improve this question

2 Answers 2

up vote 11 down vote accepted

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.

share|improve this answer
    
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 Mar 3 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.

share|improve this answer
    
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 at 10:59

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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