# Computing the number of bits of a large power of integer

Given two integers $x$ and $n$ in binary representation, what is the complexity of computing the bit-size of $x^n$?

One way to do so is to compute $1+\lfloor \log_2(x^n)\rfloor=1+\lfloor n\log_2(x)\rfloor$ by computing an approximation of $\log_2(x)$ with sufficient precision. It appears that computing $\log_2(x)$ with $k$ bits of precisions can be done in $O(M(k)\log k)$ where $M(k)$ is the time needed to compute the product of two integers of length $k$. This yields a (not specially simple) algorithm of complexity approximately $O(s\log^2 s)$ if $s$ is a bound on the bitsize of both $x$ and $n$ (if I made no error).

Can we beat $O(s\log^2(s))$ where $s$ is the size of $x$ and $n$ (in the case where they have comparable sizes)? Is there a simple algorithm to get this complexity or better?

Note: I am interested in the complexity in a theoretical model such as Turing machines.

• suggest migrating/ "promoting" this to Theoretical Computer Science – vzn Nov 26 '14 at 2:59
• @vzn: I do not think this is useful... – Bruno Nov 26 '14 at 9:29
• why not? this question reminds me of algorithmic attacks on Dysons conjecture eg as covered by RJLipton in 1, 2 – vzn Nov 26 '14 at 22:48
• Simply because I found an answer to my question, so no need to ask it elsewhere to my mind. – Bruno Nov 27 '14 at 8:52

 As suggested, I edit my answer to give more details.

The answer to my second question is no:

Proposition. Computing $\log(x)$ up to precision $k$ is at least as hard as computing the bit-size of $x^{2^k}$.

Proof. Let $|y|$ denote the bit-size of an integer $y$. First notice that for a nonnegative integer $y$, the bit-size of $y$ is $1+\lfloor \log y\rfloor$.

Thus, $\left|x^{2^k}\right| = 1+\lfloor 2^k\log x\rfloor$. Now $2^k\log(x)$ is $\log(x)$ shifted $k$ positions to the left. Thus one can compute $\log(x)$ to precision $k$ by simply subtracting $1$ to the bit-size of $x^{2^k}$ and shifting the result $k$ positions to the right.

• Why does the number of bits in $x^{2^k}$ enable you to compute $\log x$ to $k$ bits of precision? Does your reduction actually work? What if the special case where $n=2^k$ was much easier/harder than all the other possible values of $n$ (non-powers-of-two)? Do you have a way to rule out that possibility? – D.W. Jun 27 '14 at 16:54
• @D.W.: I come back to this question, after vzn's comment. My proof is as follows: The number of bits of an integer $y$ is $1+\lfloor\log y\rfloor$. Thus, the number of bits in $x^{2^k}$ is $1+\lfloor 2^k\log x\rfloor$. Further, $2^k\log x$ is the same as $\log x$ but shifted $k$ positions to the left. Thus, $\lfloor 2^k\log x\rfloor$ gives you (at least) the $k$ first bits of $\log x$. Thus, if you can compute the number of bits of $x^{2^k}$, by subtracting $1$ to the result, you obtain the first $k$ bits of $\log x$. Does this make sense? – Bruno Nov 26 '14 at 9:28
• Yes, that makes more sense to me! Particularly since you're just trying to show hardness. May I encourage you to update your answer with this more detailed explanation? Thank you for coming back to this and documenting the answer to your own question. – D.W. Nov 26 '14 at 18:07