C++之竹

无论是太阳下,还是风雨中,都要成长!

常用链接

统计

最新评论

关于数值的整数次方的计算

在计算一个浮点数(双精度或单精度)的整数次方时,一般的,我们会直接使用 C++ 本身所提供的 pow 函数,事实上也推荐直接使用 pow 函数(为了称呼简便,后面称该 pow 函数为系统 pow 函数)。

但是,当我们准备写一个自己的 pow 时,我们又会怎么写呢?一般的,我们会写上一个 for 循环来循环幂的指数次,而且每次循环都会去执行一次浮点数的乘法操作。但是,当我们拿这个 pow 函数来跟系统 pow 函数作一运行比较时,就会发现,我们的 pow 实在是太低效了。那么怎么样才能使我们自己写的 pow 也能有系统函数那样的时间效率呢?

仔细分析,我们用的那个求幂值的循环过程,就能发现,其实我们还是做了很多不必要的浮点数乘法炒作。整个计算过程太过按步就班了。譬如说在计算 val(待传入pow 函数求幂的浮点数,下同) 的4次方,我们总是先计算出3次方的值,然后再根据3次方的值和原始值来求4次方的值;然而,我们其实本可以在计算出2次方值后,平方2次方值来得到4次方的值的。接下来,就是探索算法,以减少浮点数乘法的事了。

通过所学的指数函数的知识,我们知道指数函数有着这样的性质:

  • V(a+b) = Va * Vb
  • Va*b = (Va)b             ;这里 * 为乘法运算符

另外,对于整数,有如下性质:

  1.  2n = (1 << n)         ;这里 << 是向左移位的操作符。
  2. C++中的任何一个正整数(负整数同,但须处理好符合位)都可以表示为以下形式:
    n = 2a1 + 2a2 + ... + 2ak
    (其中,a1, a2, ... , ak 为闭区间 [0, 30] 上的整数值,且互不相同。)

由此,我们就可以事先依次计算出 val, val2, val4, ... , val30 预存备用,然后再根据 val 相应 bit 上是 1 还是 0,来选取相应的预存数据进行相乘,从而得到最终的结果。当然,合理设计逻辑,还可以减少所需的预存数据。下面是我的Pow 代码,欢迎点评。

 

#define INTBITS_WITHOUT_SIGN 31 // the bit-size of type int with the sign bit being excluded.


bool IsZero(double val, double precision /*= DEFAULT_PRECISION*/)
{
    
if (precision >= 0{
        
return (-precision <= val) && (val <= precision);
    }
 else {
        
return (precision <= val) && (val <= -precision);
    }

}


double Pow(double val, int exponent)
{
    
if (IsZero(val)) {
        
return 0.0;
    }


    
if (0 == exponent) {
        
return 1.0;
    }


    
bool bIsExponentMinus = false;
    
if (exponent < 0{
        exponent 
= -exponent;
        bIsExponentMinus 
= true;
    }


    
double tempVal[INTBITS_WITHOUT_SIGN];
    memset(tempVal, 
0, INTBITS_WITHOUT_SIGN);
    tempVal[
0= val;

    
double result = 1.0;
    
int index = 0;
    
while (exponent != 0{
        
if ((exponent & 1!= 0{
            result 
*= tempVal[index];
        }


        exponent 
>>= 1;
        
if (exponent != 0{
            tempVal[index 
+ 1= tempVal[index] * tempVal[index];
            
++index;
        }

    }


    
if (bIsExponentMinus) {
        result 
= 1.0 / result;
    }


    
return result;
}

 
【补充】:

1. 在指数中,0的负数次方和0的0次方,都是没有意义的,所以对“if (IsZero(val))”分支内的处理如果能加上一些异常的输出就更好了,如:

   在Widows下,可通过 SetLastError(...) 来设置错误码。

2. Pow中的 “double tempVal[INTBITS_WITHOUT_SIGN];” 一句,改写为

   double * pTempVal = new double[sizeof(int) * 8 - 1];

(当然,后面代码中的tempVal 也都要改为相应的 pTempVal,同时须记得在return 前把delete [] pTempVal)

就可以使代码也能够适应于64位系统的处理。对于无符号整数的为指数的情况,则辅助值空间应为“sizeof(unsigned int) * 8”,同时,无需再考虑负指数的情况。

(这里,很感谢春秋十二月的补充。)
 

posted on 2012-03-17 04:01 青碧竹 阅读(2884) 评论(4)  编辑 收藏 引用 所属分类: 算法相关

评论

# re: 关于数值的整数次方的计算 2012-03-17 09:26 tb

算法不错  回复  更多评论   

# re: 关于数值的整数次方的计算 2012-03-17 11:12 zdhsoft

好像浮点数有这样的汇编指令!  回复  更多评论   

# re: 关于数值的整数次方的计算 2012-03-17 13:27 春秋十二月

楼主算法不错,补充说明几个小问题:
(1)C++中的任何一个正整数(负整数同,但须处理好符合位)都可以表示为以下形式:n = 2^a1 + 2^a2 + ... + 2^ak
(其中,a1, a2, ... , ak 为闭区间 [0, 30] 上的整数值,且互不相同。)
正确描述应该是:n = k1*2^a1+k2*2^a2+...+kn*2^ak,k(i)=0或1。你这里取值为30,针对的是有符号4个字节大小的整数。
(2)依(1)所述,如果是无符号整数或8个字节大小的整数,就不是30了,为完备灵活起见,Pow函数内部辅助空间大小应依据int或unsigned int的大小来编译时决定。
  回复  更多评论   

# re: 关于数值的整数次方的计算 2012-03-18 23:31 青碧竹

@春秋十二月
多谢兄弟的补充!在写这篇博文时,确实是只针对了32位的int。

对于补充(1):其实 32位int的完整表示为
((-1)^<符号位数值>) * (k0*2^0+k1*2^1+...+k30*2^30)
ki ∈{0,1}, i ∈{0, 1, ... , 30}
而在我文中,是略去 符号位 和 ki=0 的项后的表示形式。

对于补充(2):64位系统日益普遍的现在,确实应该考虑64为整数的情况。这点我疏忽了。
  回复  更多评论   


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理