Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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).
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.
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.
