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

无心人

另外，你能否对105#的修改进行测试
和你原来的比较下

Mgccl

gxqcn...我将你的代码借用一下?

gxqcn

尽管拿去用！

无须声明，且可自修订；
若有改进请告诉我一声。

llxxtnt

提高程序的性能，主要应该依赖于高效的算法
而不是在于更先进的编程工具，更快的编程语言，更高明的编程技巧
这些都应该只是次要的手段
我看到很多人都在讨论如何使用更先进的汇编指令来完成高效的计算，是不是走入了误区
我用16#的算法，写了一个C程序，如果不打印结果，性能还不错

1. 
   
2. //这个程序计算从1到0xFFFFFFFF的所有数的平方根，并全部打印
   
3. #include <stdio.h>
   
4. #include <stdlib.h>
   
5. 
   
6. int main(int argc, char** argv)
   
7. {
   
8.     register unsigned int num = 1;
   
9.     register unsigned int root = 1;
   
10.     register unsigned int square = 0;
    
11. 
    
12. 
    
13.     for( ; ; root++)
    
14.     {
    
15.         square += root << 1;
    
16.         square--;
    
17. 
    
18.         for( ; ; )
    
19.         {
    
20.             if(num == square)
    
21.             {
    
22. #ifdef __DEBUG__
    
23.                 printf("square root of %d is %d\n", num, root);
    
24. #endif
    
25.                 num++;
    
26.                 break;
    
27.             }
    
28. 
    
29. #ifdef __DEBUG__                        
    
30.             printf("square root of %d is %d\n", num, root-1);
    
31. #endif                        
    
32.             num++;
    
33. 
    
34.             if(num == 0xFFFFFFFF)
    
35.             {
    
36.                 return 0;
    
37.             }
    
38.         }
    
39.     }
    
40. 
    
41.     return 0;
    
42. }
    

复制代码

mathe

你做的不是同一件事情.

无心人

你是枚举每一个的平方根
那个是不用乘除法的

我们是随机数字的平方根
如果你有兴趣

请考虑下
求2^48-- 2^64 - 1
下任意一个数字的平方根
你看你如何求？

你就知道其中区别了

G-Spider

看到这个代码，我满意地笑了。

1. #include <stdio.h>
   
2. 
   
3. _declspec(naked) float fast_sqrt(float x)
   
4. {
   
5. _asm
   
6.     {
   
7.         sub esp,4
   
8.         mov eax,[esp+8]
   
9.         sub eax,0x3f800000
   
10.         sar eax,1
    
11.         add eax,0x3f800000
    
12.         mov [esp],eax
    
13.         fld dword ptr [esp]
    
14.         add esp,4
    
15.         ret
    
16.     }
    
17. }
    
18. 
    
19. int main()
    
20. {
    
21.     float i;
    
22.     for(i=0.0;i<=16.0;i+=0.2)     //test
    
23.         printf("%f    %f\n",i,fast_sqrt(i));
    
24.    
    
25.     return 0;
    
26. 
    
27. }

复制代码

liangbch

在137#的基础上，封装一个和参考函数接口完全相同的函数iSqt_FPU1_gspider。使用70#的源代码进行测试，发现这个函数的速度不太理想。

测试平台：
core2, 4G,windows XP,VC6.0 release 方式编译

1. typedef unsigned long DWORD;
   
2. _declspec(naked)
   
3. float gspider_fast_sqrt(float x)
   
4. {
   
5. _asm
   
6. {
   
7.         sub esp,4
   
8.         mov eax,[esp+8]
   
9.         sub eax,0x3f800000
   
10.         sar eax,1
    
11.         add eax,0x3f800000
    
12.         mov [esp],eax
    
13.         fld dword ptr [esp]
    
14.         add esp,4
    
15.         ret
    
16.     }
    
17. }
    
18. 
    
19. DWORD __fastcall iSqrt_FPU1_gspider(DWORD n)
    
20. {
    
21.         float x=(float)n;
    
22.         return (DWORD)(gspider_fast_sqrt(x));
    
23. }
    
24. 
    
25. 
    
26. n: 0-0x10000
    
27. iSqt_ref#: 0.00106 s
    
28. iSqt_c1_lbc#: 0.00033 s
    
29. iSqt_c2_lbc#: 0.00064 s
    
30. iSqt_FPU1_lbc#: 0.00039 s
    
31. iSqt_FPU2_lbc#: 0.00040 s
    
32. iSqt_FPU3_lbc#: 0.00078 s
    
33. iSqt_FPU_yaos#: 0.00112 s
    
34. iSqt_FPU2_yaos#: 0.00046 s
    
35. iSqt_gxq_c#: 0.00073 s
    
36. iSqt_GxQ_asm#: 0.00259 s
    
37. iSqt_16#: 0.00356 s
    
38. iSqt_FPU1_gspider#: 0.00160 s
    
39. 
    
40. 
    
41. n: 0-0x10000000
    
42. iSqt_ref#: 4.78258 s
    
43. iSqt_c1_lbc#: 1.90706 s
    
44. iSqt_c2_lbc#: 4.69837 s
    
45. iSqt_FPU2_lbc#: 1.80180 s
    
46. iSqt_FPU3_lbc#: 3.52315 s
    
47. iSqt_FPU_yaos#: 5.06165 s
    
48. iSqt_FPU1_yaos#: 5.06292 s
    
49. iSqt_FPU2_yaos#: 2.07291 s
    
50. iSqt_gxq_c#: 3.13477 s
    
51. iSqt_GxQ_asm#: 11.72902 s
    
52. iSqt_16#: 16.66489 s
    
53. iSqt_FPU1_gspider#: 7.45803 s

复制代码

G-Spider

138# liangbch
原理也是适用于float型的粗糙开方。经过两次强制类型转换，再多了一次调用，会慢下来。

G-Spider

也来一个FPU版，差不多的性能。

1. char b80[32]={0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,\
   
2.               0,0,0,0,0,0,0,0x80,0x1f,0x40,0,0,0,0,0,0};
   
3.               
   
4. __declspec(naked)
   
5. DWORD __fastcall fast_sqrt(DWORD n)
   
6. {
   
7.         __asm
   
8.         {
   
9.                     push   ecx
   
10.                         shr    ecx, 27
    
11.                         and    ecx, 16
    
12.                         fld    tbyte ptr [b80+ecx]
    
13.                         fild   dword ptr [esp]
    
14.                         faddp  st(1),st
    
15.                         fsqrt
    
16.                        
    
17.             fisttp dword ptr[esp]
    
18.             pop    eax
    
19.                         ret
    
20.         }
    
21. }

复制代码