傳統作法

 

只考慮整數情況。一般在求 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;
}

 

edisonx 發表在 痞客邦 PIXNET 留言(0) 人氣()