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

From: Paul A Bristow (pbristow_at_[hidden])
Date: 2006-10-30 05:50:08

|  -----Original Message-----
|  From: boost-bounces_at_[hidden] 
|  [mailto:boost-bounces_at_[hidden]] 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
[phone] & SMS, Mobile [phone] & SMS
pbristow_at_[hidden]