Karim BELABAS on Sat, 16 Mar 2002 12:26:21 +0100 (MET)


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

Re: serreverse() bugs


On Fri, 15 Mar 2002, Michael Somos wrote:
> There is at least two bugs in 'serreverse()'. One is very easy to fix,
> but the other is probably a stack clobber bug. Here is the evidence :
>
> ? \v
>                  GP/PARI CALCULATOR Version 2.2.3 (development)
>                  UltraSparc (MicroSparc kernel) 32-bit version
>               (readline v2.2 enabled, extended help not available)
                                        ^^^^^^^^^^^^^^^^^^^^^^^^^^^
Btw, is this expected ? [ e.g perl not installed on your system? ]

> ? serreverse(O(x))
>   ***   incorrect type in gmulsg.
> ? serreverse(x+O(x^2))
>   ***   bug in GP (Bus Error), please report
> ? oo=12;
> ? a(n)=eval(Str("a"n))
> ? d(z,n)=denominator(polcoeff(z,n))/n!
> ? y=sum(n=1,oo,a(n)*x^n/n!,x*O(x^oo));
> ? for(n=2,oo,z=serreverse(y+x*O(x^n));print(n" "gettime" "d(z,n)))
[...]
> 5 0 0
[...]
> The first bug is due to assumption that terms exist which don't in :
>
>     u[2]=un; u[3]=lmulsg(-2,(GEN)x[3]);
>     y[2]=un; y[3]=lneg((GEN)x[3]);

Easy to fix indeed. In fact a few lines above:

    a = (GEN)x[2];
    if (gcmp1(a)) ...

was already making undue assumptions.

> The second bug is a mystery to me.

Second bug is unrelated to serreverse and took place in
  gdivgs(t_RFRAC x, long s).
This function implicitly assumed that the gcd of numerator(x) and s was an
integer. [it can in fact be a rational number]. So not a stack clobber after
all.

I fixed both of these in the CVS sources.

Btw, I also improved on
(12:18) gp > serreverse(x+O(x^1000))
time = 1mn, 42,290 ms
%1 = x + O(x^1000)

    Karim.
-- 
Karim Belabas                    Tel: (+33) (0)1 69 15 57 48
Dép. de Mathematiques, Bat. 425  Fax: (+33) (0)1 69 15 60 19
Université Paris-Sud             Email: Karim.Belabas@math.u-psud.fr
F-91405 Orsay (France)           http://www.math.u-psud.fr/~belabas
--
PARI/GP Home Page: http://www.parigp-home.de/