Most efficient way to calculate logarithm numerically? I was asked a question the other day about how to calculate logarithms $\log(t)$ without log tables.
Some approaches I thought of (own work) were


*

*Different methods solving $\exp(x) = t$

*Taylor expand $\log(1+t)$ around $t=0$, it will converge for $t\in [-1,1]$.

*Combine any of the above with log laws $$\cases{\log(nx) = \log(n) + \log(x)\\\\\log(x^n) = n\log(x)}$$
However I don't know how this is typically done in practice, for example in software or hardware in electronics and computers. It would be interesting with introduction to some methods and/or some sources to read up on it.
 A: It... depends. $\def\artanh{\operatorname{artanh} } \def\larr{\leftarrow}$ 
Whether some approach is a good choice depends on many factors:


*

*What arithmetic / operations are available / can be used? What are
their costs w.r.t. execution time, memory usage (static and dynamic,
volatile and non-volatile), silicon consumption, current consumption.

*Is it about absolute error or relative error?

*Is it fixed-point arithmetic or floating-point?

*Is the required precision known in advance and what is it? Or is it
for some arbitrary precision library like MPFR?

*Is the range known in advance? Or is is for some generic library that
must handle any input range?

*If fixed-point arithmetic is used, extra care must be taken that intermediate results do not overflow resp. approaches like Taylor series might be obsolete. In that case, consider Bernstein polynomials evaluated using De Casteljau's algorithm which avoids intermediate overflow by design provided the control points are representable. 

*What are the metrics for "optimal"? Precision? Speed of execution?
Code consumption? Memory consumption? Ease of implementation? ...
In hardware, CORDIC might be the way to go. In software, it depends on
which instructions are available and how they perform. CORDIC is
usually advantageous if shifting is much faster than multiplication.
Some months ago I implemented an IEEE-754 double emulation for an 8-bit
microcontroller, and even though the emulated multiplication is very
expensive (takes some 1000 cycles), approximation via polynomials beat
CORDIC which was implemented by a fellow. The algorithm goes basically
like this:


*

*Range reduction to $[1,2]$ and then to $[1/\sqrt2, \sqrt2]$. This is
basically a no-op with binary floating-point because the mantissa stays the same.

*Compute $$\ln x = 2\artanh\frac{x-1}{x+1}$$ That series is much
better suited than the Mercator series, the Taylor expansion of $\ln$
around 1. Notice that the speed of convergence of the McLaurin series
for $\artanh$ with the argument above is basically the same when $x$ is
replaced by $1/x$. This is the reason for the choice in 1.

*The implementation uses a pre-computed polynomial of degree 7 which
minimizes the maximal relative error against
$$f(x) = 2\frac{\artanh(\sqrt x)}{\sqrt x}$$
so that we have
$$\ln x = y\cdot f(y^2)\quad\text{ with }\quad y=\frac{x-1}{x+1}$$
This function is better suited than using $\artanh$ directly because it
kind of encodes the symmetry of $\artanh$ (which would be lost if I'd
approxed $\artanh$ directly by a polynomial). And it "removes" the zero
at $y=0$ which is much more convenient as the approximation is about
relative error, which is not compromized by that approach.
Degree 7 is enough to get double precision, i.e. 53 bits or more.
Due to the range reduction, the argument of $\artanh$ satisfies
$$|y| < 0.172 \approx \frac{\sqrt2-1}{\sqrt2+1}$$ and thus $f(y)$ has to
be approxed for $|y| < 0.1716^2 \approx 0.0295$.

*Undo the range reduction. As $\ln x = \ln (x\cdot 2^k) - k\ln2$ all
we have to do is adding an integral multiple of $\ln2$.
Apart from the range reduction, this consumes 9 additions, 9
multiplications and 1 division.

A much more elementary approach is the following spigot-like algorithm.
Notice that


*

*Squaring a number shifts it's base-2 exponent one to the left.

*Dividing a number by 2 decrements it's base-2 exponent by 1.

*$\log_2x$ of a number $x$ has the representation 0.* in base 2 iff $1\leqslant x<2$, and the representation 1.* iff $2\leqslant x<2^2$.
This leads to the following algorithm to compute the fractional bits
$b_n$ of $\log_2 x$:


*

*Shift $x$ until $1\leqslant x < 2$. The number of right-shifts is the
integral part of $\log_2x$. It's negative if you have to left-shift $x$
to normalize it.

*$n \larr 1$

*$x \larr x^2$

*If $x \geqslant2$ then $b_n \larr 1$, else  $b_n\larr0$

*If $x \geqslant2$ then $x \larr x/2$

*$n\larr n+1$

*goto 3

Some more remarks:


*

*MiniMax polynomials perform better than Taylor series of same degree.
Taylor has the advantage that it's easy to come by for most functions
you might need. Disadvantage of MiniMax polynomials is that they have
to be pre-computed, and that you must know the needed precision in
advance. On the other hand they do not suffer from convergence issues,
whereas Taylor sucks or does not work at all if there are singularities
around and it has only finite radius of convergence.

*MiniMax rational functions perform better than Padé of same degree.
Basically everything from the previous point carries over to this one.

*As a rule of thumb, MiniMax rational functions of degree $[2n/n]$
perform better than MiniMax polynomials of degree $3n$ (for the same target
function and interval, of course), with a clear advantage if singularities hang
around and as you move towards higher degrees. In the presence of
singularities however, MiniMax rational approximations might be tricky
to compute.

*As a rule of thumb, if you fix $m+n$ then rational MiniMax of degree
$[m/n]$ performs best if $n \approx m/2$.
