一种快速求幂的算法，大神们来议论两句吧！

weiweishuo

  正整数求幂，一般的写法是：
[code=c]pow_int:        ;pow_int(int base, int exp)
        mov ebx,[esp+4]
        mov ecx,[esp+8]
        mov eax,1
        .mult:
        mul ebx
        loop .mult
       
        ret[/code]
  我今天想到了一种加速的算法（当然，肯定早就有人想到了，只是我孤陋寡闻没学过）：例如计算3的21次方，3exp(21)可以拆解成:
  3exp(16) + 3exp(4) +3exp(1)
  我们求3exp(16)时候，只需要4次乘法，3exp(4)只要2次乘法，而且在求3exp(16)的过程中，顺便就求出了3exp(4)。
  下面我粗糙的用汇编实现了，只能处理 1<指数<32的情形。
[code=c]
[section .text]
pow_int_fast:
        mov eax,[esp+4]
        mov ebx,[esp+8]
        mov edi,magic_val
        mov [edi],eax

        bsr ecx,ebx
       
        .fill_magic:
        mul dword [edi]
        add edi,4
        mov [edi],eax
        loop .fill_magic

        mov eax,1
        mov esi,magic_val
       
        .accumulate:
        bsf ecx,ebx
        jz .return
        btr ebx,ecx
        mul dword [esi+ecx*4]
        jmp .accumulate
       
        .return:
        ret

[section .data]
magic_val:
times 5 dd 0[/code]
这两个汇编模块运行结果都是正确的。我对比测试他俩的速度，几乎没有区别！
我的cpu是酷睿i5的，我怀疑后者虽有算法优势，但代码较长，对cache，流水和分支预测都不友好，因此将功折罪了。大神们能否指点指点？

下面是我的测试代码：
[code=c]#include<stdio.h>
#include<sys/time.h>
#define timelen(a,b) ((b.tv_sec - a.tv_sec)*1000 +(b.tv_usec - a.tv_usec)/1000)
int pow_int(int base, int exp);
int pow_int_fast(int base, int exp);
int main(void){
        int base;
        int repeat;
        int exp;
        struct timeval t0,t1,t2;
        while(printf("\nbase exp repeat\n"),scanf("%d%d%d",&base,&exp,&repeat)){
                int x,x_fast;
                repeat*=1000000;
                for(int k=0;k<5;k++){
                        gettimeofday(&t0,0);
                        for(int i=0;i<repeat;i++) x=pow_int(base,exp);
                        gettimeofday(&t1,0);
                        for(int i=0;i<repeat;i++) x_fast=pow_int_fast(base,exp);
                        gettimeofday(&t2,0);
                        printf("x:%10d%10d\ny:%10d%10dfast\n",x,timelen(t0,t1),x_fast,timelen(t1,t2));
                }
        }
        return 0;
}[/code]
测试如下：
第一组：
base exp repeat
2    20  10
x:   1048576       380
y:    1048576        126
x:   1048576       347
y:    1048576        127
x:   1048576       348
y:    1048576        126
x:   1048576       347
y:    1048576        128
x:   1048576       347
y:    1048576        126

第二组：
base exp repeat
3    10  10                                                                        
x:     59049       193
y:      59049        108
x:     59049       183
y:      59049        107
x:     59049       183
y:      59049        108
x:     59049       183
y:      59049        108
x:     59049       184
y:      59049        107

把测试代码里两行for(int i=...)交换位置
第一组：
2    20  10
x:   1048576       132
y:    1048576        345
x:   1048576       126
y:    1048576        347
x:   1048576       126
y:    1048576        346
x:   1048576       126
y:    1048576        346
x:   1048576       126
y:    1048576        344

第二组：
3    10  10
x:     59049       117
y:      59049        182
x:     59049       107
y:      59049        183
x:     59049       107
y:      59049        184
x:     59049       108
y:      59049        183
x:     59049       108
y:      59049        183

之所以交换位置，是发现交换位置后输出结果差别巨大，似乎先测试的模块总是运行的慢，后测试的模块总是运行的快。交换就像是高中时候做的对照实验。

folklore

做大数运算时， 很自然不会想到这个方法， 不然没办法计算啊。