9
$\begingroup$

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.

$\endgroup$
8
  • 7
    $\begingroup$ $m=\lfloor\frac{\log3}{\log2}n\rfloor$, using the base change constant to whatever degree of accuracy necessary. $\endgroup$
    – anon
    Aug 24, 2011 at 22:11
  • 2
    $\begingroup$ By repeated squaring, you can compute $3^n$ in about $2\log_2 n$ multiplies, which is already sub-linear. $\endgroup$ Aug 24, 2011 at 22:15
  • 2
    $\begingroup$ Both of these ideas still require $\Omega(n)$ time. Note that the final repeated squaring alone requires $\Omega(n \lg n)$ time because of the size of the numbers involved. For the logarithm idea, you still need a lot of precision to get the exact answer. $\endgroup$
    – jonderry
    Aug 24, 2011 at 22:59
  • 1
    $\begingroup$ @Jonderry: Representing the largest power of $2$ which is less than $3^n$ requires $\Omega(n)$ bits. So I don't see how you can do better, unless you mess with the representation... $\endgroup$
    – Aryabhata
    Aug 24, 2011 at 23:11
  • 2
    $\begingroup$ @jonderry: I see. Perhaps you should clarify it a bit in the question... $\endgroup$
    – Aryabhata
    Aug 24, 2011 at 23:33

3 Answers 3

4
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ The $\log(n)^{\mathrm{th}}$ term will have $\Omega(n)$ bits in its representation, right? Won't this still require $\Omega(n)$ time? $\endgroup$
    – jonderry
    Aug 25, 2011 at 17:45
  • $\begingroup$ @jonderry: Only $O(\log n)$ significant digits are needed in most cases. J.M. has pointed out the cases in which another method may be required. But Consider using floating-point representations that only keep track of the first $O(\log n)$ significant digits. That way, enough accuracy is maintained that the calculations will work out correctly, while still keeping the amount of time and space required small. $\endgroup$
    – Matt Groff
    Aug 25, 2011 at 20:35
  • $\begingroup$ I was mainly interested in the 'hard' cases where the numbers are very close together, but I think the application of this algorithm that I had in mind should have a small number of such cases. Still, it needs to be correct, so variable precision is needed for instances in which the results are close at low precision. This solution is one approach to variable precision (+1). $\endgroup$
    – jonderry
    Aug 26, 2011 at 17:39
  • $\begingroup$ I'm still musing over this question...I suppose that it might be possible to adapt Chinese Remaindering or modulated values to give perfect precision while still using only small values. I can comment on this more if you're still interested... $\endgroup$
    – Matt Groff
    Aug 28, 2011 at 17:40
  • $\begingroup$ Yes, any ideas you have would be great. $\endgroup$
    – jonderry
    Aug 29, 2011 at 20:33
2
$\begingroup$

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)]
$\endgroup$
3
  • 1
    $\begingroup$ This is just a theoretical remark; practically speaking I think your approach is fine: For this to be sublinear in $n$ in the worst case, $\log3/\log2$ needs to have finite irrationality measure. If it doesn't, there's no $O(\log n)$ bound on the number of terms you need to consider. $\log3$ and $\log2$ are both known to have finite irrationality measure, but I couldn't find anything about the quotient. $\endgroup$
    – joriki
    Aug 25, 2011 at 16:56
  • $\begingroup$ @joriki: true. In an older discussion I tried to prove, that the approximation cannot be better than some lower bound depending on n , where I related n to the number of leading terms in a quite similar series. That was 2004, when I had near no experience in NT, so I couldn't complete that sketch and everything must be reconsidered more seriously. I've gotten a weak health over the last years and don't know, whether I can come up with it again this days. If you'are interested just email me for more details. $\endgroup$ Aug 25, 2011 at 19:02
  • $\begingroup$ @joriki:(2) I found a remark on that approximation, which should be related to the question of the irrationality measure (I'm not sure, however). Assume $ \small H=max(n,m) \gt 2 $ then $\small abs(m \log(2)-n \log(3)) \gt H^{-13.5} $ by Georges Rhin(1987) due to Ray Steiner. $\endgroup$ Aug 25, 2011 at 20:21

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .