二进制32位整数快速平方根

liangbch

Intel PM 1.7G L1 Data: 32K, L1 inst: 32K L2 cache: 2048K RAM DDR 1248M case 1: 计算0-65535 1）liangbch的这两个C版本排到第1和第2，iSqt_gxq_c的C版本排到了第3,不过另一个整数版本iSqt_16却是最慢的，在这个CPU上整数的版本快于浮点版本，可能与PM的整数运算能力计较强有关。 2）只有一个版本慢于参考函数。 3）各个函数的实际速度为（按速度排序） iSqt_c1_lbc#: 0.00071 s iSqt_c2_lbc#: 0.00137 s iSqt_gxq_c#: 0.00170 s iSqt_FPU1_lbc#: 0.00220 s iSqt_FPU2_lbc#: 0.00220 s iSqt_FPU2_yaos#: 0.00220 s iSqt_FPU1_yaos#: 0.00290 s iSqt_FPU3_lbc#: 0.00448 s iSqt_FPU_yaos#: 0.00455 s iSqt_GxQ_asm#: 0.00518 s iSqt_ref#: 0.00525 s iSqt_16#: 0.00751 s case 2: 计算0-2^28-1 1）liangbch的第一个版本仍是最快的，在被开方数较大的情况下，iSqt_gxq_c 将 iSqt_c2_lbc 超越成为第2快的版本，而iSqt_c2_lbc则慢于3个浮点版本。 2）iSqt_FPU2_lbc，iSqt_FPU2_yaos，iSqt_FPU1_lbc 性能区别不大，可视为速度基本相同。 2）仍然只有iSqrt_16 慢于参考函数 3）各个函数的实际速度为（按速度排序） iSqt_c1_lbc#: 5.73374 s iSqt_gxq_c#: 7.73133 s iSqt_FPU2_lbc#: 9.20537 s iSqt_FPU2_yaos#: 9.26246 s iSqt_FPU1_lbc#: 9.66667 s iSqt_c2_lbc#: 10.39615 s iSqt_FPU1_yaos#: 12.13651 s iSqt_FPU3_lbc#: 18.79839 s iSqt_FPU_yaos#: 19.12746 s iSqt_GxQ_asm#: 21.65353 s iSqt_ref#: 21.96407 s iSqt_16#: 33.18486 s

liangbch

看了一下iSqrt_gxq_c编译后的代码，每得到1bit的结果仅仅需要6条指令。而我的确是9条指令，当被开方数较大时，iSqrt_c2_lbc 慢于iSqrt_gxq_c 也就可以理解了，gxq这个版本确实很巧妙。 iSqrt_c2_lbc 仍然有改进的余地，现在的iSqrt_c2_lbc可直接得到前4bit初值，如果将平方表增加到256（现在是16项），这样平方表所占用的空间达到2*256=512, 则可直接得到前8bi的初值。在被开方数很大时,速度有望超过iSqrt_gxq_c，不过，我以为这个算法差不多到头了，速度很难有本质性提高了。

无心人

TO 80# 增加两个语句不会增加执行时间的 TO 81# PM处于PIII和PIV之间， 或者说，其浮点速度慢啊 我有三点感受 1、P4级别上，纯整数指令几乎不占优势 2、Core 2以上，浮点最好了，直接用fisttp好了 3、PM以下，纯整数指令最好了

liangbch

因本帖涉及到众多技术点，故予以加精。 1. 涉及到用整数指令开方，和浮点指令开方。 2. 涉及到跳转表，bsr指令技术。 3. 涉及到使用 swtich/case语句循环展开技术。 4. 涉及到牛顿迭代法和逐位求平方根两种算法。 5. 设计到用整数指令求浮点数转化为整数的技术。

无心人

呵呵 还有问题么解决 如果诸位有兴趣 可以把整数算法完全汇编优化了

gxqcn

无心人近来喜欢用“么”这个字，估计是网络语，开始还读不大习惯。 其实有一个字更准确——“冇”（读作mǎo，没有的意思，刚才用智能拼音居然没打出来）， 我老家那一带就有此方言。

无心人

呵呵 么那个意思啊 么确实是么有的意思 么比冇要容易理解啊 主要是这么说很好玩么

liangbch

我曾又写了一版 逐位开方算法(汇编版)。此算法模拟手动开方算法,不查表。每求1bit需要8条指令，但速度却并不理想。 我看了一下，gxq的c版经编译后只有6条指令，即使用汇编重写代码，采用逐位求平方根的算法也也很难突破6条指令。所以，我以为类似的算法，gxq的C版已经达到极限，是否用汇编重写的算法已经没有多大意义了。 gxq 的6条指令如下：

1. lea edx, DWORD PTR [eax+67108864]
2. shr eax, 1
3. cmp ecx, edx
4. jb SHORT \$L275
5. sub ecx, edx
6. add eax, 67108864

复制代码

无心人

先告一段落吧

gxqcn

我自己曾写了好几套纯ALU指令的汇编代码， 但在我的机器上测试下来的结果均不如编译器直接编译的c代码， 估计与CPU特性相关。 下面这一版本是比较优化的纯ALU汇编代码，无跳转指令：

1. __declspec(naked)
2. UINT32 __fastcall iSqrt( UINT32 n )
3. {
4. __asm push esi;
5. __asm push edi;
6. __asm xor eax, eax;
8. #define SQRT_CORE_ASM(x) \
9. __asm lea edx, [eax+(1UL<<(x))] \
10. __asm shr eax, 1 \
11. __asm mov esi, ecx \
12. __asm sub ecx, edx \
13. __asm lea edi, [eax+(1UL<<(x))] \
14. __asm cmovb ecx, esi \
15. __asm cmovae eax, edi
18. SQRT_CORE_ASM(30);
19. SQRT_CORE_ASM(28);
20. SQRT_CORE_ASM(26);
21. SQRT_CORE_ASM(24);
22. SQRT_CORE_ASM(22);
23. SQRT_CORE_ASM(20);
24. SQRT_CORE_ASM(18);
25. SQRT_CORE_ASM(16);
26. SQRT_CORE_ASM(14);
27. SQRT_CORE_ASM(12);
28. SQRT_CORE_ASM(10);
29. SQRT_CORE_ASM(8);
30. SQRT_CORE_ASM(6);
31. SQRT_CORE_ASM(4);
32. SQRT_CORE_ASM(2);
33. SQRT_CORE_ASM(0);
35. #undef SQRT_CORE_ASM
37. __asm pop edi;
38. __asm pop esi;
39. __asm ret;
40. }

复制代码

该版本估计在比较好的CPU上运行（比如无心人的），在整型指令版本中可以胜出； 由于CPU对浮点指令的提速也比较快，所以可能仍落后于浮点指令版本。 补记：在 96# 我给出了3个ALU汇编版本，即便在比较高级的 CPU 上，仍可能胜出。