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

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

How to manually parse a floating point number from a string

当然,大多数语言对此都有库函数,但是假设我想自己做。

假设以C或Java程序的形式给出浮点数(" f"或" d"后缀除外),例如" 4.2e1"," .42e2"或简称为" 42"。通常,我们在小数点前有"整数部分",在小数点后有"分数部分",以及"指数"。这三个都是整数。

查找和处理单个数字很容易,但是如何在不损失精度的情况下将它们组合为类型为floatdouble的值?

我正在考虑将整数部分与10 ^ n相乘,其中n是小数部分中的位数,然后将小数部分加到整数部分,然后从指数中减去n。例如,这有效地将4.2e1变为42e0。然后,我可以使用pow函数计算10 ^指数,然后将结果与新的整数部分相乘。问题是,这种方法是否始终保证最高的精度?

有什么想法吗?


所有其他答案都错过了正确执行此操作的难度。您可以在某种程度上做到这一点,但这种方法在某种程度上是准确的,但是除非考虑到IEEE舍入模式(等),否则您将永远找不到正确的答案。我之前写过一些幼稚的实现,但有很多错误。

如果您不害怕数学,我强烈建议您阅读以下由David Goldberg撰写的文章,《每位计算机科学家应该了解的浮点算术》。您将更好地了解引擎盖下发生的事情以及这些位为何如此布置。

我最好的建议是从可行的atoi实施开始,然后从那里实施。您会迅速发现自己缺少的东西,但是有一些人看着strtod的来源,您将走在正确的道路上(这是一条漫长的道路)。最终,您会赞叹在这里插入Diety,因为这里有标准库。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/* 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的"快速,准确地打印浮点数"中可以找到从浮点数打印最佳十进制数的另一种算法,可在此处下载。这也需要多精度整数运算

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


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

依次读入一个数字,然后首先找到所有数字。用整数算术做到这一点。还要跟踪小数点和指数。这一点以后很重要。

现在,您可以汇编您的浮点数了。首先要做的是扫描数字的整数表示形式,以找到第一个设置的一位(最高到最低)。

第一个后跟的位是尾数。

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

此指数应在0到255的范围内。如果它更大或更小,则表示正数或负数为无穷大(特殊情况)。

将指数存储在浮点数的第24至30位中。

最重要的一点就是符号。一表示负数,零表示正数。

很难描述它,而不是真正地描述它,尝试分解浮点数并查看指数和尾数,您会发现它实际上是多么容易。

顺便说一句-在浮点数中进行算术运算本身不是一个好主意,因为您将始终迫使尾数被截断为23个有效位。这样您将无法获得确切的表示。


是的,您可以将构造分解为浮点运算,只要这些运算是精确的即可,并且您可以负担一个最终的不??精确运算。

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

但是,让我们看看如何可以:

如果您像这样仔细地重构浮点数:

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

累积整数位数(如果有很多数字时)以及将10提高到biasedExponent的幂时都有风险超过精度

幸运的是,如果前两个操作正确无误,那么您可以负担最终的不精确操作*或/,这要归功于IEEE属性,结果将正确舍入。

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

1
10^8 > 2^24 > 10^7

注意2的倍数只会增加指数,而尾数保持不变,我们只需要对5的幂进行幂运算即可得到10的幂:

1
5^11 > 2^24 > 5^10

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

以双精度53位

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

因此,您可以负担15个十进制数字,以及介于-22和22之间的有偏指数。

由您自己决定是否将数字始终落在正确的范围内……(如果您真的很棘手,则可以通过插入/删除尾随零来安排尾数和指数的平衡)。

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

请注意,这些是简单而幼稚的实现。幸运的是,libc进行了更优化。


您可以在分析时忽略小数点(位置除外)。说输入是:
156.7834e10 ...可以很容易地将其解析为整数1567834,后跟e10,然后将其修改为e6,因为小数点是浮点数"数字"部分末尾的4位数字。

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

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

当然,您可以使用以下方法:将小数点前的每个数字都乘以10,然后将当前总数(以浮点数)乘以10,然后添加新数字。对于小数点后的数字,将数字乘以10的递增幂,然后再添加到当前总数中。但是,此方法似乎引出了您为什么要这样做的问题,因为它需要使用浮点基元而不使用随时可用的解析库。

无论如何,祝你好运!


我的第一个想法是仅使用尾数的前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和infinity。我没有考虑过非规范化数字或舍入模式。


在不损失精度的情况下,不可能将代表数字的任意字符串转换为双精度或浮点型。许多小数可以精确地用十进制表示(例如" 0.1"),只能用二进制浮点数或双精度数近似。这类似于分数1/3不能精确地用十进制表示的方式,您只能写0.333333 ...

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


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


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

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


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

这个问题并不简单。

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

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

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

是的,我已经阅读了Clinger的文章,但是作为一名简单的硬件工程师,我无法理解所提供的代码。 Knuth课文中提到的Steele算法参考对我很有帮助。输入和输出都是有问题的。

前面提到的各种文章的引用都很出色。

我还没有在这里注册,但是当我这样做的时候,假设没有登录,那就很麻烦了。 (点点)。

克莱德


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


推荐阅读

    字符库快捷键|字符串快捷键

    字符库快捷键|字符串快捷键,,1. 字符串快捷键1、单行注释单行注释是 #Mac的快捷键是 command+/windows的快捷键是 Ctrl + /2、多行注

    探探语言设置|探探怎么设置语言

    探探语言设置|探探怎么设置语言,,1. 探探怎么设置语言打开探探软件,然后就有消息提示的红点,点开就行了!其实这些软件都是挺简单的操作的,都是

    git设置编码|git语言设置

    git设置编码|git语言设置,,git设置编码点击cap4j搜索从git直接链接上拉代码。git语言设置Git是一个开源的分布式版本控制系统,可以有效、高

    区域语言设置|区域语言设置工具

    区域语言设置|区域语言设置工具,,区域语言设置工具你好,大致的方法如下,可以参考:1、按下键盘的windows 图标,再开始菜单中单击“设置”;出现的

    c4d语言设置|c4d汉语设置

    c4d语言设置|c4d汉语设置,,1. c4d汉语设置mac版的C4D是这样的,中文字体是有的,但是是以拼音的形式存在,比如黑体就是ht。中文字体以拼音方式

    电脑宣传语|电脑宣传语言

    电脑宣传语|电脑宣传语言,,1. 电脑宣传语言1.我做好了与你过一辈子的打算,也做好了你随时要走的准备,2.每段青春都会苍老,但我希望记忆里的你

    office语言设置|微软office语言设置

    office语言设置|微软office语言设置,,微软office语言设置一、首先点击桌面左下角“WIN键”。二、弹出选项内点击“所有程序”。三、接着点

    小米设置日语|小米设置日语语言

    小米设置日语|小米设置日语语言,,1. 小米设置日语语言MIUI系统文字目前只支持简体中文、繁体中文、英文、藏文和维吾尔文,不支持日文 2. 小