数学研发网设为首页收藏本站
切换到窄版

 找回密码
 欢迎注册
数学研发论坛»论坛 › 【算法研发】 › 编程擂台 › 二进制32位整数快速平方根
1 ...789101112131415下一页
返回列表 发新帖
楼主: 无心人

[讨论] 二进制32位整数快速平方根

[复制链接]
无心人
 楼主| 发表于 2009-2-18 07:53:30 | 显示全部楼层

  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#代码
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

无心人
 楼主| 发表于 2009-2-18 08:51:25 | 显示全部楼层

宝宝的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
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

无心人
 楼主| 发表于 2009-2-18 08:55:36 | 显示全部楼层
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
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

无心人
 楼主| 发表于 2009-2-18 09:06:21 | 显示全部楼层

  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
  13.                        
  14.                 //设置FPU的取整方式  为了直接使用fistp浮点指令
  15.                 FNSTCW  [esp-4]            // 保存协处理器控制字,用来恢复
  16.                 mov word ptr [esp-6], 0x0E60     //截断， 64位浮点
  17.                 FLDCW   [esp-6]            // 载入协处理器控制字,RC场已经修改
  18.                        
  19.                 fistp   dword ptr [esp]                        //恢复FPU的取整方式
  20.                 FLDCW   [esp-4]
  21.                
  22.                 pop eax
  23.                 ret
  24.         }
  25. }
复制代码
宝宝的程序还可以继续精简
两个 FWAIT都不是必需的
仅在浮点存，且下个指令是读存储的数据时需要FWAIT
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

无心人
 楼主| 发表于 2009-2-18 09:13:16 | 显示全部楼层

  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指令
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

无心人
 楼主| 发表于 2009-2-18 09:36:57 | 显示全部楼层
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
发表于 2009-2-18 09:52:57 | 显示全部楼层
这么说，CPU 的 ALU 比 FPU 提速幅度更大？
如果真是这样的，发展基于整型指令的算法将更具竞争力？
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

liangbch
发表于 2009-2-18 10:32:59 | 显示全部楼层
楼主辛苦了
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

无心人
 楼主| 发表于 2009-2-18 10:34:05 | 显示全部楼层


关键是ALU算法并不是最好的
这就是为什么Intel推SIMD的原因

也许你的算法改SSE2更快
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

无心人
 楼主| 发表于 2009-2-18 10:35:10 | 显示全部楼层


你们俩有时间测下我改的
宝宝和我的三个汇编的数据
FPU1_yaos 就别测了

看是否我改的快了
或者反而慢了
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

1 ...789101112131415下一页
返回列表 发新帖
高级模式
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2024-5-4 22:01 , Processed in 0.043193 second(s), 15 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

快速回复 返回顶部 返回列表