Karim Belabas on Tue, 20 Apr 2004 17:51:26 +0200


[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]

Re: bug report


* Denis Simon [2004-04-19 19:25]:
> ? \v
>           GP/PARI CALCULATOR Version 2.2.8 (development CHANGES-1.935)
>                 i686 running linux (ix86 kernel) 32-bit version
>           compiled: Apr 19 2004, gcc-3.2 (Mandrake Linux 9.0 3.2-1mdk)
>                 (readline v4.3 enabled, extended help available)
> ? Y=Mod(y,y+1);Mod(Y*x,x-1)^2
>   ***   bug in FpX_divrem, p==NULL, please report

Fixed in CVS. This code has become mostly obsolete, but it may still useful
for GP users.

Background: "modular" operations e.g in (Z/p)[X] or R[X]/(T(X)) for some
ring R are done in GP via the t_INTMOD and t_POLMOD types and dynamic
typing, which provide automatic reduction in possibly complicated
(commutative) algebras. This is simple and powerful, but terribly
inefficient compared to "lifted" representations [ where reduction modulo
appropriate ideals is delayed until it becomes useful, and multivariate
objects are interpolated to asymptotically fast univariate arithmetic ].

Internally (in libpari), these types have almost disappeared, replaced
everywhere by the new modular kernel [ to be documented in the near future,
now that the interface have stabilized ], which is orders of magnitude faster
(and even supports some restricted FFTs with the GMP kernel, via Kronecker's
trick).  The downside is that interfaces are much more rigid ( e.g assume
the main inputs are polynomials in the same variable, whose coefficients
are integers in the range [0, p-1] ).


Of course, there's no way to use this directly under GP yet ( one needs to
install() a number of routines first ). The error above came from the one
place in the whole library ( gsqr(t_POL) ), where the library tries
to be clever, and determine whether the coefficient ring of the t_POL
supports fast lifted representation [ this was introduced in 1997, long
before the representations actually became available... ].

Now that the whole modular kernel has been standardized (by Bill, mostly),
some ad hoc assumptions made at the time have become invalid. I have
simply cleaned up this lone gsqr() call.

Cheers,

    Karim.
-- 
Karim Belabas                     Tel: (+33) (0)1 69 15 57 48
Dep. de Mathematiques, Bat. 425   Fax: (+33) (0)1 69 15 60 19
Universite Paris-Sud              http://www.math.u-psud.fr/~belabas/ 
F-91405 Orsay (France)            http://pari.math.u-bordeaux.fr/  [PARI/GP]