Bill Allombert on Fri, 04 Nov 2016 12:02:51 +0100 |
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
Re: A function for inverting power series |
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.