
Boost : 
From: Zara (yozara_at_[hidden])
Date: 20061030 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 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.
According to HP calculator 32 SII, the best fraction to use is
146/485, with an error of 9.32171e7. Hope this helps
Zara
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk