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$
4
  • $\begingroup$ suggest migrating/ "promoting" this to Theoretical Computer Science $\endgroup$
    – vzn
    Nov 26, 2014 at 2:59
  • $\begingroup$ @vzn: I do not think this is useful... $\endgroup$
    – Bruno
    Nov 26, 2014 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, 2014 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, 2014 at 8:52

1 Answer 1

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$
3
  • 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, 2014 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, 2014 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, 2014 at 18:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.