|
之前在看 lua 源码的时候，看到一处浮点数转整数的方法，当时确实吓我一跳，后来在网上搜索了才知道浮点数原来还有这么神奇的地方，我看到一篇喜欢的文章，翻译一下（英文一般还请见谅），大家要闲着没事可以看看，先贴出 lua 中的转换方法。
/*
@@ lua_number2int is a macro to convert lua_Number to int.
@@ lua_number2integer is a macro to convert lua_Number to lua_Integer.
** CHANGE them if you know a faster way to convert a lua_Number to
** int (with any rounding method and without throwing errors) in your
** system. In Pentium machines, a naive typecast from double to int
** in C is extremely slow, so any alternative is worth trying.
*/
// 这是这个文件最trick的地方，把一个double数转换成long，用到了神奇的数字6755399441055744.0
/* On a Pentium, resort to a trick */
#if defined(LUA_NUMBER_DOUBLE) && !defined(LUA_ANSI) && !defined(__SSE2__) && (defined(__i386) || defined (_M_IX86) || defined(__i386__))
union luai_Cast { double l_d; long l_l; };
#define lua_number2int(i,d) { volatile union luai_Cast u; u.l_d = (d) + 6755399441055744.0; (i) = u.l_l; }
#define lua_number2integer(i,n) lua_number2int(i, n)
/* this option always works, but may be slow */
#else
#define lua_number2int(i,d) ((i)=(int)(d))
#define lua_number2integer(i,d) ((i)=(lua_Integer)(d))
#endif
上面用到了一个神奇的数字 6755399441055744.0，通过把一个 double 类型的数加上这个数字再直接拿来用就是整型了。这个真心让我惊奇。于是我马上在我的 vs 里写了个测试了一下，结果同样令我心惊： 
可以看到我用 8.75 作为测试的 double 数，结果经过 lua 这个宏转换的结果是 9，其实当我把数改成 8.45 时，结果是 8，正好是转换成整数的结果。那么 6755399441055744.0 这个神奇的数字到底是哪里来的呢？ 我打开计算器看了一下，发现这个 6755399441055744.0 是 1.5 * 2^52，既然是这么个特殊的数，我们知道在 IEEE 754 里规定双精度浮点数是 64 位，而其中符号位占 1 位，指数部分是 11 位，那么尾数部分就是 52 位，那么这个 1.5 * 2^52 会不会跟这个有关呢？网上一搜看到篇文章，这里翻译了一下，有兴趣了解的朋友可以看看，我这里把文章的意思总结一下，大体意思就是说在做浮点数加减法的时候有这么几个步骤： 1、对阶 （就是使两个浮点数的两个指数部分相同，规定小数向大数对齐，因为如果是大数向小数对齐，那么就要左移大数的尾数部分，就有可能会丢失大数的最高有效位；小数向大数对齐是右移小数的尾数部分，而丢失小数的那点精度对结果来说是无关紧要的） 2、尾数相加 （为什么是相加而不是相加减，因为减法被转成加法做了，这个应该好理解，计算机里只有累加器） 3、对结果规格化 （这个可能比较生疏，其实也很好理解，就像我们十进制的科学记数法一样，我们规定尾数为 [1, 10) 之间的数,二进制里面我们如果尾数不是 1 开头，我们就移动成 1 开头，然后省去存 1，比如计算结果尾数为 0010，那么我就把尾数左移 3 位得到 1000， 然后省去 1，只存 000，当然这个过程指数也会变） 4、舍入处理 （这个不多说，就那个意思）
下面来说这个 6755399441055744.0 的来历，我们利用的就是“对阶”的过程，如果我们把一个双精度浮点数加上 1.5 * 2^52，因为双精度浮点数的尾数部分正好是 52 位，那么在进行对阶的时候，我们想要转换的浮点数如果比 1.5 * 2^52 小，那么就会向 1.5 * 2^52 对齐，对齐的方法我上面也说了， 就是右移小数的尾数，而这里需要右移 52-目标数的指数位数，正好把目标数的所有小数部分全部移掉了，我们这里忽略舍入过程，只理解这个数的来源。那如果目标数比 1.5 * 2^52 大呢？呵呵，不用比 6755399441055744.0 大就会失败，为什么呢？因为我们这里的目的本来就是把 double 转换成 long，而 long 的范围是 （32位数）-2147483648 ~ 2147483647，远没有到 6755399441055744.0 这么大，所以这个转换的隐含条件还包括了一个 long 的范围在这里。其实根据这个方法看，只要求 long 的范围在 2^52 的规模以下就行。 为了更好的理解这个过程，我们来看一下这个转换的二进制的过程（这里的二进制表示没有对指数域做偏置，在标准 IEEE 中会进行偏置，想了解什么是偏置可以看看下面我翻译的那篇文章或者参考 IEEE 754 标准）： 
了解了浮点数的各种特性之后，你就可以随心所欲了，比如马上就可以知道单精度浮点数也可以有这么一个数字，对，单精度浮点数的这个数字是 1.5 * 2^23。当然，你还可以设计出非常有意思的一些转换，不过总体还是根据浮点数的结构来。 比如这个地方的 magic number 不一定必须是 1.5 * 2^52 ，看懂了我上面这张图的人应该都能看出来，其实这个神奇数字是有限的，他要满足2个条件，一个是它必须是一个大于 1 * 2 ^ 52 的数，同时必须要小于 1 * 2 ^ 53。这样才能保证正好把目标数的尾数部分全部移除；另一个条件是这个数的尾数部分必须没有用到 double 类型的低 32 位，因为这样才能保证最后做 long 转换的时候取到的正好是目标数的整数部分，否则就乱了。这里还有一个隐含条件我没有说，就是要保证这个 magic number 尾数部分 32 位之前的那些位必须至少要有一个 1，因为这样才能保证当目标数是负数的运算正确性，这个我就不解释了，你仔细分析一下，像我上面那张图一样手动做一下负数的取整操作就明白了，如果还不明白也可以看我下面翻译的文章，里面虽然说到了，但是没有解释清楚，我还是建议你手动做一下会理解更加深刻。那么这样一来，我就可以罗列出所有跟 6755399441055744.0 一样的 magic number了。下面我列了一些供大家参考： ( 1 + 2 ^ ( -20 ) ) * 2 ^ 52 ( 1 + 2 ^ ( -19 ) ) * 2 ^ 52 ………… ( 1 + 2 ^ ( -1 ) ) * 2 ^ 52 —— 这个就是 6755399441055744.0 ( 1 + 2 ^ ( -20 ) + 2 ^ ( -19 ) ) * 2 ^ 52 …………
准确来说，这样的魔法数字总共有 2 ^ 20 - 1，唯一排除的一个就是尾数部分前 20 位全部为 0 的情况，这种情况也仅仅只是因为对负数不成立罢了。你完全可以写一个简单的程序把所有这些数都列举出来，这样一来，这个神奇的魔法数字也显得不那么特殊了。欢迎大家和我讨论。 Lua ：luaconf.h
Let’s Get to the (Floating) Point 来源：http:///images/f/fb/Gdmfp.pdf 作者： Chris Hecker
引子：
问：浮点数运算生来就是邪恶的吗？
答：也许不是，只要现代计算机的芯片中指令的时序是可以被信任的。
问：但是，他们可以被信任吗？ 当我坐下来写这篇文章的时候，这将会是我们那史诗般的“透视校正的纹理贴图”系列最后一次被安装了。鉴于此，我意识到我需要去写一篇真正关于浮点数优化的文章，来作为我们在“透视校正的纹理贴图”中所做优化的结尾。所以，我们首先将学到一些非常酷的技巧，并在下一个话题中把他们应用到我们的纹理贴图系统中去。事实上，这些技术适用于任何在混合了浮点数运算和整数运算的现代处理器上运行的高性能系统。当然，这些技术是否适合于所有的游戏，而无论它们是否使用了贴图技术，这个就仁者见仁智者见智了。 真实的故事
几年前，你不能用“一个混合了浮点数和整数运算的应用”来描述一个游戏软件，因为那时没有游戏使用浮点数。事实上，自从个人计算机出现以来，浮点数一直都是慢的象征。当时想玩游戏，你必须去买一个浮点数的协处理器，然后自己动手把它安装在主板上。这并非是游戏开发者不愿意使用真正的浮点数运算，在当时，PC 机处理整数运算已经有一大堆麻烦了，更别谈去处理浮点数了。
我们没有大量的篇幅来回忆整数运算是如何过渡到定点数运算，最后到浮点数运算的（举个简单的例子大家就明白了，比如 Bresenham 直线算法，这里我就做个总结：在很长一段时间里，游戏开发者只在使用高级语言设计算法原型的时候使用浮点数运算。一旦原型写好了，程序员为了提高运算速度在真正的实现代码里通常把浮点数转换成定点数。近年来，我们能够看到，浮点数运算的速度已经追上了整数和定点数，甚至在某些方面还超过了它们。
为什么会这样呢，让我们来看一下那些被游戏开发人员使用最多的算术运算（加减乘、以及希望极少使用的除法）对于定点数、整数、浮点数有什么不同周期时序。表1 显示了在第三代 Intel 处理器上、PowerPC 604、一个现代 MIPS 这三种平台上不同的周期时间。我们从中可以看出加减法浮点数操作的期望确实比整数更快（386，如果不集成浮点数元算单元的话其实不算一个高级处理器，落后其他处理器太多了；处于过渡期的 486 表现中等）。 
当然了，纯粹看数字也说明不了全部的情况。比如这个表并没有说明，尽管多个周期肯定比单个周期的指令要慢，比如整数的加法。但是你在执行一条长时间的浮点数操作的同时，经常会同时执行其他的整数运算指令。关于这个周期重叠的问题不同的处理器情况也不一样，但是对于一些耗时非常长的指令，比如浮点数的除法，经常是整个执行周期和整数操作指令的执行（甚至是浮点数操作指令）都重叠而不是只有一些。与之相反，在当前的 Intel 处理器上一条耗时很长的整数指令执行时，却无法同时执行别的指令，其他的处理器一般也都有所限制。
还有一点需要注意，就是浮点数操作并不像表中显示的那样快，因为在进行操作之前，还需要加载这些操作数到浮点数运算单元中去，然而浮点数的加载和存储通常来说比整数要慢一些。更糟糕的是，把浮点数转换成整数的指令通常更加慢。事实上，尽管浮点数指令的运算时间其实比同类型的整数操作要快，但 486 上浮点数加载、存储、转换的开销已经让我们有理由为了速度而使用定点数了。
但是今天，我们在这篇文章里涉及到的技巧和技术将会给是浮点数运算以及定点数运算带来无可匹敌的速度上的优势。 如果它不是浮点数，不要修复它
跟往常一样，我将假设在讨论这个话题之前你已经知道了定点数是如何运作的了。从数学上讲，一个定点数是一个实数乘以一个固定规模的正整数，然后移除结果的小数部分获得的。这个整数的规模有一部分是原实数的小数部分编码得到的最小有效位。这也是为什么这么多年来定点数作为实数系统的一个选择。一旦我们确定了范围，那么我就可以在只有极少数需要格外处理的情况下使用更快的整数操作。但是定点数在大多数情况下，有很多问题和一堆特殊情况需要处理，你必须非常小心的避免上溢和下溢的发生。而且这些以前所谓的更快速的整数操作在现在也没有浮点数操作快了。
浮点数运算是一件轻松的事情，它背后的主要思想是牺牲一些精度来换取数的范围。（意思就是说比如 64 位的浮点数，精度有 52 位，指数部分有 11 位，还有一位符号位）
现在，让我们忘掉浮点数，来想象一下我们有一个很巨大的二进制定点数，它有很多位整数部分和小数部分。比如有 1000 位整数部分，和 1000 位小数部分，所以我们可以表示一个数大到 2^1000 小到 -2^1000。这个假想的定点数格式有一个巨大的范围和一个非常高的精度，范围的意思是能够表示的最大的数和最小的数的比值，精度的意思是有效数字的位数。所以，我们能够处理在我们模拟星系的系统中那些难以置信的大数，在保持星体间距离的准确性的同时我们也能够计算亚原子的半径。
但是，大多数应用并非是处处都需要这么高的精度。很多应用更多的是需要范围来表示巨大的值，比如星球之间的距离；或者是极小的值，比如原子之间的距离。但是通常不需要表示确切的数在处理两个不同规模的数的时候。
浮点数利用了这个精度和范围在使用上的差异，在存储的时候仅仅用了很少的几位就记录下了很大的范围（事实上甚至比我们假想的 2000 位定点数还要大）。浮点数通过把实数的指数和尾数分开存储来达到这个效果。就好像科学表示法一样，一个数比如 2.345*10^35 的尾数是 2.345，指数是 35（有时你也会看到不同的表示方式，但是他们都是等价的）。这个数只有 4 位精度，但是它的范围确实非常的大。
表示数值的精度同样是一件重要的事情。当指数是 35 时，改变第一位数字将按照 10^35 的规模来改变这个数，但是当指数为 0 时，改变第一位数字仅仅只按 1 的规模来改变。这个方法让你在处理“埃米”级别（纳米的十分之一）的规模的时候能够获得“埃米”级别的精确度，对于星系规模来说也是一样。
IEEE 浮点数标准规定了浮点数的表示方法以及如何操作浮点数。其中 IEEE 规定的浮点数格式中我们关心的只有两种：单精度浮点数和双精度浮点数。它们使用相同的转换方程来把二进制浮点数表示变成实数表示。你会发现它就像是一个二进制的科学记数法： 
单精和双精这两种格式唯一不同的地方是上面这个格式中一些值的范围。所以我们接下来会按照顺序指出每个部分的不同点。
我们从上面格式的右手侧开始。尾数表示方法（1.mantissa）在第一次看的时候略显奇怪，但是当你意识到它是一个二进制数的时候时候就会觉得它清晰了一点。你同时也应该意识到这是一个规范的二进制数。“规范”在科学表示法里意思是尾数是大于等于 1 且小于 10（换句话说是一个不包括 0 的一位数）。我们上面那个科学表示法的例子 2.345*10^35 就是规范的，而 234500*10^30 就不规范。 一个规范的二进制数意思就是它会移动它的数位直到最高位为 1。仔细想想这个概念的意思。（001011 - > 1011）如果这个二进制数有前导 0，那么我们能够用指数的一部分来表示它们，就像我们在十进制科学记数法中所做的一样。因为最高位始终为 1，所以我们能够免去存储这个 1，把它作为我们这种表示法的一种默认值就可以了。就像十进制科学记数法中保持尾数部分在 1 到 10 之间一样，二进制浮点数的尾数在 1 到 2 之间（大于等于 1 小于 2）。
接下来，二进制指数的小数点是向左移还是向右移取决于指数是正还是负。这跟十进制科学记数法类似，当指数的小数点移动的时候，就补 0。指数域位数相同的浮点数比定点数有范围表示上的优势。其实定点数有一个隐含的小数点而它的所有位数其实都是指数，浮点数通过保存指数域来移动二进制小数点（这也就是浮点的意思）。如果用 8 位来保存指数，那么一个 32 位数能够表示的范围就是 2^127 到 2^-127，而最好的定点数仅仅能表示 2^32 到 0 和 2^16 到 2^-16 或者是 0 到 2^-32，而且还不能同时表示这两个范围。当然，天下没有免费的午餐，32 位定点数比浮点数的精度更高，因为定点数有 32 位有效数字，而浮点数去掉指数部分后只有 24 位有效数字。
你会注意到 IEEE 标准中指数表达式实际上是一种指数的偏置。偏置的目的是使指数域的值始终为正。换句话说，假设一个 8 位的指数，那么它偏置的值就是 127，如果一个没有偏置的指数是 -126那么偏置后的指数为 1。同样的道理，一个偏置后指数域的值为 254，那么没有偏置的指数就是 127。全 0 和全 1 的指数值保留做无穷和 0 的指数值，当然我们没有足够的值去对应所有的特殊数。
最后，符号位（sign bit）的意思是这个数为正还是为负。不同于二进制补码的表示法，浮点数的正负仅仅由符号位决定。我们后面会谈到这样做的目的。表2 显示了单精度浮点数和双精度浮点数在 IEEE 规定的格式位数，Figure 1 显示了他们的是什么样的，最高有效位就是符号位。 
一个例子
让我们来看一个例子，把一个十进制数转换成一个单精度二进制浮点数。我将用 8.75 举例，因为它比较简单，甚至可以用手写来转换，但是它也能够展现一些复杂的地方。首先，我们将它变成一个二进制定点数—— 1000.11（小数的二进制转换方法），小数部分 .75 就是 2^-1 + 2^-2，所以是 .11。然后，我们把这个二进制数左移 3 位使它规格化，也就是 1.00011 * 2^3。最后，我们通过给指数加 127 来偏置指数，那么指数就是 130（10000010）。那么我们的浮点数尾数部分就是 1.00011，当然，前置 1 是隐式的。我们的数是正的，所以符号位是 0。所以 8.75 最后的二进制浮点数的样子就如 Figure 2 所示，好了，现在我们已经熟悉了浮点数以及它的表示方法，接下来，我们可以学一些技巧了。 
转换
毫不夸张的说，我注意到在某些处理器上浮点数转换成整数相当的慢。在奔腾处理器上，把浮点数转换成整数存下来的指令“FIST”（FIST 指令转换和舍入在堆栈顶 ST(0) 的源值为符号整数并复制它至规定的 16 位或 32 位内存单元。源可以是任一浮点数据类型，包括单精度、双精度或扩展的双精度浮点值。——引至《64位微处理器应用编程》）需要 6 个 CPU 周期，而乘法运算都仅仅只需要 3 个周期，这样你就明白我说的慢是什么意思了。更糟糕的是，FIST 指令同时占据浮点数通道和整数通道，所以其他的指令也没有办法执行。但是这里还有个选择，那就是我们动用我们学过的浮点数知识来写一个我们自己版本的 FIST，并且只需要用到普通的浮点数加法。
在做浮点数加法之前，CPU 需要对齐二进制小数点，小数点不对齐是没办法把尾数相加的。对齐的方法通常是左移较小的数的小数点。举例来说，如果我们想把两个用科学记数法表示的十进制数 2.345 * 10^35 和 1.0 * 10^32 相加，我们把较小的数的小数点左移 3 位来使他们达到同一个级别。然后再相加：2.345*10^35 + 0.001*10^35 = 2.346*10^35。二进制数跟这个道理是一样的。
我们能够利用这种对齐移动的方式来把浮点数位数表示弄的跟整数位数表示的一样，然后我们就可以像普通整数那样加了。理解这个的关键在于我们想要的整数已经存在于浮点数的位数中了，但是它被规范化了，所以移动它尾数部分的前导位，比如 8.75，就像 Figure 2 显示的那样。整数部分 8 是隐式的那一位加上尾数部分前面 3 个 0 组成的。尾数部分接着的 11 是二进制 .75 的小数部分，等着转换成一个定点数。
想象一下当你把 2 个浮点数相加时，比如 2^8 = 256 加到 8.75，如 Figure 3。为了做这个加法，因为指数不相同，所以 CPU 会左移 5 位 8.75 的二进制小数点（8 - 3 = 5）。加法把 256 隐含的那一位加到了小数点对齐之后的 8.75 中，然后当结果做了规范化之后，在 256 中隐含的那一位仍然是隐含的，所以 8.75 就下移了。你在 Figure 3 的结果尾数部分可以看到 8.75。那当我加 233 时呢，或者加跟尾数的宽度一样大的数呢？就像你想的那样，8.75 的尾数会移动 23 - 3 = 20 位，只留下1000，这个的值是 8（因为 .75 被我们移除掉了，单精度浮点数的尾数只有 23 位，虽然这个时候舍入模式就会生效，但是为了简化，我们这里假设舍入为 0）。如果我们盖住符号位和指数部分，直接读尾数部分，那么我们就得到了把 8.75 转换成整数的结果 8。 
这个技巧只对正数有效，如果你尝试把一个负数转换过来就会发现出错了。你可以通过自己手动操作移位来看看为什么会出错。我发现两个正数相减比一正数一负数相加要容易。比如计算 2^23 + (-8.75)，而 2^23 - 8.75 要容易一些。这是由于符号位的表示方法导致的（用一张纸一支笔你可以看得更加清楚）。所以，当你在做减法的对齐的时候，8.75 减去一个大的尾数，如果所有位都为 0 了，就会从那个隐含的位借一。这个最初看起来不错，尾数是正确值 -8.75，但是执行规范化步骤之后，整个数就乱了，因为我们从隐含位借了 1，那么这个隐含位就不再是最高有效位了，所以规范化的操作移动整个数之后，这个数就乱了。
但是，等等，好像并非全乱了。我们需要的其实只是一位尾数让我们可以借位罢了，这样我们那个隐含位仍然保留并正确移动。我们可以通过乘以 1.5 来实现这个多出的一位，1.5 在二进制中是 1.1，那么第一个 1 就成为隐含位，第二个 1 就变成了尾数的最高有效位拿来借位。这样，无论是正数还是负数的规范化操作都能够正确的进行了。负数就在最高位加 1 来完成二进制补码的表示。
当你仅处理一两个正数和负数时，计算掩码已经够麻烦了，更别谈你想要透明的进行这种处理，计算如何使用掩码对于高位数来说非常缓慢。但是，这里也有一个小技巧。如果你把这个浮点数减去我们刚刚用上面转换成整数方法得到的那个整数，那么就会正确的移除掉所有的高位，正数就置 0，负数就置 1。 你会发现这个技巧只使用到了 32 位中的一部分，因为还有指数部分和符号位。并且当我们使用“1.5”的小技巧时，我们还会失去额外的一位来确保正数和负数同样适用。但是，我们可以通过使用一个双精度数来作为暂时的转换这样就可以避免范围问题和掩码问题。如果我们做加法时把我们的数当作一个双精度类型（确保在做整数转换时加的值是 1.5 * 2^52）并且只读取最低的 32 位有效数字作为整数，我们就得到了一个 32 位精度的数并且不需要使用掩码。因为指数部分和符号位移到了双精度值的第二个 32 位中。
总之，在做整数转换时我们可以通过加一个大数来控制怎么去移动对齐。我们一直移位直到只保留整数部分，或者可以移动一定值保留一定的小数精度。
使用这些技巧看起来确实麻烦，但是在一些处理器上，像 X86 系列，这会带来很大的不同。在奔腾处理器上使用 FIST 指令，你需要 6 个 CPU 周期，在此之间你无法执行任何其他的指令。但是使用这个加法的技巧，你就可以节省出 3 个周期来进行别的整数指令的运行。你同时能够控制有多少位小数精度而不是一味的全部转换成整数。 你的观点呢？
在我做总结之前，我想告诉你一些别的技巧，来供你做判断做不做这些改变。对指数做偏置是因为这样在做两个数的比较的时候更加方便。指数永远是正的，这样一个大数比一个小数要大在比较指数部分的时候就已经确定了。符号位的存在导致比较更加麻烦，但是单符号值却没有问题。当然，你可以移除符号位来取得浮点数的绝对值。
我已经非常接近最酷的技巧了，这个技巧就是在做坑爹的除法的时候重叠整数指令的运行。但是我没有深入探讨这个话题，这个就要等到下一次了。
最后作者推荐了一些读物： The Art of Computer Programming, Vol. 2: Seminumerical Algorithms (Addison-Wesley, 1981) by D.Knuth
Graphics Gems series from AP Professional
|
