Re: [boost] Simulating log{10}(2)

From: Zara (yozara_at_[hidden])
Date: 2006-10-30 01:49:32

On Sun, 29 Oct 2006 14:59:32 -0500, Daryle Walker
<darylew_at_[hidden]> wrote:

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

According to HP calculator 32 SII, the best fraction to use is
146/485, with an error of -9.32171e-7. Hope this helps

Zara