如何从字符串中手动解析浮点数

StackOverflow https://stackoverflow.com/questions/85223

题

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

假设浮点数的给出方式类似于 C 或 Java 程序（“f”或“d”后缀除外），例如“4.2e1", ".42e2“或者简单地”42”。一般来说，我们有小数点前的“整数部分”，小数点后的“小数部分”，以及“指数”。这三个都是整数。

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

我正在考虑将整数部分乘以 10^n, ， 在哪里 n 是小数部分的位数，然后将小数部分与整数部分相加并减去 n 从指数。这有效地转变了 4.2e1 进入 42e0, ， 例如。然后我可以使用 pow 计算 10^ 的函数指数 并将结果与​​新的整数部分相乘。问题是，这种方法能否保证始终达到最大精度？

对此有什么想法吗？

有帮助吗？

解决方案

我将使用其二进制表示形式直接组装浮点数。

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

现在您可以组装浮点数了。要做的第一件事是扫描数字的整数表示形式以查找第一组一位（从最高到最低）。

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

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

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

将指数原样存储到浮点数的第 24 到 30 位中。

最重要的位就是符号。1 表示负数，0 表示正数。

描述起来比实际情况更难，尝试分解浮点数并查看指数和尾数，您就会发现它实际上是多么容易。

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

其他提示

所有其他答案都错过了如何 难的 就是要正确地做到这一点。您可以对此进行第一次切割方法，该方法在一定程度上是准确的，但是除非您考虑 IEEE 舍入模式（等），否则您将永远不会有 正确的 回答。我之前写过幼稚的实现，但有相当多的错误。

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

我最好的建议是从一个有效的 atoi 实现开始，然后从那里开始。你很快就会发现自己错过了一些东西，但只要看几眼 斯特托德的来源，你就会走在正确的道路上（这是一条很长很长的路）。最终你会赞叹 在此插入饮食 有标准库。

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

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

Burger 和 Dybvig 中找到了另一种算法，即从浮点数中打印出最佳的十进制数 快速准确地打印浮点数,可下载 这里. 。这也需要多精度整数运算

另请参阅大卫·M·盖伊 (David M Gay) 的 正确舍入的二进制-十进制和十进制-二进制转换 对于双向算法。

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

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

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

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

无论如何，祝你好运！

是的, ，您可以将构造分解为浮点运算 只要 这些操作是 精确的, ，你可以买得起 单最终不精确 手术。

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

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

如果你像这样仔细地重建浮动：

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

如果整数尾数有很多位，则在累积该整数尾数时，以及在计算 10 的biasedExponent 次方时，都存在超出精度的风险...

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

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

10^8 > 2^24 > 10^7

请注意，2 的倍数只会增加指数并保持尾数不变，因此我们只需处理 10 的幂的 5 次方：

5^11 > 2^24 > 5^10

不过，您可以在整数尾数中提供 7 位精度，并在 -10 和 10 之间提供偏置指数。

以双精度，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 更加优化。

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

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

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

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

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

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

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

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

我同意终点站的观点。状态机是完成此任务的最佳方法，因为有许多愚蠢的方法可以破坏解析器。我现在正在开发一个，我认为它已经完成，并且我认为它有 13 个状态。

这个问题并非微不足道。

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

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

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

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

所有上述对各种文章的参考都非常好。

我还没有在这里注册，但是当我注册时，假设没有登录，那将会是兄弟。（布罗点）。

克莱德

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top