Problem Detail: 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).
Asked By : Elliott
Answered By : Yuval Filmus
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.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/22200
