Re: A function for inverting power series

[Bill Allombert <Bill.Allombert@math.u-bordeaux.fr>]

On Fri, Nov 04, 2016 at 10:22:39AM +0100, Thomas Baruchel wrote:
> Hi,
> 
> Maybe it will be more convenient to compile a standalone file containing
> some benchmark tests. The remaining of my message is a piece of C code
> with a 'main' function. Could you compile it and see if it would be worth
> adding the function ser_inv2 (since 'ser_inv' already exists). This function
> behaves not too bad for inverting power series with a small number of terms,
> most favorable cases being small powers of 2 like 8, 16, 32.x;

The behaviour of any power series algorithm depends in a large part of the
coefficient ring.  A simple complexity model is to count only the number
of operations on the base ring. However this only reflects practical
running time when the ring is a finite field.

So for benchmarking purpose, it might be better to use finite fields,
and use much larger precision.

Furthermore in PARI 2.9, ser_inv is a wrapper around RgXn_inv which is
faster than ser_inv in PARI 2.7, so it would be better to implement 
ser_inv2 as a function RgXn_inv_new.

We have plans to add dedicated functions for power series over finite
fields (Flxn_, FlxqXn, FpXn, FpXQXn, FqXn). The same code can be reused
with little modification.

Your code seems OK.
Replace
 if (p2[l])
by
 if (gel(p2,l))
because some compiler will take this as a pretext to miscompile your code.

Cheers,
Bill.