整数平方和开根号的性能优化

整数的平方和开根号操作通过sqrt实现性能已经不容易优化，但如果要求精度不高，可以进一步优化，方法有三种：1、isqrt；2、查表法；3、三角函数法

1、isqrt即整数平方根，有多种算法。通过询问ChatGPT，AI给出了几种实现，这里取一种比较快的实现：

 1 u32 isqrt2(u32 x)
 2 {
 3     u32 res = 0;
 4     u32 bit = 1 << 30; // The second-to-top bit is set: 1 << 30 for 32 bits
 5     // "bit" starts at the highest power of four <= the argument.
 6     while (bit > x) bit >>= 2;
 7     while (bit != 0)
 8     {
 9         if (x >= res + bit)
10         {
11             x -= res + bit;
12             res = (res >> 1) + bit;
13         }
14         else res >>= 1;
15         bit >>= 2;
16     }
17     return res;
18 }

这种算法的速度比浮点sqrt函数慢很多。又尝试了牛顿迭代法、割线法求整数平方根的整数部分，其性能均不如浮点算法。牛顿迭代法的迭代次数为2~3次的时候就能满足精度指标，但其性能已经远远落后于sqrt。

2、查表法

整数平方和是一个非常大的数，一般项目中都在16bit以上，要做一个超级大的表才能实现精确的查表。所以这里的查表法是分两部分查表，若输入小，则直接查表输出。若输入较大，则将其高位数值查表，低位忽略。这样就能大大降低表的大小，并且仅通过一次查表实现输出。理论上误差为表大小开根号乘以0.414。例如，256的表，最大误差时为计算511的平方根，结果为16，误差为16*0.414=6.6；4K的表最大误差27。

一个实现的例子：

1 u8 isqrt_N(u16 x) //只能算根在256以内的，超过就错了
2 {
3     u16 x0=x>>8;
4     if(x0<=0) return isqrt_N_tab[x];
5     u16 x1=isqrt_N_tab[x0]; //高8bit开方
6     return x1<<4;
7 }

3、三角函数法

整数平方和开根号可以看做是已知三角形的两个直角边，求斜边。首先设其中比较大的输入为x，小的为y。则x边的角度为atan(y/x)，斜边长度为x/cos(atan(y/x))。由于y/x这个比值小于1，不会让atan出现很多不均匀的情况，所以可以将1/ x/cos(atan(y/x))做成查找表，并通过定点数存储。计算平方根时，只需计算x/查表值即可。由于需要计算除法，导致此算法效率并没有比浮点sqrt快很多

一个例程：

 1 u16 isqrt_sq_sum(int x,int y) //平方和开根号
 2 {
 3     u32 xx=abs(x);
 4     u32 yy=abs(y);
 5     if(xx>yy)
 6     {
 7         if(xx==0) return 0;
 8         u32 ind=yy*128/xx; //肯定是正的，肯定小于128
 9         return (xx*cos_tan_tab[ind])>>12; // x*4096/cos(tan(y/x))/4096
10     }
11     else
12     {
13         if(yy==0) return 0;
14         u32 ind=xx*127/yy; //有x=y的情况
15         return (yy*cos_tan_tab[ind])>>12; // x*4096/cos(tan(y/x))/4096
16     }
17 }

以上三种算法均依赖-O3编译器优化，才能实现比sqrt快的性能。而sqrt函数本身是经过优化的，所以编译器优化对其无优化效果。