Code coverage tests

This page documents the degree to which the PARI/GP source code is tested by our public test suite, distributed with the source distribution in directory src/test/. This is measured by the gcov utility; we then process gcov output using the lcov frond-end.

We test a few variants depending on Configure flags on the pari.math.u-bordeaux.fr machine (x86_64 architecture), and agregate them in the final report:

The target is 90% coverage for all mathematical modules (given that branches depending on DEBUGLEVEL or DEBUGMEM are not covered). This script is run to produce the results below.

LCOV - code coverage report
Current view: top level - basemath - RgX.c (source / functions) Hit Total Coverage
Test: PARI/GP v2.8.0 lcov report (development 19053-42ab05e) Lines: 1261 1377 91.6 %
Date: 2016-06-29 Functions: 138 148 93.2 %
Legend: Lines: hit not hit | Branches: + taken - not taken # not executed Branches: 828 1010 82.0 %

           Branch data     Line data    Source code
       1                 :            : /* Copyright (C) 2000  The PARI group.
       2                 :            : 
       3                 :            : This file is part of the PARI/GP package.
       4                 :            : 
       5                 :            : PARI/GP is free software; you can redistribute it and/or modify it under the
       6                 :            : terms of the GNU General Public License as published by the Free Software
       7                 :            : Foundation. It is distributed in the hope that it will be useful, but WITHOUT
       8                 :            : ANY WARRANTY WHATSOEVER.
       9                 :            : 
      10                 :            : Check the License for details. You should have received a copy of it, along
      11                 :            : with the package; see the file 'COPYING'. If not, write to the Free Software
      12                 :            : Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. */
      13                 :            : 
      14                 :            : #include "pari.h"
      15                 :            : #include "paripriv.h"
      16                 :            : 
      17                 :            : /*******************************************************************/
      18                 :            : /*                                                                 */
      19                 :            : /*                         GENERIC                                 */
      20                 :            : /*                                                                 */
      21                 :            : /*******************************************************************/
      22                 :            : 
      23                 :            : /* Return optimal parameter l for the evaluation of n/m polynomials of degree d
      24                 :            :    Fractional values can be used if the evaluations are done with different
      25                 :            :    accuracies, and thus have different weights.
      26                 :            :  */
      27                 :            : long
      28                 :    1781495 : brent_kung_optpow(long d, long n, long m)
      29                 :            : {
      30                 :            :   long p, r;
      31                 :    1781495 :   long pold=1, rold=n*(d-1);
      32         [ +  + ]:   10525660 :   for(p=2; p<=d; p++)
      33                 :            :   {
      34                 :    8744165 :     r = m*(p-1) + n*((d-1)/p);
      35         [ +  + ]:    8744165 :     if (r<rold) { pold=p; rold=r; }
      36                 :            :   }
      37                 :    1781495 :   return pold;
      38                 :            : }
      39                 :            : 
      40                 :            : static GEN
      41                 :    7753765 : gen_RgXQ_eval_powers(GEN P, GEN V, long a, long n, void *E, const struct bb_algebra *ff,
      42                 :            :                                            GEN cmul(void *E, GEN P, long a, GEN x))
      43                 :            : {
      44                 :    7753765 :   pari_sp av = avma;
      45                 :            :   long i;
      46                 :    7753765 :   GEN z = cmul(E,P,a,ff->one(E));
      47         [ +  + ]:    7753713 :   if (!z) z = gen_0;
      48         [ +  + ]:   60085109 :   for (i=1; i<=n; i++)
      49                 :            :   {
      50                 :   52331352 :     GEN t = cmul(E,P,a+i,gel(V,i+1));
      51         [ +  + ]:   52331205 :     if (t) {
      52                 :   51187928 :       z = ff->add(E, z, t);
      53         [ +  + ]:   51187971 :       if (gc_needed(av,2)) z = gerepileupto(av, z);
      54                 :            :     }
      55                 :            :   }
      56                 :    7753757 :   return ff->red(E,z);
      57                 :            : }
      58                 :            : 
      59                 :            : /* Brent & Kung
      60                 :            :  * (Fast algorithms for manipulating formal power series, JACM 25:581-595, 1978)
      61                 :            :  *
      62                 :            :  * V as output by FpXQ_powers(x,l,T,p). For optimal performance, l is as given
      63                 :            :  * by brent_kung_optpow */
      64                 :            : GEN
      65                 :    4868698 : gen_bkeval_powers(GEN P, long d, GEN V, void *E, const struct bb_algebra *ff,
      66                 :            :                                      GEN cmul(void *E, GEN P, long a, GEN x))
      67                 :            : {
      68                 :    4868698 :   pari_sp av = avma;
      69                 :    4868698 :   long l = lg(V)-1;
      70                 :            :   GEN z, u;
      71                 :            : 
      72         [ +  + ]:    4868698 :   if (d < 0) return ff->zero(E);
      73         [ +  + ]:    4410339 :   if (d < l) return gerepileupto(av, gen_RgXQ_eval_powers(P,V,0,d,E,ff,cmul));
      74         [ -  + ]:    2036288 :   if (l<2) pari_err_DOMAIN("gen_RgX_bkeval_powers", "#powers", "<",gen_2,V);
      75                 :    2036288 :   d -= l;
      76                 :    2036288 :   z = gen_RgXQ_eval_powers(P,V,d+1,l-1,E,ff,cmul);
      77         [ +  + ]:    3343423 :   while (d >= l-1)
      78                 :            :   {
      79                 :    1307136 :     d -= l-1;
      80                 :    1307136 :     u = gen_RgXQ_eval_powers(P,V,d+1,l-2,E,ff,cmul);
      81                 :    1307128 :     z = ff->add(E,u, ff->mul(E,z,gel(V,l)));
      82         [ +  + ]:    1307135 :     if (gc_needed(av,2))
      83                 :         79 :       z = gerepileupto(av, z);
      84                 :            :   }
      85                 :    2036287 :   u = gen_RgXQ_eval_powers(P,V,0,d,E,ff,cmul);
      86                 :    2036289 :   z = ff->add(E,u, ff->mul(E,z,gel(V,d+2)));
      87         [ -  + ]:    2036290 :   if (DEBUGLEVEL>=8)
      88                 :            :   {
      89                 :          0 :     long cnt = 1 + (d - l) / (l-1);
      90                 :          0 :     err_printf("RgX_RgXQV_eval: %ld RgXQ_mul [%ld]\n", cnt, l-1);
      91                 :            :   }
      92                 :    4868700 :   return gerepileupto(av, ff->red(E,z));
      93                 :            : }
      94                 :            : 
      95                 :            : GEN
      96                 :     967029 : gen_bkeval(GEN Q, long d, GEN x, int use_sqr, void *E, const struct bb_algebra *ff,
      97                 :            :                                       GEN cmul(void *E, GEN P, long a, GEN x))
      98                 :            : {
      99                 :     967029 :   pari_sp av = avma;
     100                 :            :   GEN z, V;
     101                 :            :   long rtd;
     102         [ +  + ]:     967029 :   if (d < 0) return ff->zero(E);
     103                 :     966938 :   rtd = (long) sqrt((double)d);
     104                 :     966938 :   V = gen_powers(x,rtd,use_sqr,E,ff->sqr,ff->mul,ff->one);
     105                 :     966936 :   z = gen_bkeval_powers(Q, d, V, E, ff, cmul);
     106                 :     967028 :   return gerepileupto(av, z);
     107                 :            : }
     108                 :            : 
     109                 :            : static GEN
     110                 :     458909 : _gen_nored(void *E, GEN x) { (void)E; return x; }
     111                 :            : static GEN
     112                 :   32692708 : _gen_add(void *E, GEN x, GEN y) { (void)E; return gadd(x, y); }
     113                 :            : static GEN
     114                 :          0 : _gen_sub(void *E, GEN x, GEN y) { (void)E; return gsub(x, y); }
     115                 :            : static GEN
     116                 :     490940 : _gen_mul(void *E, GEN x, GEN y) { (void)E; return gmul(x, y); }
     117                 :            : static GEN
     118                 :     158608 : _gen_sqr(void *E, GEN x) { (void)E; return gsqr(x); }
     119                 :            : static GEN
     120                 :     467330 : _gen_one(void *E) { (void)E; return gen_1; }
     121                 :            : static GEN
     122                 :         84 : _gen_zero(void *E) { (void)E; return gen_0; }
     123                 :            : 
     124                 :            : static struct bb_algebra Rg_algebra = { _gen_nored, _gen_add, _gen_sub,
     125                 :            :               _gen_mul, _gen_sqr,_gen_one,_gen_zero };
     126                 :            : 
     127                 :            : static GEN
     128                 :      16135 : _gen_cmul(void *E, GEN P, long a, GEN x)
     129                 :      16135 : {(void)E; return gmul(gel(P,a+2), x);}
     130                 :            : 
     131                 :            : GEN
     132                 :       5257 : RgX_RgV_eval(GEN Q, GEN x)
     133                 :            : {
     134                 :       5257 :   return gen_bkeval_powers(Q, degpol(Q), x, NULL, &Rg_algebra, _gen_cmul);
     135                 :            : }
     136                 :            : 
     137                 :            : GEN
     138                 :          0 : RgX_Rg_eval_bk(GEN Q, GEN x)
     139                 :            : {
     140                 :          0 :   return gen_bkeval(Q, degpol(Q), x, 1, NULL, &Rg_algebra, _gen_cmul);
     141                 :            : }
     142                 :            : 
     143                 :            : GEN
     144                 :        105 : RgXV_RgV_eval(GEN Q, GEN x)
     145                 :            : {
     146                 :        105 :   long i, l = lg(Q), vQ = gvar(Q);
     147                 :        105 :   GEN v = cgetg(l, t_VEC);
     148         [ +  + ]:      12726 :   for (i = 1; i < l; i++)
     149                 :            :   {
     150                 :      12621 :     GEN Qi = gel(Q, i);
     151 [ +  + ][ +  - ]:      12621 :     gel(v, i) = typ(Qi)==t_POL && varn(Qi)==vQ? RgX_RgV_eval(Qi, x): gcopy(Qi);
     152                 :            :   }
     153                 :        105 :   return v;
     154                 :            : }
     155                 :            : 
     156                 :            : const struct bb_algebra *
     157                 :      54149 : get_Rg_algebra(void)
     158                 :            : {
     159                 :      54149 :   return &Rg_algebra;
     160                 :            : }
     161                 :            : 
     162                 :            : /*******************************************************************/
     163                 :            : /*                                                                 */
     164                 :            : /*                         RgX                                     */
     165                 :            : /*                                                                 */
     166                 :            : /*******************************************************************/
     167                 :            : 
     168                 :            : long
     169                 :    4119572 : RgX_equal(GEN x, GEN y)
     170                 :            : {
     171                 :    4119572 :   long i = lg(x);
     172                 :            : 
     173         [ +  + ]:    4119572 :   if (i != lg(y)) return 0;
     174         [ +  + ]:   21095231 :   for (i--; i > 1; i--)
     175         [ +  + ]:   17036293 :     if (!gequal(gel(x,i),gel(y,i))) return 0;
     176                 :    4119572 :   return 1;
     177                 :            : }
     178                 :            : 
     179                 :            : /* Returns 1 in the base ring over which x is defined */
     180                 :            : /* HACK: this also works for t_SER */
     181                 :            : GEN
     182                 :     331613 : RgX_get_1(GEN x)
     183                 :            : {
     184                 :            :   GEN p, T;
     185                 :     331613 :   long i, lx, tx = RgX_type(x, &p, &T, &lx);
     186         [ +  + ]:     331613 :   if (RgX_type_is_composite(tx))
     187                 :         21 :     RgX_type_decode(tx, &i /*junk*/, &tx);
     188   [ +  +  +  + ]:     331613 :   switch(tx)
     189                 :            :   {
     190                 :         28 :     case t_INTMOD: retmkintmod(gen_1, icopy(p));
     191                 :         14 :     case t_PADIC: return cvtop(gen_1, p, lx);
     192                 :         14 :     case t_FFELT: return FF_1(T);
     193                 :     331613 :     default: return gen_1;
     194                 :            :   }
     195                 :            : }
     196                 :            : /* Returns 0 in the base ring over which x is defined */
     197                 :            : /* HACK: this also works for t_SER */
     198                 :            : GEN
     199                 :       7147 : RgX_get_0(GEN x)
     200                 :            : {
     201                 :            :   GEN p, T;
     202                 :       7147 :   long i, lx, tx = RgX_type(x, &p, &T, &lx);
     203         [ -  + ]:       7147 :   if (RgX_type_is_composite(tx))
     204                 :          0 :     RgX_type_decode(tx, &i /*junk*/, &tx);
     205   [ +  -  -  + ]:       7147 :   switch(tx)
     206                 :            :   {
     207                 :         14 :     case t_INTMOD: retmkintmod(gen_0, icopy(p));
     208                 :          0 :     case t_PADIC: return cvtop(gen_0, p, lx);
     209                 :          0 :     case t_FFELT: return FF_zero(T);
     210                 :       7147 :     default: return gen_0;
     211                 :            :   }
     212                 :            : }
     213                 :            : 
     214                 :            : GEN
     215                 :       1652 : QX_ZXQV_eval(GEN P, GEN V, GEN dV)
     216                 :            : {
     217                 :       1652 :   long i, n = degpol(P);
     218                 :            :   GEN z, dz, dP;
     219         [ -  + ]:       1652 :   if (n < 0) return gen_0;
     220                 :       1652 :   P = Q_remove_denom(P, &dP);
     221         [ +  + ]:       1652 :   z = gel(P,2); if (n == 0) return icopy(z);
     222         [ +  + ]:        917 :   if (dV) z = mulii(dV, z); /* V[1] = dV */
     223                 :        917 :   z = ZX_Z_add_shallow(ZX_Z_mul(gel(V,2),gel(P,3)), z);
     224         [ +  + ]:       2394 :   for (i=2; i<=n; i++) z = ZX_add(ZX_Z_mul(gel(V,i+1),gel(P,2+i)), z);
     225                 :        917 :   dz = mul_denom(dP, dV);
     226         [ +  + ]:       1652 :   return dz? RgX_Rg_div(z, dz): z;
     227                 :            : }
     228                 :            : 
     229                 :            : /* Return P(h * x), not memory clean */
     230                 :            : GEN
     231                 :       3626 : RgX_unscale(GEN P, GEN h)
     232                 :            : {
     233                 :       3626 :   long i, l = lg(P);
     234                 :       3626 :   GEN hi = gen_1, Q = cgetg(l, t_POL);
     235                 :       3626 :   Q[1] = P[1];
     236         [ -  + ]:       3626 :   if (l == 2) return Q;
     237                 :       3626 :   gel(Q,2) = gcopy(gel(P,2));
     238         [ +  + ]:      13524 :   for (i=3; i<l; i++)
     239                 :            :   {
     240                 :       9898 :     hi = gmul(hi,h);
     241                 :       9898 :     gel(Q,i) = gmul(gel(P,i), hi);
     242                 :            :   }
     243                 :       3626 :   return Q;
     244                 :            : }
     245                 :            : /* P a ZX, h a t_INT. Return P(h * x), not memory clean; optimize for h = -1 */
     246                 :            : GEN
     247                 :       6314 : ZX_unscale(GEN P, GEN h)
     248                 :            : {
     249                 :       6314 :   long i, l = lg(P);
     250                 :       6314 :   GEN Q = cgetg(l, t_POL);
     251                 :       6314 :   Q[1] = P[1];
     252         [ -  + ]:       6314 :   if (l == 2) return Q;
     253                 :       6314 :   gel(Q,2) = gel(P,2);
     254         [ -  + ]:       6314 :   if (l == 3) return Q;
     255         [ +  + ]:       6314 :   if (equalim1(h))
     256         [ +  + ]:     297008 :     for (i=3; i<l; i++)
     257                 :            :     {
     258                 :     290827 :       gel(Q,i) = negi(gel(P,i));
     259         [ +  + ]:     290827 :       if (++i == l) break;
     260                 :     288456 :       gel(Q,i) = gel(P,i);
     261                 :            :     }
     262                 :            :   else
     263                 :            :   {
     264                 :        133 :     GEN hi = h;
     265                 :        133 :     gel(Q,3) = mulii(gel(P,3), hi);
     266         [ +  + ]:        399 :     for (i=4; i<l; i++)
     267                 :            :     {
     268                 :        266 :       hi = mulii(hi,h);
     269                 :        266 :       gel(Q,i) = mulii(gel(P,i), hi);
     270                 :            :     }
     271                 :            :   }
     272                 :       6314 :   return Q;
     273                 :            : }
     274                 :            : /* P a ZX. Return P(x << n), not memory clean */
     275                 :            : GEN
     276                 :       8001 : ZX_unscale2n(GEN P, long n)
     277                 :            : {
     278                 :       8001 :   long i, ni = n, l = lg(P);
     279                 :       8001 :   GEN Q = cgetg(l, t_POL);
     280                 :       8001 :   Q[1] = P[1];
     281         [ -  + ]:       8001 :   if (l == 2) return Q;
     282                 :       8001 :   gel(Q,2) = gel(P,2);
     283         [ -  + ]:       8001 :   if (l == 3) return Q;
     284                 :       8001 :   gel(Q,3) = shifti(gel(P,3), ni);
     285         [ +  + ]:      40337 :   for (i=4; i<l; i++)
     286                 :            :   {
     287                 :      32336 :     ni += n;
     288                 :      32336 :     gel(Q,i) = shifti(gel(P,i), ni);
     289                 :            :   }
     290                 :       8001 :   return Q;
     291                 :            : }
     292                 :            : /* P(h*X) / h, assuming h | P(0), i.e. the result is a ZX */
     293                 :            : GEN
     294                 :        147 : ZX_unscale_div(GEN P, GEN h)
     295                 :            : {
     296                 :        147 :   long i, l = lg(P);
     297                 :        147 :   GEN hi, Q = cgetg(l, t_POL);
     298                 :        147 :   Q[1] = P[1];
     299         [ -  + ]:        147 :   if (l == 2) return Q;
     300                 :        147 :   gel(Q,2) = diviiexact(gel(P,2), h);
     301         [ -  + ]:        147 :   if (l == 3) return Q;
     302                 :        147 :   gel(Q,3) = gel(P,3);
     303         [ -  + ]:        147 :   if (l == 4) return Q;
     304                 :        147 :   hi = h;
     305                 :        147 :   gel(Q,4) = mulii(gel(P,4), hi);
     306         [ +  + ]:        483 :   for (i=5; i<l; i++)
     307                 :            :   {
     308                 :        336 :     hi = mulii(hi,h);
     309                 :        336 :     gel(Q,i) = mulii(gel(P,i), hi);
     310                 :            :   }
     311                 :        147 :   return Q;
     312                 :            : }
     313                 :            : 
     314                 :            : GEN
     315                 :        161 : RgXV_unscale(GEN v, GEN h)
     316                 :            : {
     317                 :            :   long i, l;
     318                 :            :   GEN w;
     319 [ +  - ][ +  + ]:        161 :   if (!h || isint1(h)) return v;
     320                 :        105 :   w = cgetg_copy(v, &l);
     321         [ +  + ]:        350 :   for (i=1; i<l; i++) gel(w,i) = RgX_unscale(gel(v,i), h);
     322                 :        161 :   return w;
     323                 :            : }
     324                 :            : 
     325                 :            : /* Return h^degpol(P) P(x / h), not memory clean */
     326                 :            : GEN
     327                 :       1414 : RgX_rescale(GEN P, GEN h)
     328                 :            : {
     329                 :       1414 :   long i, l = lg(P);
     330                 :       1414 :   GEN Q = cgetg(l,t_POL), hi = h;
     331                 :       1414 :   Q[l-1] = P[l-1];
     332         [ +  - ]:       8687 :   for (i=l-2; i>=2; i--)
     333                 :            :   {
     334                 :       8687 :     gel(Q,i) = gmul(gel(P,i), hi);
     335         [ +  + ]:       8687 :     if (i == 2) break;
     336                 :       7273 :     hi = gmul(hi,h);
     337                 :            :   }
     338                 :       1414 :   Q[1] = P[1]; return Q;
     339                 :            : }
     340                 :            : 
     341                 :            : /* A(X^d) --> A(X) */
     342                 :            : GEN
     343                 :      70195 : RgX_deflate(GEN x0, long d)
     344                 :            : {
     345                 :            :   GEN z, y, x;
     346                 :      70195 :   long i,id, dy, dx = degpol(x0);
     347 [ +  + ][ -  + ]:      70195 :   if (d == 1 || dx <= 0) return leafcopy(x0);
     348                 :      48375 :   dy = dx/d;
     349                 :      48375 :   y = cgetg(dy+3, t_POL); y[1] = x0[1];
     350                 :      48375 :   z = y + 2;
     351                 :      48375 :   x = x0+ 2;
     352         [ +  + ]:     237934 :   for (i=id=0; i<=dy; i++,id+=d) gel(z,i) = gel(x,id);
     353                 :      70195 :   return y;
     354                 :            : }
     355                 :            : 
     356                 :            : /* return x0(X^d) */
     357                 :            : GEN
     358                 :     101313 : RgX_inflate(GEN x0, long d)
     359                 :            : {
     360                 :     101313 :   long i, id, dy, dx = degpol(x0);
     361                 :     101314 :   GEN x = x0 + 2, z, y;
     362         [ +  + ]:     101314 :   if (dx <= 0) return leafcopy(x0);
     363                 :     100943 :   dy = dx*d;
     364                 :     100943 :   y = cgetg(dy+3, t_POL); y[1] = x0[1];
     365                 :     100943 :   z = y + 2;
     366         [ +  + ]:    2804666 :   for (i=0; i<=dy; i++) gel(z,i) = gen_0;
     367         [ +  + ]:     733006 :   for (i=id=0; i<=dx; i++,id+=d) gel(z,id) = gel(x,i);
     368                 :     101314 :   return y;
     369                 :            : }
     370                 :            : 
     371                 :            : /* return P(X + c) using destructive Horner, optimize for c = 1,-1 */
     372                 :            : GEN
     373                 :     980256 : RgX_translate(GEN P, GEN c)
     374                 :            : {
     375                 :     980256 :   pari_sp av = avma;
     376                 :            :   GEN Q, *R;
     377                 :            :   long i, k, n;
     378                 :            : 
     379 [ +  - ][ +  + ]:     980256 :   if (!signe(P) || gequal0(c)) return RgX_copy(P);
     380                 :     977397 :   Q = leafcopy(P);
     381                 :     977397 :   R = (GEN*)(Q+2); n = degpol(P);
     382         [ +  + ]:     977397 :   if (gequal1(c))
     383                 :            :   {
     384         [ +  + ]:       2744 :     for (i=1; i<=n; i++)
     385                 :            :     {
     386         [ +  + ]:      14294 :       for (k=n-i; k<n; k++) R[k] = gadd(R[k], R[k+1]);
     387         [ -  + ]:       2380 :       if (gc_needed(av,2))
     388                 :            :       {
     389         [ #  # ]:          0 :         if(DEBUGMEM>1) pari_warn(warnmem,"TR_POL(1), i = %ld/%ld", i,n);
     390                 :          0 :         Q = gerepilecopy(av, Q); R = (GEN*)Q+2;
     391                 :            :       }
     392                 :            :     }
     393                 :            :   }
     394         [ +  + ]:     977033 :   else if (gequalm1(c))
     395                 :            :   {
     396         [ +  + ]:     130984 :     for (i=1; i<=n; i++)
     397                 :            :     {
     398         [ +  + ]:     917665 :       for (k=n-i; k<n; k++) R[k] = gsub(R[k], R[k+1]);
     399         [ -  + ]:     112336 :       if (gc_needed(av,2))
     400                 :            :       {
     401         [ #  # ]:          0 :         if(DEBUGMEM>1) pari_warn(warnmem,"TR_POL(-1), i = %ld/%ld", i,n);
     402                 :          0 :         Q = gerepilecopy(av, Q); R = (GEN*)Q+2;
     403                 :            :       }
     404                 :            :     }
     405                 :            :   }
     406                 :            :   else
     407                 :            :   {
     408         [ +  + ]:    3294571 :     for (i=1; i<=n; i++)
     409                 :            :     {
     410         [ +  + ]:    8440360 :       for (k=n-i; k<n; k++) R[k] = gadd(R[k], gmul(c, R[k+1]));
     411         [ -  + ]:    2336186 :       if (gc_needed(av,2))
     412                 :            :       {
     413         [ #  # ]:          0 :         if(DEBUGMEM>1) pari_warn(warnmem,"TR_POL, i = %ld/%ld", i,n);
     414                 :          0 :         Q = gerepilecopy(av, Q); R = (GEN*)Q+2;
     415                 :            :       }
     416                 :            :     }
     417                 :            :   }
     418                 :     980256 :   return gerepilecopy(av, Q);
     419                 :            : }
     420                 :            : 
     421                 :            : /* return P(X + c) using destructive Horner, optimize for c = 1,-1 */
     422                 :            : GEN
     423                 :      33387 : ZX_translate(GEN P, GEN c)
     424                 :            : {
     425                 :      33387 :   pari_sp av = avma;
     426                 :            :   GEN Q, *R;
     427                 :            :   long i, k, n;
     428                 :            : 
     429 [ +  - ][ +  + ]:      33387 :   if (!signe(P) || !signe(c)) return ZX_copy(P);
     430                 :      33352 :   Q = leafcopy(P);
     431                 :      33352 :   R = (GEN*)(Q+2); n = degpol(P);
     432         [ +  + ]:      33352 :   if (equali1(c))
     433                 :            :   {
     434         [ +  + ]:     375236 :     for (i=1; i<=n; i++)
     435                 :            :     {
     436         [ +  + ]:    4226212 :       for (k=n-i; k<n; k++) R[k] = addii(R[k], R[k+1]);
     437         [ -  + ]:     346492 :       if (gc_needed(av,2))
     438                 :            :       {
     439         [ #  # ]:          0 :         if(DEBUGMEM>1) pari_warn(warnmem,"ZX_translate(1), i = %ld/%ld", i,n);
     440                 :          0 :         Q = gerepilecopy(av, Q); R = (GEN*)Q+2;
     441                 :            :       }
     442                 :            :     }
     443                 :            :   }
     444         [ +  + ]:       4608 :   else if (equalim1(c))
     445                 :            :   {
     446         [ +  + ]:         28 :     for (i=1; i<=n; i++)
     447                 :            :     {
     448         [ +  + ]:         63 :       for (k=n-i; k<n; k++) R[k] = subii(R[k], R[k+1]);
     449         [ -  + ]:         21 :       if (gc_needed(av,2))
     450                 :            :       {
     451         [ #  # ]:          0 :         if(DEBUGMEM>1) pari_warn(warnmem,"ZX_translate(-1), i = %ld/%ld", i,n);
     452                 :          0 :         Q = gerepilecopy(av, Q); R = (GEN*)Q+2;
     453                 :            :       }
     454                 :            :     }
     455                 :            :   }
     456                 :            :   else
     457                 :            :   {
     458         [ +  + ]:      58549 :     for (i=1; i<=n; i++)
     459                 :            :     {
     460         [ +  + ]:     654182 :       for (k=n-i; k<n; k++) R[k] = addii(R[k], mulii(c, R[k+1]));
     461         [ -  + ]:      53948 :       if (gc_needed(av,2))
     462                 :            :       {
     463         [ #  # ]:          0 :         if(DEBUGMEM>1) pari_warn(warnmem,"ZX_translate, i = %ld/%ld", i,n);
     464                 :          0 :         Q = gerepilecopy(av, Q); R = (GEN*)Q+2;
     465                 :            :       }
     466                 :            :     }
     467                 :            :   }
     468                 :      33387 :   return gerepilecopy(av, Q);
     469                 :            : }
     470                 :            : /* return lift( P(X + c) ) using Horner, c in R[y]/(T) */
     471                 :            : GEN
     472                 :       6055 : RgXQX_translate(GEN P, GEN c, GEN T)
     473                 :            : {
     474                 :       6055 :   pari_sp av = avma;
     475                 :            :   GEN Q, *R;
     476                 :            :   long i, k, n;
     477                 :            : 
     478 [ +  - ][ +  + ]:       6055 :   if (!signe(P) || gequal0(c)) return RgX_copy(P);
     479                 :       6034 :   Q = leafcopy(P);
     480                 :       6034 :   R = (GEN*)(Q+2); n = degpol(P);
     481         [ +  + ]:      34720 :   for (i=1; i<=n; i++)
     482                 :            :   {
     483         [ +  + ]:     141547 :     for (k=n-i; k<n; k++)
     484                 :            :     {
     485                 :     112861 :       pari_sp av2 = avma;
     486                 :     112861 :       R[k] = gerepileupto(av2, RgX_rem(gadd(R[k], gmul(c, R[k+1])), T));
     487                 :            :     }
     488         [ -  + ]:      28686 :     if (gc_needed(av,2))
     489                 :            :     {
     490         [ #  # ]:          0 :       if(DEBUGMEM>1) pari_warn(warnmem,"RgXQX_translate, i = %ld/%ld", i,n);
     491                 :          0 :       Q = gerepilecopy(av, Q); R = (GEN*)Q+2;
     492                 :            :     }
     493                 :            :   }
     494                 :       6055 :   return gerepilecopy(av, Q);
     495                 :            : }
     496                 :            : 
     497                 :            : /********************************************************************/
     498                 :            : /**                                                                **/
     499                 :            : /**                          CONVERSIONS                           **/
     500                 :            : /**                       (not memory clean)                       **/
     501                 :            : /**                                                                **/
     502                 :            : /********************************************************************/
     503                 :            : /* to INT / FRAC / (POLMOD mod T), not memory clean because T not copied,
     504                 :            :  * but everything else is */
     505                 :            : static GEN
     506                 :      13776 : QXQ_to_mod_copy(GEN x, GEN T)
     507                 :            : {
     508                 :            :   long d;
     509   [ +  +  +  - ]:      13776 :   switch(typ(x))
     510                 :            :   {
     511                 :       5096 :     case t_INT:  return icopy(x);
     512                 :        371 :     case t_FRAC: return gcopy(x);
     513                 :            :     case t_POL:
     514                 :       8309 :       d = degpol(x);
     515         [ +  + ]:       8309 :       if (d < 0) return gen_0;
     516         [ +  + ]:       8057 :       if (d == 0) return gcopy(gel(x,2));
     517                 :       7805 :       return mkpolmod(RgX_copy(x), T);
     518                 :          0 :     default: pari_err_TYPE("QXQ_to_mod",x);
     519                 :      13776 :              return NULL;/* not reached */
     520                 :            :   }
     521                 :            : }
     522                 :            : /* pure shallow version */
     523                 :            : static GEN
     524                 :     407592 : QXQ_to_mod(GEN x, GEN T)
     525                 :            : {
     526                 :            :   long d;
     527      [ +  +  - ]:     407592 :   switch(typ(x))
     528                 :            :   {
     529                 :            :     case t_INT:
     530                 :     354872 :     case t_FRAC: return x;
     531                 :            :     case t_POL:
     532                 :      52720 :       d = degpol(x);
     533         [ +  + ]:      52720 :       if (d < 0) return gen_0;
     534         [ +  + ]:      48118 :       if (d == 0) return gel(x,2);
     535                 :      44240 :       return mkpolmod(x, T);
     536                 :          0 :     default: pari_err_TYPE("QXQ_to_mod",x);
     537                 :     407592 :              return NULL;/* not reached */
     538                 :            :   }
     539                 :            : }
     540                 :            : /* T a ZX, z lifted from (Q[Y]/(T(Y)))[X], apply QXQ_to_mod_copy to all coeffs.
     541                 :            :  * Not memory clean because T not copied, but everything else is */
     542                 :            : static GEN
     543                 :       1883 : QXQX_to_mod(GEN z, GEN T)
     544                 :            : {
     545                 :       1883 :   long i,l = lg(z);
     546                 :       1883 :   GEN x = cgetg(l,t_POL);
     547         [ +  + ]:      13566 :   for (i=2; i<l; i++) gel(x,i) = QXQ_to_mod_copy(gel(z,i), T);
     548                 :       1883 :   x[1] = z[1]; return normalizepol_lg(x,l);
     549                 :            : }
     550                 :            : /* pure shallow version */
     551                 :            : GEN
     552                 :      83048 : QXQX_to_mod_shallow(GEN z, GEN T)
     553                 :            : {
     554                 :      83048 :   long i,l = lg(z);
     555                 :      83048 :   GEN x = cgetg(l,t_POL);
     556         [ +  + ]:     490640 :   for (i=2; i<l; i++) gel(x,i) = QXQ_to_mod(gel(z,i), T);
     557                 :      83048 :   x[1] = z[1]; return normalizepol_lg(x,l);
     558                 :            : }
     559                 :            : /* Apply QXQX_to_mod to all entries. Memory-clean ! */
     560                 :            : GEN
     561                 :        525 : QXQXV_to_mod(GEN V, GEN T)
     562                 :            : {
     563                 :        525 :   long i, l = lg(V);
     564                 :        525 :   GEN z = cgetg(l, t_VEC); T = ZX_copy(T);
     565         [ +  + ]:       2408 :   for (i=1;i<l; i++) gel(z,i) = QXQX_to_mod(gel(V,i), T);
     566                 :        525 :   return z;
     567                 :            : }
     568                 :            : /* Apply QXQ_to_mod_copy to all entries. Memory-clean ! */
     569                 :            : GEN
     570                 :        812 : QXQV_to_mod(GEN V, GEN T)
     571                 :            : {
     572                 :        812 :   long i, l = lg(V);
     573                 :        812 :   GEN z = cgetg(l, t_VEC); T = ZX_copy(T);
     574         [ +  + ]:       2905 :   for (i=1;i<l; i++) gel(z,i) = QXQ_to_mod_copy(gel(V,i), T);
     575                 :        812 :   return z;
     576                 :            : }
     577                 :            : 
     578                 :            : GEN
     579                 :     312480 : RgX_renormalize_lg(GEN x, long lx)
     580                 :            : {
     581                 :            :   long i;
     582         [ +  + ]:     725382 :   for (i = lx-1; i>1; i--)
     583         [ +  + ]:     725249 :     if (! gequal0(gel(x,i))) break; /* _not_ isexactzero */
     584                 :     312480 :   stackdummy((pari_sp)(x + lg(x)), (pari_sp)(x + i+1));
     585         [ +  + ]:     312480 :   setlg(x, i+1); setsigne(x, i != 1); return x;
     586                 :            : }
     587                 :            : 
     588                 :            : GEN
     589                 :     348009 : RgV_to_RgX(GEN x, long v)
     590                 :            : {
     591                 :     348009 :   long i, k = lg(x);
     592                 :            :   GEN p;
     593                 :            : 
     594 [ +  + ][ +  + ]:    1322711 :   while (--k && gequal0(gel(x,k)));
     595         [ +  + ]:     348009 :   if (!k) return pol_0(v);
     596                 :     347666 :   i = k+2; p = cgetg(i,t_POL);
     597                 :     347666 :   p[1] = evalsigne(1) | evalvarn(v);
     598         [ +  + ]:    3071071 :   x--; for (k=2; k<i; k++) gel(p,k) = gel(x,k);
     599                 :     348009 :   return p;
     600                 :            : }
     601                 :            : GEN
     602                 :     149838 : RgV_to_RgX_reverse(GEN x, long v)
     603                 :            : {
     604                 :     149838 :   long j, k, l = lg(x);
     605                 :            :   GEN p;
     606                 :            : 
     607         [ +  - ]:     149838 :   for (k = 1; k < l; k++)
     608         [ +  - ]:     149838 :     if (!gequal0(gel(x,k))) break;
     609         [ -  + ]:     149838 :   if (k == l) return pol_0(v);
     610                 :     149838 :   k -= 1;
     611                 :     149838 :   l -= k;
     612                 :     149838 :   x += k;
     613                 :     149838 :   p = cgetg(l+1,t_POL);
     614                 :     149838 :   p[1] = evalsigne(1) | evalvarn(v);
     615         [ +  + ]:     869235 :   for (j=2, k=l; j<=l; j++) gel(p,j) = gel(x,--k);
     616                 :     149838 :   return p;
     617                 :            : }
     618                 :            : 
     619                 :            : /* return the (N-dimensional) vector of coeffs of p */
     620                 :            : GEN
     621                 :    3769362 : RgX_to_RgC(GEN x, long N)
     622                 :            : {
     623                 :            :   long i, l;
     624                 :            :   GEN z;
     625                 :    3769362 :   l = lg(x)-1; x++;
     626         [ +  + ]:    3769362 :   if (l > N+1) l = N+1; /* truncate higher degree terms */
     627                 :    3769362 :   z = cgetg(N+1,t_COL);
     628         [ +  + ]:   28462903 :   for (i=1; i<l ; i++) gel(z,i) = gel(x,i);
     629         [ +  + ]:   10340099 :   for (   ; i<=N; i++) gel(z,i) = gen_0;
     630                 :    3769362 :   return z;
     631                 :            : }
     632                 :            : GEN
     633                 :      25599 : Rg_to_RgC(GEN x, long N)
     634                 :            : {
     635         [ +  + ]:      25599 :   return (typ(x) == t_POL)? RgX_to_RgC(x,N): scalarcol_shallow(x, N);
     636                 :            : }
     637                 :            : 
     638                 :            : /* vector of polynomials (in v) whose coeffs are given by the columns of x */
     639                 :            : GEN
     640                 :      35244 : RgM_to_RgXV(GEN x, long v)
     641                 :            : {
     642                 :      35244 :   long j, lx = lg(x);
     643                 :      35244 :   GEN y = cgetg(lx, t_VEC);
     644         [ +  + ]:     212057 :   for (j=1; j<lx; j++) gel(y,j) = RgV_to_RgX(gel(x,j), v);
     645                 :      35244 :   return y;
     646                 :            : }
     647                 :            : 
     648                 :            : /* matrix whose entries are given by the coeffs of the polynomials in
     649                 :            :  * vector v (considered as degree n-1 polynomials) */
     650                 :            : GEN
     651                 :       5957 : RgV_to_RgM(GEN v, long n)
     652                 :            : {
     653                 :       5957 :   long j, N = lg(v);
     654                 :       5957 :   GEN y = cgetg(N, t_MAT);
     655         [ +  + ]:      30478 :   for (j=1; j<N; j++) gel(y,j) = Rg_to_RgC(gel(v,j), n);
     656                 :       5957 :   return y;
     657                 :            : }
     658                 :            : GEN
     659                 :       4881 : RgXV_to_RgM(GEN v, long n)
     660                 :            : {
     661                 :       4881 :   long j, N = lg(v);
     662                 :       4881 :   GEN y = cgetg(N, t_MAT);
     663         [ +  + ]:      26662 :   for (j=1; j<N; j++) gel(y,j) = RgX_to_RgC(gel(v,j), n);
     664                 :       4881 :   return y;
     665                 :            : }
     666                 :            : 
     667                 :            : /* polynomial (in v) of polynomials (in w) whose coeffs are given by the columns of x */
     668                 :            : GEN
     669                 :      15050 : RgM_to_RgXX(GEN x, long v,long w)
     670                 :            : {
     671                 :      15050 :   long j, lx = lg(x);
     672                 :      15050 :   GEN y = cgetg(lx+1, t_POL);
     673                 :      15050 :   y[1] = evalsigne(1) | evalvarn(v);
     674                 :      15050 :   y++;
     675         [ +  + ]:      81067 :   for (j=1; j<lx; j++) gel(y,j) = RgV_to_RgX(gel(x,j), w);
     676                 :      15050 :   return normalizepol_lg(--y, lx+1);
     677                 :            : }
     678                 :            : 
     679                 :            : /* matrix whose entries are given by the coeffs of the polynomial v in
     680                 :            :  * two variables (considered as degree n-1 polynomials) */
     681                 :            : GEN
     682                 :         21 : RgXX_to_RgM(GEN v, long n)
     683                 :            : {
     684                 :         21 :   long j, N = lg(v)-1;
     685                 :         21 :   GEN y = cgetg(N, t_MAT);
     686         [ +  + ]:         63 :   for (j=1; j<N; j++) gel(y,j) = Rg_to_RgC(gel(v,j+1), n);
     687                 :         21 :   return y;
     688                 :            : }
     689                 :            : 
     690                 :            : /* P(X,Y) --> P(Y,X), n is an upper bound for deg_Y(P) */
     691                 :            : GEN
     692                 :      21698 : RgXY_swapspec(GEN x, long n, long w, long nx)
     693                 :            : {
     694                 :      21698 :   long j, ly = n+3;
     695                 :      21698 :   GEN y = cgetg(ly, t_POL);
     696                 :      21698 :   y[1] = evalsigne(1);
     697         [ +  + ]:     258619 :   for (j=2; j<ly; j++)
     698                 :            :   {
     699                 :            :     long k;
     700                 :     236921 :     GEN a = cgetg(nx+2,t_POL);
     701                 :     236921 :     a[1] = evalsigne(1) | evalvarn(w);
     702         [ +  + ]:    1131023 :     for (k=0; k<nx; k++)
     703                 :            :     {
     704                 :     894102 :       GEN xk = gel(x,k);
     705         [ +  + ]:     894102 :       if (typ(xk)==t_POL)
     706         [ +  + ]:     808828 :         gel(a,k+2) = j<lg(xk)? gel(xk,j): gen_0;
     707                 :            :       else
     708         [ +  + ]:      85274 :         gel(a,k+2) = j==2 ? xk: gen_0;
     709                 :            :     }
     710                 :     236921 :     gel(y,j) = normalizepol_lg(a, nx+2);
     711                 :            :   }
     712                 :      21698 :   return normalizepol_lg(y,ly);
     713                 :            : }
     714                 :            : 
     715                 :            : /* P(X,Y) --> P(Y,X), n is an upper bound for deg_Y(P) */
     716                 :            : GEN
     717                 :        224 : RgXY_swap(GEN x, long n, long w)
     718                 :            : {
     719                 :        224 :   GEN z = RgXY_swapspec(x+2, n, w, lgpol(x));
     720                 :        224 :   setvarn(z, varn(x)); return z;
     721                 :            : }
     722                 :            : 
     723                 :            : long
     724                 :          1 : RgXY_degreex(GEN b)
     725                 :            : {
     726                 :          1 :   long deg = -1, i;
     727         [ -  + ]:          1 :   if (!signe(b)) return -1;
     728         [ +  + ]:          3 :   for (i = 2; i < lg(b); ++i)
     729                 :            :   {
     730                 :          2 :     GEN bi = gel(b, i);
     731         [ +  + ]:          2 :     if (typ(bi) == t_POL)
     732                 :          1 :       deg = maxss(deg, degpol(bi));
     733                 :            :   }
     734                 :          1 :   return deg;
     735                 :            : }
     736                 :            : 
     737                 :            : /* return (x % X^n). Shallow */
     738                 :            : GEN
     739                 :       4476 : RgXn_red_shallow(GEN a, long n)
     740                 :            : {
     741                 :       4476 :   long i, L, l = lg(a);
     742                 :            :   GEN  b;
     743 [ +  - ][ -  + ]:       4476 :   if (l == 2 || !n) return pol_0(varn(a));
     744         [ +  + ]:       4476 :   L = n+2; if (L > l) L = l;
     745                 :       4476 :   b = cgetg(L, t_POL); b[1] = a[1];
     746         [ +  + ]:      21695 :   for (i=2; i<L; i++) gel(b,i) = gel(a,i);
     747                 :       4476 :   return normalizepol_lg(b,L);
     748                 :            : }
     749                 :            : 
     750                 :            : GEN
     751                 :        336 : RgXnV_red_shallow(GEN P, long n)
     752                 :            : {
     753                 :        336 :   long i, l = lg(P);
     754                 :        336 :   GEN Q = cgetg(l, t_VEC);
     755         [ +  + ]:       1603 :   for (i=1; i<l; i++) gel(Q,i) = RgXn_red_shallow(gel(P,i), n);
     756                 :        336 :   return Q;
     757                 :            : }
     758                 :            : 
     759                 :            : /* return (x * X^n). Shallow */
     760                 :            : GEN
     761                 :   54455589 : RgX_shift_shallow(GEN a, long n)
     762                 :            : {
     763                 :   54455589 :   long i, l = lg(a);
     764                 :            :   GEN  b;
     765 [ +  + ][ +  + ]:   54455589 :   if (l == 2 || !n) return a;
     766                 :   40505151 :   l += n;
     767         [ +  + ]:   40505151 :   if (n < 0)
     768                 :            :   {
     769         [ +  + ]:   36533792 :     if (l <= 2) return pol_0(varn(a));
     770                 :   36533386 :     b = cgetg(l, t_POL); b[1] = a[1];
     771                 :   36533387 :     a -= n;
     772         [ +  + ]:   99737720 :     for (i=2; i<l; i++) gel(b,i) = gel(a,i);
     773                 :            :   } else {
     774                 :    3971359 :     b = cgetg(l, t_POL); b[1] = a[1];
     775                 :    3971359 :     a -= n; n += 2;
     776         [ +  + ]:   10012039 :     for (i=2; i<n; i++) gel(b,i) = gen_0;
     777         [ +  + ]:  258247181 :     for (   ; i<l; i++) gel(b,i) = gel(a,i);
     778                 :            :   }
     779                 :   54455590 :   return b;
     780                 :            : }
     781                 :            : /* return (x * X^n). */
     782                 :            : GEN
     783                 :    3346181 : RgX_shift(GEN a, long n)
     784                 :            : {
     785                 :    3346181 :   long i, l = lg(a);
     786                 :            :   GEN  b;
     787 [ +  + ][ +  + ]:    3346181 :   if (l == 2 || !n) return RgX_copy(a);
     788                 :    3345957 :   l += n;
     789         [ +  + ]:    3345957 :   if (n < 0)
     790                 :            :   {
     791         [ +  + ]:        595 :     if (l <= 2) return pol_0(varn(a));
     792                 :        553 :     b = cgetg(l, t_POL); b[1] = a[1];
     793                 :        553 :     a -= n;
     794         [ +  + ]:       2177 :     for (i=2; i<l; i++) gel(b,i) = gcopy(gel(a,i));
     795                 :            :   } else {
     796                 :    3345362 :     b = cgetg(l, t_POL); b[1] = a[1];
     797                 :    3345362 :     a -= n; n += 2;
     798         [ +  + ]:    8534839 :     for (i=2; i<n; i++) gel(b,i) = gen_0;
     799         [ +  + ]:   10878576 :     for (   ; i<l; i++) gel(b,i) = gcopy(gel(a,i));
     800                 :            :   }
     801                 :    3346181 :   return b;
     802                 :            : }
     803                 :            : 
     804                 :            : GEN
     805                 :     309295 : RgX_rotate_shallow(GEN P, long k, long p)
     806                 :            : {
     807                 :     309295 :   long i, l = lgpol(P);
     808                 :            :   GEN r;
     809         [ +  + ]:     309295 :   if (signe(P)==0)
     810                 :        329 :     return pol_0(varn(P));
     811                 :     308966 :   r = cgetg(p+2,t_POL); r[1] = P[1];
     812         [ +  + ]:    2055102 :   for(i=0; i<p; i++)
     813                 :            :   {
     814                 :    1746136 :     long s = 2+(i+k)%p;
     815         [ +  + ]:    1746136 :     gel(r,s) = i<l? gel(P,2+i): gen_0;
     816                 :            :   }
     817                 :     309295 :   return RgX_renormalize(r);
     818                 :            : }
     819                 :            : 
     820                 :            : GEN
     821                 :    2580142 : RgX_mulXn(GEN x, long d)
     822                 :            : {
     823                 :            :   pari_sp av;
     824                 :            :   GEN z;
     825                 :            :   long v;
     826         [ +  + ]:    2580142 :   if (d >= 0) return RgX_shift(x, d);
     827                 :    1133659 :   d = -d;
     828                 :    1133659 :   v = RgX_val(x);
     829         [ +  + ]:    1133659 :   if (v >= d) return RgX_shift(x, -d);
     830                 :    1133652 :   av = avma;
     831                 :    1133652 :   z = gred_rfrac_simple( RgX_shift_shallow(x, -v),
     832                 :    1133652 :                          monomial(gen_1, d - v, varn(x)));
     833                 :    2580142 :   return gerepileupto(av, z);
     834                 :            : }
     835                 :            : 
     836                 :            : long
     837                 :    1983190 : RgX_val(GEN x)
     838                 :            : {
     839                 :    1983190 :   long i, lx = lg(x);
     840         [ +  + ]:    1983190 :   if (lx == 2) return LONG_MAX;
     841         [ +  - ]:    1998030 :   for (i = 2; i < lx; i++)
     842         [ +  + ]:    1998030 :     if (!isexactzero(gel(x,i))) break;
     843         [ -  + ]:    1983183 :   if (i == lx) i--; /* possible with non-rational zeros */
     844                 :    1983190 :   return i - 2;
     845                 :            : }
     846                 :            : long
     847                 :   40356484 : RgX_valrem(GEN x, GEN *Z)
     848                 :            : {
     849                 :   40356484 :   long v, i, lx = lg(x);
     850         [ -  + ]:   40356484 :   if (lx == 2) { *Z = pol_0(varn(x)); return LONG_MAX; }
     851         [ +  - ]:   77418452 :   for (i = 2; i < lx; i++)
     852         [ +  + ]:   77418452 :     if (!isexactzero(gel(x,i))) break;
     853         [ -  + ]:   40356484 :   if (i == lx) i--; /* possible with non-rational zeros */
     854                 :   40356484 :   v = i - 2;
     855                 :   40356484 :   *Z = RgX_shift_shallow(x, -v);
     856                 :   40356484 :   return v;
     857                 :            : }
     858                 :            : long
     859                 :       2885 : RgX_valrem_inexact(GEN x, GEN *Z)
     860                 :            : {
     861                 :            :   long v;
     862 [ -  + ][ #  # ]:       2885 :   if (!signe(x)) { if (Z) *Z = pol_0(varn(x)); return LONG_MAX; }
     863                 :       2885 :   for (v = 0;; v++)
     864         [ +  + ]:       3067 :     if (!gequal0(gel(x,2+v))) break;
     865         [ +  - ]:       3067 :   if (Z) *Z = RgX_shift_shallow(x, -v);
     866                 :       2885 :   return v;
     867                 :            : }
     868                 :            : 
     869                 :            : GEN
     870                 :          0 : RgXQC_red(GEN P, GEN T)
     871                 :            : {
     872                 :          0 :   long i, l = lg(P);
     873                 :          0 :   GEN Q = cgetg(l, t_COL);
     874         [ #  # ]:          0 :   for (i=1; i<l; i++) gel(Q,i) = grem(gel(P,i), T);
     875                 :          0 :   return Q;
     876                 :            : }
     877                 :            : 
     878                 :            : GEN
     879                 :         42 : RgXQV_red(GEN P, GEN T)
     880                 :            : {
     881                 :         42 :   long i, l = lg(P);
     882                 :         42 :   GEN Q = cgetg(l, t_VEC);
     883         [ +  + ]:        308 :   for (i=1; i<l; i++) gel(Q,i) = grem(gel(P,i), T);
     884                 :         42 :   return Q;
     885                 :            : }
     886                 :            : 
     887                 :            : GEN
     888                 :      23898 : RgXQX_red(GEN P, GEN T)
     889                 :            : {
     890                 :      23898 :   long i, l = lg(P);
     891                 :      23898 :   GEN Q = cgetg(l, t_POL);
     892                 :      23898 :   Q[1] = P[1];
     893         [ +  + ]:     125727 :   for (i=2; i<l; i++) gel(Q,i) = grem(gel(P,i), T);
     894                 :      23898 :   return normalizepol_lg(Q, l);
     895                 :            : }
     896                 :            : 
     897                 :            : GEN
     898                 :     265626 : RgX_deriv(GEN x)
     899                 :            : {
     900                 :     265626 :   long i,lx = lg(x)-1;
     901                 :            :   GEN y;
     902                 :            : 
     903         [ +  + ]:     265626 :   if (lx<3) return pol_0(varn(x));
     904                 :     264842 :   y = cgetg(lx,t_POL); gel(y,2) = gcopy(gel(x,3));
     905         [ +  + ]:    1184638 :   for (i=3; i<lx ; i++) gel(y,i) = gmulsg(i-1,gel(x,i+1));
     906                 :     265626 :   y[1] = x[1]; return normalizepol_lg(y,i);
     907                 :            : }
     908                 :            : 
     909                 :            : GEN
     910                 :     294579 : RgX_recipspec_shallow(GEN x, long l, long n)
     911                 :            : {
     912                 :            :   long i;
     913                 :     294579 :   GEN z=cgetg(n+2,t_POL)+2;
     914         [ +  + ]:   13829018 :   for(i=0; i<l; i++)
     915                 :   13534438 :     gel(z,n-i-1) = gel(x,i);
     916         [ +  + ]:     382304 :   for(   ; i<n; i++)
     917                 :      87724 :     gel(z, n-i-1) = gen_0;
     918                 :     294580 :   return normalizepol_lg(z-2,n+2);
     919                 :            : }
     920                 :            : 
     921                 :            : /* return coefficients s.t x = x_0 X^n + ... + x_n */
     922                 :            : GEN
     923                 :      63847 : RgX_recip(GEN x)
     924                 :            : {
     925                 :            :   long lx, i, j;
     926                 :      63847 :   GEN y = cgetg_copy(x, &lx);
     927         [ +  + ]:     382837 :   y[1] = x[1]; for (i=2,j=lx-1; i<lx; i++,j--) gel(y,i) = gcopy(gel(x,j));
     928                 :      63847 :   return normalizepol_lg(y,lx);
     929                 :            : }
     930                 :            : /* shallow version */
     931                 :            : GEN
     932                 :    1155941 : RgX_recip_shallow(GEN x)
     933                 :            : {
     934                 :            :   long lx, i, j;
     935                 :    1155941 :   GEN y = cgetg_copy(x, &lx);
     936         [ +  + ]:    5249076 :   y[1] = x[1]; for (i=2,j=lx-1; i<lx; i++,j--) gel(y,i) = gel(x,j);
     937                 :    1155961 :   return y;
     938                 :            : }
     939                 :            : /*******************************************************************/
     940                 :            : /*                                                                 */
     941                 :            : /*                      ADDITION / SUBTRACTION                     */
     942                 :            : /*                                                                 */
     943                 :            : /*******************************************************************/
     944                 :            : /* same variable */
     945                 :            : GEN
     946                 :   17486284 : RgX_add(GEN x, GEN y)
     947                 :            : {
     948                 :   17486284 :   long i, lx = lg(x), ly = lg(y);
     949                 :            :   GEN z;
     950         [ +  + ]:   17486284 :   if (ly <= lx) {
     951                 :   15579750 :     z = cgetg(lx,t_POL); z[1] = x[1];
     952         [ +  + ]:   86915605 :     for (i=2; i < ly; i++) gel(z,i) = gadd(gel(x,i),gel(y,i));
     953         [ +  + ]:   30706641 :     for (   ; i < lx; i++) gel(z,i) = gcopy(gel(x,i));
     954                 :   15579749 :     z = normalizepol_lg(z, lx);
     955                 :            :   } else {
     956                 :    1906534 :     z = cgetg(ly,t_POL); z[1] = y[1];
     957         [ +  + ]:   21971587 :     for (i=2; i < lx; i++) gel(z,i) = gadd(gel(x,i),gel(y,i));
     958         [ +  + ]:    6875839 :     for (   ; i < ly; i++) gel(z,i) = gcopy(gel(y,i));
     959                 :    1906536 :     z = normalizepol_lg(z, ly);
     960                 :            :   }
     961                 :   17486285 :   return z;
     962                 :            : }
     963                 :            : GEN
     964                 :   10088449 : RgX_sub(GEN x, GEN y)
     965                 :            : {
     966                 :   10088449 :   long i, lx = lg(x), ly = lg(y);
     967                 :            :   GEN z;
     968         [ +  + ]:   10088449 :   if (ly <= lx) {
     969                 :    8064044 :     z = cgetg(lx,t_POL); z[1] = x[1];
     970         [ +  + ]:   58824298 :     for (i=2; i < ly; i++) gel(z,i) = gsub(gel(x,i),gel(y,i));
     971         [ +  + ]:   14444706 :     for (   ; i < lx; i++) gel(z,i) = gcopy(gel(x,i));
     972                 :    8064041 :     z = normalizepol_lg(z, lx);
     973                 :            :   } else {
     974                 :    2024405 :     z = cgetg(ly,t_POL); z[1] = y[1];
     975         [ +  + ]:    9518762 :     for (i=2; i < lx; i++) gel(z,i) = gsub(gel(x,i),gel(y,i));
     976         [ +  + ]:    5376554 :     for (   ; i < ly; i++) gel(z,i) = gneg(gel(y,i));
     977                 :    2024405 :     z = normalizepol_lg(z, ly);
     978                 :            :   }
     979                 :   10088446 :   return z;
     980                 :            : }
     981                 :            : GEN
     982                 :    1245673 : RgX_neg(GEN x)
     983                 :            : {
     984                 :    1245673 :   long i, lx = lg(x);
     985                 :    1245673 :   GEN y = cgetg(lx, t_POL); y[1] = x[1];
     986         [ +  + ]:   17239920 :   for (i=2; i<lx; i++) gel(y,i) = gneg(gel(x,i));
     987                 :    1245673 :   return y;
     988                 :            : }
     989                 :            : 
     990                 :            : GEN
     991                 :   10662525 : RgX_Rg_add(GEN y, GEN x)
     992                 :            : {
     993                 :            :   GEN z;
     994                 :   10662525 :   long lz = lg(y), i;
     995         [ +  + ]:   10662525 :   if (lz == 2) return scalarpol(x,varn(y));
     996                 :    9114234 :   z = cgetg(lz,t_POL); z[1] = y[1];
     997                 :    9114234 :   gel(z,2) = gadd(gel(y,2),x);
     998         [ +  + ]:   32058017 :   for(i=3; i<lz; i++) gel(z,i) = gcopy(gel(y,i));
     999                 :            :   /* probably useless unless lz = 3, but cannot be skipped if y is
    1000                 :            :    * an inexact 0 */
    1001                 :   10662525 :   return normalizepol_lg(z,lz);
    1002                 :            : }
    1003                 :            : GEN
    1004                 :       2380 : RgX_Rg_add_shallow(GEN y, GEN x)
    1005                 :            : {
    1006                 :            :   GEN z;
    1007                 :       2380 :   long lz = lg(y), i;
    1008         [ -  + ]:       2380 :   if (lz == 2) return scalarpol(x,varn(y));
    1009                 :       2380 :   z = cgetg(lz,t_POL); z[1] = y[1];
    1010                 :       2380 :   gel(z,2) = gadd(gel(y,2),x);
    1011         [ +  + ]:       4844 :   for(i=3; i<lz; i++) gel(z,i) = gel(y,i);
    1012                 :       2380 :   return z = normalizepol_lg(z,lz);
    1013                 :            : }
    1014                 :            : GEN
    1015                 :      30675 : RgX_Rg_sub(GEN y, GEN x)
    1016                 :            : {
    1017                 :            :   GEN z;
    1018                 :      30675 :   long lz = lg(y), i;
    1019         [ +  + ]:      30675 :   if (lz == 2)
    1020                 :            :   { /* scalarpol(gneg(x),varn(y)) optimized */
    1021                 :       3864 :     long v = varn(y);
    1022         [ +  + ]:       3864 :     if (isrationalzero(x)) return pol_0(v);
    1023                 :         14 :     z = cgetg(3,t_POL);
    1024         [ -  + ]:         14 :     z[1] = gequal0(x)? evalvarn(v)
    1025                 :         14 :                    : evalvarn(v) | evalsigne(1);
    1026                 :         14 :     gel(z,2) = gneg(x); return z;
    1027                 :            :   }
    1028                 :      26811 :   z = cgetg(lz,t_POL); z[1] = y[1];
    1029                 :      26811 :   gel(z,2) = gsub(gel(y,2),x);
    1030         [ +  + ]:     110251 :   for(i=3; i<lz; i++) gel(z,i) = gcopy(gel(y,i));
    1031                 :      30675 :   return z = normalizepol_lg(z,lz);
    1032                 :            : }
    1033                 :            : GEN
    1034                 :     440613 : Rg_RgX_sub(GEN x, GEN y)
    1035                 :            : {
    1036                 :            :   GEN z;
    1037                 :     440613 :   long lz = lg(y), i;
    1038         [ +  + ]:     440613 :   if (lz == 2) return scalarpol(x,varn(y));
    1039                 :     439598 :   z = cgetg(lz,t_POL); z[1] = y[1];
    1040                 :     439598 :   gel(z,2) = gsub(x, gel(y,2));
    1041         [ +  + ]:    1450394 :   for(i=3; i<lz; i++) gel(z,i) = gneg(gel(y,i));
    1042                 :     440613 :   return z = normalizepol_lg(z,lz);
    1043                 :            : }
    1044                 :            : /*******************************************************************/
    1045                 :            : /*                                                                 */
    1046                 :            : /*                  KARATSUBA MULTIPLICATION                       */
    1047                 :            : /*                                                                 */
    1048                 :            : /*******************************************************************/
    1049                 :            : #if 0
    1050                 :            : /* to debug Karatsuba-like routines */
    1051                 :            : GEN
    1052                 :            : zx_debug_spec(GEN x, long nx)
    1053                 :            : {
    1054                 :            :   GEN z = cgetg(nx+2,t_POL);
    1055                 :            :   long i;
    1056                 :            :   for (i=0; i<nx; i++) gel(z,i+2) = stoi(x[i]);
    1057                 :            :   z[1] = evalsigne(1); return z;
    1058                 :            : }
    1059                 :            : 
    1060                 :            : GEN
    1061                 :            : RgX_debug_spec(GEN x, long nx)
    1062                 :            : {
    1063                 :            :   GEN z = cgetg(nx+2,t_POL);
    1064                 :            :   long i;
    1065                 :            :   for (i=0; i<nx; i++) z[i+2] = x[i];
    1066                 :            :   z[1] = evalsigne(1); return z;
    1067                 :            : }
    1068                 :            : #endif
    1069                 :            : 
    1070                 :            : /* generic multiplication */
    1071                 :            : 
    1072                 :            : static GEN
    1073                 :    2786731 : addpol(GEN x, GEN y, long lx, long ly)
    1074                 :            : {
    1075                 :            :   long i,lz;
    1076                 :            :   GEN z;
    1077                 :            : 
    1078         [ +  + ]:    2786731 :   if (ly>lx) swapspec(x,y, lx,ly);
    1079                 :    2786731 :   lz = lx+2; z = cgetg(lz,t_POL) + 2;
    1080         [ +  + ]:   12161918 :   for (i=0; i<ly; i++) gel(z,i) = gadd(gel(x,i),gel(y,i));
    1081         [ +  + ]:    8385405 :   for (   ; i<lx; i++) gel(z,i) = gel(x,i);
    1082                 :    2786725 :   z -= 2; z[1]=0; return normalizepol_lg(z, lz);
    1083                 :            : }
    1084                 :            : 
    1085                 :            : static GEN
    1086                 :     285848 : addpolcopy(GEN x, GEN y, long lx, long ly)
    1087                 :            : {
    1088                 :            :   long i,lz;
    1089                 :            :   GEN z;
    1090                 :            : 
    1091         [ -  + ]:     285848 :   if (ly>lx) swapspec(x,y, lx,ly);
    1092                 :     285848 :   lz = lx+2; z = cgetg(lz,t_POL) + 2;
    1093         [ +  + ]:    1625601 :   for (i=0; i<ly; i++) gel(z,i) = gadd(gel(x,i),gel(y,i));
    1094         [ +  + ]:    3797484 :   for (   ; i<lx; i++) gel(z,i) = gcopy(gel(x,i));
    1095                 :     285849 :   z -= 2; z[1]=0; return normalizepol_lg(z, lz);
    1096                 :            : }
    1097                 :            : 
    1098                 :            : /* Return the vector of coefficients of x, where we replace rational 0s by NULL
    1099                 :            :  * [ to speed up basic operation s += x[i]*y[j] ]. We create a proper
    1100                 :            :  * t_VECSMALL, to hold this, which can be left on stack: gerepile
    1101                 :            :  * will not crash on it. The returned vector itself is not a proper GEN,
    1102                 :            :  * we access the coefficients as x[i], i = 0..deg(x) */
    1103                 :            : static GEN
    1104                 :   30999627 : RgXspec_kill0(GEN x, long lx)
    1105                 :            : {
    1106                 :   30999627 :   GEN z = cgetg(lx+1, t_VECSMALL) + 1; /* inhibit gerepile-wise */
    1107                 :            :   long i;
    1108         [ +  + ]:  130205977 :   for (i=0; i <lx; i++)
    1109                 :            :   {
    1110                 :   99206401 :     GEN c = gel(x,i);
    1111         [ +  + ]:   99206401 :     z[i] = (long)(isrationalzero(c)? NULL: c);
    1112                 :            :   }
    1113                 :   30999576 :   return z;
    1114                 :            : }
    1115                 :            : 
    1116                 :            : INLINE GEN
    1117                 :   71141733 : RgX_mulspec_basecase_limb(GEN x, GEN y, long a, long b)
    1118                 :            : {
    1119                 :   71141733 :   pari_sp av = avma;
    1120                 :   71141733 :   GEN s = NULL;
    1121                 :            :   long i;
    1122                 :            : 
    1123         [ +  + ]:  278689839 :   for (i=a; i<b; i++)
    1124 [ +  + ][ +  + ]:  207553412 :     if (gel(y,i) && gel(x,-i))
    1125                 :            :     {
    1126                 :  158353701 :       GEN t = gmul(gel(y,i), gel(x,-i));
    1127         [ +  + ]:  158358605 :       s = s? gadd(s, t): t;
    1128                 :            :     }
    1129         [ +  + ]:   71136427 :   return s? gerepileupto(av, s): gen_0;
    1130                 :            : }
    1131                 :            : 
    1132                 :            : /* assume nx >= ny > 0, return x * y * t^v */
    1133                 :            : static GEN
    1134                 :   12296680 : RgX_mulspec_basecase(GEN x, GEN y, long nx, long ny, long v)
    1135                 :            : {
    1136                 :            :   long i, lz, nz;
    1137                 :            :   GEN z;
    1138                 :            : 
    1139                 :   12296680 :   x = RgXspec_kill0(x,nx);
    1140                 :   12296665 :   y = RgXspec_kill0(y,ny);
    1141                 :   12296666 :   lz = nx + ny + 1; nz = lz-2;
    1142                 :   12296666 :   lz += v;
    1143                 :   12296666 :   z = cgetg(lz, t_POL) + 2; /* x:y:z [i] = term of degree i */
    1144         [ +  + ]:   27045969 :   for (i=0; i<v; i++) gel(z++, 0) = gen_0;
    1145         [ +  + ]:   37148660 :   for (i=0; i<ny; i++)gel(z,i) = RgX_mulspec_basecase_limb(x+i,y, 0, i+1);
    1146         [ +  + ]:   26894118 :   for (  ; i<nx; i++) gel(z,i) = RgX_mulspec_basecase_limb(x+i,y, 0,ny);
    1147         [ +  + ]:   24852009 :   for (  ; i<nz; i++) gel(z,i) = RgX_mulspec_basecase_limb(x+i,y, i-nx+1,ny);
    1148                 :   12296672 :   z -= v+2; z[1] = 0; return normalizepol_lg(z, lz);
    1149                 :            : }
    1150                 :            : 
    1151                 :            : /* return (x * X^d) + y. Assume d > 0 */
    1152                 :            : GEN
    1153                 :    1850485 : addmulXn(GEN x, GEN y, long d)
    1154                 :            : {
    1155                 :            :   GEN xd, yd, zd;
    1156                 :            :   long a, lz, nx, ny;
    1157                 :            : 
    1158         [ +  + ]:    1850485 :   if (!signe(x)) return y;
    1159                 :    1785018 :   ny = lgpol(y);
    1160                 :    1785018 :   nx = lgpol(x);
    1161                 :    1785017 :   zd = (GEN)avma;
    1162                 :    1785017 :   x += 2; y += 2; a = ny-d;
    1163         [ +  + ]:    1785017 :   if (a <= 0)
    1164                 :            :   {
    1165                 :     140419 :     lz = nx+d+2;
    1166                 :     140419 :     (void)new_chunk(lz); xd = x+nx; yd = y+ny;
    1167         [ +  + ]:     717572 :     while (xd > x) gel(--zd,0) = gel(--xd,0);
    1168                 :     140420 :     x = zd + a;
    1169         [ +  + ]:     157190 :     while (zd > x) gel(--zd,0) = gen_0;
    1170                 :            :   }
    1171                 :            :   else
    1172                 :            :   {
    1173                 :    1644598 :     xd = new_chunk(d); yd = y+d;
    1174                 :    1644598 :     x = addpol(x,yd, nx,a);
    1175         [ +  + ]:    1644602 :     lz = (a>nx)? ny+2: lg(x)+d;
    1176         [ +  + ]:   10472334 :     x += 2; while (xd > x) *--zd = *--xd;
    1177                 :            :   }
    1178         [ +  + ]:    6878808 :   while (yd > y) *--zd = *--yd;
    1179                 :    1785022 :   *--zd = evalsigne(1);
    1180                 :    1850489 :   *--zd = evaltyp(t_POL) | evallg(lz); return zd;
    1181                 :            : }
    1182                 :            : 
    1183                 :            : GEN
    1184                 :     116879 : addshiftpol(GEN x, GEN y, long d)
    1185                 :            : {
    1186                 :     116879 :   long v = varn(x);
    1187                 :     116879 :   x = addmulXn(x,y,d);
    1188                 :     116879 :   setvarn(x,v); return x;
    1189                 :            : }
    1190                 :            : 
    1191                 :            : /* as above, producing a clean malloc */
    1192                 :            : static GEN
    1193                 :     578229 : addmulXncopy(GEN x, GEN y, long d)
    1194                 :            : {
    1195                 :            :   GEN xd, yd, zd;
    1196                 :            :   long a, lz, nx, ny;
    1197                 :            : 
    1198         [ +  + ]:     578229 :   if (!signe(x)) return RgX_copy(y);
    1199                 :     578208 :   nx = lgpol(x);
    1200                 :     578208 :   ny = lgpol(y);
    1201                 :     578208 :   zd = (GEN)avma;
    1202                 :     578208 :   x += 2; y += 2; a = ny-d;
    1203         [ +  + ]:     578208 :   if (a <= 0)
    1204                 :            :   {
    1205                 :     292359 :     lz = nx+d+2;
    1206                 :     292359 :     (void)new_chunk(lz); xd = x+nx; yd = y+ny;
    1207         [ +  + ]:    4106199 :     while (xd > x) gel(--zd,0) = gcopy(gel(--xd,0));
    1208                 :     292371 :     x = zd + a;
    1209         [ +  + ]:     760877 :     while (zd > x) gel(--zd,0) = gen_0;
    1210                 :            :   }
    1211                 :            :   else
    1212                 :            :   {
    1213                 :     285849 :     xd = new_chunk(d); yd = y+d;
    1214                 :     285848 :     x = addpolcopy(x,yd, nx,a);
    1215         [ -  + ]:     285848 :     lz = (a>nx)? ny+2: lg(x)+d;
    1216         [ +  + ]:    5137577 :     x += 2; while (xd > x) *--zd = *--xd;
    1217                 :            :   }
    1218         [ +  + ]:    3439566 :   while (yd > y) gel(--zd,0) = gcopy(gel(--yd,0));
    1219                 :     578208 :   *--zd = evalsigne(1);
    1220                 :     578229 :   *--zd = evaltyp(t_POL) | evallg(lz); return zd;
    1221                 :            : }
    1222                 :            : 
    1223                 :            : /* return x * y mod t^n */
    1224                 :            : static GEN
    1225                 :    3073803 : RgXn_mul_basecase(GEN x, GEN y, long n)
    1226                 :            : {
    1227                 :    3073803 :   long i, lz = n+2, lx = lgpol(x), ly = lgpol(y);
    1228                 :            :   GEN z;
    1229         [ -  + ]:    3073803 :   if (lx < 0) return pol_0(varn(x));
    1230         [ -  + ]:    3073803 :   if (ly < 0) return pol_0(varn(x));
    1231                 :    3073803 :   z = cgetg(lz, t_POL) + 2;
    1232         [ +  + ]:    3073803 :   x+=2; if (lx > n) lx = n;
    1233         [ +  + ]:    3073803 :   y+=2; if (ly > n) ly = n;
    1234                 :    3073803 :   z[-1] = x[-1];
    1235         [ +  + ]:    3073803 :   if (ly > lx) { swap(x,y); lswap(lx,ly); }
    1236                 :    3073803 :   x = RgXspec_kill0(x, lx);
    1237                 :    3073803 :   y = RgXspec_kill0(y, ly);
    1238                 :            :   /* x:y:z [i] = term of degree i */
    1239         [ +  + ]:   18251029 :   for (i=0;i<ly; i++) gel(z,i) = RgX_mulspec_basecase_limb(x+i,y, 0,i+1);
    1240         [ +  + ]:    6135980 :   for (  ; i<lx; i++) gel(z,i) = RgX_mulspec_basecase_limb(x+i,y, 0,ly);
    1241         [ +  + ]:    3967920 :   for (  ; i<n; i++)  gel(z,i) = RgX_mulspec_basecase_limb(x+i,y, i-lx+1,ly);
    1242                 :    3073803 :   return normalizepol_lg(z - 2, lz);
    1243                 :            : }
    1244                 :            : /* Mulders / Karatsuba product f*g mod t^n (Hanrot-Zimmermann variant) */
    1245                 :            : GEN
    1246                 :    3528572 : RgXn_mul(GEN f, GEN g, long n)
    1247                 :            : {
    1248                 :    3528572 :   pari_sp av = avma;
    1249                 :            :   GEN fe,fo, ge,go, l,h,m;
    1250                 :            :   long n0, n1;
    1251         [ +  + ]:    3528572 :   if (degpol(f) + degpol(g) < n) return RgX_mul(f,g);
    1252         [ +  + ]:    3073831 :   if (n < 80) return RgXn_mul_basecase(f,g,n);
    1253                 :         28 :   n0 = n>>1; n1 = n-n0;
    1254                 :         28 :   RgX_even_odd(f, &fe, &fo);
    1255                 :         28 :   RgX_even_odd(g, &ge, &go);
    1256                 :         28 :   l = RgXn_mul(fe,ge,n1);
    1257                 :         28 :   h = RgXn_mul(fo,go,n0);
    1258                 :         28 :   m = RgX_sub(RgXn_mul(RgX_add(fe,fo),RgX_add(ge,go),n0), RgX_add(l,h));
    1259                 :            :   /* n1-1 <= n0 <= n1, deg l,m <= n1-1, deg h <= n0-1
    1260                 :            :    * result is t^2 h(t^2) + t m(t^2) + l(t^2) */
    1261                 :         28 :   l = RgX_inflate(l,2); /* deg l <= 2n1 - 2 <= n-1 */
    1262                 :            :   /* deg(t m(t^2)) <= 2n1 - 1 <= n, truncate to < n */
    1263         [ -  + ]:         28 :   if (2*degpol(m)+1 == n) m = normalizepol_lg(m, lg(m)-1);
    1264                 :         28 :   m = RgX_inflate(m,2);
    1265                 :            :   /* deg(t^2 h(t^2)) <= 2n0 <= n, truncate to < n */
    1266         [ +  - ]:         28 :   if (2*degpol(h)+2 == n) h = normalizepol_lg(h, lg(h)-1);
    1267                 :         28 :   h = RgX_inflate(h,2);
    1268                 :         28 :   h = addmulXncopy(addmulXn(h,m,1), l,1);
    1269                 :    3528572 :   setvarn(h, varn(f)); return gerepileupto(av, h);
    1270                 :            : }
    1271                 :            : 
    1272                 :            : /* fast product (Karatsuba) of polynomials a,b. These are not real GENs, a+2,
    1273                 :            :  * b+2 were sent instead. na, nb = number of terms of a, b.
    1274                 :            :  * Only c, c0, c1, c2 are genuine GEN.
    1275                 :            :  */
    1276                 :            : GEN
    1277                 :   13078189 : RgX_mulspec(GEN a, GEN b, long na, long nb)
    1278                 :            : {
    1279                 :            :   GEN a0, c, c0;
    1280                 :   13078189 :   long n0, n0a, i, v = 0;
    1281                 :            :   pari_sp av;
    1282                 :            : 
    1283 [ +  + ][ +  + ]:   19868994 :   while (na && isrationalzero(gel(a,0))) { a++; na--; v++; }
    1284 [ +  + ][ +  + ]:   21534954 :   while (nb && isrationalzero(gel(b,0))) { b++; nb--; v++; }
    1285         [ +  + ]:   13078188 :   if (na < nb) swapspec(a,b, na,nb);
    1286         [ +  + ]:   13078188 :   if (!nb) return pol_0(0);
    1287                 :            : 
    1288         [ +  + ]:   12874520 :   if (nb < RgX_MUL_LIMIT) return RgX_mulspec_basecase(a,b,na,nb, v);
    1289                 :     577840 :   RgX_shift_inplace_init(v);
    1290                 :     577843 :   i = (na>>1); n0 = na-i; na = i;
    1291                 :     577843 :   av = avma; a0 = a+n0; n0a = n0;
    1292 [ +  + ][ +  + ]:    1608232 :   while (n0a && isrationalzero(gel(a,n0a-1))) n0a--;
    1293                 :            : 
    1294         [ +  + ]:     577840 :   if (nb > n0)
    1295                 :            :   {
    1296                 :            :     GEN b0,c1,c2;
    1297                 :            :     long n0b;
    1298                 :            : 
    1299                 :     571068 :     nb -= n0; b0 = b+n0; n0b = n0;
    1300 [ +  + ][ +  + ]:    1399868 :     while (n0b && isrationalzero(gel(b,n0b-1))) n0b--;
    1301                 :     571067 :     c = RgX_mulspec(a,b,n0a,n0b);
    1302                 :     571070 :     c0 = RgX_mulspec(a0,b0, na,nb);
    1303                 :            : 
    1304                 :     571072 :     c2 = addpol(a0,a, na,n0a);
    1305                 :     571072 :     c1 = addpol(b0,b, nb,n0b);
    1306                 :            : 
    1307                 :     571071 :     c1 = RgX_mulspec(c1+2,c2+2, lgpol(c1),lgpol(c2));
    1308                 :     571071 :     c2 = RgX_sub(c1, RgX_add(c0,c));
    1309                 :     571069 :     c0 = addmulXn(c0, c2, n0);
    1310                 :            :   }
    1311                 :            :   else
    1312                 :            :   {
    1313                 :       6772 :     c = RgX_mulspec(a,b,n0a,nb);
    1314                 :       6773 :     c0 = RgX_mulspec(a0,b,na,nb);
    1315                 :            :   }
    1316                 :     577845 :   c0 = addmulXncopy(c0,c,n0);
    1317                 :   13078174 :   return RgX_shift_inplace(gerepileupto(av,c0), v);
    1318                 :            : }
    1319                 :            : 
    1320                 :            : INLINE GEN
    1321                 :    2709583 : RgX_sqrspec_basecase_limb(GEN x, long a, long i)
    1322                 :            : {
    1323                 :    2709583 :   pari_sp av = avma;
    1324                 :    2709583 :   GEN s = NULL;
    1325                 :    2709583 :   long j, l = (i+1)>>1;
    1326         [ +  + ]:    9985312 :   for (j=a; j<l; j++)
    1327                 :            :   {
    1328                 :    7277902 :     GEN xj = gel(x,j), xx = gel(x,i-j);
    1329 [ +  + ][ +  + ]:    7277902 :     if (xj && xx)
    1330                 :            :     {
    1331                 :    4644787 :       GEN t = gmul(xj, xx);
    1332         [ +  + ]:    4648443 :       s = s? gadd(s, t): t;
    1333                 :            :     }
    1334                 :            :   }
    1335         [ +  + ]:    2707410 :   if (s) s = gshift(s,1);
    1336         [ +  + ]:    2707562 :   if ((i&1) == 0)
    1337                 :            :   {
    1338                 :    1483273 :     GEN t = gel(x, i>>1);
    1339         [ +  + ]:    1483273 :     if (t) {
    1340                 :    1236787 :       t = gsqr(t);
    1341         [ +  + ]:    1236813 :       s = s? gadd(s, t): t;
    1342                 :            :     }
    1343                 :            :   }
    1344         [ +  + ]:    2707488 :   return s? gerepileupto(av,s): gen_0;
    1345                 :            : }
    1346                 :            : static GEN
    1347                 :     258027 : RgX_sqrspec_basecase(GEN x, long nx, long v)
    1348                 :            : {
    1349                 :            :   long i, lz, nz;
    1350                 :            :   GEN z;
    1351                 :            : 
    1352         [ +  + ]:     258027 :   if (!nx) return pol_0(0);
    1353                 :     258020 :   x = RgXspec_kill0(x,nx);
    1354                 :     258019 :   lz = (nx << 1) + 1, nz = lz-2;
    1355                 :     258019 :   lz += v;
    1356                 :     258019 :   z = cgetg(lz,t_POL) + 2;
    1357         [ +  + ]:     403038 :   for (i=0; i<v; i++) gel(z++, 0) = gen_0;
    1358         [ +  + ]:    1735901 :   for (i=0; i<nx; i++)gel(z,i) = RgX_sqrspec_basecase_limb(x, 0, i);
    1359         [ +  + ]:    1477859 :   for (  ; i<nz; i++) gel(z,i) = RgX_sqrspec_basecase_limb(x, i-nx+1, i);
    1360                 :     258025 :   z -= v+2; z[1] = 0; return normalizepol_lg(z, lz);
    1361                 :            : }
    1362                 :            : /* return x^2 mod t^n */
    1363                 :            : static GEN
    1364                 :        665 : RgXn_sqr_basecase(GEN x, long n)
    1365                 :            : {
    1366                 :        665 :   long i, lz = n+2, lx = lgpol(x);
    1367                 :            :   GEN z;
    1368         [ -  + ]:        665 :   if (lx < 0) return pol_0(varn(x));
    1369                 :        665 :   z = cgetg(lz, t_POL);
    1370                 :        665 :   z[1] = x[1];
    1371         [ -  + ]:        665 :   x+=2; if (lx > n) lx = n;
    1372                 :        665 :   x = RgXspec_kill0(x,lx);
    1373                 :        665 :   z+=2;/* x:z [i] = term of degree i */
    1374         [ +  + ]:      11116 :   for (i=0;i<lx; i++) gel(z,i) = RgX_sqrspec_basecase_limb(x, 0, i);
    1375         [ -  + ]:        665 :   for (  ; i<n; i++)  gel(z,i) = RgX_sqrspec_basecase_limb(x, i-lx+1, i);
    1376                 :        665 :   z -= 2; return normalizepol_lg(z, lz);
    1377                 :            : }
    1378                 :            : /* Mulders / Karatsuba product f^2 mod t^n (Hanrot-Zimmermann variant) */
    1379                 :            : GEN
    1380                 :       1967 : RgXn_sqr(GEN f, long n)
    1381                 :            : {
    1382                 :       1967 :   pari_sp av = avma;
    1383                 :            :   GEN fe,fo, l,h,m;
    1384                 :            :   long n0, n1;
    1385         [ +  + ]:       1967 :   if (2*degpol(f) < n) return RgX_sqr(f);
    1386         [ +  + ]:        693 :   if (n < 80) return RgXn_sqr_basecase(f,n);
    1387                 :         28 :   n0 = n>>1; n1 = n-n0;
    1388                 :         28 :   RgX_even_odd(f, &fe, &fo);
    1389                 :         28 :   l = RgXn_sqr(fe,n1);
    1390                 :         28 :   h = RgXn_sqr(fo,n0);
    1391                 :         28 :   m = RgX_sub(RgXn_sqr(RgX_add(fe,fo),n0), RgX_add(l,h));
    1392                 :            :   /* n1-1 <= n0 <= n1, deg l,m <= n1-1, deg h <= n0-1
    1393                 :            :    * result is t^2 h(t^2) + t m(t^2) + l(t^2) */
    1394                 :         28 :   l = RgX_inflate(l,2); /* deg l <= 2n1 - 2 <= n-1 */
    1395                 :            :   /* deg(t m(t^2)) <= 2n1 - 1 <= n, truncate to < n */
    1396         [ -  + ]:         28 :   if (2*degpol(m)+1 == n) m = normalizepol_lg(m, lg(m)-1);
    1397                 :         28 :   m = RgX_inflate(m,2);
    1398                 :            :   /* deg(t^2 h(t^2)) <= 2n0 <= n, truncate to < n */
    1399         [ +  - ]:         28 :   if (2*degpol(h)+2 == n) h = normalizepol_lg(h, lg(h)-1);
    1400                 :         28 :   h = RgX_inflate(h,2);
    1401                 :         28 :   h = addmulXncopy(addmulXn(h,m,1), l,1);
    1402                 :       1967 :   setvarn(h, varn(f)); return gerepileupto(av, h);
    1403                 :            : }
    1404                 :            : 
    1405                 :            : GEN
    1406                 :     258354 : RgX_sqrspec(GEN a, long na)
    1407                 :            : {
    1408                 :            :   GEN a0, c, c0, c1;
    1409                 :     258354 :   long n0, n0a, i, v = 0;
    1410                 :            :   pari_sp av;
    1411                 :            : 
    1412 [ +  + ][ +  + ]:     330865 :   while (na && isrationalzero(gel(a,0))) { a++; na--; v += 2; }
    1413         [ +  + ]:     258355 :   if (na<RgX_SQR_LIMIT) return RgX_sqrspec_basecase(a, na, v);
    1414                 :        328 :   RgX_shift_inplace_init(v);
    1415                 :        328 :   i = (na>>1); n0 = na-i; na = i;
    1416                 :        328 :   av = avma; a0 = a+n0; n0a = n0;
    1417 [ +  - ][ +  + ]:        392 :   while (n0a && isrationalzero(gel(a,n0a-1))) n0a--;
    1418                 :            : 
    1419                 :        328 :   c = RgX_sqrspec(a,n0a);
    1420                 :        328 :   c0 = RgX_sqrspec(a0,na);
    1421                 :        328 :   c1 = gmul2n(RgX_mulspec(a0,a, na,n0a), 1);
    1422                 :        328 :   c0 = addmulXn(c0,c1, n0);
    1423                 :        328 :   c0 = addmulXncopy(c0,c,n0);
    1424                 :     258353 :   return RgX_shift_inplace(gerepileupto(av,c0), v);
    1425                 :            : }
    1426                 :            : 
    1427                 :            : /* (X^a + A)(X^b + B) - X^(a+b), where deg A < a, deg B < b */
    1428                 :            : GEN
    1429                 :     418342 : RgX_mul_normalized(GEN A, long a, GEN B, long b)
    1430                 :            : {
    1431                 :     418342 :   GEN z = RgX_mul(A, B);
    1432         [ +  + ]:     418342 :   if (a < b)
    1433                 :      10003 :     z = addmulXn(addmulXn(A, B, b-a), z, a);
    1434         [ +  + ]:     408339 :   else if (a > b)
    1435                 :     245199 :     z = addmulXn(addmulXn(B, A, a-b), z, b);
    1436                 :            :   else
    1437                 :     163140 :     z = addmulXn(RgX_add(A, B), z, a);
    1438                 :     418342 :   setvarn(z,varn(A)); return z;
    1439                 :            : }
    1440                 :            : 
    1441                 :            : GEN
    1442                 :   11351113 : RgX_mul(GEN x, GEN y)
    1443                 :            : {
    1444                 :   11351113 :   GEN z = RgX_mulspec(y+2, x+2, lgpol(y), lgpol(x));
    1445                 :   11351113 :   setvarn(z,varn(x)); return z;
    1446                 :            : }
    1447                 :            : 
    1448                 :            : GEN
    1449                 :     257698 : RgX_sqr(GEN x)
    1450                 :            : {
    1451                 :     257698 :   GEN z = RgX_sqrspec(x+2, lgpol(x));
    1452                 :     257697 :   setvarn(z,varn(x)); return z;
    1453                 :            : }
    1454                 :            : 
    1455                 :            : /*******************************************************************/
    1456                 :            : /*                                                                 */
    1457                 :            : /*                               DIVISION                          */
    1458                 :            : /*                                                                 */
    1459                 :            : /*******************************************************************/
    1460                 :            : GEN
    1461                 :    1585683 : RgX_Rg_divexact(GEN x, GEN y) {
    1462                 :            :   long i, lx;
    1463                 :            :   GEN z;
    1464 [ +  + ][ +  + ]:    1585683 :   if (typ(y) == t_INT && is_pm1(y))
    1465         [ +  + ]:     325291 :     return signe(y) < 0 ? RgX_neg(x): RgX_copy(x);
    1466                 :    1260392 :   z = cgetg_copy(x, &lx); z[1] = x[1];
    1467         [ +  + ]:    5159571 :   for (i=2; i<lx; i++) gel(z,i) = gdivexact(gel(x,i),y);
    1468                 :    1585683 :   return z;
    1469                 :            : }
    1470                 :            : GEN
    1471                 :   22153478 : RgX_Rg_div(GEN x, GEN y) {
    1472                 :            :   long i, lx;
    1473                 :   22153478 :   GEN z = cgetg_copy(x, &lx); z[1] = x[1];
    1474         [ +  + ]:   61776998 :   for (i=2; i<lx; i++) gel(z,i) = gdiv(gel(x,i),y);
    1475                 :   22153478 :   return normalizepol_lg(z, lx);
    1476                 :            : }
    1477                 :            : GEN
    1478                 :       1449 : RgX_normalize(GEN x)
    1479                 :            : {
    1480                 :       1449 :   GEN d = NULL;
    1481                 :       1449 :   long i, n = lg(x)-1;
    1482         [ +  - ]:       1449 :   for (i = n; i > 1; i--)
    1483                 :            :   {
    1484                 :       1449 :     d = gel(x,i);
    1485         [ +  - ]:       1449 :     if (!gequal0(d)) break;
    1486                 :            :   }
    1487         [ -  + ]:       1449 :   if (i == 1) return pol_0(varn(x));
    1488 [ +  - ][ +  + ]:       1449 :   if (i == n && isint1(d)) return x;
    1489                 :       1449 :   return normalizepol_lg(RgX_Rg_div(x, d), i+1);
    1490                 :            : }
    1491                 :            : GEN
    1492                 :       1729 : RgX_divs(GEN x, long y) {
    1493                 :            :   long i, lx;
    1494                 :       1729 :   GEN z = cgetg_copy(x, &lx); z[1] = x[1];
    1495         [ +  + ]:       7672 :   for (i=2; i<lx; i++) gel(z,i) = gdivgs(gel(x,i),y);
    1496                 :       1729 :   return normalizepol_lg(z, lx);
    1497                 :            : }
    1498                 :            : GEN
    1499                 :      30163 : RgX_div_by_X_x(GEN a, GEN x, GEN *r)
    1500                 :            : {
    1501                 :      30163 :   long l = lg(a), i;
    1502                 :      30163 :   GEN a0, z0, z = cgetg(l-1, t_POL);
    1503                 :      30163 :   z[1] = a[1];
    1504                 :      30163 :   a0 = a + l-1;
    1505                 :      30163 :   z0 = z + l-2; *z0 = *a0--;
    1506         [ +  + ]:     723289 :   for (i=l-3; i>1; i--) /* z[i] = a[i+1] + x*z[i+1] */
    1507                 :            :   {
    1508                 :     693126 :     GEN t = gadd(gel(a0--,0), gmul(x, gel(z0--,0)));
    1509                 :     693126 :     gel(z0,0) = t;
    1510                 :            :   }
    1511         [ -  + ]:      30163 :   if (r) *r = gadd(gel(a0,0), gmul(x, gel(z0,0)));
    1512                 :      30163 :   return z;
    1513                 :            : }
    1514                 :            : /* Polynomial division x / y:
    1515                 :            :  *   if z = ONLY_REM  return remainder, otherwise return quotient
    1516                 :            :  *   if z != NULL set *z to remainder
    1517                 :            :  *   *z is the last object on stack (and thus can be disposed of with cgiv
    1518                 :            :  *   instead of gerepile) */
    1519                 :            : /* assume, typ(x) = typ(y) = t_POL, same variable */
    1520                 :            : GEN
    1521                 :   13149685 : RgX_divrem(GEN x, GEN y, GEN *pr)
    1522                 :            : {
    1523                 :            :   pari_sp avy, av, av1;
    1524                 :            :   long dx,dy,dz,i,j,sx,lr;
    1525                 :            :   GEN z,p1,p2,rem,y_lead,mod;
    1526                 :            :   GEN (*f)(GEN,GEN);
    1527                 :            : 
    1528         [ -  + ]:   13149685 :   if (!signe(y)) pari_err_INV("RgX_divrem",y);
    1529                 :            : 
    1530                 :   13149685 :   dy = degpol(y);
    1531                 :   13149649 :   y_lead = gel(y,dy+2);
    1532         [ -  + ]:   13149649 :   if (gequal0(y_lead)) /* normalize denominator if leading term is 0 */
    1533                 :            :   {
    1534                 :          0 :     pari_warn(warner,"normalizing a polynomial with 0 leading term");
    1535         [ #  # ]:          0 :     for (dy--; dy>=0; dy--)
    1536                 :            :     {
    1537                 :          0 :       y_lead = gel(y,dy+2);
    1538         [ #  # ]:          0 :       if (!gequal0(y_lead)) break;
    1539                 :            :     }
    1540                 :            :   }
    1541         [ +  + ]:   13149639 :   if (!dy) /* y is constant */
    1542                 :            :   {
    1543         [ +  + ]:      54792 :     if (pr == ONLY_REM) return pol_0(varn(x));
    1544                 :      54183 :     z = RgX_Rg_div(x, y_lead);
    1545         [ +  + ]:      54183 :     if (pr == ONLY_DIVIDES) return z;
    1546         [ -  + ]:      53504 :     if (pr) *pr = pol_0(varn(x));
    1547                 :      53504 :     return z;
    1548                 :            :   }
    1549                 :   13094847 :   dx = degpol(x);
    1550         [ +  + ]:   13094816 :   if (dx < dy)
    1551                 :            :   {
    1552         [ +  + ]:    1094333 :     if (pr == ONLY_REM) return RgX_copy(x);
    1553 [ +  + ][ -  + ]:     305572 :     if (pr == ONLY_DIVIDES) return signe(x)? NULL: pol_0(varn(x));
    1554                 :     305551 :     z = pol_0(varn(x));
    1555         [ +  + ]:     305551 :     if (pr) *pr = RgX_copy(x);
    1556                 :     305551 :     return z;
    1557                 :            :   }
    1558                 :            : 
    1559                 :            :   /* x,y in R[X], y non constant */
    1560                 :   12000483 :   av = avma;
    1561      [ +  +  + ]:   12000483 :   switch(typ(y_lead))
    1562                 :            :   {
    1563                 :            :     case t_REAL:
    1564                 :       2836 :       y_lead = ginv(y_lead);
    1565                 :       2836 :       f = gmul; mod = NULL;
    1566                 :       2836 :       break;
    1567                 :            :     case t_INTMOD:
    1568                 :       4522 :     case t_POLMOD: y_lead = ginv(y_lead);
    1569                 :       4522 :       f = gmul; mod = gmodulo(gen_1, gel(y_lead,1));
    1570                 :       4522 :       break;
    1571         [ +  + ]:   11993125 :     default: if (gequal1(y_lead)) y_lead = NULL;
    1572                 :   11993139 :       f = gdiv; mod = NULL;
    1573                 :            :   }
    1574                 :            : 
    1575         [ +  + ]:   12000497 :   if (y_lead == NULL)
    1576                 :   10145367 :     p2 = gel(x,dx+2);
    1577                 :            :   else {
    1578                 :            :     for(;;) {
    1579                 :    1855130 :       p2 = f(gel(x,dx+2),y_lead);
    1580                 :    1855130 :       p2 = simplify_shallow(p2);
    1581 [ -  + ][ #  # ]:    1855130 :       if (!isexactzero(p2) || (--dx < 0)) break;
    1582                 :          0 :     }
    1583         [ -  + ]:    1855130 :     if (dx < dy) /* leading coeff of x was in fact zero */
    1584                 :            :     {
    1585         [ #  # ]:          0 :       if (pr == ONLY_DIVIDES) {
    1586                 :          0 :         avma = av;
    1587         [ #  # ]:          0 :         return (dx < 0)? pol_0(varn(x)) : NULL;
    1588                 :            :       }
    1589         [ #  # ]:          0 :       if (pr == ONLY_REM)
    1590                 :            :       {
    1591         [ #  # ]:          0 :         if (dx < 0)
    1592                 :          0 :           return gerepilecopy(av, scalarpol(p2, varn(x)));
    1593                 :            :         else
    1594                 :            :         {
    1595                 :            :           GEN t;
    1596                 :          0 :           avma = av;
    1597                 :          0 :           t = cgetg(dx + 3, t_POL); t[1] = x[1];
    1598         [ #  # ]:          0 :           for (i = 2; i < dx + 3; i++) gel(t,i) = gcopy(gel(x,i));
    1599                 :          0 :           return t;
    1600                 :            :         }
    1601                 :            :       }
    1602         [ #  # ]:          0 :       if (pr) /* cf ONLY_REM above */
    1603                 :            :       {
    1604         [ #  # ]:          0 :         if (dx < 0)
    1605                 :            :         {
    1606                 :          0 :           p2 = gclone(p2);
    1607                 :          0 :           avma = av;
    1608                 :          0 :           z = pol_0(varn(x));
    1609                 :          0 :           x = scalarpol(p2, varn(x));
    1610                 :          0 :           gunclone(p2);
    1611                 :            :         }
    1612                 :            :         else
    1613                 :            :         {
    1614                 :            :           GEN t;
    1615                 :          0 :           avma = av;
    1616                 :          0 :           z = pol_0(varn(x));
    1617                 :          0 :           t = cgetg(dx + 3, t_POL); t[1] = x[1];
    1618         [ #  # ]:          0 :           for (i = 2; i < dx + 3; i++) gel(t,i) = gcopy(gel(x,i));
    1619                 :          0 :           x = t;
    1620                 :            :         }
    1621                 :          0 :         *pr = x;
    1622                 :            :       }
    1623                 :            :       else
    1624                 :            :       {
    1625                 :          0 :         avma = av;
    1626                 :          0 :         z = pol_0(varn(x));
    1627                 :            :       }
    1628                 :          0 :       return z;
    1629                 :            :     }
    1630                 :            :   }
    1631                 :            :   /* dx >= dy */
    1632                 :   12000497 :   avy = avma;
    1633                 :   12000497 :   dz = dx-dy;
    1634                 :   12000497 :   z = cgetg(dz+3,t_POL); z[1] = x[1];
    1635                 :   12000448 :   x += 2;
    1636                 :   12000448 :   z += 2;
    1637                 :   12000448 :   y += 2;
    1638                 :   12000448 :   gel(z,dz) = gcopy(p2);
    1639                 :            : 
    1640         [ +  + ]:   34633724 :   for (i=dx-1; i>=dy; i--)
    1641                 :            :   {
    1642                 :   22633127 :     av1=avma; p1=gel(x,i);
    1643 [ +  + ][ +  + ]: 1119213809 :     for (j=i-dy+1; j<=i && j<=dz; j++) p1 = gsub(p1, gmul(gel(z,j),gel(y,i-j)));
    1644         [ +  + ]:   22597503 :     if (y_lead) p1 = simplify(f(p1,y_lead));
    1645                 :            : 
    1646         [ +  + ]:   22597503 :     if (isrationalzero(p1)) { avma=av1; p1 = gen_0; }
    1647                 :            :     else
    1648         [ -  + ]:   13075862 :       p1 = avma==av1? gcopy(p1): gerepileupto(av1,p1);
    1649                 :   22633046 :     gel(z,i-dy) = p1;
    1650                 :            :   }
    1651         [ +  + ]:   12000597 :   if (!pr) return gerepileupto(av,z-2);
    1652                 :            : 
    1653                 :    5943687 :   rem = (GEN)avma; av1 = (pari_sp)new_chunk(dx+3);
    1654                 :    5943613 :   for (sx=0; ; i--)
    1655                 :            :   {
    1656                 :    6741842 :     p1 = gel(x,i);
    1657                 :            :     /* we always enter this loop at least once */
    1658 [ +  + ][ +  + ]:   26277012 :     for (j=0; j<=i && j<=dz; j++) p1 = gsub(p1, gmul(gel(z,j),gel(y,i-j)));
    1659 [ +  + ][ -  + ]:    6741600 :     if (mod && avma==av1) p1 = gmul(p1,mod);
    1660         [ +  + ]:    6741600 :     if (!gequal0(p1)) { sx = 1; break; } /* remainder is non-zero */
    1661         [ +  + ]:    3992362 :     if (!isexactzero(p1)) break;
    1662         [ +  + ]:    3985848 :     if (!i) break;
    1663                 :     798229 :     avma=av1;
    1664                 :     798229 :   }
    1665         [ +  + ]:    5943616 :   if (pr == ONLY_DIVIDES)
    1666                 :            :   {
    1667         [ +  + ]:        693 :     if (sx) { avma=av; return NULL; }
    1668                 :        686 :     avma = (pari_sp)rem;
    1669                 :        686 :     return gerepileupto(av,z-2);
    1670                 :            :   }
    1671                 :    5942923 :   lr=i+3; rem -= lr;
    1672         [ +  + ]:    5942923 :   if (avma==av1) { avma = (pari_sp)rem; p1 = gcopy(p1); }
    1673                 :    5883322 :   else p1 = gerepileupto((pari_sp)rem,p1);
    1674                 :    5943006 :   rem[0] = evaltyp(t_POL) | evallg(lr);
    1675                 :    5942133 :   rem[1] = z[-1];
    1676                 :    5942133 :   rem += 2;
    1677                 :    5942133 :   gel(rem,i) = p1;
    1678         [ +  + ]:   15726895 :   for (i--; i>=0; i--)
    1679                 :            :   {
    1680                 :    9783910 :     av1=avma; p1 = gel(x,i);
    1681 [ +  + ][ +  + ]:   67829710 :     for (j=0; j<=i && j<=dz; j++) p1 = gsub(p1, gmul(gel(z,j),gel(y,i-j)));
    1682 [ +  + ][ -  + ]:    9696206 :     if (mod && avma==av1) p1 = gmul(p1,mod);
    1683         [ +  + ]:    9779638 :     gel(rem,i) = avma==av1? gcopy(p1):gerepileupto(av1,p1);
    1684                 :            :   }
    1685                 :    5942985 :   rem -= 2;
    1686         [ +  + ]:    5942985 :   if (!sx) (void)normalizepol_lg(rem, lr);
    1687         [ +  + ]:    5942976 :   if (pr == ONLY_REM) return gerepileupto(av,rem);
    1688                 :    4014797 :   z -= 2;
    1689                 :            :   {
    1690                 :    4014797 :     GEN *gptr[2]; gptr[0]=&z; gptr[1]=&rem;
    1691                 :   13149707 :     gerepilemanysp(av,avy,gptr,2); *pr = rem; return z;
    1692                 :            :   }
    1693                 :            : }
    1694                 :            : 
    1695                 :            : /* x and y in (R[Y]/T)[X]  (lifted), T in R[Y]. y preferably monic */
    1696                 :            : GEN
    1697                 :      39900 : RgXQX_divrem(GEN x, GEN y, GEN T, GEN *pr)
    1698                 :            : {
    1699                 :            :   long vx, dx, dy, dz, i, j, sx, lr;
    1700                 :            :   pari_sp av0, av, tetpil;
    1701                 :            :   GEN z,p1,rem,lead;
    1702                 :            : 
    1703         [ -  + ]:      39900 :   if (!signe(y)) pari_err_INV("RgXQX_divrem",y);
    1704                 :      39900 :   vx = varn(x);
    1705                 :      39900 :   dx = degpol(x);
    1706                 :      39900 :   dy = degpol(y);
    1707         [ +  + ]:      39900 :   if (dx < dy)
    1708                 :            :   {
    1709         [ +  - ]:      11977 :     if (pr)
    1710                 :            :     {
    1711                 :      11977 :       av0 = avma; x = RgXQX_red(x, T);
    1712 [ +  + ][ -  + ]:      11977 :       if (pr == ONLY_DIVIDES) { avma=av0; return signe(x)? NULL: gen_0; }
    1713         [ +  - ]:      11963 :       if (pr == ONLY_REM) return x;
    1714                 :          0 :       *pr = x;
    1715                 :            :     }
    1716                 :          0 :     return pol_0(vx);
    1717                 :            :   }
    1718                 :      27923 :   lead = leading_coeff(y);
    1719         [ +  + ]:      27923 :   if (!dy) /* y is constant */
    1720                 :            :   {
    1721 [ -  + ][ #  # ]:          7 :     if (pr && pr != ONLY_DIVIDES)
    1722                 :            :     {
    1723         [ #  # ]:          0 :       if (pr == ONLY_REM) return pol_0(vx);
    1724                 :          0 :       *pr = pol_0(vx);
    1725                 :            :     }
    1726         [ +  - ]:          7 :     if (gequal1(lead)) return RgX_copy(x);
    1727                 :          0 :     av0 = avma; x = gmul(x, ginvmod(lead,T)); tetpil = avma;
    1728                 :          0 :     return gerepile(av0,tetpil,RgXQX_red(x,T));
    1729                 :            :   }
    1730                 :      27916 :   av0 = avma; dz = dx-dy;
    1731         [ +  + ]:      27916 :   lead = gequal1(lead)? NULL: gclone(ginvmod(lead,T));
    1732                 :      27916 :   avma = av0;
    1733                 :      27916 :   z = cgetg(dz+3,t_POL); z[1] = x[1];
    1734                 :      27916 :   x += 2; y += 2; z += 2;
    1735                 :            : 
    1736                 :      27916 :   p1 = gel(x,dx); av = avma;
    1737         [ +  + ]:      27916 :   gel(z,dz) = lead? gerepileupto(av, grem(gmul(p1,lead), T)): gcopy(p1);
    1738         [ +  + ]:     147990 :   for (i=dx-1; i>=dy; i--)
    1739                 :            :   {
    1740                 :     120074 :     av=avma; p1=gel(x,i);
    1741 [ +  + ][ +  + ]:     523913 :     for (j=i-dy+1; j<=i && j<=dz; j++) p1 = gsub(p1, gmul(gel(z,j),gel(y,i-j)));
    1742         [ +  + ]:     120074 :     if (lead) p1 = gmul(grem(p1, T), lead);
    1743                 :     120074 :     tetpil=avma; gel(z,i-dy) = gerepile(av,tetpil, grem(p1, T));
    1744                 :            :   }
    1745 [ -  + ][ #  # ]:      27916 :   if (!pr) { if (lead) gunclone(lead); return z-2; }
    1746                 :            : 
    1747                 :      27916 :   rem = (GEN)avma; av = (pari_sp)new_chunk(dx+3);
    1748                 :      27916 :   for (sx=0; ; i--)
    1749                 :            :   {
    1750                 :      45266 :     p1 = gel(x,i);
    1751 [ +  + ][ +  + ]:     158121 :     for (j=0; j<=i && j<=dz; j++) p1 = gsub(p1, gmul(gel(z,j),gel(y,i-j)));
    1752         [ +  + ]:      45266 :     tetpil=avma; p1 = grem(p1, T); if (!gequal0(p1)) { sx = 1; break; }
    1753         [ +  + ]:      22768 :     if (!i) break;
    1754                 :      17350 :     avma=av;
    1755                 :      17350 :   }
    1756         [ +  + ]:      27916 :   if (pr == ONLY_DIVIDES)
    1757                 :            :   {
    1758         [ +  + ]:       4984 :     if (lead) gunclone(lead);
    1759         [ +  + ]:       4984 :     if (sx) { avma=av0; return NULL; }
    1760                 :       4886 :     avma = (pari_sp)rem; return z-2;
    1761                 :            :   }
    1762                 :      22932 :   lr=i+3; rem -= lr;
    1763                 :      22932 :   rem[0] = evaltyp(t_POL) | evallg(lr);
    1764                 :      22932 :   rem[1] = z[-1];
    1765                 :      22932 :   p1 = gerepile((pari_sp)rem,tetpil,p1);
    1766                 :      22932 :   rem += 2; gel(rem,i) = p1;
    1767         [ +  + ]:      69667 :   for (i--; i>=0; i--)
    1768                 :            :   {
    1769                 :      46735 :     av=avma; p1 = gel(x,i);
    1770 [ +  + ][ +  + ]:     139799 :     for (j=0; j<=i && j<=dz; j++)
    1771                 :      93064 :       p1 = gsub(p1, gmul(gel(z,j),gel(y,i-j)));
    1772                 :      46735 :     tetpil=avma; gel(rem,i) = gerepile(av,tetpil, grem(p1, T));
    1773                 :            :   }
    1774                 :      22932 :   rem -= 2;
    1775         [ -  + ]:      22932 :   if (lead) gunclone(lead);
    1776         [ +  + ]:      22932 :   if (!sx) (void)normalizepol_lg(rem, lr);
    1777         [ +  + ]:      22932 :   if (pr == ONLY_REM) return gerepileupto(av0,rem);
    1778                 :      39900 :   *pr = rem; return z-2;
    1779                 :            : }
    1780                 :            : 
    1781                 :            : /*******************************************************************/
    1782                 :            : /*                                                                 */
    1783                 :            : /*                        PSEUDO-DIVISION                          */
    1784                 :            : /*                                                                 */
    1785                 :            : /*******************************************************************/
    1786                 :            : INLINE GEN
    1787                 :    2235668 : rem(GEN c, GEN T)
    1788                 :            : {
    1789 [ +  + ][ +  - ]:    2235668 :   if (T && typ(c) == t_POL && varn(c) == varn(T)) c = RgX_rem(c, T);
                 [ +  - ]
    1790                 :    2235668 :   return c;
    1791                 :            : }
    1792                 :            : 
    1793                 :            : /* x, y, are ZYX, lc(y) is an integer, T is a ZY */
    1794                 :            : int
    1795                 :       1127 : ZXQX_dvd(GEN x, GEN y, GEN T)
    1796                 :            : {
    1797                 :            :   long dx, dy, dz, i, p, T_ismonic;
    1798                 :       1127 :   pari_sp av = avma, av2;
    1799                 :            :   GEN y_lead;
    1800                 :            : 
    1801         [ -  + ]:       1127 :   if (!signe(y)) pari_err_INV("ZXQX_dvd",y);
    1802                 :       1127 :   dy = degpol(y); y_lead = gel(y,dy+2);
    1803         [ +  - ]:       1127 :   if (typ(y_lead) == t_POL) y_lead = gel(y_lead, 2); /* t_INT */
    1804                 :            :   /* if monic, no point in using pseudo-division */
    1805         [ +  + ]:       1127 :   if (gequal1(y_lead)) return signe(RgXQX_rem(x, y, T)) == 0;
    1806                 :        637 :   T_ismonic = gequal1(leading_coeff(T));
    1807                 :        637 :   dx = degpol(x);
    1808         [ -  + ]:        637 :   if (dx < dy) return !signe(x);
    1809                 :        637 :   (void)new_chunk(2);
    1810                 :        637 :   x = RgX_recip_shallow(x)+2;
    1811                 :        637 :   y = RgX_recip_shallow(y)+2;
    1812                 :            :   /* pay attention to sparse divisors */
    1813         [ +  + ]:       1400 :   for (i = 1; i <= dy; i++)
    1814         [ +  + ]:        763 :     if (!signe(gel(y,i))) gel(y,i) = NULL;
    1815                 :        637 :   dz = dx-dy; p = dz+1;
    1816                 :        637 :   av2 = avma;
    1817                 :            :   for (;;)
    1818                 :            :   {
    1819                 :       7147 :     GEN m, x0 = gel(x,0), y0 = y_lead, cx = content(x0);
    1820                 :       7147 :     x0 = gneg(x0); p--;
    1821                 :       7147 :     m = gcdii(cx, y0);
    1822         [ +  + ]:       7147 :     if (!equali1(m))
    1823                 :            :     {
    1824                 :       6405 :       x0 = gdiv(x0, m);
    1825                 :       6405 :       y0 = diviiexact(y0, m);
    1826         [ +  + ]:       6405 :       if (equali1(y0)) y0 = NULL;
    1827                 :            :     }
    1828         [ +  + ]:      15120 :     for (i=1; i<=dy; i++)
    1829                 :            :     {
    1830         [ +  + ]:       7973 :       GEN c = gel(x,i); if (y0) c = gmul(y0, c);
    1831         [ +  + ]:       7973 :       if (gel(y,i)) c = gadd(c, gmul(x0,gel(y,i)));
    1832 [ +  + ][ +  + ]:       7973 :       if (typ(c) == t_POL) c = T_ismonic ? ZX_rem(c, T): RgX_rem(c, T);
    1833                 :       7973 :       gel(x,i) = c;
    1834                 :            :     }
    1835         [ +  + ]:      77287 :     for (   ; i<=dx; i++)
    1836                 :            :     {
    1837         [ +  + ]:      70140 :       GEN c = gel(x,i); if (y0) c = gmul(y0, c);
    1838 [ +  + ][ +  + ]:      70140 :       if (typ(c) == t_POL) c = T_ismonic ? ZX_rem(c, T): RgX_rem(c, T);
    1839                 :      70140 :       gel(x,i) = c;
    1840                 :            :     }
    1841 [ +  + ][ +  + ]:       7924 :     do { x++; dx--; } while (dx >= 0 && !signe(gel(x,0)));
    1842         [ +  + ]:       7147 :     if (dx < dy) break;
    1843         [ -  + ]:       6510 :     if (gc_needed(av2,1))
    1844                 :            :     {
    1845         [ #  # ]:          0 :       if(DEBUGMEM>1) pari_warn(warnmem,"ZXQX_dvd dx = %ld >= %ld",dx,dy);
    1846                 :          0 :       gerepilecoeffs(av2,x,dx+1);
    1847                 :            :     }
    1848                 :       6510 :   }
    1849                 :       1127 :   avma = av; return (dx < 0);
    1850                 :            : }
    1851                 :            : 
    1852                 :            : /* T either NULL or a t_POL. */
    1853                 :            : GEN
    1854                 :      68684 : RgXQX_pseudorem(GEN x, GEN y, GEN T)
    1855                 :            : {
    1856                 :      68684 :   long vx = varn(x), dx, dy, dz, i, lx, p;
    1857                 :      68684 :   pari_sp av = avma, av2;
    1858                 :            :   GEN y_lead;
    1859                 :            : 
    1860         [ -  + ]:      68684 :   if (!signe(y)) pari_err_INV("RgXQX_pseudorem",y);
    1861                 :      68684 :   dy = degpol(y); y_lead = gel(y,dy+2);
    1862                 :            :   /* if monic, no point in using pseudo-division */
    1863 [ +  + ][ -  + ]:      68684 :   if (gequal1(y_lead)) return T? RgXQX_rem(x, y, T): RgX_rem(x, y);
    1864                 :      64876 :   dx = degpol(x);
    1865         [ -  + ]:      64876 :   if (dx < dy) return RgX_copy(x);
    1866                 :      64876 :   (void)new_chunk(2);
    1867                 :      64876 :   x = RgX_recip_shallow(x)+2;
    1868                 :      64876 :   y = RgX_recip_shallow(y)+2;
    1869                 :            :   /* pay attention to sparse divisors */
    1870         [ +  + ]:     246298 :   for (i = 1; i <= dy; i++)
    1871         [ +  + ]:     181422 :     if (isexactzero(gel(y,i))) gel(y,i) = NULL;
    1872                 :      64876 :   dz = dx-dy; p = dz+1;
    1873                 :      64876 :   av2 = avma;
    1874                 :            :   for (;;)
    1875                 :            :   {
    1876                 :     171934 :     gel(x,0) = gneg(gel(x,0)); p--;
    1877         [ +  + ]:     625726 :     for (i=1; i<=dy; i++)
    1878                 :            :     {
    1879                 :     453792 :       GEN c = gmul(y_lead, gel(x,i));
    1880         [ +  + ]:     453792 :       if (gel(y,i)) c = gadd(c, gmul(gel(x,0),gel(y,i)));
    1881                 :     453792 :       gel(x,i) = rem(c, T);
    1882                 :            :     }
    1883         [ +  + ]:     441718 :     for (   ; i<=dx; i++)
    1884                 :            :     {
    1885                 :     269784 :       GEN c = gmul(y_lead, gel(x,i));
    1886                 :     269784 :       gel(x,i) = rem(c, T);
    1887                 :            :     }
    1888 [ +  + ][ +  + ]:     178920 :     do { x++; dx--; } while (dx >= 0 && gequal0(gel(x,0)));
    1889         [ +  + ]:     171934 :     if (dx < dy) break;
    1890         [ -  + ]:     107058 :     if (gc_needed(av2,1))
    1891                 :            :     {
    1892         [ #  # ]:          0 :       if(DEBUGMEM>1) pari_warn(warnmem,"RgX_pseudorem dx = %ld >= %ld",dx,dy);
    1893                 :          0 :       gerepilecoeffs(av2,x,dx+1);
    1894                 :            :     }
    1895                 :     107058 :   }
    1896         [ +  + ]:      64876 :   if (dx < 0) return pol_0(vx);
    1897                 :      63357 :   lx = dx+3; x -= 2;
    1898                 :      63357 :   x[0] = evaltyp(t_POL) | evallg(lx);
    1899                 :      63357 :   x[1] = evalsigne(1) | evalvarn(vx);
    1900                 :      63357 :   x = RgX_recip_shallow(x);
    1901         [ +  + ]:      63357 :   if (p)
    1902                 :            :   { /* multiply by y[0]^p   [beware dummy vars from FpX_FpXY_resultant] */
    1903                 :       1519 :     GEN t = y_lead;
    1904 [ -  + ][ #  # ]:       1519 :     if (T && typ(t) == t_POL && varn(t) == varn(T))
                 [ #  # ]
    1905                 :          0 :       t = RgXQ_powu(t, p, T);
    1906                 :            :     else
    1907                 :       1519 :       t = gpowgs(t, p);
    1908         [ +  + ]:       5502 :     for (i=2; i<lx; i++)
    1909                 :            :     {
    1910                 :       3983 :       GEN c = gmul(gel(x,i), t);
    1911                 :       3983 :       gel(x,i) = rem(c,T);
    1912                 :            :     }
    1913         [ +  - ]:       1519 :     if (!T) return gerepileupto(av, x);
    1914                 :            :   }
    1915                 :      68684 :   return gerepilecopy(av, x);
    1916                 :            : }
    1917                 :            : 
    1918                 :            : GEN
    1919                 :      68684 : RgX_pseudorem(GEN x, GEN y) { return RgXQX_pseudorem(x,y, NULL); }
    1920                 :            : 
    1921                 :            : /* Compute z,r s.t lc(y)^(dx-dy+1) x = z y + r */
    1922                 :            : GEN
    1923                 :     263197 : RgXQX_pseudodivrem(GEN x, GEN y, GEN T, GEN *ptr)
    1924                 :            : {
    1925                 :     263197 :   long vx = varn(x), dx, dy, dz, i, iz, lx, lz, p;
    1926                 :     263197 :   pari_sp av = avma, av2;
    1927                 :            :   GEN z, r, ypow, y_lead;
    1928                 :            : 
    1929         [ -  + ]:     263197 :   if (!signe(y)) pari_err_INV("RgXQX_pseudodivrem",y);
    1930                 :     263197 :   dy = degpol(y); y_lead = gel(y,dy+2);
    1931 [ +  + ][ +  + ]:     263197 :   if (gequal1(y_lead)) return T? RgXQX_divrem(x,y, T, ptr): RgX_divrem(x,y, ptr);
    1932                 :     198291 :   dx = degpol(x);
    1933         [ -  + ]:     198291 :   if (dx < dy) { *ptr = RgX_copy(x); return pol_0(vx); }
    1934         [ +  + ]:     198291 :   if (dx == dy)
    1935                 :            :   {
    1936                 :         28 :     GEN x_lead = gel(x,lg(x)-1);
    1937                 :         28 :     x = RgX_renormalize_lg(leafcopy(x), lg(x)-1);
    1938                 :         28 :     y = RgX_renormalize_lg(leafcopy(y), lg(y)-1);
    1939                 :         28 :     r = RgX_sub(RgX_Rg_mul(x, y_lead), RgX_Rg_mul(y, x_lead));
    1940                 :         28 :     *ptr = gerepileupto(av, r); return scalarpol(x_lead, vx);
    1941                 :            :   }
    1942                 :     198263 :   (void)new_chunk(2);
    1943                 :     198263 :   x = RgX_recip_shallow(x)+2;
    1944                 :     198263 :   y = RgX_recip_shallow(y)+2;
    1945                 :            :   /* pay attention to sparse divisors */
    1946         [ +  + ]:     638408 :   for (i = 1; i <= dy; i++)
    1947         [ +  + ]:     440145 :     if (isexactzero(gel(y,i))) gel(y,i) = NULL;
    1948                 :     198263 :   dz = dx-dy; p = dz+1;
    1949                 :     198263 :   lz = dz+3;
    1950                 :     198263 :   z = cgetg(lz, t_POL);
    1951                 :     198263 :   z[1] = evalsigne(1) | evalvarn(vx);
    1952         [ +  + ]:     607526 :   for (i = 2; i < lz; i++) gel(z,i) = gen_0;
    1953                 :     198263 :   ypow = new_chunk(dz+1);
    1954                 :     198263 :   gel(ypow,0) = gen_1;
    1955                 :     198263 :   gel(ypow,1) = y_lead;
    1956         [ +  + ]:     211000 :   for (i=2; i<=dz; i++)
    1957                 :            :   {
    1958                 :      12737 :     GEN c = gmul(gel(ypow,i-1), y_lead);
    1959                 :      12737 :     gel(ypow,i) = rem(c,T);
    1960                 :            :   }
    1961                 :     198263 :   av2 = avma;
    1962                 :     198263 :   for (iz=2;;)
    1963                 :            :   {
    1964                 :     395690 :     p--;
    1965                 :     395690 :     gel(z,iz++) = rem(gmul(gel(x,0), gel(ypow,p)), T);
    1966         [ +  + ]:    1268410 :     for (i=1; i<=dy; i++)
    1967                 :            :     {
    1968                 :     872720 :       GEN c = gmul(y_lead, gel(x,i));
    1969         [ +  + ]:     872720 :       if (gel(y,i)) c = gsub(c, gmul(gel(x,0),gel(y,i)));
    1970                 :     872720 :       gel(x,i) = rem(c, T);
    1971                 :            :     }
    1972         [ +  + ]:     622652 :     for (   ; i<=dx; i++)
    1973                 :            :     {
    1974                 :     226962 :       GEN c = gmul(y_lead, gel(x,i));
    1975                 :     226962 :       gel(x,i) = rem(c,T);
    1976                 :            :     }
    1977                 :     395690 :     x++; dx--;
    1978 [ +  + ][ +  + ]:     409263 :     while (dx >= dy && gequal0(gel(x,0))) { x++; dx--; iz++; }
    1979         [ +  + ]:     395690 :     if (dx < dy) break;
    1980         [ -  + ]:     197427 :     if (gc_needed(av2,1))
    1981                 :            :     {
    1982                 :          0 :       GEN X = x-2;
    1983         [ #  # ]:          0 :       if(DEBUGMEM>1) pari_warn(warnmem,"RgX_pseudodivrem dx=%ld >= %ld",dx,dy);
    1984                 :          0 :       X[0] = evaltyp(t_POL)|evallg(dx+3); X[1] = z[1]; /* hack */
    1985                 :          0 :       gerepileall(av2,2, &X, &z); x = X+2;
    1986                 :            :     }
    1987                 :     197427 :   }
    1988 [ +  + ][ +  + ]:     207585 :   while (dx >= 0 && gequal0(gel(x,0))) { x++; dx--; }
    1989         [ +  + ]:     198263 :   if (dx < 0)
    1990                 :         98 :     x = pol_0(vx);
    1991                 :            :   else
    1992                 :            :   {
    1993                 :     198165 :     lx = dx+3; x -= 2;
    1994                 :     198165 :     x[0] = evaltyp(t_POL) | evallg(lx);
    1995                 :     198165 :     x[1] = evalsigne(1) | evalvarn(vx);
    1996                 :     198165 :     x = RgX_recip_shallow(x);
    1997                 :            :   }
    1998                 :     198263 :   z = RgX_recip_shallow(z);
    1999                 :     198263 :   r = x;
    2000         [ +  + ]:     198263 :   if (p)
    2001                 :            :   {
    2002                 :      11639 :     GEN c = gel(ypow,p); r = RgX_Rg_mul(r, c);
    2003 [ +  + ][ +  - ]:      11639 :     if (T && typ(c) == t_POL && varn(c) == varn(T)) r = RgXQX_red(r, T);
                 [ +  - ]
    2004                 :            :   }
    2005                 :     198263 :   gerepileall(av, 2, &z, &r);
    2006                 :     263197 :   *ptr = r; return z;
    2007                 :            : }
    2008                 :            : GEN
    2009                 :     263078 : RgX_pseudodivrem(GEN x, GEN y, GEN *ptr)
    2010                 :     263078 : { return RgXQX_pseudodivrem(x,y,NULL,ptr); }
    2011                 :            : 
    2012                 :            : GEN
    2013                 :       9478 : RgXQX_mul(GEN x, GEN y, GEN T)
    2014                 :            : {
    2015                 :       9478 :   return RgXQX_red(RgX_mul(x,y), T);
    2016                 :            : }
    2017                 :            : GEN
    2018                 :   65657346 : RgX_Rg_mul(GEN y, GEN x) {
    2019                 :            :   long i, ly;
    2020                 :   65657346 :   GEN z = cgetg_copy(y, &ly); z[1] = y[1];
    2021         [ +  + ]:   65657346 :   if (ly == 2) return z;
    2022         [ +  + ]:  228777389 :   for (i = 2; i < ly; i++) gel(z,i) = gmul(x,gel(y,i));
    2023                 :   65657339 :   return normalizepol_lg(z,ly);
    2024                 :            : }
    2025                 :            : GEN
    2026                 :        231 : RgX_muls(GEN y, long x) {
    2027                 :            :   long i, ly;
    2028                 :        231 :   GEN z = cgetg_copy(y, &ly); z[1] = y[1];
    2029         [ +  + ]:        231 :   if (ly == 2) return z;
    2030         [ +  + ]:       1428 :   for (i = 2; i < ly; i++) gel(z,i) = gmulsg(x,gel(y,i));
    2031                 :        231 :   return normalizepol_lg(z,ly);
    2032                 :            : }
    2033                 :            : GEN
    2034                 :         14 : RgXQX_RgXQ_mul(GEN x, GEN y, GEN T)
    2035                 :            : {
    2036                 :         14 :   return RgXQX_red(RgX_Rg_mul(x,y), T);
    2037                 :            : }
    2038                 :            : GEN
    2039                 :         42 : RgXQV_RgXQ_mul(GEN v, GEN x, GEN T)
    2040                 :            : {
    2041                 :         42 :   return RgXQV_red(RgV_Rg_mul(v,x), T);
    2042                 :            : }
    2043                 :            : 
    2044                 :            : GEN
    2045                 :          0 : RgXQX_sqr(GEN x, GEN T)
    2046                 :            : {
    2047                 :          0 :   return RgXQX_red(RgX_sqr(x), T);
    2048                 :            : }
    2049                 :            : 
    2050                 :            : static GEN
    2051                 :      68145 : _add(void *data, GEN x, GEN y) { (void)data; return RgX_add(x, y); }
    2052                 :            : static GEN
    2053                 :          0 : _sub(void *data, GEN x, GEN y) { (void)data; return RgX_sub(x, y); }
    2054                 :            : static GEN
    2055                 :     195096 : _sqr(void *data, GEN x) { return RgXQ_sqr(x, (GEN)data); }
    2056                 :            : static GEN
    2057                 :      80332 : _mul(void *data, GEN x, GEN y) { return RgXQ_mul(x,y, (GEN)data); }
    2058                 :            : static GEN
    2059                 :     111888 : _cmul(void *data, GEN P, long a, GEN x) { (void)data; return RgX_Rg_mul(x,gel(P,a+2)); }
    2060                 :            : static GEN
    2061                 :     103173 : _one(void *data) { return pol_1(varn((GEN)data)); }
    2062                 :            : static GEN
    2063                 :         91 : _zero(void *data) { return pol_0(varn((GEN)data)); }
    2064                 :            : static GEN
    2065                 :      71113 : _red(void *data, GEN x) { (void)data; return gcopy(x); }
    2066                 :            : 
    2067                 :            : static struct bb_algebra RgXQ_algebra = { _red, _add, _sub,
    2068                 :            :               _mul, _sqr, _one, _zero };
    2069                 :            : 
    2070                 :            : GEN
    2071                 :          0 : RgX_RgXQV_eval(GEN Q, GEN x, GEN T)
    2072                 :            : {
    2073                 :          0 :   return gen_bkeval_powers(Q,degpol(Q),x,(void*)T,&RgXQ_algebra,_cmul);
    2074                 :            : }
    2075                 :            : 
    2076                 :            : GEN
    2077                 :      43155 : RgX_RgXQ_eval(GEN Q, GEN x, GEN T)
    2078                 :            : {
    2079                 :      43155 :   int use_sqr = 2*degpol(x) >= degpol(T);
    2080                 :      43155 :   return gen_bkeval(Q,degpol(Q),x,use_sqr,(void*)T,&RgXQ_algebra,_cmul);
    2081                 :            : }
    2082                 :            : 
    2083                 :            : /* mod X^n */
    2084                 :            : struct modXn {
    2085                 :            :   long v; /* varn(X) */
    2086                 :            :   long n;
    2087                 :            : } ;
    2088                 :            : static GEN
    2089                 :       1785 : _sqrXn(void *data, GEN x) {
    2090                 :       1785 :   struct modXn *S = (struct modXn*)data;
    2091                 :       1785 :   return RgXn_sqr(x, S->n);
    2092                 :            : }
    2093                 :            : static GEN
    2094                 :       1176 : _mulXn(void *data, GEN x, GEN y) {
    2095                 :       1176 :   struct modXn *S = (struct modXn*)data;
    2096                 :       1176 :   return RgXn_mul(x,y, S->n);
    2097                 :            : }
    2098                 :            : static GEN
    2099                 :       1407 : _oneXn(void *data) {
    2100                 :       1407 :   struct modXn *S = (struct modXn*)data;
    2101                 :       1407 :   return pol_1(S->v);
    2102                 :            : }
    2103                 :            : static GEN
    2104                 :          0 : _zeroXn(void *data) {
    2105                 :          0 :   struct modXn *S = (struct modXn*)data;
    2106                 :          0 :   return pol_0(S->v);
    2107                 :            : }
    2108                 :            : static struct bb_algebra RgXn_algebra = { _red, _add, _sub, _mulXn, _sqrXn,
    2109                 :            :                                           _oneXn, _zeroXn };
    2110                 :            : 
    2111                 :            : GEN
    2112                 :        336 : RgXn_powers(GEN x, long m, long n)
    2113                 :            : {
    2114                 :        336 :   long d = degpol(x);
    2115                 :        336 :   int use_sqr = (d<<1) >= n;
    2116                 :            :   struct modXn S;
    2117                 :        336 :   S.v = varn(x); S.n = n;
    2118                 :        336 :   return gen_powers(x,m,use_sqr,(void*)&S,_sqrXn,_mulXn,_oneXn);
    2119                 :            : }
    2120                 :            : 
    2121                 :            : GEN
    2122                 :       1505 : RgXn_powu_i(GEN x, ulong m, long n)
    2123                 :            : {
    2124                 :            :   struct modXn S;
    2125                 :       1505 :   S.v = varn(x); S.n = n;
    2126                 :       1505 :   return gen_powu_i(x, m, (void*)&S,_sqrXn,_mulXn);
    2127                 :            : }
    2128                 :            : GEN
    2129                 :          0 : RgXn_powu(GEN x, ulong m, long n)
    2130                 :            : {
    2131                 :            :   struct modXn S;
    2132                 :          0 :   S.v = varn(x); S.n = n;
    2133                 :          0 :   return gen_powu(x, m, (void*)&S,_sqrXn,_mulXn);
    2134                 :            : }
    2135                 :            : 
    2136                 :            : GEN
    2137                 :        672 : RgX_RgXnV_eval(GEN Q, GEN x, long n)
    2138                 :            : {
    2139                 :            :   struct modXn S;
    2140                 :        672 :   S.v = varn(gel(x,2)); S.n = n;
    2141                 :        672 :   return gen_bkeval_powers(Q,degpol(Q),x,(void*)&S,&RgXn_algebra,_cmul);
    2142                 :            : }
    2143                 :            : 
    2144                 :            : GEN
    2145                 :          0 : RgX_RgXn_eval(GEN Q, GEN x, long n)
    2146                 :            : {
    2147                 :          0 :   int use_sqr = 2*degpol(x) >= n;
    2148                 :            :   struct modXn S;
    2149                 :          0 :   S.v = varn(x); S.n = n;
    2150                 :          0 :   return gen_bkeval(Q,degpol(Q),x,use_sqr,(void*)&S,&RgXn_algebra,_cmul);
    2151                 :            : }
    2152                 :            : 
    2153                 :            : /* Q(x) mod t^n, x in R[t], n >= 1 */
    2154                 :            : GEN
    2155                 :       1491 : RgXn_eval(GEN Q, GEN x, long n)
    2156                 :            : {
    2157                 :       1491 :   long d = degpol(x);
    2158                 :            :   int use_sqr;
    2159                 :            :   struct modXn S;
    2160 [ +  + ][ +  - ]:       1491 :   if (d == 1 && isrationalzero(gel(x,2)))
    2161                 :            :   {
    2162                 :       1484 :     GEN y = RgX_unscale(Q, gel(x,3));
    2163                 :       1484 :     setvarn(y, varn(x)); return y;
    2164                 :            :   }
    2165                 :          7 :   S.v = varn(x);
    2166                 :          7 :   S.n = n;
    2167                 :          7 :   use_sqr = (d<<1) >= n;
    2168                 :       1491 :   return gen_bkeval(Q,degpol(Q),x,use_sqr,(void*)&S,&RgXn_algebra,_cmul);
    2169                 :            : }
    2170                 :            : 
    2171                 :            : GEN
    2172                 :        462 : RgXn_inv(GEN f, long e)
    2173                 :            : {
    2174                 :        462 :   pari_sp av = avma, av2;
    2175                 :            :   ulong mask;
    2176                 :            :   GEN W;
    2177                 :        462 :   long v = varn(f), n=1;
    2178         [ -  + ]:        462 :   if (signe(f)==0)
    2179                 :          0 :     pari_err_INV("RgXn_inv",f);
    2180                 :        462 :   W = scalarpol(ginv(gel(f,2)),v);
    2181                 :        462 :   mask = quadratic_prec_mask(e);
    2182                 :        462 :   av2 = avma;
    2183         [ +  + ]:       2079 :   for (;mask>1;)
    2184                 :            :   {
    2185                 :            :     GEN u, fr;
    2186                 :       1617 :     long n2 = n;
    2187         [ +  + ]:       1617 :     n<<=1; if (mask & 1) n--;
    2188                 :       1617 :     mask >>= 1;
    2189                 :       1617 :     fr = RgXn_red_shallow(f, n);
    2190                 :       1617 :     u = RgX_shift_shallow(RgXn_mul(W, fr, n), -n2);
    2191                 :       1617 :     W = RgX_sub(W, RgX_shift_shallow(RgXn_mul(u, W, n-n2), n2));
    2192         [ -  + ]:       1617 :     if (gc_needed(av2,2))
    2193                 :            :     {
    2194         [ #  # ]:          0 :       if(DEBUGMEM>1) pari_warn(warnmem,"RgXn_inv, e = %ld", n);
    2195                 :          0 :       W = gerepileupto(av2, W);
    2196                 :            :     }
    2197                 :            :   }
    2198                 :        462 :   return gerepileupto(av, W);
    2199                 :            : }
    2200                 :            : 
    2201                 :            : GEN
    2202                 :          0 : RgXn_exp(GEN h, long e)
    2203                 :            : {
    2204                 :          0 :   pari_sp av = avma, av2;
    2205                 :          0 :   long v = varn(h), n=1;
    2206                 :          0 :   GEN f = pol_1(v), g = pol_1(v);
    2207                 :          0 :   ulong mask = quadratic_prec_mask(e);
    2208                 :          0 :   av2 = avma;
    2209 [ #  # ][ #  # ]:          0 :   if (signe(h)==0 || degpol(h)<1 || !gequal0(gel(h,2)))
                 [ #  # ]
    2210                 :          0 :     pari_err_DOMAIN("RgXn_exp","valuation", "<", gen_1, h);
    2211         [ #  # ]:          0 :   for (;mask>1;)
    2212                 :            :   {
    2213                 :            :     GEN q, w;
    2214                 :          0 :     long n2 = n;
    2215         [ #  # ]:          0 :     n<<=1; if (mask & 1) n--;
    2216                 :          0 :     mask >>= 1;
    2217                 :          0 :     g = RgX_sub(RgX_muls(g,2),RgXn_mul(f,RgXn_sqr(g,n2),n2));
    2218                 :          0 :     q = RgX_deriv(RgXn_red_shallow(h,n2));
    2219                 :          0 :     w = RgX_add(q, RgXn_mul(g, RgX_sub(RgX_deriv(f), RgXn_mul(f,q,n-1)),n-1));
    2220                 :          0 :     f = RgX_add(f, RgXn_mul(f, RgX_sub(RgXn_red_shallow(h, n), RgX_integ(w)), n));
    2221         [ #  # ]:          0 :     if (gc_needed(av2,2))
    2222                 :            :     {
    2223         [ #  # ]:          0 :       if(DEBUGMEM>1) pari_warn(warnmem,"RgXn_exp, e = %ld", n);
    2224                 :          0 :       gerepileall(av2, 2, &f, &g);
    2225                 :            :     }
    2226                 :            :   }
    2227                 :          0 :   return gerepileupto(av, f);
    2228                 :            : }
    2229                 :            : 
    2230                 :            : GEN
    2231                 :         84 : RgXn_reverse(GEN f, long e)
    2232                 :            : {
    2233                 :         84 :   pari_sp av = avma, av2;
    2234                 :            :   ulong mask;
    2235                 :            :   GEN fi, a, df, W, an;
    2236                 :         84 :   long v = varn(f), n=1;
    2237 [ +  - ][ -  + ]:         84 :   if (degpol(f)<1 || !gequal0(gel(f,2)))
    2238                 :          0 :     pari_err_INV("serreverse",f);
    2239                 :         84 :   fi = ginv(gel(f,3));
    2240                 :         84 :   a = deg1pol_shallow(fi,gen_0,v);
    2241         [ -  + ]:         84 :   if (e <= 2) return gerepilecopy(av, a);
    2242                 :         84 :   W = scalarpol(fi,v);
    2243                 :         84 :   df = RgX_deriv(f);
    2244                 :         84 :   mask = quadratic_prec_mask(e);
    2245                 :         84 :   av2 = avma;
    2246         [ +  + ]:        420 :   for (;mask>1;)
    2247                 :            :   {
    2248                 :            :     GEN u, fa, fr;
    2249                 :        336 :     long n2 = n, rt;
    2250         [ +  + ]:        336 :     n<<=1; if (mask & 1) n--;
    2251                 :        336 :     mask >>= 1;
    2252                 :        336 :     fr = RgXn_red_shallow(f, n);
    2253                 :        336 :     rt = brent_kung_optpow(degpol(fr), 4, 3);
    2254                 :        336 :     an = RgXn_powers(a, rt, n);
    2255         [ +  - ]:        336 :     if (n>1)
    2256                 :            :     {
    2257                 :        336 :       long n4 = (n2+1)>>1;
    2258                 :        336 :       GEN dfr = RgXn_red_shallow(df, n2);
    2259                 :        336 :       dfr = RgX_RgXnV_eval(dfr, RgXnV_red_shallow(an, n2), n2);
    2260                 :        336 :       u = RgX_shift(RgX_Rg_sub(RgXn_mul(W, dfr, n2), gen_1), -n4);
    2261                 :        336 :       W = RgX_sub(W, RgX_shift(RgXn_mul(u, W, n2-n4), n4));
    2262                 :            :     }
    2263                 :        336 :     fa = RgX_sub(RgX_RgXnV_eval(fr, an, n), pol_x(v));
    2264                 :        336 :     fa = RgX_shift(fa, -n2);
    2265                 :        336 :     a = RgX_sub(a, RgX_shift(RgXn_mul(W, fa, n-n2), n2));
    2266         [ -  + ]:        336 :     if (gc_needed(av2,2))
    2267                 :            :     {
    2268         [ #  # ]:          0 :       if(DEBUGMEM>1) pari_warn(warnmem,"RgXn_reverse, e = %ld", n);
    2269                 :          0 :       gerepileall(av2, 2, &a, &W);
    2270                 :            :     }
    2271                 :            :   }
    2272                 :         84 :   return gerepileupto(av, a);
    2273                 :            : }
    2274                 :            : 
    2275                 :            : /* x,T in Rg[X], n in N, compute lift(x^n mod T)) */
    2276                 :            : GEN
    2277                 :     184120 : RgXQ_powu(GEN x, ulong n, GEN T)
    2278                 :            : {
    2279                 :            :   pari_sp av;
    2280                 :            :   GEN y;
    2281                 :            : 
    2282         [ +  + ]:     184120 :   if (!n) return pol_1(varn(x));
    2283         [ +  + ]:     182671 :   if (n == 1) return RgX_copy(x);
    2284                 :     124921 :   av = avma;
    2285                 :     124921 :   y = gen_powu(x, n, (void*)T, &_sqr, &_mul);
    2286                 :     184120 :   return gerepileupto(av, y);
    2287                 :            : }
    2288                 :            : /* x,T in Rg[X], n in N, compute lift(x^n mod T)) */
    2289                 :            : GEN
    2290                 :       3130 : RgXQ_pow(GEN x, GEN n, GEN T)
    2291                 :            : {
    2292                 :            :   pari_sp av;
    2293                 :       3130 :   long s = signe(n);
    2294                 :            :   GEN y;
    2295                 :            : 
    2296         [ -  + ]:       3130 :   if (!s) return pol_1(varn(x));
    2297         [ +  + ]:       3130 :   if (is_pm1(n) == 1)
    2298         [ +  - ]:          7 :     return (s < 0)? RgXQ_inv(x, T): RgX_copy(x);
    2299                 :       3123 :   av = avma;
    2300         [ +  + ]:       3123 :   if (s < 0) x = RgXQ_inv(x, T);
    2301                 :       3123 :   y = gen_pow(x, n, (void*)T, &_sqr, &_mul);
    2302                 :       3130 :   return gerepileupto(av, y);
    2303                 :            : }
    2304                 :            : 
    2305                 :            : /* generates the list of powers of x of degree 0,1,2,...,l*/
    2306                 :            : GEN
    2307                 :       1659 : RgXQ_powers(GEN x, long l, GEN T)
    2308                 :            : {
    2309                 :       1659 :   int use_sqr = 2*degpol(x) >= degpol(T);
    2310                 :       1659 :   return gen_powers(x, l, use_sqr, (void *)T,_sqr,_mul,_one);
    2311                 :            : }
    2312                 :            : 
    2313                 :            : /* a in K = Q[X]/(T), returns [a^0, ..., a^n] */
    2314                 :            : GEN
    2315                 :       1351 : QXQ_powers(GEN a, long n, GEN T)
    2316                 :            : {
    2317                 :       1351 :   GEN den, v = RgXQ_powers(Q_remove_denom(a, &den), n, T);
    2318                 :            :   /* den*a integral; v[i+1] = (den*a)^i in K */
    2319         [ +  + ]:       1351 :   if (den)
    2320                 :            :   { /* restore denominators */
    2321                 :        840 :     GEN d = den;
    2322                 :            :     long i;
    2323                 :        840 :     gel(v,2) = a;
    2324         [ +  + ]:       3276 :     for (i=3; i<=n+1; i++) {
    2325                 :       2436 :       d = mulii(d,den);
    2326                 :       2436 :       gel(v,i) = RgX_Rg_div(gel(v,i), d);
    2327                 :            :     }
    2328                 :            :   }
    2329                 :       1351 :   return v;
    2330                 :            : }
    2331                 :            : 
    2332                 :            : static GEN
    2333                 :        777 : do_QXQ_eval(GEN v, long imin, GEN a, GEN T)
    2334                 :            : {
    2335                 :        777 :   long l, i, m = 0;
    2336                 :            :   GEN dz, z;
    2337                 :        777 :   GEN V = cgetg_copy(v, &l);
    2338         [ +  + ]:       2506 :   for (i = imin; i < l; i++)
    2339                 :            :   {
    2340                 :       1729 :     GEN c = gel(v, i);
    2341         [ +  + ]:       1729 :     if (typ(c) == t_POL) m = maxss(m, degpol(c));
    2342                 :            :   }
    2343                 :        777 :   z = Q_remove_denom(QXQ_powers(a, m, T), &dz);
    2344         [ +  + ]:        819 :   for (i = 1; i < imin; i++) V[i] = v[i];
    2345         [ +  + ]:       2506 :   for (i = imin; i < l; i++)
    2346                 :            :   {
    2347                 :       1729 :     GEN c = gel(v,i);
    2348         [ +  + ]:       1729 :     if (typ(c) == t_POL) c = QX_ZXQV_eval(c, z, dz);
    2349                 :       1729 :     gel(V,i) = c;
    2350                 :            :   }
    2351                 :        777 :   return V;
    2352                 :            : }
    2353                 :            : /* [ s(a mod T) | s <- lift(v) ], a,T are QX, v a QXV */
    2354                 :            : GEN
    2355                 :        735 : QXV_QXQ_eval(GEN v, GEN a, GEN T)
    2356                 :        735 : { return do_QXQ_eval(v, 1, a, T); }
    2357                 :            : GEN
    2358                 :         42 : QXX_QXQ_eval(GEN v, GEN a, GEN T)
    2359                 :         42 : { return normalizepol(do_QXQ_eval(v, 2, a, T)); }
    2360                 :            : 
    2361                 :            : GEN
    2362                 :        287 : RgXQ_matrix_pow(GEN y, long n, long m, GEN P)
    2363                 :            : {
    2364                 :        287 :   return RgXV_to_RgM(RgXQ_powers(y,m-1,P),n);
    2365                 :            : }
    2366                 :            : 
    2367                 :            : GEN
    2368                 :         56 : RgXQ_minpoly_naive(GEN y, GEN P)
    2369                 :            : {
    2370                 :         56 :   pari_sp ltop=avma;
    2371                 :         56 :   long n=lgpol(P);
    2372                 :         56 :   GEN M=ker(RgXQ_matrix_pow(y,n,n,P));
    2373                 :         56 :   M=content(RgM_to_RgXV(M,varn(P)));
    2374                 :         56 :   return gerepileupto(ltop,M);
    2375                 :            : }
    2376                 :            : 
    2377                 :            : GEN
    2378                 :      23925 : RgXQ_norm(GEN x, GEN T)
    2379                 :            : {
    2380                 :            :   pari_sp av;
    2381                 :      23925 :   long dx = degpol(x);
    2382                 :            :   GEN L, y;
    2383                 :            : 
    2384                 :      23925 :   av = avma; y = resultant(T, x);
    2385                 :      23925 :   L = leading_coeff(T);
    2386 [ +  + ][ +  - ]:      23925 :   if (gequal1(L) || !signe(x)) return y;
    2387                 :      23925 :   return gerepileupto(av, gdiv(y, gpowgs(L, dx)));
    2388                 :            : }
    2389                 :            : 
    2390                 :            : GEN
    2391                 :      69664 : RgX_blocks(GEN P, long n, long m)
    2392                 :            : {
    2393                 :      69664 :   GEN z = cgetg(m+1,t_VEC);
    2394                 :      69664 :   long i,j, k=2, l = lg(P);
    2395         [ +  + ]:     400708 :   for(i=1; i<=m; i++)
    2396                 :            :   {
    2397                 :     331044 :     GEN zi = cgetg(n+2,t_POL);
    2398                 :     331044 :     zi[1] = P[1];
    2399                 :     331044 :     gel(z,i) = zi;
    2400         [ +  + ]:    2012857 :     for(j=2; j<n+2; j++)
    2401         [ +  + ]:    1681813 :       gel(zi, j) = k==l ? gen_0 : gel(P,k++);
    2402                 :     331044 :     zi = ZX_renormalize(zi, n+2);
    2403                 :            :   }
    2404                 :      69664 :   return z;
    2405                 :            : }
    2406                 :            : 
    2407                 :            : /* write p(X) = e(X^2) + Xo(X^2), shallow function */
    2408                 :            : void
    2409                 :      22279 : RgX_even_odd(GEN p, GEN *pe, GEN *po)
    2410                 :            : {
    2411                 :      22279 :   long n = degpol(p), v = varn(p), n0, n1, i;
    2412                 :            :   GEN p0, p1;
    2413                 :            : 
    2414         [ -  + ]:      44563 :   if (n <= 0) { *pe = RgX_copy(p); *po = zeropol(v); return; }
    2415                 :            : 
    2416                 :      22280 :   n0 = (n>>1)+1; n1 = n+1 - n0; /* n1 <= n0 <= n1+1 */
    2417                 :      22280 :   p0 = cgetg(n0+2, t_POL); p0[1] = evalvarn(v)|evalsigne(1);
    2418                 :      22281 :   p1 = cgetg(n1+2, t_POL); p1[1] = evalvarn(v)|evalsigne(1);
    2419         [ +  + ]:     533615 :   for (i=0; i<n1; i++)
    2420                 :            :   {
    2421                 :     511332 :     p0[2+i] = p[2+(i<<1)];
    2422                 :     511332 :     p1[2+i] = p[3+(i<<1)];
    2423                 :            :   }
    2424         [ +  + ]:      22283 :   if (n1 != n0)
    2425                 :      15862 :     p0[2+i] = p[2+(i<<1)];
    2426                 :      22283 :   *pe = normalizepol(p0);
    2427                 :      22281 :   *po = normalizepol(p1);
    2428                 :            : }
    2429                 :            : 
    2430                 :            : /* write p(X) = a_0(X^k) + Xa_1(X^k) + ... + X^(k-1)a_{k-1}(X^k), shallow function */
    2431                 :            : GEN
    2432                 :      40390 : RgX_splitting(GEN p, long k)
    2433                 :            : {
    2434                 :      40390 :   long n = degpol(p), v = varn(p), m, i, j, l;
    2435                 :            :   GEN r;
    2436                 :            : 
    2437                 :      40390 :   m = n/k;
    2438                 :      40390 :   r = cgetg(k+1,t_VEC);
    2439         [ +  + ]:     222530 :   for(i=1; i<=k; i++)
    2440                 :            :   {
    2441                 :     182140 :     gel(r,i) = cgetg(m+3, t_POL);
    2442                 :     182140 :     mael(r,i,1) = evalvarn(v)|evalsigne(1);
    2443                 :            :   }
    2444         [ +  + ]:     537124 :   for (j=1, i=0, l=2; i<=n; i++)
    2445                 :            :   {
    2446                 :     496734 :     gmael(r,j,l) = gel(p,2+i);
    2447         [ +  + ]:     496734 :     if (j==k) { j=1; l++; } else j++;
    2448                 :            :   }
    2449         [ +  + ]:     222530 :   for(i=1; i<=k; i++)
    2450         [ +  + ]:     182140 :     gel(r,i) = normalizepol_lg(gel(r,i),i<j?l+1:l);
    2451                 :      40390 :   return r;
    2452                 :            : }
    2453                 :            : 
    2454                 :            : /*******************************************************************/
    2455                 :            : /*                                                                 */
    2456                 :            : /*                        Kronecker form                           */
    2457                 :            : /*                                                                 */
    2458                 :            : /*******************************************************************/
    2459                 :            : 
    2460                 :            : /* z in R[Y] representing an elt in R[X,Y] mod T(Y) in Kronecker form,
    2461                 :            :  * i.e subst(lift(z), x, y^(2deg(z)-1)). Recover the "real" z, with
    2462                 :            :  * normalized coefficients */
    2463                 :            : GEN
    2464                 :        189 : Kronecker_to_mod(GEN z, GEN T)
    2465                 :            : {
    2466                 :        189 :   long i,j,lx,l = lg(z), N = (degpol(T)<<1) + 1;
    2467                 :        189 :   GEN x, t = cgetg(N,t_POL);
    2468                 :        189 :   t[1] = T[1];
    2469                 :        189 :   lx = (l-2) / (N-2); x = cgetg(lx+3,t_POL);
    2470                 :        189 :   x[1] = z[1];
    2471                 :        189 :   T = RgX_copy(T);
    2472         [ +  + ]:       4389 :   for (i=2; i<lx+2; i++, z+= N-2)
    2473                 :            :   {
    2474         [ +  + ]:      25200 :     for (j=2; j<N; j++) gel(t,j) = gel(z,j);
    2475                 :       4200 :     gel(x,i) = mkpolmod(RgX_rem(normalizepol_lg(t,N), T), T);
    2476                 :            :   }
    2477                 :        189 :   N = (l-2) % (N-2) + 2;
    2478         [ +  + ]:        378 :   for (j=2; j<N; j++) t[j] = z[j];
    2479                 :        189 :   gel(x,i) = mkpolmod(RgX_rem(normalizepol_lg(t,N), T), T);
    2480                 :        189 :   return normalizepol_lg(x, i+1);
    2481                 :            : }

Generated by: LCOV version 1.9