发个对整数开根号的算法

yuxh

1. uint8_t ary[256] = {
   
2.   0, 16, 16, 16, 32, 32, 32, 32, 32, 48, 48, 48, 48, 48, 48, 48, 64, 64, 68, 68, 72, 72, 76, 76, 76, 80, 80, 84, 84, 84, 88, 88,
   
3. 88, 92, 92, 92, 96, 96, 96,100,100,100,104,104,104,108,108,108,108,112,112,112,116,116,116,116,120,120,120,120,124,124,124,124,
   
4. 128,129,130,131,132,133,134,135,136,137,138,139,140,141,142,143,143,144,145,146,147,148,149,150,150,151,152,153,154,155,155,156,
   
5. 157,158,159,159,160,161,162,163,163,164,165,166,167,167,168,169,170,170,171,172,173,173,174,175,175,176,177,178,178,179,180,181,
   
6. 181,182,183,183,184,185,185,186,187,187,188,189,189,190,191,191,192,193,193,194,195,195,196,197,197,198,199,199,200,201,201,202,
   
7. 203,203,204,204,205,206,206,207,207,208,209,209,210,211,211,212,212,213,214,214,215,215,216,217,217,218,218,219,219,220,221,221,
   
8. 222,222,223,223,224,225,225,226,226,227,227,228,229,229,230,230,231,231,232,232,233,234,234,235,235,236,236,237,237,238,238,239,
   
9. 239,240,241,241,242,242,243,243,244,244,245,245,246,246,247,247,248,248,249,249,250,250,251,251,252,252,253,253,254,254,255,255
   
10. };  
    
11. unsigned int my_sqrt(unsigned int a)
    
12. {
    
13.     unsigned int b;
    
14. 
    
15.     if (a < 256) return (ary[a]) >> 4;
    
16.     else if (a < (1 << 12)) b = ary[a >> 4] >> 2;
    
17.     else if (a < (1 << 14)) b = ary[a >> 6] >> 1;
    
18.     else if (a < (1 << 16)) b = ary[a >> 8]   ;
    
19.     else if (a > 4294836225u) return 65535;
    
20.     else
    
21.     {
    
22.         int s = (31 - __builtin_clz((a >> 16)|1)) >> 1;
    
23.         unsigned int c = a >> (s + 2);
    
24.         b = ary[c >> (s + 8)]; // b=sqrt(c >> s)
    
25.         b = c/b + (b << s); //插值 c/b约＝b<<s
    
26.     }
    
27.     return b - (a < b * b);
    
28. }
    

复制代码

这个数组可以这样得到：

1. int main()
   
2. {
   
3.     uint8_t ary[256];
   
4.     int i = 0, j;
   
5.     memset(ary, 0, sizeof(ary));
   
6.     for(i = 0; i < 1 << 8; i++) ary[i] = 16*((int)sqrt(i));
   
7.     for(; i < 1 << 12; i++) ary[i/16] = 4*((int)sqrt(i));
   
8.     for(; i < 1 << 14; i++) ary[i/64] = 2*((int)sqrt(i));
   
9.     for(; i < 1 << 16; i++) ary[i/256] = (int)sqrt(i);
   
10.     for(i = 0; i < 255; i++)
    
11.     {
    
12.         printf("%3d,", ary[i]);
    
13.         if(i % 32 == 31)
    
14.             printf("\n");
    
15.     }
    
16.     printf("%3d\n", ary[i]);
    
17. }

复制代码

zighouse

很好，用了，谢谢。

captivated

好的, 先mark