弗洛里安的Grisu2算法是如何工作的？

Question

弗洛里安的Grisu2算法是如何工作的？

calgorithmprecisionieee-754floating-point-conversion

3

我遇到了一个将double转换为ascii的问题，经过搜索，我找到了Florian的论文"使用整数快速准确地打印浮点数", Grisu2算法非常棒且更快。我已经理解了Grisu2的思想，但我不知道如何实现它，所以我找到了Florian的C语言实现, 对我来说有点复杂，我仍然不太明白cached_power和digit_gen这两个函数，是否有了解Grisu2的人能帮助我吗？

注释显示了我的问题。

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

这个更加复杂

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

- user1024

我可能不需要问，但您是否意识到，在不使用>2010算法的情况下，您可以在一行代码中获得适用于大多数情况的结果？ - deviantfan

1

那阅读实际的论文呢？ - deviantfan

在您提供的这个链接中，是否有任何特定问题无法得到解答？您引用的论文中这句话：“正确的打印已成为许多语言规范的一部分，而且所有主要的 C 库（以及因此依赖于 printf 函数的所有程序）都采用了准确的算法，并打印出正确的结果”，这表明如果您使用的是相对较新的版本的 C，它已经包含了打印“准确”的能力。（第1页，第二栏，第二段） - ryyker

@deviantfan @ryyker 我知道如何使用sprintf来获得正确的结果，但我的问题是，即使我仔细阅读和思考了实际论文，我仍然不完全理解这个Grisu2算法。 - user1024

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- deviantfan · Accepted Answer

第一部分：

diy_fp_t是一个浮点结构体，其尾数和指数作为单独的成员存在（并不是很有趣，但在这里：https://github.com/miloyip/dtoa-benchmark/blob/master/src/grisu/diy_fp.h）。

cached_power(k)的目的是计算10^k的值并将结果保存到diy_fp_t中。因为对于计算机来说，这既不是微不足道的，也不是快速的，所以作者有一个预先计算好的数组（一个用于尾数，一个用于指数），包含了必要的幂次的预计算值（Grisu不会使用其他的幂次。在论文的第4章和第5章中有解释）。

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