Java浮点数精度溢出

Published: by Creative Commons Licence

  • Tags:

java的浮点数溢出

最近做了一场SRM,其中最后一道题目要求一个公式:

\[\frac{n}{n+1}\frac{1}{\prod_i^na_i}[x^{n+1}]^R_L\]

这个公式本身没有什么问题,但是上面的公式会被重复计算10万次,为了性能考虑,需要预先计算$\prod_i^na_i$。但是这里$1\leq a_i\leq 10^9$,因此要准确存储,需要$10^6$个十进制位才行。当然我们可以舍弃一些精度,但是考虑到double类型的十进制指数最多为$308$,因此存不下的。

这里我提两种解决方案。

第一种,就是我们将每个数以对数形式保存,即$x$保存为$\ln x$,使用的时候再还原。这样我们要存储$\ln \prod_i^na_i$,就非常简单了,我们只需要存储$\sum_i^n\ln a_i$,这个结果的范围是不超过$10^7$的,这样就能用double存了。同理计算$x^{n+1}$的时候也可以通过计算$(n+1)\ln x$来获得结果。

但是上面这种方法还是会存在精度问题,我试用了这种方法,精度误差大概为$10^{-5}$,可以接受,但是无法AC。(如果用C++,可以使用long double类型,这样精度就够了,可以使用这种方法)。

第二种方法,是用java自带的BigDecimal类型,它支持幂运算,加减乘除。为啥可以使用这个呢,因为之所以不能直接用double算,不是因为精度存不下,而是double的指数位太少了,所以没法表示一个非常大的数,我们利用BigDecimal来存储一个很大的指数位。但是如果直接使用的话,会发现计算非常慢,因为默认运算是不带精度溢出的,这样随着计算次数的增加,要存储的精度位也需要越大,对应的计算速度也会越慢。这时候我们可以使用MathContext来限制它可以使用的位数,个人实测30位就足够了,误差仅为$10^{-12}$。由于仅存储30位(这里提到的30位是指十进制位,相当于快100个二进制位了),因此加减乘除每次运算的时间复杂度可以认为是$O(30)$的,还是够用的。