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

parsing floating-point precision

14369 观看

11回复

110172 作者的声誉

当然,大多数语言都有库函数,但我想自己想做。

假设浮点数是在C或Java程序中给出的(除了'f'或'd'后缀除外),例如“ 4.2e1”,“ .42e2”或简单地“ 42”。通常,我们在小数点之前有“整数部分”,在小数点之后有“小数部分”和“指数”。这三个都是整数。

很容易找到并处理各个数字,但是如何将它们组合成类型的值floatdouble不丢失精度?

我想将整数部分乘以10 ^ n,其中n是小数部分中的位数,然后将小数部分添加到整数部分并从指数中减去n。例如,这有效地变成4.2e142e0。然后我可以使用该pow函数来计算10 ^ 指数并将结果与​​新的整数部分相乘。问题是,这种方法是否能保证最高精度?

有什么想法吗?

作者: Thomas 的来源 发布者: 2008 年 9 月 17 日

回应 11


0

6741 作者的声誉

使用状态机。它很容易做到,甚至可以在数据流中断时工作(你只需要保持状态和部分结果)。您还可以使用解析器生成器(如果您正在执行更复杂的操作)。

作者: terminus 发布者: 2008 年 9 月 17 日

0

73670 作者的声誉

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

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

作者: Jorge Ferreira 发布者: 2008 年 9 月 17 日

0

301221 作者的声誉

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

作者: Adam Rosenfield 发布者: 2008 年 9 月 17 日

10

64121 作者的声誉

决定

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

读入一个接一个的字符,首先找到所有数字。在整数运算中执行此操作。还要跟踪小数点和指数。这个将在以后重要。

现在您可以组装浮点数。首先要做的是扫描第一组一位(从最高到最低)的数字的整数表示。

紧跟在第一位之后的位是你的尾数。

获得指数也不难。你知道第一个一位的位置,小数点的位置和科学记数法中的可选指数。合并它们并添加浮点指数偏差(我认为它是127,但请检查一些参考)。

该指数应该在0到255范围内。如果它更大或更小,你有一个正或负无限数(特殊情况)。

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

最重要的一点就是标志。一个意味着消极,零意味着积极。

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

顺便说一句 - 在浮点本身做算术是一个坏主意,因为你总是强迫你的尾数被截断为23个有效位。你不会那样得到精确的表达方式。

作者: Nils Pipenbrinck 发布者: 2008 年 9 月 17 日

1

12508 作者的声誉

解析时可以忽略小数(除了它的位置)。假设输入为:156.7834e10 ...这可以很容易地解析为整数1567834,然后是e10,然后你将修改为e6,因为小数是浮点数“数字”部分末尾的4位数。

精确是一个问题。您需要检查您正在使用的语言的IEEE规范。如果尾数(或分数)中的位数大于整数类型中的位数,那么当有人输入数字时,您可能会失去精度:

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

当然,您可以使用一种方法,将每个数字放在小数前面,将当前总数(在浮点数中)乘以10,然后添加新数字。对于小数点后的数字,在增加当前总数之前,将数字乘以10的增长幂。这个方法似乎提出了为什么你要这样做的问题,因为它需要使用浮点原语而不使用现成的解析库。

无论如何,祝你好运!

作者: billjamesdev 发布者: 2008 年 9 月 17 日

0

4893 作者的声誉

无法将任何表示数字的任意字符串转换为double或float而不会丢失精度。有许多小数可以精确地用十进制表示(例如“0.1”),只能用二进制浮点数或双精度表示。这类似于小数1/3如何不能用十进制精确表示,你只能写0.333333 ...

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

作者: sk. 发布者: 2008 年 9 月 17 日

18

54070 作者的声誉

所有其他答案都错过了正确执行此操作的难度。您可以在此处进行第一次切割,这在某种程度上是准确的,但在您考虑IEEE舍入模式(等)之前,您将永远无法得到正确的答案。我之前写过一些天真的实现,但是有很多错误。

如果您不害怕数学,我强烈建议您阅读David Goldberg撰写的以下文章,即每个计算机科学家应该知道的关于浮点运算的内容。您将更好地了解引擎盖下的内容,以及为什么这些内容都是如此布局的。

我最好的建议是从一个有效的atoi实现开始,然后从那里搬出去。你很快就会发现你错过了一些东西,但是有些人会看到strtod的来源,你会走上正确的道路(这是一条漫长而漫长的道路)。最后,你会赞美插入diety有标准库。

/* 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);
}
作者: user7116 发布者: 2008 年 9 月 17 日

16

2421 作者的声誉

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

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

另请参阅David M Gay的正确舍入二进制 - 十进制和十进制 - 二进制转换,以实现双向算法。

作者: Peter S. Housel 发布者: 2008 年 9 月 29 日

-1

0 作者的声誉

我同意终点。状态机是完成此任务的最佳方式,因为解析器有许多愚蠢的方法可以被破坏。我现在正在研究一个,我认为它是完整的,我认为有13个州。

问题不是微不足道的。

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

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

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

是的,我读过克林格的文章,但作为一个头脑简单的硬件工程师,我无法理解所呈现的代码。在Knuth的文本中对Steele算法的引用对我有帮助。输入和输出都有问题。

所有上述对各种物品的参考都是优秀的。

我还没有在这里注册,但是当我这样做时,假设没有采取登录,它将是布鲁赫。(broh点)。

克莱德

作者: Clyde R. Shappee 发布者: 2009 年 8 月 7 日

1

39063 作者的声誉

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

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

作者: Jon Harrop 发布者: 2012 年 6 月 28 日

1

6342 作者的声誉

是的只要这些操作是完全的,您就可以将构造分解为浮点运算,并且您可以承担单个最终的不​​精确操作。

不幸的是,浮点运算很快变得不精确,当你超过尾数的精度时,结果是四舍五入的。一旦引入了舍入“错误”,它将在进一步的操作中累积...
所以,通常,,你不能使用这种天真的算法来转换任意小数,这可能会导致错误的舍入数字,关闭几个正如其他人已经告诉过你的那个正确的。

但让我们看看我们能够做多远:

如果你像这样仔细重建浮点数:

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

如果累积整数尾数(如果它有多个数字),并且当将10增加到biasedExponent的幂时,则存在超过精度的风险...

幸运的是,如果前两个操作是准确的,那么你可以提供最终的不精确操作*或/,由于IEEE属性,结果将被正确舍入。

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

10^8 > 2^24 > 10^7

注意2的倍数只会增加指数并保持尾数不变,我们只需处理10的幂幂就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.htmlhttp://smallissimo.blogspot.fr/2011/09/reviewing-fraction-asfloat.html

请注意,这些是简单而天真的实现。幸运的是,libc更加优化。

作者: aka.nice 发布者: 2012 年 7 月 28 日
32x32