单片机上的开方程序.lst

单片机上的开方程,C语言写的,在keil下调试通过

C51 COMPILER V7.50   单芲籣上的开方程序                                                    12/28/2006 23:41:23 PAGE 1   


C51 COMPILER V7.50, COMPILATION OF MODULE 单芲籣上的开方程序
OBJECT MODULE PLACED IN 单片机上的开方程序.OBJ
COMPILER INVOKED BY: D:\Program Files\Keil\C51\BIN\C51.EXE 单片机上的开方程序.c BROWSE DEBUG OBJECTEXTEND

line level    source

   1          /*
   2          因为工作的需要，要在单片机上实现开根号的操作。目前开平方的方法大部分
   3          是用牛顿迭代法。我在查了一些资料以后找到了一个比牛顿迭代法更加快速的
   4          方法。不敢独享，介绍给大家，希望会有些帮助。
   5          
   6          1.原理
   7          因为排版的原因，用pow(X,Y)表示X的Y次幂，用B[0]，B[1]，...，B[m-1]表示一个序列，
   8          其中[x]为下标。
   9          
  10          假设：
  11          B[x],b[x]都是二进制序列,取值0或1。
  12          M = B[m-1]*pow(2,m-1) + B[m-2]*pow(2,m-2) + ... + B[1]*pow(2,1) + B[0]*pow
  13          (2,0)
  14          N = b[n-1]*pow(2,n-1) + b[n-2]*pow(2,n-2) + ... + b[1]*pow(2,1) + n[0]*pow
  15          (2,0)
  16          pow(N,2) = M
  17          
  18          (1) N的最高位b[n-1]可以根据M的最高位B[m-1]直接求得。
  19          设 m 已知,因为 pow(2, m-1) <= M <= pow(2, m)，所以 pow(2, (m-1)/2) <= N <=
  20          pow(2, m/2)
  21          如果 m 是奇数，设m=2*k+1,
  22          那么 pow(2,k) <= N < pow(2, 1/2+k) < pow(2, k+1),
  23          n-1=k, n=k+1=(m+1)/2
  24          如果 m 是偶数，设m=2k,
  25          那么 pow(2,k) > N >= pow(2, k-1/2) > pow(2, k-1),
  26          n-1=k-1,n=k=m/2
  27          所以b[n-1]完全由B[m-1]决定。
  28          余数 M[1] = M - b[n-1]*pow(2, 2*n-2)
  29          
  30          (2) N的次高位b[n-2]可以采用试探法来确定。
  31          因为b[n-1]=1，假设b[n-2]=1，则 pow(b[n-1]*pow(2,n-1) + b[n-1]*pow(2,n-2),
  32          2) = b[n-1]*pow(2,2*n-2) + (b[n-1]*pow(2,2*n-2) + b[n-2]*pow(2,2*n-4)),
  33          然后比较余数M[1]是否大于等于 (pow(2,2)*b[n-1] + b[n-2]) * pow(2,2*n-4)。这种
  34          比较只须根据B[m-1]、B[m-2]、...、B[2*n-4]便可做出判断，其余低位不做比较。
  35          若 M[1] >= (pow(2,2)*b[n-1] + b[n-2]) * pow(2,2*n-4), 则假设有效，b[n-2] =
  36          1；
  37          余数 M[2] = M[1] - pow(pow(2,n-1)*b[n-1] + pow(2,n-2)*b[n-2], 2) = M[1] -
  38          (pow(2,2)+1)*pow(2,2*n-4)；
  39          若 M[1] < (pow(2,2)*b[n-1] + b[n-2]) * pow(2,2*n-4), 则假设无效，b[n-2] =
  40          0；余数 M[2] = M[1]。
  41          
  42          (3) 同理，可以从高位到低位逐位求出M的平方根N的各位。
  43          
  44          使用这种算法计算32位数的平方根时最多只须比较16次，而且每次比较时不必把M的各位逐
  45          一比较，尤其是开始时比较的位数很少，所以消耗的时间远低于牛顿迭代法。
  46          
  47          2. 流程图
  48          (制作中，稍候再上)
  49          
  50          3. 实现代码
  51          这里给出实现32位无符号整数开方得到16位无符号整数的C语言代码。
  52          */
  53          
  54          /****************************************/ 
  55          /*Function: 开根号处理 */ 
C51 COMPILER V7.50   单芲籣上的开方程序                                                    12/28/2006 23:41:23 PAGE 2   

  56          /*入口参数：被开方数，长整型 */ 
  57          /*出口参数：开方结果，整型 */ 
  58          /****************************************/ 
  59          #include <REG51.H> 
  60          #include <stdio.H>
  61          unsigned int sqrt_16(unsigned long M) 
  62          { 
  63   1       unsigned int N, i; 
  64   1       unsigned long tmp, ttp; // 结果、循环计数 
  65   1       if (M == 0)            // 被开方数，开方结果也为0 
  66   1       return 0; 
  67   1      
  68   1       N = 0; 
  69   1      
  70   1       tmp = (M >> 30);       // 获取最高位：B[m-1] 
  71   1       M <<= 2; 
  72   1       if (tmp > 1)           // 最高位为1 
  73   1       { 
  74   2        N ++;                 // 结果当前位为1，否则为默认的0 
  75   2        tmp -= N; 
  76   2       } 
  77   1      
  78   1       for (i=15; i>0; i--)   // 求剩余的15位 
  79   1       { 
  80   2        N <<= 1;              // 左移一位 
  81   2      
  82   2        tmp <<= 2; 
  83   2        tmp += (M >> 30);     // 假设 
  84   2      
  85   2        ttp = N; 
  86   2        ttp = (ttp<<1)+1; 
  87   2      
  88   2        M <<= 2; 
  89   2        if (tmp >= ttp)   // 假设成立 
  90   2        { 
  91   3         tmp -= ttp; 
  92   3         N ++; 
  93   3        } 
  94   2       } 
  95   1       return N; 
  96   1      } 
  97          main()
  98          {
  99   1       unsigned long num;
 100   1       unsigned int result;
 101   1       SCON=0X50;
 102   1       TMOD=0X20;
 103   1       TH1=0XF3;
 104   1       TR1=1;
 105   1       TI=1;
 106   1       scanf("%blu",&num);
 107   1       result=sqrt_16(num);
 108   1       printf("%u\n",result);
 109   1      }


MODULE INFORMATION:   STATIC OVERLAYABLE
   CODE SIZE        =    393    ----
   CONSTANT SIZE    =      9    ----
   XDATA SIZE       =   ----    ----
   PDATA SIZE       =   ----    ----
   DATA SIZE        =   ----      18
C51 COMPILER V7.50   单芲籣上的开方程序                                                    12/28/2006 23:41:23 PAGE 3   

   IDATA SIZE       =   ----    ----
   BIT SIZE         =   ----    ----
END OF MODULE INFORMATION.


C51 COMPILATION COMPLETE.  0 WARNING(S),  0 ERROR(S)