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

无心人

2. __declspec(naked)
3. DWORD __fastcall iSqrt_FPU1_yaos(DWORD n)
4. {
5. __asm
6. {
7. push ecx
8. sub esp, 4
9. mov word ptr [esp], 0x0E60
10. fnstcw word ptr [esp + 2]
11. fldcw word ptr [esp] //提前设定截断加64位
12. xor eax, eax
13. shld eax, ecx, 1 //修改
14. fld qword ptr [b32 + eax * 8]
15. fild dword ptr [esp + 4]
16. faddp st(1), st
17. fsqrt
18. fistp dword ptr [esp + 4]
19. fldcw word ptr [esp + 2]
20. mov eax, [esp + 4]
21. add esp, 8
22. ret
23. }
24. }

复制代码

继续优化， 通过测试 重大改进，执行时间在Core2上有大幅度减少 减少44% !!!!! =========================== 呵呵， 明白问题在哪里了 是使用了32位精度浮点了 ========================== 马上进行全数字检测！！！！ 不行！！

无心人

考虑楼上的低精度平方根后的一次纠正是否合算 在计算是否比正确值最多少1

无心人

目前看，仅2^32-1不行 其他都可计算出正确值

2. __declspec(naked)
3. DWORD __fastcall iSqrt_FPU4(DWORD n)
4. {
5. __asm
6. {
7. push ecx
8. sub esp, 4
9. mov word ptr [esp], 0x0C60
10. fnstcw word ptr [esp + 2]
11. fldcw word ptr [esp]
12. mov eax, ecx
13. shr eax, 31
14. fld qword ptr [b32 + eax * 8]
15. fild dword ptr [esp + 4]
16. faddp st(1), st
17. fsqrt
18. fistp dword ptr [esp + 4]
19. fldcw word ptr [esp + 2]
20. mov eax, [esp + 4]
21. add eax, 1
22. mul eax
23. mov edx, eax
24. xor eax, eax
25. cmp edx, ecx
26. setbe al
27. add eax, [esp + 4]
28. add esp, 8
29. ret
30. }
31. }

复制代码

无心人

2. __declspec(naked)
3. DWORD __fastcall iSqrt_FPU4(DWORD n)
4. {
5. __asm
6. {
7. push ecx
8. sub esp, 4
9. mov word ptr [esp], 0x0C60 //单精度截断方式
10. fnstcw word ptr [esp + 2]
11. fldcw word ptr [esp]
12. mov eax, ecx
13. shr eax, 31
14. fld qword ptr [b32 + eax * 8]
15. fild dword ptr [esp + 4]
16. faddp st(1), st
17. fsqrt
18. fistp dword ptr [esp + 4]
19. fldcw word ptr [esp + 2]
20. mov eax, [esp + 4]
21. add eax, 1
22. mul eax
23. mov edx, eax
24. xor eax, eax
25. cmp edx, ecx
26. setbe al
27. add eax, [esp + 4]
28. add esp, 8
29. mov edx, eax
30. shr edx, 16 //测试是否大于等于65536
31. sub eax, edx //纠正2^32-1时计算错误
32. ret
33. }
34. }

复制代码

这样就正常了 两位测试下，这个函数在你们机器的执行时间

无心人

FPU Version: 3609.623 ms FPU1 Version: 3606.396 ms FPU2 Version: 3593.823 ms FPU4 Version: 2623.458 ms 在我机器上是非常快的

gxqcn

在我的 AMD 3200+ CPU 上， 测试 n: 0-2^28 56# 需要 5s / 124# 需要 23s 看来 iSqrt_FPU4 对 CPU 比较挑

无心人

如果能去掉那个乘法就好了

无心人

可以考虑单精度下的浮点纠正 加或者减一个小数 不过， 具体如何做，在尝试

liangbch

PIV 2.6 测试结果 n: 0-0x10000 iSqt_ref#: 0.00306 s iSqt_c1_lbc#: 0.00137 s iSqt_c2_lbc#: 0.00151 s iSqt_FPU1_lbc#: 0.00095 s iSqt_FPU2_lbc#: 0.00189 s iSqt_FPU3_lbc#: 0.00127 s iSqt_FPU_yaos#: 0.00230 s iSqt_FPU1_yaos#: 0.00220 s iSqt_FPU2_yaos#: 0.00255 s iSqt_FPU4_124#: 0.00843 s (124楼函数) iSqt_gxq_c#: 0.00176 s iSqt_GxQ_asm#: 0.00448 s iSqt_gxq_90#: 0.00434 s iSqt_16#: 0.00384 s n: 0-0x10000000 iSqt_ref#: 13.66799 s iSqt_c1_lbc#: 9.00341 s iSqt_c2_lbc#: 11.29242 s iSqt_FPU1_lbc#: 4.39066 s iSqt_FPU2_lbc#: 8.79425 s iSqt_FPU3_lbc#: 6.42752 s iSqt_FPU_yaos#: 10.13491 s iSqt_FPU1_yaos#: 9.89024 s iSqt_FPU2_yaos#: 10.96591 s iSqt_FPU4_124#: 37.71079 s (124楼函数) iSqt_gxq_c#: 8.64673 s iSqt_GxQ_asm#: 20.26102 s iSqt_gxq_90#: 19.40886 s iSqt_16#: 16.53817 s 测试结果表明：在PIV上运行，124楼的版本出奇的慢，运行时间是 iSqt_FPU1_lbc 的8倍多，看来确实如gxq如言，这个版本很挑CPU

无心人

宝宝 考虑下128#的建议 不过，我想这个理论上容易 实际上很不好处理