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

无心人 · 发表于 2009-2-18 11:53:15

__declspec(naked)
DWORD __fastcall iSqrt_FPU1_yaos(DWORD n)
{
__asm
{
push ecx
sub esp, 4
mov word ptr [esp], 0x0E60
fnstcw word ptr [esp + 2]
fldcw word ptr [esp] //提前设定截断加64位
xor eax, eax
shld eax, ecx, 1 //修改
fld qword ptr [b32 + eax * 8]
fild dword ptr [esp + 4]
faddp st(1), st
fsqrt
fistp dword ptr [esp + 4]
fldcw word ptr [esp + 2]
mov eax, [esp + 4]
add esp, 8
ret
}
}

复制代码

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

无心人 · 发表于 2009-2-18 15:18:14

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

无心人 · 发表于 2009-2-18 15:44:22

目前看，仅2^32-1不行

其他都可计算出正确值

__declspec(naked)
DWORD __fastcall iSqrt_FPU4(DWORD n)
{
__asm
{
push ecx
sub esp, 4
mov word ptr [esp], 0x0C60
fnstcw word ptr [esp + 2]
fldcw word ptr [esp]
mov eax, ecx
shr eax, 31
fld qword ptr [b32 + eax * 8]
fild dword ptr [esp + 4]
faddp st(1), st
fsqrt
fistp dword ptr [esp + 4]
fldcw word ptr [esp + 2]
mov eax, [esp + 4]
add eax, 1
mul eax
mov edx, eax
xor eax, eax
cmp edx, ecx
setbe al
add eax, [esp + 4]
add esp, 8
ret
}
}

复制代码

无心人 · 发表于 2009-2-18 15:55:48

__declspec(naked)
DWORD __fastcall iSqrt_FPU4(DWORD n)
{
__asm
{
push ecx
sub esp, 4
mov word ptr [esp], 0x0C60 //单精度截断方式
fnstcw word ptr [esp + 2]
fldcw word ptr [esp]
mov eax, ecx
shr eax, 31
fld qword ptr [b32 + eax * 8]
fild dword ptr [esp + 4]
faddp st(1), st
fsqrt
fistp dword ptr [esp + 4]
fldcw word ptr [esp + 2]
mov eax, [esp + 4]
add eax, 1
mul eax
mov edx, eax
xor eax, eax
cmp edx, ecx
setbe al
add eax, [esp + 4]
add esp, 8
mov edx, eax
shr edx, 16 //测试是否大于等于65536
sub eax, edx //纠正2^32-1时计算错误
ret
}
}

复制代码

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

无心人 · 发表于 2009-2-18 16:04:40

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

gxqcn · 发表于 2009-2-18 16:12:46

在我的 AMD 3200+ CPU 上，
测试 n: 0-2^28
56# 需要 5s / 124# 需要 23s

看来 iSqrt_FPU4 对 CPU 比较挑

无心人 · 发表于 2009-2-18 16:28:10

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

无心人 · 发表于 2009-2-18 16:34:36

可以考虑单精度下的浮点纠正
加或者减一个小数

不过，具体如何做，在尝试

liangbch · 发表于 2009-2-18 16:51:59

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

无心人 · 发表于 2009-2-18 16:55:51

宝宝

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

账号		自动登录	找回密码
密码			欢迎注册

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

回复 125# 无心人的帖子

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

回复 125# 无心人 的帖子

回复 125# 无心人的帖子