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 20277-2bd9113) Lines: 1272 1381 92.1 %
Date: 2017-02-21 05:49:51 Functions: 139 150 92.7 %
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     1948274 : brent_kung_optpow(long d, long n, long m)
      29             : {
      30             :   long p, r;
      31     1948274 :   long pold=1, rold=n*(d-1);
      32    11823174 :   for(p=2; p<=d; p++)
      33             :   {
      34     9874900 :     r = m*(p-1) + n*((d-1)/p);
      35     9874900 :     if (r<rold) { pold=p; rold=r; }
      36             :   }
      37     1948274 :   return pold;
      38             : }
      39             : 
      40             : static GEN
      41     8741401 : 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     8741401 :   pari_sp av = avma;
      45             :   long i;
      46     8741401 :   GEN z = cmul(E,P,a,ff->one(E));
      47     8741323 :   if (!z) z = gen_0;
      48    57250048 :   for (i=1; i<=n; i++)
      49             :   {
      50    48508665 :     GEN t = cmul(E,P,a+i,gel(V,i+1));
      51    48508893 :     if (t) {
      52    47253711 :       z = ff->add(E, z, t);
      53    47253402 :       if (gc_needed(av,2)) z = gerepileupto(av, z);
      54             :     }
      55             :   }
      56     8741383 :   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     5420571 : 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     5420571 :   pari_sp av = avma;
      69     5420571 :   long l = lg(V)-1;
      70             :   GEN z, u;
      71             : 
      72     5420571 :   if (d < 0) return ff->zero(E);
      73     4946123 :   if (d < l) return gerepileupto(av, gen_RgXQ_eval_powers(P,V,0,d,E,ff,cmul));
      74     2239563 :   if (l<2) pari_err_DOMAIN("gen_RgX_bkeval_powers", "#powers", "<",gen_2,V);
      75     2239563 :   d -= l;
      76     2239563 :   z = gen_RgXQ_eval_powers(P,V,d+1,l-1,E,ff,cmul);
      77     6034848 :   while (d >= l-1)
      78             :   {
      79     1555725 :     d -= l-1;
      80     1555725 :     u = gen_RgXQ_eval_powers(P,V,d+1,l-2,E,ff,cmul);
      81     1555695 :     z = ff->add(E,u, ff->mul(E,z,gel(V,l)));
      82     1555721 :     if (gc_needed(av,2))
      83          61 :       z = gerepileupto(av, z);
      84             :   }
      85     2239563 :   u = gen_RgXQ_eval_powers(P,V,0,d,E,ff,cmul);
      86     2239559 :   z = ff->add(E,u, ff->mul(E,z,gel(V,d+2)));
      87     2239562 :   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     2239562 :   return gerepileupto(av, ff->red(E,z));
      93             : }
      94             : 
      95             : GEN
      96     1031498 : 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     1031498 :   pari_sp av = avma;
     100             :   GEN z, V;
     101             :   long rtd;
     102     1031498 :   if (d < 0) return ff->zero(E);
     103     1031393 :   rtd = (long) sqrt((double)d);
     104     1031393 :   V = gen_powers(x,rtd,use_sqr,E,ff->sqr,ff->mul,ff->one);
     105     1031393 :   z = gen_bkeval_powers(Q, d, V, E, ff, cmul);
     106     1031391 :   return gerepileupto(av, z);
     107             : }
     108             : 
     109             : static GEN
     110      537533 : _gen_nored(void *E, GEN x) { (void)E; return x; }
     111             : static GEN
     112    20247973 : _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      541067 : _gen_mul(void *E, GEN x, GEN y) { (void)E; return gmul(x, y); }
     117             : static GEN
     118      173833 : _gen_sqr(void *E, GEN x) { (void)E; return gsqr(x); }
     119             : static GEN
     120      547767 : _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       70998 : get_Rg_algebra(void)
     158             : {
     159       70998 :   return &Rg_algebra;
     160             : }
     161             : 
     162             : /*******************************************************************/
     163             : /*                                                                 */
     164             : /*                         RgX                                     */
     165             : /*                                                                 */
     166             : /*******************************************************************/
     167             : 
     168             : long
     169     3983182 : RgX_equal(GEN x, GEN y)
     170             : {
     171     3983182 :   long i = lg(x);
     172             : 
     173     3983182 :   if (i != lg(y)) return 0;
     174    20528205 :   for (i--; i > 1; i--)
     175    16605958 :     if (!gequal(gel(x,i),gel(y,i))) return 0;
     176     3922247 :   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      568713 : RgX_get_1(GEN x)
     183             : {
     184             :   GEN p, T;
     185      568713 :   long i, lx, tx = RgX_type(x, &p, &T, &lx);
     186      568713 :   if (RgX_type_is_composite(tx))
     187        1211 :     RgX_type_decode(tx, &i /*junk*/, &tx);
     188      568713 :   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      568643 :     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        1729 : QX_ZXQV_eval(GEN P, GEN V, GEN dV)
     216             : {
     217        1729 :   long i, n = degpol(P);
     218             :   GEN z, dz, dP;
     219        1729 :   if (n < 0) return gen_0;
     220        1729 :   P = Q_remove_denom(P, &dP);
     221        1729 :   z = gel(P,2); if (n == 0) return icopy(z);
     222         952 :   if (dV) z = mulii(dV, z); /* V[1] = dV */
     223         952 :   z = ZX_Z_add_shallow(ZX_Z_mul(gel(V,2),gel(P,3)), z);
     224         952 :   for (i=2; i<=n; i++) z = ZX_add(ZX_Z_mul(gel(V,i+1),gel(P,2+i)), z);
     225         952 :   dz = mul_denom(dP, dV);
     226         952 :   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        7965 : ZX_unscale(GEN P, GEN h)
     248             : {
     249        7965 :   long i, l = lg(P);
     250        7965 :   GEN Q = cgetg(l, t_POL);
     251        7965 :   Q[1] = P[1];
     252        7965 :   if (l == 2) return Q;
     253        7965 :   gel(Q,2) = gel(P,2);
     254        7965 :   if (l == 3) return Q;
     255        7965 :   if (equalim1(h))
     256      297134 :     for (i=3; i<l; i++)
     257             :     {
     258      293052 :       gel(Q,i) = negi(gel(P,i));
     259      293052 :       if (++i == l) break;
     260      290401 :       gel(Q,i) = gel(P,i);
     261             :     }
     262             :   else
     263             :   {
     264        1232 :     GEN hi = h;
     265        1232 :     gel(Q,3) = mulii(gel(P,3), hi);
     266        6524 :     for (i=4; i<l; i++)
     267             :     {
     268        5292 :       hi = mulii(hi,h);
     269        5292 :       gel(Q,i) = mulii(gel(P,i), hi);
     270             :     }
     271             :   }
     272        7965 :   return Q;
     273             : }
     274             : /* P a ZX. Return P(x << n), not memory clean */
     275             : GEN
     276        9682 : ZX_unscale2n(GEN P, long n)
     277             : {
     278        9682 :   long i, ni = n, l = lg(P);
     279        9682 :   GEN Q = cgetg(l, t_POL);
     280        9682 :   Q[1] = P[1];
     281        9682 :   if (l == 2) return Q;
     282        9682 :   gel(Q,2) = gel(P,2);
     283        9682 :   if (l == 3) return Q;
     284        9682 :   gel(Q,3) = shifti(gel(P,3), ni);
     285       48844 :   for (i=4; i<l; i++)
     286             :   {
     287       39162 :     ni += n;
     288       39162 :     gel(Q,i) = shifti(gel(P,i), ni);
     289             :   }
     290        9682 :   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       73706 : RgX_deflate(GEN x0, long d)
     344             : {
     345             :   GEN z, y, x;
     346       73706 :   long i,id, dy, dx = degpol(x0);
     347       73706 :   if (d == 1 || dx <= 0) return leafcopy(x0);
     348       49927 :   dy = dx/d;
     349       49927 :   y = cgetg(dy+3, t_POL); y[1] = x0[1];
     350       49927 :   z = y + 2;
     351       49927 :   x = x0+ 2;
     352       49927 :   for (i=id=0; i<=dy; i++,id+=d) gel(z,i) = gel(x,id);
     353       49927 :   return y;
     354             : }
     355             : 
     356             : /* return x0(X^d) */
     357             : GEN
     358      109592 : RgX_inflate(GEN x0, long d)
     359             : {
     360      109592 :   long i, id, dy, dx = degpol(x0);
     361      109592 :   GEN x = x0 + 2, z, y;
     362      109592 :   if (dx <= 0) return leafcopy(x0);
     363      109004 :   dy = dx*d;
     364      109004 :   y = cgetg(dy+3, t_POL); y[1] = x0[1];
     365      109005 :   z = y + 2;
     366      109005 :   for (i=0; i<=dy; i++) gel(z,i) = gen_0;
     367      109005 :   for (i=id=0; i<=dx; i++,id+=d) gel(z,id) = gel(x,i);
     368      109005 :   return y;
     369             : }
     370             : 
     371             : /* return P(X + c) using destructive Horner, optimize for c = 1,-1 */
     372             : GEN
     373     1008747 : RgX_translate(GEN P, GEN c)
     374             : {
     375     1008747 :   pari_sp av = avma;
     376             :   GEN Q, *R;
     377             :   long i, k, n;
     378             : 
     379     1008747 :   if (!signe(P) || gequal0(c)) return RgX_copy(P);
     380     1005827 :   Q = leafcopy(P);
     381     1005827 :   R = (GEN*)(Q+2); n = degpol(P);
     382     1005827 :   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     1005554 :   else if (gequalm1(c))
     395             :   {
     396      133280 :     for (i=1; i<=n; i++)
     397             :     {
     398      114114 :       for (k=n-i; k<n; k++) R[k] = gsub(R[k], R[k+1]);
     399      114114 :       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     3360127 :     for (i=1; i<=n; i++)
     409             :     {
     410     2373739 :       for (k=n-i; k<n; k++) R[k] = gadd(R[k], gmul(c, R[k+1]));
     411     2373739 :       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     1005827 :   return gerepilecopy(av, Q);
     419             : }
     420             : 
     421             : /* return P(X + c) using destructive Horner, optimize for c = 1,-1 */
     422             : GEN
     423       44669 : ZX_translate(GEN P, GEN c)
     424             : {
     425       44669 :   pari_sp av = avma;
     426             :   GEN Q, *R;
     427             :   long i, k, n;
     428             : 
     429       44669 :   if (!signe(P) || !signe(c)) return ZX_copy(P);
     430       44634 :   Q = leafcopy(P);
     431       44634 :   R = (GEN*)(Q+2); n = degpol(P);
     432       44634 :   if (equali1(c))
     433             :   {
     434      707611 :     for (i=1; i<=n; i++)
     435             :     {
     436      668817 :       for (k=n-i; k<n; k++) R[k] = addii(R[k], R[k+1]);
     437      668817 :       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        5840 :   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       88915 :     for (i=1; i<=n; i++)
     459             :     {
     460       83096 :       for (k=n-i; k<n; k++) R[k] = addii(R[k], mulii(c, R[k+1]));
     461       83096 :       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       44634 :   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       14375 : QXQ_to_mod_copy(GEN x, GEN T)
     507             : {
     508             :   long d;
     509       14375 :   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        8880 :       d = degpol(x);
     515        8880 :       if (d < 0) return gen_0;
     516        8607 :       if (d == 0) return gcopy(gel(x,2));
     517        8292 :       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        1037 : QXQV_to_mod(GEN V, GEN T)
     571             : {
     572        1037 :   long i, l = lg(V);
     573        1037 :   GEN z = cgetg(l, t_VEC); T = ZX_copy(T);
     574        1037 :   for (i=1;i<l; i++) gel(z,i) = QXQ_to_mod_copy(gel(V,i), T);
     575        1037 :   return z;
     576             : }
     577             : 
     578             : GEN
     579      653296 : RgX_renormalize_lg(GEN x, long lx)
     580             : {
     581             :   long i;
     582     1865808 :   for (i = lx-1; i>1; i--)
     583     1764091 :     if (! gequal0(gel(x,i))) break; /* _not_ isexactzero */
     584      653296 :   stackdummy((pari_sp)(x + lg(x)), (pari_sp)(x + i+1));
     585      653296 :   setlg(x, i+1); setsigne(x, i != 1); return x;
     586             : }
     587             : 
     588             : GEN
     589      359858 : RgV_to_RgX(GEN x, long v)
     590             : {
     591      359858 :   long i, k = lg(x);
     592             :   GEN p;
     593             : 
     594      359858 :   while (--k && gequal0(gel(x,k)));
     595      359858 :   if (!k) return pol_0(v);
     596      359480 :   i = k+2; p = cgetg(i,t_POL);
     597      359480 :   p[1] = evalsigne(1) | evalvarn(v);
     598      359480 :   x--; for (k=2; k<i; k++) gel(p,k) = gel(x,k);
     599      359480 :   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     3378796 : RgX_to_RgC(GEN x, long N)
     622             : {
     623             :   long i, l;
     624             :   GEN z;
     625     3378796 :   l = lg(x)-1; x++;
     626     3378796 :   if (l > N+1) l = N+1; /* truncate higher degree terms */
     627     3378796 :   z = cgetg(N+1,t_COL);
     628     3378796 :   for (i=1; i<l ; i++) gel(z,i) = gel(x,i);
     629     3378796 :   for (   ; i<=N; i++) gel(z,i) = gen_0;
     630     3378796 :   return z;
     631             : }
     632             : GEN
     633       25809 : Rg_to_RgC(GEN x, long N)
     634             : {
     635       25809 :   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       35383 : RgM_to_RgXV(GEN x, long v)
     641             : {
     642       35383 :   long j, lx = lg(x);
     643       35383 :   GEN y = cgetg(lx, t_VEC);
     644       35383 :   for (j=1; j<lx; j++) gel(y,j) = RgV_to_RgX(gel(x,j), v);
     645       35383 :   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        6202 : RgV_to_RgM(GEN v, long n)
     652             : {
     653        6202 :   long j, N = lg(v);
     654        6202 :   GEN y = cgetg(N, t_MAT);
     655        6202 :   for (j=1; j<N; j++) gel(y,j) = Rg_to_RgC(gel(v,j), n);
     656        6202 :   return y;
     657             : }
     658             : GEN
     659        5355 : RgXV_to_RgM(GEN v, long n)
     660             : {
     661        5355 :   long j, N = lg(v);
     662        5355 :   GEN y = cgetg(N, t_MAT);
     663        5355 :   for (j=1; j<N; j++) gel(y,j) = RgX_to_RgC(gel(v,j), n);
     664        5355 :   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       12978 : RgXY_swapspec(GEN x, long n, long w, long nx)
     693             : {
     694       12978 :   long j, ly = n+3;
     695       12978 :   GEN y = cgetg(ly, t_POL);
     696       12978 :   y[1] = evalsigne(1);
     697      192999 :   for (j=2; j<ly; j++)
     698             :   {
     699             :     long k;
     700      180021 :     GEN a = cgetg(nx+2,t_POL);
     701      180021 :     a[1] = evalsigne(1) | evalvarn(w);
     702      961296 :     for (k=0; k<nx; k++)
     703             :     {
     704      781275 :       GEN xk = gel(x,k);
     705      781275 :       if (typ(xk)==t_POL)
     706      695770 :         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      180021 :     gel(y,j) = normalizepol_lg(a, nx+2);
     711             :   }
     712       12978 :   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        7856 : RgXn_red_shallow(GEN a, long n)
     740             : {
     741        7856 :   long i, L, l = lg(a);
     742             :   GEN  b;
     743        7856 :   if (l == 2 || !n) return pol_0(varn(a));
     744        7856 :   L = n+2; if (L > l) L = l;
     745        7856 :   b = cgetg(L, t_POL); b[1] = a[1];
     746        7856 :   for (i=2; i<L; i++) gel(b,i) = gel(a,i);
     747        7856 :   return normalizepol_lg(b,L);
     748             : }
     749             : 
     750             : GEN
     751         336 : RgXnV_red_shallow(GEN P, long n)
     752             : {
     753         336 :   long i, l = lg(P);
     754         336 :   GEN Q = cgetg(l, t_VEC);
     755         336 :   for (i=1; i<l; i++) gel(Q,i) = RgXn_red_shallow(gel(P,i), n);
     756         336 :   return Q;
     757             : }
     758             : 
     759             : /* return (x * X^n). Shallow */
     760             : GEN
     761    55595985 : RgX_shift_shallow(GEN a, long n)
     762             : {
     763    55595985 :   long i, l = lg(a);
     764             :   GEN  b;
     765    55595985 :   if (l == 2 || !n) return a;
     766    41223976 :   l += n;
     767    41223976 :   if (n < 0)
     768             :   {
     769    37206865 :     if (l <= 2) return pol_0(varn(a));
     770    37205948 :     b = cgetg(l, t_POL); b[1] = a[1];
     771    37205948 :     a -= n;
     772    37205948 :     for (i=2; i<l; i++) gel(b,i) = gel(a,i);
     773             :   } else {
     774     4017111 :     b = cgetg(l, t_POL); b[1] = a[1];
     775     4017111 :     a -= n; n += 2;
     776     4017111 :     for (i=2; i<n; i++) gel(b,i) = gen_0;
     777     4017111 :     for (   ; i<l; i++) gel(b,i) = gel(a,i);
     778             :   }
     779    41223059 :   return b;
     780             : }
     781             : /* return (x * X^n). */
     782             : GEN
     783     3393144 : RgX_shift(GEN a, long n)
     784             : {
     785     3393144 :   long i, l = lg(a);
     786             :   GEN  b;
     787     3393144 :   if (l == 2 || !n) return RgX_copy(a);
     788     3392920 :   l += n;
     789     3392920 :   if (n < 0)
     790             :   {
     791         595 :     if (l <= 2) return pol_0(varn(a));
     792         553 :     b = cgetg(l, t_POL); b[1] = a[1];
     793         553 :     a -= n;
     794         553 :     for (i=2; i<l; i++) gel(b,i) = gcopy(gel(a,i));
     795             :   } else {
     796     3392325 :     b = cgetg(l, t_POL); b[1] = a[1];
     797     3392325 :     a -= n; n += 2;
     798     3392325 :     for (i=2; i<n; i++) gel(b,i) = gen_0;
     799     3392325 :     for (   ; i<l; i++) gel(b,i) = gcopy(gel(a,i));
     800             :   }
     801     3392878 :   return b;
     802             : }
     803             : 
     804             : GEN
     805      315777 : RgX_rotate_shallow(GEN P, long k, long p)
     806             : {
     807      315777 :   long i, l = lgpol(P);
     808             :   GEN r;
     809      315777 :   if (signe(P)==0)
     810         427 :     return pol_0(varn(P));
     811      315350 :   r = cgetg(p+2,t_POL); r[1] = P[1];
     812     2095422 :   for(i=0; i<p; i++)
     813             :   {
     814     1780072 :     long s = 2+(i+k)%p;
     815     1780072 :     gel(r,s) = i<l? gel(P,2+i): gen_0;
     816             :   }
     817      315350 :   return RgX_renormalize(r);
     818             : }
     819             : 
     820             : GEN
     821     2829272 : RgX_mulXn(GEN x, long d)
     822             : {
     823             :   pari_sp av;
     824             :   GEN z;
     825             :   long v;
     826     2829272 :   if (d >= 0) return RgX_shift(x, d);
     827     1335917 :   d = -d;
     828     1335917 :   v = RgX_val(x);
     829     1335917 :   if (v >= d) return RgX_shift(x, -d);
     830     1335910 :   av = avma;
     831     1335910 :   z = gred_rfrac_simple(RgX_shift_shallow(x, -v), pol_xn(d - v, varn(x)));
     832     1335910 :   return gerepileupto(av, z);
     833             : }
     834             : 
     835             : long
     836     2316767 : RgX_val(GEN x)
     837             : {
     838     2316767 :   long i, lx = lg(x);
     839     2316767 :   if (lx == 2) return LONG_MAX;
     840     2338187 :   for (i = 2; i < lx; i++)
     841     2338187 :     if (!isexactzero(gel(x,i))) break;
     842     2316753 :   if (i == lx) i--; /* possible with non-rational zeros */
     843     2316753 :   return i - 2;
     844             : }
     845             : long
     846    41275309 : RgX_valrem(GEN x, GEN *Z)
     847             : {
     848    41275309 :   long v, i, lx = lg(x);
     849    41275309 :   if (lx == 2) { *Z = pol_0(varn(x)); return LONG_MAX; }
     850    80227805 :   for (i = 2; i < lx; i++)
     851    80227805 :     if (!isexactzero(gel(x,i))) break;
     852    41275309 :   if (i == lx) i--; /* possible with non-rational zeros */
     853    41275309 :   v = i - 2;
     854    41275309 :   *Z = RgX_shift_shallow(x, -v);
     855    41275309 :   return v;
     856             : }
     857             : long
     858        3054 : RgX_valrem_inexact(GEN x, GEN *Z)
     859             : {
     860             :   long v;
     861        3054 :   if (!signe(x)) { if (Z) *Z = pol_0(varn(x)); return LONG_MAX; }
     862        3334 :   for (v = 0;; v++)
     863        3334 :     if (!gequal0(gel(x,2+v))) break;
     864         287 :   if (Z) *Z = RgX_shift_shallow(x, -v);
     865        3047 :   return v;
     866             : }
     867             : 
     868             : GEN
     869           0 : RgXQC_red(GEN P, GEN T)
     870             : {
     871           0 :   long i, l = lg(P);
     872           0 :   GEN Q = cgetg(l, t_COL);
     873           0 :   for (i=1; i<l; i++) gel(Q,i) = grem(gel(P,i), T);
     874           0 :   return Q;
     875             : }
     876             : 
     877             : GEN
     878          56 : RgXQV_red(GEN P, GEN T)
     879             : {
     880          56 :   long i, l = lg(P);
     881          56 :   GEN Q = cgetg(l, t_VEC);
     882          56 :   for (i=1; i<l; i++) gel(Q,i) = grem(gel(P,i), T);
     883          56 :   return Q;
     884             : }
     885             : 
     886             : GEN
     887           0 : RgXQM_red(GEN P, GEN T)
     888             : {
     889           0 :   long i, l = lg(P);
     890           0 :   GEN Q = cgetg(l, t_MAT);
     891           0 :   for (i=1; i<l; i++) gel(Q,i) = RgXQC_red(gel(P,i), T);
     892           0 :   return Q;
     893             : }
     894             : 
     895             : GEN
     896           0 : RgXQM_mul(GEN P, GEN Q, GEN T)
     897             : {
     898           0 :   return RgXQM_red(RgM_mul(P, Q), T);
     899             : }
     900             : 
     901             : GEN
     902        5530 : RgXQX_red(GEN P, GEN T)
     903             : {
     904        5530 :   long i, l = lg(P);
     905        5530 :   GEN Q = cgetg(l, t_POL);
     906        5530 :   Q[1] = P[1];
     907        5530 :   for (i=2; i<l; i++) gel(Q,i) = grem(gel(P,i), T);
     908        5530 :   return normalizepol_lg(Q, l);
     909             : }
     910             : 
     911             : GEN
     912      265087 : RgX_deriv(GEN x)
     913             : {
     914      265087 :   long i,lx = lg(x)-1;
     915             :   GEN y;
     916             : 
     917      265087 :   if (lx<3) return pol_0(varn(x));
     918      263715 :   y = cgetg(lx,t_POL); gel(y,2) = gcopy(gel(x,3));
     919      263715 :   for (i=3; i<lx ; i++) gel(y,i) = gmulsg(i-1,gel(x,i+1));
     920      263715 :   y[1] = x[1]; return normalizepol_lg(y,i);
     921             : }
     922             : 
     923             : GEN
     924      287670 : RgX_recipspec_shallow(GEN x, long l, long n)
     925             : {
     926             :   long i;
     927      287670 :   GEN z=cgetg(n+2,t_POL)+2;
     928    13480427 :   for(i=0; i<l; i++)
     929    13192757 :     gel(z,n-i-1) = gel(x,i);
     930      375394 :   for(   ; i<n; i++)
     931       87724 :     gel(z, n-i-1) = gen_0;
     932      287670 :   return normalizepol_lg(z-2,n+2);
     933             : }
     934             : 
     935             : /* return coefficients s.t x = x_0 X^n + ... + x_n */
     936             : GEN
     937       60928 : RgX_recip(GEN x)
     938             : {
     939             :   long lx, i, j;
     940       60928 :   GEN y = cgetg_copy(x, &lx);
     941       60928 :   y[1] = x[1]; for (i=2,j=lx-1; i<lx; i++,j--) gel(y,i) = gcopy(gel(x,j));
     942       60928 :   return normalizepol_lg(y,lx);
     943             : }
     944             : /* shallow version */
     945             : GEN
     946      449365 : RgX_recip_shallow(GEN x)
     947             : {
     948             :   long lx, i, j;
     949      449365 :   GEN y = cgetg_copy(x, &lx);
     950      449383 :   y[1] = x[1]; for (i=2,j=lx-1; i<lx; i++,j--) gel(y,i) = gel(x,j);
     951      449383 :   return y;
     952             : }
     953             : /*******************************************************************/
     954             : /*                                                                 */
     955             : /*                      ADDITION / SUBTRACTION                     */
     956             : /*                                                                 */
     957             : /*******************************************************************/
     958             : /* same variable */
     959             : GEN
     960    16440030 : RgX_add(GEN x, GEN y)
     961             : {
     962    16440030 :   long i, lx = lg(x), ly = lg(y);
     963             :   GEN z;
     964    16440030 :   if (ly <= lx) {
     965    14776907 :     z = cgetg(lx,t_POL); z[1] = x[1];
     966    14776911 :     for (i=2; i < ly; i++) gel(z,i) = gadd(gel(x,i),gel(y,i));
     967    14776907 :     for (   ; i < lx; i++) gel(z,i) = gcopy(gel(x,i));
     968    14776907 :     z = normalizepol_lg(z, lx);
     969             :   } else {
     970     1663123 :     z = cgetg(ly,t_POL); z[1] = y[1];
     971     1663130 :     for (i=2; i < lx; i++) gel(z,i) = gadd(gel(x,i),gel(y,i));
     972     1663123 :     for (   ; i < ly; i++) gel(z,i) = gcopy(gel(y,i));
     973     1663123 :     z = normalizepol_lg(z, ly);
     974             :   }
     975    16440029 :   return z;
     976             : }
     977             : GEN
     978     9645801 : RgX_sub(GEN x, GEN y)
     979             : {
     980     9645801 :   long i, lx = lg(x), ly = lg(y);
     981             :   GEN z;
     982     9645801 :   if (ly <= lx) {
     983     7808809 :     z = cgetg(lx,t_POL); z[1] = x[1];
     984     7808828 :     for (i=2; i < ly; i++) gel(z,i) = gsub(gel(x,i),gel(y,i));
     985     7808810 :     for (   ; i < lx; i++) gel(z,i) = gcopy(gel(x,i));
     986     7808810 :     z = normalizepol_lg(z, lx);
     987             :   } else {
     988     1836992 :     z = cgetg(ly,t_POL); z[1] = y[1];
     989     1836992 :     for (i=2; i < lx; i++) gel(z,i) = gsub(gel(x,i),gel(y,i));
     990     1836992 :     for (   ; i < ly; i++) gel(z,i) = gneg(gel(y,i));
     991     1836992 :     z = normalizepol_lg(z, ly);
     992             :   }
     993     9645801 :   return z;
     994             : }
     995             : GEN
     996     1162841 : RgX_neg(GEN x)
     997             : {
     998     1162841 :   long i, lx = lg(x);
     999     1162841 :   GEN y = cgetg(lx, t_POL); y[1] = x[1];
    1000     1162841 :   for (i=2; i<lx; i++) gel(y,i) = gneg(gel(x,i));
    1001     1162841 :   return y;
    1002             : }
    1003             : 
    1004             : GEN
    1005    10698427 : RgX_Rg_add(GEN y, GEN x)
    1006             : {
    1007             :   GEN z;
    1008    10698427 :   long lz = lg(y), i;
    1009    10698427 :   if (lz == 2) return scalarpol(x,varn(y));
    1010     9061129 :   z = cgetg(lz,t_POL); z[1] = y[1];
    1011     9061129 :   gel(z,2) = gadd(gel(y,2),x);
    1012     9061129 :   for(i=3; i<lz; i++) gel(z,i) = gcopy(gel(y,i));
    1013             :   /* probably useless unless lz = 3, but cannot be skipped if y is
    1014             :    * an inexact 0 */
    1015     9061129 :   return normalizepol_lg(z,lz);
    1016             : }
    1017             : GEN
    1018        2422 : RgX_Rg_add_shallow(GEN y, GEN x)
    1019             : {
    1020             :   GEN z;
    1021        2422 :   long lz = lg(y), i;
    1022        2422 :   if (lz == 2) return scalarpol(x,varn(y));
    1023        2422 :   z = cgetg(lz,t_POL); z[1] = y[1];
    1024        2422 :   gel(z,2) = gadd(gel(y,2),x);
    1025        2422 :   for(i=3; i<lz; i++) gel(z,i) = gel(y,i);
    1026        2422 :   return z = normalizepol_lg(z,lz);
    1027             : }
    1028             : GEN
    1029       32215 : RgX_Rg_sub(GEN y, GEN x)
    1030             : {
    1031             :   GEN z;
    1032       32215 :   long lz = lg(y), i;
    1033       32215 :   if (lz == 2)
    1034             :   { /* scalarpol(gneg(x),varn(y)) optimized */
    1035        3864 :     long v = varn(y);
    1036        3864 :     if (isrationalzero(x)) return pol_0(v);
    1037          14 :     z = cgetg(3,t_POL);
    1038          28 :     z[1] = gequal0(x)? evalvarn(v)
    1039          14 :                    : evalvarn(v) | evalsigne(1);
    1040          14 :     gel(z,2) = gneg(x); return z;
    1041             :   }
    1042       28351 :   z = cgetg(lz,t_POL); z[1] = y[1];
    1043       28351 :   gel(z,2) = gsub(gel(y,2),x);
    1044       28351 :   for(i=3; i<lz; i++) gel(z,i) = gcopy(gel(y,i));
    1045       28351 :   return z = normalizepol_lg(z,lz);
    1046             : }
    1047             : GEN
    1048      308804 : Rg_RgX_sub(GEN x, GEN y)
    1049             : {
    1050             :   GEN z;
    1051      308804 :   long lz = lg(y), i;
    1052      308804 :   if (lz == 2) return scalarpol(x,varn(y));
    1053      307789 :   z = cgetg(lz,t_POL); z[1] = y[1];
    1054      307789 :   gel(z,2) = gsub(x, gel(y,2));
    1055      307789 :   for(i=3; i<lz; i++) gel(z,i) = gneg(gel(y,i));
    1056      307789 :   return z = normalizepol_lg(z,lz);
    1057             : }
    1058             : /*******************************************************************/
    1059             : /*                                                                 */
    1060             : /*                  KARATSUBA MULTIPLICATION                       */
    1061             : /*                                                                 */
    1062             : /*******************************************************************/
    1063             : #if 0
    1064             : /* to debug Karatsuba-like routines */
    1065             : GEN
    1066             : zx_debug_spec(GEN x, long nx)
    1067             : {
    1068             :   GEN z = cgetg(nx+2,t_POL);
    1069             :   long i;
    1070             :   for (i=0; i<nx; i++) gel(z,i+2) = stoi(x[i]);
    1071             :   z[1] = evalsigne(1); return z;
    1072             : }
    1073             : 
    1074             : GEN
    1075             : RgX_debug_spec(GEN x, long nx)
    1076             : {
    1077             :   GEN z = cgetg(nx+2,t_POL);
    1078             :   long i;
    1079             :   for (i=0; i<nx; i++) z[i+2] = x[i];
    1080             :   z[1] = evalsigne(1); return z;
    1081             : }
    1082             : #endif
    1083             : 
    1084             : /* generic multiplication */
    1085             : 
    1086             : static GEN
    1087     2817713 : addpol(GEN x, GEN y, long lx, long ly)
    1088             : {
    1089             :   long i,lz;
    1090             :   GEN z;
    1091             : 
    1092     2817713 :   if (ly>lx) swapspec(x,y, lx,ly);
    1093     2817713 :   lz = lx+2; z = cgetg(lz,t_POL) + 2;
    1094     2817840 :   for (i=0; i<ly; i++) gel(z,i) = gadd(gel(x,i),gel(y,i));
    1095     2817707 :   for (   ; i<lx; i++) gel(z,i) = gel(x,i);
    1096     2817707 :   z -= 2; z[1]=0; return normalizepol_lg(z, lz);
    1097             : }
    1098             : 
    1099             : static GEN
    1100      294696 : addpolcopy(GEN x, GEN y, long lx, long ly)
    1101             : {
    1102             :   long i,lz;
    1103             :   GEN z;
    1104             : 
    1105      294696 :   if (ly>lx) swapspec(x,y, lx,ly);
    1106      294696 :   lz = lx+2; z = cgetg(lz,t_POL) + 2;
    1107      294714 :   for (i=0; i<ly; i++) gel(z,i) = gadd(gel(x,i),gel(y,i));
    1108      294703 :   for (   ; i<lx; i++) gel(z,i) = gcopy(gel(x,i));
    1109      294695 :   z -= 2; z[1]=0; return normalizepol_lg(z, lz);
    1110             : }
    1111             : 
    1112             : /* Return the vector of coefficients of x, where we replace rational 0s by NULL
    1113             :  * [ to speed up basic operation s += x[i]*y[j] ]. We create a proper
    1114             :  * t_VECSMALL, to hold this, which can be left on stack: gerepile
    1115             :  * will not crash on it. The returned vector itself is not a proper GEN,
    1116             :  * we access the coefficients as x[i], i = 0..deg(x) */
    1117             : static GEN
    1118    30894329 : RgXspec_kill0(GEN x, long lx)
    1119             : {
    1120    30894329 :   GEN z = cgetg(lx+1, t_VECSMALL) + 1; /* inhibit gerepile-wise */
    1121             :   long i;
    1122   130937686 :   for (i=0; i <lx; i++)
    1123             :   {
    1124   100043397 :     GEN c = gel(x,i);
    1125   100043397 :     z[i] = (long)(isrationalzero(c)? NULL: c);
    1126             :   }
    1127    30894289 :   return z;
    1128             : }
    1129             : 
    1130             : INLINE GEN
    1131    71583809 : RgX_mulspec_basecase_limb(GEN x, GEN y, long a, long b)
    1132             : {
    1133    71583809 :   pari_sp av = avma;
    1134    71583809 :   GEN s = NULL;
    1135             :   long i;
    1136             : 
    1137   283216479 :   for (i=a; i<b; i++)
    1138   211635735 :     if (gel(y,i) && gel(x,-i))
    1139             :     {
    1140   162508805 :       GEN t = gmul(gel(y,i), gel(x,-i));
    1141   162513214 :       s = s? gadd(s, t): t;
    1142             :     }
    1143    71580744 :   return s? gerepileupto(av, s): gen_0;
    1144             : }
    1145             : 
    1146             : /* assume nx >= ny > 0, return x * y * t^v */
    1147             : static GEN
    1148    12158667 : RgX_mulspec_basecase(GEN x, GEN y, long nx, long ny, long v)
    1149             : {
    1150             :   long i, lz, nz;
    1151             :   GEN z;
    1152             : 
    1153    12158667 :   x = RgXspec_kill0(x,nx);
    1154    12158653 :   y = RgXspec_kill0(y,ny);
    1155    12158654 :   lz = nx + ny + 1; nz = lz-2;
    1156    12158654 :   lz += v;
    1157    12158654 :   z = cgetg(lz, t_POL) + 2; /* x:y:z [i] = term of degree i */
    1158    12158730 :   for (i=0; i<v; i++) gel(z++, 0) = gen_0;
    1159    12158730 :   for (i=0; i<ny; i++)gel(z,i) = RgX_mulspec_basecase_limb(x+i,y, 0, i+1);
    1160    12158629 :   for (  ; i<nx; i++) gel(z,i) = RgX_mulspec_basecase_limb(x+i,y, 0,ny);
    1161    12158631 :   for (  ; i<nz; i++) gel(z,i) = RgX_mulspec_basecase_limb(x+i,y, i-nx+1,ny);
    1162    12158675 :   z -= v+2; z[1] = 0; return normalizepol_lg(z, lz);
    1163             : }
    1164             : 
    1165             : /* return (x * X^d) + y. Assume d > 0 */
    1166             : GEN
    1167     1864589 : addmulXn(GEN x, GEN y, long d)
    1168             : {
    1169             :   GEN xd, yd, zd;
    1170             :   long a, lz, nx, ny;
    1171             : 
    1172     1864589 :   if (!signe(x)) return y;
    1173     1799690 :   ny = lgpol(y);
    1174     1799691 :   nx = lgpol(x);
    1175     1799691 :   zd = (GEN)avma;
    1176     1799691 :   x += 2; y += 2; a = ny-d;
    1177     1799691 :   if (a <= 0)
    1178             :   {
    1179      140887 :     lz = nx+d+2;
    1180      140887 :     (void)new_chunk(lz); xd = x+nx; yd = y+ny;
    1181      140889 :     while (xd > x) gel(--zd,0) = gel(--xd,0);
    1182      140889 :     x = zd + a;
    1183      140889 :     while (zd > x) gel(--zd,0) = gen_0;
    1184             :   }
    1185             :   else
    1186             :   {
    1187     1658804 :     xd = new_chunk(d); yd = y+d;
    1188     1658804 :     x = addpol(x,yd, nx,a);
    1189     1658804 :     lz = (a>nx)? ny+2: lg(x)+d;
    1190     1658804 :     x += 2; while (xd > x) *--zd = *--xd;
    1191             :   }
    1192     1799693 :   while (yd > y) *--zd = *--yd;
    1193     1799693 :   *--zd = evalsigne(1);
    1194     1799693 :   *--zd = evaltyp(t_POL) | evallg(lz); return zd;
    1195             : }
    1196             : 
    1197             : GEN
    1198      112182 : addshiftpol(GEN x, GEN y, long d)
    1199             : {
    1200      112182 :   long v = varn(x);
    1201      112182 :   x = addmulXn(x,y,d);
    1202      112182 :   setvarn(x,v); return x;
    1203             : }
    1204             : 
    1205             : /* as above, producing a clean malloc */
    1206             : static GEN
    1207      587878 : addmulXncopy(GEN x, GEN y, long d)
    1208             : {
    1209             :   GEN xd, yd, zd;
    1210             :   long a, lz, nx, ny;
    1211             : 
    1212      587878 :   if (!signe(x)) return RgX_copy(y);
    1213      587704 :   nx = lgpol(x);
    1214      587703 :   ny = lgpol(y);
    1215      587704 :   zd = (GEN)avma;
    1216      587704 :   x += 2; y += 2; a = ny-d;
    1217      587704 :   if (a <= 0)
    1218             :   {
    1219      293007 :     lz = nx+d+2;
    1220      293007 :     (void)new_chunk(lz); xd = x+nx; yd = y+ny;
    1221      293018 :     while (xd > x) gel(--zd,0) = gcopy(gel(--xd,0));
    1222      293018 :     x = zd + a;
    1223      293018 :     while (zd > x) gel(--zd,0) = gen_0;
    1224             :   }
    1225             :   else
    1226             :   {
    1227      294697 :     xd = new_chunk(d); yd = y+d;
    1228      294697 :     x = addpolcopy(x,yd, nx,a);
    1229      294694 :     lz = (a>nx)? ny+2: lg(x)+d;
    1230      294694 :     x += 2; while (xd > x) *--zd = *--xd;
    1231             :   }
    1232      587712 :   while (yd > y) gel(--zd,0) = gcopy(gel(--yd,0));
    1233      587702 :   *--zd = evalsigne(1);
    1234      587702 :   *--zd = evaltyp(t_POL) | evallg(lz); return zd;
    1235             : }
    1236             : 
    1237             : /* return x * y mod t^n */
    1238             : static GEN
    1239     3146777 : RgXn_mul_basecase(GEN x, GEN y, long n)
    1240             : {
    1241     3146777 :   long i, lz = n+2, lx = lgpol(x), ly = lgpol(y);
    1242             :   GEN z;
    1243     3146777 :   if (lx < 0) return pol_0(varn(x));
    1244     3146777 :   if (ly < 0) return pol_0(varn(x));
    1245     3146777 :   z = cgetg(lz, t_POL) + 2;
    1246     3146777 :   x+=2; if (lx > n) lx = n;
    1247     3146777 :   y+=2; if (ly > n) ly = n;
    1248     3146777 :   z[-1] = x[-1];
    1249     3146777 :   if (ly > lx) { swap(x,y); lswap(lx,ly); }
    1250     3146777 :   x = RgXspec_kill0(x, lx);
    1251     3146777 :   y = RgXspec_kill0(y, ly);
    1252             :   /* x:y:z [i] = term of degree i */
    1253     3146777 :   for (i=0;i<ly; i++) gel(z,i) = RgX_mulspec_basecase_limb(x+i,y, 0,i+1);
    1254     3146777 :   for (  ; i<lx; i++) gel(z,i) = RgX_mulspec_basecase_limb(x+i,y, 0,ly);
    1255     3146777 :   for (  ; i<n; i++)  gel(z,i) = RgX_mulspec_basecase_limb(x+i,y, i-lx+1,ly);
    1256     3146777 :   return normalizepol_lg(z - 2, lz);
    1257             : }
    1258             : /* Mulders / Karatsuba product f*g mod t^n (Hanrot-Zimmermann variant) */
    1259             : GEN
    1260     3611367 : RgXn_mul(GEN f, GEN g, long n)
    1261             : {
    1262     3611367 :   pari_sp av = avma;
    1263             :   GEN fe,fo, ge,go, l,h,m;
    1264             :   long n0, n1;
    1265     3611367 :   if (degpol(f) + degpol(g) < n) return RgX_mul(f,g);
    1266     3148212 :   if (n < 80) return RgXn_mul_basecase(f,g,n);
    1267        1435 :   n0 = n>>1; n1 = n-n0;
    1268        1435 :   RgX_even_odd(f, &fe, &fo);
    1269        1435 :   RgX_even_odd(g, &ge, &go);
    1270        1435 :   l = RgXn_mul(fe,ge,n1);
    1271        1435 :   h = RgXn_mul(fo,go,n0);
    1272        1435 :   m = RgX_sub(RgXn_mul(RgX_add(fe,fo),RgX_add(ge,go),n0), RgX_add(l,h));
    1273             :   /* n1-1 <= n0 <= n1, deg l,m <= n1-1, deg h <= n0-1
    1274             :    * result is t^2 h(t^2) + t m(t^2) + l(t^2) */
    1275        1435 :   l = RgX_inflate(l,2); /* deg l <= 2n1 - 2 <= n-1 */
    1276             :   /* deg(t m(t^2)) <= 2n1 - 1 <= n, truncate to < n */
    1277        1435 :   if (2*degpol(m)+1 == n) m = normalizepol_lg(m, lg(m)-1);
    1278        1435 :   m = RgX_inflate(m,2);
    1279             :   /* deg(t^2 h(t^2)) <= 2n0 <= n, truncate to < n */
    1280        1435 :   if (2*degpol(h)+2 == n) h = normalizepol_lg(h, lg(h)-1);
    1281        1435 :   h = RgX_inflate(h,2);
    1282        1435 :   h = addmulXncopy(addmulXn(h,m,1), l,1);
    1283        1435 :   setvarn(h, varn(f)); return gerepileupto(av, h);
    1284             : }
    1285             : 
    1286             : /* fast product (Karatsuba) of polynomials a,b. These are not real GENs, a+2,
    1287             :  * b+2 were sent instead. na, nb = number of terms of a, b.
    1288             :  * Only c, c0, c1, c2 are genuine GEN.
    1289             :  */
    1290             : GEN
    1291    12833412 : RgX_mulspec(GEN a, GEN b, long na, long nb)
    1292             : {
    1293             :   GEN a0, c, c0;
    1294    12833412 :   long n0, n0a, i, v = 0;
    1295             :   pari_sp av;
    1296             : 
    1297    12833412 :   while (na && isrationalzero(gel(a,0))) { a++; na--; v++; }
    1298    12833412 :   while (nb && isrationalzero(gel(b,0))) { b++; nb--; v++; }
    1299    12833407 :   if (na < nb) swapspec(a,b, na,nb);
    1300    12833407 :   if (!nb) return pol_0(0);
    1301             : 
    1302    12744278 :   if (nb < RgX_MUL_LIMIT) return RgX_mulspec_basecase(a,b,na,nb, v);
    1303      585610 :   RgX_shift_inplace_init(v);
    1304      585610 :   i = (na>>1); n0 = na-i; na = i;
    1305      585610 :   av = avma; a0 = a+n0; n0a = n0;
    1306      585610 :   while (n0a && isrationalzero(gel(a,n0a-1))) n0a--;
    1307             : 
    1308      585609 :   if (nb > n0)
    1309             :   {
    1310             :     GEN b0,c1,c2;
    1311             :     long n0b;
    1312             : 
    1313      579459 :     nb -= n0; b0 = b+n0; n0b = n0;
    1314      579459 :     while (n0b && isrationalzero(gel(b,n0b-1))) n0b--;
    1315      579459 :     c = RgX_mulspec(a,b,n0a,n0b);
    1316      579461 :     c0 = RgX_mulspec(a0,b0, na,nb);
    1317             : 
    1318      579459 :     c2 = addpol(a0,a, na,n0a);
    1319      579459 :     c1 = addpol(b0,b, nb,n0b);
    1320             : 
    1321      579455 :     c1 = RgX_mulspec(c1+2,c2+2, lgpol(c1),lgpol(c2));
    1322      579459 :     c2 = RgX_sub(c1, RgX_add(c0,c));
    1323      579458 :     c0 = addmulXn(c0, c2, n0);
    1324             :   }
    1325             :   else
    1326             :   {
    1327        6150 :     c = RgX_mulspec(a,b,n0a,nb);
    1328        6150 :     c0 = RgX_mulspec(a0,b,na,nb);
    1329             :   }
    1330      585610 :   c0 = addmulXncopy(c0,c,n0);
    1331      585608 :   return RgX_shift_inplace(gerepileupto(av,c0), v);
    1332             : }
    1333             : 
    1334             : INLINE GEN
    1335     2929686 : RgX_sqrspec_basecase_limb(GEN x, long a, long i)
    1336             : {
    1337     2929686 :   pari_sp av = avma;
    1338     2929686 :   GEN s = NULL;
    1339     2929686 :   long j, l = (i+1)>>1;
    1340    10695366 :   for (j=a; j<l; j++)
    1341             :   {
    1342     7767322 :     GEN xj = gel(x,j), xx = gel(x,i-j);
    1343     7767322 :     if (xj && xx)
    1344             :     {
    1345     4876425 :       GEN t = gmul(xj, xx);
    1346     4878797 :       s = s? gadd(s, t): t;
    1347             :     }
    1348             :   }
    1349     2928044 :   if (s) s = gshift(s,1);
    1350     2928092 :   if ((i&1) == 0)
    1351             :   {
    1352     1605849 :     GEN t = gel(x, i>>1);
    1353     1605849 :     if (t) {
    1354     1333864 :       t = gsqr(t);
    1355     1333875 :       s = s? gadd(s, t): t;
    1356             :     }
    1357             :   }
    1358     2928024 :   return s? gerepileupto(av,s): gen_0;
    1359             : }
    1360             : static GEN
    1361      282811 : RgX_sqrspec_basecase(GEN x, long nx, long v)
    1362             : {
    1363             :   long i, lz, nz;
    1364             :   GEN z;
    1365             : 
    1366      282811 :   if (!nx) return pol_0(0);
    1367      282804 :   x = RgXspec_kill0(x,nx);
    1368      282804 :   lz = (nx << 1) + 1, nz = lz-2;
    1369      282804 :   lz += v;
    1370      282804 :   z = cgetg(lz,t_POL) + 2;
    1371      282821 :   for (i=0; i<v; i++) gel(z++, 0) = gen_0;
    1372      282821 :   for (i=0; i<nx; i++)gel(z,i) = RgX_sqrspec_basecase_limb(x, 0, i);
    1373      282807 :   for (  ; i<nz; i++) gel(z,i) = RgX_sqrspec_basecase_limb(x, i-nx+1, i);
    1374      282802 :   z -= v+2; z[1] = 0; return normalizepol_lg(z, lz);
    1375             : }
    1376             : /* return x^2 mod t^n */
    1377             : static GEN
    1378         665 : RgXn_sqr_basecase(GEN x, long n)
    1379             : {
    1380         665 :   long i, lz = n+2, lx = lgpol(x);
    1381             :   GEN z;
    1382         665 :   if (lx < 0) return pol_0(varn(x));
    1383         665 :   z = cgetg(lz, t_POL);
    1384         665 :   z[1] = x[1];
    1385         665 :   x+=2; if (lx > n) lx = n;
    1386         665 :   x = RgXspec_kill0(x,lx);
    1387         665 :   z+=2;/* x:z [i] = term of degree i */
    1388         665 :   for (i=0;i<lx; i++) gel(z,i) = RgX_sqrspec_basecase_limb(x, 0, i);
    1389         665 :   for (  ; i<n; i++)  gel(z,i) = RgX_sqrspec_basecase_limb(x, i-lx+1, i);
    1390         665 :   z -= 2; return normalizepol_lg(z, lz);
    1391             : }
    1392             : /* Mulders / Karatsuba product f^2 mod t^n (Hanrot-Zimmermann variant) */
    1393             : GEN
    1394        2380 : RgXn_sqr(GEN f, long n)
    1395             : {
    1396        2380 :   pari_sp av = avma;
    1397             :   GEN fe,fo, l,h,m;
    1398             :   long n0, n1;
    1399        2380 :   if (2*degpol(f) < n) return RgX_sqr(f);
    1400         693 :   if (n < 80) return RgXn_sqr_basecase(f,n);
    1401          28 :   n0 = n>>1; n1 = n-n0;
    1402          28 :   RgX_even_odd(f, &fe, &fo);
    1403          28 :   l = RgXn_sqr(fe,n1);
    1404          28 :   h = RgXn_sqr(fo,n0);
    1405          28 :   m = RgX_sub(RgXn_sqr(RgX_add(fe,fo),n0), RgX_add(l,h));
    1406             :   /* n1-1 <= n0 <= n1, deg l,m <= n1-1, deg h <= n0-1
    1407             :    * result is t^2 h(t^2) + t m(t^2) + l(t^2) */
    1408          28 :   l = RgX_inflate(l,2); /* deg l <= 2n1 - 2 <= n-1 */
    1409             :   /* deg(t m(t^2)) <= 2n1 - 1 <= n, truncate to < n */
    1410          28 :   if (2*degpol(m)+1 == n) m = normalizepol_lg(m, lg(m)-1);
    1411          28 :   m = RgX_inflate(m,2);
    1412             :   /* deg(t^2 h(t^2)) <= 2n0 <= n, truncate to < n */
    1413          28 :   if (2*degpol(h)+2 == n) h = normalizepol_lg(h, lg(h)-1);
    1414          28 :   h = RgX_inflate(h,2);
    1415          28 :   h = addmulXncopy(addmulXn(h,m,1), l,1);
    1416          28 :   setvarn(h, varn(f)); return gerepileupto(av, h);
    1417             : }
    1418             : 
    1419             : GEN
    1420      283616 : RgX_sqrspec(GEN a, long na)
    1421             : {
    1422             :   GEN a0, c, c0, c1;
    1423      283616 :   long n0, n0a, i, v = 0;
    1424             :   pari_sp av;
    1425             : 
    1426      283616 :   while (na && isrationalzero(gel(a,0))) { a++; na--; v += 2; }
    1427      283616 :   if (na<RgX_SQR_LIMIT) return RgX_sqrspec_basecase(a, na, v);
    1428         805 :   RgX_shift_inplace_init(v);
    1429         805 :   i = (na>>1); n0 = na-i; na = i;
    1430         805 :   av = avma; a0 = a+n0; n0a = n0;
    1431         805 :   while (n0a && isrationalzero(gel(a,n0a-1))) n0a--;
    1432             : 
    1433         805 :   c = RgX_sqrspec(a,n0a);
    1434         805 :   c0 = RgX_sqrspec(a0,na);
    1435         805 :   c1 = gmul2n(RgX_mulspec(a0,a, na,n0a), 1);
    1436         805 :   c0 = addmulXn(c0,c1, n0);
    1437         805 :   c0 = addmulXncopy(c0,c,n0);
    1438         805 :   return RgX_shift_inplace(gerepileupto(av,c0), v);
    1439             : }
    1440             : 
    1441             : /* (X^a + A)(X^b + B) - X^(a+b), where deg A < a, deg B < b */
    1442             : GEN
    1443      428059 : RgX_mul_normalized(GEN A, long a, GEN B, long b)
    1444             : {
    1445      428059 :   GEN z = RgX_mul(A, B);
    1446      428059 :   if (a < b)
    1447        5201 :     z = addmulXn(addmulXn(A, B, b-a), z, a);
    1448      422858 :   else if (a > b)
    1449      272565 :     z = addmulXn(addmulXn(B, A, a-b), z, b);
    1450             :   else
    1451      150293 :     z = addmulXn(RgX_add(A, B), z, a);
    1452      428059 :   setvarn(z,varn(A)); return z;
    1453             : }
    1454             : 
    1455             : GEN
    1456    11081936 : RgX_mul(GEN x, GEN y)
    1457             : {
    1458    11081936 :   GEN z = RgX_mulspec(y+2, x+2, lgpol(y), lgpol(x));
    1459    11081936 :   setvarn(z,varn(x)); return z;
    1460             : }
    1461             : 
    1462             : GEN
    1463      282006 : RgX_sqr(GEN x)
    1464             : {
    1465      282006 :   GEN z = RgX_sqrspec(x+2, lgpol(x));
    1466      282004 :   setvarn(z,varn(x)); return z;
    1467             : }
    1468             : 
    1469             : /*******************************************************************/
    1470             : /*                                                                 */
    1471             : /*                               DIVISION                          */
    1472             : /*                                                                 */
    1473             : /*******************************************************************/
    1474             : GEN
    1475      953045 : RgX_Rg_divexact(GEN x, GEN y) {
    1476             :   long i, lx;
    1477             :   GEN z;
    1478      953045 :   if (typ(y) == t_INT && is_pm1(y))
    1479       93936 :     return signe(y) < 0 ? RgX_neg(x): RgX_copy(x);
    1480      859109 :   z = cgetg_copy(x, &lx); z[1] = x[1];
    1481      859109 :   for (i=2; i<lx; i++) gel(z,i) = gdivexact(gel(x,i),y);
    1482      859109 :   return z;
    1483             : }
    1484             : GEN
    1485    22303130 : RgX_Rg_div(GEN x, GEN y) {
    1486             :   long i, lx;
    1487    22303130 :   GEN z = cgetg_copy(x, &lx); z[1] = x[1];
    1488    22303130 :   for (i=2; i<lx; i++) gel(z,i) = gdiv(gel(x,i),y);
    1489    22303130 :   return normalizepol_lg(z, lx);
    1490             : }
    1491             : GEN
    1492        1456 : RgX_normalize(GEN x)
    1493             : {
    1494        1456 :   GEN d = NULL;
    1495        1456 :   long i, n = lg(x)-1;
    1496        1456 :   for (i = n; i > 1; i--)
    1497             :   {
    1498        1456 :     d = gel(x,i);
    1499        1456 :     if (!gequal0(d)) break;
    1500             :   }
    1501        1456 :   if (i == 1) return pol_0(varn(x));
    1502        1456 :   if (i == n && isint1(d)) return x;
    1503         287 :   return normalizepol_lg(RgX_Rg_div(x, d), i+1);
    1504             : }
    1505             : GEN
    1506        1729 : RgX_divs(GEN x, long y) {
    1507             :   long i, lx;
    1508        1729 :   GEN z = cgetg_copy(x, &lx); z[1] = x[1];
    1509        1729 :   for (i=2; i<lx; i++) gel(z,i) = gdivgs(gel(x,i),y);
    1510        1729 :   return normalizepol_lg(z, lx);
    1511             : }
    1512             : GEN
    1513       31727 : RgX_div_by_X_x(GEN a, GEN x, GEN *r)
    1514             : {
    1515       31727 :   long l = lg(a), i;
    1516       31727 :   GEN a0, z0, z = cgetg(l-1, t_POL);
    1517       31727 :   z[1] = a[1];
    1518       31727 :   a0 = a + l-1;
    1519       31727 :   z0 = z + l-2; *z0 = *a0--;
    1520      735267 :   for (i=l-3; i>1; i--) /* z[i] = a[i+1] + x*z[i+1] */
    1521             :   {
    1522      703540 :     GEN t = gadd(gel(a0--,0), gmul(x, gel(z0--,0)));
    1523      703540 :     gel(z0,0) = t;
    1524             :   }
    1525       31727 :   if (r) *r = gadd(gel(a0,0), gmul(x, gel(z0,0)));
    1526       31727 :   return z;
    1527             : }
    1528             : /* Polynomial division x / y:
    1529             :  *   if z = ONLY_REM  return remainder, otherwise return quotient
    1530             :  *   if z != NULL set *z to remainder
    1531             :  *   *z is the last object on stack (and thus can be disposed of with cgiv
    1532             :  *   instead of gerepile) */
    1533             : /* assume, typ(x) = typ(y) = t_POL, same variable */
    1534             : GEN
    1535    13162154 : RgX_divrem(GEN x, GEN y, GEN *pr)
    1536             : {
    1537             :   pari_sp avy, av, av1;
    1538             :   long dx,dy,dz,i,j,sx,lr;
    1539             :   GEN z,p1,p2,rem,y_lead,mod;
    1540             :   GEN (*f)(GEN,GEN);
    1541             : 
    1542    13162154 :   if (!signe(y)) pari_err_INV("RgX_divrem",y);
    1543             : 
    1544    13162154 :   dy = degpol(y);
    1545    13162343 :   y_lead = gel(y,dy+2);
    1546    13162343 :   if (gequal0(y_lead)) /* normalize denominator if leading term is 0 */
    1547             :   {
    1548           0 :     pari_warn(warner,"normalizing a polynomial with 0 leading term");
    1549           0 :     for (dy--; dy>=0; dy--)
    1550             :     {
    1551           0 :       y_lead = gel(y,dy+2);
    1552           0 :       if (!gequal0(y_lead)) break;
    1553             :     }
    1554             :   }
    1555    13162146 :   if (!dy) /* y is constant */
    1556             :   {
    1557       55527 :     if (pr == ONLY_REM) return pol_0(varn(x));
    1558       54918 :     z = RgX_Rg_div(x, y_lead);
    1559       54918 :     if (pr == ONLY_DIVIDES) return z;
    1560       54239 :     if (pr) *pr = pol_0(varn(x));
    1561       54239 :     return z;
    1562             :   }
    1563    13106619 :   dx = degpol(x);
    1564    13106722 :   if (dx < dy)
    1565             :   {
    1566      943185 :     if (pr == ONLY_REM) return RgX_copy(x);
    1567      309268 :     if (pr == ONLY_DIVIDES) return signe(x)? NULL: pol_0(varn(x));
    1568      309247 :     z = pol_0(varn(x));
    1569      309247 :     if (pr) *pr = RgX_copy(x);
    1570      309247 :     return z;
    1571             :   }
    1572             : 
    1573             :   /* x,y in R[X], y non constant */
    1574    12163537 :   av = avma;
    1575    12163537 :   switch(typ(y_lead))
    1576             :   {
    1577             :     case t_REAL:
    1578           0 :       y_lead = ginv(y_lead);
    1579           0 :       f = gmul; mod = NULL;
    1580           0 :       break;
    1581             :     case t_INTMOD:
    1582        4535 :     case t_POLMOD: y_lead = ginv(y_lead);
    1583        4535 :       f = gmul; mod = gmodulo(gen_1, gel(y_lead,1));
    1584        4535 :       break;
    1585    12159002 :     default: if (gequal1(y_lead)) y_lead = NULL;
    1586    12159085 :       f = gdiv; mod = NULL;
    1587             :   }
    1588             : 
    1589    12163620 :   if (y_lead == NULL)
    1590    10392830 :     p2 = gel(x,dx+2);
    1591             :   else {
    1592             :     for(;;) {
    1593     1770790 :       p2 = f(gel(x,dx+2),y_lead);
    1594     1770855 :       p2 = simplify_shallow(p2);
    1595     1770855 :       if (!isexactzero(p2) || (--dx < 0)) break;
    1596           0 :     }
    1597     1770855 :     if (dx < dy) /* leading coeff of x was in fact zero */
    1598             :     {
    1599           0 :       if (pr == ONLY_DIVIDES) {
    1600           0 :         avma = av;
    1601           0 :         return (dx < 0)? pol_0(varn(x)) : NULL;
    1602             :       }
    1603           0 :       if (pr == ONLY_REM)
    1604             :       {
    1605           0 :         if (dx < 0)
    1606           0 :           return gerepilecopy(av, scalarpol(p2, varn(x)));
    1607             :         else
    1608             :         {
    1609             :           GEN t;
    1610           0 :           avma = av;
    1611           0 :           t = cgetg(dx + 3, t_POL); t[1] = x[1];
    1612           0 :           for (i = 2; i < dx + 3; i++) gel(t,i) = gcopy(gel(x,i));
    1613           0 :           return t;
    1614             :         }
    1615             :       }
    1616           0 :       if (pr) /* cf ONLY_REM above */
    1617             :       {
    1618           0 :         if (dx < 0)
    1619             :         {
    1620           0 :           p2 = gclone(p2);
    1621           0 :           avma = av;
    1622           0 :           z = pol_0(varn(x));
    1623           0 :           x = scalarpol(p2, varn(x));
    1624           0 :           gunclone(p2);
    1625             :         }
    1626             :         else
    1627             :         {
    1628             :           GEN t;
    1629           0 :           avma = av;
    1630           0 :           z = pol_0(varn(x));
    1631           0 :           t = cgetg(dx + 3, t_POL); t[1] = x[1];
    1632           0 :           for (i = 2; i < dx + 3; i++) gel(t,i) = gcopy(gel(x,i));
    1633           0 :           x = t;
    1634             :         }
    1635           0 :         *pr = x;
    1636             :       }
    1637             :       else
    1638             :       {
    1639           0 :         avma = av;
    1640           0 :         z = pol_0(varn(x));
    1641             :       }
    1642           0 :       return z;
    1643             :     }
    1644             :   }
    1645             :   /* dx >= dy */
    1646    12163685 :   avy = avma;
    1647    12163685 :   dz = dx-dy;
    1648    12163685 :   z = cgetg(dz+3,t_POL); z[1] = x[1];
    1649    12163655 :   x += 2;
    1650    12163655 :   z += 2;
    1651    12163655 :   y += 2;
    1652    12163655 :   gel(z,dz) = gcopy(p2);
    1653             : 
    1654    34908126 :   for (i=dx-1; i>=dy; i--)
    1655             :   {
    1656    22744187 :     av1=avma; p1=gel(x,i);
    1657    22744187 :     for (j=i-dy+1; j<=i && j<=dz; j++) p1 = gsub(p1, gmul(gel(z,j),gel(y,i-j)));
    1658    22631028 :     if (y_lead) p1 = simplify(f(p1,y_lead));
    1659             : 
    1660    22631028 :     if (isrationalzero(p1)) { avma=av1; p1 = gen_0; }
    1661             :     else
    1662    12959961 :       p1 = avma==av1? gcopy(p1): gerepileupto(av1,p1);
    1663    22744229 :     gel(z,i-dy) = p1;
    1664             :   }
    1665    12163939 :   if (!pr) return gerepileupto(av,z-2);
    1666             : 
    1667     5853839 :   rem = (GEN)avma; av1 = (pari_sp)new_chunk(dx+3);
    1668     6620120 :   for (sx=0; ; i--)
    1669             :   {
    1670     6620120 :     p1 = gel(x,i);
    1671             :     /* we always enter this loop at least once */
    1672     6620120 :     for (j=0; j<=i && j<=dz; j++) p1 = gsub(p1, gmul(gel(z,j),gel(y,i-j)));
    1673     6619353 :     if (mod && avma==av1) p1 = gmul(p1,mod);
    1674     6619353 :     if (!gequal0(p1)) { sx = 1; break; } /* remainder is non-zero */
    1675     3854353 :     if (!isexactzero(p1)) break;
    1676     3847802 :     if (!i) break;
    1677      766333 :     avma=av1;
    1678      766333 :   }
    1679     5853737 :   if (pr == ONLY_DIVIDES)
    1680             :   {
    1681         693 :     if (sx) { avma=av; return NULL; }
    1682         686 :     avma = (pari_sp)rem;
    1683         686 :     return gerepileupto(av,z-2);
    1684             :   }
    1685     5853044 :   lr=i+3; rem -= lr;
    1686     5853044 :   if (avma==av1) { avma = (pari_sp)rem; p1 = gcopy(p1); }
    1687     5777357 :   else p1 = gerepileupto((pari_sp)rem,p1);
    1688     5853106 :   rem[0] = evaltyp(t_POL) | evallg(lr);
    1689     5852795 :   rem[1] = z[-1];
    1690     5852795 :   rem += 2;
    1691     5852795 :   gel(rem,i) = p1;
    1692    15165789 :   for (i--; i>=0; i--)
    1693             :   {
    1694     9312684 :     av1=avma; p1 = gel(x,i);
    1695     9312684 :     for (j=0; j<=i && j<=dz; j++) p1 = gsub(p1, gmul(gel(z,j),gel(y,i-j)));
    1696     9286673 :     if (mod && avma==av1) p1 = gmul(p1,mod);
    1697     9310099 :     gel(rem,i) = avma==av1? gcopy(p1):gerepileupto(av1,p1);
    1698             :   }
    1699     5853105 :   rem -= 2;
    1700     5853105 :   if (!sx) (void)normalizepol_lg(rem, lr);
    1701     5853108 :   if (pr == ONLY_REM) return gerepileupto(av,rem);
    1702     3945523 :   z -= 2;
    1703             :   {
    1704     3945523 :     GEN *gptr[2]; gptr[0]=&z; gptr[1]=&rem;
    1705     3945523 :     gerepilemanysp(av,avy,gptr,2); *pr = rem; return z;
    1706             :   }
    1707             : }
    1708             : 
    1709             : /* x and y in (R[Y]/T)[X]  (lifted), T in R[Y]. y preferably monic */
    1710             : GEN
    1711       21096 : RgXQX_divrem(GEN x, GEN y, GEN T, GEN *pr)
    1712             : {
    1713             :   long vx, dx, dy, dz, i, j, sx, lr;
    1714             :   pari_sp av0, av, tetpil;
    1715             :   GEN z,p1,rem,lead;
    1716             : 
    1717       21096 :   if (!signe(y)) pari_err_INV("RgXQX_divrem",y);
    1718       21096 :   vx = varn(x);
    1719       21096 :   dx = degpol(x);
    1720       21096 :   dy = degpol(y);
    1721       21096 :   if (dx < dy)
    1722             :   {
    1723        1414 :     if (pr)
    1724             :     {
    1725        1414 :       av0 = avma; x = RgXQX_red(x, T);
    1726        1414 :       if (pr == ONLY_DIVIDES) { avma=av0; return signe(x)? NULL: gen_0; }
    1727        1414 :       if (pr == ONLY_REM) return x;
    1728           0 :       *pr = x;
    1729             :     }
    1730           0 :     return pol_0(vx);
    1731             :   }
    1732       19682 :   lead = leading_coeff(y);
    1733       19682 :   if (!dy) /* y is constant */
    1734             :   {
    1735           7 :     if (pr && pr != ONLY_DIVIDES)
    1736             :     {
    1737           0 :       if (pr == ONLY_REM) return pol_0(vx);
    1738           0 :       *pr = pol_0(vx);
    1739             :     }
    1740           7 :     if (gequal1(lead)) return RgX_copy(x);
    1741           0 :     av0 = avma; x = gmul(x, ginvmod(lead,T)); tetpil = avma;
    1742           0 :     return gerepile(av0,tetpil,RgXQX_red(x,T));
    1743             :   }
    1744       19675 :   av0 = avma; dz = dx-dy;
    1745       19675 :   lead = gequal1(lead)? NULL: gclone(ginvmod(lead,T));
    1746       19675 :   avma = av0;
    1747       19675 :   z = cgetg(dz+3,t_POL); z[1] = x[1];
    1748       19675 :   x += 2; y += 2; z += 2;
    1749             : 
    1750       19675 :   p1 = gel(x,dx); av = avma;
    1751       19675 :   gel(z,dz) = lead? gerepileupto(av, grem(gmul(p1,lead), T)): gcopy(p1);
    1752      105530 :   for (i=dx-1; i>=dy; i--)
    1753             :   {
    1754       85855 :     av=avma; p1=gel(x,i);
    1755       85855 :     for (j=i-dy+1; j<=i && j<=dz; j++) p1 = gsub(p1, gmul(gel(z,j),gel(y,i-j)));
    1756       85855 :     if (lead) p1 = gmul(grem(p1, T), lead);
    1757       85855 :     tetpil=avma; gel(z,i-dy) = gerepile(av,tetpil, grem(p1, T));
    1758             :   }
    1759       19675 :   if (!pr) { if (lead) gunclone(lead); return z-2; }
    1760             : 
    1761       19675 :   rem = (GEN)avma; av = (pari_sp)new_chunk(dx+3);
    1762       29856 :   for (sx=0; ; i--)
    1763             :   {
    1764       29856 :     p1 = gel(x,i);
    1765       29856 :     for (j=0; j<=i && j<=dz; j++) p1 = gsub(p1, gmul(gel(z,j),gel(y,i-j)));
    1766       29856 :     tetpil=avma; p1 = grem(p1, T); if (!gequal0(p1)) { sx = 1; break; }
    1767       14330 :     if (!i) break;
    1768       10181 :     avma=av;
    1769       10181 :   }
    1770       19675 :   if (pr == ONLY_DIVIDES)
    1771             :   {
    1772        3855 :     if (lead) gunclone(lead);
    1773        3855 :     if (sx) { avma=av0; return NULL; }
    1774        3645 :     avma = (pari_sp)rem; return z-2;
    1775             :   }
    1776       15820 :   lr=i+3; rem -= lr;
    1777       15820 :   rem[0] = evaltyp(t_POL) | evallg(lr);
    1778       15820 :   rem[1] = z[-1];
    1779       15820 :   p1 = gerepile((pari_sp)rem,tetpil,p1);
    1780       15820 :   rem += 2; gel(rem,i) = p1;
    1781       30580 :   for (i--; i>=0; i--)
    1782             :   {
    1783       14760 :     av=avma; p1 = gel(x,i);
    1784       36902 :     for (j=0; j<=i && j<=dz; j++)
    1785       22142 :       p1 = gsub(p1, gmul(gel(z,j),gel(y,i-j)));
    1786       14760 :     tetpil=avma; gel(rem,i) = gerepile(av,tetpil, grem(p1, T));
    1787             :   }
    1788       15820 :   rem -= 2;
    1789       15820 :   if (lead) gunclone(lead);
    1790       15820 :   if (!sx) (void)normalizepol_lg(rem, lr);
    1791       15820 :   if (pr == ONLY_REM) return gerepileupto(av0,rem);
    1792          42 :   *pr = rem; return z-2;
    1793             : }
    1794             : 
    1795             : /*******************************************************************/
    1796             : /*                                                                 */
    1797             : /*                        PSEUDO-DIVISION                          */
    1798             : /*                                                                 */
    1799             : /*******************************************************************/
    1800             : INLINE GEN
    1801      938299 : rem(GEN c, GEN T)
    1802             : {
    1803      938299 :   if (T && typ(c) == t_POL && varn(c) == varn(T)) c = RgX_rem(c, T);
    1804      938299 :   return c;
    1805             : }
    1806             : 
    1807             : /* x, y, are ZYX, lc(y) is an integer, T is a ZY */
    1808             : int
    1809        1099 : ZXQX_dvd(GEN x, GEN y, GEN T)
    1810             : {
    1811             :   long dx, dy, dz, i, p, T_ismonic;
    1812        1099 :   pari_sp av = avma, av2;
    1813             :   GEN y_lead;
    1814             : 
    1815        1099 :   if (!signe(y)) pari_err_INV("ZXQX_dvd",y);
    1816        1099 :   dy = degpol(y); y_lead = gel(y,dy+2);
    1817        1099 :   if (typ(y_lead) == t_POL) y_lead = gel(y_lead, 2); /* t_INT */
    1818             :   /* if monic, no point in using pseudo-division */
    1819        1099 :   if (gequal1(y_lead)) return signe(RgXQX_rem(x, y, T)) == 0;
    1820         637 :   T_ismonic = gequal1(leading_coeff(T));
    1821         637 :   dx = degpol(x);
    1822         637 :   if (dx < dy) return !signe(x);
    1823         637 :   (void)new_chunk(2);
    1824         637 :   x = RgX_recip_shallow(x)+2;
    1825         637 :   y = RgX_recip_shallow(y)+2;
    1826             :   /* pay attention to sparse divisors */
    1827        1400 :   for (i = 1; i <= dy; i++)
    1828         763 :     if (!signe(gel(y,i))) gel(y,i) = NULL;
    1829         637 :   dz = dx-dy; p = dz+1;
    1830         637 :   av2 = avma;
    1831             :   for (;;)
    1832             :   {
    1833        7147 :     GEN m, x0 = gel(x,0), y0 = y_lead, cx = content(x0);
    1834        7147 :     x0 = gneg(x0); p--;
    1835        7147 :     m = gcdii(cx, y0);
    1836        7147 :     if (!equali1(m))
    1837             :     {
    1838        6405 :       x0 = gdiv(x0, m);
    1839        6405 :       y0 = diviiexact(y0, m);
    1840        6405 :       if (equali1(y0)) y0 = NULL;
    1841             :     }
    1842       15120 :     for (i=1; i<=dy; i++)
    1843             :     {
    1844        7973 :       GEN c = gel(x,i); if (y0) c = gmul(y0, c);
    1845        7973 :       if (gel(y,i)) c = gadd(c, gmul(x0,gel(y,i)));
    1846        7973 :       if (typ(c) == t_POL) c = T_ismonic ? ZX_rem(c, T): RgX_rem(c, T);
    1847        7973 :       gel(x,i) = c;
    1848             :     }
    1849       77287 :     for (   ; i<=dx; i++)
    1850             :     {
    1851       70140 :       GEN c = gel(x,i); if (y0) c = gmul(y0, c);
    1852       70140 :       if (typ(c) == t_POL) c = T_ismonic ? ZX_rem(c, T): RgX_rem(c, T);
    1853       70140 :       gel(x,i) = c;
    1854             :     }
    1855        7924 :     do { x++; dx--; } while (dx >= 0 && !signe(gel(x,0)));
    1856        7147 :     if (dx < dy) break;
    1857        6510 :     if (gc_needed(av2,1))
    1858             :     {
    1859           0 :       if(DEBUGMEM>1) pari_warn(warnmem,"ZXQX_dvd dx = %ld >= %ld",dx,dy);
    1860           0 :       gerepilecoeffs(av2,x,dx+1);
    1861             :     }
    1862        6510 :   }
    1863         637 :   avma = av; return (dx < 0);
    1864             : }
    1865             : 
    1866             : /* T either NULL or a t_POL. */
    1867             : GEN
    1868       68515 : RgXQX_pseudorem(GEN x, GEN y, GEN T)
    1869             : {
    1870       68515 :   long vx = varn(x), dx, dy, dz, i, lx, p;
    1871       68515 :   pari_sp av = avma, av2;
    1872             :   GEN y_lead;
    1873             : 
    1874       68515 :   if (!signe(y)) pari_err_INV("RgXQX_pseudorem",y);
    1875       68515 :   dy = degpol(y); y_lead = gel(y,dy+2);
    1876             :   /* if monic, no point in using pseudo-division */
    1877       68515 :   if (gequal1(y_lead)) return T? RgXQX_rem(x, y, T): RgX_rem(x, y);
    1878       64637 :   dx = degpol(x);
    1879       64637 :   if (dx < dy) return RgX_copy(x);
    1880       64637 :   (void)new_chunk(2);
    1881       64637 :   x = RgX_recip_shallow(x)+2;
    1882       64637 :   y = RgX_recip_shallow(y)+2;
    1883             :   /* pay attention to sparse divisors */
    1884      240592 :   for (i = 1; i <= dy; i++)
    1885      175955 :     if (isexactzero(gel(y,i))) gel(y,i) = NULL;
    1886       64637 :   dz = dx-dy; p = dz+1;
    1887       64637 :   av2 = avma;
    1888             :   for (;;)
    1889             :   {
    1890      172086 :     gel(x,0) = gneg(gel(x,0)); p--;
    1891      616721 :     for (i=1; i<=dy; i++)
    1892             :     {
    1893      444635 :       GEN c = gmul(y_lead, gel(x,i));
    1894      444635 :       if (gel(y,i)) c = gadd(c, gmul(gel(x,0),gel(y,i)));
    1895      444635 :       gel(x,i) = rem(c, T);
    1896             :     }
    1897      443625 :     for (   ; i<=dx; i++)
    1898             :     {
    1899      271539 :       GEN c = gmul(y_lead, gel(x,i));
    1900      271539 :       gel(x,i) = rem(c, T);
    1901             :     }
    1902      179023 :     do { x++; dx--; } while (dx >= 0 && gequal0(gel(x,0)));
    1903      172086 :     if (dx < dy) break;
    1904      107449 :     if (gc_needed(av2,1))
    1905             :     {
    1906           0 :       if(DEBUGMEM>1) pari_warn(warnmem,"RgX_pseudorem dx = %ld >= %ld",dx,dy);
    1907           0 :       gerepilecoeffs(av2,x,dx+1);
    1908             :     }
    1909      107449 :   }
    1910       64637 :   if (dx < 0) return pol_0(vx);
    1911       63125 :   lx = dx+3; x -= 2;
    1912       63125 :   x[0] = evaltyp(t_POL) | evallg(lx);
    1913       63125 :   x[1] = evalsigne(1) | evalvarn(vx);
    1914       63125 :   x = RgX_recip_shallow(x);
    1915       63125 :   if (p)
    1916             :   { /* multiply by y[0]^p   [beware dummy vars from FpX_FpXY_resultant] */
    1917        1421 :     GEN t = y_lead;
    1918        1421 :     if (T && typ(t) == t_POL && varn(t) == varn(T))
    1919           0 :       t = RgXQ_powu(t, p, T);
    1920             :     else
    1921        1421 :       t = gpowgs(t, p);
    1922        4795 :     for (i=2; i<lx; i++)
    1923             :     {
    1924        3374 :       GEN c = gmul(gel(x,i), t);
    1925        3374 :       gel(x,i) = rem(c,T);
    1926             :     }
    1927        1421 :     if (!T) return gerepileupto(av, x);
    1928             :   }
    1929       61704 :   return gerepilecopy(av, x);
    1930             : }
    1931             : 
    1932             : GEN
    1933       68515 : RgX_pseudorem(GEN x, GEN y) { return RgXQX_pseudorem(x,y, NULL); }
    1934             : 
    1935             : /* Compute z,r s.t lc(y)^(dx-dy+1) x = z y + r */
    1936             : GEN
    1937       45403 : RgXQX_pseudodivrem(GEN x, GEN y, GEN T, GEN *ptr)
    1938             : {
    1939       45403 :   long vx = varn(x), dx, dy, dz, i, iz, lx, lz, p;
    1940       45403 :   pari_sp av = avma, av2;
    1941             :   GEN z, r, ypow, y_lead;
    1942             : 
    1943       45403 :   if (!signe(y)) pari_err_INV("RgXQX_pseudodivrem",y);
    1944       45403 :   dy = degpol(y); y_lead = gel(y,dy+2);
    1945       45403 :   if (gequal1(y_lead)) return T? RgXQX_divrem(x,y, T, ptr): RgX_divrem(x,y, ptr);
    1946       21343 :   dx = degpol(x);
    1947       21343 :   if (dx < dy) { *ptr = RgX_copy(x); return pol_0(vx); }
    1948       21343 :   if (dx == dy)
    1949             :   {
    1950          28 :     GEN x_lead = gel(x,lg(x)-1);
    1951          28 :     x = RgX_renormalize_lg(leafcopy(x), lg(x)-1);
    1952          28 :     y = RgX_renormalize_lg(leafcopy(y), lg(y)-1);
    1953          28 :     r = RgX_sub(RgX_Rg_mul(x, y_lead), RgX_Rg_mul(y, x_lead));
    1954          28 :     *ptr = gerepileupto(av, r); return scalarpol(x_lead, vx);
    1955             :   }
    1956       21315 :   (void)new_chunk(2);
    1957       21315 :   x = RgX_recip_shallow(x)+2;
    1958       21315 :   y = RgX_recip_shallow(y)+2;
    1959             :   /* pay attention to sparse divisors */
    1960       87948 :   for (i = 1; i <= dy; i++)
    1961       66633 :     if (isexactzero(gel(y,i))) gel(y,i) = NULL;
    1962       21315 :   dz = dx-dy; p = dz+1;
    1963       21315 :   lz = dz+3;
    1964       21315 :   z = cgetg(lz, t_POL);
    1965       21315 :   z[1] = evalsigne(1) | evalvarn(vx);
    1966       21315 :   for (i = 2; i < lz; i++) gel(z,i) = gen_0;
    1967       21315 :   ypow = new_chunk(dz+1);
    1968       21315 :   gel(ypow,0) = gen_1;
    1969       21315 :   gel(ypow,1) = y_lead;
    1970       27719 :   for (i=2; i<=dz; i++)
    1971             :   {
    1972        6404 :     GEN c = gmul(gel(ypow,i-1), y_lead);
    1973        6404 :     gel(ypow,i) = rem(c,T);
    1974             :   }
    1975       21315 :   av2 = avma;
    1976       21315 :   for (iz=2;;)
    1977             :   {
    1978       43268 :     p--;
    1979       43268 :     gel(z,iz++) = rem(gmul(gel(x,0), gel(ypow,p)), T);
    1980      174263 :     for (i=1; i<=dy; i++)
    1981             :     {
    1982      130995 :       GEN c = gmul(y_lead, gel(x,i));
    1983      130995 :       if (gel(y,i)) c = gsub(c, gmul(gel(x,0),gel(y,i)));
    1984      130995 :       gel(x,i) = rem(c, T);
    1985             :     }
    1986       81352 :     for (   ; i<=dx; i++)
    1987             :     {
    1988       38084 :       GEN c = gmul(y_lead, gel(x,i));
    1989       38084 :       gel(x,i) = rem(c,T);
    1990             :     }
    1991       43268 :     x++; dx--;
    1992       43268 :     while (dx >= dy && gequal0(gel(x,0))) { x++; dx--; iz++; }
    1993       43268 :     if (dx < dy) break;
    1994       21953 :     if (gc_needed(av2,1))
    1995             :     {
    1996           0 :       GEN X = x-2;
    1997           0 :       if(DEBUGMEM>1) pari_warn(warnmem,"RgX_pseudodivrem dx=%ld >= %ld",dx,dy);
    1998           0 :       X[0] = evaltyp(t_POL)|evallg(dx+3); X[1] = z[1]; /* hack */
    1999           0 :       gerepileall(av2,2, &X, &z); x = X+2;
    2000             :     }
    2001       21953 :   }
    2002       21315 :   while (dx >= 0 && gequal0(gel(x,0))) { x++; dx--; }
    2003       21315 :   if (dx < 0)
    2004          98 :     x = pol_0(vx);
    2005             :   else
    2006             :   {
    2007       21217 :     lx = dx+3; x -= 2;
    2008       21217 :     x[0] = evaltyp(t_POL) | evallg(lx);
    2009       21217 :     x[1] = evalsigne(1) | evalvarn(vx);
    2010       21217 :     x = RgX_recip_shallow(x);
    2011             :   }
    2012       21315 :   z = RgX_recip_shallow(z);
    2013       21315 :   r = x;
    2014       21315 :   if (p)
    2015             :   {
    2016        3945 :     GEN c = gel(ypow,p); r = RgX_Rg_mul(r, c);
    2017        3945 :     if (T && typ(c) == t_POL && varn(c) == varn(T)) r = RgXQX_red(r, T);
    2018             :   }
    2019       21315 :   gerepileall(av, 2, &z, &r);
    2020       21315 :   *ptr = r; return z;
    2021             : }
    2022             : GEN
    2023       45284 : RgX_pseudodivrem(GEN x, GEN y, GEN *ptr)
    2024       45284 : { return RgXQX_pseudodivrem(x,y,NULL,ptr); }
    2025             : 
    2026             : GEN
    2027        1659 : RgXQX_mul(GEN x, GEN y, GEN T)
    2028             : {
    2029        1659 :   return RgXQX_red(RgX_mul(x,y), T);
    2030             : }
    2031             : GEN
    2032    65817346 : RgX_Rg_mul(GEN y, GEN x) {
    2033             :   long i, ly;
    2034    65817346 :   GEN z = cgetg_copy(y, &ly); z[1] = y[1];
    2035    65817346 :   if (ly == 2) return z;
    2036    65759806 :   for (i = 2; i < ly; i++) gel(z,i) = gmul(x,gel(y,i));
    2037    65759799 :   return normalizepol_lg(z,ly);
    2038             : }
    2039             : GEN
    2040         616 : RgX_muls(GEN y, long x) {
    2041             :   long i, ly;
    2042         616 :   GEN z = cgetg_copy(y, &ly); z[1] = y[1];
    2043         616 :   if (ly == 2) return z;
    2044         581 :   for (i = 2; i < ly; i++) gel(z,i) = gmulsg(x,gel(y,i));
    2045         581 :   return normalizepol_lg(z,ly);
    2046             : }
    2047             : GEN
    2048          28 : RgXQX_RgXQ_mul(GEN x, GEN y, GEN T)
    2049             : {
    2050          28 :   return RgXQX_red(RgX_Rg_mul(x,y), T);
    2051             : }
    2052             : GEN
    2053          56 : RgXQV_RgXQ_mul(GEN v, GEN x, GEN T)
    2054             : {
    2055          56 :   return RgXQV_red(RgV_Rg_mul(v,x), T);
    2056             : }
    2057             : 
    2058             : GEN
    2059           0 : RgXQX_sqr(GEN x, GEN T)
    2060             : {
    2061           0 :   return RgXQX_red(RgX_sqr(x), T);
    2062             : }
    2063             : 
    2064             : static GEN
    2065       69636 : _add(void *data, GEN x, GEN y) { (void)data; return RgX_add(x, y); }
    2066             : static GEN
    2067           0 : _sub(void *data, GEN x, GEN y) { (void)data; return RgX_sub(x, y); }
    2068             : static GEN
    2069      220785 : _sqr(void *data, GEN x) { return RgXQ_sqr(x, (GEN)data); }
    2070             : static GEN
    2071       94306 : _mul(void *data, GEN x, GEN y) { return RgXQ_mul(x,y, (GEN)data); }
    2072             : static GEN
    2073      114737 : _cmul(void *data, GEN P, long a, GEN x) { (void)data; return RgX_Rg_mul(x,gel(P,a+2)); }
    2074             : static GEN
    2075      106078 : _one(void *data) { return pol_1(varn((GEN)data)); }
    2076             : static GEN
    2077         105 : _zero(void *data) { return pol_0(varn((GEN)data)); }
    2078             : static GEN
    2079       72751 : _red(void *data, GEN x) { (void)data; return gcopy(x); }
    2080             : 
    2081             : static struct bb_algebra RgXQ_algebra = { _red, _add, _sub,
    2082             :               _mul, _sqr, _one, _zero };
    2083             : 
    2084             : GEN
    2085           0 : RgX_RgXQV_eval(GEN Q, GEN x, GEN T)
    2086             : {
    2087           0 :   return gen_bkeval_powers(Q,degpol(Q),x,(void*)T,&RgXQ_algebra,_cmul);
    2088             : }
    2089             : 
    2090             : GEN
    2091       44527 : RgX_RgXQ_eval(GEN Q, GEN x, GEN T)
    2092             : {
    2093       44527 :   int use_sqr = 2*degpol(x) >= degpol(T);
    2094       44527 :   return gen_bkeval(Q,degpol(Q),x,use_sqr,(void*)T,&RgXQ_algebra,_cmul);
    2095             : }
    2096             : 
    2097             : /* mod X^n */
    2098             : struct modXn {
    2099             :   long v; /* varn(X) */
    2100             :   long n;
    2101             : } ;
    2102             : static GEN
    2103        1785 : _sqrXn(void *data, GEN x) {
    2104        1785 :   struct modXn *S = (struct modXn*)data;
    2105        1785 :   return RgXn_sqr(x, S->n);
    2106             : }
    2107             : static GEN
    2108        1176 : _mulXn(void *data, GEN x, GEN y) {
    2109        1176 :   struct modXn *S = (struct modXn*)data;
    2110        1176 :   return RgXn_mul(x,y, S->n);
    2111             : }
    2112             : static GEN
    2113        1407 : _oneXn(void *data) {
    2114        1407 :   struct modXn *S = (struct modXn*)data;
    2115        1407 :   return pol_1(S->v);
    2116             : }
    2117             : static GEN
    2118           0 : _zeroXn(void *data) {
    2119           0 :   struct modXn *S = (struct modXn*)data;
    2120           0 :   return pol_0(S->v);
    2121             : }
    2122             : static struct bb_algebra RgXn_algebra = { _red, _add, _sub, _mulXn, _sqrXn,
    2123             :                                           _oneXn, _zeroXn };
    2124             : 
    2125             : GEN
    2126         336 : RgXn_powers(GEN x, long m, long n)
    2127             : {
    2128         336 :   long d = degpol(x);
    2129         336 :   int use_sqr = (d<<1) >= n;
    2130             :   struct modXn S;
    2131         336 :   S.v = varn(x); S.n = n;
    2132         336 :   return gen_powers(x,m,use_sqr,(void*)&S,_sqrXn,_mulXn,_oneXn);
    2133             : }
    2134             : 
    2135             : GEN
    2136        1505 : RgXn_powu_i(GEN x, ulong m, long n)
    2137             : {
    2138             :   struct modXn S;
    2139        1505 :   S.v = varn(x); S.n = n;
    2140        1505 :   return gen_powu_i(x, m, (void*)&S,_sqrXn,_mulXn);
    2141             : }
    2142             : GEN
    2143           0 : RgXn_powu(GEN x, ulong m, long n)
    2144             : {
    2145             :   struct modXn S;
    2146           0 :   S.v = varn(x); S.n = n;
    2147           0 :   return gen_powu(x, m, (void*)&S,_sqrXn,_mulXn);
    2148             : }
    2149             : 
    2150             : GEN
    2151         672 : RgX_RgXnV_eval(GEN Q, GEN x, long n)
    2152             : {
    2153             :   struct modXn S;
    2154         672 :   S.v = varn(gel(x,2)); S.n = n;
    2155         672 :   return gen_bkeval_powers(Q,degpol(Q),x,(void*)&S,&RgXn_algebra,_cmul);
    2156             : }
    2157             : 
    2158             : GEN
    2159           0 : RgX_RgXn_eval(GEN Q, GEN x, long n)
    2160             : {
    2161           0 :   int use_sqr = 2*degpol(x) >= n;
    2162             :   struct modXn S;
    2163           0 :   S.v = varn(x); S.n = n;
    2164           0 :   return gen_bkeval(Q,degpol(Q),x,use_sqr,(void*)&S,&RgXn_algebra,_cmul);
    2165             : }
    2166             : 
    2167             : /* Q(x) mod t^n, x in R[t], n >= 1 */
    2168             : GEN
    2169        1561 : RgXn_eval(GEN Q, GEN x, long n)
    2170             : {
    2171        1561 :   long d = degpol(x);
    2172             :   int use_sqr;
    2173             :   struct modXn S;
    2174        1561 :   if (d == 1 && isrationalzero(gel(x,2)))
    2175             :   {
    2176        1554 :     GEN y = RgX_unscale(Q, gel(x,3));
    2177        1554 :     setvarn(y, varn(x)); return y;
    2178             :   }
    2179           7 :   S.v = varn(x);
    2180           7 :   S.n = n;
    2181           7 :   use_sqr = (d<<1) >= n;
    2182           7 :   return gen_bkeval(Q,degpol(Q),x,use_sqr,(void*)&S,&RgXn_algebra,_cmul);
    2183             : }
    2184             : 
    2185             : GEN
    2186         896 : RgXn_inv(GEN f, long e)
    2187             : {
    2188         896 :   pari_sp av = avma, av2;
    2189             :   ulong mask;
    2190             :   GEN W;
    2191         896 :   long v = varn(f), n=1;
    2192         896 :   if (signe(f)==0)
    2193           0 :     pari_err_INV("RgXn_inv",f);
    2194         896 :   W = scalarpol(ginv(gel(f,2)),v);
    2195         896 :   mask = quadratic_prec_mask(e);
    2196         896 :   av2 = avma;
    2197        5935 :   for (;mask>1;)
    2198             :   {
    2199             :     GEN u, fr;
    2200        4143 :     long n2 = n;
    2201        4143 :     n<<=1; if (mask & 1) n--;
    2202        4143 :     mask >>= 1;
    2203        4143 :     fr = RgXn_red_shallow(f, n);
    2204        4143 :     u = RgX_shift_shallow(RgXn_mul(W, fr, n), -n2);
    2205        4143 :     W = RgX_sub(W, RgX_shift_shallow(RgXn_mul(u, W, n-n2), n2));
    2206        4143 :     if (gc_needed(av2,2))
    2207             :     {
    2208           0 :       if(DEBUGMEM>1) pari_warn(warnmem,"RgXn_inv, e = %ld", n);
    2209           0 :       W = gerepileupto(av2, W);
    2210             :     }
    2211             :   }
    2212         896 :   return gerepileupto(av, W);
    2213             : }
    2214             : 
    2215             : GEN
    2216         203 : RgXn_exp(GEN h, long e)
    2217             : {
    2218         203 :   pari_sp av = avma, av2;
    2219         203 :   long v = varn(h), n=1;
    2220         203 :   GEN f = pol_1(v), g = pol_1(v);
    2221         203 :   ulong mask = quadratic_prec_mask(e);
    2222         203 :   av2 = avma;
    2223         203 :   if (signe(h)==0 || degpol(h)<1 || !gequal0(gel(h,2)))
    2224           0 :     pari_err_DOMAIN("RgXn_exp","valuation", "<", gen_1, h);
    2225         791 :   for (;mask>1;)
    2226             :   {
    2227             :     GEN q, w;
    2228         385 :     long n2 = n;
    2229         385 :     n<<=1; if (mask & 1) n--;
    2230         385 :     mask >>= 1;
    2231         385 :     g = RgX_sub(RgX_muls(g,2),RgXn_mul(f,RgXn_sqr(g,n2),n2));
    2232         385 :     q = RgX_deriv(RgXn_red_shallow(h,n2));
    2233         385 :     w = RgX_add(q, RgXn_mul(g, RgX_sub(RgX_deriv(f), RgXn_mul(f,q,n-1)),n-1));
    2234         385 :     f = RgX_add(f, RgXn_mul(f, RgX_sub(RgXn_red_shallow(h, n), RgX_integ(w)), n));
    2235         385 :     if (gc_needed(av2,2))
    2236             :     {
    2237           0 :       if(DEBUGMEM>1) pari_warn(warnmem,"RgXn_exp, e = %ld", n);
    2238           0 :       gerepileall(av2, 2, &f, &g);
    2239             :     }
    2240             :   }
    2241         203 :   return gerepileupto(av, f);
    2242             : }
    2243             : 
    2244             : GEN
    2245          84 : RgXn_reverse(GEN f, long e)
    2246             : {
    2247          84 :   pari_sp av = avma, av2;
    2248             :   ulong mask;
    2249             :   GEN fi, a, df, W, an;
    2250          84 :   long v = varn(f), n=1;
    2251          84 :   if (degpol(f)<1 || !gequal0(gel(f,2)))
    2252           0 :     pari_err_INV("serreverse",f);
    2253          84 :   fi = ginv(gel(f,3));
    2254          84 :   a = deg1pol_shallow(fi,gen_0,v);
    2255          84 :   if (e <= 2) return gerepilecopy(av, a);
    2256          84 :   W = scalarpol(fi,v);
    2257          84 :   df = RgX_deriv(f);
    2258          84 :   mask = quadratic_prec_mask(e);
    2259          84 :   av2 = avma;
    2260         504 :   for (;mask>1;)
    2261             :   {
    2262             :     GEN u, fa, fr;
    2263         336 :     long n2 = n, rt;
    2264         336 :     n<<=1; if (mask & 1) n--;
    2265         336 :     mask >>= 1;
    2266         336 :     fr = RgXn_red_shallow(f, n);
    2267         336 :     rt = brent_kung_optpow(degpol(fr), 4, 3);
    2268         336 :     an = RgXn_powers(a, rt, n);
    2269         336 :     if (n>1)
    2270             :     {
    2271         336 :       long n4 = (n2+1)>>1;
    2272         336 :       GEN dfr = RgXn_red_shallow(df, n2);
    2273         336 :       dfr = RgX_RgXnV_eval(dfr, RgXnV_red_shallow(an, n2), n2);
    2274         336 :       u = RgX_shift(RgX_Rg_sub(RgXn_mul(W, dfr, n2), gen_1), -n4);
    2275         336 :       W = RgX_sub(W, RgX_shift(RgXn_mul(u, W, n2-n4), n4));
    2276             :     }
    2277         336 :     fa = RgX_sub(RgX_RgXnV_eval(fr, an, n), pol_x(v));
    2278         336 :     fa = RgX_shift(fa, -n2);
    2279         336 :     a = RgX_sub(a, RgX_shift(RgXn_mul(W, fa, n-n2), n2));
    2280         336 :     if (gc_needed(av2,2))
    2281             :     {
    2282           0 :       if(DEBUGMEM>1) pari_warn(warnmem,"RgXn_reverse, e = %ld", n);
    2283           0 :       gerepileall(av2, 2, &a, &W);
    2284             :     }
    2285             :   }
    2286          84 :   return gerepileupto(av, a);
    2287             : }
    2288             : 
    2289             : /* x,T in Rg[X], n in N, compute lift(x^n mod T)) */
    2290             : GEN
    2291      180494 : RgXQ_powu(GEN x, ulong n, GEN T)
    2292             : {
    2293             :   pari_sp av;
    2294             :   GEN y;
    2295             : 
    2296      180494 :   if (!n) return pol_1(varn(x));
    2297      178961 :   if (n == 1) return RgX_copy(x);
    2298      121127 :   av = avma;
    2299      121127 :   y = gen_powu(x, n, (void*)T, &_sqr, &_mul);
    2300      121127 :   return gerepileupto(av, y);
    2301             : }
    2302             : /* x,T in Rg[X], n in N, compute lift(x^n mod T)) */
    2303             : GEN
    2304       30050 : RgXQ_pow(GEN x, GEN n, GEN T)
    2305             : {
    2306             :   pari_sp av;
    2307       30050 :   long s = signe(n);
    2308             :   GEN y;
    2309             : 
    2310       30050 :   if (!s) return pol_1(varn(x));
    2311       30050 :   if (is_pm1(n) == 1)
    2312           0 :     return (s < 0)? RgXQ_inv(x, T): RgX_copy(x);
    2313       30050 :   av = avma;
    2314       30050 :   if (s < 0) x = RgXQ_inv(x, T);
    2315       30050 :   y = gen_pow(x, n, (void*)T, &_sqr, &_mul);
    2316       30050 :   return gerepileupto(av, y);
    2317             : }
    2318             : 
    2319             : /* generates the list of powers of x of degree 0,1,2,...,l*/
    2320             : GEN
    2321        1701 : RgXQ_powers(GEN x, long l, GEN T)
    2322             : {
    2323        1701 :   int use_sqr = 2*degpol(x) >= degpol(T);
    2324        1701 :   return gen_powers(x, l, use_sqr, (void *)T,_sqr,_mul,_one);
    2325             : }
    2326             : 
    2327             : /* a in K = Q[X]/(T), returns [a^0, ..., a^n] */
    2328             : GEN
    2329        1393 : QXQ_powers(GEN a, long n, GEN T)
    2330             : {
    2331        1393 :   GEN den, v = RgXQ_powers(Q_remove_denom(a, &den), n, T);
    2332             :   /* den*a integral; v[i+1] = (den*a)^i in K */
    2333        1393 :   if (den)
    2334             :   { /* restore denominators */
    2335         847 :     GEN d = den;
    2336             :     long i;
    2337         847 :     gel(v,2) = a;
    2338        3283 :     for (i=3; i<=n+1; i++) {
    2339        2436 :       d = mulii(d,den);
    2340        2436 :       gel(v,i) = RgX_Rg_div(gel(v,i), d);
    2341             :     }
    2342             :   }
    2343        1393 :   return v;
    2344             : }
    2345             : 
    2346             : static GEN
    2347         819 : do_QXQ_eval(GEN v, long imin, GEN a, GEN T)
    2348             : {
    2349         819 :   long l, i, m = 0;
    2350             :   GEN dz, z;
    2351         819 :   GEN V = cgetg_copy(v, &l);
    2352        2625 :   for (i = imin; i < l; i++)
    2353             :   {
    2354        1806 :     GEN c = gel(v, i);
    2355        1806 :     if (typ(c) == t_POL) m = maxss(m, degpol(c));
    2356             :   }
    2357         819 :   z = Q_remove_denom(QXQ_powers(a, m, T), &dz);
    2358         819 :   for (i = 1; i < imin; i++) V[i] = v[i];
    2359        2625 :   for (i = imin; i < l; i++)
    2360             :   {
    2361        1806 :     GEN c = gel(v,i);
    2362        1806 :     if (typ(c) == t_POL) c = QX_ZXQV_eval(c, z, dz);
    2363        1806 :     gel(V,i) = c;
    2364             :   }
    2365         819 :   return V;
    2366             : }
    2367             : /* [ s(a mod T) | s <- lift(v) ], a,T are QX, v a QXV */
    2368             : GEN
    2369         777 : QXV_QXQ_eval(GEN v, GEN a, GEN T)
    2370         777 : { return do_QXQ_eval(v, 1, a, T); }
    2371             : GEN
    2372          42 : QXX_QXQ_eval(GEN v, GEN a, GEN T)
    2373          42 : { return normalizepol(do_QXQ_eval(v, 2, a, T)); }
    2374             : 
    2375             : GEN
    2376         287 : RgXQ_matrix_pow(GEN y, long n, long m, GEN P)
    2377             : {
    2378         287 :   return RgXV_to_RgM(RgXQ_powers(y,m-1,P),n);
    2379             : }
    2380             : 
    2381             : GEN
    2382          56 : RgXQ_minpoly_naive(GEN y, GEN P)
    2383             : {
    2384          56 :   pari_sp ltop=avma;
    2385          56 :   long n=lgpol(P);
    2386          56 :   GEN M=ker(RgXQ_matrix_pow(y,n,n,P));
    2387          56 :   M=content(RgM_to_RgXV(M,varn(P)));
    2388          56 :   return gerepileupto(ltop,M);
    2389             : }
    2390             : 
    2391             : GEN
    2392       33029 : RgXQ_norm(GEN x, GEN T)
    2393             : {
    2394             :   pari_sp av;
    2395       33029 :   long dx = degpol(x);
    2396             :   GEN L, y;
    2397             : 
    2398       33029 :   av = avma; y = resultant(T, x);
    2399       33029 :   L = leading_coeff(T);
    2400       33029 :   if (gequal1(L) || !signe(x)) return y;
    2401           0 :   return gerepileupto(av, gdiv(y, gpowgs(L, dx)));
    2402             : }
    2403             : 
    2404             : GEN
    2405       70168 : RgX_blocks(GEN P, long n, long m)
    2406             : {
    2407       70168 :   GEN z = cgetg(m+1,t_VEC);
    2408       70168 :   long i,j, k=2, l = lg(P);
    2409      403956 :   for(i=1; i<=m; i++)
    2410             :   {
    2411      333788 :     GEN zi = cgetg(n+2,t_POL);
    2412      333788 :     zi[1] = P[1];
    2413      333788 :     gel(z,i) = zi;
    2414     2109373 :     for(j=2; j<n+2; j++)
    2415     1775585 :       gel(zi, j) = k==l ? gen_0 : gel(P,k++);
    2416      333788 :     zi = RgX_renormalize_lg(zi, n+2);
    2417             :   }
    2418       70168 :   return z;
    2419             : }
    2420             : 
    2421             : /* write p(X) = e(X^2) + Xo(X^2), shallow function */
    2422             : void
    2423       25535 : RgX_even_odd(GEN p, GEN *pe, GEN *po)
    2424             : {
    2425       25535 :   long n = degpol(p), v = varn(p), n0, n1, i;
    2426             :   GEN p0, p1;
    2427             : 
    2428       51070 :   if (n <= 0) { *pe = RgX_copy(p); *po = zeropol(v); return; }
    2429             : 
    2430       25535 :   n0 = (n>>1)+1; n1 = n+1 - n0; /* n1 <= n0 <= n1+1 */
    2431       25535 :   p0 = cgetg(n0+2, t_POL); p0[1] = evalvarn(v)|evalsigne(1);
    2432       25535 :   p1 = cgetg(n1+2, t_POL); p1[1] = evalvarn(v)|evalsigne(1);
    2433      674139 :   for (i=0; i<n1; i++)
    2434             :   {
    2435      648604 :     p0[2+i] = p[2+(i<<1)];
    2436      648604 :     p1[2+i] = p[3+(i<<1)];
    2437             :   }
    2438       25535 :   if (n1 != n0)
    2439       17766 :     p0[2+i] = p[2+(i<<1)];
    2440       25535 :   *pe = normalizepol(p0);
    2441       25535 :   *po = normalizepol(p1);
    2442             : }
    2443             : 
    2444             : /* write p(X) = a_0(X^k) + Xa_1(X^k) + ... + X^(k-1)a_{k-1}(X^k), shallow function */
    2445             : GEN
    2446       40642 : RgX_splitting(GEN p, long k)
    2447             : {
    2448       40642 :   long n = degpol(p), v = varn(p), m, i, j, l;
    2449             :   GEN r;
    2450             : 
    2451       40642 :   m = n/k;
    2452       40642 :   r = cgetg(k+1,t_VEC);
    2453      224154 :   for(i=1; i<=k; i++)
    2454             :   {
    2455      183512 :     gel(r,i) = cgetg(m+3, t_POL);
    2456      183512 :     mael(r,i,1) = evalvarn(v)|evalsigne(1);
    2457             :   }
    2458      552986 :   for (j=1, i=0, l=2; i<=n; i++)
    2459             :   {
    2460      512344 :     gmael(r,j,l) = gel(p,2+i);
    2461      512344 :     if (j==k) { j=1; l++; } else j++;
    2462             :   }
    2463      224154 :   for(i=1; i<=k; i++)
    2464      183512 :     gel(r,i) = normalizepol_lg(gel(r,i),i<j?l+1:l);
    2465       40642 :   return r;
    2466             : }
    2467             : 
    2468             : /*******************************************************************/
    2469             : /*                                                                 */
    2470             : /*                        Kronecker form                           */
    2471             : /*                                                                 */
    2472             : /*******************************************************************/
    2473             : 
    2474             : /* z in R[Y] representing an elt in R[X,Y] mod T(Y) in Kronecker form,
    2475             :  * i.e subst(lift(z), x, y^(2deg(z)-1)). Recover the "real" z, with
    2476             :  * normalized coefficients */
    2477             : GEN
    2478         189 : Kronecker_to_mod(GEN z, GEN T)
    2479             : {
    2480         189 :   long i,j,lx,l = lg(z), N = (degpol(T)<<1) + 1;
    2481         189 :   GEN x, t = cgetg(N,t_POL);
    2482         189 :   t[1] = T[1];
    2483         189 :   lx = (l-2) / (N-2); x = cgetg(lx+3,t_POL);
    2484         189 :   x[1] = z[1];
    2485         189 :   T = RgX_copy(T);
    2486        4389 :   for (i=2; i<lx+2; i++, z+= N-2)
    2487             :   {
    2488        4200 :     for (j=2; j<N; j++) gel(t,j) = gel(z,j);
    2489        4200 :     gel(x,i) = mkpolmod(RgX_rem(normalizepol_lg(t,N), T), T);
    2490             :   }
    2491         189 :   N = (l-2) % (N-2) + 2;
    2492         189 :   for (j=2; j<N; j++) t[j] = z[j];
    2493         189 :   gel(x,i) = mkpolmod(RgX_rem(normalizepol_lg(t,N), T), T);
    2494         189 :   return normalizepol_lg(x, i+1);
    2495             : }

Generated by: LCOV version 1.11