Edison.X. Blog

傳統作法

只考慮整數情況。一般在求 power 時大多這麼做

double power(double base, int exponment)
{
     double rst=1.0;
     int i;
     if(exponment<0)
           for(exponment=-exponment, i=0; i<exponment; ++i)
                rst/=base;
     else
           for(i=0; i<exponment; ++i)
                rst*=base;
     return rst;
}

筆者私心認為乘法比除法快、準，於是將除法部份改為乘法方式，

原理為 base^(-exp) = 1.0 / (base^exp)

double power(double base, int exponment)
{
     double rst=1.0;
     int i, n = (exponment >= 0) ? exponment : -exponment;
     for(i=n; i; --i)
           rst*=base;
     return (exponment >=0) ? rst : 1.0/rst;
}

效率 O(n)，若 exopnment 為整數情況時，此法也比 math.h 之 pow 快許多。

這裡提效率 O(log(n)) 之 fast power。

虛擬碼

Algorithm FastPower

    E0 : 初始化 base , exponment , rst=1.0, pwr = base

    E1 : 若 exponment <0 成立， n=-exponment；反之 n=exponment

    E2 : n 之最後一個 bit 若為 1，則 rst = rst * base

    E3 : n 右移 1 bit， pwr = pwr * pwr (自身平方)

    E4 : 若 n =0 成立，演算法結束，傳回 rst (exponment >0 ) 或 1.0 / rst (exponment < 0)

    E5 : 回到步驟 E2

End Algorithm

C語言 fastpower

double fastpower(double base, int exponment)
{
     double rst=1.0, pwr=base;
     int n = exponment < 0 ? -exponment : exponment;
     while(n) {
           if(n&1) rst*=pwr;
           n>>=1, pwr*=pwr;
     }
     return exponment < 0 ? 1.0/rst : rst;
}