Compute the exponent of the largest power of 2 that is less than $3^n$ efficiently

Question

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.

Answer 1

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?

Answer 2

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.

Answer 3

Hmm, just while I'm typing Matt gives the same idea. However, I don't want to waste the work of having typed this all, and at least here is it with a concrete example.

---

There is a very simple one. It makes use of the partial sums of the logarithmic series.

say, you've n=53 and look for m, such that $ \small 2^m<3^n<2*2^m $ . Then $ \small m = floor(n*log(3)/log(2)) $

So if we use an appropriate power series for log(3) and log(2), and evaluate successively to higher orders we will arrive at a value, where the floor-function does no more increase.
The given example works fast because the partial evaluations converge geometrically with the index

There is a powerseries for the logarithm, which also converges for x>2. This $$ \small f(x,k) = 2 \cdot ( {x-1\over x+1} + ({x-1\over x+1})^3{1 \over 3} + ({x-1\over x+1})^5 {1 \over 5} + \ldots +({x-1\over x+1})^{2 k+1} {1 \over 2*k+1 } ) $$ So we have by the partial evaluations

$$ \small \lim_{ k \to \infty} ps(k) = floor ( {f(3,k) \over f(2,k)} ) \text{ and } m(k)=n \cdot ps(k) $$ We arrive at m=84 at k=6

The evaluation of the powerseries is then with the terms for x=3: $ \small {x-1\over x+1} = {1 \over 2} \text{ and } ({x-1\over x+1})^2= {1 \over 4} $
and with the terms for x=2: $ \small {x-1\over x+1} = { 1 \over 3} \text{ and } ({x-1\over x+1})^2= {1 \over 9} $
then $$ \small \begin{array} {rllll} ps(1) &=& { 1/2 \over 1/3 } &=& {3 \over 2} = 1.5 \\ ps(2) &=& { 1/2 + 1/8/3 \over 1/3+1/27/3 } &=& { 13*81 \over 24*28 } \\ ps(3) &=& { 1/2 + 1/8/3 + 1/32/5 \over 1/3+1/27/3 +1/243/5 } &=& { \cdots \over \cdots } \\ \cdots& & \cdots \end{array} $$

Here is some Pari/GP-code:

m_by_n(n)=floor(log(3)/log(2)*n)

[n=53,m_by_n(n)]  \\ have a check for the true result

\\ initialize loop:
 k  = 1
 f3 = 1/2    f2 = 1/3
 s3 = f3     s2 = f2
 ps = 1.0*s3/s2       \\ this is the lower approximate of log(3)/log(2) 
 m_k = n * ps         \\ this is our approximate of n* log(3)/log(2)

\\ loop through the following until convergence 
 k++
 f3 /= 4             f2 /= 9
 s3 += f3/(2*k1-1)   s2 += f2/(2*k1-1)
 ps =  1.0*s3/s2
 m_k = n*ps 
  change_k = m_k -m_k1  
  m_k1     = m_k

         k   ps        m_k         change_k
------------------------------------------------------------ 
 %211 = [1, 1.5000000, 79.500000]
 %212 = [2, 1.5669643, 83.049107, 3.5491071]
 %213 = [3, 1.5812797, 83.807824, 0.75871649]
 %214 = [4, 1.5842020, 83.962707, 0.15488293]
 %215 = [5, 1.5848024, 83.994526, 0.031819453]
 %216 = [6, 1.5849281, 84.001190, 0.0066638762]
 %217 = [7, 1.5849550, 84.002614, 0.0014242816]
 %218 = [8, 1.5849608, 84.002924, 0.00031000195]
 %219 = [9, 1.5849621, 84.002993, 0.000068520789]

we could stop at k=6 because the change is smaller than the distance to the next greater integer but its rate of decrease is stronger than 1/2

It would be even more elegant if we had a second powerseries which approximates from above, and then stop iteration when there is only one integer in between (but I didn't give this much thought).

---

[update]

For n which provide m with a very good approximation (that means we use convergents of the continued fraction of $ \small \log(3)/ \log(2)) $ ) we need always most series terms. In http://go.helms-net.de/math/collatz/2hochS_3hochN_V2.htm I have a table with such convergents. For the highest n documented there ( n=22431534635635487631007267235817836787 ( 38 digits), log(n)~86.0035311129 ) the algorithm needs 120 series terms while for an "average" number in the near of that number the algo need about the half number of series terms. It is perhaps of interest, that the ratios series terms/log(n) are relatively constant along the sequences of best approximations (by continued fractions) as well as for sequences of "average" approximations, if I choose one random-number n . For the best approximations this is in the near of 1.4 (in the example 120/86.0 ) and for the average approximations it is in the near of 0.7 (or just the half of series terms are required).

[update 2] This update occurs long after the question is answered just for the cursory reader. I give a better Pari/GP-implementation so you can try it immediately with different values. Also I adapted the notation to my usual conventions.

\\ code for Pari/GP
SbyN(N)=floor(log(3)/log(2)*N)   \\ the reference value


{SbyN_part(N,maxit=150)=local(f3,f2,s3,s2,ps,m_k,change_k,m_k_prev);
 print(" ");           \\ print-cmds only for demo
 f3 = 1/2 ;   f2 = 1/3 ;
 s3 = f3  ;   s2 = f2;
 ps = 1.0*s3/s2  ;     \\ this is the lower approximate of log(3)/log(2) 
 m_k = N * ps   ;      \\ this is our approximate of n* log(3)/log(2)

\\ loop through the following until convergence 
 for(k=1,maxit,
        f3 /= 4 ;           f2 /= 9;
        s3 += f3/(2*k+1);   s2 += f2/(2*k+1);
        ps =  1.0*s3/s2 ;
                             m_k_prev  = m_k;
        m_k = N*ps ;
             change_k = m_k -m_k_prev  ;
             print([k, s2*1.0, s3*1.0, ps,
                     floor(m_k),min(frac(m_k),frac(m_k)-1),change_k]);
        if( frac(m_k) + change_k  < 1,break());
     );
 return(floor(m_k)); }

Try some interesting values which need either many or few iterations:

\p 200       \\ I work with 200 digits prec by default
[N1=41,m_by_n(N1),SbyN_part(N1)]
[N1=94,m_by_n(N1),SbyN_part(N1)]
[N1=253,m_by_n(N1),SbyN_part(N1)]
[N1=253+1,m_by_n(N1),SbyN_part(N1)]
[N1=190537,m_by_n(N1),SbyN_part(N1)]
[N1=190537+1,m_by_n(N1),SbyN_part(N1)]
[N1=22431534635635487631007267235817836787;m_by_n(N1);SbyN_part(N1)]
[N1=22431534635635487631007267235817836787+1;m_by_n(N1);SbyN_part(N1)]
[N1=22431534635635487631007267235817836787+2;m_by_n(N1);SbyN_part(N1)]