3

I come across a problem about converting double to ascii, after searching, I got Florian's paper "Printing Floating-Point Numbers Quickly and Accurately with Integers", Grisu2 algorithm is really awesome and much faster. I have understood Grisu2's idea but I don't know how to implement it, so I got Florian's C implement, it's a little complicated for me and I still don't really understand 2 functions: cached_power and digit_gen, could anyone who knows Grisu2 help me?

Comments show my question.

    //    cached_power function:

static const uint64_t powers_ten[] = {0xbf29dcaba82fdeae , 0xeef453d6923bd65a,...};  
//how do these numbers precomputed 
static const int powers_ten_e[] = {-1203 , -1200 , -1196 , -1193 , -1190 , ...};//and what do they mean?

static diy_fp_t cached_power(int k) 
{//does this function mean give k and return the normalized 10^k diy_fp_t?
      diy_fp_t res;
      int index = 343 + k;//why add 343?
      res.f = powers_ten[index];
      res.e = powers_ten_e[index];
      return res;
}

this one is more complicated

void digit_gen(diy_fp_t Mp, diy_fp_t delta,//Is Mp normalized?
char* buffer, int* len, int* K) 
{
     uint32_t div; int d, kappa; diy_fp_t one;
     one.f = ((uint64_t)1) << -Mp.e; one.e = Mp.e;//what if Mp.e is positive? what's the purpose of one?
     uint32_t p1 = Mp.f >> -one.e; /// Mp_cut// what does p1 mean?
     uint64_t p2 = Mp.f & (one.f - 1);//what does p2 mean?
     *len = 0; kappa = 3; div = TEN2;//why kappa=3 and div=100? is kappa related to div?
    while (kappa > 0) 
    {    /// Mp_inv1  //what does this loop mean?
         d = p1 / div;
         if (d || *len) buffer[(*len)++] = '0' + d;
         p1 %= div; kappa--; div /= 10;
         if ((((uint64_t)p1) << -one.e) + p2 <= delta.f) 
         { /// Mp_delta
             *K += kappa; return;
         }
    }
    do 
    {  //what does this loop mean?
         p2 *= 10;
         d = p2 >> -one.e;
         if (d || *len) buffer[(*len)++] = '0' + d; /// Mp_inv2
         p2 &= one.f - 1; kappa--; delta.f *= 10;// p2&=one.f-1 means what?
    } while (p2 > delta.f);
    *K += kappa;
}
vitaut
  • 49,672
  • 25
  • 199
  • 336
user1024
  • 982
  • 4
  • 13
  • 26
  • I probably don´t have to ask, but you´re aware that you´ll get results acceptable for most situations in one code line, without using >2010 algorithms? – deviantfan Mar 09 '15 at 13:26
  • 1
    And what about reading the actual paper? – deviantfan Mar 09 '15 at 13:30
  • Is there a specific problem that cannot be answered in this ***[link](http://florian.loitsch.com/publications)***? (provided by you) This statement in the paper you cite: ***Correct printing become part of the specification of many languages and furthermore all major C libraries (and as a consequence all programs relying on the*** _printf_ ***functions) adapted accurate algorithms and print correct results now***, suggests it is likely the version of C you are using (if it is reasonably recent) already contains the ability to print _accurately_. (page 1, second column, second paragraph) – ryyker Mar 09 '15 at 13:57
  • @deviantfan @ryyker Well, i do know how to use `sprintf` to get right results, but my question is i don't completely understand this `Grisu2` algorithm even after reading and thinking about the actual paper carefully. – user1024 Mar 10 '15 at 05:12

1 Answers1

3

The first part:

diy_fp_t is a floating point struct with mantisse and exponent as separate members (not very interesting, but it´s here: https://github.com/miloyip/dtoa-benchmark/blob/master/src/grisu/diy_fp.h).

The purpose of cached_power(k) is to compute the value of 10^k and save the result to a diy_fp_t. Because that is neither trivial nor fast for the computer, the author has arrays (one for mantisse, one for exponent) of precalculated values (as good as possible) of the necessary powers (Grisu won´t use other powers than that. An explanation is in the paper, chapter 4 and 5).

The array in the example code begins with the value for 10^(-343), this is 0xbf29dcaba82fdeae * 2^(-1203), = 13774783565108600494 * 2^(-1203). 10^(-342) belongs to the next array position, and so on. And because -343 has the array index [0], 343 is added first.

deviantfan
  • 11,268
  • 3
  • 32
  • 49