Florian的Grisu2算法如何工作? [英] how does Florian's Grisu2 algorithm work?

问题描述

我遇到了一个关于将double转换为ascii的问题，经过搜索，我得到了Florian的论文，Grisu2算法确实很棒，而且速度更快.我已经了解了Grisu2的想法，但是我不知道如何实现它，所以我得到了 Florian的C实现工具，这对我来说有点复杂，我仍然不太了解2个功能:cached_power和digit_gen，知道Grisu2的人可以帮助我吗?

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?

评论显示了我的问题.

    //    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;
}

推荐答案

第一部分:

diy_fp_t 是一个浮点结构，具有螳螂和指数作为单独的成员(不是很有趣，但是它在这里:

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

cached_power(k)的目的是计算10 ^ k的值并将结果保存到 diy_fp_t 中.因为这对于计算机而言既不容易也不是很快，所以作者拥有预先计算出的必要能力(尽可能好)的值的数组(一个用于螳螂，一个用于指数)(格里苏将不使用其他能力).在论文的第4章和第5章中.

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

示例代码中的数组以 10 ^(-343)的值开头，这是 0xbf29dcaba82fdeae * 2 ^(-1203)，= 13774783565108600494 * 2 ^(-1203). 10 ^(-342)属于下一个数组位置，依此类推.并且由于 -343 具有数组索引 [0] ，因此首先添加343.

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.

这篇关于Florian的Grisu2算法如何工作?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！