11
$\begingroup$

I'm seeking an efficient algorithm for the problem:

Input: The positive integer $3^n$ (stored as bits) for some integer $n \geq 0$.

Output: The number $n$.

Question: Can we compute $n$ from the bits of $3^n$ in $O(n)$ time?


This is a theoretical question motivated by my answer to a math.SE question How to find a formula for this bijection?. In this question, the author wanted to find a bijection from $$\{2^n 3^m: n \geq 0 \text{ and } m \geq 0\}$$ and the natural numbers $\mathbb{N}=\{1,2,\ldots\}$. I proposed $$2^m 3^n \mapsto 2^m(2n+1)$$ as a solution. Another answer there asserted "there is no simple formula", which makes me wonder how (computationally) simple my proposed solution is.

With my proposed solution, if we know $n$ and $m$, we can easily compute $2^m(2n+1)$ (write the binary digits of $n$ followed by $1$ followed by $m$ zeroes). This takes $O(n+m)$ time.

Finding $m$ from the bits of $2^m 3^n$ amounts to finding the least significant bit (which can be computed by counting right bit shifts, leaving $3^n$ in memory). This takes $O(m)$ time.

However, we also need to find $n$, which might be more difficult. It would be possible to find $n$ by repeatedly dividing by $3$, but this seems wasteful. It requires $n$ division operations, each of which will take $O(n)$ time, so this is $O(n^2)$ time in total. [Actually, the after each iteration, the number of digits will decrease linearly, but this still results in $O(n^2)$ time.]

It seems like we should be able to exploit knowing the input is a power of $3$.

$\endgroup$
  • 2
    $\begingroup$ What is your exact model of computations? What operations are allowed in $O(1)$ time? (If we could do arithmetic with numbers such as $\log_2 3$ it would be quite useful...) $\endgroup$ – Yuval Filmus Sep 13 '13 at 17:37
  • 3
    $\begingroup$ Can the downvoter explain the downvote? It doesn't seem like a trivial question at all. What is the best running time under some reasonable computation model? $\endgroup$ – Yuval Filmus Sep 13 '13 at 17:40
  • 1
    $\begingroup$ I'm imagining tapes with 0's, 1's and empty cells (with an infinite number of tapes). I want single bit toggling and left/right shifting operations to run in $O(1)$ time. (If we have a marker the 0-th bit on an infinite tape, then left/right shifting is achieved by shifting the marker). Unlike a Turing machine, I don't want it to take any time to move a pointer. So "toggle the 0-th bit" takes the same time as "toggle the 124126-th bit". $\endgroup$ – Rebecca J. Stones Sep 13 '13 at 17:56
  • $\begingroup$ It might be somehow related to this question $\endgroup$ – J.-E. Pin Sep 13 '13 at 20:45
  • $\begingroup$ Is the lower bound of $\Omega(n)$ obvious? $\endgroup$ – Boris Bukh Sep 13 '13 at 23:07
9
$\begingroup$

The obvious approach is:

(1) Compute an approximation to $\log_2(3^n)$. You can approximate it to within an additive error of 1 by counting the number of bits in the given binary representation, and to within an additive error of $\epsilon$ by additionally looking at the top $O(\log\frac{1}{\epsilon})$ bits of the input. It should suffice to choose a constant value of $\epsilon$, so that (after combining with the error in step (2)) the final result ends up within an additive error of $1/2$ of correct.

(2) Compute an approximation to $\log_2(3)$. I'm not familiar with the algorithms for this but I expect they take time polynomial in the number of bits of precision you need, and you only need $O(\log n)$ bits of precision.

(3) Divide the answer to (1) by the answer to (2), and round to the nearest integer.

So the first step takes linear time (in most models of computation although maybe not for some underpowered ones like single-head Turing machines) and the remaining steps should be polylogarithmic.

$\endgroup$
  • 3
    $\begingroup$ I believe that computing $\log_2(3)$ to $t$ bits of precision takes time $O(M(t) \log t)$, where $M(t) \leq O(t \log t 2^{\log^* t})$ is the time to multiply $t$-bit numbers. See Brent--Zimmermann, loria.fr/~zimmerma/mca/pub226.html $\endgroup$ – Ryan O'Donnell Sep 18 '13 at 1:20
  • $\begingroup$ Thanks for the reference, and apologies for being too lazy to look it up myself. $\endgroup$ – David Eppstein Sep 18 '13 at 5:41
9
$\begingroup$

For any integer $n>0$, writing $3^n$ in binary requires exactly $L = \lceil \log_2(3^n)+1\rceil$ bits. Some elementary algebra implies that $$ \frac{L-2}{\log_2 3} \le n \le \frac{L-1}{\log_2 3}. $$ For any bit length $L\ge 1$, there is at most one integer in this range. Thus, given an integral power of $3$ that is $L$ bits long, the exponent must be the integer $$ n = \left\lfloor\frac{L-1}{\log_2 3}\right\rfloor. $$

$\endgroup$
4
$\begingroup$

Here is another approach. Given the low $k$ digits of $3^n$, you can learn $3^n \bmod 10^k$ and thus $3^n \bmod 5^k$. It looks like $3$ is a generator modulo $5^k$ (i.e., $3$ has order $\varphi(5^k)=5^{k-1} \times 4$).

Therefore, by using discrete log and Hensel lifting, I think you should be able to compute $n \bmod \varphi(5^k)$ from the low $k$ digits of $3^n$ very efficiently. In other words, you start by computing $n \bmod 4$ from the low digit of $3^n$, by taking the discrete log of $3^n \bmod 5$ to the base $3$, modulo $5$; this reveals $n \bmod 4$, and can be done in $O(1)$ time. Then, you find the discrete log of $3^n \bmod 25$ to the base $e$, modulo $25$; this reveals $n \bmod 20$, and can be done in $O(1)$ time (taking advantage of the knowledge of $n \bmod 4$, there are only $5$ possibilities you have to try). Iterate. At each step, you use the knowledge of $n \bmod \varphi(5^{k-1})$ to help you efficiently compute the discrete log of $3^n \bmod 5^k$, making use of the fact that there are only $5$ possible values for $n \bmod \varphi(5^k)$.

Now just let $k$ be large enough, and this reveals $n$.

You'll need to work out whether the running time is $O(n)$, but it looks to me like it might be. I suspect it's enough to let $k=O(n)$, and I suspect you can do each iteration in $O(1)$ time, for a total of $O(n)$ time.

$\endgroup$

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.