10
$\begingroup$

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.

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

[edit] 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.

$\endgroup$
  • 1
    $\begingroup$ 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? $\endgroup$ – D.W. Jun 27 '14 at 16:54
  • $\begingroup$ @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? $\endgroup$ – Bruno Nov 26 '14 at 9:28
  • $\begingroup$ 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. $\endgroup$ – D.W. Nov 26 '14 at 18:07

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.