
Boost : 
From: Daryle Walker (darylew_at_[hidden])
Date: 20061029 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 compiletime 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 cutoff 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.9995664e5
log{10}(2)  59/196 = 9.58750072e6
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
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk