Java浮点数精度溢出
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)$的，还是够用的。