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.10.0 lcov report (development 20422-b487f4d) Lines: 1287 1395 92.3 %
Date: 2017-03-22 05:51:54 Functions: 141 152 92.8 %
Legend: Lines: hit not hit

          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     1962386 : brent_kung_optpow(long d, long n, long m)
      29             : {
      30             :   long p, r;
      31     1962386 :   long pold=1, rold=n*(d-1);
      32    11867524 :   for(p=2; p<=d; p++)
      33             :   {
      34     9905138 :     r = m*(p-1) + n*((d-1)/p);
      35     9905138 :     if (r<rold) { pold=p; rold=r; }
      36             :   }
      37     1962386 :   return pold;
      38             : }
      39             : 
      40             : static GEN
      41     9415314 : 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     9415314 :   pari_sp av = avma;
      45             :   long i;
      46     9415314 :   GEN z = cmul(E,P,a,ff->one(E));
      47     9415254 :   if (!z) z = gen_0;
      48    59233196 :   for (i=1; i<=n; i++)
      49             :   {
      50    49817884 :     GEN t = cmul(E,P,a+i,gel(V,i+1));
      51    49818269 :     if (t) {
      52    48563115 :       z = ff->add(E, z, t);
      53    48562473 :       if (gc_needed(av,2)) z = gerepileupto(av, z);
      54             :     }
      55             :   }
      56     9415312 :   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     6019663 : 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     6019663 :   pari_sp av = avma;
      69     6019663 :   long l = lg(V)-1;
      70             :   GEN z, u;
      71             : 
      72     6019663 :   if (d < 0) return ff->zero(E);
      73     5532200 :   if (d < l) return gerepileupto(av, gen_RgXQ_eval_powers(P,V,0,d,E,ff,cmul));
      74     2330702 :   if (l<2) pari_err_DOMAIN("gen_RgX_bkeval_powers", "#powers", "<",gen_2,V);
      75     2330702 :   d -= l;
      76     2330702 :   z = gen_RgXQ_eval_powers(P,V,d+1,l-1,E,ff,cmul);
      77     6213818 :   while (d >= l-1)
      78             :   {
      79     1552421 :     d -= l-1;
      80     1552421 :     u = gen_RgXQ_eval_powers(P,V,d+1,l-2,E,ff,cmul);
      81     1552392 :     z = ff->add(E,u, ff->mul(E,z,gel(V,l)));
      82     1552406 :     if (gc_needed(av,2))
      83          61 :       z = gerepileupto(av, z);
      84             :   }
      85     2330698 :   u = gen_RgXQ_eval_powers(P,V,0,d,E,ff,cmul);
      86     2330698 :   z = ff->add(E,u, ff->mul(E,z,gel(V,d+2)));
      87     2330701 :   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     2330701 :   return gerepileupto(av, ff->red(E,z));
      93             : }
      94             : 
      95             : GEN
      96     1030224 : 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     1030224 :   pari_sp av = avma;
     100             :   GEN z, V;
     101             :   long rtd;
     102     1030224 :   if (d < 0) return ff->zero(E);
     103     1030119 :   rtd = (long) sqrt((double)d);
     104     1030119 :   V = gen_powers(x,rtd,use_sqr,E,ff->sqr,ff->mul,ff->one);
     105     1030115 :   z = gen_bkeval_powers(Q, d, V, E, ff, cmul);
     106     1030117 :   return gerepileupto(av, z);
     107             : }
     108             : 
     109             : static GEN
     110      537155 : _gen_nored(void *E, GEN x) { (void)E; return x; }
     111             : static GEN
     112    20244179 : _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      540605 : _gen_mul(void *E, GEN x, GEN y) { (void)E; return gmul(x, y); }
     117             : static GEN
     118      173693 : _gen_sqr(void *E, GEN x) { (void)E; return gsqr(x); }
     119             : static GEN
     120      547389 : _gen_one(void *E) { (void)E; return gen_1; }
     121             : static GEN
     122         168 : _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       31787 : _gen_cmul(void *E, GEN P, long a, GEN x)
     129       31787 : {(void)E; return gmul(gel(P,a+2), x);}
     130             : 
     131             : GEN
     132       10073 : RgX_RgV_eval(GEN Q, GEN x)
     133             : {
     134       10073 :   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         203 : RgXV_RgV_eval(GEN Q, GEN x)
     145             : {
     146         203 :   long i, l = lg(Q), vQ = gvar(Q);
     147         203 :   GEN v = cgetg(l, t_VEC);
     148       24675 :   for (i = 1; i < l; i++)
     149             :   {
     150       24472 :     GEN Qi = gel(Q, i);
     151       24472 :     gel(v, i) = typ(Qi)==t_POL && varn(Qi)==vQ? RgX_RgV_eval(Qi, x): gcopy(Qi);
     152             :   }
     153         203 :   return v;
     154             : }
     155             : 
     156             : const struct bb_algebra *
     157       70970 : get_Rg_algebra(void)
     158             : {
     159       70970 :   return &Rg_algebra;
     160             : }
     161             : 
     162             : /*******************************************************************/
     163             : /*                                                                 */
     164             : /*                         RgX                                     */
     165             : /*                                                                 */
     166             : /*******************************************************************/
     167             : 
     168             : long
     169     3981929 : RgX_equal(GEN x, GEN y)
     170             : {
     171     3981929 :   long i = lg(x);
     172             : 
     173     3981929 :   if (i != lg(y)) return 0;
     174    20554007 :   for (i--; i > 1; i--)
     175    16633034 :     if (!gequal(gel(x,i),gel(y,i))) return 0;
     176     3920973 :   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      568657 : RgX_get_1(GEN x)
     183             : {
     184             :   GEN p, T;
     185      568657 :   long i, lx, tx = RgX_type(x, &p, &T, &lx);
     186      568657 :   if (RgX_type_is_composite(tx))
     187        1211 :     RgX_type_decode(tx, &i /*junk*/, &tx);
     188      568657 :   switch(tx)
     189             :   {
     190          49 :     case t_INTMOD: retmkintmod(gen_1, icopy(p));
     191           7 :     case t_PADIC: return cvtop(gen_1, p, lx);
     192          14 :     case t_FFELT: return FF_1(T);
     193      568587 :     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      128107 : RgX_get_0(GEN x)
     200             : {
     201             :   GEN p, T;
     202      128107 :   long i, lx, tx = RgX_type(x, &p, &T, &lx);
     203      128107 :   if (RgX_type_is_composite(tx))
     204       13433 :     RgX_type_decode(tx, &i /*junk*/, &tx);
     205      128107 :   switch(tx)
     206             :   {
     207         245 :     case t_INTMOD: retmkintmod(gen_0, icopy(p));
     208           0 :     case t_PADIC: return cvtop(gen_0, p, lx);
     209         210 :     case t_FFELT: return FF_zero(T);
     210      127652 :     default: return gen_0;
     211             :   }
     212             : }
     213             : 
     214             : GEN
     215        1750 : QX_ZXQV_eval(GEN P, GEN V, GEN dV)
     216             : {
     217        1750 :   long i, n = degpol(P);
     218             :   GEN z, dz, dP;
     219        1750 :   if (n < 0) return gen_0;
     220        1750 :   P = Q_remove_denom(P, &dP);
     221        1750 :   z = gel(P,2); if (n == 0) return icopy(z);
     222         966 :   if (dV) z = mulii(dV, z); /* V[1] = dV */
     223         966 :   z = ZX_Z_add_shallow(ZX_Z_mul(gel(V,2),gel(P,3)), z);
     224         966 :   for (i=2; i<=n; i++) z = ZX_add(ZX_Z_mul(gel(V,i+1),gel(P,2+i)), z);
     225         966 :   dz = mul_denom(dP, dV);
     226         966 :   return dz? RgX_Rg_div(z, dz): z;
     227             : }
     228             : 
     229             : /* Return P(h * x), not memory clean */
     230             : GEN
     231        3353 : RgX_unscale(GEN P, GEN h)
     232             : {
     233        3353 :   long i, l = lg(P);
     234        3353 :   GEN hi = gen_1, Q = cgetg(l, t_POL);
     235        3353 :   Q[1] = P[1];
     236        3353 :   if (l == 2) return Q;
     237        3353 :   gel(Q,2) = gcopy(gel(P,2));
     238        8596 :   for (i=3; i<l; i++)
     239             :   {
     240        5243 :     hi = gmul(hi,h);
     241        5243 :     gel(Q,i) = gmul(gel(P,i), hi);
     242             :   }
     243        3353 :   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       15092 : ZX_unscale(GEN P, GEN h)
     248             : {
     249       15092 :   long i, l = lg(P);
     250       15092 :   GEN Q = cgetg(l, t_POL);
     251       15092 :   Q[1] = P[1];
     252       15092 :   if (l == 2) return Q;
     253       15092 :   gel(Q,2) = gel(P,2);
     254       15092 :   if (l == 3) return Q;
     255       15092 :   if (equalim1(h))
     256      297220 :     for (i=3; i<l; i++)
     257             :     {
     258      293110 :       gel(Q,i) = negi(gel(P,i));
     259      293110 :       if (++i == l) break;
     260      290458 :       gel(Q,i) = gel(P,i);
     261             :     }
     262             :   else
     263             :   {
     264        8330 :     GEN hi = h;
     265        8330 :     gel(Q,3) = mulii(gel(P,3), hi);
     266       48321 :     for (i=4; i<l; i++)
     267             :     {
     268       39991 :       hi = mulii(hi,h);
     269       39991 :       gel(Q,i) = mulii(gel(P,i), hi);
     270             :     }
     271             :   }
     272       15092 :   return Q;
     273             : }
     274             : /* P a ZX. Return P(x << n), not memory clean */
     275             : GEN
     276        9740 : ZX_unscale2n(GEN P, long n)
     277             : {
     278        9740 :   long i, ni = n, l = lg(P);
     279        9740 :   GEN Q = cgetg(l, t_POL);
     280        9740 :   Q[1] = P[1];
     281        9740 :   if (l == 2) return Q;
     282        9740 :   gel(Q,2) = gel(P,2);
     283        9740 :   if (l == 3) return Q;
     284        9740 :   gel(Q,3) = shifti(gel(P,3), ni);
     285       49074 :   for (i=4; i<l; i++)
     286             :   {
     287       39334 :     ni += n;
     288       39334 :     gel(Q,i) = shifti(gel(P,i), ni);
     289             :   }
     290        9740 :   return Q;
     291             : }
     292             : /* P(h*X) / h, assuming h | P(0), i.e. the result is a ZX */
     293             : GEN
     294         161 : ZX_unscale_div(GEN P, GEN h)
     295             : {
     296         161 :   long i, l = lg(P);
     297         161 :   GEN hi, Q = cgetg(l, t_POL);
     298         161 :   Q[1] = P[1];
     299         161 :   if (l == 2) return Q;
     300         161 :   gel(Q,2) = diviiexact(gel(P,2), h);
     301         161 :   if (l == 3) return Q;
     302         161 :   gel(Q,3) = gel(P,3);
     303         161 :   if (l == 4) return Q;
     304         161 :   hi = h;
     305         161 :   gel(Q,4) = mulii(gel(P,4), hi);
     306         504 :   for (i=5; i<l; i++)
     307             :   {
     308         343 :     hi = mulii(hi,h);
     309         343 :     gel(Q,i) = mulii(gel(P,i), hi);
     310             :   }
     311         161 :   return Q;
     312             : }
     313             : 
     314             : GEN
     315         203 : RgXV_unscale(GEN v, GEN h)
     316             : {
     317             :   long i, l;
     318             :   GEN w;
     319         203 :   if (!h || isint1(h)) return v;
     320         147 :   w = cgetg_copy(v, &l);
     321         147 :   for (i=1; i<l; i++) gel(w,i) = RgX_unscale(gel(v,i), h);
     322         147 :   return w;
     323             : }
     324             : 
     325             : /* Return h^degpol(P) P(x / h), not memory clean */
     326             : GEN
     327        1099 : RgX_rescale(GEN P, GEN h)
     328             : {
     329        1099 :   long i, l = lg(P);
     330        1099 :   GEN Q = cgetg(l,t_POL), hi = h;
     331        1099 :   Q[l-1] = P[l-1];
     332        6909 :   for (i=l-2; i>=2; i--)
     333             :   {
     334        6909 :     gel(Q,i) = gmul(gel(P,i), hi);
     335        6909 :     if (i == 2) break;
     336        5810 :     hi = gmul(hi,h);
     337             :   }
     338        1099 :   Q[1] = P[1]; return Q;
     339             : }
     340             : 
     341             : /* A(X^d) --> A(X) */
     342             : GEN
     343       74028 : RgX_deflate(GEN x0, long d)
     344             : {
     345             :   GEN z, y, x;
     346       74028 :   long i,id, dy, dx = degpol(x0);
     347       74028 :   if (d == 1 || dx <= 0) return leafcopy(x0);
     348       50123 :   dy = dx/d;
     349       50123 :   y = cgetg(dy+3, t_POL); y[1] = x0[1];
     350       50123 :   z = y + 2;
     351       50123 :   x = x0+ 2;
     352       50123 :   for (i=id=0; i<=dy; i++,id+=d) gel(z,i) = gel(x,id);
     353       50123 :   return y;
     354             : }
     355             : 
     356             : /* return x0(X^d) */
     357             : GEN
     358      108261 : RgX_inflate(GEN x0, long d)
     359             : {
     360      108261 :   long i, id, dy, dx = degpol(x0);
     361      108261 :   GEN x = x0 + 2, z, y;
     362      108261 :   if (dx <= 0) return leafcopy(x0);
     363      107659 :   dy = dx*d;
     364      107659 :   y = cgetg(dy+3, t_POL); y[1] = x0[1];
     365      107660 :   z = y + 2;
     366      107660 :   for (i=0; i<=dy; i++) gel(z,i) = gen_0;
     367      107660 :   for (i=id=0; i<=dx; i++,id+=d) gel(z,id) = gel(x,i);
     368      107660 :   return y;
     369             : }
     370             : 
     371             : /* return P(X + c) using destructive Horner, optimize for c = 1,-1 */
     372             : GEN
     373     1009092 : RgX_translate(GEN P, GEN c)
     374             : {
     375     1009092 :   pari_sp av = avma;
     376             :   GEN Q, *R;
     377             :   long i, k, n;
     378             : 
     379     1009092 :   if (!signe(P) || gequal0(c)) return RgX_copy(P);
     380     1006172 :   Q = leafcopy(P);
     381     1006172 :   R = (GEN*)(Q+2); n = degpol(P);
     382     1006172 :   if (gequal1(c))
     383             :   {
     384        2072 :     for (i=1; i<=n; i++)
     385             :     {
     386        1799 :       for (k=n-i; k<n; k++) R[k] = gadd(R[k], R[k+1]);
     387        1799 :       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     1005899 :   else if (gequalm1(c))
     395             :   {
     396      133679 :     for (i=1; i<=n; i++)
     397             :     {
     398      114478 :       for (k=n-i; k<n; k++) R[k] = gsub(R[k], R[k+1]);
     399      114478 :       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     3361141 :     for (i=1; i<=n; i++)
     409             :     {
     410     2374443 :       for (k=n-i; k<n; k++) R[k] = gadd(R[k], gmul(c, R[k+1]));
     411     2374443 :       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     1006172 :   return gerepilecopy(av, Q);
     419             : }
     420             : 
     421             : /* return P(X + c) using destructive Horner, optimize for c = 1,-1 */
     422             : GEN
     423      366270 : ZX_translate(GEN P, GEN c)
     424             : {
     425      366270 :   pari_sp av = avma;
     426             :   GEN Q, *R;
     427             :   long i, k, n;
     428             : 
     429      366270 :   if (!signe(P) || !signe(c)) return ZX_copy(P);
     430      366235 :   Q = leafcopy(P);
     431      366235 :   R = (GEN*)(Q+2); n = degpol(P);
     432      366235 :   if (equali1(c))
     433             :   {
     434     2276787 :     for (i=1; i<=n; i++)
     435             :     {
     436     2011536 :       for (k=n-i; k<n; k++) R[k] = addii(R[k], R[k+1]);
     437     2011536 :       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      100984 :   else if (equalim1(c))
     445             :   {
     446          70 :     for (i=1; i<=n; i++)
     447             :     {
     448          49 :       for (k=n-i; k<n; k++) R[k] = subii(R[k], R[k+1]);
     449          49 :       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      746292 :     for (i=1; i<=n; i++)
     459             :     {
     460      645329 :       for (k=n-i; k<n; k++) R[k] = addii(R[k], mulii(c, R[k+1]));
     461      645329 :       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      366235 :   return gerepilecopy(av, Q);
     469             : }
     470             : /* return lift( P(X + c) ) using Horner, c in R[y]/(T) */
     471             : GEN
     472        6048 : RgXQX_translate(GEN P, GEN c, GEN T)
     473             : {
     474        6048 :   pari_sp av = avma;
     475             :   GEN Q, *R;
     476             :   long i, k, n;
     477             : 
     478        6048 :   if (!signe(P) || gequal0(c)) return RgX_copy(P);
     479        6027 :   Q = leafcopy(P);
     480        6027 :   R = (GEN*)(Q+2); n = degpol(P);
     481       34608 :   for (i=1; i<=n; i++)
     482             :   {
     483      141106 :     for (k=n-i; k<n; k++)
     484             :     {
     485      112525 :       pari_sp av2 = avma;
     486      112525 :       R[k] = gerepileupto(av2, RgX_rem(gadd(R[k], gmul(c, R[k+1])), T));
     487             :     }
     488       28581 :     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        6027 :   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       14417 : QXQ_to_mod_copy(GEN x, GEN T)
     507             : {
     508             :   long d;
     509       14417 :   switch(typ(x))
     510             :   {
     511        5124 :     case t_INT:  return icopy(x);
     512         371 :     case t_FRAC: return gcopy(x);
     513             :     case t_POL:
     514        8922 :       d = degpol(x);
     515        8922 :       if (d < 0) return gen_0;
     516        8649 :       if (d == 0) return gcopy(gel(x,2));
     517        8334 :       return mkpolmod(RgX_copy(x), T);
     518           0 :     default: pari_err_TYPE("QXQ_to_mod",x);
     519             :              return NULL;/* LCOV_EXCL_LINE */
     520             :   }
     521             : }
     522             : /* pure shallow version */
     523             : static GEN
     524      408321 : QXQ_to_mod(GEN x, GEN T)
     525             : {
     526             :   long d;
     527      408321 :   switch(typ(x))
     528             :   {
     529             :     case t_INT:
     530      355201 :     case t_FRAC: return x;
     531             :     case t_POL:
     532       53120 :       d = degpol(x);
     533       53120 :       if (d < 0) return gen_0;
     534       48888 :       if (d == 0) return gel(x,2);
     535       45031 :       return mkpolmod(x, T);
     536           0 :     default: pari_err_TYPE("QXQ_to_mod",x);
     537             :              return NULL;/* LCOV_EXCL_LINE */
     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        1918 : QXQX_to_mod(GEN z, GEN T)
     544             : {
     545        1918 :   long i,l = lg(z);
     546        1918 :   GEN x = cgetg(l,t_POL);
     547        1918 :   for (i=2; i<l; i++) gel(x,i) = QXQ_to_mod_copy(gel(z,i), T);
     548        1918 :   x[1] = z[1]; return normalizepol_lg(x,l);
     549             : }
     550             : /* pure shallow version */
     551             : GEN
     552       83111 : QXQX_to_mod_shallow(GEN z, GEN T)
     553             : {
     554       83111 :   long i,l = lg(z);
     555       83111 :   GEN x = cgetg(l,t_POL);
     556       83111 :   for (i=2; i<l; i++) gel(x,i) = QXQ_to_mod(gel(z,i), T);
     557       83111 :   x[1] = z[1]; return normalizepol_lg(x,l);
     558             : }
     559             : /* Apply QXQX_to_mod to all entries. Memory-clean ! */
     560             : GEN
     561         539 : QXQXV_to_mod(GEN V, GEN T)
     562             : {
     563         539 :   long i, l = lg(V);
     564         539 :   GEN z = cgetg(l, t_VEC); T = ZX_copy(T);
     565         539 :   for (i=1;i<l; i++) gel(z,i) = QXQX_to_mod(gel(V,i), T);
     566         539 :   return z;
     567             : }
     568             : /* Apply QXQ_to_mod_copy to all entries. Memory-clean ! */
     569             : GEN
     570        1079 : QXQV_to_mod(GEN V, GEN T)
     571             : {
     572        1079 :   long i, l = lg(V);
     573        1079 :   GEN z = cgetg(l, t_VEC); T = ZX_copy(T);
     574        1079 :   for (i=1;i<l; i++) gel(z,i) = QXQ_to_mod_copy(gel(V,i), T);
     575        1079 :   return z;
     576             : }
     577             : 
     578             : GEN
     579      692690 : RgX_renormalize_lg(GEN x, long lx)
     580             : {
     581             :   long i;
     582     1935751 :   for (i = lx-1; i>1; i--)
     583     1827454 :     if (! gequal0(gel(x,i))) break; /* _not_ isexactzero */
     584      692690 :   stackdummy((pari_sp)(x + lg(x)), (pari_sp)(x + i+1));
     585      692690 :   setlg(x, i+1); setsigne(x, i != 1); return x;
     586             : }
     587             : 
     588             : GEN
     589      357433 : RgV_to_RgX(GEN x, long v)
     590             : {
     591      357433 :   long i, k = lg(x);
     592             :   GEN p;
     593             : 
     594      357433 :   while (--k && gequal0(gel(x,k)));
     595      357433 :   if (!k) return pol_0(v);
     596      357055 :   i = k+2; p = cgetg(i,t_POL);
     597      357055 :   p[1] = evalsigne(1) | evalvarn(v);
     598      357055 :   x--; for (k=2; k<i; k++) gel(p,k) = gel(x,k);
     599      357055 :   return p;
     600             : }
     601             : GEN
     602      149566 : RgV_to_RgX_reverse(GEN x, long v)
     603             : {
     604      149566 :   long j, k, l = lg(x);
     605             :   GEN p;
     606             : 
     607      149566 :   for (k = 1; k < l; k++)
     608      149566 :     if (!gequal0(gel(x,k))) break;
     609      149566 :   if (k == l) return pol_0(v);
     610      149566 :   k -= 1;
     611      149566 :   l -= k;
     612      149566 :   x += k;
     613      149566 :   p = cgetg(l+1,t_POL);
     614      149566 :   p[1] = evalsigne(1) | evalvarn(v);
     615      149566 :   for (j=2, k=l; j<=l; j++) gel(p,j) = gel(x,--k);
     616      149566 :   return p;
     617             : }
     618             : 
     619             : /* return the (N-dimensional) vector of coeffs of p */
     620             : GEN
     621     3426043 : RgX_to_RgC(GEN x, long N)
     622             : {
     623             :   long i, l;
     624             :   GEN z;
     625     3426043 :   l = lg(x)-1; x++;
     626     3426043 :   if (l > N+1) l = N+1; /* truncate higher degree terms */
     627     3426043 :   z = cgetg(N+1,t_COL);
     628     3426043 :   for (i=1; i<l ; i++) gel(z,i) = gel(x,i);
     629     3426043 :   for (   ; i<=N; i++) gel(z,i) = gen_0;
     630     3426043 :   return z;
     631             : }
     632             : GEN
     633      127093 : Rg_to_RgC(GEN x, long N)
     634             : {
     635      127093 :   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       35459 : RgM_to_RgXV(GEN x, long v)
     641             : {
     642       35459 :   long j, lx = lg(x);
     643       35459 :   GEN y = cgetg(lx, t_VEC);
     644       35459 :   for (j=1; j<lx; j++) gel(y,j) = RgV_to_RgX(gel(x,j), v);
     645       35459 :   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       25665 : RgV_to_RgM(GEN v, long n)
     652             : {
     653       25665 :   long j, N = lg(v);
     654       25665 :   GEN y = cgetg(N, t_MAT);
     655       25665 :   for (j=1; j<N; j++) gel(y,j) = Rg_to_RgC(gel(v,j), n);
     656       25665 :   return y;
     657             : }
     658             : GEN
     659        1826 : RgXV_to_RgM(GEN v, long n)
     660             : {
     661        1826 :   long j, N = lg(v);
     662        1826 :   GEN y = cgetg(N, t_MAT);
     663        1826 :   for (j=1; j<N; j++) gel(y,j) = RgX_to_RgC(gel(v,j), n);
     664        1826 :   return y;
     665             : }
     666             : 
     667             : /* polynomial (in v) of polynomials (in w) whose coeffs are given by the columns of x */
     668             : GEN
     669       15309 : RgM_to_RgXX(GEN x, long v,long w)
     670             : {
     671       15309 :   long j, lx = lg(x);
     672       15309 :   GEN y = cgetg(lx+1, t_POL);
     673       15309 :   y[1] = evalsigne(1) | evalvarn(v);
     674       15309 :   y++;
     675       15309 :   for (j=1; j<lx; j++) gel(y,j) = RgV_to_RgX(gel(x,j), w);
     676       15309 :   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          21 :   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       12880 : RgXY_swapspec(GEN x, long n, long w, long nx)
     693             : {
     694       12880 :   long j, ly = n+3;
     695       12880 :   GEN y = cgetg(ly, t_POL);
     696       12880 :   y[1] = evalsigne(1);
     697      192509 :   for (j=2; j<ly; j++)
     698             :   {
     699             :     long k;
     700      179629 :     GEN a = cgetg(nx+2,t_POL);
     701      179629 :     a[1] = evalsigne(1) | evalvarn(w);
     702      960386 :     for (k=0; k<nx; k++)
     703             :     {
     704      780757 :       GEN xk = gel(x,k);
     705      780757 :       if (typ(xk)==t_POL)
     706      695252 :         gel(a,k+2) = j<lg(xk)? gel(xk,j): gen_0;
     707             :       else
     708       85505 :         gel(a,k+2) = j==2 ? xk: gen_0;
     709             :     }
     710      179629 :     gel(y,j) = normalizepol_lg(a, nx+2);
     711             :   }
     712       12880 :   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       38110 : RgXn_red_shallow(GEN a, long n)
     740             : {
     741       38110 :   long i, L = n+2, l = lg(a);
     742             :   GEN  b;
     743       38110 :   if (L >= l) return a; /* deg(x) < n */
     744       29122 :   b = cgetg(L, t_POL); b[1] = a[1];
     745       29122 :   for (i=2; i<L; i++) gel(b,i) = gel(a,i);
     746       29122 :   return normalizepol_lg(b,L);
     747             : }
     748             : 
     749             : GEN
     750         336 : RgXnV_red_shallow(GEN P, long n)
     751             : {
     752         336 :   long i, l = lg(P);
     753         336 :   GEN Q = cgetg(l, t_VEC);
     754         336 :   for (i=1; i<l; i++) gel(Q,i) = RgXn_red_shallow(gel(P,i), n);
     755         336 :   return Q;
     756             : }
     757             : 
     758             : /* return (x * X^n). Shallow */
     759             : GEN
     760    55481215 : RgX_shift_shallow(GEN a, long n)
     761             : {
     762    55481215 :   long i, l = lg(a);
     763             :   GEN  b;
     764    55481215 :   if (l == 2 || !n) return a;
     765    41258302 :   l += n;
     766    41258302 :   if (n < 0)
     767             :   {
     768    37223451 :     if (l <= 2) return pol_0(varn(a));
     769    37211103 :     b = cgetg(l, t_POL); b[1] = a[1];
     770    37211103 :     a -= n;
     771    37211103 :     for (i=2; i<l; i++) gel(b,i) = gel(a,i);
     772             :   } else {
     773     4034851 :     b = cgetg(l, t_POL); b[1] = a[1];
     774     4034851 :     a -= n; n += 2;
     775     4034851 :     for (i=2; i<n; i++) gel(b,i) = gen_0;
     776     4034851 :     for (   ; i<l; i++) gel(b,i) = gel(a,i);
     777             :   }
     778    41245954 :   return b;
     779             : }
     780             : /* return (x * X^n). */
     781             : GEN
     782     3393158 : RgX_shift(GEN a, long n)
     783             : {
     784     3393158 :   long i, l = lg(a);
     785             :   GEN  b;
     786     3393158 :   if (l == 2 || !n) return RgX_copy(a);
     787     3392934 :   l += n;
     788     3392934 :   if (n < 0)
     789             :   {
     790         595 :     if (l <= 2) return pol_0(varn(a));
     791         553 :     b = cgetg(l, t_POL); b[1] = a[1];
     792         553 :     a -= n;
     793         553 :     for (i=2; i<l; i++) gel(b,i) = gcopy(gel(a,i));
     794             :   } else {
     795     3392339 :     b = cgetg(l, t_POL); b[1] = a[1];
     796     3392339 :     a -= n; n += 2;
     797     3392339 :     for (i=2; i<n; i++) gel(b,i) = gen_0;
     798     3392339 :     for (   ; i<l; i++) gel(b,i) = gcopy(gel(a,i));
     799             :   }
     800     3392892 :   return b;
     801             : }
     802             : 
     803             : GEN
     804      315777 : RgX_rotate_shallow(GEN P, long k, long p)
     805             : {
     806      315777 :   long i, l = lgpol(P);
     807             :   GEN r;
     808      315777 :   if (signe(P)==0)
     809         427 :     return pol_0(varn(P));
     810      315350 :   r = cgetg(p+2,t_POL); r[1] = P[1];
     811     2095422 :   for(i=0; i<p; i++)
     812             :   {
     813     1780072 :     long s = 2+(i+k)%p;
     814     1780072 :     gel(r,s) = i<l? gel(P,2+i): gen_0;
     815             :   }
     816      315350 :   return RgX_renormalize(r);
     817             : }
     818             : 
     819             : GEN
     820     2829272 : RgX_mulXn(GEN x, long d)
     821             : {
     822             :   pari_sp av;
     823             :   GEN z;
     824             :   long v;
     825     2829272 :   if (d >= 0) return RgX_shift(x, d);
     826     1335917 :   d = -d;
     827     1335917 :   v = RgX_val(x);
     828     1335917 :   if (v >= d) return RgX_shift(x, -d);
     829     1335910 :   av = avma;
     830     1335910 :   z = gred_rfrac_simple(RgX_shift_shallow(x, -v), pol_xn(d - v, varn(x)));
     831     1335910 :   return gerepileupto(av, z);
     832             : }
     833             : 
     834             : long
     835     2108104 : RgX_val(GEN x)
     836             : {
     837     2108104 :   long i, lx = lg(x);
     838     2108104 :   if (lx == 2) return LONG_MAX;
     839     2129559 :   for (i = 2; i < lx; i++)
     840     2129559 :     if (!isexactzero(gel(x,i))) break;
     841     2108090 :   if (i == lx) i--; /* possible with non-rational zeros */
     842     2108090 :   return i - 2;
     843             : }
     844             : long
     845    41281305 : RgX_valrem(GEN x, GEN *Z)
     846             : {
     847    41281305 :   long v, i, lx = lg(x);
     848    41281305 :   if (lx == 2) { *Z = pol_0(varn(x)); return LONG_MAX; }
     849    80235614 :   for (i = 2; i < lx; i++)
     850    80235614 :     if (!isexactzero(gel(x,i))) break;
     851    41281305 :   if (i == lx) i--; /* possible with non-rational zeros */
     852    41281305 :   v = i - 2;
     853    41281305 :   *Z = RgX_shift_shallow(x, -v);
     854    41281305 :   return v;
     855             : }
     856             : long
     857        3152 : RgX_valrem_inexact(GEN x, GEN *Z)
     858             : {
     859             :   long v;
     860        3152 :   if (!signe(x)) { if (Z) *Z = pol_0(varn(x)); return LONG_MAX; }
     861        3439 :   for (v = 0;; v++)
     862        3439 :     if (!gequal0(gel(x,2+v))) break;
     863         294 :   if (Z) *Z = RgX_shift_shallow(x, -v);
     864        3145 :   return v;
     865             : }
     866             : 
     867             : GEN
     868           0 : RgXQC_red(GEN P, GEN T)
     869             : {
     870           0 :   long i, l = lg(P);
     871           0 :   GEN Q = cgetg(l, t_COL);
     872           0 :   for (i=1; i<l; i++) gel(Q,i) = grem(gel(P,i), T);
     873           0 :   return Q;
     874             : }
     875             : 
     876             : GEN
     877          56 : RgXQV_red(GEN P, GEN T)
     878             : {
     879          56 :   long i, l = lg(P);
     880          56 :   GEN Q = cgetg(l, t_VEC);
     881          56 :   for (i=1; i<l; i++) gel(Q,i) = grem(gel(P,i), T);
     882          56 :   return Q;
     883             : }
     884             : 
     885             : GEN
     886           0 : RgXQM_red(GEN P, GEN T)
     887             : {
     888           0 :   long i, l = lg(P);
     889           0 :   GEN Q = cgetg(l, t_MAT);
     890           0 :   for (i=1; i<l; i++) gel(Q,i) = RgXQC_red(gel(P,i), T);
     891           0 :   return Q;
     892             : }
     893             : 
     894             : GEN
     895           0 : RgXQM_mul(GEN P, GEN Q, GEN T)
     896             : {
     897           0 :   return RgXQM_red(RgM_mul(P, Q), T);
     898             : }
     899             : 
     900             : GEN
     901        5530 : RgXQX_red(GEN P, GEN T)
     902             : {
     903        5530 :   long i, l = lg(P);
     904        5530 :   GEN Q = cgetg(l, t_POL);
     905        5530 :   Q[1] = P[1];
     906        5530 :   for (i=2; i<l; i++) gel(Q,i) = grem(gel(P,i), T);
     907        5530 :   return normalizepol_lg(Q, l);
     908             : }
     909             : 
     910             : GEN
     911      175443 : RgX_deriv(GEN x)
     912             : {
     913      175443 :   long i,lx = lg(x)-1;
     914             :   GEN y;
     915             : 
     916      175443 :   if (lx<3) return pol_0(varn(x));
     917      174071 :   y = cgetg(lx,t_POL); gel(y,2) = gcopy(gel(x,3));
     918      174071 :   for (i=3; i<lx ; i++) gel(y,i) = gmulsg(i-1,gel(x,i+1));
     919      174071 :   y[1] = x[1]; return normalizepol_lg(y,i);
     920             : }
     921             : 
     922             : GEN
     923      287793 : RgX_recipspec_shallow(GEN x, long l, long n)
     924             : {
     925             :   long i;
     926      287793 :   GEN z=cgetg(n+2,t_POL)+2;
     927    13852325 :   for(i=0; i<l; i++)
     928    13564531 :     gel(z,n-i-1) = gel(x,i);
     929      375518 :   for(   ; i<n; i++)
     930       87724 :     gel(z, n-i-1) = gen_0;
     931      287794 :   return normalizepol_lg(z-2,n+2);
     932             : }
     933             : 
     934             : /* return coefficients s.t x = x_0 X^n + ... + x_n */
     935             : GEN
     936         504 : RgX_recip(GEN x)
     937             : {
     938             :   long lx, i, j;
     939         504 :   GEN y = cgetg_copy(x, &lx);
     940         504 :   y[1] = x[1]; for (i=2,j=lx-1; i<lx; i++,j--) gel(y,i) = gcopy(gel(x,j));
     941         504 :   return normalizepol_lg(y,lx);
     942             : }
     943             : /* shallow version */
     944             : GEN
     945      320442 : RgX_recip_shallow(GEN x)
     946             : {
     947             :   long lx, i, j;
     948      320442 :   GEN y = cgetg_copy(x, &lx);
     949      320453 :   y[1] = x[1]; for (i=2,j=lx-1; i<lx; i++,j--) gel(y,i) = gel(x,j);
     950      320453 :   return y;
     951             : }
     952             : /*******************************************************************/
     953             : /*                                                                 */
     954             : /*                      ADDITION / SUBTRACTION                     */
     955             : /*                                                                 */
     956             : /*******************************************************************/
     957             : /* same variable */
     958             : GEN
     959    15514454 : RgX_add(GEN x, GEN y)
     960             : {
     961    15514454 :   long i, lx = lg(x), ly = lg(y);
     962             :   GEN z;
     963    15514454 :   if (ly <= lx) {
     964    14084125 :     z = cgetg(lx,t_POL); z[1] = x[1];
     965    14084132 :     for (i=2; i < ly; i++) gel(z,i) = gadd(gel(x,i),gel(y,i));
     966    14084126 :     for (   ; i < lx; i++) gel(z,i) = gcopy(gel(x,i));
     967    14084126 :     z = normalizepol_lg(z, lx);
     968             :   } else {
     969     1430329 :     z = cgetg(ly,t_POL); z[1] = y[1];
     970     1430341 :     for (i=2; i < lx; i++) gel(z,i) = gadd(gel(x,i),gel(y,i));
     971     1430330 :     for (   ; i < ly; i++) gel(z,i) = gcopy(gel(y,i));
     972     1430330 :     z = normalizepol_lg(z, ly);
     973             :   }
     974    15514455 :   return z;
     975             : }
     976             : GEN
     977     9654725 : RgX_sub(GEN x, GEN y)
     978             : {
     979     9654725 :   long i, lx = lg(x), ly = lg(y);
     980             :   GEN z;
     981     9654725 :   if (ly <= lx) {
     982     7803424 :     z = cgetg(lx,t_POL); z[1] = x[1];
     983     7803452 :     for (i=2; i < ly; i++) gel(z,i) = gsub(gel(x,i),gel(y,i));
     984     7803425 :     for (   ; i < lx; i++) gel(z,i) = gcopy(gel(x,i));
     985     7803425 :     z = normalizepol_lg(z, lx);
     986             :   } else {
     987     1851301 :     z = cgetg(ly,t_POL); z[1] = y[1];
     988     1851301 :     for (i=2; i < lx; i++) gel(z,i) = gsub(gel(x,i),gel(y,i));
     989     1851301 :     for (   ; i < ly; i++) gel(z,i) = gneg(gel(y,i));
     990     1851301 :     z = normalizepol_lg(z, ly);
     991             :   }
     992     9654725 :   return z;
     993             : }
     994             : GEN
     995      876094 : RgX_neg(GEN x)
     996             : {
     997      876094 :   long i, lx = lg(x);
     998      876094 :   GEN y = cgetg(lx, t_POL); y[1] = x[1];
     999      876094 :   for (i=2; i<lx; i++) gel(y,i) = gneg(gel(x,i));
    1000      876094 :   return y;
    1001             : }
    1002             : 
    1003             : GEN
    1004    10412651 : RgX_Rg_add(GEN y, GEN x)
    1005             : {
    1006             :   GEN z;
    1007    10412651 :   long lz = lg(y), i;
    1008    10412651 :   if (lz == 2) return scalarpol(x,varn(y));
    1009     8775423 :   z = cgetg(lz,t_POL); z[1] = y[1];
    1010     8775423 :   gel(z,2) = gadd(gel(y,2),x);
    1011     8775423 :   for(i=3; i<lz; i++) gel(z,i) = gcopy(gel(y,i));
    1012             :   /* probably useless unless lz = 3, but cannot be skipped if y is
    1013             :    * an inexact 0 */
    1014     8775423 :   return normalizepol_lg(z,lz);
    1015             : }
    1016             : GEN
    1017        2422 : RgX_Rg_add_shallow(GEN y, GEN x)
    1018             : {
    1019             :   GEN z;
    1020        2422 :   long lz = lg(y), i;
    1021        2422 :   if (lz == 2) return scalarpol(x,varn(y));
    1022        2422 :   z = cgetg(lz,t_POL); z[1] = y[1];
    1023        2422 :   gel(z,2) = gadd(gel(y,2),x);
    1024        2422 :   for(i=3; i<lz; i++) gel(z,i) = gel(y,i);
    1025        2422 :   return z = normalizepol_lg(z,lz);
    1026             : }
    1027             : GEN
    1028       32278 : RgX_Rg_sub(GEN y, GEN x)
    1029             : {
    1030             :   GEN z;
    1031       32278 :   long lz = lg(y), i;
    1032       32278 :   if (lz == 2)
    1033             :   { /* scalarpol(gneg(x),varn(y)) optimized */
    1034        3864 :     long v = varn(y);
    1035        3864 :     if (isrationalzero(x)) return pol_0(v);
    1036          14 :     z = cgetg(3,t_POL);
    1037          28 :     z[1] = gequal0(x)? evalvarn(v)
    1038          14 :                    : evalvarn(v) | evalsigne(1);
    1039          14 :     gel(z,2) = gneg(x); return z;
    1040             :   }
    1041       28414 :   z = cgetg(lz,t_POL); z[1] = y[1];
    1042       28414 :   gel(z,2) = gsub(gel(y,2),x);
    1043       28414 :   for(i=3; i<lz; i++) gel(z,i) = gcopy(gel(y,i));
    1044       28414 :   return z = normalizepol_lg(z,lz);
    1045             : }
    1046             : GEN
    1047      309420 : Rg_RgX_sub(GEN x, GEN y)
    1048             : {
    1049             :   GEN z;
    1050      309420 :   long lz = lg(y), i;
    1051      309420 :   if (lz == 2) return scalarpol(x,varn(y));
    1052      308405 :   z = cgetg(lz,t_POL); z[1] = y[1];
    1053      308405 :   gel(z,2) = gsub(x, gel(y,2));
    1054      308405 :   for(i=3; i<lz; i++) gel(z,i) = gneg(gel(y,i));
    1055      308405 :   return z = normalizepol_lg(z,lz);
    1056             : }
    1057             : /*******************************************************************/
    1058             : /*                                                                 */
    1059             : /*                  KARATSUBA MULTIPLICATION                       */
    1060             : /*                                                                 */
    1061             : /*******************************************************************/
    1062             : #if 0
    1063             : /* to debug Karatsuba-like routines */
    1064             : GEN
    1065             : zx_debug_spec(GEN x, long nx)
    1066             : {
    1067             :   GEN z = cgetg(nx+2,t_POL);
    1068             :   long i;
    1069             :   for (i=0; i<nx; i++) gel(z,i+2) = stoi(x[i]);
    1070             :   z[1] = evalsigne(1); return z;
    1071             : }
    1072             : 
    1073             : GEN
    1074             : RgX_debug_spec(GEN x, long nx)
    1075             : {
    1076             :   GEN z = cgetg(nx+2,t_POL);
    1077             :   long i;
    1078             :   for (i=0; i<nx; i++) z[i+2] = x[i];
    1079             :   z[1] = evalsigne(1); return z;
    1080             : }
    1081             : #endif
    1082             : 
    1083             : /* generic multiplication */
    1084             : 
    1085             : static GEN
    1086     2790993 : addpol(GEN x, GEN y, long lx, long ly)
    1087             : {
    1088             :   long i,lz;
    1089             :   GEN z;
    1090             : 
    1091     2790993 :   if (ly>lx) swapspec(x,y, lx,ly);
    1092     2790993 :   lz = lx+2; z = cgetg(lz,t_POL) + 2;
    1093     2791110 :   for (i=0; i<ly; i++) gel(z,i) = gadd(gel(x,i),gel(y,i));
    1094     2790986 :   for (   ; i<lx; i++) gel(z,i) = gel(x,i);
    1095     2790986 :   z -= 2; z[1]=0; return normalizepol_lg(z, lz);
    1096             : }
    1097             : 
    1098             : static GEN
    1099      300548 : addpolcopy(GEN x, GEN y, long lx, long ly)
    1100             : {
    1101             :   long i,lz;
    1102             :   GEN z;
    1103             : 
    1104      300548 :   if (ly>lx) swapspec(x,y, lx,ly);
    1105      300548 :   lz = lx+2; z = cgetg(lz,t_POL) + 2;
    1106      300586 :   for (i=0; i<ly; i++) gel(z,i) = gadd(gel(x,i),gel(y,i));
    1107      300561 :   for (   ; i<lx; i++) gel(z,i) = gcopy(gel(x,i));
    1108      300548 :   z -= 2; z[1]=0; return normalizepol_lg(z, lz);
    1109             : }
    1110             : 
    1111             : /* Return the vector of coefficients of x, where we replace rational 0s by NULL
    1112             :  * [ to speed up basic operation s += x[i]*y[j] ]. We create a proper
    1113             :  * t_VECSMALL, to hold this, which can be left on stack: gerepile
    1114             :  * will not crash on it. The returned vector itself is not a proper GEN,
    1115             :  * we access the coefficients as x[i], i = 0..deg(x) */
    1116             : static GEN
    1117    30892923 : RgXspec_kill0(GEN x, long lx)
    1118             : {
    1119    30892923 :   GEN z = cgetg(lx+1, t_VECSMALL) + 1; /* inhibit gerepile-wise */
    1120             :   long i;
    1121   130866738 :   for (i=0; i <lx; i++)
    1122             :   {
    1123    99973865 :     GEN c = gel(x,i);
    1124    99973865 :     z[i] = (long)(isrationalzero(c)? NULL: c);
    1125             :   }
    1126    30892873 :   return z;
    1127             : }
    1128             : 
    1129             : INLINE GEN
    1130    71525617 : RgX_mulspec_basecase_limb(GEN x, GEN y, long a, long b)
    1131             : {
    1132    71525617 :   pari_sp av = avma;
    1133    71525617 :   GEN s = NULL;
    1134             :   long i;
    1135             : 
    1136   282993254 :   for (i=a; i<b; i++)
    1137   211470387 :     if (gel(y,i) && gel(x,-i))
    1138             :     {
    1139   162325206 :       GEN t = gmul(gel(y,i), gel(x,-i));
    1140   162328265 :       s = s? gadd(s, t): t;
    1141             :     }
    1142    71522867 :   return s? gerepileupto(av, s): gen_0;
    1143             : }
    1144             : 
    1145             : /* assume nx >= ny > 0, return x * y * t^v */
    1146             : static GEN
    1147    12155524 : RgX_mulspec_basecase(GEN x, GEN y, long nx, long ny, long v)
    1148             : {
    1149             :   long i, lz, nz;
    1150             :   GEN z;
    1151             : 
    1152    12155524 :   x = RgXspec_kill0(x,nx);
    1153    12155511 :   y = RgXspec_kill0(y,ny);
    1154    12155513 :   lz = nx + ny + 1; nz = lz-2;
    1155    12155513 :   lz += v;
    1156    12155513 :   z = cgetg(lz, t_POL) + 2; /* x:y:z [i] = term of degree i */
    1157    12155628 :   for (i=0; i<v; i++) gel(z++, 0) = gen_0;
    1158    12155628 :   for (i=0; i<ny; i++)gel(z,i) = RgX_mulspec_basecase_limb(x+i,y, 0, i+1);
    1159    12155487 :   for (  ; i<nx; i++) gel(z,i) = RgX_mulspec_basecase_limb(x+i,y, 0,ny);
    1160    12155486 :   for (  ; i<nz; i++) gel(z,i) = RgX_mulspec_basecase_limb(x+i,y, i-nx+1,ny);
    1161    12155521 :   z -= v+2; z[1] = 0; return normalizepol_lg(z, lz);
    1162             : }
    1163             : 
    1164             : /* return (x * X^d) + y. Assume d > 0 */
    1165             : GEN
    1166     1781238 : addmulXn(GEN x, GEN y, long d)
    1167             : {
    1168             :   GEN xd, yd, zd;
    1169             :   long a, lz, nx, ny;
    1170             : 
    1171     1781238 :   if (!signe(x)) return y;
    1172     1761223 :   ny = lgpol(y);
    1173     1761223 :   nx = lgpol(x);
    1174     1761223 :   zd = (GEN)avma;
    1175     1761223 :   x += 2; y += 2; a = ny-d;
    1176     1761223 :   if (a <= 0)
    1177             :   {
    1178      140801 :     lz = nx+d+2;
    1179      140801 :     (void)new_chunk(lz); xd = x+nx; yd = y+ny;
    1180      140801 :     while (xd > x) gel(--zd,0) = gel(--xd,0);
    1181      140801 :     x = zd + a;
    1182      140801 :     while (zd > x) gel(--zd,0) = gen_0;
    1183             :   }
    1184             :   else
    1185             :   {
    1186     1620422 :     xd = new_chunk(d); yd = y+d;
    1187     1620423 :     x = addpol(x,yd, nx,a);
    1188     1620423 :     lz = (a>nx)? ny+2: lg(x)+d;
    1189     1620423 :     x += 2; while (xd > x) *--zd = *--xd;
    1190             :   }
    1191     1761224 :   while (yd > y) *--zd = *--yd;
    1192     1761224 :   *--zd = evalsigne(1);
    1193     1761224 :   *--zd = evaltyp(t_POL) | evallg(lz); return zd;
    1194             : }
    1195             : 
    1196             : GEN
    1197       22778 : addshiftpol(GEN x, GEN y, long d)
    1198             : {
    1199       22778 :   long v = varn(x);
    1200       22778 :   x = addmulXn(x,y,d);
    1201       22778 :   setvarn(x,v); return x;
    1202             : }
    1203             : 
    1204             : /* as above, producing a clean malloc */
    1205             : static GEN
    1206      593261 : addmulXncopy(GEN x, GEN y, long d)
    1207             : {
    1208             :   GEN xd, yd, zd;
    1209             :   long a, lz, nx, ny;
    1210             : 
    1211      593261 :   if (!signe(x)) return RgX_copy(y);
    1212      593129 :   nx = lgpol(x);
    1213      593129 :   ny = lgpol(y);
    1214      593129 :   zd = (GEN)avma;
    1215      593129 :   x += 2; y += 2; a = ny-d;
    1216      593129 :   if (a <= 0)
    1217             :   {
    1218      292581 :     lz = nx+d+2;
    1219      292581 :     (void)new_chunk(lz); xd = x+nx; yd = y+ny;
    1220      292592 :     while (xd > x) gel(--zd,0) = gcopy(gel(--xd,0));
    1221      292592 :     x = zd + a;
    1222      292592 :     while (zd > x) gel(--zd,0) = gen_0;
    1223             :   }
    1224             :   else
    1225             :   {
    1226      300548 :     xd = new_chunk(d); yd = y+d;
    1227      300548 :     x = addpolcopy(x,yd, nx,a);
    1228      300548 :     lz = (a>nx)? ny+2: lg(x)+d;
    1229      300548 :     x += 2; while (xd > x) *--zd = *--xd;
    1230             :   }
    1231      593140 :   while (yd > y) gel(--zd,0) = gcopy(gel(--yd,0));
    1232      593129 :   *--zd = evalsigne(1);
    1233      593129 :   *--zd = evaltyp(t_POL) | evallg(lz); return zd;
    1234             : }
    1235             : 
    1236             : /* return x * y mod t^n */
    1237             : static GEN
    1238     3155439 : RgXn_mul_basecase(GEN x, GEN y, long n)
    1239             : {
    1240     3155439 :   long i, lz = n+2, lx = lgpol(x), ly = lgpol(y);
    1241             :   GEN z;
    1242     3155439 :   if (lx < 0) return pol_0(varn(x));
    1243     3155439 :   if (ly < 0) return pol_0(varn(x));
    1244     3155439 :   z = cgetg(lz, t_POL) + 2;
    1245     3155439 :   x+=2; if (lx > n) lx = n;
    1246     3155439 :   y+=2; if (ly > n) ly = n;
    1247     3155439 :   z[-1] = x[-1];
    1248     3155439 :   if (ly > lx) { swap(x,y); lswap(lx,ly); }
    1249     3155439 :   x = RgXspec_kill0(x, lx);
    1250     3155439 :   y = RgXspec_kill0(y, ly);
    1251             :   /* x:y:z [i] = term of degree i */
    1252     3155439 :   for (i=0;i<ly; i++) gel(z,i) = RgX_mulspec_basecase_limb(x+i,y, 0,i+1);
    1253     3155439 :   for (  ; i<lx; i++) gel(z,i) = RgX_mulspec_basecase_limb(x+i,y, 0,ly);
    1254     3155439 :   for (  ; i<n; i++)  gel(z,i) = RgX_mulspec_basecase_limb(x+i,y, i-lx+1,ly);
    1255     3155439 :   return normalizepol_lg(z - 2, lz);
    1256             : }
    1257             : /* Mulders / Karatsuba product f*g mod t^n (Hanrot-Zimmermann variant) */
    1258             : GEN
    1259     3642660 : RgXn_mul(GEN f, GEN g, long n)
    1260             : {
    1261     3642660 :   pari_sp av = avma;
    1262             :   GEN fe,fo, ge,go, l,h,m;
    1263             :   long n0, n1;
    1264     3642660 :   if (degpol(f) + degpol(g) < n) return RgX_mul(f,g);
    1265     3156426 :   if (n < 80) return RgXn_mul_basecase(f,g,n);
    1266         987 :   n0 = n>>1; n1 = n-n0;
    1267         987 :   RgX_even_odd(f, &fe, &fo);
    1268         987 :   RgX_even_odd(g, &ge, &go);
    1269         987 :   l = RgXn_mul(fe,ge,n1);
    1270         987 :   h = RgXn_mul(fo,go,n0);
    1271         987 :   m = RgX_sub(RgXn_mul(RgX_add(fe,fo),RgX_add(ge,go),n0), RgX_add(l,h));
    1272             :   /* n1-1 <= n0 <= n1, deg l,m <= n1-1, deg h <= n0-1
    1273             :    * result is t^2 h(t^2) + t m(t^2) + l(t^2) */
    1274         987 :   l = RgX_inflate(l,2); /* deg l <= 2n1 - 2 <= n-1 */
    1275             :   /* deg(t m(t^2)) <= 2n1 - 1 <= n, truncate to < n */
    1276         987 :   if (2*degpol(m)+1 == n) m = normalizepol_lg(m, lg(m)-1);
    1277         987 :   m = RgX_inflate(m,2);
    1278             :   /* deg(t^2 h(t^2)) <= 2n0 <= n, truncate to < n */
    1279         987 :   if (2*degpol(h)+2 == n) h = normalizepol_lg(h, lg(h)-1);
    1280         987 :   h = RgX_inflate(h,2);
    1281         987 :   h = addmulXncopy(addmulXn(h,m,1), l,1);
    1282         987 :   setvarn(h, varn(f)); return gerepileupto(av, h);
    1283             : }
    1284             : /* (f*g) \/ x^n */
    1285             : GEN
    1286       19697 : RgX_mulhigh_i(GEN f, GEN g, long n)
    1287             : {
    1288       19697 :   long d = degpol(f)+degpol(g) + 1 - n;
    1289             :   GEN h;
    1290       19697 :   if (d <= 2) return RgX_shift_shallow(RgX_mul(f,g), -n);
    1291        1501 :   h = RgX_recip_shallow(RgXn_mul(RgX_recip_shallow(f),
    1292             :                                  RgX_recip_shallow(g), d));
    1293        1501 :   return RgX_shift_shallow(h, d-1-degpol(h)); /* possibly (fg)(0) = 0 */
    1294             : }
    1295             : 
    1296             : /* fast product (Karatsuba) of polynomials a,b. These are not real GENs, a+2,
    1297             :  * b+2 were sent instead. na, nb = number of terms of a, b.
    1298             :  * Only c, c0, c1, c2 are genuine GEN.
    1299             :  */
    1300             : GEN
    1301    12846779 : RgX_mulspec(GEN a, GEN b, long na, long nb)
    1302             : {
    1303             :   GEN a0, c, c0;
    1304    12846779 :   long n0, n0a, i, v = 0;
    1305             :   pari_sp av;
    1306             : 
    1307    12846779 :   while (na && isrationalzero(gel(a,0))) { a++; na--; v++; }
    1308    12846777 :   while (nb && isrationalzero(gel(b,0))) { b++; nb--; v++; }
    1309    12846771 :   if (na < nb) swapspec(a,b, na,nb);
    1310    12846771 :   if (!nb) return pol_0(0);
    1311             : 
    1312    12746960 :   if (nb < RgX_MUL_LIMIT) return RgX_mulspec_basecase(a,b,na,nb, v);
    1313      591439 :   RgX_shift_inplace_init(v);
    1314      591440 :   i = (na>>1); n0 = na-i; na = i;
    1315      591440 :   av = avma; a0 = a+n0; n0a = n0;
    1316      591440 :   while (n0a && isrationalzero(gel(a,n0a-1))) n0a--;
    1317             : 
    1318      591437 :   if (nb > n0)
    1319             :   {
    1320             :     GEN b0,c1,c2;
    1321             :     long n0b;
    1322             : 
    1323      585287 :     nb -= n0; b0 = b+n0; n0b = n0;
    1324      585287 :     while (n0b && isrationalzero(gel(b,n0b-1))) n0b--;
    1325      585286 :     c = RgX_mulspec(a,b,n0a,n0b);
    1326      585289 :     c0 = RgX_mulspec(a0,b0, na,nb);
    1327             : 
    1328      585291 :     c2 = addpol(a0,a, na,n0a);
    1329      585289 :     c1 = addpol(b0,b, nb,n0b);
    1330             : 
    1331      585288 :     c1 = RgX_mulspec(c1+2,c2+2, lgpol(c1),lgpol(c2));
    1332      585289 :     c2 = RgX_sub(c1, RgX_add(c0,c));
    1333      585290 :     c0 = addmulXn(c0, c2, n0);
    1334             :   }
    1335             :   else
    1336             :   {
    1337        6150 :     c = RgX_mulspec(a,b,n0a,nb);
    1338        6150 :     c0 = RgX_mulspec(a0,b,na,nb);
    1339             :   }
    1340      591441 :   c0 = addmulXncopy(c0,c,n0);
    1341      591441 :   return RgX_shift_inplace(gerepileupto(av,c0), v);
    1342             : }
    1343             : 
    1344             : INLINE GEN
    1345     2849446 : RgX_sqrspec_basecase_limb(GEN x, long a, long i)
    1346             : {
    1347     2849446 :   pari_sp av = avma;
    1348     2849446 :   GEN s = NULL;
    1349     2849446 :   long j, l = (i+1)>>1;
    1350    10533730 :   for (j=a; j<l; j++)
    1351             :   {
    1352     7685785 :     GEN xj = gel(x,j), xx = gel(x,i-j);
    1353     7685785 :     if (xj && xx)
    1354             :     {
    1355     4820511 :       GEN t = gmul(xj, xx);
    1356     4822513 :       s = s? gadd(s, t): t;
    1357             :     }
    1358             :   }
    1359     2847945 :   if (s) s = gshift(s,1);
    1360     2847999 :   if ((i&1) == 0)
    1361             :   {
    1362     1559557 :     GEN t = gel(x, i>>1);
    1363     1559557 :     if (t) {
    1364     1295681 :       t = gsqr(t);
    1365     1295695 :       s = s? gadd(s, t): t;
    1366             :     }
    1367             :   }
    1368     2847954 :   return s? gerepileupto(av,s): gen_0;
    1369             : }
    1370             : static GEN
    1371      270365 : RgX_sqrspec_basecase(GEN x, long nx, long v)
    1372             : {
    1373             :   long i, lz, nz;
    1374             :   GEN z;
    1375             : 
    1376      270365 :   if (!nx) return pol_0(0);
    1377      270358 :   x = RgXspec_kill0(x,nx);
    1378      270354 :   lz = (nx << 1) + 1, nz = lz-2;
    1379      270354 :   lz += v;
    1380      270354 :   z = cgetg(lz,t_POL) + 2;
    1381      270372 :   for (i=0; i<v; i++) gel(z++, 0) = gen_0;
    1382      270372 :   for (i=0; i<nx; i++)gel(z,i) = RgX_sqrspec_basecase_limb(x, 0, i);
    1383      270345 :   for (  ; i<nz; i++) gel(z,i) = RgX_sqrspec_basecase_limb(x, i-nx+1, i);
    1384      270356 :   z -= v+2; z[1] = 0; return normalizepol_lg(z, lz);
    1385             : }
    1386             : /* return x^2 mod t^n */
    1387             : static GEN
    1388         665 : RgXn_sqr_basecase(GEN x, long n)
    1389             : {
    1390         665 :   long i, lz = n+2, lx = lgpol(x);
    1391             :   GEN z;
    1392         665 :   if (lx < 0) return pol_0(varn(x));
    1393         665 :   z = cgetg(lz, t_POL);
    1394         665 :   z[1] = x[1];
    1395         665 :   x+=2; if (lx > n) lx = n;
    1396         665 :   x = RgXspec_kill0(x,lx);
    1397         665 :   z+=2;/* x:z [i] = term of degree i */
    1398         665 :   for (i=0;i<lx; i++) gel(z,i) = RgX_sqrspec_basecase_limb(x, 0, i);
    1399         665 :   for (  ; i<n; i++)  gel(z,i) = RgX_sqrspec_basecase_limb(x, i-lx+1, i);
    1400         665 :   z -= 2; return normalizepol_lg(z, lz);
    1401             : }
    1402             : /* Mulders / Karatsuba product f^2 mod t^n (Hanrot-Zimmermann variant) */
    1403             : GEN
    1404        2380 : RgXn_sqr(GEN f, long n)
    1405             : {
    1406        2380 :   pari_sp av = avma;
    1407             :   GEN fe,fo, l,h,m;
    1408             :   long n0, n1;
    1409        2380 :   if (2*degpol(f) < n) return RgX_sqr(f);
    1410         693 :   if (n < 80) return RgXn_sqr_basecase(f,n);
    1411          28 :   n0 = n>>1; n1 = n-n0;
    1412          28 :   RgX_even_odd(f, &fe, &fo);
    1413          28 :   l = RgXn_sqr(fe,n1);
    1414          28 :   h = RgXn_sqr(fo,n0);
    1415          28 :   m = RgX_sub(RgXn_sqr(RgX_add(fe,fo),n0), RgX_add(l,h));
    1416             :   /* n1-1 <= n0 <= n1, deg l,m <= n1-1, deg h <= n0-1
    1417             :    * result is t^2 h(t^2) + t m(t^2) + l(t^2) */
    1418          28 :   l = RgX_inflate(l,2); /* deg l <= 2n1 - 2 <= n-1 */
    1419             :   /* deg(t m(t^2)) <= 2n1 - 1 <= n, truncate to < n */
    1420          28 :   if (2*degpol(m)+1 == n) m = normalizepol_lg(m, lg(m)-1);
    1421          28 :   m = RgX_inflate(m,2);
    1422             :   /* deg(t^2 h(t^2)) <= 2n0 <= n, truncate to < n */
    1423          28 :   if (2*degpol(h)+2 == n) h = normalizepol_lg(h, lg(h)-1);
    1424          28 :   h = RgX_inflate(h,2);
    1425          28 :   h = addmulXncopy(addmulXn(h,m,1), l,1);
    1426          28 :   setvarn(h, varn(f)); return gerepileupto(av, h);
    1427             : }
    1428             : 
    1429             : GEN
    1430      271170 : RgX_sqrspec(GEN a, long na)
    1431             : {
    1432             :   GEN a0, c, c0, c1;
    1433      271170 :   long n0, n0a, i, v = 0;
    1434             :   pari_sp av;
    1435             : 
    1436      271170 :   while (na && isrationalzero(gel(a,0))) { a++; na--; v += 2; }
    1437      271170 :   if (na<RgX_SQR_LIMIT) return RgX_sqrspec_basecase(a, na, v);
    1438         805 :   RgX_shift_inplace_init(v);
    1439         805 :   i = (na>>1); n0 = na-i; na = i;
    1440         805 :   av = avma; a0 = a+n0; n0a = n0;
    1441         805 :   while (n0a && isrationalzero(gel(a,n0a-1))) n0a--;
    1442             : 
    1443         805 :   c = RgX_sqrspec(a,n0a);
    1444         805 :   c0 = RgX_sqrspec(a0,na);
    1445         805 :   c1 = gmul2n(RgX_mulspec(a0,a, na,n0a), 1);
    1446         805 :   c0 = addmulXn(c0,c1, n0);
    1447         805 :   c0 = addmulXncopy(c0,c,n0);
    1448         805 :   return RgX_shift_inplace(gerepileupto(av,c0), v);
    1449             : }
    1450             : 
    1451             : /* (X^a + A)(X^b + B) - X^(a+b), where deg A < a, deg B < b */
    1452             : GEN
    1453      428234 : RgX_mul_normalized(GEN A, long a, GEN B, long b)
    1454             : {
    1455      428234 :   GEN z = RgX_mul(A, B);
    1456      428234 :   if (a < b)
    1457        5222 :     z = addmulXn(addmulXn(A, B, b-a), z, a);
    1458      423012 :   else if (a > b)
    1459      272642 :     z = addmulXn(addmulXn(B, A, a-b), z, b);
    1460             :   else
    1461      150370 :     z = addmulXn(RgX_add(A, B), z, a);
    1462      428234 :   setvarn(z,varn(A)); return z;
    1463             : }
    1464             : 
    1465             : GEN
    1466    11077808 : RgX_mul(GEN x, GEN y)
    1467             : {
    1468    11077808 :   GEN z = RgX_mulspec(y+2, x+2, lgpol(y), lgpol(x));
    1469    11077808 :   setvarn(z,varn(x)); return z;
    1470             : }
    1471             : 
    1472             : GEN
    1473      269559 : RgX_sqr(GEN x)
    1474             : {
    1475      269559 :   GEN z = RgX_sqrspec(x+2, lgpol(x));
    1476      269558 :   setvarn(z,varn(x)); return z;
    1477             : }
    1478             : 
    1479             : /*******************************************************************/
    1480             : /*                                                                 */
    1481             : /*                               DIVISION                          */
    1482             : /*                                                                 */
    1483             : /*******************************************************************/
    1484             : GEN
    1485      509246 : RgX_Rg_divexact(GEN x, GEN y) {
    1486             :   long i, lx;
    1487             :   GEN z;
    1488      509246 :   if (typ(y) == t_INT && is_pm1(y))
    1489       93045 :     return signe(y) < 0 ? RgX_neg(x): RgX_copy(x);
    1490      416201 :   z = cgetg_copy(x, &lx); z[1] = x[1];
    1491      416201 :   for (i=2; i<lx; i++) gel(z,i) = gdivexact(gel(x,i),y);
    1492      416201 :   return z;
    1493             : }
    1494             : GEN
    1495    22311246 : RgX_Rg_div(GEN x, GEN y) {
    1496             :   long i, lx;
    1497    22311246 :   GEN z = cgetg_copy(x, &lx); z[1] = x[1];
    1498    22311246 :   for (i=2; i<lx; i++) gel(z,i) = gdiv(gel(x,i),y);
    1499    22311246 :   return normalizepol_lg(z, lx);
    1500             : }
    1501             : GEN
    1502        1456 : RgX_normalize(GEN x)
    1503             : {
    1504        1456 :   GEN d = NULL;
    1505        1456 :   long i, n = lg(x)-1;
    1506        1456 :   for (i = n; i > 1; i--)
    1507             :   {
    1508        1456 :     d = gel(x,i);
    1509        1456 :     if (!gequal0(d)) break;
    1510             :   }
    1511        1456 :   if (i == 1) return pol_0(varn(x));
    1512        1456 :   if (i == n && isint1(d)) return x;
    1513         287 :   return normalizepol_lg(RgX_Rg_div(x, d), i+1);
    1514             : }
    1515             : GEN
    1516        1729 : RgX_divs(GEN x, long y) {
    1517             :   long i, lx;
    1518        1729 :   GEN z = cgetg_copy(x, &lx); z[1] = x[1];
    1519        1729 :   for (i=2; i<lx; i++) gel(z,i) = gdivgs(gel(x,i),y);
    1520        1729 :   return normalizepol_lg(z, lx);
    1521             : }
    1522             : GEN
    1523       31958 : RgX_div_by_X_x(GEN a, GEN x, GEN *r)
    1524             : {
    1525       31958 :   long l = lg(a), i;
    1526       31958 :   GEN a0, z0, z = cgetg(l-1, t_POL);
    1527       31958 :   z[1] = a[1];
    1528       31958 :   a0 = a + l-1;
    1529       31958 :   z0 = z + l-2; *z0 = *a0--;
    1530      736814 :   for (i=l-3; i>1; i--) /* z[i] = a[i+1] + x*z[i+1] */
    1531             :   {
    1532      704856 :     GEN t = gadd(gel(a0--,0), gmul(x, gel(z0--,0)));
    1533      704856 :     gel(z0,0) = t;
    1534             :   }
    1535       31958 :   if (r) *r = gadd(gel(a0,0), gmul(x, gel(z0,0)));
    1536       31958 :   return z;
    1537             : }
    1538             : /* Polynomial division x / y:
    1539             :  *   if z = ONLY_REM  return remainder, otherwise return quotient
    1540             :  *   if z != NULL set *z to remainder
    1541             :  *   *z is the last object on stack (and thus can be disposed of with cgiv
    1542             :  *   instead of gerepile) */
    1543             : /* assume, typ(x) = typ(y) = t_POL, same variable */
    1544             : GEN
    1545    13044004 : RgX_divrem(GEN x, GEN y, GEN *pr)
    1546             : {
    1547             :   pari_sp avy, av, av1;
    1548             :   long dx,dy,dz,i,j,sx,lr;
    1549             :   GEN z,p1,p2,rem,y_lead,mod;
    1550             :   GEN (*f)(GEN,GEN);
    1551             : 
    1552    13044004 :   if (!signe(y)) pari_err_INV("RgX_divrem",y);
    1553             : 
    1554    13044004 :   dy = degpol(y);
    1555    13043961 :   y_lead = gel(y,dy+2);
    1556    13043961 :   if (gequal0(y_lead)) /* normalize denominator if leading term is 0 */
    1557             :   {
    1558           0 :     pari_warn(warner,"normalizing a polynomial with 0 leading term");
    1559           0 :     for (dy--; dy>=0; dy--)
    1560             :     {
    1561           0 :       y_lead = gel(y,dy+2);
    1562           0 :       if (!gequal0(y_lead)) break;
    1563             :     }
    1564             :   }
    1565    13043956 :   if (!dy) /* y is constant */
    1566             :   {
    1567       10630 :     if (pr == ONLY_REM) return pol_0(varn(x));
    1568       10021 :     z = RgX_Rg_div(x, y_lead);
    1569       10021 :     if (pr == ONLY_DIVIDES) return z;
    1570        9342 :     if (pr) *pr = pol_0(varn(x));
    1571        9342 :     return z;
    1572             :   }
    1573    13033326 :   dx = degpol(x);
    1574    13033305 :   if (dx < dy)
    1575             :   {
    1576      938312 :     if (pr == ONLY_REM) return RgX_copy(x);
    1577      309268 :     if (pr == ONLY_DIVIDES) return signe(x)? NULL: pol_0(varn(x));
    1578      309247 :     z = pol_0(varn(x));
    1579      309247 :     if (pr) *pr = RgX_copy(x);
    1580      309247 :     return z;
    1581             :   }
    1582             : 
    1583             :   /* x,y in R[X], y non constant */
    1584    12094993 :   av = avma;
    1585    12094993 :   switch(typ(y_lead))
    1586             :   {
    1587             :     case t_REAL:
    1588           0 :       y_lead = ginv(y_lead);
    1589           0 :       f = gmul; mod = NULL;
    1590           0 :       break;
    1591             :     case t_INTMOD:
    1592        4514 :     case t_POLMOD: y_lead = ginv(y_lead);
    1593        4514 :       f = gmul; mod = gmodulo(gen_1, gel(y_lead,1));
    1594        4514 :       break;
    1595    12090479 :     default: if (gequal1(y_lead)) y_lead = NULL;
    1596    12090455 :       f = gdiv; mod = NULL;
    1597             :   }
    1598             : 
    1599    12094969 :   if (y_lead == NULL)
    1600    10324230 :     p2 = gel(x,dx+2);
    1601             :   else {
    1602             :     for(;;) {
    1603     1770739 :       p2 = f(gel(x,dx+2),y_lead);
    1604     1770735 :       p2 = simplify_shallow(p2);
    1605     1770735 :       if (!isexactzero(p2) || (--dx < 0)) break;
    1606           0 :     }
    1607     1770735 :     if (dx < dy) /* leading coeff of x was in fact zero */
    1608             :     {
    1609           0 :       if (pr == ONLY_DIVIDES) {
    1610           0 :         avma = av;
    1611           0 :         return (dx < 0)? pol_0(varn(x)) : NULL;
    1612             :       }
    1613           0 :       if (pr == ONLY_REM)
    1614             :       {
    1615           0 :         if (dx < 0)
    1616           0 :           return gerepilecopy(av, scalarpol(p2, varn(x)));
    1617             :         else
    1618             :         {
    1619             :           GEN t;
    1620           0 :           avma = av;
    1621           0 :           t = cgetg(dx + 3, t_POL); t[1] = x[1];
    1622           0 :           for (i = 2; i < dx + 3; i++) gel(t,i) = gcopy(gel(x,i));
    1623           0 :           return t;
    1624             :         }
    1625             :       }
    1626           0 :       if (pr) /* cf ONLY_REM above */
    1627             :       {
    1628           0 :         if (dx < 0)
    1629             :         {
    1630           0 :           p2 = gclone(p2);
    1631           0 :           avma = av;
    1632           0 :           z = pol_0(varn(x));
    1633           0 :           x = scalarpol(p2, varn(x));
    1634           0 :           gunclone(p2);
    1635             :         }
    1636             :         else
    1637             :         {
    1638             :           GEN t;
    1639           0 :           avma = av;
    1640           0 :           z = pol_0(varn(x));
    1641           0 :           t = cgetg(dx + 3, t_POL); t[1] = x[1];
    1642           0 :           for (i = 2; i < dx + 3; i++) gel(t,i) = gcopy(gel(x,i));
    1643           0 :           x = t;
    1644             :         }
    1645           0 :         *pr = x;
    1646             :       }
    1647             :       else
    1648             :       {
    1649           0 :         avma = av;
    1650           0 :         z = pol_0(varn(x));
    1651             :       }
    1652           0 :       return z;
    1653             :     }
    1654             :   }
    1655             :   /* dx >= dy */
    1656    12094965 :   avy = avma;
    1657    12094965 :   dz = dx-dy;
    1658    12094965 :   z = cgetg(dz+3,t_POL); z[1] = x[1];
    1659    12094903 :   x += 2;
    1660    12094903 :   z += 2;
    1661    12094903 :   y += 2;
    1662    12094903 :   gel(z,dz) = gcopy(p2);
    1663             : 
    1664    34729859 :   for (i=dx-1; i>=dy; i--)
    1665             :   {
    1666    22634701 :     av1=avma; p1=gel(x,i);
    1667    22634701 :     for (j=i-dy+1; j<=i && j<=dz; j++) p1 = gsub(p1, gmul(gel(z,j),gel(y,i-j)));
    1668    22623421 :     if (y_lead) p1 = simplify(f(p1,y_lead));
    1669             : 
    1670    22623421 :     if (isrationalzero(p1)) { avma=av1; p1 = gen_0; }
    1671             :     else
    1672    12889095 :       p1 = avma==av1? gcopy(p1): gerepileupto(av1,p1);
    1673    22634164 :     gel(z,i-dy) = p1;
    1674             :   }
    1675    12095158 :   if (!pr) return gerepileupto(av,z-2);
    1676             : 
    1677     5785128 :   rem = (GEN)avma; av1 = (pari_sp)new_chunk(dx+3);
    1678     6520886 :   for (sx=0; ; i--)
    1679             :   {
    1680     6520886 :     p1 = gel(x,i);
    1681             :     /* we always enter this loop at least once */
    1682     6520886 :     for (j=0; j<=i && j<=dz; j++) p1 = gsub(p1, gmul(gel(z,j),gel(y,i-j)));
    1683     6520474 :     if (mod && avma==av1) p1 = gmul(p1,mod);
    1684     6520474 :     if (!gequal0(p1)) { sx = 1; break; } /* remainder is non-zero */
    1685     3823943 :     if (!isexactzero(p1)) break;
    1686     3817398 :     if (!i) break;
    1687      735818 :     avma=av1;
    1688      735818 :   }
    1689     5785090 :   if (pr == ONLY_DIVIDES)
    1690             :   {
    1691         693 :     if (sx) { avma=av; return NULL; }
    1692         686 :     avma = (pari_sp)rem;
    1693         686 :     return gerepileupto(av,z-2);
    1694             :   }
    1695     5784397 :   lr=i+3; rem -= lr;
    1696     5784397 :   if (avma==av1) { avma = (pari_sp)rem; p1 = gcopy(p1); }
    1697     5708675 :   else p1 = gerepileupto((pari_sp)rem,p1);
    1698     5784405 :   rem[0] = evaltyp(t_POL) | evallg(lr);
    1699     5783736 :   rem[1] = z[-1];
    1700     5783736 :   rem += 2;
    1701     5783736 :   gel(rem,i) = p1;
    1702    14930857 :   for (i--; i>=0; i--)
    1703             :   {
    1704     9146522 :     av1=avma; p1 = gel(x,i);
    1705     9146522 :     for (j=0; j<=i && j<=dz; j++) p1 = gsub(p1, gmul(gel(z,j),gel(y,i-j)));
    1706     9178554 :     if (mod && avma==av1) p1 = gmul(p1,mod);
    1707     9148270 :     gel(rem,i) = avma==av1? gcopy(p1):gerepileupto(av1,p1);
    1708             :   }
    1709     5784335 :   rem -= 2;
    1710     5784335 :   if (!sx) (void)normalizepol_lg(rem, lr);
    1711     5784336 :   if (pr == ONLY_REM) return gerepileupto(av,rem);
    1712     3945970 :   z -= 2;
    1713             :   {
    1714     3945970 :     GEN *gptr[2]; gptr[0]=&z; gptr[1]=&rem;
    1715     3945970 :     gerepilemanysp(av,avy,gptr,2); *pr = rem; return z;
    1716             :   }
    1717             : }
    1718             : 
    1719             : /* x and y in (R[Y]/T)[X]  (lifted), T in R[Y]. y preferably monic */
    1720             : GEN
    1721       21180 : RgXQX_divrem(GEN x, GEN y, GEN T, GEN *pr)
    1722             : {
    1723             :   long vx, dx, dy, dz, i, j, sx, lr;
    1724             :   pari_sp av0, av, tetpil;
    1725             :   GEN z,p1,rem,lead;
    1726             : 
    1727       21180 :   if (!signe(y)) pari_err_INV("RgXQX_divrem",y);
    1728       21180 :   vx = varn(x);
    1729       21180 :   dx = degpol(x);
    1730       21180 :   dy = degpol(y);
    1731       21180 :   if (dx < dy)
    1732             :   {
    1733        1414 :     if (pr)
    1734             :     {
    1735        1414 :       av0 = avma; x = RgXQX_red(x, T);
    1736        1414 :       if (pr == ONLY_DIVIDES) { avma=av0; return signe(x)? NULL: gen_0; }
    1737        1414 :       if (pr == ONLY_REM) return x;
    1738           0 :       *pr = x;
    1739             :     }
    1740           0 :     return pol_0(vx);
    1741             :   }
    1742       19766 :   lead = leading_coeff(y);
    1743       19766 :   if (!dy) /* y is constant */
    1744             :   {
    1745           7 :     if (pr && pr != ONLY_DIVIDES)
    1746             :     {
    1747           0 :       if (pr == ONLY_REM) return pol_0(vx);
    1748           0 :       *pr = pol_0(vx);
    1749             :     }
    1750           7 :     if (gequal1(lead)) return RgX_copy(x);
    1751           0 :     av0 = avma; x = gmul(x, ginvmod(lead,T)); tetpil = avma;
    1752           0 :     return gerepile(av0,tetpil,RgXQX_red(x,T));
    1753             :   }
    1754       19759 :   av0 = avma; dz = dx-dy;
    1755       19759 :   lead = gequal1(lead)? NULL: gclone(ginvmod(lead,T));
    1756       19759 :   avma = av0;
    1757       19759 :   z = cgetg(dz+3,t_POL); z[1] = x[1];
    1758       19759 :   x += 2; y += 2; z += 2;
    1759             : 
    1760       19759 :   p1 = gel(x,dx); av = avma;
    1761       19759 :   gel(z,dz) = lead? gerepileupto(av, grem(gmul(p1,lead), T)): gcopy(p1);
    1762      105894 :   for (i=dx-1; i>=dy; i--)
    1763             :   {
    1764       86135 :     av=avma; p1=gel(x,i);
    1765       86135 :     for (j=i-dy+1; j<=i && j<=dz; j++) p1 = gsub(p1, gmul(gel(z,j),gel(y,i-j)));
    1766       86135 :     if (lead) p1 = gmul(grem(p1, T), lead);
    1767       86135 :     tetpil=avma; gel(z,i-dy) = gerepile(av,tetpil, grem(p1, T));
    1768             :   }
    1769       19759 :   if (!pr) { if (lead) gunclone(lead); return z-2; }
    1770             : 
    1771       19759 :   rem = (GEN)avma; av = (pari_sp)new_chunk(dx+3);
    1772       29940 :   for (sx=0; ; i--)
    1773             :   {
    1774       29940 :     p1 = gel(x,i);
    1775       29940 :     for (j=0; j<=i && j<=dz; j++) p1 = gsub(p1, gmul(gel(z,j),gel(y,i-j)));
    1776       29940 :     tetpil=avma; p1 = grem(p1, T); if (!gequal0(p1)) { sx = 1; break; }
    1777       14414 :     if (!i) break;
    1778       10181 :     avma=av;
    1779       10181 :   }
    1780       19759 :   if (pr == ONLY_DIVIDES)
    1781             :   {
    1782        3939 :     if (lead) gunclone(lead);
    1783        3939 :     if (sx) { avma=av0; return NULL; }
    1784        3729 :     avma = (pari_sp)rem; return z-2;
    1785             :   }
    1786       15820 :   lr=i+3; rem -= lr;
    1787       15820 :   rem[0] = evaltyp(t_POL) | evallg(lr);
    1788       15820 :   rem[1] = z[-1];
    1789       15820 :   p1 = gerepile((pari_sp)rem,tetpil,p1);
    1790       15820 :   rem += 2; gel(rem,i) = p1;
    1791       30580 :   for (i--; i>=0; i--)
    1792             :   {
    1793       14760 :     av=avma; p1 = gel(x,i);
    1794       36902 :     for (j=0; j<=i && j<=dz; j++)
    1795       22142 :       p1 = gsub(p1, gmul(gel(z,j),gel(y,i-j)));
    1796       14760 :     tetpil=avma; gel(rem,i) = gerepile(av,tetpil, grem(p1, T));
    1797             :   }
    1798       15820 :   rem -= 2;
    1799       15820 :   if (lead) gunclone(lead);
    1800       15820 :   if (!sx) (void)normalizepol_lg(rem, lr);
    1801       15820 :   if (pr == ONLY_REM) return gerepileupto(av0,rem);
    1802          42 :   *pr = rem; return z-2;
    1803             : }
    1804             : 
    1805             : /*******************************************************************/
    1806             : /*                                                                 */
    1807             : /*                        PSEUDO-DIVISION                          */
    1808             : /*                                                                 */
    1809             : /*******************************************************************/
    1810             : INLINE GEN
    1811      626918 : rem(GEN c, GEN T)
    1812             : {
    1813      626918 :   if (T && typ(c) == t_POL && varn(c) == varn(T)) c = RgX_rem(c, T);
    1814      626918 :   return c;
    1815             : }
    1816             : 
    1817             : /* x, y, are ZYX, lc(y) is an integer, T is a ZY */
    1818             : int
    1819        1099 : ZXQX_dvd(GEN x, GEN y, GEN T)
    1820             : {
    1821             :   long dx, dy, dz, i, p, T_ismonic;
    1822        1099 :   pari_sp av = avma, av2;
    1823             :   GEN y_lead;
    1824             : 
    1825        1099 :   if (!signe(y)) pari_err_INV("ZXQX_dvd",y);
    1826        1099 :   dy = degpol(y); y_lead = gel(y,dy+2);
    1827        1099 :   if (typ(y_lead) == t_POL) y_lead = gel(y_lead, 2); /* t_INT */
    1828             :   /* if monic, no point in using pseudo-division */
    1829        1099 :   if (gequal1(y_lead)) return signe(RgXQX_rem(x, y, T)) == 0;
    1830         637 :   T_ismonic = gequal1(leading_coeff(T));
    1831         637 :   dx = degpol(x);
    1832         637 :   if (dx < dy) return !signe(x);
    1833         637 :   (void)new_chunk(2);
    1834         637 :   x = RgX_recip_shallow(x)+2;
    1835         637 :   y = RgX_recip_shallow(y)+2;
    1836             :   /* pay attention to sparse divisors */
    1837        1400 :   for (i = 1; i <= dy; i++)
    1838         763 :     if (!signe(gel(y,i))) gel(y,i) = NULL;
    1839         637 :   dz = dx-dy; p = dz+1;
    1840         637 :   av2 = avma;
    1841             :   for (;;)
    1842             :   {
    1843        7147 :     GEN m, x0 = gel(x,0), y0 = y_lead, cx = content(x0);
    1844        7147 :     x0 = gneg(x0); p--;
    1845        7147 :     m = gcdii(cx, y0);
    1846        7147 :     if (!equali1(m))
    1847             :     {
    1848        6405 :       x0 = gdiv(x0, m);
    1849        6405 :       y0 = diviiexact(y0, m);
    1850        6405 :       if (equali1(y0)) y0 = NULL;
    1851             :     }
    1852       15120 :     for (i=1; i<=dy; i++)
    1853             :     {
    1854        7973 :       GEN c = gel(x,i); if (y0) c = gmul(y0, c);
    1855        7973 :       if (gel(y,i)) c = gadd(c, gmul(x0,gel(y,i)));
    1856        7973 :       if (typ(c) == t_POL) c = T_ismonic ? ZX_rem(c, T): RgX_rem(c, T);
    1857        7973 :       gel(x,i) = c;
    1858             :     }
    1859       77287 :     for (   ; i<=dx; i++)
    1860             :     {
    1861       70140 :       GEN c = gel(x,i); if (y0) c = gmul(y0, c);
    1862       70140 :       if (typ(c) == t_POL) c = T_ismonic ? ZX_rem(c, T): RgX_rem(c, T);
    1863       70140 :       gel(x,i) = c;
    1864             :     }
    1865        7924 :     do { x++; dx--; } while (dx >= 0 && !signe(gel(x,0)));
    1866        7147 :     if (dx < dy) break;
    1867        6510 :     if (gc_needed(av2,1))
    1868             :     {
    1869           0 :       if(DEBUGMEM>1) pari_warn(warnmem,"ZXQX_dvd dx = %ld >= %ld",dx,dy);
    1870           0 :       gerepilecoeffs(av2,x,dx+1);
    1871             :     }
    1872        6510 :   }
    1873         637 :   avma = av; return (dx < 0);
    1874             : }
    1875             : 
    1876             : /* T either NULL or a t_POL. */
    1877             : GEN
    1878       23666 : RgXQX_pseudorem(GEN x, GEN y, GEN T)
    1879             : {
    1880       23666 :   long vx = varn(x), dx, dy, dz, i, lx, p;
    1881       23666 :   pari_sp av = avma, av2;
    1882             :   GEN y_lead;
    1883             : 
    1884       23666 :   if (!signe(y)) pari_err_INV("RgXQX_pseudorem",y);
    1885       23666 :   dy = degpol(y); y_lead = gel(y,dy+2);
    1886             :   /* if monic, no point in using pseudo-division */
    1887       23666 :   if (gequal1(y_lead)) return T? RgXQX_rem(x, y, T): RgX_rem(x, y);
    1888       20054 :   dx = degpol(x);
    1889       20054 :   if (dx < dy) return RgX_copy(x);
    1890       20054 :   (void)new_chunk(2);
    1891       20054 :   x = RgX_recip_shallow(x)+2;
    1892       20054 :   y = RgX_recip_shallow(y)+2;
    1893             :   /* pay attention to sparse divisors */
    1894       62624 :   for (i = 1; i <= dy; i++)
    1895       42570 :     if (isexactzero(gel(y,i))) gel(y,i) = NULL;
    1896       20054 :   dz = dx-dy; p = dz+1;
    1897       20054 :   av2 = avma;
    1898             :   for (;;)
    1899             :   {
    1900       83053 :     gel(x,0) = gneg(gel(x,0)); p--;
    1901      261632 :     for (i=1; i<=dy; i++)
    1902             :     {
    1903      178579 :       GEN c = gmul(y_lead, gel(x,i));
    1904      178579 :       if (gel(y,i)) c = gadd(c, gmul(gel(x,0),gel(y,i)));
    1905      178579 :       gel(x,i) = rem(c, T);
    1906             :     }
    1907      309939 :     for (   ; i<=dx; i++)
    1908             :     {
    1909      226886 :       GEN c = gmul(y_lead, gel(x,i));
    1910      226886 :       gel(x,i) = rem(c, T);
    1911             :     }
    1912       89668 :     do { x++; dx--; } while (dx >= 0 && gequal0(gel(x,0)));
    1913       83053 :     if (dx < dy) break;
    1914       62999 :     if (gc_needed(av2,1))
    1915             :     {
    1916           0 :       if(DEBUGMEM>1) pari_warn(warnmem,"RgX_pseudorem dx = %ld >= %ld",dx,dy);
    1917           0 :       gerepilecoeffs(av2,x,dx+1);
    1918             :     }
    1919       62999 :   }
    1920       20054 :   if (dx < 0) return pol_0(vx);
    1921       18542 :   lx = dx+3; x -= 2;
    1922       18542 :   x[0] = evaltyp(t_POL) | evallg(lx);
    1923       18542 :   x[1] = evalsigne(1) | evalvarn(vx);
    1924       18542 :   x = RgX_recip_shallow(x);
    1925       18542 :   if (p)
    1926             :   { /* multiply by y[0]^p   [beware dummy vars from FpX_FpXY_resultant] */
    1927        1078 :     GEN t = y_lead;
    1928        1078 :     if (T && typ(t) == t_POL && varn(t) == varn(T))
    1929           0 :       t = RgXQ_powu(t, p, T);
    1930             :     else
    1931        1078 :       t = gpowgs(t, p);
    1932        3430 :     for (i=2; i<lx; i++)
    1933             :     {
    1934        2352 :       GEN c = gmul(gel(x,i), t);
    1935        2352 :       gel(x,i) = rem(c,T);
    1936             :     }
    1937        1078 :     if (!T) return gerepileupto(av, x);
    1938             :   }
    1939       17464 :   return gerepilecopy(av, x);
    1940             : }
    1941             : 
    1942             : GEN
    1943       23666 : RgX_pseudorem(GEN x, GEN y) { return RgXQX_pseudorem(x,y, NULL); }
    1944             : 
    1945             : /* Compute z,r s.t lc(y)^(dx-dy+1) x = z y + r */
    1946             : GEN
    1947       45484 : RgXQX_pseudodivrem(GEN x, GEN y, GEN T, GEN *ptr)
    1948             : {
    1949       45484 :   long vx = varn(x), dx, dy, dz, i, iz, lx, lz, p;
    1950       45484 :   pari_sp av = avma, av2;
    1951             :   GEN z, r, ypow, y_lead;
    1952             : 
    1953       45484 :   if (!signe(y)) pari_err_INV("RgXQX_pseudodivrem",y);
    1954       45484 :   dy = degpol(y); y_lead = gel(y,dy+2);
    1955       45484 :   if (gequal1(y_lead)) return T? RgXQX_divrem(x,y, T, ptr): RgX_divrem(x,y, ptr);
    1956       21403 :   dx = degpol(x);
    1957       21403 :   if (dx < dy) { *ptr = RgX_copy(x); return pol_0(vx); }
    1958       21403 :   if (dx == dy)
    1959             :   {
    1960          28 :     GEN x_lead = gel(x,lg(x)-1);
    1961          28 :     x = RgX_renormalize_lg(leafcopy(x), lg(x)-1);
    1962          28 :     y = RgX_renormalize_lg(leafcopy(y), lg(y)-1);
    1963          28 :     r = RgX_sub(RgX_Rg_mul(x, y_lead), RgX_Rg_mul(y, x_lead));
    1964          28 :     *ptr = gerepileupto(av, r); return scalarpol(x_lead, vx);
    1965             :   }
    1966       21375 :   (void)new_chunk(2);
    1967       21375 :   x = RgX_recip_shallow(x)+2;
    1968       21375 :   y = RgX_recip_shallow(y)+2;
    1969             :   /* pay attention to sparse divisors */
    1970       88093 :   for (i = 1; i <= dy; i++)
    1971       66718 :     if (isexactzero(gel(y,i))) gel(y,i) = NULL;
    1972       21375 :   dz = dx-dy; p = dz+1;
    1973       21375 :   lz = dz+3;
    1974       21375 :   z = cgetg(lz, t_POL);
    1975       21375 :   z[1] = evalsigne(1) | evalvarn(vx);
    1976       21375 :   for (i = 2; i < lz; i++) gel(z,i) = gen_0;
    1977       21375 :   ypow = new_chunk(dz+1);
    1978       21375 :   gel(ypow,0) = gen_1;
    1979       21375 :   gel(ypow,1) = y_lead;
    1980       27779 :   for (i=2; i<=dz; i++)
    1981             :   {
    1982        6404 :     GEN c = gmul(gel(ypow,i-1), y_lead);
    1983        6404 :     gel(ypow,i) = rem(c,T);
    1984             :   }
    1985       21375 :   av2 = avma;
    1986       21375 :   for (iz=2;;)
    1987             :   {
    1988       43388 :     p--;
    1989       43388 :     gel(z,iz++) = rem(gmul(gel(x,0), gel(ypow,p)), T);
    1990      174553 :     for (i=1; i<=dy; i++)
    1991             :     {
    1992      131165 :       GEN c = gmul(y_lead, gel(x,i));
    1993      131165 :       if (gel(y,i)) c = gsub(c, gmul(gel(x,0),gel(y,i)));
    1994      131165 :       gel(x,i) = rem(c, T);
    1995             :     }
    1996       81532 :     for (   ; i<=dx; i++)
    1997             :     {
    1998       38144 :       GEN c = gmul(y_lead, gel(x,i));
    1999       38144 :       gel(x,i) = rem(c,T);
    2000             :     }
    2001       43388 :     x++; dx--;
    2002       43388 :     while (dx >= dy && gequal0(gel(x,0))) { x++; dx--; iz++; }
    2003       43388 :     if (dx < dy) break;
    2004       22013 :     if (gc_needed(av2,1))
    2005             :     {
    2006           0 :       GEN X = x-2;
    2007           0 :       if(DEBUGMEM>1) pari_warn(warnmem,"RgX_pseudodivrem dx=%ld >= %ld",dx,dy);
    2008           0 :       X[0] = evaltyp(t_POL)|evallg(dx+3); X[1] = z[1]; /* hack */
    2009           0 :       gerepileall(av2,2, &X, &z); x = X+2;
    2010             :     }
    2011       22013 :   }
    2012       21375 :   while (dx >= 0 && gequal0(gel(x,0))) { x++; dx--; }
    2013       21375 :   if (dx < 0)
    2014          98 :     x = pol_0(vx);
    2015             :   else
    2016             :   {
    2017       21277 :     lx = dx+3; x -= 2;
    2018       21277 :     x[0] = evaltyp(t_POL) | evallg(lx);
    2019       21277 :     x[1] = evalsigne(1) | evalvarn(vx);
    2020       21277 :     x = RgX_recip_shallow(x);
    2021             :   }
    2022       21375 :   z = RgX_recip_shallow(z);
    2023       21375 :   r = x;
    2024       21375 :   if (p)
    2025             :   {
    2026        3945 :     GEN c = gel(ypow,p); r = RgX_Rg_mul(r, c);
    2027        3945 :     if (T && typ(c) == t_POL && varn(c) == varn(T)) r = RgXQX_red(r, T);
    2028             :   }
    2029       21375 :   gerepileall(av, 2, &z, &r);
    2030       21375 :   *ptr = r; return z;
    2031             : }
    2032             : GEN
    2033       45365 : RgX_pseudodivrem(GEN x, GEN y, GEN *ptr)
    2034       45365 : { return RgXQX_pseudodivrem(x,y,NULL,ptr); }
    2035             : 
    2036             : GEN
    2037        1659 : RgXQX_mul(GEN x, GEN y, GEN T)
    2038             : {
    2039        1659 :   return RgXQX_red(RgX_mul(x,y), T);
    2040             : }
    2041             : GEN
    2042    64725632 : RgX_Rg_mul(GEN y, GEN x) {
    2043             :   long i, ly;
    2044    64725632 :   GEN z = cgetg_copy(y, &ly); z[1] = y[1];
    2045    64725632 :   if (ly == 2) return z;
    2046    64668092 :   for (i = 2; i < ly; i++) gel(z,i) = gmul(x,gel(y,i));
    2047    64668085 :   return normalizepol_lg(z,ly);
    2048             : }
    2049             : GEN
    2050         616 : RgX_muls(GEN y, long x) {
    2051             :   long i, ly;
    2052         616 :   GEN z = cgetg_copy(y, &ly); z[1] = y[1];
    2053         616 :   if (ly == 2) return z;
    2054         581 :   for (i = 2; i < ly; i++) gel(z,i) = gmulsg(x,gel(y,i));
    2055         581 :   return normalizepol_lg(z,ly);
    2056             : }
    2057             : GEN
    2058          28 : RgXQX_RgXQ_mul(GEN x, GEN y, GEN T)
    2059             : {
    2060          28 :   return RgXQX_red(RgX_Rg_mul(x,y), T);
    2061             : }
    2062             : GEN
    2063          56 : RgXQV_RgXQ_mul(GEN v, GEN x, GEN T)
    2064             : {
    2065          56 :   return RgXQV_red(RgV_Rg_mul(v,x), T);
    2066             : }
    2067             : 
    2068             : GEN
    2069           0 : RgXQX_sqr(GEN x, GEN T)
    2070             : {
    2071           0 :   return RgXQX_red(RgX_sqr(x), T);
    2072             : }
    2073             : 
    2074             : static GEN
    2075       62846 : _add(void *data, GEN x, GEN y) { (void)data; return RgX_add(x, y); }
    2076             : static GEN
    2077           0 : _sub(void *data, GEN x, GEN y) { (void)data; return RgX_sub(x, y); }
    2078             : static GEN
    2079      207604 : _sqr(void *data, GEN x) { return RgXQ_sqr(x, (GEN)data); }
    2080             : static GEN
    2081       85255 : _mul(void *data, GEN x, GEN y) { return RgXQ_mul(x,y, (GEN)data); }
    2082             : static GEN
    2083      106610 : _cmul(void *data, GEN P, long a, GEN x) { (void)data; return RgX_Rg_mul(x,gel(P,a+2)); }
    2084             : static GEN
    2085      101129 : _one(void *data) { return pol_1(varn((GEN)data)); }
    2086             : static GEN
    2087         105 : _zero(void *data) { return pol_0(varn((GEN)data)); }
    2088             : static GEN
    2089       68201 : _red(void *data, GEN x) { (void)data; return gcopy(x); }
    2090             : 
    2091             : static struct bb_algebra RgXQ_algebra = { _red, _add, _sub,
    2092             :               _mul, _sqr, _one, _zero };
    2093             : 
    2094             : GEN
    2095           0 : RgX_RgXQV_eval(GEN Q, GEN x, GEN T)
    2096             : {
    2097           0 :   return gen_bkeval_powers(Q,degpol(Q),x,(void*)T,&RgXQ_algebra,_cmul);
    2098             : }
    2099             : 
    2100             : GEN
    2101       43190 : RgX_RgXQ_eval(GEN Q, GEN x, GEN T)
    2102             : {
    2103       43190 :   int use_sqr = 2*degpol(x) >= degpol(T);
    2104       43190 :   return gen_bkeval(Q,degpol(Q),x,use_sqr,(void*)T,&RgXQ_algebra,_cmul);
    2105             : }
    2106             : 
    2107             : /* mod X^n */
    2108             : struct modXn {
    2109             :   long v; /* varn(X) */
    2110             :   long n;
    2111             : } ;
    2112             : static GEN
    2113        1785 : _sqrXn(void *data, GEN x) {
    2114        1785 :   struct modXn *S = (struct modXn*)data;
    2115        1785 :   return RgXn_sqr(x, S->n);
    2116             : }
    2117             : static GEN
    2118        1176 : _mulXn(void *data, GEN x, GEN y) {
    2119        1176 :   struct modXn *S = (struct modXn*)data;
    2120        1176 :   return RgXn_mul(x,y, S->n);
    2121             : }
    2122             : static GEN
    2123        1407 : _oneXn(void *data) {
    2124        1407 :   struct modXn *S = (struct modXn*)data;
    2125        1407 :   return pol_1(S->v);
    2126             : }
    2127             : static GEN
    2128           0 : _zeroXn(void *data) {
    2129           0 :   struct modXn *S = (struct modXn*)data;
    2130           0 :   return pol_0(S->v);
    2131             : }
    2132             : static struct bb_algebra RgXn_algebra = { _red, _add, _sub, _mulXn, _sqrXn,
    2133             :                                           _oneXn, _zeroXn };
    2134             : 
    2135             : GEN
    2136         336 : RgXn_powers(GEN x, long m, long n)
    2137             : {
    2138         336 :   long d = degpol(x);
    2139         336 :   int use_sqr = (d<<1) >= n;
    2140             :   struct modXn S;
    2141         336 :   S.v = varn(x); S.n = n;
    2142         336 :   return gen_powers(x,m,use_sqr,(void*)&S,_sqrXn,_mulXn,_oneXn);
    2143             : }
    2144             : 
    2145             : GEN
    2146        1505 : RgXn_powu_i(GEN x, ulong m, long n)
    2147             : {
    2148             :   struct modXn S;
    2149        1505 :   S.v = varn(x); S.n = n;
    2150        1505 :   return gen_powu_i(x, m, (void*)&S,_sqrXn,_mulXn);
    2151             : }
    2152             : GEN
    2153           0 : RgXn_powu(GEN x, ulong m, long n)
    2154             : {
    2155             :   struct modXn S;
    2156           0 :   S.v = varn(x); S.n = n;
    2157           0 :   return gen_powu(x, m, (void*)&S,_sqrXn,_mulXn);
    2158             : }
    2159             : 
    2160             : GEN
    2161         672 : RgX_RgXnV_eval(GEN Q, GEN x, long n)
    2162             : {
    2163             :   struct modXn S;
    2164         672 :   S.v = varn(gel(x,2)); S.n = n;
    2165         672 :   return gen_bkeval_powers(Q,degpol(Q),x,(void*)&S,&RgXn_algebra,_cmul);
    2166             : }
    2167             : 
    2168             : GEN
    2169           0 : RgX_RgXn_eval(GEN Q, GEN x, long n)
    2170             : {
    2171           0 :   int use_sqr = 2*degpol(x) >= n;
    2172             :   struct modXn S;
    2173           0 :   S.v = varn(x); S.n = n;
    2174           0 :   return gen_bkeval(Q,degpol(Q),x,use_sqr,(void*)&S,&RgXn_algebra,_cmul);
    2175             : }
    2176             : 
    2177             : /* Q(x) mod t^n, x in R[t], n >= 1 */
    2178             : GEN
    2179        1561 : RgXn_eval(GEN Q, GEN x, long n)
    2180             : {
    2181        1561 :   long d = degpol(x);
    2182             :   int use_sqr;
    2183             :   struct modXn S;
    2184        1561 :   if (d == 1 && isrationalzero(gel(x,2)))
    2185             :   {
    2186        1554 :     GEN y = RgX_unscale(Q, gel(x,3));
    2187        1554 :     setvarn(y, varn(x)); return y;
    2188             :   }
    2189           7 :   S.v = varn(x);
    2190           7 :   S.n = n;
    2191           7 :   use_sqr = (d<<1) >= n;
    2192           7 :   return gen_bkeval(Q,degpol(Q),x,use_sqr,(void*)&S,&RgXn_algebra,_cmul);
    2193             : }
    2194             : 
    2195             : /* (f*g mod t^n) \ t^n2, assuming 2*n2 >= n */
    2196             : static GEN
    2197       19697 : RgXn_mulhigh(GEN f, GEN g, long n2, long n)
    2198             : {
    2199       19697 :   GEN F = RgX_blocks(f, n2, 2), fl = gel(F,1), fh = gel(F,2);
    2200       19697 :   return RgX_add(RgX_mulhigh_i(fl, g, n2), RgXn_mul(fh, g, n - n2));
    2201             : }
    2202             : 
    2203             : GEN
    2204       98301 : RgXn_inv(GEN f, long e)
    2205             : {
    2206       98301 :   pari_sp av = avma, av2;
    2207             :   ulong mask;
    2208             :   GEN W, a;
    2209       98301 :   long v = varn(f), n = 1;
    2210             : 
    2211       98301 :   if (!signe(f)) pari_err_INV("RgXn_inv",f);
    2212       98301 :   a = ginv(gel(f,2));
    2213       98301 :   if (e == 1) return scalarpol(a, v);
    2214       98301 :   else if (e == 2)
    2215             :   {
    2216             :     GEN b;
    2217       90587 :     if (degpol(f) <= 0 || gequal0(b = gel(f,3))) return scalarpol(a, v);
    2218       86877 :     b = gneg(b);
    2219       86877 :     if (!gequal1(a)) b = gmul(b, gsqr(a));
    2220       86877 :     W = deg1pol_shallow(b, a, v);
    2221       86877 :     return gerepilecopy(av, W);
    2222             :   }
    2223        7714 :   W = scalarpol_shallow(ginv(gel(f,2)),v);
    2224        7714 :   mask = quadratic_prec_mask(e);
    2225        7714 :   av2 = avma;
    2226       35125 :   for (;mask>1;)
    2227             :   {
    2228             :     GEN u, fr;
    2229       19697 :     long n2 = n;
    2230       19697 :     n<<=1; if (mask & 1) n--;
    2231       19697 :     mask >>= 1;
    2232       19697 :     fr = RgXn_red_shallow(f, n);
    2233       19697 :     u = RgXn_mul(W, RgXn_mulhigh(fr, W, n2, n), n-n2);
    2234       19697 :     W = RgX_sub(W, RgX_shift_shallow(u, n2));
    2235       19697 :     if (gc_needed(av2,2))
    2236             :     {
    2237           0 :       if(DEBUGMEM>1) pari_warn(warnmem,"RgXn_inv, e = %ld", n);
    2238           0 :       W = gerepileupto(av2, W);
    2239             :     }
    2240             :   }
    2241        7714 :   return gerepileupto(av, W);
    2242             : }
    2243             : 
    2244             : GEN
    2245         203 : RgXn_exp(GEN h, long e)
    2246             : {
    2247         203 :   pari_sp av = avma, av2;
    2248         203 :   long v = varn(h), n=1;
    2249         203 :   GEN f = pol_1(v), g = pol_1(v);
    2250         203 :   ulong mask = quadratic_prec_mask(e);
    2251         203 :   av2 = avma;
    2252         203 :   if (signe(h)==0 || degpol(h)<1 || !gequal0(gel(h,2)))
    2253           0 :     pari_err_DOMAIN("RgXn_exp","valuation", "<", gen_1, h);
    2254         791 :   for (;mask>1;)
    2255             :   {
    2256             :     GEN q, w;
    2257         385 :     long n2 = n;
    2258         385 :     n<<=1; if (mask & 1) n--;
    2259         385 :     mask >>= 1;
    2260         385 :     g = RgX_sub(RgX_muls(g,2),RgXn_mul(f,RgXn_sqr(g,n2),n2));
    2261         385 :     q = RgX_deriv(RgXn_red_shallow(h,n2));
    2262         385 :     w = RgX_add(q, RgXn_mul(g, RgX_sub(RgX_deriv(f), RgXn_mul(f,q,n-1)),n-1));
    2263         385 :     f = RgX_add(f, RgXn_mul(f, RgX_sub(RgXn_red_shallow(h, n), RgX_integ(w)), n));
    2264         385 :     if (gc_needed(av2,2))
    2265             :     {
    2266           0 :       if(DEBUGMEM>1) pari_warn(warnmem,"RgXn_exp, e = %ld", n);
    2267           0 :       gerepileall(av2, 2, &f, &g);
    2268             :     }
    2269             :   }
    2270         203 :   return gerepileupto(av, f);
    2271             : }
    2272             : 
    2273             : GEN
    2274          84 : RgXn_reverse(GEN f, long e)
    2275             : {
    2276          84 :   pari_sp av = avma, av2;
    2277             :   ulong mask;
    2278             :   GEN fi, a, df, W, an;
    2279          84 :   long v = varn(f), n=1;
    2280          84 :   if (degpol(f)<1 || !gequal0(gel(f,2)))
    2281           0 :     pari_err_INV("serreverse",f);
    2282          84 :   fi = ginv(gel(f,3));
    2283          84 :   a = deg1pol_shallow(fi,gen_0,v);
    2284          84 :   if (e <= 2) return gerepilecopy(av, a);
    2285          84 :   W = scalarpol(fi,v);
    2286          84 :   df = RgX_deriv(f);
    2287          84 :   mask = quadratic_prec_mask(e);
    2288          84 :   av2 = avma;
    2289         504 :   for (;mask>1;)
    2290             :   {
    2291             :     GEN u, fa, fr;
    2292         336 :     long n2 = n, rt;
    2293         336 :     n<<=1; if (mask & 1) n--;
    2294         336 :     mask >>= 1;
    2295         336 :     fr = RgXn_red_shallow(f, n);
    2296         336 :     rt = brent_kung_optpow(degpol(fr), 4, 3);
    2297         336 :     an = RgXn_powers(a, rt, n);
    2298         336 :     if (n>1)
    2299             :     {
    2300         336 :       long n4 = (n2+1)>>1;
    2301         336 :       GEN dfr = RgXn_red_shallow(df, n2);
    2302         336 :       dfr = RgX_RgXnV_eval(dfr, RgXnV_red_shallow(an, n2), n2);
    2303         336 :       u = RgX_shift(RgX_Rg_sub(RgXn_mul(W, dfr, n2), gen_1), -n4);
    2304         336 :       W = RgX_sub(W, RgX_shift(RgXn_mul(u, W, n2-n4), n4));
    2305             :     }
    2306         336 :     fa = RgX_sub(RgX_RgXnV_eval(fr, an, n), pol_x(v));
    2307         336 :     fa = RgX_shift(fa, -n2);
    2308         336 :     a = RgX_sub(a, RgX_shift(RgXn_mul(W, fa, n-n2), n2));
    2309         336 :     if (gc_needed(av2,2))
    2310             :     {
    2311           0 :       if(DEBUGMEM>1) pari_warn(warnmem,"RgXn_reverse, e = %ld", n);
    2312           0 :       gerepileall(av2, 2, &a, &W);
    2313             :     }
    2314             :   }
    2315          84 :   return gerepileupto(av, a);
    2316             : }
    2317             : 
    2318             : /* x,T in Rg[X], n in N, compute lift(x^n mod T)) */
    2319             : GEN
    2320      180493 : RgXQ_powu(GEN x, ulong n, GEN T)
    2321             : {
    2322             :   pari_sp av;
    2323             :   GEN y;
    2324             : 
    2325      180493 :   if (!n) return pol_1(varn(x));
    2326      178960 :   if (n == 1) return RgX_copy(x);
    2327      121126 :   av = avma;
    2328      121126 :   y = gen_powu(x, n, (void*)T, &_sqr, &_mul);
    2329      121127 :   return gerepileupto(av, y);
    2330             : }
    2331             : /* x,T in Rg[X], n in N, compute lift(x^n mod T)) */
    2332             : GEN
    2333       17408 : RgXQ_pow(GEN x, GEN n, GEN T)
    2334             : {
    2335             :   pari_sp av;
    2336       17408 :   long s = signe(n);
    2337             :   GEN y;
    2338             : 
    2339       17408 :   if (!s) return pol_1(varn(x));
    2340       17408 :   if (is_pm1(n) == 1)
    2341           0 :     return (s < 0)? RgXQ_inv(x, T): RgX_copy(x);
    2342       17408 :   av = avma;
    2343       17408 :   if (s < 0) x = RgXQ_inv(x, T);
    2344       17408 :   y = gen_pow(x, n, (void*)T, &_sqr, &_mul);
    2345       17408 :   return gerepileupto(av, y);
    2346             : }
    2347             : 
    2348             : /* generates the list of powers of x of degree 0,1,2,...,l*/
    2349             : GEN
    2350        1743 : RgXQ_powers(GEN x, long l, GEN T)
    2351             : {
    2352        1743 :   int use_sqr = 2*degpol(x) >= degpol(T);
    2353        1743 :   return gen_powers(x, l, use_sqr, (void *)T,_sqr,_mul,_one);
    2354             : }
    2355             : 
    2356             : /* a in K = Q[X]/(T), returns [a^0, ..., a^n] */
    2357             : GEN
    2358        1435 : QXQ_powers(GEN a, long n, GEN T)
    2359             : {
    2360        1435 :   GEN den, v = RgXQ_powers(Q_remove_denom(a, &den), n, T);
    2361             :   /* den*a integral; v[i+1] = (den*a)^i in K */
    2362        1435 :   if (den)
    2363             :   { /* restore denominators */
    2364         868 :     GEN d = den;
    2365             :     long i;
    2366         868 :     gel(v,2) = a;
    2367        3325 :     for (i=3; i<=n+1; i++) {
    2368        2457 :       d = mulii(d,den);
    2369        2457 :       gel(v,i) = RgX_Rg_div(gel(v,i), d);
    2370             :     }
    2371             :   }
    2372        1435 :   return v;
    2373             : }
    2374             : 
    2375             : static GEN
    2376         847 : do_QXQ_eval(GEN v, long imin, GEN a, GEN T)
    2377             : {
    2378         847 :   long l, i, m = 0;
    2379             :   GEN dz, z;
    2380         847 :   GEN V = cgetg_copy(v, &l);
    2381        2779 :   for (i = imin; i < l; i++)
    2382             :   {
    2383        1932 :     GEN c = gel(v, i);
    2384        1932 :     if (typ(c) == t_POL) m = maxss(m, degpol(c));
    2385             :   }
    2386         847 :   z = Q_remove_denom(QXQ_powers(a, m, T), &dz);
    2387         847 :   for (i = 1; i < imin; i++) V[i] = v[i];
    2388        2779 :   for (i = imin; i < l; i++)
    2389             :   {
    2390        1932 :     GEN c = gel(v,i);
    2391        1932 :     if (typ(c) == t_POL) c = QX_ZXQV_eval(c, z, dz);
    2392        1932 :     gel(V,i) = c;
    2393             :   }
    2394         847 :   return V;
    2395             : }
    2396             : /* [ s(a mod T) | s <- lift(v) ], a,T are QX, v a QXV */
    2397             : GEN
    2398         784 : QXV_QXQ_eval(GEN v, GEN a, GEN T)
    2399         784 : { return do_QXQ_eval(v, 1, a, T); }
    2400             : GEN
    2401          63 : QXX_QXQ_eval(GEN v, GEN a, GEN T)
    2402          63 : { return normalizepol(do_QXQ_eval(v, 2, a, T)); }
    2403             : 
    2404             : GEN
    2405         287 : RgXQ_matrix_pow(GEN y, long n, long m, GEN P)
    2406             : {
    2407         287 :   return RgXV_to_RgM(RgXQ_powers(y,m-1,P),n);
    2408             : }
    2409             : 
    2410             : GEN
    2411          56 : RgXQ_minpoly_naive(GEN y, GEN P)
    2412             : {
    2413          56 :   pari_sp ltop=avma;
    2414          56 :   long n=lgpol(P);
    2415          56 :   GEN M=ker(RgXQ_matrix_pow(y,n,n,P));
    2416          56 :   M=content(RgM_to_RgXV(M,varn(P)));
    2417          56 :   return gerepileupto(ltop,M);
    2418             : }
    2419             : 
    2420             : GEN
    2421       32757 : RgXQ_norm(GEN x, GEN T)
    2422             : {
    2423             :   pari_sp av;
    2424       32757 :   long dx = degpol(x);
    2425             :   GEN L, y;
    2426             : 
    2427       32757 :   av = avma; y = resultant(T, x);
    2428       32757 :   L = leading_coeff(T);
    2429       32757 :   if (gequal1(L) || !signe(x)) return y;
    2430           0 :   return gerepileupto(av, gdiv(y, gpowgs(L, dx)));
    2431             : }
    2432             : 
    2433             : GEN
    2434       89865 : RgX_blocks(GEN P, long n, long m)
    2435             : {
    2436       89865 :   GEN z = cgetg(m+1,t_VEC);
    2437       89865 :   long i,j, k=2, l = lg(P);
    2438      463047 :   for(i=1; i<=m; i++)
    2439             :   {
    2440      373182 :     GEN zi = cgetg(n+2,t_POL);
    2441      373182 :     zi[1] = P[1];
    2442      373182 :     gel(z,i) = zi;
    2443     2287477 :     for(j=2; j<n+2; j++)
    2444     1914295 :       gel(zi, j) = k==l ? gen_0 : gel(P,k++);
    2445      373182 :     zi = RgX_renormalize_lg(zi, n+2);
    2446             :   }
    2447       89865 :   return z;
    2448             : }
    2449             : 
    2450             : /* write p(X) = e(X^2) + Xo(X^2), shallow function */
    2451             : void
    2452       24602 : RgX_even_odd(GEN p, GEN *pe, GEN *po)
    2453             : {
    2454       24602 :   long n = degpol(p), v = varn(p), n0, n1, i;
    2455             :   GEN p0, p1;
    2456             : 
    2457       49205 :   if (n <= 0) { *pe = RgX_copy(p); *po = zeropol(v); return; }
    2458             : 
    2459       24602 :   n0 = (n>>1)+1; n1 = n+1 - n0; /* n1 <= n0 <= n1+1 */
    2460       24602 :   p0 = cgetg(n0+2, t_POL); p0[1] = evalvarn(v)|evalsigne(1);
    2461       24602 :   p1 = cgetg(n1+2, t_POL); p1[1] = evalvarn(v)|evalsigne(1);
    2462      637786 :   for (i=0; i<n1; i++)
    2463             :   {
    2464      613183 :     p0[2+i] = p[2+(i<<1)];
    2465      613183 :     p1[2+i] = p[3+(i<<1)];
    2466             :   }
    2467       24603 :   if (n1 != n0)
    2468       17324 :     p0[2+i] = p[2+(i<<1)];
    2469       24603 :   *pe = normalizepol(p0);
    2470       24601 :   *po = normalizepol(p1);
    2471             : }
    2472             : 
    2473             : /* write p(X) = a_0(X^k) + Xa_1(X^k) + ... + X^(k-1)a_{k-1}(X^k), shallow function */
    2474             : GEN
    2475       40642 : RgX_splitting(GEN p, long k)
    2476             : {
    2477       40642 :   long n = degpol(p), v = varn(p), m, i, j, l;
    2478             :   GEN r;
    2479             : 
    2480       40642 :   m = n/k;
    2481       40642 :   r = cgetg(k+1,t_VEC);
    2482      224154 :   for(i=1; i<=k; i++)
    2483             :   {
    2484      183512 :     gel(r,i) = cgetg(m+3, t_POL);
    2485      183512 :     mael(r,i,1) = evalvarn(v)|evalsigne(1);
    2486             :   }
    2487      552986 :   for (j=1, i=0, l=2; i<=n; i++)
    2488             :   {
    2489      512344 :     gmael(r,j,l) = gel(p,2+i);
    2490      512344 :     if (j==k) { j=1; l++; } else j++;
    2491             :   }
    2492      224154 :   for(i=1; i<=k; i++)
    2493      183512 :     gel(r,i) = normalizepol_lg(gel(r,i),i<j?l+1:l);
    2494       40642 :   return r;
    2495             : }
    2496             : 
    2497             : /*******************************************************************/
    2498             : /*                                                                 */
    2499             : /*                        Kronecker form                           */
    2500             : /*                                                                 */
    2501             : /*******************************************************************/
    2502             : 
    2503             : /* z in R[Y] representing an elt in R[X,Y] mod T(Y) in Kronecker form,
    2504             :  * i.e subst(lift(z), x, y^(2deg(z)-1)). Recover the "real" z, with
    2505             :  * normalized coefficients */
    2506             : GEN
    2507         189 : Kronecker_to_mod(GEN z, GEN T)
    2508             : {
    2509         189 :   long i,j,lx,l = lg(z), N = (degpol(T)<<1) + 1;
    2510         189 :   GEN x, t = cgetg(N,t_POL);
    2511         189 :   t[1] = T[1];
    2512         189 :   lx = (l-2) / (N-2); x = cgetg(lx+3,t_POL);
    2513         189 :   x[1] = z[1];
    2514         189 :   T = RgX_copy(T);
    2515        4389 :   for (i=2; i<lx+2; i++, z+= N-2)
    2516             :   {
    2517        4200 :     for (j=2; j<N; j++) gel(t,j) = gel(z,j);
    2518        4200 :     gel(x,i) = mkpolmod(RgX_rem(normalizepol_lg(t,N), T), T);
    2519             :   }
    2520         189 :   N = (l-2) % (N-2) + 2;
    2521         189 :   for (j=2; j<N; j++) t[j] = z[j];
    2522         189 :   gel(x,i) = mkpolmod(RgX_rem(normalizepol_lg(t,N), T), T);
    2523         189 :   return normalizepol_lg(x, i+1);
    2524             : }

Generated by: LCOV version 1.11