R..*_*R.. 32 c algorithm math floating-point
首先,这不是浮点新手问题.我知道浮点运算的结果(更不用说超越函数)通常不能准确表示,并且大多数终止小数不能完全表示为二进制浮点数.
也就是说,每个可能的浮点值完全对应于一个二元有理数(一个有理数p/q,其中q是2的幂),而这又有一个精确的十进制表示.
我的问题是:你如何有效地找到这个精确的十进制表示？sprintf类似的函数通常只指定多个有效数字来唯一确定原始浮点值; 它们不一定打印精确的十进制表示.我知道我使用过的一种算法,但它很慢,指数O(e^2)在哪里e.这是一个大纲:
这真的是最好的吗？我对此表示怀疑,但我不是浮点专家,我无法找到一种方法对数字的浮点表示进行基数10计算,而不会遇到不精确结果的可能性(乘以或除以除了你知道你有空闲位之外,除了2的幂之外的任何东西都是浮点数的有损操作.
Gre*_*erg 35
这个问题有一个官僚部分和一个算法部分.浮点数在内部存储为(2 e ×m),其中e是指数(本身是二进制),m是尾数.问题的官僚部分是如何访问这些数据,但R.似乎对问题的算法部分更感兴趣,即将(2 e ×m)转换为十进制形式的分数(a/b).几种语言的官僚问题的答案是"frexp"(这是我今天之前不知道的有趣细节).
确实,乍一看,O(e 2)工作只需要用十进制写2 e,并且尾数的时间更长.但是,由于Schonhage-Strassen快速乘法算法的神奇之处,你可以在Õ(e)时间内完成它,其中波浪线意味着"达到记录因子".如果你认为Schonhage-Strassen是神奇的,那么想想该做什么并不难.如果e是偶数,则可以递归计算2 e/2,然后使用快速乘法对其进行平方.另一方面,如果e是奇数,你可以递归计算2 e-1然后加倍.您必须小心检查基础10中是否存在Schonhage-Strassen的版本.虽然没有广泛记录,但可以在任何基础上完成.
将非常长的尾数从二进制转换为基数10并不是完全相同的问题,但它有类似的答案.您可以将尾数分成两半,m = a 2 k + b.然后递归地将a和b转换为基数10,将2 ^ k转换为基数10,并进行另一次快速乘法以计算基数10中的m.
所有这些背后的抽象结果是你可以在Õ(N)时间内将整数从一个基数转换为另一个基数.
如果问题是关于标准的64位浮点数,那么它对于花哨的Schonhage-Strassen算法来说太小了.在此范围内,您可以使用各种技巧来保存工作.一种方法是将2e的所有2048个值存储在查找表中,然后在尾数中使用不对称乘法(在长乘法和短乘法之间).另一个技巧是在基数10000(或10的更高功率,取决于架构)而不是基数10工作.但是,正如R.在评论中指出的那样,128位浮点数已经允许足够大的指数调用询问查找表和标准长乘法.实际上,长乘法是最快的数字,然后在很大的中等范围内可以使用Karatsuba乘法或Toom-Cook乘法,然后Schonhage-Strassen的变化最好不仅在理论上而且在实践中.
实际上,大整数包GMP已经具有Õ(N)时基数转换,以及选择乘法算法的良好启发式.他们的解决方案和我的解决方案之间的唯一区别是,它不是在基数10中进行任何大算术,而是在基数2中计算10的大功率.在这个解决方案中,它们还需要快速除法,但这可以从任何快速乘法中获得.几种方式.
Ric*_*gan 16
我已经看到你已经接受了一个答案,但是这里有一些你可能想要看到的转换的开源实现:
David Gay的dtoa()职能dtoa.c(http://www.netlib.org/fp/dtoa.c).
glibc ___printf_fp()文件/stdio-common/printf_fp.c中的函数(例如http://ftp.gnu.org/gnu/glibc/glibc-2.11.2.tar.gz).
两者都会打印出你在一个%f类型中要求的数字printf(正如我在这里所写的那样:http://www.exploringbinary.com/print-precision-of-dyadic-fractions-varies-by-language/和http ://www.exploringbinary.com/print-precision-of-floating-point-integers-varies-too/).
打印浮点数方面已经做了很多工作.黄金标准是打印出最小长度的十进制等效值,这样当读回十进制等效值时,无论回读期间的舍入模式如何,都会得到相同的浮点数.您可以在Burger和Dybvig的优秀论文中了解该算法.