2
$\begingroup$

Suppose $N$ is $L$-bit long and $k$ is also $L$-bit long.

How to show that it takes at most O$(L^2)$ operations to compute it.

For example $N = 1010$ and $k = 10$. Then $N^k = 6^2 = 100100$. But I am not familiar with how $100100$ comes up without going back to decimal and using the fact that $6*6 = 36$. Therefore, I also find it hard to realize that it takes at most O$(L^2)$ operations to compute the powering of a number.

$\endgroup$
  • 1
    $\begingroup$ Before trying to understand how to compute powers, make sure that you thoroughly understand binary arithmetic. There is absolutely no need to convert to decimal in order to do arithmetic on binary numbers. I suggest reading a relevant textbook before trying to tackle your question. $\endgroup$ – Yuval Filmus Nov 3 '15 at 8:49
  • 1
    $\begingroup$ To emphasize the need for more precision in the statement of the question, note that $N^k$ can be nearly $L 2^L$ bits in size.... $\endgroup$ – Hurkyl Nov 4 '15 at 0:08
  • $\begingroup$ Keyword: repeated squaring. $\endgroup$ – David Richerby Nov 13 '15 at 8:20
4
$\begingroup$

It depends on what you mean by operations. If multiplication of unbounded numbers is considered one operation, then repeated squaring takes at most $2L$ operations. In that case we don't care about the size of $N$.

If we only consider multiplication of $L$-bit integers as a unit operation, then multiplying $ML$-bit integers takes $O(M^2)$ operations using the high-school algorithm (in fact, much better algorithms are known), and so repeated squaring, in which the integers have size $L,2L,4L,\ldots,2^LL$, takes $O(1^2 + 2^2 + \cdots + 2^{2L}) = O(2^{2L}L)$ operations. Using fancier multiplication algorithms that take $\tilde{O}(L)$ operations (if they exist in this setting) reduces the number of operations to $\tilde{O}(2^L)$.

$\endgroup$
  • $\begingroup$ Repeated squaring produces numbers of length $L, 2L, 4L, 8L, 16L, \ldots$. $\endgroup$ – Hurkyl Nov 4 '15 at 0:03

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.