在任意精度十进制库中实现基本和特殊数学函数
Implementing basic and special mathematical functions in an arbitrary precision decimal library
如果你有一个任意精度的十进制库,但它没有任何基本的(例如指数函数、正弦函数)或特殊的(例如误差函数、对数积分)数学函数,什么是实施它们的最佳方式吗?
显然,由于这些函数中的大多数值都是无理数,因此只有在指定精度下给出答案才有意义。所以假设我想计算 erf(x) (例如)到小数点后 50 位,最好的方法是什么?
我得到的最佳答案是将参数映射到某个合适的范围,然后使用函数的泰勒级数得到一个(希望)相当快地收敛的答案。我们可以使用类似泰勒定理的东西来限制误差项,但通常,这涉及将阶乘与 10 的幂进行比较(例如,请参见维基页面 Taylor's Theorem 上 "Taylor's theorem in one real variable" 下的示例),其中,虽然可行,但似乎冗长。
此外,虽然实现这些功能似乎是可行的,但在处理这些功能的组合时如何处理精度?例如,如果我们想计算 1000*exp(sqrt(2)) 到小数点后 n 位,我们应该计算中间结果的精度级别以获得准确的最终答案并不是很明显。
有谁知道我可以从哪里开始解决这个问题?
这个主题很宽泛,每种函数都有很大的不同。泰勒级数是最后的手段,如果你还想要速度,通常不可用。通常有替代方案(Chebyshev,...),但每种类型的功能都不同,需要不同的方法来优化 performance/precision。例如:
- 基本测角函数有时用CORDIC算法求解
pow,exp,log
可以用log2,exp2
来解决
log2,exp2
可以通过基础数学 (+,-,*,/
) 和位 (<<,>>,&,|,^
) 函数使用 sqrt
来求解小数位
sqrt
可以通过binary search without multiplication 计算
要更好地理解任意精度函数之间的差异,请参阅我的任务:
- Fast bignum square computation
- arbitrary precision Floating Point Divider
- Fast exact bigint factorial
- fixed point bignum pow
因此,您最好询问有关特定功能实现的问题,而不是针对任何功能的任意方法。
结果的位宽通常被截断为函数属性的一些合理大小。例如乘法是操作数位的总和,+,-
可以比最大操作数大 1 位,等等...
在选择算法时不要忘记,算法基础复杂度与实际实现复杂度之间存在很大差异。尤其是在任意精度数字上,因为即使像加法这样简单的事情也不再 O(1)
...
如果你有一个任意精度的十进制库,但它没有任何基本的(例如指数函数、正弦函数)或特殊的(例如误差函数、对数积分)数学函数,什么是实施它们的最佳方式吗?
显然,由于这些函数中的大多数值都是无理数,因此只有在指定精度下给出答案才有意义。所以假设我想计算 erf(x) (例如)到小数点后 50 位,最好的方法是什么?
我得到的最佳答案是将参数映射到某个合适的范围,然后使用函数的泰勒级数得到一个(希望)相当快地收敛的答案。我们可以使用类似泰勒定理的东西来限制误差项,但通常,这涉及将阶乘与 10 的幂进行比较(例如,请参见维基页面 Taylor's Theorem 上 "Taylor's theorem in one real variable" 下的示例),其中,虽然可行,但似乎冗长。
此外,虽然实现这些功能似乎是可行的,但在处理这些功能的组合时如何处理精度?例如,如果我们想计算 1000*exp(sqrt(2)) 到小数点后 n 位,我们应该计算中间结果的精度级别以获得准确的最终答案并不是很明显。
有谁知道我可以从哪里开始解决这个问题?
这个主题很宽泛,每种函数都有很大的不同。泰勒级数是最后的手段,如果你还想要速度,通常不可用。通常有替代方案(Chebyshev,...),但每种类型的功能都不同,需要不同的方法来优化 performance/precision。例如:
- 基本测角函数有时用CORDIC算法求解
pow,exp,log
可以用log2,exp2
来解决
log2,exp2
可以通过基础数学 (+,-,*,/
) 和位 (<<,>>,&,|,^
) 函数使用sqrt
来求解小数位sqrt
可以通过binary search without multiplication 计算
要更好地理解任意精度函数之间的差异,请参阅我的任务:
- Fast bignum square computation
- arbitrary precision Floating Point Divider
- Fast exact bigint factorial
- fixed point bignum pow
因此,您最好询问有关特定功能实现的问题,而不是针对任何功能的任意方法。
结果的位宽通常被截断为函数属性的一些合理大小。例如乘法是操作数位的总和,+,-
可以比最大操作数大 1 位,等等...
在选择算法时不要忘记,算法基础复杂度与实际实现复杂度之间存在很大差异。尤其是在任意精度数字上,因为即使像加法这样简单的事情也不再 O(1)
...