1
$\begingroup$

Can anyone share an easy way to approximate $\log_2(x)$, given $x$ is between $0$ and 1?

I'm trying to solve this using an old fashioned calculator (i.e. no logs)

Thanks!

EDIT: I realize that I stepped a bit ahead. The x comes in the form of a fraction, e.g. 3/8, which is indeed between 0 and 1, but could also be written as log2(3) - log2(8). I am hoping there is a quick way to approximate this calculation to let's say 2 decimals

$\endgroup$
  • $\begingroup$ Close to $0$ a logarithm diverges to $-\infty$... How close to zero do you need to go? A fast (and quite rough) approximation is a decimal logarithm is minus a number of zeros in front of your number (including the one before the decimal point), and the binary logarithm is 10/3 times the decimal logarithm (as $2^{10} = 1024$ is quite close to $10^3=1000$). But it is rough: counting zeros gives result $\pm 1$, multiplied by 10/3 makes max error about $3$... $\endgroup$ – CiaPan Mar 21 '16 at 9:38
  • $\begingroup$ @CiaPan Please see my edited question. Not that close to 0 like 0.0001. Solving something in the lines of log(3/7) would be the goal. $\endgroup$ – Dimebag Mar 21 '16 at 9:57
1
$\begingroup$

First normalize the value to the range $[1,2)$, multiplying by $2$ as long as necessary (the number of multiplies will form the integer part of the logarithm).

Then use the formula

$$\log_2\left(\frac{1+t}{1-t}\right)=\frac2{\ln(2)}\left(t+\frac{t^3}3+\frac{t^5}5\cdots\right)$$ evaluating for

$$t=\frac{x-1}{x+1}$$which will be in range $[0,\dfrac13)$. It will converge reasonably quickly, about one correct decimal per term.


Another option is to keep a tabulated list of constants such as $1.5,1.25,1.125\cdots$ together with their logarithms, and use

$$x>C_i\to \log_2(x)=\log_2\left(\frac x{C_i}\right)+\log(C_i).$$

At the same time as you divide $x$ by the constants (but keeping $x>1$), you accumulate the logarithms of these constants. When $x\approx1$, you have it. You can choose the set of constants that suits you best.

$\endgroup$
  • $\begingroup$ How would this fare on very small numbers? would the "about one correct decimal per term" apply after the first significant digit or in general? $\endgroup$ – whn Sep 25 at 16:00
  • $\begingroup$ @opa: one decimal per term is the worst case. $\endgroup$ – Yves Daoust Sep 25 at 20:36
2
$\begingroup$

Using that $\log_2(x)=\mbox{ln}(x)/\mbox{ln}(2)$, now you can use the Taylor expansion: \begin{equation} \mbox{ln}(x)=\mbox{ln}\left((x-1)+1\right)=\sum_{k=1}^{\infty}\frac{(-1)^{k-1}}{k}(x-1)^k \end{equation} The same expansion can be used for determining the $\mbox{ln}(2)$. The first terms of the expansion are \begin{equation} \log_2(x)=\frac{1}{\mbox{ln}(2)}\left[(x-1)-(x-1)^2/2+...\right] \end{equation} This expansion is working better around $x=1$. These kind of expansion are commonly used in calculators or programming languages to compute analytic functions.

EDIT: Another possibility to compute the natural logarithm is to use the generalized continued fraction \begin{equation} \log((x-1)+1)=\cfrac{2(x-1)}{(x-1)+2-\cfrac{(x-1)^2}{3((x-1)+2)-\cfrac{4(x-1)^2}{5((x-1)+2)-\cfrac{9(x-1)^2}{7((x-1)+2)-\cdots}}}} \end{equation} I think this option will be converging faster than the Taylor expansion

As a final approximation, I would recommend you also to have a look at the Padé expansion of the logarithm. Having a fast look to the old questions in this website I found Approximating Logs and Antilogs by hand, where user153012 gives next Padé approximation to compute the logarithm $\phi_3(x)\leq\mbox{ln}(x)\leq\psi_3(x)$ where the lower bound is $$\phi_3(x)=\frac{x(60+60x+11x^2)}{3(20+30x+12x^2+x^3)},$$ and the upper $$\psi_3(x)=\frac{x(30+21x+x^2)}{3(10+12x+3x^2)}.$$

$\endgroup$
  • $\begingroup$ The problem with this one is that it is not fast, i.e., doing by hand, you need to go up to (I guess) k=10 or 15 (up to k=5 is not enough) to get a good answer of let's say 2 decimals. $\endgroup$ – Dimebag Mar 21 '16 at 9:55
  • $\begingroup$ Please check my edited question. I am looking for something as easy as approximating powers of e using the solution I found here: math.stackexchange.com/questions/71357/approximation-of-e-x $\endgroup$ – Dimebag Mar 21 '16 at 10:02
  • $\begingroup$ You can also use a continued fraction to compute the logarithm, included in the answer (I have no experience with these continued fraction method, but apparently they are faster than Taylor series). If not, a Padé expansion of the logarithm should work fine $\endgroup$ – seoanes Mar 21 '16 at 10:13
1
$\begingroup$

When $x$ is in the range $]0.5, 1[$ you can easily find a binary representation of the $\log_2(x)$ using this algorithm:

  1. Start writing $-0.$ (with the dot as the result will be fractional) and evaluate $z=1/x$.
  2. if $z^2>2$ append $1$ and let $z=z/2$, else append $0$, to the result.
  3. go to step 2 until you have enough digits (or you have $z=1$)

Calculate $3.3$ binary digit for each decimal to stop the algorithm.

You will find a number like $-0.0110101$ that can easily be converted in decimal as $-0.4140625$ weighting each digit as $1 \over 2^n$.

Following is an example of the calculations for $\log_2(0.75)\approx -0.415$.

1.333333333 0           -0.     
1.333333333 1.777777778   0  0
1.777777778 3.160493827   1 -0.25
1.580246914 2.497180308   1 -0.125
1.248590154 1.558977373   0  0
1.558977373 2.430410448   1 -0.03125
1.215205224 1.476723736   0  0
1.476723736 2.180712994   1 -0.0078125
                            -0.4140625
$\endgroup$
0
$\begingroup$

If your input involves just multiplication or division of small natural numbers and you don't need accuracy exceeding 4 decimal numbers, then logarithmic tables could be the simplest solution.

See for example

For much bigger or smaller numbers you may apply standard reduction: $$\log_2 (x\cdot 2^n) = \log_2 x + n$$ $$\log_2 (x/ 2^n) = \log_2 x - n$$

with some pre-selected powers, say
$2^3 = 8$, $2^5 = 32$, $2^8=256$, $2^{10} = 1024$, $2^{15}=32768$, $2^{20} = 1048576$...


You may also search the Web for some online $\log_2$ calculator, like this one.

$\endgroup$
0
$\begingroup$

$$\log(2)=\sum_{n=1}^{\infty}\frac{1}{n2^n}$$

$$(1/2)+(1/(2\cdot2^2))+(1/(3\cdot2^3))+(1/(4\cdot2^4))+(1/(5\cdot2^5))+(1/(6\cdot2^6))+(1/(7\cdot2^7))+(1/(8\cdot2^8))+(1/(9\cdot2^9))+(1/(10\cdot2^{10}))=0.6930...$$

Even by hand this is giving a simple procedure of finding $\log(2)$ in base $2$

$\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.