0
$\begingroup$

Easy ways are nice, but im not looking for an easy way to solve pre-solved logarithms with clean digits or perfect fractions. Like if I had something like $127$ and i wanted to know how many times $2$ went into it, its not going to be a clean answer. (it's something like $6.988684686$, which i got from trial and error, not a particular operation, and even that's not perfect)

Not looking for tricks here, just looking for the right algorithm, even if it is as tedious as cube root long division or taylor series trigonometry solutions.

Put bluntly, to some reasonable decimal accuracy ($2$-$3$ places?) like babylonian variants for square roots, how can I solve logarithms with pen and paper? Is there a series or some kind of iteration loop that gets closer and closer?

$\endgroup$
2
$\begingroup$

Method 1: To compute $\log_a(b)$, compute the smallest integer $n$ such that $b/a^n \leq 2$. Also compute the smallest integer $m$ such that $a/e^m \leq 2$. Then $\log_a(b)=\frac{n+\ln(b/a^n)}{m+\ln(a/e^m)}$. These logarithms can now be computed using the Maclaurin series $\ln(1+x)=\sum_{n=1}^\infty (-1)^{n-1} \frac{x^n}{n}$, which will converge in this range.

If $|x|$ is very close to $1$, and especially if $x=1$, this series converges quite slowly, in which case you will want to use series acceleration. One way to achieve this is to use the fact mentioned in another answer, which is that if $y=x/(2+x)$ then $\ln(1+x)=2\sum_{n=1}^\infty y^{2n-1}/(2n-1)$. With this series acceleration, even in the worst case $x=1$, you still get about 1 ternary digit per step.

Method 2: To get binary digits of $\log_2(x)$, first read off its integer part by repeated division by $2$ (or directly from the representation, if you are given the number in floating point). Now read off the binary digits after the "decimal" point by dividing by $2^{2^{-n}},n=1,2,\dots$ and seeing if the result is now less than $1$ or not. If it is, then that digit is $0$ and you go back to the same input you had. If it is not, then that digit is $1$, and you preserve the division and continue. So for example, $\log_2(127)=6+\log_2(127/64)$, and now to continue you need to check whether $127/64$ is greater than $\sqrt{2}$ (it is), whether $127/(64\sqrt{2})$ is greater than $2^{1/4}$ (it is), whether $127/(64 \cdot 2^{3/4})$ is greater than $2^{1/8}$ (it is), etc.

You can also evaluate these inequalities indirectly if evaluating roots is a problem: for example, you want to check whether $127/64$ is greater than $\sqrt{2}$ so instead you check whether $127^2>2 \cdot 64^2$. This will always boil down to checking whether your original number to some integer power exceeds $2$ to some other integer power, which is particularly straightforward in floating point arithmetic (where you don't actually need to compute the powers of $2$ at all).

You can then adapt this method for getting $\log_2(x)$ to other bases using the change of base formula as in the previous method.

$\endgroup$
  • $\begingroup$ how would one go about precomputing these values, without a calculator? $\endgroup$ – Tristian Jul 26 '18 at 14:39
  • $\begingroup$ @Tristian In this answer I'm assuming that you have bunch of logs, all base $a$, that you want to compute. If your base varies, then you should just convert everything to base $e$. The awkward thing about that is that you need to choose an approximation of $e$ up front in order to do the divisions by hand. If your base doesn't vary, then you can use the same algorithm to get $\ln(a)$, for example $\ln(2)=1+\ln(2/e)$ and now pick an approximation of $e$ and Taylor expand to get an approximation of $\ln(2/e)$. $\endgroup$ – Ian Jul 26 '18 at 15:06
  • $\begingroup$ @Tristian (Cont.) But since the overwhelming majority of log calculations that people do are base 2,e, or 10, you would be better off just memorizing a few digits of $\ln(2)$ and $\ln(10)$, if you really need to hand-compute logarithms sometimes. $\endgroup$ – Ian Jul 26 '18 at 15:08
  • $\begingroup$ I'm more familiar with ln(10) approximations, but e is the natural logarithm, im wondering. e^30 is about the same as log10 to the 130 (3:13 ratio) but its not precise (20.0855 vs. 19.952, so about 99.3% close). The advantage of 1.2558925... over 2.718281828459045... is that it returns back to 10 then repeats, but is e the only way to do it? That self correcting/repeating aspect of base 10 is really nice. $\endgroup$ – Tristian Jul 26 '18 at 15:37
  • 1
    $\begingroup$ @Tristian Working with $e$ gives the nice Taylor expansion, $\ln(1+x)=\sum_{n=1}^\infty (-1)^{n-1} \frac{x^n}{n!}$ for $0<x \leq 2$. $\endgroup$ – Ian Jul 26 '18 at 15:55
2
$\begingroup$

I have a table of logarithms that goes out to 5 places. Bound pages of log tables were used for high precision until the 1960s approximately but they still can be used effectively even if they qualify today as antiques.

Also see CORDIC or Volder's algorithm as adapted to the HP 35 calculator for computing trig functions and logarithms.

$\endgroup$
0
$\begingroup$

For $-1<x\leq 1$ we have $\ln (1+x)=x-x^2/2+x^/3-...$ and if we let $y=x/(2+x)$ then $(1+y)/(1-y)=1+x$ so $$(\bullet)\quad \ln (1+x)=\ln (1+y) -\ln (1-y)=$$ $$=(y-y^2/2+y^3/3-...)-(-y-y^2/2-y^3/3-...)=$$ $$=2(y+y^3/3+y^5/5+...).$$ In particular, for $x=1$ we have $y=3^{-1}$ so $\ln 2=2(3^{-1}+3^{-3}/3+3^{-5}/5+...),$ which converges fast enough for easy manual calculation of $\ln 2.$ Then we can also calculate $1/\ln 2,$ which we will need if we want to obtain logs to base $2.$

For integer $n$ and $2^n<z\leq (3/2)2^n$ let $\ln z=n\ln 2+ \ln (1+x)$ where $x=2^{-n}x-1.$ For integer $n$ and $(3/2)2^n<z<2^{n+1}$ let $\ln z =(n+1)\ln 2 +\ln (1+x)$ where $x=2^{-(n+1)}-1.$ In either case apply $(\bullet).$ In either case we have $|y|\leq 1/5.$

For $\log_2 z,$ compute $\ln (1+x)$ as in the above paragraph, and calculate $\log_2(1+x)=(\ln (1+x))\cdot (1/\ln 2).$

For common logs (Base Ten): Having already obtained $\ln 2,$ we need the value $(\ln 2)/(\ln 10) =(3\ln 2+\ln (1+x))^{-1}$ where, in $(\bullet) $ we have $x=1/4 $ and $y=x/(2+x)=1/9.$ So for $\log_{10}z, $ calculate $\log_2 z$ and multiply it by $(\ln 2)/ (\ln 10)$.

$\endgroup$
  • $\begingroup$ That $x/(2+x)$ trick is really nice. $\endgroup$ – Ian Jul 27 '18 at 3:54
  • 1
    $\begingroup$ John Napier invented (discovered?) logarithms long before there was calculus or power series. He could calculate approximate logs to a base $B$ that was very close to $1.$ E.g. by repeated squaring and other short cuts we find that $(1.000001)^{693147}$ is very close to $2$. And $(1.000001)^{2302585}$ is very close to $10.$ $\endgroup$ – DanielWainfleet Jul 27 '18 at 5:04
  • 1
    $\begingroup$ True, but this is more or less working with a table (compute powers and read them in reverse to get logs). That's not quite in the spirit of this question. $\endgroup$ – Ian Jul 27 '18 at 5:07
  • 1
    $\begingroup$ There are other tricks for turning some power series, such as the series for $\ln (1+x),$ into faster-converging series. $\endgroup$ – DanielWainfleet Jul 27 '18 at 5:15
0
$\begingroup$

This is a very different method than in my other answer. Use Newton's Method $U_{n+1}=U_n-\delta_n$ where $\delta_n=\frac {f(U_n)}{f'(U_n)}.$

With $f(x)=e^x-z$ and $f'(x)=e^x$, we obtain a sequence $(U_n)_n$ converging to $L=\ln z.$

Calculate $e^{U_{n+1}}$ (in order to calculate $U_{n+2}$) by $e^{U_{n+1}}=e^{U_n}e^{-\delta_n},$ using the power series for $e^{-\delta_n}.$

We can improve on this by replacing $\delta_n$ with $\delta^*_n=\frac {2f(U_n)}{f'(L)+f'(U_n)}$, which in this case is $\frac {2(e^{U_n}-z)}{z+f'(U_n)}.$ Each iteration in Newton's method approximately doubles the number of decimal places of accuracy; This improvement approximately triples it. It is usually only possible to employ this improvement with certain transcendental functions, such as $f(x)=e^x-z,$ where we know what $f'(L)$ is when $f(L)=0$ without knowing $L.$

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