二进制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. mov eax, ecx
12. shr eax, 31
13. fld qword ptr [b32 + eax * 8]
14. fild dword ptr [esp + 4]
15. faddp st(1), st
16. fsqrt
17. fldcw word ptr [esp]
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. }

复制代码

再次优化99#代码

无心人

宝宝的FPU3版本可修改为

2. __declspec(naked)
3. DWORD __fastcall iSqrt_FPU3_lbc(DWORD n)
4. {
5. __asm
6. {
7. push ecx
8. shr ecx, 31
9. fld qword ptr [lbc_b32 + ecx * 8]
10. fild dword ptr [esp]
11. faddp st(1),st
12. fsqrt
14. //设置FPU的取整方式 为了直接使用fistp浮点指令
15. FNSTCW [esp-4] // 保存协处理器控制字,用来恢复
16. mov word ptr [esp-6], 0x0E60 //截断， 64位浮点
17. FWAIT
18. FLDCW [esp-6] // 载入协处理器控制字,RC场已经修改
20. fistp dword ptr [esp]
22. //恢复FPU的取整方式
23. FWAIT
24. FLDCW [esp-4]
26. pop eax
27. ret
28. }
29. }

复制代码

比较了SSE3版本，和宝宝的版本2几乎相同 另外，在我的机器上，我的FPU几个版本和宝宝的差距很小 测试的0-2^24-1 iSqt_FPU1_lbc#: 0.60082 s iSqt_FPU2_lbc#: 0.60123 s iSqt_FPU3_lbc#: 0.60077 s //修改为上面版本 iSqt_FPU_yaos#: 0.62264 s iSqt_FPU1_yaos#: 0.60129 s //修改为SSE3版本 iSqt_FPU2_yaos#: 0.60084 s

无心人

iSqt_FPU1_lbc#: 0.60160 s iSqt_FPU2_lbc#: 0.60122 s iSqt_FPU3_lbc#: 0.60101 s iSqt_FPU_yaos#: 0.60096 s //修改为101#版本 iSqt_FPU1_yaos#: 0.60080 s //修改为SSE3版本 iSqt_FPU2_yaos#: 0.60056 s

无心人

2. __declspec(naked)
3. DWORD __fastcall iSqrt_FPU3_lbc(DWORD n)
4. {
5. __asm
6. {
7. push ecx
8. shr ecx, 31
9. fld qword ptr [lbc_b32 + ecx * 8]
10. fild dword ptr [esp]
11. faddp st(1),st
12. fsqrt
14. //设置FPU的取整方式 为了直接使用fistp浮点指令
15. FNSTCW [esp-4] // 保存协处理器控制字,用来恢复
16. mov word ptr [esp-6], 0x0E60 //截断， 64位浮点
17. FLDCW [esp-6] // 载入协处理器控制字,RC场已经修改
19. fistp dword ptr [esp] //恢复FPU的取整方式
20. FLDCW [esp-4]
22. pop eax
23. ret
24. }
25. }

复制代码

宝宝的程序还可以继续精简 两个 FWAIT都不是必需的 仅在浮点存，且下个指令是读存储的数据时需要FWAIT

无心人

2. double lbc_b32[] = {0.0,4294967296.0};
3. //实验证明zero5不能大于0.49999999999636
4. double zero5= 0.49999999999636;;
6. __declspec(naked)
7. DWORD __fastcall iSqrt_FPU1_lbc(DWORD n)
8. {
9. __asm
10. {
11. push ecx
13. shr ecx, 31
14. fld qword ptr [lbc_b32 + ecx * 8]
15. fild dword ptr [esp]
16. faddp st(1),st
17. fsqrt
18. fsub qword ptr [zero5]
19. fistp dword ptr [esp]
20. pop eax
21. ret
22. }
23. }
25. __declspec(naked)
26. DWORD __fastcall iSqrt_FPU2_lbc(DWORD n)
27. {
28. __asm
29. {
30. or ecx,ecx
31. jnz next00
32. mov eax,0
33. ret
34. next00:
35. push ecx
37. shr ecx, 31
38. fld qword ptr [lbc_b32 + ecx * 8]
39. fild dword ptr [esp]
40. faddp st(1),st
41. fsqrt
42. fstp qword ptr [esp-8]
44. fwait
45. mov ecx,dword ptr [esp-4]
46. mov edx,0xfff00000
47. mov eax,0xfffff
49. and edx,ecx //阶码
50. and eax,ecx //尾数
51. shr edx,20 //得到阶段码
52. add eax,0x100000 //设置位数最高有效位
53. mov ecx,1043
54. sub ecx,edx
55. shr eax,cl //得到整数
57. pop ecx
58. ret
59. }
60. }
62. __declspec(naked)
63. DWORD __fastcall iSqrt_FPU3_lbc(DWORD n)
64. {
65. __asm
66. {
67. push ecx
68. shr ecx, 31
69. fld qword ptr [lbc_b32 + ecx * 8]
70. fild dword ptr [esp]
71. faddp st(1),st
72. fsqrt
74. //设置FPU的取整方式 为了直接使用fistp浮点指令
75. FNSTCW [esp-4] // 保存协处理器控制字,用来恢复
76. mov word ptr [esp-6], 0x0E60 //截断， 64位浮点
77. FLDCW [esp-6] // 载入协处理器控制字,RC场已经修改
79. fistp dword ptr [esp] //恢复FPU的取整方式
80. FLDCW [esp-4]
82. pop eax
83. ret
84. }
85. }

复制代码

2. double b32[] = {0.0,4294967296.0};
4. __declspec(naked)
5. DWORD __fastcall iSqrt_FPU_yaos(DWORD n)
6. {
7. __asm
8. {
9. push ecx
10. sub esp, 4
11. mov word ptr [esp], 0x0E60
12. fnstcw word ptr [esp + 2]
13. mov eax, ecx
14. shr eax, 31
15. fld qword ptr [b32 + eax * 8]
16. fild dword ptr [esp + 4]
17. faddp st(1), st
18. fsqrt
19. fldcw word ptr [esp]
20. fistp dword ptr [esp + 4]
21. fldcw word ptr [esp + 2]
22. mov eax, [esp + 4]
23. add esp, 8
24. ret
26. }
27. }
29. __declspec(naked)
30. DWORD __fastcall iSqrt_FPU1_yaos(DWORD n)
31. {
32. __asm
33. {
34. push ecx
35. mov eax, ecx
36. shr eax, 31
37. fld qword ptr [b32 + eax * 8]
38. fild dword ptr [esp]
39. faddp st(1), st
40. fsqrt
41. fisttp dword ptr [esp]
42. fwait
43. pop eax
44. ret
45. }
46. }
48. __declspec(naked)
49. DWORD __fastcall iSqrt_FPU2_yaos(DWORD n)
50. {
51. __asm
52. {
53. push ecx
54. mov eax, ecx
55. and eax, 0x80000000
56. shr eax, 31
57. fld qword ptr [b32 + eax * 8]
58. fild dword ptr [esp]
59. faddp st(1), st
60. fsqrt
61. sub esp, 8
62. fstp qword ptr [esp]
63. fwait
64. mov edx, dword ptr [esp + 4]
65. mov eax, edx
66. and edx,0x7ff00000
67. and eax,0xfffff
68. shr edx, 20
69. or eax, 0x100000
70. xchg ecx, edx
71. sub ecx, 1043
72. neg ecx
73. shr eax, cl
74. xchg edx, ecx
75. add esp, 12
76. or ecx, ecx
77. cmove eax, ecx
78. ret
79. }
80. }

复制代码

完全测试 n: 0-0x10000 iSqt_FPU1_lbc#: 0.00234 s iSqt_FPU2_lbc#: 0.00234 s iSqt_FPU3_lbc#: 0.00234 s iSqt_FPU_yaos#: 0.00234 s iSqt_FPU1_yaos#: 0.00235 s iSqt_FPU2_yaos#: 0.00234 s n: 0-0x10000000 iSqt_FPU1_lbc#: 9.62084 s iSqt_FPU2_lbc#: 9.64661 s iSqt_FPU3_lbc#: 9.62920 s iSqt_FPU_yaos#: 9.61824 s iSqt_FPU1_yaos#: 9.62351 s iSqt_FPU2_yaos#: 9.61847 s ================================ iSqrt_FPU1_yaos是SSE3指令

无心人

n: 0-0x10000 iSqt_FPU1_lbc#: 0.00234 s iSqt_FPU2_lbc#: 0.00234 s iSqt_FPU3_lbc#: 0.00234 s iSqt_FPU_yaos#: 0.00234 s iSqt_FPU1_yaos#: 0.00234 s iSqt_FPU2_yaos#: 0.00234 s iSqt_gxq_ALU#: 0.00378 s n: 0-0x10000000 iSqt_FPU1_lbc#: 9.61900 s iSqt_FPU2_lbc#: 9.66175 s iSqt_FPU3_lbc#: 9.66552 s iSqt_FPU_yaos#: 9.63164 s iSqt_FPU1_yaos#: 9.61888 s iSqt_FPU2_yaos#: 9.61667 s iSqt_gxq_ALU#: 15.48249 s //版本3 n: 0-0x10000 iSqt_FPU1_lbc#: 0.00234 s iSqt_FPU2_lbc#: 0.00234 s iSqt_FPU3_lbc#: 0.00234 s iSqt_FPU_yaos#: 0.00234 s iSqt_FPU1_yaos#: 0.00234 s iSqt_FPU2_yaos#: 0.00234 s iSqt_gxq_ALU#: 0.00559 s n: 0-0x10000000 iSqt_FPU1_lbc#: 9.62917 s iSqt_FPU2_lbc#: 9.62330 s iSqt_FPU3_lbc#: 9.62190 s iSqt_FPU_yaos#: 9.62101 s iSqt_FPU1_yaos#: 9.62660 s iSqt_FPU2_yaos#: 9.67119 s iSqt_gxq_ALU#: 23.00808 s //版本2 n: 0-0x10000 iSqt_FPU1_lbc#: 0.00234 s iSqt_FPU2_lbc#: 0.00235 s iSqt_FPU3_lbc#: 0.00234 s iSqt_FPU_yaos#: 0.00234 s iSqt_FPU1_yaos#: 0.00234 s iSqt_FPU2_yaos#: 0.00234 s iSqt_gxq_ALU#: 0.00189 s n: 0-0x10000000 iSqt_FPU1_lbc#: 9.62116 s iSqt_FPU2_lbc#: 9.61972 s iSqt_FPU3_lbc#: 9.61780 s iSqt_FPU_yaos#: 9.61988 s iSqt_FPU1_yaos#: 9.62212 s iSqt_FPU2_yaos#: 9.62422 s iSqt_gxq_ALU#: 7.02810 s //版本1

gxqcn

这么说，CPU 的 ALU 比 FPU 提速幅度更大？ 如果真是这样的，发展基于整型指令的算法将更具竞争力？

liangbch

楼主辛苦了

无心人

关键是ALU算法并不是最好的 这就是为什么Intel推SIMD的原因 也许你的算法改SSE2更快

无心人

你们俩有时间测下我改的 宝宝和我的三个汇编的数据 FPU1_yaos 就别测了 看是否我改的快了 或者反而慢了