指数运算快速算法

2019-04-14 20:56发布

pow(x,y)  => exp(y*log(x)) 用e指数和2对数替换一般的指数运算,log函数本身通过泰勒展式计算,相比pow会损失一点精度,但提高了速度。
转:http://www.guokr.com/answer/595717/
exp(y*log(x))和pow(x,y)的区别在于前者不能处理x<=0的部分。100M次循环统计平均下来每次的执行时间大概分别是36ns和40ns的样子。考虑到我的机器单纯的乘法循环单次执行时间大概是0.2~0.3ns,应该是差了20个clock cycle的样子
显然的,x^y==(|x|^y)*(sgn(x)^floor(y))*(sgn(x)^frac(y))
(|x|^y)和(sgn(x)^floor(y))当然不会有问题(x!=0)
对任意0>z>1,考虑双精度浮点一般的格式(11-52-1),其最终表示结果对应的10进制数一定是(2*k+1)/2^m的形式(4*k<2^m,m<56)
当sgn(x)=-1;frac(y)!=0时,设frac(y)=(2*k+1)/2^m,则有(sgn(x)^frac(y))=power(power(-1,2*k+1),2^-m)=power(-1,2^-m)为非实数
(所以说现有的浮点数格式下负数的奇次方根什么的还是自己手工处理吧,用VS2010写的试验程序,pow(-1,1.0/5)果然算不出来)
fact(y)==0的判断也应该不难,最低的11位的读出来值为x,尾数中第x+1到第52位不全为0则fact(y)!=0。按说判断不应该消耗太长的时间,那这10%的时间差距是出在哪的?


计算log2(x)时,产生一个大数结果t1和一个小数结果t2,即前几次级数展开之和放到t1,后几次级数展开之和放到t2,t1相比t2来说很大,大得如果直接t1+t2的话会丢精度。乘以y时,要单独相乘,得到w1=y*t1和w2=y*t2,再把它们的小数部分提出来之后再相加。如果y比较大,那么w1的小数部分与w2的小数部分相比就不显得那么大了,它们相加就显得很有意义,能获得一个很精确的y'的值。