[嵌入式]MCU裸系统下快速平方根实现

很多MCU平台均没有支持完整的数学运算指令，此时如果计算算术平方根就需要利用软件函数库，但是这些库代码一般都会占用不少的ROM空间，当ROM区域特别紧张时可能无法利用现成的库代码，此时就要自己实现一个快速平方根。以下是一个典型的逼近法实现的快速平方根函数，只用了整数乘法就可以做到32位范围内的整数平方根计算，并且计算中边界值始终按照二分法定位可以显著缩短查找逼近时间，算法复杂度近似于Log2(N)。

算法：

0) 声明并准备如下变量：
    value - 要计算平方根的原始输入数值
    s 	- 平方根结果变量
    n 	- 下一个逼近结果变量
    s2 	- 临时变量用于储存平方数值
    d 	- 当前平方数值和输入数值的误差	
1）读入要计算的数值变量value，按照value/2准备计算边界变量t（t最大65534）
2）当value为0,1,2时直接返回结果0,1,1,否则继续
3）初始化结果变量s为2，初始化差值变量d为value当前数值
4）判断结果变量，当s>t时直接返回s作为最终结果，否则继续
5）计算s2=s*s，当s2等于value时直接返回s，否则继续
6）如果s2大于value并且s2-value大于差值变量d，则返回数值s-1作为最终结果，否则继续
7）如果s2大于value并且s2-value小于等于差值变量d，则返回数值s作为最终结果，否则继续
8）计算差值变量d=value-s2
9）计算二分法下个变量n=(s+t)/2
10）计算s2=n*n，当s2等于value时直接返回n，否则继续
11) 如果s2大于value，则另t=n，s=s+1，跳转步骤4）
12）计算差值变量d=value-s2，设置s=n+1，跳转步骤4)

程序：

uint32_t SQRT(uint32_t value) {
  /* 声明变量 */
  uint32_t s, t, n, s2, d;
  /* 当value为0,1,2时直接返回结果0,1,1,否则继续 */
  if( value == 0 )
    return 0;
  else if( value <= 2 )
    return 1;
  /* 按照value/2准备计算边界变量t（t最大65534）*/
  t = value/2;
  if( t > 65534 )
    t = 65534;
  /* 初始化结果变量s为2，初始化差值变量d为value当前数值 */
  s = 2;
  d = value;
  while( s <= t ) {
    s2 = s*s;
    if( s2 == value )
      break;     /* 当s2等于value时直接返回s */
    if( s2 > value ) {
      /* 如果s2大于value并且s2-value大于差值变量d，则返回数值s-1作为最终结果 */
      if( s2 - value > d )
        s = s - 1;
      break;
    }
    /* 计算差值变量d=value-s2 */
    d = value - s2;
    
    /* 计算二分法下个变量n=(s+t)/2 */
    n = (s + t)/2;
    s2 = n*n;
    if( s2 == value ) {
      s = n;
      break;
    } else if( s2 < value ) {
      /* 如果s2小于value，则计算差值变量d=value-s2，设置s=n+1 */
      d = value - s2;
      s = n + 1;
    } else {
      /*  如果s2大于value，则另t=n，s=s+1 */    
      t = n;
      s++;
    }
  } 
  /* 返回数值s作为最终结果 */
  return s;
}

注：

• 以上运算中所有/2操作最终编译器将优化为>>1右移操作，不会采用费时的除法运算，如果不放心可以改为显式的>>1右移运算
• 程序堆栈开销为20个字节相当于五个32位寄存器，在大部分默认优化的ARM系统下实际编译出来的汇编指令都是直接寄存器操作而非堆栈内存操作