[boost] Simulating log{10}(2)

From: Daryle Walker (darylew_at_[hidden])
Date: 2006-10-29 14:59:32

Our code that deals with determining how many characters are needed to
express an integer in decimal form, based on the number of bits, use a
conversion factor like:

    #digits <= 2 + #bits * log{10}(2)

where "log{10}(2)" is the logarithm of 2 for base 10.  This can be
calculated from "ln(2) / ln(10)", where "ln" is the natural logarithm
function.  Since the conversion factor is used in compile-time integer
contexts, the constant is expressed as an integer multiply followed by an
integer divide.  The decimal expansion of the constant is approximately
0.30102999566....  Our code uses cut-off versions of that expansion for the
constant:

    static  int const  digits10 = 2 + digits * 301 / 1000;

I've also seen "30103 / 100000" being used.  Couldn't there be better
approximate fractions to use?  Based on various web calculators, like
Google's and "Contfrac" at
<http://wims.unice.fr/wims/wims.cgi?session=B75AF6A950.2&+lang=en&+module=to
ol%2Fnumber%2Fcontfrac.en>, I've found a continued fraction representation
of the constant.  An irrational number has an infinitely long c.f.
expansion, but the convergents off that expansion are usually the best
rational approximations of an irrational value.

Let's compare expansions:

1.  ln 2 / ln 10 = [0; 3, 3, 9, 2, 2, 4, 6, 2, 1, 1, 3, 1, 18, 1, 6, 1,...]
2.         0.301 = [0; 3, 3, 9, 1, 2, 3]
3.       0.30103 = [0; 3, 3, 9, 2, 2, 4, 5, 1, 1, 1, 2]

where [a0; a1, a2,...] = a0 + 1/(a1 + 1/(a2 + ...)).

The common approximation 0.301 differs from the actual expansion at a4 = 2.
The convergent there is 59/196.  The absolute differences between those
values and the actual value are:

     |log{10}(2) - 0.301| = 2.9995664e-5
    |log{10}(2) - 59/196| = 9.58750072e-6

The convergent is 3.1 times closer to the actual value than the common
approximation.  Using 0.30103 versus the convergent 4004/13301 at the point
of differing a7 = 6 gives the convergent an improvement factor of 2.1.  The
convergents have smaller numerators and denominators than their common
approximations, making them easier to calculate without worry of overflow.
Conversely, if you know that you have more leeway in multiplications, then
using higher convergent fractions instead of the decimal expansion are a
better bet.

-- 
Daryle Walker
Mac, Internet, and Video Game Junkie
darylew AT hotmail DOT com