Efficient series expansion of exp(p(x))

Arithmetic, algebra, number theory, sequence and series, analysis, ...
Post Reply
plamenko
Posts: 6
Joined: Sun Sep 25, 2011 3:46 pm

Efficient series expansion of exp(p(x))

Post by plamenko » Thu Dec 21, 2017 9:12 pm

I asked about this some time ago on math.stackexchange, here is the link https://math.stackexchange.com/question ... n-of-exppx.

I've seen recently that someone mentioned in in the problem thread of one of the project euler problems that this can actually be done. They said:
... and then calculate the exponential function of prepared polynomial (in modulo $x^n$) in $O(n \log n)$ by Newton's method and fast convolution.
Can anyone please point to the algorithm?

plamenko
Posts: 6
Joined: Sun Sep 25, 2011 3:46 pm

Re: Efficient series expansion of exp(p(x))

Post by plamenko » Thu Dec 21, 2017 10:20 pm

Eh, this time googling was successful.
Found this: http://www.eecs.harvard.edu/~htk/public ... t-kung.pdf

Post Reply