formal power series
keith.briggs at bt.com
Mon Oct 24 16:23:29 CEST 2005
(Hopefully not considered off-topic ...)
We have several projects built on top of gmp, but I don't see a formal power series package anywhere.
This is despite some of our esteemed developers writing papers about fast algorithms for such problems.
I would find such a package very useful, and in fact have written prototypes, but I'm never happy with what I
produce. Has anyone else tried? Some relevant thoughts:
1. probably we want rational coefficients in general, but for exponential generating functions it might be preferable
to make the factorial implicit.
2. we have plenty of fast algorithms in the literature (Brent, Traub, Henrici, Bernstein, Zimmermann, ...) including
FFT and Newton-based methods. But has anybody ever done a test to see how long a series has to be in practice
for these to win? In combinatorics applications, the coefficients can get huge, so it doesn't make sense to assume
a constant time for all scalar operations.
3. could we mimic the gmp design, with a lower layer like mpn, and then a user layer?
4. I'd like to solve implicit and functional equations, not just do the standard + - * / exp log sqrt etc.
5. We might need a sparse representation to store things like x^n*f(x^m) (with big n and m) efficiently.
More information about the gmp-discuss