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

gxqcn

原帖由 无心人 于 2009-2-18 10:34 发表


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

也许你的算法改SSE2更快

SIMD 的妙处是将同一个128bit数据可以看做 128x1 / 64x1 / 32x4 / 8x16
如何看待取决于不同的指令。
这样可以做到多路并行的效果。

这里的ALU算法并不是最好的，
但在一定使用范围内却是最有效的。

比如，如果确知被开方数不大于 0xFFFF，
则仅需调用 8 次 SQRT_CORE 即可。
这是 FPU 等其它算法所不具备的。
当然，也可看作是 FPU 算法的精度过剩造成的，
因为实际上它是在做 64bit 数的开方。

SIMD 系列指令集也分整型指令和浮点型指令。
一般来说，整型指令比浮点型指令具有更短的周期，以及更大的吞吐率。

无心人

是53Bit啊

宝宝的代码我修改了
改成肯定是64位浮点运算了

无心人

你程序能不能使用一个预先得到的初始值？

根据首四位，能得到一个2位的初始值

gxqcn

主要是嫌 bsr 指令周期太长（新的 CPU 已改善不少），
要不完全可以动态决定循环次数的。

无心人

2个周期的指令还嫌长啊

无心人

如果你是AMD的U
怎么不用shr啊

gxqcn

你查到的是在 Core 2；
在 P4E 上得 2+16 个周期，
在 AMD K7 上得 23+9，
在 AMD K8上得 28+10，
在 AMD K7 上得 7+4。

无心人

P4上是6个啊
微操作3个，6个周期延迟

P4E是16个
微操作2个，16个周期延迟

呵呵

无心人

LEA 代价也不小
P4E是2.5
P4才是0.5

无心人

1. 
   
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.    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 esp, 8
    
22.    ret
    
23.    }
    
24. }
    

复制代码

继续优化， 通过测试