pekempelog

ペケンペイのブログ

Exponential Function Evaluation

This article shows an implementation of the exponential of a formal power series. This runs in O(n log n) time. I compute the nth term of the partition function for benchmark.

https://ideone.com/m1LAWr




[1] is a standard reference of formal power series (?) Newton's method is described in [2] but the correctness is not discussed. Please try it yourself. It is a little difficult but not impossible.




[1] Ivan Niven, Formal Power Series, The American Mathematical Monthy, vol. 76, pp. 871--889, 1969.
[2] R. P. Brent, Multiple-precision zero-finding methods and the complexity of elementary function evaluation, https://arxiv.org/abs/1004.3412.