35

当然大多数语言都有这方面的库函数，但假设我想自己做。

假设像在 C 或 Java 程序中一样给出浮点数（'f' 或 'd' 后缀除外），例如“ 4.2e1”、“ .42e2”或简单的“ 42”。一般来说，我们有小数点前的“整数部分”、小数点后的“小数部分”和“指数”。这三个都是整数。

查找和处理单个数字很容易，但是如何将它们组合成类型值float或double不丢失精度？

我正在考虑将整数部分乘以 10^ n，其中n是小数部分中的位数，然后将小数部分添加到整数部分并从指数中减去n 。例如，这实际上变成4.2e1了42e0。然后我可以使用该pow函数计算 10^指数并将结果与​​新的整数部分相乘。问题是，这种方法是否能保证整个过程的最大精度？

对此有什么想法吗？

4

11 回答 11

26

所有其他答案都忽略了正确执行此操作的难度。您可以在此采用第一种方法，这在一定程度上是准确的，但在您考虑 IEEE 舍入模式（等）之前，您永远不会得到正确的答案。我之前写过一些幼稚的实现，但有相当多的错误。

如果您不害怕数学，我强烈建议您阅读 David Goldberg 的以下文章，每位计算机科学家都应该了解浮点运算。您将更好地了解幕后发生的事情，以及这些位为何如此布局。

我最好的建议是从一个有效的 atoi 实施开始，然后从那里搬出去。您会很快发现自己遗漏了一些东西，但只要看看strtod的源代码，您就会走上正确的道路（这是一条漫长而漫长的道路）。最终你会称赞insertdiety 这里有标准库。

/* use this to start your atof implementation */

/* atoi - christopher.watford@gmail.com */
/* PUBLIC DOMAIN */
long atoi(const char *value) {
  unsigned long ival = 0, c, n = 1, i = 0, oval;
  for( ; c = value[i]; ++i) /* chomp leading spaces */
    if(!isspace(c)) break;
  if(c == '-' || c == '+') { /* chomp sign */
    n = (c != '-' ? n : -1);
    i++;
  }
  while(c = value[i++]) { /* parse number */
    if(!isdigit(c)) return 0;
    ival = (ival * 10) + (c - '0'); /* mult/accum */
    if((n > 0 && ival > LONG_MAX)
    || (n < 0 && ival > (LONG_MAX + 1UL))) {
      /* report overflow/underflow */
      errno = ERANGE;
      return (n > 0 ? LONG_MAX : LONG_MIN);
    }
  }
  return (n>0 ? (long)ival : -(long)ival);
}
于 2008-09-17T17:17:32.110 回答
21

将十进制数转换为最佳浮点近似值的“标准”算法是 William Clinger 的如何准确读取浮点数，可从此处下载。请注意，正确执行此操作需要多精度整数，至少在一定百分比的时间内，才能处理极端情况。

在 Burger 和 Dybvig 的“快速准确地打印浮点数”中可以找到另一种方法，即从浮点数中打印最佳十进制数，可在此处下载。这也需要多精度整数运算

另请参阅 David M Gay 的正确舍入二进制-十进制和十进制-二进制转换，了解双向算法。

于 2008-09-29T22:21:21.510 回答
10

我会使用它的二进制表示直接组装浮点数。

一个接一个地读入第一个字符，首先找到所有数字。在整数算术中做到这一点。还要跟踪小数点和指数。这个稍后会很重要。

现在你可以组装你的浮点数了。首先要做的是扫描数字的整数表示以查找第一个设置的一位（从最高到最低）。

第一个位之后的位是尾数。

获得指数也不难。您可以从科学记数法中知道第一位的位置、小数点的位置和可选的指数。结合它们并添加浮点指数偏差（我认为是 127，但请查看一些参考资料）。

这个指数应该在 0 到 255 的范围内。如果它更大或更小，你有一个正或负的无限数（特殊情况）。

将指数存储到浮点数的 24 到 30 位。

最重要的位只是符号。一表示负，零表示正。

它比实际更难描述，尝试分解一个浮点数并查看指数和尾数，你会发现它真的很容易。

顺便说一句 - 在浮点本身中进行算术是一个坏主意，因为你总是会强制你的尾数被截断为 23 个有效位。这样你不会得到准确的表示。

于 2008-09-17T17:05:11.780 回答
2

解析时可以忽略小数点（位置除外）。假设输入是：156.7834e10... 这可以很容易地解析为整数 1567834，后跟 e10，然后您可以将其修改为 e6，因为小数是浮点数“数字”部分末尾的 4 位数字.

精度是个问题。您需要检查您使用的语言的 IEEE 规范。如果尾数（或分数）中的位数大于 Integer 类型中的位数，那么当有人键入以下数字时，您可能会丢失精度：

5123.123123e0 - 在我们的方法中转换为 5123123123，它不适合整数，但 5.123123123 的位可能适合浮点规范的尾数。

当然，您可以使用一种方法，将每个数字放在小数点前，将当前总数（以浮点数）乘以 10，然后添加新数字。对于小数点后的数字，在添加到当前总数之前，将该数字乘以 10 的增长幂。但是，此方法似乎引出了您为什么要这样做的问题，因为它需要使用浮点原语而不使用现成的解析库。

无论如何，祝你好运！

于 2008-09-17T17:05:47.380 回答
2

是的，只要这些操作是EXACT ，您就可以将构造分解为浮点操作，并且您可以负担一个最终的不​​精确操作。

不幸的是，浮点运算很快就会变得不精确，当你超过尾数的精度时，结果会被四舍五入。一旦引入了舍入“错误”，它将在进一步的操作中累积......
所以，一般来说，不，你不能使用这种幼稚的算法来转换任意小数，这可能会导致不正确的舍入数字，相差几个正确的 ulp，就像其他人已经告诉你的那样。

但让我们看看我们能走多远：

如果您像这样仔细重建浮点数：

if(biasedExponent >= 0)
    return integerMantissa * (10^biasedExponent);
else
    return integerMantissa / (10^(-biasedExponent));

在累积整数尾数（如果它有很多位）以及将 10 提高到biasedExponent 的幂时，都存在超过精度的风险......

幸运的是，如果前两个运算是精确的，那么您可以承受最终的不精确运算 * 或 /，这要归功于 IEEE 属性，结果将被正确舍入。

让我们将其应用于精度为 24 位的单精度浮点数。

10^8 > 2^24 > 10^7

注意 2 的倍数只会增加指数而尾数保持不变，我们只需要处理 5 的幂即可获得 10 的幂：

5^11 > 2^24 > 5^10

不过，您可以在 integerMantissa 中提供 7 位精度和 -10 到 10 之间的 biasedExponent。

双精度，53 位，

10^16 > 2^53 > 10^15
5^23 > 2^53 > 5^22

所以你可以负担得起 15 个十进制数字，以及 -22 和 22 之间的有偏指数。

看你的数字是否总是在正确的范围内由你决定......（如果你真的很棘手，你可以通过插入/删除尾随零来安排尾数和指数的平衡）。

否则，您将不得不使用一些扩展精度。
如果您的语言提供任意精度整数，那么要正确处理它有点棘手，但并不难，我在 Smalltalk 中做了这个，并在http://smallissimo.blogspot.fr/2011/09/clarifying-and -optimizing.html和http://smallissimo.blogspot.fr/2011/09/reviewing-fraction-asfloat.html

请注意，这些都是简单而幼稚的实现。幸运的是，libc 更加优化。

于 2012-07-28T23:58:42.467 回答
1

我的第一个想法是仅使用尾数的前 18 位将字符串解析为int64尾数和int十进制指数。例如，1.2345e-5 将被解析为 12345 和 -9。然后我会继续将尾数乘以 10 并递减指数，直到尾数长 18 位（>56 位精度）。然后我会在表格中查找十进制指数以找到一个因子和二进制指数，可用于将数字从十进制 n*10^m 转换为二进制 p*2^q 形式。这个因素是另一个因素，int64所以我将尾数乘以它，这样我就得到了结果 128 位数字的前 64 位。该int64尾数可以转换为仅损失必要精度的浮点数，并且可以使用乘法应用 2^q 指数而不会损失精度。

我希望这是非常准确且非常快速的，但您可能还想处理特殊数字 NaN、-infinity、-0.0 和无穷大。我没有考虑过非规范化数字或舍入模式。

于 2012-06-28T22:38:30.050 回答
0

为此，您必须了解标准 IEEE 754 才能获得正确的二进制表示。之后，您可以使用Float.intBitsToFloat或Double.longBitsToDouble。

http://en.wikipedia.org/wiki/IEEE_754

于 2008-09-17T17:00:03.057 回答
0

如果您想要最精确的结果，您应该使用更高的内部工作精度，然后将结果下转换为所需的精度。如果您不介意一些 ULP 错误，那么您可以根据需要以所需的精度重复乘以 10。我会避免使用 pow() 函数，因为它会为大指数产生不精确的结果。

于 2008-09-17T17:03:25.920 回答
0

在不损失精度的情况下，不可能将任何表示数字的任意字符串转换为双精度或浮点数。有许多小数可以精确地用十进制表示（例如“0.1”），只能用二进制浮点数或双精度数来近似。这类似于分数 1/3 不能用十进制精确表示，你只能写 0.333333...

如果您不想直接使用库函数，为什么不查看这些库函数的源代码呢？你提到了Java；大多数 JDK 附带类库的源代码，因此您可以查看 java.lang.Double.parseDouble(String) 方法的工作原理。当然，像 BigDecimal 这样的东西更适合控制精度和舍入模式，但你说它需要是浮点数或双精度数。

于 2008-09-17T17:09:57.790 回答
-1

使用状态机。这很容易做到，即使数据流被中断也可以工作（您只需要保留状态和部分结果）。您还可以使用解析器生成器（如果您正在做更复杂的事情）。

于 2008-09-17T16:51:20.423 回答
-1

我同意终点站。状态机是完成这项任务的最佳方式，因为有许多愚蠢的方式可以破坏解析器。我现在正在研究一个，我认为它已经完成了，我认为它有 13 个州。

问题不是微不足道的。

我是一名对设计浮点硬件感兴趣的硬件工程师。我正在进行第二次实施。

我今天发现了这个http://speleotrove.com/decimal/decarith.pdf

第 18 页给出了一些有趣的测试用例。

是的，我读过 Clinger 的文章，但作为一个头脑简单的硬件工程师，我无法理解所提供的代码。Knuth 的文章中提到的 Steele 算法对我很有帮助。输入和输出都有问题。

上述对各种文章的所有引用都非常出色。

我还没有在这里注册，但是当我这样做时，假设没有登录，那就是兄弟。（兄弟点）。

克莱德

于 2009-08-07T23:28:05.420 回答