Compute the exponent of the largest power of 2 that is less than $3^n$ efficiently Per the title, what is the fastest way to compute exactly the exponent $m$ of the largest power of 2 such that $2^m < 3^n$? Is it possible to do this in time that is sub-linear in the value of $n$?
I'm wondering if there's a way that is better than simply computing $3^n$ and counting the number of bits in the resulting number.
 A: As others have noted the problem is equivalent to calculating $\log_23=1/\log_32$ accurately enough. A problematic case may occur when $n\log_23$ is very close to an integer, because then you may need to increase the precision to unexpected heights. I don't know how to do that, but one of the authors of 

"Hirvensalo and Karhumäki. Computing partial information out of intractable one - the first (ternary) digit of $2^n$ at base $3$ as an example. In Mathematical foundations of computer science 2002, volume 2420 of Lecture Notes in Computer Science, pp. 319-327" 

confided to me that they managed to do exactly this in order to solve their problem (described in the title of the paper). May be their technique will help you also?
A: First, please observe that $m=\lfloor\frac{\log_e{3}}{\log_e{2}}n\rfloor$, as @anon states.
So if we calculate these two logarithms and apply the function above, we are done.
The series expansion of logarithms can be obtained using 
$\log_e{\frac{1+x}{1-x}}$ = $2\left(x + \frac{x^3}{3} + \frac{x^5}{5} + \dots + \frac{x^{2n+1}}{2n+1} + \dots\right)$ $, |x| < 1$
Observe (perhaps again) that we are looking for $\log_e{3}$ and $\log_e{2}$.  We can estimate these by using the first $O(\log n)$ terms for each series.  There are at most $O(\log n)$ multiplies for each element of the series.  Say that arithmetic operations like multiplication and division take time $f(n)$.  Then we can calculate each logarithm in time $O(\log{n}\log{n}f(x))$.
Let's observe now that that is the running time.  We first calculate $x$ in order to get the algorithms by solving:
$\frac{1+x}{1-x}=c$ where $c$ is either two or three.  This can obviously be done faster than actually taking the logarithm, and the solution is $x = \frac{c-1}{1+c}$.  Now we can plug the value into the logarithm equations, which is the most time consuming portion of the algorithm.  Finally, we solve the original logarithmic equation for $m$.  It's obvious that this doesn't take the most time.  So we are done.
This should be accurate, and therefore, once again, takes time $O(\log{n}\log{n}f(x))$, where $f(x)$ is the time for arithmetic operations on an $x$ bit number.
For small numbers, we can use a lookup table, and this will ensure faster than $O(n)$ time.
