Tag Archives: Grisu

浮点数知识及Grisu算法介绍

进入研究生生涯完成的第一个新生培训作业是“2.5亿个浮点数的外部排序算法”,前后折腾了将近一个月,结果是在i7处理器上,限制512MB内存,排序用时250秒左右。

这个作业的常规思路大部分人都能想到,按块读取文件->atof转换为double->内部快速排序或基数排序->dtoa转换为char*->按块写入文件。这里面中间的三个过程都很耗时,特别是atof和dtoa,因为精度只要求保留9位小数,所以可以自己实现atof和dtoa来加速,也可以使用多线程加速。

整个作业都是基于对IEEE754浮点数的深刻理解展开的,所以下面详细讲解浮点数的一些知识。

IEEE754双精度浮点数

目前大多数CPU内浮点数的表示都遵循IEEE754标准,IEEE754双精度浮点数(double)表示如下图所示。

IEEE754 double在内存中的形式[1]

IEEE754 double在内存中的形式[1]

Continue reading