How to manually parse a floating point number from a string当然,大多数语言对此都有库函数,但是假设我想自己做。
假设以C或Java程序的形式给出浮点数(" f"或" d"后缀除外),例如"
查找和处理单个数字很容易,但是如何在不损失精度的情况下将它们组合为类型为
我正在考虑将整数部分与10 ^ n相乘,其中n是小数部分中的位数,然后将小数部分加到整数部分,然后从指数中减去n。例如,这有效地将 有什么想法吗? 所有其他答案都错过了正确执行此操作的难度。您可以在某种程度上做到这一点,但这种方法在某种程度上是准确的,但是除非考虑到IEEE舍入模式(等),否则您将永远找不到正确的答案。我之前写过一些幼稚的实现,但有很多错误。 如果您不害怕数学,我强烈建议您阅读以下由David Goldberg撰写的文章,《每位计算机科学家应该了解的浮点算术》。您将更好地了解引擎盖下发生的事情以及这些位为何如此布置。 我最好的建议是从可行的atoi实施开始,然后从那里实施。您会迅速发现自己缺少的东西,但是有一些人看着strtod的来源,您将走在正确的道路上(这是一条漫长的道路)。最终,您会赞叹在这里插入Diety,因为这里有标准库。
将小数转换为最佳浮点近似值的"标准"算法是William Clinger的"如何准确读取浮点数",可从此处下载。请注意,正确地执行此操作需要至少在一定百分比的时间中使用多个精度整数,以便处理极端情况。 从Burger和Dybvig的"快速,准确地打印浮点数"中可以找到从浮点数打印最佳十进制数的另一种算法,可在此处下载。这也需要多精度整数运算 另请参见David M Gay的正确舍入的二进制-十进制和十进制-二进制转换,以了解双向算法。 我将使用其二进制表示形式直接汇编浮点数。 依次读入一个数字,然后首先找到所有数字。用整数算术做到这一点。还要跟踪小数点和指数。这一点以后很重要。 现在,您可以汇编您的浮点数了。首先要做的是扫描数字的整数表示形式,以找到第一个设置的一位(最高到最低)。 第一个后跟的位是尾数。 获得指数也不难。您可以从科学计数法中知道第一个位,小数点的位置和可选的指数。合并它们并添加浮点指数偏差(我认为是127,但请检查一些参考)。 此指数应在0到255的范围内。如果它更大或更小,则表示正数或负数为无穷大(特殊情况)。 将指数存储在浮点数的第24至30位中。 最重要的一点就是符号。一表示负数,零表示正数。 很难描述它,而不是真正地描述它,尝试分解浮点数并查看指数和尾数,您会发现它实际上是多么容易。 顺便说一句-在浮点数中进行算术运算本身不是一个好主意,因为您将始终迫使尾数被截断为23个有效位。这样您将无法获得确切的表示。 是的,您可以将构造分解为浮点运算,只要这些运算是精确的即可,并且您可以负担一个最终的不??精确运算。
不幸的是,浮点运算很快就会变得不精确,当您超过尾数的精度时,结果会四舍五入。一旦引入了舍入的"错误",它将在进一步的操作中累积... 但是,让我们看看如何可以: 如果您像这样仔细地重构浮点数:
累积整数位数(如果有很多数字时)以及将10提高到biasedExponent的幂时都有风险超过精度 幸运的是,如果前两个操作正确无误,那么您可以负担最终的不精确操作*或/,这要归功于IEEE属性,结果将正确舍入。 让我们将其应用于精度为24位的单精度浮点数。
注意2的倍数只会增加指数,而尾数保持不变,我们只需要对5的幂进行幂运算即可得到10的幂:
不过,您可以在integerMantissa中提供7位精度,并在-10和10之间提供biasedExponent。 以双精度53位
因此,您可以负担15个十进制数字,以及介于-22和22之间的有偏指数。 由您自己决定是否将数字始终落在正确的范围内……(如果您真的很棘手,则可以通过插入/删除尾随零来安排尾数和指数的平衡)。
否则,您将不得不使用一些扩展精度。 请注意,这些是简单而幼稚的实现。幸运的是,libc进行了更优化。
您可以在分析时忽略小数点(位置除外)。说输入是: 精度是一个问题。您需要检查所用语言的IEEE规范。如果尾数(或分数)中的位数大于整数类型中的位数,那么当有人键入以下数字时,您可能会失去精度: 5123.123123e0-在我们的方法中转换为5123123123,这不适合整数,但是5.123123123的位可能适合于float规范的尾数。 当然,您可以使用以下方法:将小数点前的每个数字都乘以10,然后将当前总数(以浮点数)乘以10,然后添加新数字。对于小数点后的数字,将数字乘以10的递增幂,然后再添加到当前总数中。但是,此方法似乎引出了您为什么要这样做的问题,因为它需要使用浮点基元而不使用随时可用的解析库。 无论如何,祝你好运!
我的第一个想法是仅使用尾数的前18位将字符串解析为 我希望这是非常准确且非常快的,但您可能还需要处理特殊数字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算法参考对我很有帮助。输入和输出都是有问题的。 前面提到的各种文章的引用都很出色。 我还没有在这里注册,但是当我这样做的时候,假设没有登录,那就很麻烦了。 (点点)。 克莱德 使用状态机。这很容易做到,甚至在数据流中断的情况下也可以工作(您只需要保留状态和部分结果即可)。您还可以使用解析器生成器(如果您要执行更复杂的操作)。 |