The traditional—but certainly not the best—way to compute the value of the logarithm of some number is to use a Taylor series, for example

but that expansion is only valid for , or so, because it is the Taylor expansion of "around 1", and the convergence radius of this particular expression isn't very large. Furthermore, it needs a great deal of terms before converging.

To accelerate convergence, Young and Gregory [1] propose to “compress” the series (by a short series of identities and manipulations):

,

or

.

This series, where the “around ” condition has been removed, should converge for any . However, it does not so very fast. So the problem seems to be to have a good initial guess on and use a Taylor series expansion around this good guess. Let’s revisit the first formula, valid for , but this time setting . We get

,

or

.

So, now we’re stuck with . The constant clearly depends on (since we have that ), and so can’t really be a constant. We must find a convenient from . Finding is easy when is of some special form, namely . It would be especially easy to find if (because we could use some compiler built-in, say `__builtin_clz`, to find ), but we want , not . Well, no matter, we observe that since

,

we can write

,

where , but since we choose , we get

.

Lastly, since , can be approximated as the number of bits in , something like . This operation, of course, is to be carried not in floating point (because if we’re doing series, it’s likely because we do not have a log function in the first place) but with an efficient built-in, something like `__builtin_clz`.

*

* *

Let us now compare how fast each of the variants converge.

The series “around ” with a very good (and deusexmechanically chosen) guess for converges very fast ( was chosen). The second, in green, is the series with (where the brackets stand for rounding). Lastly, Young’s and Gregory’s “compressed” series. It does converge, but it requires *a lot* of iterations.

Numerically, we also see rather rapid convergence: (with the columns in the same order: good initial guess, guess, and Young’s and Gregory’s):

*

* *

Lastly, we can ask ourselves how bad the initial guess can be given the number of iterations we are willing to perform. For now, I do not have a good characterization of it. But if we look at the following graph:

we find that, even as the number of terms grows, the convergence radius (which we should define more formally but that could be understood to be the region where the initial guess still leads to an approximation with a small error) doesn’t grow exponentially fast. More on this later, maybe.

*

* *

Choosing an initial guess using base 2 logarithms makes only sense if we have a *very* efficient way of finding integer in (where is not necessarily an integer. For this, you may use, as I said earlier, a compiler-specific extension, such as GCC’s `__builtin_clz`, that we used before, or something like it that maps to an efficient machine instruction. I also am not sure that Taylor series, and variants, are the best way of computing logarithms. However, except maybe for CORDIC algorithms, pretty much every textbook on numerical mathematics approaches the problem as we did here, except that they do not choose in “around ” adaptively.

[1] David M. Young, Robert Todd Gregory — *A Survey of Numerical Mathematics, Vol 1* — Addison-Wesley (1972)