Simulating log{10}(2)
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
On 10/29/06, Daryle Walker <darylew@hotmail.com> wrote:
Couldn't there be better approximate fractions to use?
I'm not sure if there were other questions implied by the ommited portions of your post, but my best guess is that you are looking for an algorithm which builds a good fit rational number from a float without resorting to a simple and inefficient decimal truncation. If this is what you are looking for then what might work is a function which builds a rational number as a continued fraction. Essentially you strip off the integer part of your rational number, take the inverse of the rest, strip off the integer part, take the inverse, and keep going until you hit a depth you like (3 or 4 is usually plenty). When you hit the maximum depth use zero as an approximation for the fraction built so far and pass it back up. Each level then considers the rational returned to it to be the inverse of part of the fraction it was building, so it flips the numerator and denominator and adds the whole part it stripped off. A greater depth will give you greater accuracy, but you also need to be careful of hitting a depth where extremely small numbers (usually the result of floating point error) will result in overflowing your integer type. Hope this helps -Jason
On 10/29/06 3:23 PM, "Jason Hise" <0xchaos@gmail.com> wrote:
On 10/29/06, Daryle Walker <darylew@hotmail.com> wrote:
Couldn't there be better approximate fractions to use?
I'm not sure if there were other questions implied by the ommited portions of your post, but my best guess is that you are looking for an algorithm which builds a good fit rational number from a float without resorting to a simple and inefficient decimal truncation. If this is what you are looking for then what might work is a function which builds a rational number as a continued fraction. [TRUNCATE description of the building algorithm]
Actually, the question was rhetorical. I already found, using various web calculators, better approximate fractions that could be used instead of the "crude" 301/1000 or 30103/100000. I was suggesting that we could use one of those "better" fractions instead. -- Daryle Walker Mac, Internet, and Video Game Junkie darylew AT hotmail DOT com
On Sun, 29 Oct 2006 14:59:32 -0500, Daryle Walker <darylew@hotmail.com> 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
| -----Original Message----- | From: boost-bounces@lists.boost.org | [mailto:boost-bounces@lists.boost.org] On Behalf Of Daryle Walker | Sent: 29 October 2006 20:00 | To: Boost mailing list | Subject: [boost] Simulating log{10}(2) <snip> | 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. Well this is very interesting and I am sure you are right, but for the purpose of calculating the number of decimal digits, the approximation seems to me to be 'fit for purpose' (or good enough). Fred Tydeman put me right on this (especially with regard to overflow and accuracy) with the following, extracted from his comments incorporated in http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1171.pdf <quote> For base 2 systems, values for these macros are usually conveniently derived from the number of significand (mantissa) binary digits, significand_digits defined by FLT_MANT_DIG, DBL_MANT_DIG or LDBL_MANT_DIG using the formula max_digits10 = 2 + significand_digits * 301/1000 // if 16-bit integers else max_digits10 = 2 + significand_digits * 30103UL/100000UL For example, for systems with 32-bit integers: #define FLT_MAXDIG10 (2+(FLT_MANT_DIG * 30103UL)/100000UL) #define DBL_MAXDIG10 (2+ (DBL_MANT_DIG * 30103UL)/100000UL) #define LDBL_MAXDIG10 (2+ (LDBL_MANT_DIG * 30103UL)/100000UL) which yield the following values on typical implementations: 32-bit IEEE 754 float FLT_DIG 6, FLT_MAXDIG10 9 64-bit IEEE 754 double DBL_DIG 15, DBL_MAXDIG10 17 80-bit IEEE 754 long double LDBL_DIG 19, LDBL_MAXDIG10 21 For 16-bit integer systems: if DBLMANT_DIG is 53 (for IEEE 64-bit doubles) then 53 * 301 = 15953, but larger and more accurate approximations, like 3010/10000 or 30103/100000, would overflow 16-bit integers. For 32-bit integer systems: the more accurate ratio 30103UL/100000UL is preferred to give the correct values for well beyond 256 significand bits. Significand bit values where .3 and .30103 produce different values: 103, 113, 123, 133, 143, 153, 163, 173, 183, 193, 196, 203, 206, 213, 216, 223, 226, 233, 236, 243, 246, 253, 256, 263, 266, 273, 276, 283, 286, 293, 296, 299, ... showing that using 301/1000 would give an incorrect result for these significand bits but 30103UL/100000UL will be correct. Using UL further reduces the risk of overflow. For user defined floating-point types, usually to implement very high precision not available in hardware, similar (but of course non-standard) macros can be defined. </quote> The corresponding C++ document is http://www2.open-std.org/JTC1/SC22/WG21/docs/papers/2005/n1822.pdf std::numeric_limits::max_digits10 should become standard in time. meanwhile you might like to declare macros as above DBL_MAXDIG10 etc when you can use your shiny new improved approximation. Or should Boost do this as BOOST_FLT_MAXDIG10 BOOST_DBL_MAXDIG10, BOOST_LDBL_MAXDIG10 right now? Paul --- Paul A Bristow Prizet Farmhouse, Kendal, Cumbria UK LA8 8AB +44 1539561830 & SMS, Mobile +44 7714 330204 & SMS pbristow@hetp.u-net.com
On 10/30/06 5:50 AM, "Paul A Bristow" <pbristow@hetp.u-net.com> wrote:
-----Original Message----- From: boost-bounces@lists.boost.org [mailto:boost-bounces@lists.boost.org] On Behalf Of Daryle Walker Sent: 29 October 2006 20:00 To: Boost mailing list Subject: [boost] Simulating log{10}(2) <snip>
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.
Well this is very interesting and I am sure you are right, but for the purpose of calculating the number of decimal digits, the approximation seems to me to be 'fit for purpose' (or good enough). [TRUNCATE how the current approximations are used]
But we have the option of doing better. I'm wondering if we should change our code to use the better approximating fractions. -- Daryle Walker Mac, Internet, and Video Game Junkie darylew AT hotmail DOT com
| -----Original Message----- | From: boost-bounces@lists.boost.org | [mailto:boost-bounces@lists.boost.org] On Behalf Of Daryle Walker | Sent: 31 October 2006 17:17 | To: Boost mailing list | Subject: Re: [boost] Simulating log{10}(2) | | On 10/30/06 5:50 AM, "Paul A Bristow" | <pbristow@hetp.u-net.com> wrote: | | >> -----Original Message----- | >> From: boost-bounces@lists.boost.org | >> [mailto:boost-bounces@lists.boost.org] On Behalf Of Daryle Walker | >> Sent: 29 October 2006 20:00 | >> To: Boost mailing list | >> Subject: [boost] Simulating log{10}(2) | > <snip> | > | >> 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. | > | > Well this is very interesting and I am sure you are right, | but for the | > purpose of calculating the number of decimal digits, the | approximation seems | > to me to be 'fit for purpose' (or good enough). | [TRUNCATE how the current approximations are used] | | But we have the option of doing better. I'm wondering if we | should change | our code to use the better approximating fractions. Very probably would be better. But I'm not the maintainer of lexical cast code, etc, merely an interefering bystander ;-) Paul --- Paul A Bristow Prizet Farmhouse, Kendal, Cumbria UK LA8 8AB +44 1539561830 & SMS, Mobile +44 7714 330204 & SMS pbristow@hetp.u-net.com
Paul A Bristow wrote:
But we have the option of doing better. I'm wondering if we should change our code to use the better approximating fractions.
Very probably would be better. But I'm not the maintainer of lexical cast code, etc, merely an interefering bystander ;-)
We also know that the current approximation works, and is supported by some half-decent mathematicians, so maybe we should be conservative? Unless there are cases where the alternative works better, *and* that the alternative will never under-estimate the number of digits (overestimation being benign I assume?) Just my 2c worth... John.
Paul A Bristow wrote:
Very probably would be better. But I'm not the maintainer of lexical cast code, etc, merely an interefering bystander ;-)
Are you waiting for my decision? Well, I'm a lazy person and don't want to repeat change/test/commit cycle without a good reason. -- Alexander Nasonov Project Manager at Akmosoft ( http://www.akmosoft.com ) Blog: http://nasonov.blogspot.com Email: $(FirstName) dot $(LastName) at gmail dot com
participants (6)
-
Alexander Nasonov -
Daryle Walker -
Jason Hise -
John Maddock -
Paul A Bristow -
Zara