原创 算法优化的重要性

                    算法优化的重要性

前些日子，在开发一个单片机的产品时，遇到这么一个问题，就是要将一个无符号的16位数，乘以1.2288后，再赋给另一个无符号的16位数。用C语言可以描述如下：

INT16U x,y;

y = (INT16U)((float)x * 1.2288);    // 注：x的取值范围是500到16000

由于单片机采用的NXP的LPC762，属于51系列的，主频为7.3728MHZ，因此速度较慢。在KeilC51环境中，通过模拟运行，可以得出，运行上述C语句需要的时间为406uS。虽然这个时间比我想象的要快些，但不能满足产品的实时性要求。

由于不能慢足要求，因此我将浮点预算改成了定点运算，即将1.2288变成了12288/10000，这样上述语句就改写成如下：

y = (INT16U)((INT32U)x * (INT32U)12288 / (INT32U)10000);

结果实在是令人遗憾，执行时间不但没降，反而上升到623uS，比浮点运算更慢，估计是增加了一个除法运算引起来的。

无论是定点和浮点运算，时间都是几百微秒，都不能满足产品的实时性要求。因此只能另想办法。

在上面的定点运算中，虽然理论上说定点运算比浮点运算要快，但由于多了定点除法，导致了最终时间不但没有达到要求，而且更慢。因此就沿着这个思路，想到了用分数来近似表示一个浮点数的办法，同时要求除法要快。

所谓除法要快，就是考虑将除法变成移位操作，比如说，除以2，就相当于右移1位，除以4，就相当于右移2位，如果除以65536，就相当于右移16位，或者说直接丢弃低16位。通过这种分析，就可以将1.2288用分数近似表示成80530/65536，实际值为1.228790283203125，相对误差为(1.2288-80530/65536)/1.2288=0.0000079，应该说非常小了。由于x的取值范围是500到16000，绝对误差的最大值发生在x取16000时，此时的误差计算如下：

16000 * 1.2288 – 16000 * 80530/65536 = 19660 – 19660 = 0

可以说在x的取值范围内，没有误差。

那么这样的近似表示的好处是什么呢？答案是只要进行一次定点的乘法，得到一个无符号的32位数，然后直接丢弃低16位，高16位的数就是y。

写成C语句就是：

y = ((INT32U)x * 80530)>>16;

运行上述语句的时间为298uS。很明显，这样的算法比采用浮点运算的时间减少了108uS（相对于减少了26%）。因此可以说，算法在产品的开发中是非常重要的。

为了进一步减少运行的时间，考虑到一个32位的无符号数右移16位后赋给16位的无符号数，在汇编语言中非常容易实现，因此，决定用汇编实现上述语句，在C语言中的语句如下：

y = FUNC(x);

其中FUNC是用汇编语言写的函数，具体的代码如下，在汇编代码中，为了快速实现定点乘法，没有去调用编译器提供的库，而是根据这个具体的应用做了优化，以提高代码的运行速度（也就是说，还是算法的问题）

在汇编代码中，要根据具体问题的特点，进一步进行算法上的优化。在上述公式中，80530＝65536＋14994，这样上面的语句就可以改写成：y=x+x*14994/65536。

这样就可以将乘法变成了2个16位的无符号数的乘法，从而提高代码的运行速度。对2个16位的无符号数的乘法，分析如下：

假设一个16位的无符号数x1，其高8位和低8位表示成a1和b1，则x1 = a1 * 256 + b1。同样，另一个无符号数x2，也可以表示成x2 = a2 * 256 + b2。

x1 * x2 =(a1 * 256 + b1) * (a2 * 256 + b2)

       = a1 * a2 *65536 + (a1 * b2 + a2 * b1) *256 + b1 * b2

通过这样的分解，就可以用51的乘法指令直接运算出a1*a2、a1*b2、a2*b1和b1*b2，而不用采用移位的办法，这样也就提高了运算的速度。另外，由于最终的这个数要除以65536，因此在计算完b1*b2后，可以将低8位直接丢弃，保留高8位，与(a1 * b2 + a2 * b1)*256运算。总之，通过汇编指令的优化，可以大大提高运算速度。下面是FUNC的详细代码，通过在KeilC51环境中的模拟执行，可以得出，该函数的运行时间为49uS。这个时间只有最初采用浮点数时的十分之一左右，可见算法的优化对一个系统来说是多么重要。

       PUBLIC _FUNC

; unsigned int FUNC(unsigned int x)

; 下面的函数完成的功能：

; x * 1.2288 = x + x * 0.2288 = x + x * 14994 / 65536

; 14944用十六进制数表示为3A92H

       RSEG  ?PR?_FUNC?SUB

_FUNC:

       USING   0

; 入口时x已经在寄存器(R6,R7)中

; 第一步实现：(0,R5)<- (R7 * 92H)的高8位

        MOV     B,#92H

           MOV     A,R7

           MUL     AB

        MOV     R5,A          ;只需要保留高8位的结果

; 第二步实现：(R4,R5) <- R7 * 3AH + (R7 * 92H)的高8位

        MOV     B,#3AH

           MOV     A,R7

           MUL     AB            ;结果在（B,A）中

;下面实现(R4,R5)<-(0,R5) + (B,A)

       ADD     A,R5

           MOV     R5,A

       MOV     A,#00H

           ADDC    A,B

     MOV     R4,A

; 第三步实现：(R4,R5) <- (R6 * 92H + R7 * 3A + (R7 * 92H)的高8位)的高8位和进位

        MOV     B,#92H

       MOV     A,R6

       MUL     AB            ; 结果在（B,A）中

        ADD     A,R5          ;加低8位，目的是要进位位

           MOV     A,B          

       ADDC    A,R4         

        MOV     R5,A          ;保留高8位的运算结果

        RLC     A

        ANL     A,#01H

        MOV     R4,A          ;将进位位保存到R2的最低位中

; 第四步实现：(R4,R5) <- R6 * 3A + (R6 * 92H + R7 * 3A + (R7 * 92H)的高8位)的高8位和进位

           MOV     B,#3AH

       MOV     A,R6

           MUL     AB            ; 结果在（B,A）中

       ADD     A,R5         

        MOV     R5,A

        MOV     A,B

        ADDC    A,R4

        MOV     R4,A          ; 到此(R4,R5) <- x * 14994 / 65536

; 第五步实现：x + x * 0.2288

        MOV     A,R5

       ADD     A,R7

           MOV     R7,A

       MOV     A,R4

           ADDC    A,R6

       MOV     R6,A

           RET    

                     2010－9－19