首页 > 搜索 > 近似算法是啥,这个求指数函数exp()的快速近似方法的原理是什么?

近似算法是啥,这个求指数函数exp()的快速近似方法的原理是什么?

互联网 2020-10-22 14:54:08
在线算命,八字测算命理
原理非常简单,思路非常巧妙,全靠ieee浮点数构成形式:

我们要求exp(x),也就是 e^x并得到一个double的结果。

观察double浮点数的构成形式:Y = M * 2^E其中E为指数,M为尾数。

只观察指数部分,会发现实际上它们均为X^Y形式的。

那么就有意思了,我们要求的是X^Y形式的一个数,而由于都是浮点表达,我们的输入x也是一个X^Y的数,那么,这之间有没有什么可以玩的东西呢?

慢慢来,我们先来看看2^Y如何简便计算:假设我们有个浮点数Y,要计算2^Y观察double浮点数的构成形式:Y = M * 2^E我擦,原来2^Y已经藏在结构里面了啊!就是E啊!所以说,只要我们把Y=E,再把Y这个数放在正确的bit位置上,我们就构建好这个数了。

那么,如何放置呢?我们观察ieee的double浮点数的构成形式:第零位bit是符号位往后11位是指数位往后剩下的是尾数位

也就是说,我们只需要把Y转成int,然后放入这个浮点数的第63-52位上就行了!

那么,怎么放法?首先,我们将这个double转为int,得到一个32位的int32,再将这个int32向左移动20位,这样,这个int32的前12位就挪到了这个int32的最高12位上,这样这个int32就和ieee的double浮点数的前63-32位对应上了。但是别忙,题主的方法中,并不是直接使用移位计算的,而是直接使用乘法,乘上了2^{20}= 1048576,我们知道乘2^20和移位能达到同样的效果,这也就是代码里的这一步:

1512775 * y你会说啦,那不对啊,这明明乘的是1512775啊,对,那是因为求的是e的pow而不是2的pow。e的咱们待会儿再说。

再然后还没完,后面为什么还带一个

+ 1072632447这是因为,double的指数部分的int并非常见补码形式的int,而是一个带有偏移量的int,偏移量为2^12次方的一半也就是1023,大于1023的数值才被认为是正数。因此我们要加上这个偏移量,即加上1023*2^20=1072693248。那你就又问了,不对啊人家明明加的是1072632447啊,没错,多出来的60801是一个补偿值,具体是如何补偿的,详见“A Fast, Compact Approximation of the Exponential Function” 的第四节。

综上,题主的代码就好理解了:

double d; // 先将尾数的后32位抹零。*(reinterpret_cast(&d) + 0) = 0;//再计算指数位,移位,加上偏移量和补偿值*(reinterpret_cast(&d) + 1) = static_cast(1512775 * y + 1072632447);这么做之后,大家有没有发现有什么问题?有的! 那就是尾数并不都是0!虽然后32位被抹零了,但前面指数加尾数的部分:并不都为0,因为这一步://再计算指数位,移位,加上偏移量和补偿值*(reinterpret_cast(&d) + 1) = static_cast(1512775 * y + 1072632447);这一步中的(int)(1512775 * y + 1072632447)这个int32只保证前面12位是指数没问题,可后面还跟着20位呢!什么鬼?首先,跟着的这20位是加到尾数里的,本身影响就不大,另外人家论文里特意说了,跟着的这20位不但不会降低精度反而对精度有帮助,具体的我实在没仔细看,有兴趣那你只好去看论文了。

至此,一个简单的powerOfTwo的快速计算就完成了。那么你就问了,说了半天,exp可怎么办呢?能算2就能算e!观察此式:e^{b}有如下等式:e^{ln(a^b)} = a^b有:e^{ln(a)*b} = a^b令a=2:e^{ln(2)*b} = 2^b令x=ln(2)*b,则有:e^x = 2^{x/ln(2)}

也就是说,我们要计算exp(x),只需要计算2^(x/ln(2))就行了。而计算2^x的方法咱们前文已经讲了。那么,重新观察前文中的这一行:

1512775 * y刚才说了,这里应该乘1048576,为什么乘了1512775?因为它算的是e,不是2,所以乘的是1048576 / ln(2) !

至此,这个简便方法的大致步骤就讲完了。

这个算法的误差主要来源于主要发生在这里:

static_cast(1512775 * y + 1072632447);这个double转int时,小数部分应该被计入最终数字中的尾数,但却被忽略了,所以会产生一个来回晃动的误差。就像题主那张图那样。
免责声明:非本网注明原创的信息,皆为程序自动获取互联网,目的在于传递更多信息,并不代表本网赞同其观点和对其真实性负责;如此页面有侵犯到您的权益,请给站长发送邮件,并提供相关证明(版权证明、身份证正反面、侵权链接),站长将在收到邮件12小时内删除。

相关阅读

一周热门

查看更多