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 - gen3.c (source / functions) Hit Total Coverage
Test: PARI/GP v2.8.0 lcov report (development 19207-2ed2f69) Lines: 2037 2244 90.8 %
Date: 2016-07-25 07:10:32 Functions: 206 214 96.3 %
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             : /********************************************************************/
      15             : /**                                                                **/
      16             : /**                      GENERIC OPERATIONS                        **/
      17             : /**                         (third part)                           **/
      18             : /**                                                                **/
      19             : /********************************************************************/
      20             : #include "pari.h"
      21             : #include "paripriv.h"
      22             : 
      23             : /********************************************************************/
      24             : /**                                                                **/
      25             : /**                 PRINCIPAL VARIABLE NUMBER                      **/
      26             : /**                                                                **/
      27             : /********************************************************************/
      28             : static void
      29         329 : recvar(hashtable *h, GEN x)
      30             : {
      31         329 :   long i = 1, lx = lg(x);
      32             :   void *v;
      33         329 :   switch(typ(x))
      34             :   {
      35             :     case t_POL: case t_SER:
      36          84 :       v = (void*)varn(x);
      37          84 :       if (!hash_search(h, v)) hash_insert(h, v, NULL);
      38          84 :       i = 2; break;
      39             :     case t_POLMOD: case t_RFRAC:
      40          49 :     case t_VEC: case t_COL: case t_MAT: break;
      41             :     case t_LIST:
      42          14 :       x = list_data(x);
      43          14 :       lx = x? lg(x): 1; break;
      44             :     default:
      45         511 :       return;
      46             :   }
      47         147 :   for (; i < lx; i++) recvar(h, gel(x,i));
      48             : }
      49             : 
      50             : GEN
      51           7 : variables_vecsmall(GEN x)
      52             : {
      53           7 :   hashtable *h = hash_create_ulong(100, 1);
      54           7 :   recvar(h, x);
      55           7 :   return vars_sort_inplace(hash_keys(h));
      56             : }
      57             : 
      58             : GEN
      59          14 : variables_vec(GEN x)
      60          14 : { return x? vars_to_RgXV(variables_vecsmall(x)): gpolvar(NULL); }
      61             : 
      62             : long
      63    98869365 : gvar(GEN x)
      64             : {
      65             :   long i, v, w, lx;
      66    98869365 :   switch(typ(x))
      67             :   {
      68    32731593 :     case t_POL: case t_SER: return varn(x);
      69      110012 :     case t_POLMOD: return varn(gel(x,1));
      70    13001120 :     case t_RFRAC:  return varn(gel(x,2));
      71             :     case t_VEC: case t_COL: case t_MAT:
      72     2494079 :       lx = lg(x); break;
      73             :     case t_LIST:
      74          14 :       x = list_data(x);
      75          14 :       lx = x? lg(x): 1; break;
      76             :     default:
      77    50532547 :       return NO_VARIABLE;
      78             :   }
      79     2494093 :   v = NO_VARIABLE;
      80     2494093 :   for (i=1; i < lx; i++) { w = gvar(gel(x,i)); if (varncmp(w,v) < 0) v = w; }
      81     2494093 :   return v;
      82             : }
      83             : /* T main polynomial in R[X], A auxiliary in R[X] (possibly degree 0).
      84             :  * Guess and return the main variable of R */
      85             : static long
      86        8561 : var2_aux(GEN T, GEN A)
      87             : {
      88        8561 :   long a = gvar2(T);
      89        8561 :   long b = (typ(A) == t_POL && varn(A) == varn(T))? gvar2(A): gvar(A);
      90        8561 :   if (varncmp(a, b) > 0) a = b;
      91        8561 :   return a;
      92             : }
      93             : static long
      94        7035 : var2_rfrac(GEN x)  { return var2_aux(gel(x,2), gel(x,1)); }
      95             : static long
      96        1526 : var2_polmod(GEN x) { return var2_aux(gel(x,1), gel(x,2)); }
      97             : 
      98             : /* main variable of x, with the convention that the "natural" main
      99             :  * variable of a POLMOD is mute, so we want the next one. */
     100             : static long
     101       47789 : gvar9(GEN x)
     102       47789 : { return (typ(x) == t_POLMOD)? var2_polmod(x): gvar(x); }
     103             : 
     104             : /* main variable of the ring over wich x is defined */
     105             : long
     106    19904011 : gvar2(GEN x)
     107             : {
     108             :   long i, v, w;
     109    19904011 :   switch(typ(x))
     110             :   {
     111             :     case t_POLMOD:
     112           7 :       return var2_polmod(x);
     113             :     case t_POL: case t_SER:
     114       14672 :       v = NO_VARIABLE;
     115       61656 :       for (i=2; i < lg(x); i++) {
     116       46984 :         w = gvar9(gel(x,i));
     117       46984 :         if (varncmp(w,v) < 0) v=w;
     118             :       }
     119       14672 :       return v;
     120             :     case t_RFRAC:
     121        7035 :       return var2_rfrac(x);
     122             :     case t_VEC: case t_COL: case t_MAT:
     123          49 :       v = NO_VARIABLE;
     124         147 :       for (i=1; i < lg(x); i++) {
     125          98 :         w = gvar2(gel(x,i));
     126          98 :         if (varncmp(w,v)<0) v=w;
     127             :       }
     128          49 :       return v;
     129             :   }
     130    19882248 :   return NO_VARIABLE;
     131             : }
     132             : 
     133             : /*******************************************************************/
     134             : /*                                                                 */
     135             : /*                    PRECISION OF SCALAR OBJECTS                  */
     136             : /*                                                                 */
     137             : /*******************************************************************/
     138             : static long
     139       10914 : prec0(long e) { return (e < 0)? nbits2prec(-e): 2; }
     140             : static long
     141      920461 : precREAL(GEN x) { return signe(x) ? realprec(x): prec0(expo(x)); }
     142             : /* x t_REAL, y an exact non-complex type. Return precision(|x| + |y|) */
     143             : static long
     144      326712 : precrealexact(GEN x, GEN y)
     145             : {
     146      326712 :   long lx, ey = gexpo(y), ex, e;
     147      326712 :   if (ey == -(long)HIGHEXPOBIT) return precREAL(x);
     148      324542 :   ex = expo(x);
     149      324542 :   e = ey - ex;
     150      324542 :   if (!signe(x)) return prec0((e >= 0)? -e: ex);
     151      324269 :   lx = realprec(x);
     152      324269 :   return (e > 0)? lx + nbits2extraprec(e): lx;
     153             : }
     154             : static long
     155     1951788 : precCOMPLEX(GEN z)
     156             : { /* ~ precision(|x| + |y|) */
     157     1951788 :   GEN x = gel(z,1), y = gel(z,2);
     158             :   long e, ex, ey, lz, lx, ly;
     159     1951788 :   if (typ(x) != t_REAL) {
     160      336280 :     if (typ(y) != t_REAL) return 0;
     161      325318 :     return precrealexact(y, x);
     162             :   }
     163     1615508 :   if (typ(y) != t_REAL) return precrealexact(x, y);
     164             :   /* x, y are t_REALs, cf addrr_sign */
     165     1614114 :   ex = expo(x);
     166     1614114 :   ey = expo(y);
     167     1614114 :   e = ey - ex;
     168     1614114 :   if (!signe(x)) {
     169       41654 :     if (!signe(y)) return prec0( minss(ex,ey) );
     170       41626 :     if (e <= 0) return prec0(ex);
     171       41556 :     lz = nbits2prec(e);
     172       41556 :     ly = realprec(y); if (lz > ly) lz = ly;
     173       41556 :     return lz;
     174             :   }
     175     1572460 :   if (!signe(y)) {
     176       38806 :     if (e >= 0) return prec0(ey);
     177       38778 :     lz = nbits2prec(-e);
     178       38778 :     lx = realprec(x); if (lz > lx) lz = lx;
     179       38778 :     return lz;
     180             :   }
     181     1533654 :   if (e < 0) { swap(x, y); e = -e; }
     182     1533654 :   lx = realprec(x);
     183     1533654 :   ly = realprec(y);
     184     1533654 :   if (e) {
     185     1191129 :     long d = nbits2extraprec(e), l = ly-d;
     186     1191129 :     return (l > lx)? lx + d: ly;
     187             :   }
     188      342525 :   return minss(lx, ly);
     189             : }
     190             : long
     191     1253175 : precision(GEN z)
     192             : {
     193     1253175 :   switch(typ(z))
     194             :   {
     195      182781 :     case t_REAL: return precREAL(z);
     196      813035 :     case t_COMPLEX: return precCOMPLEX(z);
     197             :   }
     198      257359 :   return 0;
     199             : }
     200             : 
     201             : long
     202     2630846 : gprecision(GEN x)
     203             : {
     204             :   long i, k, l;
     205             : 
     206     2630846 :   switch(typ(x))
     207             :   {
     208      735510 :     case t_REAL: return precREAL(x);
     209     1138753 :     case t_COMPLEX: return precCOMPLEX(x);
     210             :     case t_INT: case t_INTMOD: case t_FRAC: case t_FFELT:
     211             :     case t_PADIC: case t_QUAD: case t_POLMOD:
     212      134249 :       return 0;
     213             : 
     214             :     case t_POL: case t_SER:
     215          56 :       k = LONG_MAX;
     216         455 :       for (i=lg(x)-1; i>1; i--)
     217             :       {
     218         399 :         l = gprecision(gel(x,i));
     219         399 :         if (l && l<k) k = l;
     220             :       }
     221          56 :       return (k==LONG_MAX)? 0: k;
     222             :     case t_VEC: case t_COL: case t_MAT:
     223      622264 :       k = LONG_MAX;
     224     2716831 :       for (i=lg(x)-1; i>0; i--)
     225             :       {
     226     2094567 :         l = gprecision(gel(x,i));
     227     2094567 :         if (l && l<k) k = l;
     228             :       }
     229      622264 :       return (k==LONG_MAX)? 0: k;
     230             : 
     231             :     case t_RFRAC:
     232             :     {
     233           7 :       k=gprecision(gel(x,1));
     234           7 :       l=gprecision(gel(x,2)); if (l && (!k || l<k)) k=l;
     235           7 :       return k;
     236             :     }
     237             :     case t_QFR:
     238           7 :       return gprecision(gel(x,4));
     239             :   }
     240           0 :   return 0;
     241             : }
     242             : 
     243             : GEN
     244        3276 : precision0(GEN x, long n)
     245             : {
     246             :   long a;
     247        3276 :   if (n) return gprec(x,n);
     248        3248 :   a = gprecision(x);
     249        3248 :   return a? utoi(prec2ndec(a)): mkoo();
     250             : }
     251             : 
     252             : GEN
     253          35 : bitprecision0(GEN x, long n)
     254             : {
     255             :   long a;
     256          35 :   if (n < 0)
     257           0 :     pari_err_DOMAIN("bitprecision", "bitprecision", "<", gen_0, stoi(n));
     258          35 :   if (n) {
     259          21 :     pari_sp av = avma;
     260          21 :     GEN y = gprec_w(x, nbits2prec(n));
     261          21 :     return gerepilecopy(av, y);
     262             :   }
     263          14 :   a = gprecision(x);
     264          14 :   return a? utoi(prec2nbits(a)): mkoo();
     265             : }
     266             : 
     267             : static long
     268         224 : vec_padicprec_relative(GEN x, long imin)
     269             : {
     270             :   long s, t, i;
     271         819 :   for (s=LONG_MAX, i=lg(x)-1; i>=imin; i--)
     272             :   {
     273         595 :     t = padicprec_relative(gel(x,i)); if (t<s) s = t;
     274             :   }
     275         224 :   return s;
     276             : }
     277             : /* RELATIVE padic precision. Only accept decent types: don't try to make sense
     278             :  * of everything like padicprec */
     279             : long
     280         826 : padicprec_relative(GEN x)
     281             : {
     282         826 :   switch(typ(x))
     283             :   {
     284             :     case t_INT: case t_FRAC:
     285         189 :       return LONG_MAX;
     286             :     case t_PADIC:
     287         413 :       return signe(gel(x,4))? precp(x): 0;
     288             :     case t_POLMOD: case t_VEC: case t_COL: case t_MAT:
     289         140 :       return vec_padicprec_relative(x, 1);
     290             :     case t_POL: case t_SER:
     291          84 :       return vec_padicprec_relative(x, 2);
     292             :   }
     293           0 :   pari_err_TYPE("padicprec_relative",x);
     294           0 :   return 0; /* not reached */
     295             : }
     296             : 
     297             : static long
     298          21 : vec_padicprec(GEN x, GEN p, long imin)
     299             : {
     300             :   long s, t, i;
     301          63 :   for (s=LONG_MAX, i=lg(x)-1; i>=imin; i--)
     302             :   {
     303          42 :     t = padicprec(gel(x,i),p); if (t<s) s = t;
     304             :   }
     305          21 :   return s;
     306             : }
     307             : static long
     308          14 : vec_serprec(GEN x, long v, long imin)
     309             : {
     310             :   long s, t, i;
     311          42 :   for (s=LONG_MAX, i=lg(x)-1; i>=imin; i--)
     312             :   {
     313          28 :     t = serprec(gel(x,i),v); if (t<s) s = t;
     314             :   }
     315          14 :   return s;
     316             : }
     317             : 
     318             : /* ABSOLUTE padic precision */
     319             : long
     320         147 : padicprec(GEN x, GEN p)
     321             : {
     322         147 :   if (typ(p) != t_INT) pari_err_TYPE("padicprec",p);
     323         140 :   switch(typ(x))
     324             :   {
     325             :     case t_INT: case t_FRAC:
     326          42 :       return LONG_MAX;
     327             : 
     328             :     case t_INTMOD:
     329           7 :       return Z_pval(gel(x,1),p);
     330             : 
     331             :     case t_PADIC:
     332          70 :       if (!equalii(gel(x,2),p)) pari_err_MODULUS("padicprec", gel(x,2), p);
     333          63 :       return precp(x)+valp(x);
     334             : 
     335             :     case t_POL: case t_SER:
     336          14 :       return vec_padicprec(x, p, 2);
     337             :     case t_COMPLEX: case t_QUAD: case t_POLMOD: case t_RFRAC:
     338             :     case t_VEC: case t_COL: case t_MAT:
     339           7 :       return vec_padicprec(x, p, 1);
     340             :   }
     341           0 :   pari_err_TYPE("padicprec",x);
     342           0 :   return 0; /* not reached */
     343             : }
     344             : GEN
     345         105 : gppadicprec(GEN x, GEN p)
     346             : {
     347         105 :   long v = padicprec(x,p);
     348          91 :   return v == LONG_MAX? mkoo(): stoi(v);
     349             : }
     350             : 
     351             : /* ABSOLUTE padic precision */
     352             : long
     353          56 : serprec(GEN x, long v)
     354             : {
     355             :   long w;
     356          56 :   switch(typ(x))
     357             :   {
     358             :     case t_INT: case t_REAL: case t_INTMOD: case t_FRAC: case t_FFELT:
     359             :     case t_COMPLEX: case t_PADIC: case t_QUAD: case t_QFR:
     360          21 :       return LONG_MAX;
     361             : 
     362             :     case t_POL:
     363           7 :       w = varn(x);
     364           7 :       if (varncmp(v,w) <= 0) return LONG_MAX;
     365           7 :       return vec_serprec(x, v, 2);
     366             :     case t_SER:
     367          28 :       w = varn(x);
     368          28 :       if (w == v) return lg(x)-2+valp(x);
     369           7 :       if (varncmp(v,w) < 0) return LONG_MAX;
     370           7 :       return vec_serprec(x, v, 2);
     371             :     case t_POLMOD: case t_RFRAC: case t_VEC: case t_COL: case t_MAT:
     372           0 :       return vec_serprec(x, v, 1);
     373             :   }
     374           0 :   pari_err_TYPE("serprec",x);
     375           0 :   return 0; /* not reached */
     376             : }
     377             : GEN
     378          28 : gpserprec(GEN x, long v)
     379             : {
     380          28 :   long p = serprec(x,v);
     381          28 :   return p == LONG_MAX? mkoo(): stoi(p);
     382             : }
     383             : 
     384             : /* Degree of x (scalar, t_POL, t_RFRAC) wrt variable v if v >= 0,
     385             :  * wrt to main variable if v < 0. */
     386             : long
     387        9161 : poldegree(GEN x, long v)
     388             : {
     389        9161 :   const long DEGREE0 = -LONG_MAX;
     390        9161 :   long tx = typ(x), lx,w,i,d;
     391             : 
     392        9161 :   if (is_scalar_t(tx)) return gequal0(x)? DEGREE0: 0;
     393        8881 :   switch(tx)
     394             :   {
     395             :     case t_POL:
     396        8867 :       if (!signe(x)) return DEGREE0;
     397        8860 :       w = varn(x);
     398        8860 :       if (v < 0 || v == w) return degpol(x);
     399         112 :       if (varncmp(v, w) < 0) return 0;
     400         112 :       lx = lg(x); d = DEGREE0;
     401         546 :       for (i=2; i<lx; i++)
     402             :       {
     403         434 :         long e = poldegree(gel(x,i), v);
     404         434 :         if (e > d) d = e;
     405             :       }
     406         112 :       return d;
     407             : 
     408             :     case t_RFRAC:
     409          14 :       if (gequal0(gel(x,1))) return DEGREE0;
     410           7 :       return poldegree(gel(x,1),v) - poldegree(gel(x,2),v);
     411             :   }
     412           0 :   pari_err_TYPE("degree",x);
     413           0 :   return 0; /* not reached  */
     414             : }
     415             : GEN
     416        5089 : gppoldegree(GEN x, long v)
     417             : {
     418        5089 :   long d = poldegree(x,v);
     419        5089 :   return d == -LONG_MAX? mkmoo(): stoi(d);
     420             : }
     421             : 
     422             : /* assume v >= 0 and x is a POLYNOMIAL in v, return deg_v(x) */
     423             : long
     424       22148 : RgX_degree(GEN x, long v)
     425             : {
     426       22148 :   long tx = typ(x), lx, w, i, d;
     427             : 
     428       22148 :   if (is_scalar_t(tx)) return gequal0(x)? -1: 0;
     429       14644 :   switch(tx)
     430             :   {
     431             :     case t_POL:
     432       14644 :       if (!signe(x)) return -1;
     433       14630 :       w = varn(x);
     434       14630 :       if (v == w) return degpol(x);
     435        4956 :       if (varncmp(v, w) < 0) return 0;
     436        4956 :       lx = lg(x); d = -1;
     437       21742 :       for (i=2; i<lx; i++)
     438             :       {
     439       16786 :         long e = RgX_degree(gel(x,i), v);
     440       16786 :         if (e > d) d = e;
     441             :       }
     442        4956 :       return d;
     443             : 
     444             :     case t_RFRAC:
     445           0 :       w = varn(gel(x,2));
     446           0 :       if (varncmp(v, w) < 0) return 0;
     447           0 :       if (RgX_degree(gel(x,2),v)) pari_err_TYPE("RgX_degree", x);
     448           0 :       return RgX_degree(gel(x,1),v);
     449             :   }
     450           0 :   pari_err_TYPE("RgX_degree",x);
     451           0 :   return 0; /* not reached  */
     452             : }
     453             : 
     454             : long
     455           0 : degree(GEN x)
     456             : {
     457           0 :   return poldegree(x,-1);
     458             : }
     459             : 
     460             : /* If v<0, leading coeff with respect to the main variable, otherwise wrt v. */
     461             : GEN
     462        3376 : pollead(GEN x, long v)
     463             : {
     464        3376 :   long tx = typ(x), w;
     465             :   pari_sp av;
     466             : 
     467        3376 :   if (is_scalar_t(tx)) return gcopy(x);
     468        3376 :   w = varn(x);
     469        3376 :   switch(tx)
     470             :   {
     471             :     case t_POL:
     472        3348 :       if (v < 0 || v == w)
     473             :       {
     474        3306 :         long l = lg(x);
     475        3306 :         return (l==2)? gen_0: gcopy(gel(x,l-1));
     476             :       }
     477          42 :       break;
     478             : 
     479             :     case t_SER:
     480          28 :       if (v < 0 || v == w) return signe(x)? gcopy(gel(x,2)): gen_0;
     481           7 :       if (varncmp(v, w) > 0) x = polcoeff_i(x, valp(x), v);
     482           7 :       break;
     483             : 
     484             :     default:
     485           0 :       pari_err_TYPE("pollead",x);
     486           0 :       return NULL; /* not reached */
     487             :   }
     488          49 :   if (varncmp(v, w) < 0) return gcopy(x);
     489          28 :   av = avma; w = fetch_var_higher();
     490          28 :   x = gsubst(x, v, pol_x(w));
     491          28 :   x = pollead(x, w);
     492          28 :   delete_var(); return gerepileupto(av, x);
     493             : }
     494             : 
     495             : /* returns 1 if there's a real component in the structure, 0 otherwise */
     496             : int
     497       13125 : isinexactreal(GEN x)
     498             : {
     499             :   long i;
     500       13125 :   switch(typ(x))
     501             :   {
     502         910 :     case t_REAL: return 1;
     503        2058 :     case t_COMPLEX: return (typ(gel(x,1))==t_REAL || typ(gel(x,2))==t_REAL);
     504             : 
     505             :     case t_INT: case t_INTMOD: case t_FRAC:
     506             :     case t_FFELT: case t_PADIC: case t_QUAD:
     507        8575 :     case t_QFR: case t_QFI: return 0;
     508             : 
     509             :     case t_RFRAC: case t_POLMOD:
     510           0 :       return isinexactreal(gel(x,1)) || isinexactreal(gel(x,2));
     511             : 
     512             :     case t_POL: case t_SER:
     513        7658 :       for (i=lg(x)-1; i>1; i--)
     514        6076 :         if (isinexactreal(gel(x,i))) return 1;
     515        1582 :       return 0;
     516             : 
     517             :     case t_VEC: case t_COL: case t_MAT:
     518           0 :       for (i=lg(x)-1; i>0; i--)
     519           0 :         if (isinexactreal(gel(x,i))) return 1;
     520           0 :       return 0;
     521           0 :     default: return 0;
     522             :   }
     523             : }
     524             : /* Check if x is approximately real with precision e */
     525             : int
     526       77844 : isrealappr(GEN x, long e)
     527             : {
     528             :   long i;
     529       77844 :   switch(typ(x))
     530             :   {
     531             :     case t_INT: case t_REAL: case t_FRAC:
     532       23880 :       return 1;
     533             :     case t_COMPLEX:
     534       53964 :       return (gexpo(gel(x,2)) < e);
     535             : 
     536             :     case t_POL: case t_SER:
     537           0 :       for (i=lg(x)-1; i>1; i--)
     538           0 :         if (! isrealappr(gel(x,i),e)) return 0;
     539           0 :       return 1;
     540             : 
     541             :     case t_RFRAC: case t_POLMOD:
     542           0 :       return isrealappr(gel(x,1),e) && isrealappr(gel(x,2),e);
     543             : 
     544             :     case t_VEC: case t_COL: case t_MAT:
     545           0 :       for (i=lg(x)-1; i>0; i--)
     546           0 :         if (! isrealappr(gel(x,i),e)) return 0;
     547           0 :       return 1;
     548           0 :     default: pari_err_TYPE("isrealappr",x); return 0;
     549             :   }
     550             : }
     551             : 
     552             : /* returns 1 if there's an inexact component in the structure, and
     553             :  * 0 otherwise. */
     554             : int
     555   128557513 : isinexact(GEN x)
     556             : {
     557             :   long lx, i;
     558             : 
     559   128557513 :   switch(typ(x))
     560             :   {
     561             :     case t_REAL: case t_PADIC: case t_SER:
     562        2135 :       return 1;
     563             :     case t_INT: case t_INTMOD: case t_FFELT: case t_FRAC:
     564             :     case t_QFR: case t_QFI:
     565    86810538 :       return 0;
     566             :     case t_COMPLEX: case t_QUAD: case t_RFRAC: case t_POLMOD:
     567     2378345 :       return isinexact(gel(x,1)) || isinexact(gel(x,2));
     568             :     case t_POL:
     569   122712632 :       for (i=lg(x)-1; i>1; i--)
     570    83347796 :         if (isinexact(gel(x,i))) return 1;
     571    39364836 :       return 0;
     572             :     case t_VEC: case t_COL: case t_MAT:
     573        8043 :       for (i=lg(x)-1; i>0; i--)
     574        6524 :         if (isinexact(gel(x,i))) return 1;
     575        1519 :       return 0;
     576             :     case t_LIST:
     577           0 :       x = list_data(x); lx = x? lg(x): 1;
     578           0 :       for (i=1; i<lx; i++)
     579           0 :         if (isinexact(gel(x,i))) return 1;
     580           0 :       return 0;
     581             :   }
     582           0 :   return 0;
     583             : }
     584             : 
     585             : int
     586           0 : isrationalzeroscalar(GEN g)
     587             : {
     588           0 :   switch (typ(g))
     589             :   {
     590           0 :     case t_INT:     return !signe(g);
     591           0 :     case t_COMPLEX: return isintzero(gel(g,1)) && isintzero(gel(g,2));
     592           0 :     case t_QUAD:    return isintzero(gel(g,2)) && isintzero(gel(g,3));
     593             :   }
     594           0 :   return 0;
     595             : }
     596             : 
     597             : int
     598          21 : iscomplex(GEN x)
     599             : {
     600          21 :   switch(typ(x))
     601             :   {
     602             :     case t_INT: case t_REAL: case t_FRAC:
     603          14 :       return 0;
     604             :     case t_COMPLEX:
     605           7 :       return !gequal0(gel(x,2));
     606             :     case t_QUAD:
     607           0 :       return signe(gmael(x,1,2)) > 0;
     608             :   }
     609           0 :   pari_err_TYPE("iscomplex",x);
     610           0 :   return 0; /* not reached */
     611             : }
     612             : 
     613             : /*******************************************************************/
     614             : /*                                                                 */
     615             : /*                    GENERIC REMAINDER                            */
     616             : /*                                                                 */
     617             : /*******************************************************************/
     618             : /* euclidean quotient for scalars of admissible types */
     619             : static GEN
     620         602 : _quot(GEN x, GEN y)
     621             : {
     622         602 :   GEN q = gdiv(x,y), f = gfloor(q);
     623         385 :   if (gsigne(y) < 0 && !gequal(f,q)) f = gaddgs(f, 1);
     624         385 :   return f;
     625             : }
     626             : /* y t_REAL, x \ y */
     627             : static GEN
     628          70 : _quotsr(long x, GEN y)
     629             : {
     630             :   GEN q, f;
     631          70 :   if (!x) return gen_0;
     632          70 :   q = divsr(x,y); f = floorr(q);
     633          70 :   if (signe(y) < 0 && signe(subir(f,q))) f = addiu(f, 1);
     634          70 :   return f;
     635             : }
     636             : /* x t_REAL, x \ y */
     637             : static GEN
     638          28 : _quotrs(GEN x, long y)
     639             : {
     640          28 :   GEN q = divrs(x,y), f = floorr(q);
     641          28 :   if (y < 0 && signe(subir(f,q))) f = addiu(f, 1);
     642          28 :   return f;
     643             : }
     644             : static GEN
     645           7 : _quotri(GEN x, GEN y)
     646             : {
     647           7 :   GEN q = divri(x,y), f = floorr(q);
     648           7 :   if (signe(y) < 0 && signe(subir(f,q))) f = addiu(f, 1);
     649           7 :   return f;
     650             : }
     651             : 
     652             : /* y t_FRAC, x \ y */
     653             : static GEN
     654          35 : _quotsf(long x, GEN y)
     655          35 : { return truedivii(mulis(gel(y,2),x), gel(y,1)); }
     656             : /* x t_FRAC, x \ y */
     657             : static GEN
     658          77 : _quotfs(GEN x, long y)
     659          77 : { return truedivii(gel(x,1),mulis(gel(x,2),y)); }
     660             : /* x t_FRAC, y t_INT, x \ y */
     661             : static GEN
     662           7 : _quotfi(GEN x, GEN y)
     663           7 : { return truedivii(gel(x,1),mulii(gel(x,2),y)); }
     664             : 
     665             : static GEN
     666         553 : quot(GEN x, GEN y)
     667         553 : { pari_sp av = avma; return gerepileupto(av, _quot(x, y)); }
     668             : static GEN
     669          14 : quotrs(GEN x, long y)
     670          14 : { pari_sp av = avma; return gerepileuptoleaf(av, _quotrs(x,y)); }
     671             : static GEN
     672          77 : quotfs(GEN x, long s)
     673          77 : { pari_sp av = avma; return gerepileuptoleaf(av, _quotfs(x,s)); }
     674             : static GEN
     675          35 : quotsr(long x, GEN y)
     676          35 : { pari_sp av = avma; return gerepileuptoleaf(av, _quotsr(x, y)); }
     677             : static GEN
     678          35 : quotsf(long x, GEN y)
     679          35 : { pari_sp av = avma; return gerepileuptoleaf(av, _quotsf(x, y)); }
     680             : static GEN
     681           7 : quotfi(GEN x, GEN y)
     682           7 : { pari_sp av = avma; return gerepileuptoleaf(av, _quotfi(x, y)); }
     683             : static GEN
     684           7 : quotri(GEN x, GEN y)
     685           7 : { pari_sp av = avma; return gerepileuptoleaf(av, _quotri(x, y)); }
     686             : 
     687             : static GEN
     688          14 : modrs(GEN x, long y)
     689             : {
     690          14 :   pari_sp av = avma;
     691          14 :   GEN q = _quotrs(x,y);
     692          14 :   if (!signe(q)) { avma = av; return rcopy(x); }
     693           7 :   return gerepileuptoleaf(av, subri(x, mulis(q,y)));
     694             : }
     695             : static GEN
     696          35 : modsr(long x, GEN y)
     697             : {
     698          35 :   pari_sp av = avma;
     699          35 :   GEN q = _quotsr(x,y);
     700          35 :   if (!signe(q)) { avma = av; return stoi(x); }
     701           7 :   return gerepileuptoleaf(av, subsr(x, mulir(q,y)));
     702             : }
     703             : static GEN
     704          35 : modsf(long x, GEN y)
     705             : {
     706          35 :   pari_sp av = avma;
     707          35 :   return gerepileupto(av, gred_frac2(modii(mulis(gel(y,2),x), gel(y,1)), gel(y,2)));
     708             : }
     709             : 
     710             : /* assume y a t_REAL, x a t_INT, t_FRAC or t_REAL.
     711             :  * Return x mod y or NULL if accuracy error */
     712             : GEN
     713      450373 : modr_safe(GEN x, GEN y)
     714             : {
     715             :   GEN q, f;
     716             :   long e;
     717      450373 :   if (typ(x) == t_INT && !signe(x)) return gen_0;
     718      450373 :   q = gdiv(x,y); /* t_REAL */
     719             : 
     720      450373 :   e = expo(q);
     721      450373 :   if (e >= 0 && nbits2prec(e+1) > realprec(q)) return NULL;
     722      450373 :   f = floorr(q);
     723      450373 :   if (gsigne(y) < 0 && signe(subri(q,f))) f = addis(f, 1);
     724      450373 :   return signe(f)? gsub(x, mulir(f,y)): x;
     725             : }
     726             : 
     727             : GEN
     728     7727195 : gmod(GEN x, GEN y)
     729             : {
     730             :   pari_sp av;
     731             :   long i, lx, ty, tx;
     732             :   GEN z;
     733             : 
     734     7727195 :   tx = typ(x); if (tx == t_INT && !is_bigint(x)) return gmodsg(itos(x),y);
     735      307110 :   ty = typ(y); if (ty == t_INT && !is_bigint(y)) return gmodgs(x,itos(y));
     736      293455 :   if (is_matvec_t(tx))
     737             :   {
     738       14259 :     z = cgetg_copy(x, &lx);
     739       14259 :     for (i=1; i<lx; i++) gel(z,i) = gmod(gel(x,i),y);
     740       14154 :     return z;
     741             :   }
     742      279196 :   if (tx == t_POL || ty == t_POL) return grem(x,y);
     743        1071 :   if (!is_scalar_t(tx) || !is_scalar_t(ty)) pari_err_TYPE2("%",x,y);
     744        1015 :   switch(ty)
     745             :   {
     746             :     case t_INT:
     747         623 :       switch(tx)
     748             :       {
     749         106 :         case t_INT: return modii(x,y);
     750           7 :         case t_INTMOD: z=cgetg(3, t_INTMOD);
     751           7 :           gel(z,1) = gcdii(gel(x,1),y);
     752           7 :           gel(z,2) = modii(gel(x,2),gel(z,1)); return z;
     753         475 :         case t_FRAC: return Fp_div(gel(x,1),gel(x,2),y);
     754           7 :         case t_QUAD: z=cgetg(4,t_QUAD);
     755           7 :           gel(z,1) = ZX_copy(gel(x,1));
     756           7 :           gel(z,2) = gmod(gel(x,2),y);
     757           7 :           gel(z,3) = gmod(gel(x,3),y); return z;
     758           7 :         case t_PADIC: return padic_to_Fp(x, y);
     759             :         case t_REAL: /* NB: conflicting semantic with lift(x * Mod(1,y)). */
     760           7 :           av = avma;
     761           7 :           return gerepileuptoleaf(av, mpsub(x, mpmul(_quot(x,y),y)));
     762          14 :         default: pari_err_TYPE2("%",x,y);
     763             :       }
     764             :     case t_REAL: case t_FRAC:
     765         112 :       if (!is_real_t(tx)) pari_err_TYPE2("%",x,y);
     766          42 :       av = avma;
     767          42 :       return gerepileupto(av, gadd(x, gneg(gmul(_quot(x,y),y))));
     768             :   }
     769         280 :   pari_err_TYPE2("%",x,y);
     770           0 :   return NULL; /* not reached */
     771             : }
     772             : 
     773             : GEN
     774       13851 : gmodgs(GEN x, long y)
     775             : {
     776             :   ulong u;
     777       13851 :   long i, lx, tx = typ(x);
     778             :   GEN z;
     779       13851 :   if (is_matvec_t(tx))
     780             :   {
     781          84 :     z = cgetg_copy(x, &lx);
     782          84 :     for (i=1; i<lx; i++) gel(z,i) = gmodgs(gel(x,i),y);
     783          84 :     return z;
     784             :   }
     785       13767 :   if (!y) pari_err_INV("gmodgs",gen_0);
     786       13767 :   switch(tx)
     787             :   {
     788         529 :     case t_INT: return modis(x,y);
     789          14 :     case t_REAL: return modrs(x,y);
     790             : 
     791          21 :     case t_INTMOD: z=cgetg(3, t_INTMOD);
     792          21 :       u = (ulong)labs(y);
     793          21 :       i = ugcd(umodiu(gel(x,1), u), u);
     794          21 :       gel(z,1) = utoi(i);
     795          21 :       gel(z,2) = modis(gel(x,2), i); return z;
     796             : 
     797             :     case t_FRAC:
     798       13119 :       u = (ulong)labs(y);
     799       13119 :       return utoi( Fl_div(umodiu(gel(x,1), u),
     800       13119 :                           umodiu(gel(x,2), u), u) );
     801             : 
     802          14 :     case t_QUAD: z=cgetg(4,t_QUAD);
     803          14 :       gel(z,1) = ZX_copy(gel(x,1));
     804          14 :       gel(z,2) = gmodgs(gel(x,2),y);
     805          14 :       gel(z,3) = gmodgs(gel(x,3),y); return z;
     806             : 
     807          14 :     case t_PADIC: return padic_to_Fp(x, stoi(y));
     808          14 :     case t_POL: return scalarpol(RgX_get_0(x), varn(x));
     809          14 :     case t_POLMOD: return gmul(gen_0,x);
     810             :   }
     811          28 :   pari_err_TYPE2("%",x,stoi(y));
     812           0 :   return NULL; /* not reached */
     813             : }
     814             : GEN
     815     7420085 : gmodsg(long x, GEN y)
     816             : {
     817     7420085 :   switch(typ(y))
     818             :   {
     819     7406100 :     case t_INT: return modsi(x,y);
     820          35 :     case t_REAL: return modsr(x,y);
     821          35 :     case t_FRAC: return modsf(x,y);
     822             :     case t_POL:
     823       13775 :       if (!signe(y)) pari_err_INV("gmodsg",y);
     824       13775 :       return degpol(y)? gmulsg(x, RgX_get_1(y)): RgX_get_0(y);
     825             :   }
     826         140 :   pari_err_TYPE2("%",stoi(x),y);
     827           0 :   return NULL; /* not reached */
     828             : }
     829             : /* divisibility: return 1 if y | x, 0 otherwise */
     830             : int
     831        3850 : gdvd(GEN x, GEN y)
     832             : {
     833        3850 :   pari_sp av = avma;
     834        3850 :   int t = gequal0( gmod(x,y) ); avma = av; return t;
     835             : }
     836             : 
     837             : GEN
     838      600371 : gmodulss(long x, long y)
     839             : {
     840      600371 :   if (!y) pari_err_INV("%",gen_0);
     841      600364 :   retmkintmod(modss(x, y), utoi(labs(y)));
     842             : }
     843             : GEN
     844      695482 : gmodulsg(long x, GEN y)
     845             : {
     846      695482 :   switch(typ(y))
     847             :   {
     848             :     case t_INT:
     849      636320 :       if (!is_bigint(y)) return gmodulss(x,itos(y));
     850       35958 :       retmkintmod(modsi(x,y), absi(y));
     851             :     case t_POL:
     852       59155 :       if (!signe(y)) pari_err_INV("%", y);
     853       59148 :       retmkpolmod(stoi(x),RgX_copy(y));
     854             :   }
     855           7 :   pari_err_TYPE2("%",stoi(x),y); return NULL; /* not reached */
     856             : }
     857             : GEN
     858      822996 : gmodulo(GEN x,GEN y)
     859             : {
     860      822996 :   long tx = typ(x), vx, vy;
     861      822996 :   if (tx == t_INT && !is_bigint(x)) return gmodulsg(itos(x), y);
     862      127618 :   if (is_matvec_t(tx))
     863             :   {
     864             :     long l, i;
     865        1120 :     GEN z = cgetg_copy(x, &l);
     866        1120 :     for (i=1; i<l; i++) gel(z,i) = gmodulo(gel(x,i),y);
     867        1120 :     return z;
     868             :   }
     869      126500 :   switch(typ(y))
     870             :   {
     871             :     case t_INT:
     872         190 :       if (!is_const_t(tx)) return gmul(x, gmodulsg(1,y));
     873         176 :       if (tx == t_INTMOD) return gmod(x,y);
     874         169 :       retmkintmod(Rg_to_Fp(x,y), absi(y));
     875             :     case t_POL:
     876      126310 :       vx = gvar(x); vy = varn(y);
     877      126310 :       if (varncmp(vy, vx) > 0) return gmul(x, gmodulsg(1,y));
     878      126254 :       if (vx == vy && tx == t_POLMOD) return grem(x,y);
     879      126149 :       retmkpolmod(grem(x,y), RgX_copy(y));
     880             :   }
     881           0 :   pari_err_TYPE2("%",x,y); return NULL; /* not reached */
     882             : }
     883             : 
     884             : /*******************************************************************/
     885             : /*                                                                 */
     886             : /*                 GENERIC EUCLIDEAN DIVISION                      */
     887             : /*                                                                 */
     888             : /*******************************************************************/
     889             : GEN
     890     6085968 : gdivent(GEN x, GEN y)
     891             : {
     892             :   long tx, ty;
     893     6085968 :   tx = typ(x); if (tx == t_INT && !is_bigint(x)) return gdiventsg(itos(x),y);
     894        1828 :   ty = typ(y); if (ty == t_INT && !is_bigint(y)) return gdiventgs(x,itos(y));
     895        1477 :   if (is_matvec_t(tx))
     896             :   {
     897             :     long i, lx;
     898         189 :     GEN z = cgetg_copy(x, &lx);
     899         189 :     for (i=1; i<lx; i++) gel(z,i) = gdivent(gel(x,i),y);
     900          84 :     return z;
     901             :   }
     902        1288 :   if (tx == t_POL || ty == t_POL) return gdeuc(x,y);
     903         945 :   switch(ty)
     904             :   {
     905             :     case t_INT:
     906         105 :       switch(tx)
     907             :       {
     908           7 :         case t_INT: return truedivii(x,y);
     909           7 :         case t_REAL: return quotri(x,y);
     910           7 :         case t_FRAC: return quotfi(x,y);
     911             :       }
     912          84 :       break;
     913         210 :     case t_REAL: case t_FRAC: return quot(x,y);
     914             :   }
     915         714 :   pari_err_TYPE2("\\",x,y);
     916           0 :   return NULL; /* not reached */
     917             : }
     918             : 
     919             : GEN
     920        1429 : gdiventgs(GEN x, long y)
     921             : {
     922             :   long i, lx;
     923             :   GEN z;
     924        1429 :   switch(typ(x))
     925             :   {
     926         652 :     case t_INT:  return truedivis(x,y);
     927          14 :     case t_REAL: return quotrs(x,y);
     928          77 :     case t_FRAC: return quotfs(x,y);
     929          28 :     case t_POL:  return gdivgs(x,y);
     930             :     case t_VEC: case t_COL: case t_MAT:
     931         490 :       z = cgetg_copy(x, &lx);
     932         490 :       for (i=1; i<lx; i++) gel(z,i) = gdiventgs(gel(x,i),y);
     933         490 :       return z;
     934             :   }
     935         168 :   pari_err_TYPE2("\\",x,stoi(y));
     936           0 :   return NULL; /* not reached */
     937             : }
     938             : GEN
     939     6084140 : gdiventsg(long x, GEN y)
     940             : {
     941     6084140 :   switch(typ(y))
     942             :   {
     943     6083720 :     case t_INT:  return truedivsi(x,y);
     944          35 :     case t_REAL: return quotsr(x,y);
     945          35 :     case t_FRAC: return quotsf(x,y);
     946             :     case t_POL:
     947          70 :       if (!signe(y)) pari_err_INV("gdiventsg",y);
     948          70 :       return degpol(y)? RgX_get_0(y): gdivsg(x,gel(y,2));
     949             :   }
     950         280 :   pari_err_TYPE2("\\",stoi(x),y);
     951           0 :   return NULL; /* not reached */
     952             : }
     953             : 
     954             : /* with remainder */
     955             : static GEN
     956         343 : quotrem(GEN x, GEN y, GEN *r)
     957             : {
     958         343 :   GEN q = quot(x,y);
     959         280 :   pari_sp av = avma;
     960         280 :   *r = gerepileupto(av, gsub(x, gmul(q,y)));
     961         280 :   return q;
     962             : }
     963             : 
     964             : GEN
     965       21357 : gdiventres(GEN x, GEN y)
     966             : {
     967       21357 :   long tx = typ(x), ty = typ(y);
     968             :   GEN z,q,r;
     969             : 
     970       21357 :   if (is_matvec_t(tx))
     971             :   {
     972             :     long i, lx;
     973           7 :     z = cgetg_copy(x, &lx);
     974           7 :     for (i=1; i<lx; i++) gel(z,i) = gdiventres(gel(x,i),y);
     975           7 :     return z;
     976             :   }
     977       21350 :   z = cgetg(3,t_COL);
     978       21350 :   if (tx == t_POL || ty == t_POL)
     979             :   {
     980         168 :     gel(z,1) = poldivrem(x,y,(GEN*)(z+2));
     981         154 :     return z;
     982             :   }
     983       21182 :   switch(ty)
     984             :   {
     985             :     case t_INT:
     986       20685 :       switch(tx)
     987             :       { /* equal to, but more efficient than next case */
     988             :         case t_INT:
     989       20538 :           gel(z,1) = truedvmdii(x,y,(GEN*)(z+2));
     990       20538 :           return z;
     991             :         case t_REAL: case t_FRAC:
     992          42 :           q = quotrem(x,y,&r);
     993          42 :           gel(z,1) = q;
     994          42 :           gel(z,2) = r; return z;
     995             :       }
     996         105 :       break;
     997             :     case t_REAL: case t_FRAC:
     998         140 :           q = quotrem(x,y,&r);
     999          77 :           gel(z,1) = q;
    1000          77 :           gel(z,2) = r; return z;
    1001             :   }
    1002         462 :   pari_err_TYPE2("\\",x,y);
    1003           0 :   return NULL; /* not reached */
    1004             : }
    1005             : 
    1006             : GEN
    1007         896 : divrem(GEN x, GEN y, long v)
    1008             : {
    1009         896 :   pari_sp av = avma;
    1010             :   long vx, vy;
    1011             :   GEN q, r;
    1012         896 :   if (v < 0 || typ(y) != t_POL || typ(x) != t_POL) return gdiventres(x,y);
    1013           7 :   vx = varn(x); if (vx != v) x = swap_vars(x,v);
    1014           7 :   vy = varn(y); if (vy != v) y = swap_vars(y,v);
    1015           7 :   q = poldivrem(x,y, &r);
    1016           7 :   if (v && (vx != v || vy != v))
    1017             :   {
    1018           7 :     GEN X = pol_x(v);
    1019           7 :     q = gsubst(q, v, X); /* poleval broken for t_RFRAC, subst is safe */
    1020           7 :     r = gsubst(r, v, X);
    1021             :   }
    1022           7 :   return gerepilecopy(av, mkcol2(q, r));
    1023             : }
    1024             : 
    1025             : GEN
    1026    12690273 : diviiround(GEN x, GEN y)
    1027             : {
    1028    12690273 :   pari_sp av1, av = avma;
    1029             :   GEN q,r;
    1030             :   int fl;
    1031             : 
    1032    12690273 :   q = dvmdii(x,y,&r); /* q = x/y rounded towards 0, sgn(r)=sgn(x) */
    1033    12690266 :   if (r==gen_0) return q;
    1034     7921937 :   av1 = avma;
    1035     7921937 :   fl = absi_cmp(shifti(r,1),y);
    1036     7921937 :   avma = av1; cgiv(r);
    1037     7921937 :   if (fl >= 0) /* If 2*|r| >= |y| */
    1038             :   {
    1039     3830410 :     long sz = signe(x)*signe(y);
    1040     3830410 :     if (fl || sz > 0) q = gerepileuptoint(av, addis(q,sz));
    1041             :   }
    1042     7921937 :   return q;
    1043             : }
    1044             : 
    1045             : /* If x and y are not both scalars, same as gdivent.
    1046             :  * Otherwise, compute the quotient x/y, rounded to the nearest integer
    1047             :  * (towards +oo in case of tie). */
    1048             : GEN
    1049      496538 : gdivround(GEN x, GEN y)
    1050             : {
    1051             :   pari_sp av;
    1052      496538 :   long tx=typ(x),ty=typ(y);
    1053             :   GEN q,r;
    1054             : 
    1055      496538 :   if (tx==t_INT && ty==t_INT) return diviiround(x,y);
    1056       50036 :   av = avma;
    1057       50036 :   if (is_real_t(tx) && is_real_t(ty))
    1058             :   { /* same as diviiround but less efficient */
    1059             :     pari_sp av1;
    1060             :     int fl;
    1061         161 :     q = quotrem(x,y,&r);
    1062         161 :     av1 = avma;
    1063         161 :     fl = gcmp(gmul2n(R_abs_shallow(r),1), R_abs_shallow(y));
    1064         161 :     avma = av1; cgiv(r);
    1065         161 :     if (fl >= 0) /* If 2*|r| >= |y| */
    1066             :     {
    1067          42 :       long sz = gsigne(y);
    1068          42 :       if (fl || sz > 0) q = gerepileupto(av, gaddgs(q, sz));
    1069             :     }
    1070         161 :     return q;
    1071             :   }
    1072       49875 :   if (is_matvec_t(tx))
    1073             :   {
    1074             :     long i, lx;
    1075       49035 :     GEN z = cgetg_copy(x, &lx);
    1076       49035 :     for (i=1; i<lx; i++) gel(z,i) = gdivround(gel(x,i),y);
    1077       48930 :     return z;
    1078             :   }
    1079         840 :   return gdivent(x,y);
    1080             : }
    1081             : 
    1082             : GEN
    1083           0 : gdivmod(GEN x, GEN y, GEN *pr)
    1084             : {
    1085           0 :   switch(typ(x))
    1086             :   {
    1087             :     case t_INT:
    1088           0 :       switch(typ(y))
    1089             :       {
    1090           0 :         case t_INT: return dvmdii(x,y,pr);
    1091           0 :         case t_POL: *pr=icopy(x); return gen_0;
    1092             :       }
    1093           0 :       break;
    1094           0 :     case t_POL: return poldivrem(x,y,pr);
    1095             :   }
    1096           0 :   pari_err_TYPE2("gdivmod",x,y);
    1097           0 :   return NULL;
    1098             : }
    1099             : 
    1100             : /*******************************************************************/
    1101             : /*                                                                 */
    1102             : /*                               SHIFT                             */
    1103             : /*                                                                 */
    1104             : /*******************************************************************/
    1105             : 
    1106             : /* Shift tronque si n<0 (multiplication tronquee par 2^n)  */
    1107             : 
    1108             : GEN
    1109    40881001 : gshift(GEN x, long n)
    1110             : {
    1111             :   long i, lx;
    1112             :   GEN y;
    1113             : 
    1114    40881001 :   switch(typ(x))
    1115             :   {
    1116    37717146 :     case t_INT: return shifti(x,n);
    1117     3018807 :     case t_REAL:return shiftr(x,n);
    1118             : 
    1119             :     case t_VEC: case t_COL: case t_MAT:
    1120       13195 :       y = cgetg_copy(x, &lx);
    1121       13195 :       for (i=1; i<lx; i++) gel(y,i) = gshift(gel(x,i),n);
    1122       13195 :       return y;
    1123             :   }
    1124      131853 :   return gmul2n(x,n);
    1125             : }
    1126             : 
    1127             : /*******************************************************************/
    1128             : /*                                                                 */
    1129             : /*           SUBSTITUTION DANS UN POLYNOME OU UNE SERIE            */
    1130             : /*                                                                 */
    1131             : /*******************************************************************/
    1132             : 
    1133             : /* Convert t_SER --> t_POL, ignoring valp. INTERNAL ! */
    1134             : GEN
    1135     3221013 : ser2pol_i(GEN x, long lx)
    1136             : {
    1137     3221013 :   long i = lx-1;
    1138             :   GEN y;
    1139     3221013 :   while (i > 1 && isexactzero(gel(x,i))) i--;
    1140     3221013 :   y = cgetg(i+1, t_POL); y[1] = x[1] & ~VALPBITS;
    1141     3221013 :   for ( ; i > 1; i--) gel(y,i) = gel(x,i);
    1142     3221013 :   return y;
    1143             : }
    1144             : 
    1145             : /* x a t_SER, prec >= 0 */
    1146             : GEN
    1147         266 : sertoser(GEN x, long prec)
    1148             : {
    1149         266 :   long i, lx = lg(x);
    1150             :   GEN y;
    1151             : 
    1152         266 :   if (lx == 2) return zeroser(varn(x), prec);
    1153         266 :   y = cgetg(prec+2,t_SER); y[1] = x[1];
    1154         266 :   for (i = prec+1; i >= lx; i--) gel(y,i) = gen_0;
    1155         266 :   for (          ; i >= 2;  i--) gel(y,i) = gel(x,i);
    1156         266 :   return y;
    1157             : }
    1158             : 
    1159             : GEN
    1160         294 : inv_ser(GEN b)
    1161             : {
    1162         294 :   pari_sp av = avma;
    1163         294 :   long l = lg(b), e = valp(b), v = varn(b), prec = l-2;
    1164         294 :   GEN y = RgXn_inv(ser2pol_i(b, l), prec);
    1165         294 :   GEN x = poltoser(y, v, prec);
    1166         294 :   setvalp(x, -e); return gerepilecopy(av, x);
    1167             : }
    1168             : 
    1169             : /* T t_POL in var v, mod out by T components of x which are
    1170             :  * t_POL/t_RFRAC in v. Recursively */
    1171             : static GEN
    1172         168 : mod_r(GEN x, long v, GEN T)
    1173             : {
    1174         168 :   long i, w, lx, tx = typ(x);
    1175             :   GEN y;
    1176             : 
    1177         168 :   if (is_const_t(tx)) return x;
    1178         147 :   switch(tx)
    1179             :   {
    1180             :     case t_POLMOD:
    1181           7 :       w = varn(gel(x,1));
    1182           7 :       if (w == v) pari_err_PRIORITY("subst", gel(x,1), "=", v);
    1183           7 :       if (varncmp(v, w) < 0) return x;
    1184           7 :       return gmodulo(mod_r(gel(x,2),v,T), mod_r(gel(x,1),v,T));
    1185             :     case t_SER:
    1186           7 :       w = varn(x);
    1187           7 :       if (w == v) break; /* fail */
    1188           7 :       if (varncmp(v, w) < 0 || ser_isexactzero(x)) return x;
    1189           7 :       y = cgetg_copy(x, &lx); y[1] = x[1];
    1190           7 :       for (i = 2; i < lx; i++) gel(y,i) = mod_r(gel(x,i),v,T);
    1191           7 :       return normalize(y);
    1192             :     case t_POL:
    1193         112 :       w = varn(x);
    1194         112 :       if (w == v) return RgX_rem(x, T);
    1195          28 :       if (varncmp(v, w) < 0) return x;
    1196          28 :       y = cgetg_copy(x, &lx); y[1] = x[1];
    1197          28 :       for (i = 2; i < lx; i++) gel(y,i) = mod_r(gel(x,i),v,T);
    1198          28 :       return normalizepol_lg(y, lx);
    1199             :     case t_RFRAC:
    1200           7 :       return gdiv(mod_r(gel(x,1),v,T), mod_r(gel(x,2),v,T));
    1201             :     case t_VEC: case t_COL: case t_MAT:
    1202           7 :       y = cgetg_copy(x, &lx);
    1203           7 :       for (i = 1; i < lx; i++) gel(y,i) = mod_r(gel(x,i),v,T);
    1204           7 :       return y;
    1205             :     case t_LIST:
    1206           7 :       y = listcreate();
    1207           7 :       list_data(y) = list_data(x)? mod_r(list_data(x),v,T): NULL;
    1208           7 :       return y;
    1209             :   }
    1210           0 :   pari_err_TYPE("substpol",x);
    1211           0 :   return NULL;/*not reached*/
    1212             : }
    1213             : GEN
    1214          35 : gsubst_expr(GEN expr, GEN from, GEN to)
    1215             : {
    1216          35 :   pari_sp av = avma;
    1217          35 :   long w, v = fetch_var(); /* FIXME: Need fetch_var_low_priority() */
    1218             :   GEN y;
    1219             : 
    1220          35 :   from = simplify_shallow(from);
    1221          35 :   switch (typ(from)) {
    1222             :     case t_RFRAC: /* M= numerator(from) - t * denominator(from) */
    1223           7 :       y = gsub(gel(from,1), gmul(pol_x(v), gel(from,2)));
    1224           7 :       break;
    1225             :     default:
    1226          28 :       y = gsub(from, pol_x(v));        /* M = from - t */
    1227             :   }
    1228          35 :   w = gvar(from);
    1229          35 :   if (varncmp(v,w) <= 0) pari_err_PRIORITY("subst", pol_x(v), "<=", w);
    1230          35 :   y = gsubst(mod_r(expr, w, y), v, to);
    1231          35 :   (void)delete_var(); return gerepileupto(av, y);
    1232             : }
    1233             : 
    1234             : GEN
    1235          84 : gsubstpol(GEN x, GEN T, GEN y)
    1236             : {
    1237          84 :   if (typ(T) == t_POL && RgX_is_monomial(T) && gequal1(leading_coeff(T)))
    1238             :   { /* T = t^d */
    1239          77 :     long d = degpol(T), v = varn(T);
    1240          77 :     pari_sp av = avma;
    1241          77 :     GEN deflated = d == 1? x: gdeflate(x, v, d);
    1242          63 :     if (deflated) return gerepileupto(av, gsubst(deflated, v, y));
    1243          28 :     avma = av;
    1244             :   }
    1245          35 :   return gsubst_expr(x,T,y);
    1246             : }
    1247             : 
    1248             : long
    1249       14283 : RgX_deflate_order(GEN x)
    1250             : {
    1251       14283 :   ulong d = 0, i, lx = (ulong)lg(x);
    1252      581219 :   for (i=3; i<lx; i++)
    1253      575183 :     if (!gequal0(gel(x,i))) { d = ugcd(d,i-2); if (d == 1) return 1; }
    1254        6036 :   return d? (long)d: 1;
    1255             : }
    1256             : long
    1257       37627 : ZX_deflate_order(GEN x)
    1258             : {
    1259       37627 :   ulong d = 0, i, lx = (ulong)lg(x);
    1260      412726 :   for (i=3; i<lx; i++)
    1261      400278 :     if (signe(gel(x,i))) { d = ugcd(d,i-2); if (d == 1) return 1; }
    1262       12448 :   return d? (long)d: 1;
    1263             : }
    1264             : 
    1265             : /* deflate (non-leaf) x recursively */
    1266             : static GEN
    1267          63 : vdeflate(GEN x, long v, long d)
    1268             : {
    1269          63 :   long i = lontyp[typ(x)], lx;
    1270          63 :   GEN z = cgetg_copy(x, &lx);
    1271          63 :   if (i == 2) z[1] = x[1];
    1272         154 :   for (; i<lx; i++)
    1273             :   {
    1274         133 :     gel(z,i) = gdeflate(gel(x,i),v,d);
    1275         133 :     if (!z[i]) return NULL;
    1276             :   }
    1277          21 :   return z;
    1278             : }
    1279             : 
    1280             : /* don't return NULL if substitution fails (fallback won't be able to handle
    1281             :  * t_SER anyway), fail with a meaningful message */
    1282             : static GEN
    1283          35 : serdeflate(GEN x, long v, long d)
    1284             : {
    1285          35 :   long V, dy, lx, vx = varn(x);
    1286             :   pari_sp av;
    1287             :   GEN y;
    1288          35 :   if (varncmp(vx, v) < 0) return vdeflate(x,v,d);
    1289          28 :   if (varncmp(vx, v) > 0) return gcopy(x);
    1290          28 :   av = avma;
    1291          28 :   V = valp(x);
    1292          28 :   lx = lg(x);
    1293          28 :   if (lx == 2) return zeroser(v, V / d);
    1294          28 :   y = ser2pol_i(x, lx);
    1295          28 :   dy = degpol(y);
    1296          28 :   if (V % d != 0 || (dy > 0 && RgX_deflate_order(y) % d != 0))
    1297             :   {
    1298          14 :     const char *s = stack_sprintf("valuation(x) %% %ld", d);
    1299          14 :     pari_err_DOMAIN("gdeflate", s, "!=", gen_0,x);
    1300             :   }
    1301          14 :   if (dy > 0) y = RgX_deflate(y, d);
    1302          14 :   y = poltoser(y, v, 1 + (lx-3)/d);
    1303          14 :   setvalp(y, V/d); return gerepilecopy(av, y);
    1304             : }
    1305             : static GEN
    1306         112 : poldeflate(GEN x, long v, long d)
    1307             : {
    1308         112 :   long vx = varn(x);
    1309             :   pari_sp av;
    1310         112 :   if (varncmp(vx, v) < 0) return vdeflate(x,v,d);
    1311          84 :   if (varncmp(vx, v) > 0 || degpol(x) <= 0) return gcopy(x);
    1312          49 :   av = avma;
    1313             :   /* x non-constant */
    1314          49 :   if (RgX_deflate_order(x) % d != 0) return NULL;
    1315          21 :   return gerepilecopy(av, RgX_deflate(x,d));
    1316             : }
    1317             : static GEN
    1318          21 : listdeflate(GEN x, long v, long d)
    1319             : {
    1320          21 :   GEN y = NULL, z = listcreate();
    1321          21 :   if (list_data(x))
    1322             :   {
    1323          14 :     y = vdeflate(list_data(x),v,d);
    1324          14 :     if (!y) return NULL;
    1325             :   }
    1326          14 :   list_data(z) = y; return z;
    1327             : }
    1328             : /* return NULL if substitution fails */
    1329             : GEN
    1330         210 : gdeflate(GEN x, long v, long d)
    1331             : {
    1332         210 :   if (d <= 0) pari_err_DOMAIN("gdeflate", "degree", "<=", gen_0,stoi(d));
    1333         210 :   switch(typ(x))
    1334             :   {
    1335             :     case t_INT:
    1336             :     case t_REAL:
    1337             :     case t_INTMOD:
    1338             :     case t_FRAC:
    1339             :     case t_FFELT:
    1340             :     case t_COMPLEX:
    1341             :     case t_PADIC:
    1342          28 :     case t_QUAD: return gcopy(x);
    1343         112 :     case t_POL: return poldeflate(x,v,d);
    1344          35 :     case t_SER: return serdeflate(x,v,d);
    1345             :     case t_POLMOD:
    1346           7 :       if (varncmp(varn(gel(x,1)), v) >= 0) return gcopy(x);
    1347             :       /* fall through */
    1348             :     case t_RFRAC:
    1349             :     case t_VEC:
    1350             :     case t_COL:
    1351          14 :     case t_MAT: return vdeflate(x,v,d);
    1352          21 :     case t_LIST: return listdeflate(x,v,d);
    1353             :   }
    1354           0 :   pari_err_TYPE("gdeflate",x);
    1355           0 :   return NULL; /* not reached */
    1356             : }
    1357             : 
    1358             : /* set *m to the largest d such that x0 = A(X^d); return A */
    1359             : GEN
    1360       14171 : RgX_deflate_max(GEN x, long *m)
    1361             : {
    1362       14171 :   *m = RgX_deflate_order(x);
    1363       14171 :   return RgX_deflate(x, *m);
    1364             : }
    1365             : GEN
    1366       21149 : ZX_deflate_max(GEN x, long *m)
    1367             : {
    1368       21149 :   *m = ZX_deflate_order(x);
    1369       21149 :   return RgX_deflate(x, *m);
    1370             : }
    1371             : 
    1372             : GEN
    1373      210112 : gsubst(GEN x, long v, GEN y)
    1374             : {
    1375      210112 :   long tx = typ(x), ty = typ(y), lx = lg(x), ly = lg(y);
    1376             :   long l, vx, vy, ex, ey, i, j, k, jb;
    1377             :   pari_sp av, av2;
    1378             :   GEN X, t, p1, p2, modp1, z;
    1379             : 
    1380      210112 :   switch(ty)
    1381             :   {
    1382             :     case t_MAT:
    1383          63 :       if (ly==1) return cgetg(1,t_MAT);
    1384          56 :       if (ly == lgcols(y)) break;
    1385             :       /* fall through */
    1386             :     case t_QFR: case t_QFI: case t_VEC: case t_COL:
    1387           7 :       pari_err_TYPE2("substitution",x,y);
    1388           0 :       break; /* not reached */
    1389             :   }
    1390             : 
    1391      210098 :   if (is_scalar_t(tx))
    1392             :   {
    1393       20020 :     if (tx!=t_POLMOD || varncmp(v, varn(gel(x,1))) <= 0)
    1394             :     {
    1395       19712 :       if (ty==t_MAT) return scalarmat(x,ly-1);
    1396       19712 :       return gcopy(x);
    1397             :     }
    1398         308 :     av=avma;
    1399         308 :     p1=gsubst(gel(x,1),v,y); vx=varn(p1);
    1400         308 :     p2=gsubst(gel(x,2),v,y); vy=gvar(p2);
    1401         308 :     if (typ(p1)!=t_POL) pari_err_TYPE2("substitution",x,y);
    1402         308 :     if (varncmp(vy, vx) >= 0) return gerepileupto(av, gmodulo(p2,p1));
    1403         266 :     modp1 = mkpolmod(gen_1,p1);
    1404         266 :     lx = lg(p2);
    1405         266 :     z = cgetg(lx,t_POL); z[1] = p2[1];
    1406        3108 :     for (i=2; i<lx; i++)
    1407             :     {
    1408        2842 :       GEN c = gel(p2,i);
    1409        2842 :       if (varncmp(vx, gvar(c)) <= 0)
    1410        2835 :         c = gmodulo(c,p1);
    1411             :       else
    1412           7 :         c = gmul(c, modp1);
    1413        2842 :       gel(z,i) = c;
    1414             :     }
    1415         266 :     return gerepileupto(av, normalizepol_lg(z,lx));
    1416             :   }
    1417             : 
    1418      190078 :   switch(tx)
    1419             :   {
    1420             :     case t_POL:
    1421      177184 :       if (lx==2)
    1422         637 :         return ty == t_MAT? scalarmat(gen_0,ly-1): gen_0;
    1423             : 
    1424      176547 :       vx = varn(x);
    1425      176547 :       if (varncmp(vx, v) > 0)
    1426        1876 :         return ty == t_MAT? scalarmat(x,ly-1): RgX_copy(x);
    1427      174671 :       if (varncmp(vx, v) < 0)
    1428             :       {
    1429        5131 :         av = avma; z = cgetg(lx, t_POL); z[1] = x[1];
    1430        5131 :         for (i=2; i<lx; i++) gel(z,i) = gsubst(gel(x,i),v,y);
    1431        5131 :         return gerepileupto(av, poleval(z, pol_x(vx)));
    1432             :       }
    1433      169540 :       return ty == t_MAT? RgX_RgM_eval(x, y): poleval(x,y);
    1434             : 
    1435             :     case t_SER:
    1436        9338 :       vx = varn(x);
    1437        9338 :       if (varncmp(vx, v) > 0)
    1438           0 :         return (ty==t_MAT)? scalarmat(x,ly-1): gcopy(x);
    1439        9338 :       ex = valp(x);
    1440        9338 :       if (varncmp(vx, v) < 0)
    1441             :       {
    1442          21 :         if (lx == 2) return (ty==t_MAT)? scalarmat(x,ly-1): gcopy(x);
    1443          21 :         av = avma; X = pol_x(vx);
    1444          21 :         av2 = avma;
    1445          21 :         z = gadd(gsubst(gel(x,lx-1),v,y), zeroser(vx,1));
    1446         133 :         for (i = lx-2; i>=2; i--)
    1447             :         {
    1448         112 :           z = gadd(gmul(z,X), gsubst(gel(x,i),v,y));
    1449         112 :           if (gc_needed(av2,1))
    1450             :           {
    1451           0 :             if(DEBUGMEM>1) pari_warn(warnmem,"gsubst (i = %ld)", i);
    1452           0 :             z = gerepileupto(av2, z);
    1453             :           }
    1454             :         }
    1455          21 :         if (ex) z = gmul(z, monomial(gen_1,ex,vx));
    1456          21 :         return gerepileupto(av, z);
    1457             :       }
    1458        9317 :       switch(ty) /* here vx == v */
    1459             :       {
    1460             :         case t_SER:
    1461        7826 :           vy = varn(y); ey = valp(y);
    1462        7826 :           if (ey < 1 || lx == 2) return zeroser(vy, ey*(ex+lx-2));
    1463        7826 :           if (vy != vx)
    1464             :           {
    1465          14 :             av = avma; z = gel(x,lx-1);
    1466             : 
    1467          42 :             for (i=lx-2; i>=2; i--)
    1468             :             {
    1469          28 :               z = gadd(gmul(y,z), gel(x,i));
    1470          28 :               if (gc_needed(av,1))
    1471             :               {
    1472           0 :                 if(DEBUGMEM>1) pari_warn(warnmem,"gsubst (i = %ld)", i);
    1473           0 :                 z = gerepileupto(av, z);
    1474             :               }
    1475             :             }
    1476          14 :             if (ex) z = gmul(z, gpowgs(y,ex));
    1477          14 :             return gerepileupto(av,z);
    1478             :           }
    1479        7812 :           l = (lx-2)*ey+2;
    1480        7812 :           if (ex) { if (l>ly) l = ly; }
    1481        7567 :           else if (lx != 3)
    1482             :           {
    1483             :             long l2;
    1484        7567 :             for (i = 3; i < lx; i++)
    1485        7567 :               if (!isexactzero(gel(x,i))) break;
    1486        7567 :             l2 = (i-2)*ey + (gequal0(y)? 2 : ly);
    1487        7567 :             if (l > l2) l = l2;
    1488             :           }
    1489        7812 :           av = avma;
    1490        7812 :           t = leafcopy(y);
    1491        7812 :           if (l < ly) setlg(t, l);
    1492        7812 :           z = scalarser(gel(x,2),varn(y),l-2);
    1493       34594 :           for (i=3,jb=ey; jb<=l-2; i++,jb+=ey)
    1494             :           {
    1495       26782 :             if (i < lx) {
    1496       85078 :               for (j=jb+2; j<minss(l, jb+ly); j++)
    1497       58478 :                 gel(z,j) = gadd(gel(z,j), gmul(gel(x,i),gel(t,j-jb)));
    1498             :             }
    1499       65954 :             for (j=l-1-jb-ey; j>1; j--)
    1500             :             {
    1501       39172 :               p1 = gen_0;
    1502      209874 :               for (k=2; k<j; k++)
    1503      170702 :                 p1 = gadd(p1, gmul(gel(t,j-k+2),gel(y,k)));
    1504       39172 :               gel(t,j) = gadd(p1, gmul(gel(t,2),gel(y,j)));
    1505             :             }
    1506       26782 :             if (gc_needed(av,1))
    1507             :             {
    1508           0 :               if(DEBUGMEM>1) pari_warn(warnmem,"gsubst");
    1509           0 :               gerepileall(av,2, &z,&t);
    1510             :             }
    1511             :           }
    1512        7812 :           if (!ex) return gerepilecopy(av,z);
    1513         245 :           return gerepileupto(av, gmul(z,gpowgs(y, ex)));
    1514             : 
    1515             :         case t_POL: case t_RFRAC:
    1516             :         {
    1517        1463 :           long N, n = lx-2;
    1518             :           GEN cx;
    1519        1463 :           vy = gvar(y); ey = gval(y,vy);
    1520        1463 :           if (ey == LONG_MAX) return n? scalarser(gel(x,2),v,n): gcopy(x);
    1521        1456 :           if (ey < 1 || n == 0) return zeroser(vy, ey*(ex+n));
    1522        1449 :           av = avma;
    1523        1449 :           n *= ey;
    1524        1449 :           N = ex? n: maxss(n-ey,1);
    1525        1449 :           y = (ty == t_RFRAC)? rfractoser(y, vy, N): poltoser(y, vy, N);
    1526        1449 :           if (lg(y)-2 > n) setlg(y, n+2);
    1527        1449 :           x = ser2pol_i(x, lx);
    1528        1449 :           x = primitive_part(x, &cx);
    1529        1449 :           if (varncmp(vy,vx) > 0)
    1530          28 :             z = poleval(x, y);
    1531             :           else
    1532             :           {
    1533        1421 :             z = RgXn_eval(x, ser2rfrac_i(y), n);
    1534        1421 :             if (varn(z) == vy) z = RgX_to_ser(z, n+2);
    1535             :           }
    1536        1449 :           switch(typ(z))
    1537             :           {
    1538             :             case t_SER:
    1539             :             case t_POL:
    1540        1442 :               if (varncmp(varn(z),vy) <= 0) break;
    1541           7 :             default: z = scalarser(z, vy, n);
    1542             :           }
    1543        1449 :           if (cx) z = gmul(z, cx);
    1544        1449 :           if (!ex && !cx) return gerepilecopy(av, z);
    1545        1421 :           if (ex) z = gmul(z, gpowgs(y,ex));
    1546        1421 :           return gerepileupto(av, z);
    1547             :         }
    1548             : 
    1549             :         default:
    1550          28 :           if (isexactzero(y))
    1551             :           {
    1552          21 :             if (ex < 0) pari_err_INV("gsubst",y);
    1553          14 :             if (ex > 0) return gcopy(y);
    1554           7 :             if (lx > 2) return gadd(gel(x,2), y); /*add maps to correct ring*/
    1555             :           }
    1556           7 :           pari_err_TYPE2("substitution",x,y);
    1557             :       }
    1558           0 :       break;
    1559             : 
    1560         154 :     case t_RFRAC: av=avma;
    1561         154 :       p1=gsubst(gel(x,1),v,y);
    1562         154 :       p2=gsubst(gel(x,2),v,y); return gerepileupto(av, gdiv(p1,p2));
    1563             : 
    1564             :     case t_VEC: case t_COL: case t_MAT:
    1565        3283 :       z = cgetg_copy(x, &lx);
    1566        3283 :       for (i=1; i<lx; i++) gel(z,i) = gsubst(gel(x,i),v,y);
    1567        3283 :       return z;
    1568             :     case t_LIST:
    1569          56 :       z = listcreate();
    1570          56 :       list_data(z) = list_data(x)? gsubst(list_data(x),v,y): NULL;
    1571          56 :       return z;
    1572             :   }
    1573          63 :   return gcopy(x);
    1574             : }
    1575             : 
    1576             : /* Return P(x * h), not memory clean */
    1577             : GEN
    1578         602 : ser_unscale(GEN P, GEN h)
    1579             : {
    1580         602 :   long l = lg(P);
    1581         602 :   GEN Q = cgetg(l,t_SER);
    1582         602 :   Q[1] = P[1];
    1583         602 :   if (l != 2)
    1584             :   {
    1585         602 :     long i = 2;
    1586         602 :     GEN hi = gpowgs(h, valp(P));
    1587         602 :     gel(Q,i) = gmul(gel(P,i), hi);
    1588         602 :     for (i++; i<l; i++) { hi = gmul(hi,h); gel(Q,i) = gmul(gel(P,i), hi); }
    1589             :   }
    1590         602 :   return Q;
    1591             : }
    1592             : 
    1593             : GEN
    1594         756 : gsubstvec(GEN e, GEN v, GEN r)
    1595             : {
    1596         756 :   pari_sp ltop=avma;
    1597         756 :   long i, j, l = lg(v);
    1598             :   GEN w, z, R;
    1599         756 :   if ( !is_vec_t(typ(v)) ) pari_err_TYPE("substvec",v);
    1600         756 :   if ( !is_vec_t(typ(r)) ) pari_err_TYPE("substvec",r);
    1601         756 :   if (lg(r)!=l) pari_err_DIM("substvec");
    1602         756 :   w = cgetg(l,t_VECSMALL);
    1603         756 :   z = cgetg(l,t_VECSMALL);
    1604         756 :   R = cgetg(l,t_VEC);
    1605        3619 :   for(i=j=1;i<l;i++)
    1606             :   {
    1607        2863 :     GEN T = gel(v,i), ri = gel(r,i);
    1608        2863 :     if (!gequalX(T)) pari_err_TYPE("substvec [not a variable]", T);
    1609        2863 :     if (gvar(ri) == NO_VARIABLE) /* no need to take precautions */
    1610        1764 :       e = gsubst(e, varn(T), ri);
    1611             :     else
    1612             :     {
    1613        1099 :       w[j] = varn(T);
    1614        1099 :       z[j] = fetch_var();
    1615        1099 :       gel(R,j) = ri;
    1616        1099 :       j++;
    1617             :     }
    1618             :   }
    1619         756 :   for(i=1;i<j;i++) e = gsubst(e,w[i],pol_x(z[i]));
    1620         756 :   for(i=1;i<j;i++) e = gsubst(e,z[i],gel(R,i));
    1621         756 :   for(i=1;i<j;i++) (void)delete_var();
    1622         756 :   return gerepileupto(ltop,e);
    1623             : }
    1624             : 
    1625             : /*******************************************************************/
    1626             : /*                                                                 */
    1627             : /*                SERIE RECIPROQUE D'UNE SERIE                     */
    1628             : /*                                                                 */
    1629             : /*******************************************************************/
    1630             : 
    1631             : GEN
    1632          49 : serreverse(GEN x)
    1633             : {
    1634          49 :   long v=varn(x), lx = lg(x), i, mi;
    1635          49 :   pari_sp av0 = avma, av;
    1636             :   GEN a, y, u;
    1637             : 
    1638          49 :   if (typ(x)!=t_SER) pari_err_TYPE("serreverse",x);
    1639          49 :   if (valp(x)!=1) pari_err_DOMAIN("serreverse", "valuation", "!=", gen_1,x);
    1640          42 :   if (lx < 3) pari_err_DOMAIN("serreverse", "x", "=", gen_0,x);
    1641          42 :   y = ser_normalize(x);
    1642          42 :   if (y == x) a = NULL; else { a = gel(x,2); x = y; }
    1643          42 :   av = avma;
    1644          42 :   mi = lx-1; while (mi>=3 && gequal0(gel(x,mi))) mi--;
    1645          42 :   u = cgetg(lx,t_SER);
    1646          42 :   y = cgetg(lx,t_SER);
    1647          42 :   u[1] = y[1] = evalsigne(1) | _evalvalp(1) | evalvarn(v);
    1648          42 :   gel(u,2) = gel(y,2) = gen_1;
    1649          42 :   if (lx > 3)
    1650             :   {
    1651          35 :     gel(u,3) = gmulsg(-2,gel(x,3));
    1652          35 :     gel(y,3) = gneg(gel(x,3));
    1653             :   }
    1654         420 :   for (i=3; i<lx-1; )
    1655             :   {
    1656             :     pari_sp av2;
    1657             :     GEN p1;
    1658         336 :     long j, k, K = minss(i,mi);
    1659        2625 :     for (j=3; j<i+1; j++)
    1660             :     {
    1661        2289 :       av2 = avma; p1 = gel(x,j);
    1662       11900 :       for (k = maxss(3,j+2-mi); k < j; k++)
    1663        9611 :         p1 = gadd(p1, gmul(gel(u,k),gel(x,j-k+2)));
    1664        2289 :       p1 = gneg(p1);
    1665        2289 :       gel(u,j) = gerepileupto(av2, gadd(gel(u,j), p1));
    1666             :     }
    1667         336 :     av2 = avma;
    1668         336 :     p1 = gmulsg(i,gel(x,i+1));
    1669        2625 :     for (k = 2; k < K; k++)
    1670             :     {
    1671        2289 :       GEN p2 = gmul(gel(x,k+1),gel(u,i-k+2));
    1672        2289 :       p1 = gadd(p1, gmulsg(k,p2));
    1673             :     }
    1674         336 :     i++;
    1675         336 :     gel(u,i) = gerepileupto(av2, gneg(p1));
    1676         336 :     gel(y,i) = gdivgs(gel(u,i), i-1);
    1677         336 :     if (gc_needed(av,2))
    1678             :     {
    1679           0 :       GEN dummy = cgetg(1,t_VEC);
    1680           0 :       if(DEBUGMEM>1) pari_warn(warnmem,"serreverse");
    1681           0 :       for(k=i+1; k<lx; k++) gel(u,k) = gel(y,k) = dummy;
    1682           0 :       gerepileall(av,2, &u,&y);
    1683             :     }
    1684             :   }
    1685          42 :   if (a) y = ser_unscale(y, ginv(a));
    1686          42 :   return gerepilecopy(av0,y);
    1687             : }
    1688             : 
    1689             : /*******************************************************************/
    1690             : /*                                                                 */
    1691             : /*                    DERIVATION ET INTEGRATION                    */
    1692             : /*                                                                 */
    1693             : /*******************************************************************/
    1694             : GEN
    1695        9891 : derivser(GEN x)
    1696             : {
    1697        9891 :   long i, vx = varn(x), e = valp(x), lx = lg(x);
    1698             :   GEN y;
    1699        9891 :   if (ser_isexactzero(x))
    1700             :   {
    1701          14 :     x = gcopy(x);
    1702          14 :     if (e) setvalp(x,e-1);
    1703          14 :     return x;
    1704             :   }
    1705        9877 :   if (e)
    1706             :   {
    1707         455 :     y = cgetg(lx,t_SER); y[1] = evalsigne(1)|evalvalp(e-1) | evalvarn(vx);
    1708         455 :     for (i=2; i<lx; i++) gel(y,i) = gmulsg(i+e-2,gel(x,i));
    1709             :   } else {
    1710        9422 :     if (lx == 3) return zeroser(vx, 0);
    1711        7728 :     lx--;
    1712        7728 :     y = cgetg(lx,t_SER); y[1] = evalsigne(1)|_evalvalp(0) | evalvarn(vx);
    1713        7728 :     for (i=2; i<lx; i++) gel(y,i) = gmulsg(i-1,gel(x,i+1));
    1714             :   }
    1715        8183 :   return normalize(y);
    1716             : }
    1717             : 
    1718             : GEN
    1719      104195 : deriv(GEN x, long v)
    1720             : {
    1721             :   long lx, tx, i, j;
    1722             :   pari_sp av;
    1723             :   GEN y;
    1724             : 
    1725      104195 :   tx = typ(x);
    1726      104195 :   if (is_const_t(tx))
    1727       34958 :     switch(tx)
    1728             :     {
    1729          21 :       case t_INTMOD: retmkintmod(gen_0, icopy(gel(x,1)));
    1730          21 :       case t_FFELT: return FF_zero(x);
    1731       34916 :       default: return gen_0;
    1732             :     }
    1733       69237 :   if (v < 0 && tx!=t_CLOSURE) v = gvar9(x);
    1734       69237 :   switch(tx)
    1735             :   {
    1736             :     case t_POLMOD:
    1737             :     {
    1738          21 :       GEN a = gel(x,2), b = gel(x,1);
    1739          21 :       if (v == varn(b)) return RgX_get_0(b);
    1740          14 :       retmkpolmod(deriv(a,v), RgX_copy(b));
    1741             :     }
    1742             :     case t_POL:
    1743       68992 :       switch(varncmp(varn(x), v))
    1744             :       {
    1745           0 :         case 1: return RgX_get_0(x);
    1746       62139 :         case 0: return RgX_deriv(x);
    1747             :       }
    1748        6853 :       y = cgetg_copy(x, &lx); y[1] = x[1];
    1749        6853 :       for (i=2; i<lx; i++) gel(y,i) = deriv(gel(x,i),v);
    1750        6853 :       return normalizepol_lg(y,i);
    1751             : 
    1752             :     case t_SER:
    1753          70 :       switch(varncmp(varn(x), v))
    1754             :       {
    1755           0 :         case 1: return RgX_get_0(x);
    1756          56 :         case 0: return derivser(x);
    1757             :       }
    1758          14 :       if (ser_isexactzero(x)) return gcopy(x);
    1759           7 :       y = cgetg_copy(x, &lx); y[1] = x[1];
    1760           7 :       for (j=2; j<lx; j++) gel(y,j) = deriv(gel(x,j),v);
    1761           7 :       return normalize(y);
    1762             : 
    1763             :     case t_RFRAC: {
    1764          42 :       GEN a = gel(x,1), b = gel(x,2), bp, b0, d, t;
    1765          42 :       y = cgetg(3,t_RFRAC); av = avma;
    1766             : 
    1767          42 :       bp = deriv(b, v);
    1768          42 :       d = RgX_gcd(bp, b);
    1769          42 :       if (gequal1(d)) {
    1770          21 :         d = gsub(gmul(b, deriv(a,v)), gmul(a, bp));
    1771          21 :         if (isexactzero(d)) return gerepileupto((pari_sp)(y+3), d);
    1772          21 :         gel(y,1) = gerepileupto(av, d);
    1773          21 :         gel(y,2) = gsqr(b); return y;
    1774             :       }
    1775          21 :       b0 = gdivexact(b, d);
    1776          21 :       bp = gdivexact(bp,d);
    1777          21 :       a = gsub(gmul(b0, deriv(a,v)), gmul(a, bp));
    1778          21 :       if (isexactzero(a)) return gerepileupto((pari_sp)(y+3), a);
    1779          14 :       t = ggcd(a, d);
    1780          14 :       if (!gequal1(t)) { a = gdivexact(a, t); d = gdivexact(d, t); }
    1781          14 :       gel(y,1) = a;
    1782          14 :       gel(y,2) = gmul(d, gsqr(b0));
    1783          14 :       return gerepilecopy((pari_sp)(y+3), y);
    1784             :     }
    1785             : 
    1786             :     case t_VEC: case t_COL: case t_MAT:
    1787          63 :       y = cgetg_copy(x, &lx);
    1788          63 :       for (i=1; i<lx; i++) gel(y,i) = deriv(gel(x,i),v);
    1789          63 :       return y;
    1790             : 
    1791             :     case t_CLOSURE:
    1792          49 :       if (v==-1) return closure_deriv(x);
    1793             :   }
    1794           0 :   pari_err_TYPE("deriv",x);
    1795           0 :   return NULL; /* not reached */
    1796             : }
    1797             : 
    1798             : static long
    1799         833 : lookup(GEN v, long vx)
    1800             : {
    1801         833 :   long i ,l = lg(v);
    1802        1491 :   for(i=1; i<l; i++)
    1803        1253 :     if (varn(gel(v,i)) == vx) return i;
    1804         238 :   return 0;
    1805             : }
    1806             : 
    1807             : GEN
    1808        3535 : diffop(GEN x, GEN v, GEN dv)
    1809             : {
    1810             :   pari_sp av;
    1811        3535 :   long i, idx, lx, tx = typ(x), vx;
    1812             :   GEN y;
    1813        3535 :   if (!is_vec_t(typ(v))) pari_err_TYPE("diffop",v);
    1814        3535 :   if (!is_vec_t(typ(dv))) pari_err_TYPE("diffop",dv);
    1815        3535 :   if (lg(v)!=lg(dv)) pari_err_DIM("diffop");
    1816        3535 :   if (is_const_t(tx)) return gen_0;
    1817        1127 :   switch(tx)
    1818             :   {
    1819             :     case t_POLMOD:
    1820          84 :       av = avma;
    1821          84 :       vx  = varn(gel(x,1)); idx = lookup(v,vx);
    1822          84 :       if (idx) /*Assume the users now what they are doing */
    1823           0 :         y = gmodulo(diffop(gel(x,2),v,dv), gel(x,1));
    1824             :       else
    1825             :       {
    1826          84 :         GEN m = gel(x,1), pol=gel(x,2);
    1827          84 :         GEN u = gneg(gdiv(diffop(m,v,dv),RgX_deriv(m)));
    1828          84 :         y = diffop(pol,v,dv);
    1829          84 :         if (typ(pol)==t_POL && varn(pol)==varn(m))
    1830          70 :           y = gadd(y, gmul(u,RgX_deriv(pol)));
    1831          84 :         y = gmodulo(y, gel(x,1));
    1832             :       }
    1833          84 :       return gerepileupto(av, y);
    1834             :     case t_POL:
    1835         931 :       if (signe(x)==0) return gen_0;
    1836         742 :       vx  = varn(x); idx = lookup(v,vx);
    1837         742 :       av = avma; lx = lg(x);
    1838         742 :       y = diffop(gel(x,lx-1),v,dv);
    1839         742 :       for (i=lx-2; i>=2; i--) y = gadd(gmul(y,pol_x(vx)),diffop(gel(x,i),v,dv));
    1840         742 :       if (idx) y = gadd(y, gmul(gel(dv,idx),RgX_deriv(x)));
    1841         742 :       return gerepileupto(av, y);
    1842             : 
    1843             :     case t_SER:
    1844           7 :       if (signe(x)==0) return gen_0;
    1845           7 :       vx  = varn(x); idx = lookup(v,vx);
    1846           7 :       if (!idx) return gen_0;
    1847           7 :       av = avma;
    1848           7 :       if (ser_isexactzero(x)) y = x;
    1849             :       else
    1850             :       {
    1851           7 :         y = cgetg_copy(x, &lx); y[1] = x[1];
    1852           7 :         for (i=2; i<lx; i++) gel(y,i) = diffop(gel(x,i),v,dv);
    1853           7 :         y = normalize(y); /* y is probably invalid */
    1854           7 :         y = gsubst(y, vx, pol_x(vx)); /* Fix that */
    1855             :       }
    1856           7 :       y = gadd(y, gmul(gel(dv,idx),derivser(x)));
    1857           7 :       return gerepileupto(av, y);
    1858             : 
    1859             :     case t_RFRAC: {
    1860         105 :       GEN a = gel(x,1), b = gel(x,2), ap, bp;
    1861         105 :       av = avma;
    1862         105 :       ap = diffop(a, v, dv); bp = diffop(b, v, dv);
    1863         105 :       y = gsub(gdiv(ap,b),gdiv(gmul(a,bp),gsqr(b)));
    1864         105 :       return gerepileupto(av, y);
    1865             :     }
    1866             : 
    1867             :     case t_VEC: case t_COL: case t_MAT:
    1868           0 :       y = cgetg_copy(x, &lx);
    1869           0 :       for (i=1; i<lx; i++) gel(y,i) = diffop(gel(x,i),v,dv);
    1870           0 :       return y;
    1871             : 
    1872             :   }
    1873           0 :   pari_err_TYPE("diffop",x);
    1874           0 :   return NULL; /* not reached */
    1875             : }
    1876             : 
    1877             : GEN
    1878          42 : diffop0(GEN x, GEN v, GEN dv, long n)
    1879             : {
    1880          42 :   pari_sp av=avma;
    1881             :   long i;
    1882         245 :   for(i=1; i<=n; i++)
    1883         203 :     x = gerepileupto(av, diffop(x,v,dv));
    1884          42 :   return x;
    1885             : }
    1886             : 
    1887             : /********************************************************************/
    1888             : /**                                                                **/
    1889             : /**                         TAYLOR SERIES                          **/
    1890             : /**                                                                **/
    1891             : /********************************************************************/
    1892             : /* swap vars (vx,v) in x (assume vx < v, vx main variable in x), then call
    1893             :  * act(data, v, x). FIXME: use in other places */
    1894             : static GEN
    1895          21 : swapvar_act(GEN x, long vx, long v, GEN (*act)(void*, long, GEN), void *data)
    1896             : {
    1897          21 :   long v0 = fetch_var();
    1898          21 :   GEN y = act(data, v, gsubst(x,vx,pol_x(v0)));
    1899          14 :   y = gsubst(y,v0,pol_x(vx));
    1900          14 :   (void)delete_var(); return y;
    1901             : }
    1902             : /* x + O(v^data) */
    1903             : static GEN
    1904           7 : tayl_act(void *data, long v, GEN x) { return gadd(zeroser(v, (long)data), x); }
    1905             : static  GEN
    1906          14 : integ_act(void *data, long v, GEN x) { (void)data; return integ(x,v); }
    1907             : 
    1908             : GEN
    1909           7 : tayl(GEN x, long v, long precS)
    1910             : {
    1911           7 :   long vx = gvar9(x);
    1912             :   pari_sp av;
    1913             : 
    1914           7 :   if (varncmp(v, vx) <= 0) return gadd(zeroser(v,precS), x);
    1915           7 :   av = avma;
    1916           7 :   return gerepileupto(av, swapvar_act(x, vx, v, tayl_act, (void*)precS));
    1917             : }
    1918             : 
    1919             : GEN
    1920        4641 : ggrando(GEN x, long n)
    1921             : {
    1922             :   long m, v;
    1923             : 
    1924        4641 :   switch(typ(x))
    1925             :   {
    1926             :   case t_INT:/* bug 3 + O(1) */
    1927        3073 :     if (signe(x) <= 0) pari_err_DOMAIN("O", "x", "<=", gen_0, x);
    1928        3073 :     if (!is_pm1(x)) return zeropadic(x,n);
    1929             :     /* +/-1 = x^0 */
    1930         126 :     v = m = 0; break;
    1931             :   case t_POL:
    1932        1561 :     if (!signe(x)) pari_err_DOMAIN("O", "x", "=", gen_0, x);
    1933        1561 :     v = varn(x);
    1934        1561 :     m = n * RgX_val(x); break;
    1935             :   case t_RFRAC:
    1936           7 :     if (gequal0(gel(x,1))) pari_err_DOMAIN("O", "x", "=", gen_0, x);
    1937           7 :     v = gvar(x);
    1938           7 :     m = n * gval(x,v); break;
    1939           0 :     default:  pari_err_TYPE("O", x);
    1940           0 :       v = m = 0; /* not reached */
    1941             :   }
    1942        1694 :   return zeroser(v,m);
    1943             : }
    1944             : 
    1945             : /*******************************************************************/
    1946             : /*                                                                 */
    1947             : /*                    FORMAL INTEGRATION                           */
    1948             : /*                                                                 */
    1949             : /*******************************************************************/
    1950             : 
    1951             : static GEN
    1952          35 : triv_integ(GEN x, long v)
    1953             : {
    1954             :   long i, lx;
    1955          35 :   GEN y = cgetg_copy(x, &lx); y[1] = x[1];
    1956          35 :   for (i=2; i<lx; i++) gel(y,i) = integ(gel(x,i),v);
    1957          35 :   return y;
    1958             : }
    1959             : 
    1960             : GEN
    1961          98 : RgX_integ(GEN x)
    1962             : {
    1963          98 :   long i, lx = lg(x);
    1964             :   GEN y;
    1965          98 :   if (lx == 2) return RgX_copy(x);
    1966          84 :   y = cgetg(lx+1, t_POL); y[1] = x[1]; gel(y,2) = gen_0;
    1967          84 :   for (i=3; i<=lx; i++) gel(y,i) = gdivgs(gel(x,i-1),i-2);
    1968          84 :   return y;
    1969             : }
    1970             : 
    1971             : static void
    1972          35 : err_intformal(GEN x)
    1973          35 : { pari_err_DOMAIN("intformal", "residue(series, pole)", "!=", gen_0, x); }
    1974             : 
    1975             : GEN
    1976       10409 : integser(GEN x)
    1977             : {
    1978       10409 :   long i, lx = lg(x), vx = varn(x), e = valp(x);
    1979             :   GEN y;
    1980       10409 :   if (lx == 2) return zeroser(vx, e+1);
    1981        8561 :   y = cgetg(lx, t_SER);
    1982       45479 :   for (i=2; i<lx; i++)
    1983             :   {
    1984       36925 :     long j = i+e-1;
    1985       36925 :     GEN c = gel(x,i);
    1986       36925 :     if (j)
    1987       36603 :       c = gdivgs(c, j);
    1988             :     else
    1989             :     { /* should be isexactzero, but try to avoid error */
    1990         322 :       if (!gequal0(c)) err_intformal(x);
    1991         315 :       c = gen_0;
    1992             :     }
    1993       36918 :     gel(y,i) = c;
    1994             :   }
    1995        8554 :   y[1] = evalsigne(1) | evalvarn(vx) | evalvalp(e+1); return y;
    1996             : }
    1997             : 
    1998             : GEN
    1999         350 : integ(GEN x, long v)
    2000             : {
    2001             :   long lx, tx, i, vx, n;
    2002         350 :   pari_sp av = avma;
    2003             :   GEN y,p1;
    2004             : 
    2005         350 :   tx = typ(x);
    2006         350 :   if (v < 0) { v = gvar9(x); if (v == NO_VARIABLE) v = 0; }
    2007         350 :   if (is_scalar_t(tx))
    2008             :   {
    2009          63 :     if (tx == t_POLMOD)
    2010             :     {
    2011          14 :       GEN a = gel(x,2), b = gel(x,1);
    2012          14 :       vx = varn(b);
    2013          14 :       if (varncmp(v, vx) > 0) retmkpolmod(integ(a,v), RgX_copy(b));
    2014           7 :       if (v == vx) pari_err_PRIORITY("intformal",x,"=",v);
    2015             :     }
    2016          49 :     return deg1pol(x, gen_0, v);
    2017             :   }
    2018             : 
    2019         287 :   switch(tx)
    2020             :   {
    2021             :     case t_POL:
    2022         112 :       vx = varn(x);
    2023         112 :       if (v == vx) return RgX_integ(x);
    2024          42 :       if (lg(x) == 2) {
    2025          14 :         if (varncmp(vx, v) < 0) v = vx;
    2026          14 :         return zeropol(v);
    2027             :       }
    2028          28 :       if (varncmp(vx, v) > 0) return deg1pol(x, gen_0, v);
    2029          28 :       return triv_integ(x,v);
    2030             : 
    2031             :     case t_SER:
    2032          77 :       vx = varn(x);
    2033          77 :       if (v == vx) return integser(x);
    2034          21 :       if (lg(x) == 2) {
    2035          14 :         if (varncmp(vx, v) < 0) v = vx;
    2036          14 :         return zeroser(v, valp(x));
    2037             :       }
    2038           7 :       if (varncmp(vx, v) > 0) return deg1pol(x, gen_0, v);
    2039           7 :       return triv_integ(x,v);
    2040             : 
    2041             :     case t_RFRAC:
    2042             :     {
    2043          56 :       GEN a = gel(x,1), b = gel(x,2), c, d, s;
    2044          56 :       vx = varn(b);
    2045          56 :       if (varncmp(vx, v) > 0) return deg1pol(x, gen_0, v);
    2046          49 :       if (varncmp(vx, v) < 0)
    2047          14 :         return gerepileupto(av, swapvar_act(x, vx, v, integ_act, NULL));
    2048             : 
    2049          35 :       n = degpol(b);
    2050          35 :       if (typ(a) == t_POL && varn(a) == vx) n += degpol(a);
    2051          35 :       y = integ(gadd(x, zeroser(v,n + 2)), v);
    2052          35 :       y = gdiv(gtrunc(gmul(b, y)), b);
    2053          35 :       if (typ(y) != t_RFRAC) pari_err_BUG("intformal(t_RFRAC)");
    2054          35 :       c = gel(y,1); d = gel(y,2);
    2055          35 :       s = gsub(gmul(deriv(c,v),d), gmul(c,deriv(d,v)));
    2056             :       /* (c'd-cd')/d^2 = y' = x = a/b ? */
    2057          35 :       if (!gequal(gmul(s,b), gmul(a,gsqr(d)))) err_intformal(x);
    2058           7 :       if (typ(y)==t_RFRAC && lg(gel(y,1)) == lg(gel(y,2)))
    2059             :       {
    2060           7 :         GEN p2 = leading_coeff(gel(y,2));
    2061           7 :         p1 = gel(y,1);
    2062           7 :         if (typ(p1) == t_POL && varn(p1) == vx) p1 = leading_coeff(p1);
    2063           7 :         y = gsub(y, gdiv(p1,p2));
    2064             :       }
    2065           7 :       return gerepileupto(av,y);
    2066             :     }
    2067             : 
    2068             :     case t_VEC: case t_COL: case t_MAT:
    2069          42 :       y = cgetg_copy(x, &lx);
    2070          42 :       for (i=1; i<lg(x); i++) gel(y,i) = integ(gel(x,i),v);
    2071          42 :       return y;
    2072             :   }
    2073           0 :   pari_err_TYPE("integ",x);
    2074           0 :   return NULL; /* not reached */
    2075             : }
    2076             : 
    2077             : /*******************************************************************/
    2078             : /*                                                                 */
    2079             : /*                    PARTIES ENTIERES                             */
    2080             : /*                                                                 */
    2081             : /*******************************************************************/
    2082             : 
    2083             : GEN
    2084     4192831 : gfloor(GEN x)
    2085             : {
    2086             :   GEN y;
    2087             :   long i, lx;
    2088             : 
    2089     4192831 :   switch(typ(x))
    2090             :   {
    2091     4190295 :     case t_INT: return icopy(x);
    2092          21 :     case t_POL: return RgX_copy(x);
    2093        1318 :     case t_REAL: return floorr(x);
    2094         805 :     case t_FRAC: return truedivii(gel(x,1),gel(x,2));
    2095          21 :     case t_RFRAC: return gdeuc(gel(x,1),gel(x,2));
    2096             :     case t_VEC: case t_COL: case t_MAT:
    2097         126 :       y = cgetg_copy(x, &lx);
    2098         126 :       for (i=1; i<lx; i++) gel(y,i) = gfloor(gel(x,i));
    2099         126 :       return y;
    2100             :   }
    2101         245 :   pari_err_TYPE("gfloor",x);
    2102           0 :   return NULL; /* not reached */
    2103             : }
    2104             : 
    2105             : GEN
    2106          91 : gfrac(GEN x)
    2107             : {
    2108          91 :   pari_sp av = avma;
    2109          91 :   return gerepileupto(av, gsub(x,gfloor(x)));
    2110             : }
    2111             : 
    2112             : /* assume x t_REAL */
    2113             : GEN
    2114       26658 : ceilr(GEN x) {
    2115       26658 :   pari_sp av = avma;
    2116       26658 :   GEN y = floorr(x);
    2117       26658 :   if (cmpri(x, y)) return gerepileuptoint(av, addui(1,y));
    2118           7 :   return y;
    2119             : }
    2120             : 
    2121             : GEN
    2122       39099 : gceil(GEN x)
    2123             : {
    2124             :   GEN y;
    2125             :   long i, lx;
    2126             :   pari_sp av;
    2127             : 
    2128       39099 :   switch(typ(x))
    2129             :   {
    2130        9627 :     case t_INT: return icopy(x);
    2131           7 :     case t_POL: return RgX_copy(x);
    2132       26581 :     case t_REAL: return ceilr(x);
    2133             :     case t_FRAC:
    2134        2807 :       av = avma; y = divii(gel(x,1),gel(x,2));
    2135        2807 :       if (signe(gel(x,1)) > 0) y = gerepileuptoint(av, addui(1,y));
    2136        2807 :       return y;
    2137             : 
    2138             :     case t_RFRAC:
    2139           7 :       return gdeuc(gel(x,1),gel(x,2));
    2140             : 
    2141             :     case t_VEC: case t_COL: case t_MAT:
    2142          28 :       y = cgetg_copy(x, &lx);
    2143          28 :       for (i=1; i<lx; i++) gel(y,i) = gceil(gel(x,i));
    2144          28 :       return y;
    2145             :   }
    2146          42 :   pari_err_TYPE("gceil",x);
    2147           0 :   return NULL; /* not reached */
    2148             : }
    2149             : 
    2150             : GEN
    2151        3626 : round0(GEN x, GEN *pte)
    2152             : {
    2153        3626 :   if (pte) { long e; x = grndtoi(x,&e); *pte = stoi(e); }
    2154        3619 :   return ground(x);
    2155             : }
    2156             : 
    2157             : /* x t_REAL, return q=floor(x+1/2), set e = expo(x-q) */
    2158             : static GEN
    2159    16899322 : round_i(GEN x, long *pe)
    2160             : {
    2161             :   long e;
    2162    16899322 :   GEN B, q,r, m = mantissa_real(x, &e); /* x = m/2^e */
    2163    16899322 :   if (e <= 0)
    2164             :   {
    2165     1944174 :     if (e) m = shifti(m,-e);
    2166     1944174 :     *pe = -e; return m;
    2167             :   }
    2168    14955148 :   B = int2n(e-1);
    2169    14955148 :   m = addii(m, B);
    2170    14955148 :   q = shifti(m, -e);
    2171    14955148 :   r = remi2n(m, e);
    2172             :   /* 2^e (x+1/2) = m = 2^e q + r, sgn(r)=sgn(m), |r|<2^e */
    2173    14955148 :   if (!signe(r))
    2174       40511 :     *pe = -1;
    2175             :   else
    2176             :   {
    2177    14914637 :     if (signe(m) < 0)
    2178             :     {
    2179     6071954 :       q = subiu(q,1);
    2180     6071954 :       r = addii(r, B);
    2181             :     }
    2182             :     else
    2183     8842683 :       r = subii(r, B);
    2184             :     /* |x - q| = |r| / 2^e */
    2185    14914637 :     *pe = signe(r)? expi(r) - e: -e;
    2186    14914637 :     cgiv(r);
    2187             :   }
    2188    14955148 :   return q;
    2189             : }
    2190             : /* assume x a t_REAL */
    2191             : GEN
    2192     2666735 : roundr(GEN x)
    2193             : {
    2194     2666735 :   long ex, s = signe(x);
    2195             :   pari_sp av;
    2196     2666735 :   if (!s || (ex=expo(x)) < -1) return gen_0;
    2197     2446534 :   if (ex == -1) return s>0? gen_1:
    2198       77294 :                             absrnz_equal2n(x)? gen_0: gen_m1;
    2199     2219787 :   av = avma; x = round_i(x, &ex);
    2200     2219787 :   if (ex >= 0) pari_err_PREC( "roundr (precision loss in truncation)");
    2201     2219787 :   return gerepileuptoint(av, x);
    2202             : }
    2203             : GEN
    2204     9605899 : roundr_safe(GEN x)
    2205             : {
    2206     9605899 :   long ex, s = signe(x);
    2207             :   pari_sp av;
    2208             : 
    2209     9605899 :   if (!s || (ex = expo(x)) < -1) return gen_0;
    2210     9605899 :   if (ex == -1) return s>0? gen_1:
    2211           0 :                             absrnz_equal2n(x)? gen_0: gen_m1;
    2212     9605899 :   av = avma; x = round_i(x, &ex);
    2213     9605899 :   return gerepileuptoint(av, x);
    2214             : }
    2215             : 
    2216             : GEN
    2217      953857 : ground(GEN x)
    2218             : {
    2219             :   GEN y;
    2220             :   long i, lx;
    2221             :   pari_sp av;
    2222             : 
    2223      953857 :   switch(typ(x))
    2224             :   {
    2225      199195 :     case t_INT: return icopy(x);
    2226          28 :     case t_INTMOD: case t_QUAD: return gcopy(x);
    2227      543784 :     case t_REAL: return roundr(x);
    2228       17171 :     case t_FRAC: return diviiround(gel(x,1), gel(x,2));
    2229          14 :     case t_POLMOD: y=cgetg(3,t_POLMOD);
    2230          14 :       gel(y,1) = RgX_copy(gel(x,1));
    2231          14 :       gel(y,2) = ground(gel(x,2)); return y;
    2232             : 
    2233             :     case t_COMPLEX:
    2234          42 :       av = avma; y = cgetg(3, t_COMPLEX);
    2235          42 :       gel(y,2) = ground(gel(x,2));
    2236          42 :       if (!signe(gel(y,2))) { avma = av; return ground(gel(x,1)); }
    2237          42 :       gel(y,1) = ground(gel(x,1)); return y;
    2238             : 
    2239             :     case t_POL:
    2240          70 :       y = cgetg_copy(x, &lx); y[1] = x[1];
    2241          70 :       for (i=2; i<lx; i++) gel(y,i) = ground(gel(x,i));
    2242          70 :       return normalizepol_lg(y, lx);
    2243             :     case t_SER:
    2244        2492 :       if (ser_isexactzero(x)) return gcopy(x);
    2245        2394 :       y = cgetg_copy(x, &lx); y[1] = x[1];
    2246        2394 :       for (i=2; i<lx; i++) gel(y,i) = ground(gel(x,i));
    2247        2394 :       return normalize(y);
    2248             :     case t_RFRAC:
    2249          21 :       av = avma;
    2250          21 :       return gerepileupto(av, gdiv(ground(gel(x,1)), ground(gel(x,2))));
    2251             :     case t_VEC: case t_COL: case t_MAT:
    2252      191033 :       y = cgetg_copy(x, &lx);
    2253      191033 :       for (i=1; i<lx; i++) gel(y,i) = ground(gel(x,i));
    2254      191033 :       return y;
    2255             :   }
    2256           7 :   pari_err_TYPE("ground",x);
    2257           0 :   return NULL; /* not reached */
    2258             : }
    2259             : 
    2260             : /* e = number of error bits on integral part */
    2261             : GEN
    2262     8301641 : grndtoi(GEN x, long *e)
    2263             : {
    2264             :   GEN y;
    2265             :   long i, lx, e1;
    2266             :   pari_sp av;
    2267             : 
    2268     8301641 :   *e = -(long)HIGHEXPOBIT;
    2269     8301641 :   switch(typ(x))
    2270             :   {
    2271      623718 :     case t_INT: return icopy(x);
    2272             :     case t_REAL: {
    2273     5622354 :       long ex = expo(x);
    2274     5622354 :       if (!signe(x) || ex < -1) { *e = ex; return gen_0; }
    2275     5073636 :       av = avma; x = round_i(x, e);
    2276     5073636 :       return gerepileuptoint(av, x);
    2277             :     }
    2278        1114 :     case t_FRAC: return diviiround(gel(x,1), gel(x,2));
    2279          14 :     case t_INTMOD: case t_QUAD: return gcopy(x);
    2280             :     case t_COMPLEX:
    2281     1033298 :       av = avma; y = cgetg(3, t_COMPLEX);
    2282     1033298 :       gel(y,2) = grndtoi(gel(x,2), e);
    2283     1033298 :       if (!signe(gel(y,2))) {
    2284      144552 :         avma = av;
    2285      144552 :         y = grndtoi(gel(x,1), &e1);
    2286             :       }
    2287             :       else
    2288      888746 :         gel(y,1) = grndtoi(gel(x,1), &e1);
    2289     1033298 :       if (e1 > *e) *e = e1;
    2290     1033298 :       return y;
    2291             : 
    2292           7 :     case t_POLMOD: y = cgetg(3,t_POLMOD);
    2293           7 :       gel(y,1) = RgX_copy(gel(x,1));
    2294           7 :       gel(y,2) = grndtoi(gel(x,2), e); return y;
    2295             : 
    2296             :     case t_POL:
    2297       26248 :       y = cgetg_copy(x, &lx); y[1] = x[1];
    2298      422056 :       for (i=2; i<lx; i++)
    2299             :       {
    2300      395808 :         gel(y,i) = grndtoi(gel(x,i),&e1);
    2301      395808 :         if (e1 > *e) *e = e1;
    2302             :       }
    2303       26248 :       return normalizepol_lg(y, lx);
    2304             :     case t_SER:
    2305          98 :       if (ser_isexactzero(x)) return gcopy(x);
    2306          84 :       y = cgetg_copy(x, &lx); y[1] = x[1];
    2307         245 :       for (i=2; i<lx; i++)
    2308             :       {
    2309         161 :         gel(y,i) = grndtoi(gel(x,i),&e1);
    2310         161 :         if (e1 > *e) *e = e1;
    2311             :       }
    2312          84 :       return normalize(y);
    2313             :     case t_RFRAC:
    2314           7 :       y = cgetg(3,t_RFRAC);
    2315           7 :       gel(y,1) = grndtoi(gel(x,1),&e1); if (e1 > *e) *e = e1;
    2316           7 :       gel(y,2) = grndtoi(gel(x,2),&e1); if (e1 > *e) *e = e1;
    2317           7 :       return y;
    2318             :     case t_VEC: case t_COL: case t_MAT:
    2319      994776 :       y = cgetg_copy(x, &lx);
    2320     4063649 :       for (i=1; i<lx; i++)
    2321             :       {
    2322     3068873 :         gel(y,i) = grndtoi(gel(x,i),&e1);
    2323     3068873 :         if (e1 > *e) *e = e1;
    2324             :       }
    2325      994776 :       return y;
    2326             :   }
    2327           7 :   pari_err_TYPE("grndtoi",x);
    2328           0 :   return NULL; /* not reached */
    2329             : }
    2330             : 
    2331             : /* trunc(x * 2^s). lindep() sanity checks rely on this function to return a
    2332             :  * t_INT or fail when fed a non-t_COMPLEX input; so do not make this one
    2333             :  * recursive [ or change the lindep call ] */
    2334             : GEN
    2335    10029130 : gtrunc2n(GEN x, long s)
    2336             : {
    2337             :   GEN z;
    2338    10029130 :   switch(typ(x))
    2339             :   {
    2340     3464560 :     case t_INT:  return shifti(x, s);
    2341     5134107 :     case t_REAL: return trunc2nr(x, s);
    2342             :     case t_FRAC: {
    2343             :       pari_sp av;
    2344           0 :       GEN a = gel(x,1), b = gel(x,2), q;
    2345           0 :       if (s == 0) return divii(a, b);
    2346           0 :       av = avma;
    2347           0 :       if (s < 0) q = divii(shifti(a, s), b);
    2348             :       else {
    2349             :         GEN r;
    2350           0 :         q = dvmdii(a, b, &r);
    2351           0 :         q = addii(shifti(q,s), divii(shifti(r,s), b));
    2352             :       }
    2353           0 :       return gerepileuptoint(av, q);
    2354             :     }
    2355             :     case t_COMPLEX:
    2356     1430463 :       z = cgetg(3, t_COMPLEX);
    2357     1430463 :       gel(z,2) = gtrunc2n(gel(x,2), s);
    2358     1430463 :       if (!signe(gel(z,2))) {
    2359      146218 :         avma = (pari_sp)(z + 3);
    2360      146218 :         return gtrunc2n(gel(x,1), s);
    2361             :       }
    2362     1284245 :       gel(z,1) = gtrunc2n(gel(x,1), s);
    2363     1284245 :       return z;
    2364           0 :     default: pari_err_TYPE("gtrunc2n",x);
    2365           0 :       return NULL; /* not reached */
    2366             :   }
    2367             : }
    2368             : 
    2369             : /* e = number of error bits on integral part */
    2370             : GEN
    2371       82195 : gcvtoi(GEN x, long *e)
    2372             : {
    2373       82195 :   long tx = typ(x), lx, e1;
    2374             :   GEN y;
    2375             : 
    2376       82195 :   if (tx == t_REAL)
    2377             :   {
    2378       82062 :     long ex = expo(x); if (ex < 0) { *e = ex; return gen_0; }
    2379       82033 :     e1 = ex - bit_prec(x) + 1;
    2380       82033 :     y = mantissa2nr(x, e1);
    2381       82033 :     if (e1 <= 0) { pari_sp av = avma; e1 = expo(subri(x,y)); avma = av; }
    2382       82033 :     *e = e1; return y;
    2383             :   }
    2384         133 :   *e = -(long)HIGHEXPOBIT;
    2385         133 :   if (is_matvec_t(tx))
    2386             :   {
    2387             :     long i;
    2388          28 :     y = cgetg_copy(x, &lx);
    2389          84 :     for (i=1; i<lx; i++)
    2390             :     {
    2391          56 :       gel(y,i) = gcvtoi(gel(x,i),&e1);
    2392          56 :       if (e1 > *e) *e = e1;
    2393             :     }
    2394          28 :     return y;
    2395             :   }
    2396         105 :   return gtrunc(x);
    2397             : }
    2398             : 
    2399             : int
    2400       24360 : isint(GEN n, GEN *ptk)
    2401             : {
    2402       24360 :   switch(typ(n))
    2403             :   {
    2404       15659 :     case t_INT: *ptk = n; return 1;
    2405             :     case t_REAL: {
    2406         574 :       pari_sp av0 = avma;
    2407         574 :       GEN z = floorr(n);
    2408         574 :       pari_sp av = avma;
    2409         574 :       long s = signe(subri(n, z));
    2410         574 :       if (s) { avma = av0; return 0; }
    2411           0 :       *ptk = z; avma = av; return 1;
    2412             :     }
    2413        7357 :     case t_FRAC:    return 0;
    2414         602 :     case t_COMPLEX: return gequal0(gel(n,2)) && isint(gel(n,1),ptk);
    2415           0 :     case t_QUAD:    return gequal0(gel(n,3)) && isint(gel(n,2),ptk);
    2416         168 :     default: pari_err_TYPE("isint",n); return 0; /* not reached */
    2417             :   }
    2418             : }
    2419             : 
    2420             : int
    2421        7469 : issmall(GEN n, long *ptk)
    2422             : {
    2423        7469 :   pari_sp av = avma;
    2424             :   GEN z;
    2425             :   long k;
    2426        7469 :   if (!isint(n, &z)) return 0;
    2427        6013 :   k = itos_or_0(z); avma = av;
    2428        6013 :   if (k || lgefint(z) == 2) { *ptk = k; return 1; }
    2429           0 :   return 0;
    2430             : }
    2431             : 
    2432             : /* smallest integer greater than any incarnations of the real x
    2433             :  * Avoid "precision loss in truncation" */
    2434             : GEN
    2435       63360 : ceil_safe(GEN x)
    2436             : {
    2437       63360 :   pari_sp av = avma;
    2438       63360 :   long e, tx = typ(x);
    2439             :   GEN y;
    2440             : 
    2441       63360 :   if (is_rational_t(tx)) return gceil(x);
    2442       63346 :   y = gcvtoi(x,&e);
    2443       63346 :   if (gsigne(x) >= 0)
    2444             :   {
    2445       62810 :     if (e < 0) e = 0;
    2446       62810 :     y = addii(y, int2n(e));
    2447             :   }
    2448       63346 :   return gerepileuptoint(av, y);
    2449             : }
    2450             : /* largest integer smaller than any incarnations of the real x
    2451             :  * Avoid "precision loss in truncation" */
    2452             : GEN
    2453        7793 : floor_safe(GEN x)
    2454             : {
    2455        7793 :   pari_sp av = avma;
    2456        7793 :   long e, tx = typ(x);
    2457             :   GEN y;
    2458             : 
    2459        7793 :   if (is_rational_t(tx)) return gfloor(x);
    2460        7793 :   y = gcvtoi(x,&e);
    2461        7793 :   if (gsigne(x) <= 0)
    2462             :   {
    2463          21 :     if (e < 0) e = 0;
    2464          21 :     y = subii(y, int2n(e));
    2465             :   }
    2466        7793 :   return gerepileuptoint(av, y);
    2467             : }
    2468             : 
    2469             : GEN
    2470        3262 : ser2rfrac_i(GEN x)
    2471             : {
    2472        3262 :   long e = valp(x);
    2473        3262 :   GEN a = ser2pol_i(x, lg(x));
    2474        3262 :   if (e) {
    2475        2100 :     if (e > 0) a = RgX_shift_shallow(a, e);
    2476           0 :     else a = gred_rfrac_simple(a, monomial(gen_1, -e, varn(a)));
    2477             :   }
    2478        3262 :   return a;
    2479             : }
    2480             : 
    2481             : static GEN
    2482         252 : ser2rfrac(GEN x)
    2483             : {
    2484         252 :   pari_sp av = avma;
    2485         252 :   return gerepilecopy(av, ser2rfrac_i(x));
    2486             : }
    2487             : 
    2488             : /* x t_PADIC, truncate to rational (t_INT/t_FRAC) */
    2489             : GEN
    2490        8141 : padic_to_Q(GEN x)
    2491             : {
    2492        8141 :   GEN u = gel(x,4), p;
    2493             :   long v;
    2494        8141 :   if (!signe(u)) return gen_0;
    2495        7728 :   v = valp(x);
    2496        7728 :   if (!v) return icopy(u);
    2497         532 :   p = gel(x,2);
    2498         532 :   if (v>0)
    2499             :   {
    2500         413 :     pari_sp av = avma;
    2501         413 :     return gerepileuptoint(av, mulii(u, powiu(p,v)));
    2502             :   }
    2503         119 :   retmkfrac(icopy(u), powiu(p,-v));
    2504             : }
    2505             : GEN
    2506          21 : padic_to_Q_shallow(GEN x)
    2507             : {
    2508          21 :   GEN u = gel(x,4), p;
    2509             :   long v;
    2510          21 :   if (!signe(u)) return gen_0;
    2511          21 :   v = valp(x);
    2512          21 :   if (!v) return u;
    2513          14 :   p = gel(x,2);
    2514          14 :   if (v>0) return mulii(powiu(p,v), u);
    2515          14 :   return mkfrac(u, powiu(p,-v));
    2516             : }
    2517             : GEN
    2518          70 : QpV_to_QV(GEN v)
    2519             : {
    2520             :   long i, l;
    2521          70 :   GEN w = cgetg_copy(v, &l);
    2522         399 :   for (i = 1; i < l; i++)
    2523             :   {
    2524         329 :     GEN c = gel(v,i);
    2525         329 :     switch(typ(c))
    2526             :     {
    2527             :       case t_INT:
    2528         308 :       case t_FRAC: break;
    2529          21 :       case t_PADIC: c = padic_to_Q_shallow(c); break;
    2530           0 :       default: pari_err_TYPE("padic_to_Q", v);
    2531             :     }
    2532         329 :     gel(w,i) = c;
    2533             :   }
    2534          70 :   return w;
    2535             : }
    2536             : 
    2537             : GEN
    2538         882 : gtrunc(GEN x)
    2539             : {
    2540             :   long i;
    2541             :   GEN y;
    2542             : 
    2543         882 :   switch(typ(x))
    2544             :   {
    2545         133 :     case t_INT: return icopy(x);
    2546          14 :     case t_REAL: return truncr(x);
    2547          56 :     case t_FRAC: return divii(gel(x,1),gel(x,2));
    2548         287 :     case t_PADIC: return padic_to_Q(x);
    2549          42 :     case t_POL: return RgX_copy(x);
    2550          14 :     case t_RFRAC: return gdeuc(gel(x,1),gel(x,2));
    2551         224 :     case t_SER: return ser2rfrac(x);
    2552             :     case t_VEC: case t_COL: case t_MAT:
    2553             :     {
    2554             :       long lx;
    2555          56 :       y = cgetg_copy(x, &lx);
    2556          56 :       for (i=1; i<lx; i++) gel(y,i) = gtrunc(gel(x,i));
    2557          56 :       return y;
    2558             :     }
    2559             :   }
    2560          56 :   pari_err_TYPE("gtrunc",x);
    2561           0 :   return NULL; /* not reached */
    2562             : }
    2563             : 
    2564             : GEN
    2565         217 : trunc0(GEN x, GEN *pte)
    2566             : {
    2567         217 :   if (pte) { long e; x = gcvtoi(x,&e); *pte = stoi(e); }
    2568         189 :   return gtrunc(x);
    2569             : }
    2570             : /*******************************************************************/
    2571             : /*                                                                 */
    2572             : /*                  CONVERSIONS -->  INT, POL & SER                */
    2573             : /*                                                                 */
    2574             : /*******************************************************************/
    2575             : 
    2576             : /* return a_(n-1) B^(n-1) + ... + a_0, where B = 2^32.
    2577             :  * The a_i are 32bits integers */
    2578             : GEN
    2579       14105 : mkintn(long n, ...)
    2580             : {
    2581             :   va_list ap;
    2582             :   GEN x, y;
    2583             :   long i;
    2584             : #ifdef LONG_IS_64BIT
    2585       12090 :   long e = (n&1);
    2586       12090 :   n = (n+1) >> 1;
    2587             : #endif
    2588       14105 :   va_start(ap,n);
    2589       14105 :   x = cgetipos(n+2);
    2590       14105 :   y = int_MSW(x);
    2591       49910 :   for (i=0; i <n; i++)
    2592             :   {
    2593             : #ifdef LONG_IS_64BIT
    2594       27900 :     ulong a = (e && !i)? 0: (ulong) va_arg(ap, unsigned int);
    2595       27900 :     ulong b = (ulong) va_arg(ap, unsigned int);
    2596       27900 :     *y = (a << 32) | b;
    2597             : #else
    2598        7905 :     *y = (ulong) va_arg(ap, unsigned int);
    2599             : #endif
    2600       35805 :     y = int_precW(y);
    2601             :   }
    2602       14105 :   va_end(ap);
    2603       14105 :   return int_normalize(x, 0);
    2604             : }
    2605             : 
    2606             : /* 2^32 a + b */
    2607             : GEN
    2608      426958 : uu32toi(ulong a, ulong b)
    2609             : {
    2610             : #ifdef LONG_IS_64BIT
    2611      354377 :   return utoi((a<<32) | b);
    2612             : #else
    2613       72581 :   return uutoi(a, b);
    2614             : #endif
    2615             : }
    2616             : 
    2617             : /* return a_(n-1) x^(n-1) + ... + a_0 */
    2618             : GEN
    2619     2387651 : mkpoln(long n, ...)
    2620             : {
    2621             :   va_list ap;
    2622             :   GEN x, y;
    2623     2387651 :   long i, l = n+2;
    2624     2387651 :   va_start(ap,n);
    2625     2387651 :   x = cgetg(l, t_POL); y = x + 2;
    2626     2387650 :   x[1] = evalvarn(0);
    2627     2387650 :   for (i=n-1; i >= 0; i--) gel(y,i) = va_arg(ap, GEN);
    2628     2387650 :   va_end(ap); return normalizepol_lg(x, l);
    2629             : }
    2630             : 
    2631             : /* return [a_1, ..., a_n] */
    2632             : GEN
    2633       16933 : mkvecn(long n, ...)
    2634             : {
    2635             :   va_list ap;
    2636             :   GEN x;
    2637             :   long i;
    2638       16933 :   va_start(ap,n);
    2639       16933 :   x = cgetg(n+1, t_VEC);
    2640       16933 :   for (i=1; i <= n; i++) gel(x,i) = va_arg(ap, GEN);
    2641       16933 :   va_end(ap); return x;
    2642             : }
    2643             : 
    2644             : GEN
    2645           0 : mkcoln(long n, ...)
    2646             : {
    2647             :   va_list ap;
    2648             :   GEN x;
    2649             :   long i;
    2650           0 :   va_start(ap,n);
    2651           0 :   x = cgetg(n+1, t_COL);
    2652           0 :   for (i=1; i <= n; i++) gel(x,i) = va_arg(ap, GEN);
    2653           0 :   va_end(ap); return x;
    2654             : }
    2655             : 
    2656             : GEN
    2657        3872 : mkvecsmalln(long n, ...)
    2658             : {
    2659             :   va_list ap;
    2660             :   GEN x;
    2661             :   long i;
    2662        3872 :   va_start(ap,n);
    2663        3872 :   x = cgetg(n+1, t_VECSMALL);
    2664        3872 :   for (i=1; i <= n; i++) x[i] = va_arg(ap, long);
    2665        3872 :   va_end(ap); return x;
    2666             : }
    2667             : 
    2668             : GEN
    2669     5184500 : scalarpol(GEN x, long v)
    2670             : {
    2671             :   GEN y;
    2672     5184500 :   if (isrationalzero(x)) return zeropol(v);
    2673     2824639 :   y = cgetg(3,t_POL);
    2674     5648830 :   y[1] = gequal0(x)? evalvarn(v)
    2675     2824191 :                    : evalvarn(v) | evalsigne(1);
    2676     2824639 :   gel(y,2) = gcopy(x); return y;
    2677             : }
    2678             : GEN
    2679      234187 : scalarpol_shallow(GEN x, long v)
    2680             : {
    2681             :   GEN y;
    2682      234187 :   if (isrationalzero(x)) return zeropol(v);
    2683      230715 :   y = cgetg(3,t_POL);
    2684      460940 :   y[1] = gequal0(x)? evalvarn(v)
    2685      230225 :                    : evalvarn(v) | evalsigne(1);
    2686      230715 :   gel(y,2) = x; return y;
    2687             : }
    2688             : 
    2689             : /* x0 + x1*T, do not assume x1 != 0 */
    2690             : GEN
    2691      523072 : deg1pol(GEN x1, GEN x0,long v)
    2692             : {
    2693      523072 :   GEN x = cgetg(4,t_POL);
    2694      523072 :   x[1] = evalsigne(1) | evalvarn(v);
    2695      523072 :   gel(x,2) = x0 == gen_0? x0: gcopy(x0); /* gen_0 frequent */
    2696      523072 :   gel(x,3) = gcopy(x1); return normalizepol_lg(x,4);
    2697             : }
    2698             : 
    2699             : /* same, no copy */
    2700             : GEN
    2701     1736520 : deg1pol_shallow(GEN x1, GEN x0,long v)
    2702             : {
    2703     1736520 :   GEN x = cgetg(4,t_POL);
    2704     1736520 :   x[1] = evalsigne(1) | evalvarn(v);
    2705     1736520 :   gel(x,2) = x0;
    2706     1736520 :   gel(x,3) = x1; return normalizepol_lg(x,4);
    2707             : }
    2708             : 
    2709             : static GEN
    2710     2492553 : _gtopoly(GEN x, long v, int reverse)
    2711             : {
    2712     2492553 :   long tx = typ(x);
    2713             :   GEN y;
    2714             : 
    2715     2492553 :   if (v<0) v = 0;
    2716     2492553 :   switch(tx)
    2717             :   {
    2718             :     case t_POL:
    2719          21 :       if (varncmp(varn(x), v) < 0) pari_err_PRIORITY("gtopoly", x, "<", v);
    2720          21 :       y = RgX_copy(x); break;
    2721             :     case t_SER:
    2722          28 :       if (varncmp(varn(x), v) < 0) pari_err_PRIORITY("gtopoly", x, "<", v);
    2723          28 :       y = ser2rfrac(x);
    2724          28 :       if (typ(y) != t_POL)
    2725           0 :         pari_err_DOMAIN("gtopoly", "valuation", "<", gen_0, x);
    2726          28 :       break;
    2727             :     case t_RFRAC:
    2728             :     {
    2729          42 :       GEN a = gel(x,1), b = gel(x,2);
    2730          42 :       long vb = varn(b);
    2731          42 :       if (varncmp(vb, v) < 0) pari_err_PRIORITY("gtopoly", x, "<", v);
    2732          42 :       if (typ(a) != t_POL || varn(a) != vb) return zeropol(v);
    2733          21 :       y = RgX_div(a,b); break;
    2734             :     }
    2735          21 :     case t_VECSMALL: x = zv_to_ZV(x); /* fall through */
    2736             :     case t_QFR: case t_QFI: case t_VEC: case t_COL: case t_MAT:
    2737             :     {
    2738     2492126 :       long j, k, lx = lg(x);
    2739             :       GEN z;
    2740     2492126 :       if (tx == t_QFR) lx--;
    2741     2492126 :       if (varncmp(gvar(x), v) <= 0) pari_err_PRIORITY("gtopoly", x, "<=", v);
    2742     2492126 :       y = cgetg(lx+1, t_POL);
    2743     2492126 :       y[1] = evalvarn(v);
    2744     2492126 :       if (reverse) {
    2745     2424380 :         x--;
    2746     2424380 :         for (j=2; j<=lx; j++) gel(y,j) = gel(x,j);
    2747             :       } else {
    2748       67746 :         for (j=2, k=lx; k>=2; j++) gel(y,j) = gel(x,--k);
    2749             :       }
    2750     2492126 :       z = RgX_copy(normalizepol_lg(y,lx+1));
    2751     2492126 :       settyp(y, t_VECSMALL);/* left on stack */
    2752     2492126 :       return z;
    2753             :     }
    2754             :     default:
    2755         336 :       if (is_scalar_t(tx)) return scalarpol(x,v);
    2756           7 :       pari_err_TYPE("gtopoly",x);
    2757           0 :       return NULL; /* not reached */
    2758             :   }
    2759          70 :   setvarn(y,v); return y;
    2760             : }
    2761             : 
    2762             : GEN
    2763     2424415 : gtopolyrev(GEN x, long v) { return _gtopoly(x,v,1); }
    2764             : 
    2765             : GEN
    2766       68138 : gtopoly(GEN x, long v) { return _gtopoly(x,v,0); }
    2767             : 
    2768             : /* assume prec >= 0 */
    2769             : GEN
    2770      186417 : scalarser(GEN x, long v, long prec)
    2771             : {
    2772             :   long i, l;
    2773             :   GEN y;
    2774             : 
    2775      186417 :   if (gequal0(x))
    2776             :   {
    2777         805 :     if (isrationalzero(x)) return zeroser(v, prec);
    2778          56 :     if (!isexactzero(x)) prec--;
    2779          56 :     y = cgetg(3, t_SER);
    2780          56 :     y[1] = evalsigne(0) | _evalvalp(prec) | evalvarn(v);
    2781          56 :     gel(y,2) = gcopy(x); return y;
    2782             :   }
    2783      185612 :   l = prec + 2; y = cgetg(l, t_SER);
    2784      185612 :   y[1] = evalsigne(1) | _evalvalp(0) | evalvarn(v);
    2785      185612 :   gel(y,2) = gcopy(x); for (i=3; i<l; i++) gel(y,i) = gen_0;
    2786      185612 :   return y;
    2787             : }
    2788             : 
    2789             : /* assume x a t_[SER|POL], apply gtoser to all coeffs */
    2790             : static GEN
    2791           7 : coefstoser(GEN x, long v, long prec)
    2792             : {
    2793             :   long i, lx;
    2794           7 :   GEN y = cgetg_copy(x, &lx); y[1] = x[1];
    2795           7 :   for (i=2; i<lx; i++) gel(y,i) = gtoser(gel(x,i), v, prec);
    2796           7 :   return y;
    2797             : }
    2798             : 
    2799             : /* x a t_POL. Not stack-clean */
    2800             : GEN
    2801      173495 : poltoser(GEN x, long v, long prec)
    2802             : {
    2803      173495 :   long vx = varn(x);
    2804             :   GEN y;
    2805             : 
    2806      173495 :   if (varncmp(vx, v) > 0) return scalarser(x, v, prec);
    2807      173439 :   if (varncmp(vx, v) < 0) return coefstoser(x, v, prec);
    2808      173439 :   y = RgX_to_ser(x, prec+2);
    2809      173439 :   setvarn(y, v); return y;
    2810             : }
    2811             : 
    2812             : /* x a t_RFRAC. Not stack-clean */
    2813             : GEN
    2814      171563 : rfractoser(GEN x, long v, long prec)
    2815             : {
    2816      171563 :   GEN n = gel(x,1);
    2817      171563 :   if (is_scalar_t(typ(n)))
    2818      171507 :     n = scalarser(n, v, prec);
    2819             :   else
    2820          56 :     n = poltoser(n, v, prec);
    2821      171563 :   return gdiv(n, poltoser(gel(x,2), v, prec));
    2822             : }
    2823             : 
    2824             : GEN
    2825      646736 : toser_i(GEN x)
    2826             : {
    2827      646736 :   switch(typ(x))
    2828             :   {
    2829       40789 :     case t_SER: return x;
    2830        1239 :     case t_POL: return RgX_to_ser(x, precdl+2);
    2831         133 :     case t_RFRAC: return rfrac_to_ser(x, precdl+2);
    2832             :   }
    2833      604575 :   return NULL;
    2834             : }
    2835             : 
    2836             : GEN
    2837      172144 : gtoser(GEN x, long v, long prec)
    2838             : {
    2839      172144 :   long tx=typ(x), i, j, l;
    2840             :   pari_sp av;
    2841             :   GEN y;
    2842             : 
    2843      172144 :   if (v < 0) v = 0;
    2844      172144 :   if (prec < 0)
    2845           7 :     pari_err_DOMAIN("gtoser", "precision", "<", gen_0, stoi(prec));
    2846      172137 :   if (tx == t_SER)
    2847             :   {
    2848          35 :     long vx = varn(x);
    2849          35 :     if      (varncmp(vx, v) < 0) y = coefstoser(x, v, prec);
    2850          28 :     else if (varncmp(vx, v) > 0) y = scalarser(x, v, prec);
    2851          14 :     else y = gcopy(x);
    2852          35 :     return y;
    2853             :   }
    2854      172102 :   if (is_scalar_t(tx)) return scalarser(x,v,prec);
    2855      171990 :   switch(tx)
    2856             :   {
    2857             :     case t_POL:
    2858         119 :       if (varncmp(varn(x), v) < 0) pari_err_PRIORITY("gtoser", x, "<", v);
    2859         119 :       y = poltoser(x, v, prec); l = lg(y);
    2860         728 :       for (i=2; i<l; i++)
    2861         609 :         if (gel(y,i) != gen_0) gel(y,i) = gcopy(gel(y,i));
    2862         119 :       break;
    2863             : 
    2864             :     case t_RFRAC:
    2865      171556 :       if (varncmp(varn(gel(x,2)), v) < 0) pari_err_PRIORITY("gtoser",x,"<",v);
    2866      171556 :       av = avma;
    2867      171556 :       return gerepileupto(av, rfractoser(x, v, prec));
    2868             : 
    2869          21 :     case t_VECSMALL: x = zv_to_ZV(x);/*fall through*/
    2870             :     case t_QFR: case t_QFI: case t_VEC: case t_COL:
    2871             :     {
    2872             :       GEN z;
    2873         308 :       long lx = lg(x); if (tx == t_QFR) lx--;
    2874         308 :       if (varncmp(gvar(x), v) <= 0) pari_err_PRIORITY("gtoser", x, "<=", v);
    2875         308 :       y = cgetg(lx+1, t_SER);
    2876         308 :       y[1] = evalvarn(v)|evalvalp(0);
    2877         308 :       x--;
    2878         308 :       for (j=2; j<=lx; j++) gel(y,j) = gel(x,j);
    2879         308 :       z = gcopy(normalize(y));
    2880         308 :       settyp(y, t_VECSMALL);/* left on stack */
    2881         308 :       return z;
    2882             :     }
    2883             : 
    2884           7 :     default: pari_err_TYPE("gtoser",x);
    2885           0 :       return NULL; /* not reached */
    2886             :   }
    2887         119 :   return y;
    2888             : }
    2889             : 
    2890             : static GEN
    2891        1141 : gtovecpost(GEN x, long n)
    2892             : {
    2893        1141 :   long i, imax, lx, tx = typ(x);
    2894        1141 :   GEN y = zerovec(n);
    2895             : 
    2896        1141 :   if (is_scalar_t(tx) || tx == t_RFRAC) { gel(y,1) = gcopy(x); return y; }
    2897         392 :   switch(tx)
    2898             :   {
    2899             :     case t_POL:
    2900          56 :       lx=lg(x); imax = minss(lx-2, n);
    2901          56 :       for (i=1; i<=imax; i++) gel(y,i) = gcopy(gel(x,lx-i));
    2902          56 :       return y;
    2903             :     case t_SER:
    2904         133 :       lx=lg(x); imax = minss(lx-2, n); x++;
    2905         133 :       for (i=1; i<=imax; i++) gel(y,i) = gcopy(gel(x,i));
    2906         133 :       return y;
    2907             :     case t_QFR: case t_QFI: case t_VEC: case t_COL:
    2908          28 :       lx=lg(x); imax = minss(lx-1, n);
    2909          28 :       for (i=1; i<=imax; i++) gel(y,i) = gcopy(gel(x,i));
    2910          28 :       return y;
    2911             :     case t_LIST:
    2912          63 :       if (list_typ(x) == t_LIST_MAP) pari_err_TYPE("gtovec",x);
    2913          56 :       x = list_data(x); lx = x? lg(x): 1;
    2914          56 :       imax = minss(lx-1, n);
    2915          56 :       for (i=1; i<=imax; i++) gel(y,i) = gcopy(gel(x,i));
    2916          56 :       return y;
    2917             :     case t_VECSMALL:
    2918          28 :       lx=lg(x);
    2919          28 :       imax = minss(lx-1, n);
    2920          28 :       for (i=1; i<=imax; i++) gel(y,i) = stoi(x[i]);
    2921          28 :       return y;
    2922          84 :     default: pari_err_TYPE("gtovec",x);
    2923           0 :       return NULL; /*notreached*/
    2924             :   }
    2925             : }
    2926             : 
    2927             : static GEN
    2928         245 : init_vectopre(long a, long n, GEN y, long *imax)
    2929             : {
    2930         245 :   *imax = minss(a, n);
    2931         245 :   return (n == *imax)?  y: y + n - a;
    2932             : }
    2933             : static GEN
    2934         343 : gtovecpre(GEN x, long n)
    2935             : {
    2936         343 :   long i, imax, lx, tx = typ(x);
    2937         343 :   GEN y = zerovec(n), y0;
    2938             : 
    2939         343 :   if (is_scalar_t(tx) || tx == t_RFRAC) { gel(y,n) = gcopy(x); return y; }
    2940         287 :   switch(tx)
    2941             :   {
    2942             :     case t_POL:
    2943          56 :       lx=lg(x);
    2944          56 :       y0 = init_vectopre(lx-2, n, y, &imax);
    2945          56 :       for (i=1; i<=imax; i++) gel(y0,i) = gcopy(gel(x,lx-i));
    2946          56 :       return y;
    2947             :     case t_SER:
    2948          28 :       lx=lg(x); x++;
    2949          28 :       y0 = init_vectopre(lx-2, n, y, &imax);
    2950          28 :       for (i=1; i<=imax; i++) gel(y0,i) = gcopy(gel(x,i));
    2951          28 :       return y;
    2952             :     case t_QFR: case t_QFI: case t_VEC: case t_COL:
    2953          28 :       lx=lg(x);
    2954          28 :       y0 = init_vectopre(lx-1, n, y, &imax);
    2955          28 :       for (i=1; i<=imax; i++) gel(y0,i) = gcopy(gel(x,i));
    2956          28 :       return y;
    2957             :     case t_LIST:
    2958          63 :       if (list_typ(x) == t_LIST_MAP) pari_err_TYPE("gtovec",x);
    2959          56 :       x = list_data(x); lx = x? lg(x): 1;
    2960          56 :       y0 = init_vectopre(lx-1, n, y, &imax);
    2961          56 :       for (i=1; i<=imax; i++) gel(y0,i) = gcopy(gel(x,i));
    2962          56 :       return y;
    2963             :     case t_VECSMALL:
    2964          28 :       lx=lg(x);
    2965          28 :       y0 = init_vectopre(lx-1, n, y, &imax);
    2966          28 :       for (i=1; i<=imax; i++) gel(y0,i) = stoi(x[i]);
    2967          28 :       return y;
    2968          84 :     default: pari_err_TYPE("gtovec",x);
    2969           0 :       return NULL; /*notreached*/
    2970             :   }
    2971             : }
    2972             : GEN
    2973      246491 : gtovec0(GEN x, long n)
    2974             : {
    2975      246491 :   if (!n) return gtovec(x);
    2976        1484 :   if (n > 0) return gtovecpost(x, n);
    2977         343 :   return gtovecpre(x, -n);
    2978             : }
    2979             : 
    2980             : GEN
    2981      245455 : gtovec(GEN x)
    2982             : {
    2983      245455 :   long i, lx, tx = typ(x);
    2984             :   GEN y;
    2985             : 
    2986      245455 :   if (is_scalar_t(tx)) return mkveccopy(x);
    2987      245413 :   switch(tx)
    2988             :   {
    2989             :     case t_POL:
    2990       15204 :       lx=lg(x); y=cgetg(lx-1,t_VEC);
    2991       15204 :       for (i=1; i<=lx-2; i++) gel(y,i) = gcopy(gel(x,lx-i));
    2992       15204 :       return y;
    2993             :     case t_SER:
    2994         196 :       lx=lg(x); y=cgetg(lx-1,t_VEC); x++;
    2995         196 :       for (i=1; i<=lx-2; i++) gel(y,i) = gcopy(gel(x,i));
    2996         196 :       return y;
    2997          28 :     case t_RFRAC: return mkveccopy(x);
    2998             :     case t_QFR: case t_QFI: case t_VEC: case t_COL: case t_MAT:
    2999      224140 :       lx=lg(x); y=cgetg(lx,t_VEC);
    3000      224140 :       for (i=1; i<lx; i++) gel(y,i) = gcopy(gel(x,i));
    3001      224140 :       return y;
    3002             :     case t_LIST:
    3003          70 :       if (list_typ(x) == t_LIST_MAP) return mapdomain(x);
    3004          56 :       x = list_data(x); lx = x? lg(x): 1;
    3005          56 :       y = cgetg(lx, t_VEC);
    3006          56 :       for (i=1; i<lx; i++) gel(y,i) = gcopy(gel(x,i));
    3007          56 :       return y;
    3008             :     case t_STR:
    3009             :     {
    3010          28 :       char *s = GSTR(x);
    3011          28 :       lx = strlen(s)+1; y = cgetg(lx, t_VEC);
    3012          28 :       s--;
    3013          28 :       for (i=1; i<lx; i++) gel(y,i) = chartoGENstr(s[i]);
    3014          28 :       return y;
    3015             :     }
    3016             :     case t_VECSMALL:
    3017        5719 :       return vecsmall_to_vec(x);
    3018             :     case t_ERROR:
    3019          28 :       lx=lg(x); y = cgetg(lx,t_VEC);
    3020          28 :       gel(y,1) = errname(x);
    3021          28 :       for (i=2; i<lx; i++) gel(y,i) = gcopy(gel(x,i));
    3022          28 :       return y;
    3023           0 :     default: pari_err_TYPE("gtovec",x);
    3024           0 :       return NULL; /*notreached*/
    3025             :   }
    3026             : }
    3027             : 
    3028             : GEN
    3029         266 : gtovecrev0(GEN x, long n)
    3030             : {
    3031         266 :   GEN y = gtovec0(x, -n);
    3032         224 :   vecreverse_inplace(y);
    3033         224 :   return y;
    3034             : }
    3035             : GEN
    3036           7 : gtovecrev(GEN x) { return gtovecrev0(x, 0); }
    3037             : 
    3038             : GEN
    3039        1197 : gtocol0(GEN x, long n)
    3040             : {
    3041             :   GEN y;
    3042        1197 :   if (!n) return gtocol(x);
    3043        1015 :   y = gtovec0(x, n);
    3044         931 :   settyp(y, t_COL); return y;
    3045             : }
    3046             : GEN
    3047         182 : gtocol(GEN x)
    3048             : {
    3049             :   long lx, tx, i, j, h;
    3050             :   GEN y;
    3051         182 :   tx = typ(x);
    3052         182 :   if (tx != t_MAT) { y = gtovec(x); settyp(y, t_COL); return y; }
    3053          14 :   lx = lg(x); if (lx == 1) return cgetg(1, t_COL);
    3054          14 :   h = lgcols(x); y = cgetg(h, t_COL);
    3055          42 :   for (i = 1 ; i < h; i++) {
    3056          28 :     gel(y,i) = cgetg(lx, t_VEC);
    3057          28 :     for (j = 1; j < lx; j++) gmael(y,i,j) = gcopy(gcoeff(x,i,j));
    3058             :   }
    3059          14 :   return y;
    3060             : }
    3061             : 
    3062             : GEN
    3063         252 : gtocolrev0(GEN x, long n)
    3064             : {
    3065         252 :   GEN y = gtocol0(x, -n);
    3066         210 :   long ly = lg(y), lim = ly>>1, i;
    3067         210 :   for (i = 1; i <= lim; i++) swap(gel(y,i), gel(y,ly-i));
    3068         210 :   return y;
    3069             : }
    3070             : GEN
    3071           0 : gtocolrev(GEN x) { return gtocolrev0(x, 0); }
    3072             : 
    3073             : static long
    3074     2941886 : Itos(GEN x)
    3075             : {
    3076     2941886 :    if (typ(x) != t_INT) pari_err_TYPE("vectosmall",x);
    3077     2941886 :    return itos(x);
    3078             : }
    3079             : 
    3080             : static GEN
    3081          84 : gtovecsmallpost(GEN x, long n)
    3082             : {
    3083             :   long i, imax, lx;
    3084          84 :   GEN y = zero_Flv(n);
    3085             : 
    3086          84 :   switch(typ(x))
    3087             :   {
    3088             :     case t_INT:
    3089           7 :       y[1] = itos(x); return y;
    3090             :     case t_POL:
    3091          14 :       lx=lg(x); imax = minss(lx-2, n);
    3092          14 :       for (i=1; i<=imax; i++) y[i] = Itos(gel(x,lx-i));
    3093          14 :       return y;
    3094             :     case t_SER:
    3095           7 :       lx=lg(x); imax = minss(lx-2, n); x++;
    3096           7 :       for (i=1; i<=imax; i++) y[i] = Itos(gel(x,i));
    3097           7 :       return y;
    3098             :     case t_VEC: case t_COL:
    3099           7 :       lx=lg(x); imax = minss(lx-1, n);
    3100           7 :       for (i=1; i<=imax; i++) y[i] = Itos(gel(x,i));
    3101           7 :       return y;
    3102             :     case t_LIST:
    3103          14 :       x = list_data(x); lx = x? lg(x): 1;
    3104          14 :       imax = minss(lx-1, n);
    3105          14 :       for (i=1; i<=imax; i++) y[i] = Itos(gel(x,i));
    3106          14 :       return y;
    3107             :     case t_VECSMALL:
    3108           7 :       lx=lg(x);
    3109           7 :       imax = minss(lx-1, n);
    3110           7 :       for (i=1; i<=imax; i++) y[i] = x[i];
    3111           7 :       return y;
    3112          28 :     default: pari_err_TYPE("gtovecsmall",x);
    3113           0 :       return NULL; /*notreached*/
    3114             :   }
    3115             : }
    3116             : static GEN
    3117          84 : gtovecsmallpre(GEN x, long n)
    3118             : {
    3119             :   long i, imax, lx;
    3120          84 :   GEN y = zero_Flv(n), y0;
    3121             : 
    3122          84 :   switch(typ(x))
    3123             :   {
    3124             :     case t_INT:
    3125           7 :       y[n] = itos(x); return y;
    3126             :     case t_POL:
    3127          14 :       lx=lg(x);
    3128          14 :       y0 = init_vectopre(lx-2, n, y, &imax);
    3129          14 :       for (i=1; i<=imax; i++) y0[i] = Itos(gel(x,lx-i));
    3130          14 :       return y;
    3131             :     case t_SER:
    3132           7 :       lx=lg(x); x++;
    3133           7 :       y0 = init_vectopre(lx-2, n, y, &imax);
    3134           7 :       for (i=1; i<=imax; i++) y0[i] = Itos(gel(x,i));
    3135           7 :       return y;
    3136             :     case t_VEC: case t_COL:
    3137           7 :       lx=lg(x);
    3138           7 :       y0 = init_vectopre(lx-1, n, y, &imax);
    3139           7 :       for (i=1; i<=imax; i++) y0[i] = Itos(gel(x,i));
    3140           7 :       return y;
    3141             :     case t_LIST:
    3142          14 :       x = list_data(x); lx = x? lg(x): 1;
    3143          14 :       y0 = init_vectopre(lx-1, n, y, &imax);
    3144          14 :       for (i=1; i<=imax; i++) y0[i] = Itos(gel(x,i));
    3145          14 :       return y;
    3146             :     case t_VECSMALL:
    3147           7 :       lx=lg(x);
    3148           7 :       y0 = init_vectopre(lx-1, n, y, &imax);
    3149           7 :       for (i=1; i<=imax; i++) y0[i] = x[i];
    3150           7 :       return y;
    3151          28 :     default: pari_err_TYPE("gtovecsmall",x);
    3152           0 :       return NULL; /*notreached*/
    3153             :   }
    3154             : }
    3155             : 
    3156             : GEN
    3157       13447 : gtovecsmall0(GEN x, long n)
    3158             : {
    3159       13447 :   if (!n) return gtovecsmall(x);
    3160         168 :   if (n > 0) return gtovecsmallpost(x, n);
    3161          84 :   return gtovecsmallpre(x, -n);
    3162             : }
    3163             : 
    3164             : GEN
    3165     1736521 : gtovecsmall(GEN x)
    3166             : {
    3167             :   GEN V;
    3168             :   long l, i;
    3169             : 
    3170     1736521 :   switch(typ(x))
    3171             :   {
    3172          28 :     case t_INT: return mkvecsmall(itos(x));
    3173             :     case t_STR:
    3174             :     {
    3175          14 :       char *s = GSTR(x);
    3176          14 :       l = strlen(s);
    3177          14 :       V = cgetg(l+1, t_VECSMALL);
    3178          14 :       s--;
    3179          14 :       for (i=1; i<=l; i++) V[i] = (long)s[i];
    3180          14 :       return V;
    3181             :     }
    3182           7 :     case t_VECSMALL: return leafcopy(x);
    3183             :     case t_LIST:
    3184          14 :       x = list_data(x);
    3185          14 :       if (!x) return cgetg(1, t_VECSMALL);
    3186             :       /* fall through */
    3187             :     case t_VEC: case t_COL:
    3188     1736430 :       l = lg(x); V = cgetg(l,t_VECSMALL);
    3189     1736430 :       for(i=1; i<l; i++) V[i] = Itos(gel(x,i));
    3190     1736430 :       return V;
    3191             :     case t_POL:
    3192          14 :       l = lg(x); V = cgetg(l-1,t_VECSMALL);
    3193          14 :       for (i=1; i<=l-2; i++) V[i] = Itos(gel(x,l-i));
    3194          14 :       return V;
    3195             :     case t_SER:
    3196           7 :       l = lg(x); V = cgetg(l-1,t_VECSMALL); x++;
    3197           7 :       for (i=1; i<=l-2; i++) V[i] = Itos(gel(x,i));
    3198           7 :       return V;
    3199             :     default:
    3200          21 :       pari_err_TYPE("vectosmall",x);
    3201           0 :       return NULL; /* not reached */
    3202             :   }
    3203             : }
    3204             : 
    3205             : GEN
    3206         312 : compo(GEN x, long n)
    3207             : {
    3208         312 :   long tx = typ(x);
    3209         312 :   ulong l, lx = (ulong)lg(x);
    3210             : 
    3211         312 :   if (!is_recursive_t(tx))
    3212             :   {
    3213          49 :     if (tx == t_VECSMALL)
    3214             :     {
    3215          21 :       if (n < 1) pari_err_COMPONENT("", "<", gen_1, stoi(n));
    3216          21 :       if ((ulong)n >= lx) pari_err_COMPONENT("", ">", utoi(lx-1), stoi(n));
    3217           7 :       return stoi(x[n]);
    3218             :     }
    3219          28 :     pari_err_TYPE("component [leaf]", x);
    3220             :   }
    3221         263 :   if (n < 1) pari_err_COMPONENT("", "<", gen_1, stoi(n));
    3222         256 :   if (tx == t_POL && (ulong)n+1 >= lx) return gen_0;
    3223         242 :   if (tx == t_LIST) {
    3224          28 :     tx = t_VEC;
    3225          28 :     x = list_data(x);
    3226          28 :     lx = (ulong)(x? lg(x): 1);
    3227             :   }
    3228         242 :   l = (ulong)lontyp[tx] + (ulong)n-1; /* beware overflow */
    3229         242 :   if (l >= lx) pari_err_COMPONENT("", ">", utoi(lx-1), utoi(l));
    3230         186 :   return gcopy(gel(x,l));
    3231             : }
    3232             : 
    3233             : /* assume v > varn(x), extract coeff of pol_x(v)^n */
    3234             : static GEN
    3235       41902 : multi_coeff(GEN x, long n, long v, long dx)
    3236             : {
    3237       41902 :   long i, lx = dx+3;
    3238       41902 :   GEN z = cgetg(lx, t_POL); z[1] = x[1];
    3239       41902 :   for (i = 2; i < lx; i++) gel(z,i) = polcoeff_i(gel(x,i), n, v);
    3240       41902 :   z = normalizepol_lg(z, lx);
    3241       41902 :   switch(lg(z))
    3242             :   {
    3243        9506 :     case 2: z = gen_0; break;
    3244       21546 :     case 3: z = gel(z,2); break;
    3245             :   }
    3246       41902 :   return z;
    3247             : }
    3248             : 
    3249             : /* assume x a t_POL */
    3250             : static GEN
    3251      199080 : _polcoeff(GEN x, long n, long v)
    3252             : {
    3253             :   long w, dx;
    3254      199080 :   dx = degpol(x);
    3255      199080 :   if (dx < 0) return gen_0;
    3256      199038 :   if (v < 0 || v == (w=varn(x)))
    3257      157157 :     return (n < 0 || n > dx)? gen_0: gel(x,n+2);
    3258       41881 :   if (varncmp(w,v) > 0) return n? gen_0: x;
    3259             :   /* w < v */
    3260       41881 :   return multi_coeff(x, n, v, dx);
    3261             : }
    3262             : 
    3263             : /* assume x a t_SER */
    3264             : static GEN
    3265        1309 : _sercoeff(GEN x, long n, long v)
    3266             : {
    3267        1309 :   long w, dx = lg(x)-3, ex = valp(x), N = n - ex;
    3268             :   GEN z;
    3269        1309 :   if (dx < 0)
    3270             :   {
    3271          14 :     if (N >= 0) pari_err_DOMAIN("polcoeff", "t_SER", "=", x, x);
    3272           7 :     return gen_0;
    3273             :   }
    3274        1295 :   if (v < 0 || v == (w=varn(x)))
    3275             :   {
    3276        1260 :     if (N > dx)
    3277          14 :       pari_err_DOMAIN("polcoeff", "degree", ">", stoi(dx+ex), stoi(n));
    3278        1246 :     return (N < 0)? gen_0: gel(x,N+2);
    3279             :   }
    3280          35 :   if (varncmp(w,v) > 0) return N? gen_0: x;
    3281             :   /* w < v */
    3282          21 :   z = multi_coeff(x, n, v, dx);
    3283          21 :   if (ex) z = gmul(z, monomial(gen_1,ex, w));
    3284          21 :   return z;
    3285             : }
    3286             : 
    3287             : /* assume x a t_RFRAC(n) */
    3288             : static GEN
    3289          21 : _rfraccoeff(GEN x, long n, long v)
    3290             : {
    3291          21 :   GEN P,Q, p = gel(x,1), q = gel(x,2);
    3292          21 :   long vp = gvar(p), vq = gvar(q);
    3293          21 :   if (v < 0) v = varncmp(vp, vq) < 0? vp: vq;
    3294          21 :   P = (vp == v)? p: swap_vars(p, v);
    3295          21 :   Q = (vq == v)? q: swap_vars(q, v);
    3296          21 :   if (!RgX_is_monomial(Q)) pari_err_TYPE("polcoeff", x);
    3297          21 :   n += degpol(Q);
    3298          21 :   return gdiv(_polcoeff(P, n, v), leading_coeff(Q));
    3299             : }
    3300             : 
    3301             : GEN
    3302      186529 : polcoeff_i(GEN x, long n, long v)
    3303             : {
    3304      186529 :   switch(typ(x))
    3305             :   {
    3306      140840 :     case t_POL: return _polcoeff(x,n,v);
    3307         147 :     case t_SER: return _sercoeff(x,n,v);
    3308           0 :     case t_RFRAC: return _rfraccoeff(x,n,v);
    3309       45542 :     default: return n? gen_0: x;
    3310             :   }
    3311             : }
    3312             : 
    3313             : /* with respect to the main variable if v<0, with respect to the variable v
    3314             :    otherwise. v ignored if x is not a polynomial/series. */
    3315             : GEN
    3316       59591 : polcoeff0(GEN x, long n, long v)
    3317             : {
    3318       59591 :   long lx, tx = typ(x);
    3319             :   pari_sp av;
    3320             : 
    3321       59591 :   if (is_scalar_t(tx)) return n? gen_0: gcopy(x);
    3322       59570 :   av = avma;
    3323       59570 :   switch(tx)
    3324             :   {
    3325       58219 :     case t_POL: x = _polcoeff(x,n,v); break;
    3326        1162 :     case t_SER: x = _sercoeff(x,n,v); break;
    3327          21 :     case t_RFRAC: x = _rfraccoeff(x,n,v); break;
    3328             : 
    3329             :     case t_QFR: case t_QFI: case t_VEC: case t_COL: case t_MAT:
    3330          56 :       if (n < 1) pari_err_COMPONENT("polcoeff","<",gen_1,stoi(n));
    3331          35 :       lx = lg(x);
    3332          35 :       if (n >= lx) pari_err_COMPONENT("polcoeff",">",stoi(lx-1),stoi(n));
    3333          14 :       return gcopy(gel(x,n));
    3334             : 
    3335         112 :     default: pari_err_TYPE("polcoeff", x);
    3336             :   }
    3337       59381 :   if (x == gen_0) return x;
    3338       57680 :   if (avma == av) return gcopy(x);
    3339        1148 :   return gerepilecopy(av, x);
    3340             : }
    3341             : 
    3342             : static GEN
    3343         812 : vecdenom(GEN v, long imin, long imax)
    3344             : {
    3345         812 :   pari_sp av = avma;
    3346         812 :   long i = imin;
    3347             :   GEN s;
    3348         812 :   if (imin > imax) return gen_1;
    3349         812 :   s = denom(gel(v,i));
    3350        1939 :   for (i++; i<=imax; i++)
    3351             :   {
    3352        1127 :     GEN t = denom(gel(v,i));
    3353        1127 :     if (t != gen_1) s = glcm(s,t);
    3354             :   }
    3355         812 :   return gerepileupto(av, s);
    3356             : }
    3357             : GEN
    3358     9168278 : denom(GEN x)
    3359             : {
    3360     9168278 :   switch(typ(x))
    3361             :   {
    3362             :     case t_INT:
    3363             :     case t_REAL:
    3364             :     case t_INTMOD:
    3365             :     case t_FFELT:
    3366             :     case t_PADIC:
    3367     1920500 :     case t_SER: return gen_1;
    3368        7617 :     case t_FRAC: return icopy(gel(x,2));
    3369          84 :     case t_COMPLEX: return vecdenom(x,1,2);
    3370          42 :     case t_QUAD: return vecdenom(x,2,3);
    3371          91 :     case t_POLMOD: return denom(gel(x,2));
    3372     7238341 :     case t_RFRAC: return RgX_copy(gel(x,2));
    3373         903 :     case t_POL: return pol_1(varn(x));
    3374         686 :     case t_VEC: case t_COL: case t_MAT: return vecdenom(x, 1, lg(x)-1);
    3375             :   }
    3376          14 :   pari_err_TYPE("denom",x);
    3377           0 :   return NULL; /* not reached */
    3378             : }
    3379             : 
    3380             : GEN
    3381     8233322 : numer(GEN x)
    3382             : {
    3383             :   pari_sp av;
    3384     8233322 :   switch(typ(x))
    3385             :   {
    3386             :     case t_INT:
    3387     1025620 :     case t_REAL: return mpcopy(x);
    3388             :     case t_INTMOD:
    3389             :     case t_FFELT:
    3390             :     case t_PADIC:
    3391         126 :     case t_SER: return gcopy(x);
    3392         819 :     case t_POL: return RgX_copy(x);
    3393        1239 :     case t_FRAC: return icopy(gel(x,1));
    3394             :     case t_POLMOD:
    3395           7 :       av = avma; return gerepileupto(av, gmodulo(numer(gel(x,2)), gel(x,1)));
    3396     7205448 :     case t_RFRAC: return gcopy(gel(x,1));
    3397             :     case t_COMPLEX:
    3398             :     case t_QUAD:
    3399             :     case t_VEC:
    3400             :     case t_COL:
    3401             :     case t_MAT:
    3402          49 :       av = avma; return gerepileupto(av, gmul(denom(x),x));
    3403             :   }
    3404          14 :   pari_err_TYPE("numer",x);
    3405           0 :   return NULL; /* not reached */
    3406             : }
    3407             : 
    3408             : /* Lift only intmods if v does not occur in x, lift with respect to main
    3409             :  * variable of x if v < 0, with respect to variable v otherwise.
    3410             :  */
    3411             : GEN
    3412      225350 : lift0(GEN x, long v)
    3413             : {
    3414             :   long lx, i;
    3415             :   GEN y;
    3416             : 
    3417      225350 :   switch(typ(x))
    3418             :   {
    3419       30303 :     case t_INT: return icopy(x);
    3420      129856 :     case t_INTMOD: return v < 0? icopy(gel(x,2)): gcopy(x);
    3421             :     case t_POLMOD:
    3422       52143 :       if (v < 0 || v == varn(gel(x,1))) return gcopy(gel(x,2));
    3423          14 :       y = cgetg(3, t_POLMOD);
    3424          14 :       gel(y,1) = lift0(gel(x,1),v);
    3425          14 :       gel(y,2) = lift0(gel(x,2),v); return y;
    3426         973 :     case t_PADIC: return v < 0? padic_to_Q(x): gcopy(x);
    3427             :     case t_POL:
    3428       10514 :       y = cgetg_copy(x, &lx); y[1] = x[1];
    3429       10514 :       for (i=2; i<lx; i++) gel(y,i) = lift0(gel(x,i), v);
    3430       10514 :       return normalizepol_lg(y,lx);
    3431             :     case t_SER:
    3432          56 :       if (ser_isexactzero(x))
    3433             :       {
    3434          14 :         if (lg(x) == 2) return gcopy(x);
    3435          14 :         return scalarser(lift0(gel(x,2),v), varn(x), valp(x));
    3436             :       }
    3437          42 :       y = cgetg_copy(x, &lx); y[1] = x[1];
    3438          42 :       for (i=2; i<lx; i++) gel(y,i) = lift0(gel(x,i), v);
    3439          42 :       return normalize(y);
    3440             :     case t_COMPLEX: case t_QUAD: case t_RFRAC:
    3441             :     case t_VEC: case t_COL: case t_MAT:
    3442        1127 :       y = cgetg_copy(x, &lx);
    3443        1127 :       for (i=1; i<lx; i++) gel(y,i) = lift0(gel(x,i), v);
    3444        1127 :       return y;
    3445         378 :     default: return gcopy(x);
    3446             :   }
    3447             : }
    3448             : GEN
    3449      135837 : lift(GEN x) { return lift0(x,-1); }
    3450             : 
    3451             : GEN
    3452         679 : liftall_shallow(GEN x)
    3453             : {
    3454             :   long lx, i;
    3455             :   GEN y;
    3456             : 
    3457         679 :   switch(typ(x))
    3458             :   {
    3459         189 :     case t_INTMOD: return gel(x,2);
    3460             :     case t_POLMOD:
    3461         140 :       return liftall_shallow(gel(x,2));
    3462         147 :     case t_PADIC: return padic_to_Q(x);
    3463             :     case t_POL:
    3464         133 :       y = cgetg_copy(x, &lx); y[1] = x[1];
    3465         133 :       for (i=2; i<lx; i++) gel(y,i) = liftall_shallow(gel(x,i));
    3466         133 :       return normalizepol_lg(y,lx);
    3467             :     case t_SER:
    3468           7 :       if (ser_isexactzero(x))
    3469             :       {
    3470           0 :         if (lg(x) == 2) return x;
    3471           0 :         return scalarser(liftall_shallow(gel(x,2)), varn(x), valp(x));
    3472             :       }
    3473           7 :       y = cgetg_copy(x, &lx); y[1] = x[1];
    3474           7 :       for (i=2; i<lx; i++) gel(y,i) = liftall_shallow(gel(x,i));
    3475           7 :       return normalize(y);
    3476             :     case t_COMPLEX: case t_QUAD: case t_RFRAC:
    3477             :     case t_VEC: case t_COL: case t_MAT:
    3478           7 :       y = cgetg_copy(x, &lx);
    3479           7 :       for (i=1; i<lx; i++) gel(y,i) = liftall_shallow(gel(x,i));
    3480           7 :       return y;
    3481          56 :     default: return x;
    3482             :   }
    3483             : }
    3484             : GEN
    3485          77 : liftall(GEN x)
    3486          77 : { pari_sp av = avma; return gerepilecopy(av, liftall_shallow(x)); }
    3487             : 
    3488             : GEN
    3489         546 : liftint_shallow(GEN x)
    3490             : {
    3491             :   long lx, i;
    3492             :   GEN y;
    3493             : 
    3494         546 :   switch(typ(x))
    3495             :   {
    3496         266 :     case t_INTMOD: return gel(x,2);
    3497          28 :     case t_PADIC: return padic_to_Q(x);
    3498             :     case t_POL:
    3499          21 :       y = cgetg_copy(x, &lx); y[1] = x[1];
    3500          21 :       for (i=2; i<lx; i++) gel(y,i) = liftint_shallow(gel(x,i));
    3501          21 :       return normalizepol_lg(y,lx);
    3502             :     case t_SER:
    3503          14 :       if (ser_isexactzero(x))
    3504             :       {
    3505           7 :         if (lg(x) == 2) return x;
    3506           7 :         return scalarser(liftint_shallow(gel(x,2)), varn(x), valp(x));
    3507             :       }
    3508           7 :       y = cgetg_copy(x, &lx); y[1] = x[1];
    3509           7 :       for (i=2; i<lx; i++) gel(y,i) = liftint_shallow(gel(x,i));
    3510           7 :       return normalize(y);
    3511             :     case t_POLMOD: case t_COMPLEX: case t_QUAD: case t_RFRAC:
    3512             :     case t_VEC: case t_COL: case t_MAT:
    3513         161 :       y = cgetg_copy(x, &lx);
    3514         161 :       for (i=1; i<lx; i++) gel(y,i) = liftint_shallow(gel(x,i));
    3515         161 :       return y;
    3516          56 :     default: return x;
    3517             :   }
    3518             : }
    3519             : GEN
    3520         119 : liftint(GEN x)
    3521         119 : { pari_sp av = avma; return gerepilecopy(av, liftint_shallow(x)); }
    3522             : 
    3523             : GEN
    3524      139013 : liftpol_shallow(GEN x)
    3525             : {
    3526             :   long lx, i;
    3527             :   GEN y;
    3528             : 
    3529      139013 :   switch(typ(x))
    3530             :   {
    3531             :     case t_POLMOD:
    3532       33663 :       return liftpol_shallow(gel(x,2));
    3533             :     case t_POL:
    3534       23478 :       y = cgetg_copy(x, &lx); y[1] = x[1];
    3535       23478 :       for (i=2; i<lx; i++) gel(y,i) = liftpol_shallow(gel(x,i));
    3536       23478 :       return normalizepol_lg(y,lx);
    3537             :     case t_SER:
    3538           7 :       if (ser_isexactzero(x))
    3539             :       {
    3540           0 :         if (lg(x) == 2) return x;
    3541           0 :         return scalarser(liftpol_shallow(gel(x,2)), varn(x), valp(x));
    3542             :       }
    3543           7 :       y = cgetg_copy(x, &lx); y[1] = x[1];
    3544           7 :       for (i=2; i<lx; i++) gel(y,i) = liftpol_shallow(gel(x,i));
    3545           7 :       return normalize(y);
    3546             :     case t_RFRAC: case t_VEC: case t_COL: case t_MAT:
    3547          42 :       y = cgetg_copy(x, &lx);
    3548          42 :       for (i=1; i<lx; i++) gel(y,i) = liftpol_shallow(gel(x,i));
    3549          42 :       return y;
    3550       81823 :     default: return x;
    3551             :   }
    3552             : }
    3553             : GEN
    3554          98 : liftpol(GEN x)
    3555          98 : { pari_sp av = avma; return gerepilecopy(av, liftpol_shallow(x)); }
    3556             : 
    3557             : /* same as lift, without copy. May DESTROY x. For internal use only */
    3558             : GEN
    3559      218088 : lift_intern(GEN x)
    3560             : {
    3561             :   long i;
    3562      218088 :   switch(typ(x))
    3563             :   {
    3564       72408 :     case t_INTMOD: case t_POLMOD: return gel(x,2);
    3565           0 :     case t_PADIC: return padic_to_Q(x);
    3566             :     case t_SER:
    3567           0 :       if (ser_isexactzero(x))
    3568             :       {
    3569           0 :         if (lg(x) == 2) return x;
    3570           0 :         return scalarser(lift_intern(gel(x,2)), varn(x), valp(x));
    3571             :       }
    3572           0 :       for (i = lg(x)-1; i>=2; i--) gel(x,i) = lift_intern(gel(x,i));
    3573           0 :       return normalize(x);
    3574             :     case t_POL:
    3575       21973 :       for (i = lg(x)-1; i>=2; i--) gel(x,i) = lift_intern(gel(x,i));
    3576       21973 :       return normalizepol(x);
    3577             :     case t_COMPLEX: case t_QUAD: case t_RFRAC:
    3578             :     case t_VEC: case t_COL: case t_MAT:
    3579       16177 :       for (i = lg(x)-1; i>=1; i--) gel(x,i) = lift_intern(gel(x,i));
    3580       16177 :       return x;
    3581      107530 :     default: return x;
    3582             :   }
    3583             : }
    3584             : 
    3585             : static GEN
    3586        9408 : centerliftii(GEN x, GEN y)
    3587             : {
    3588        9408 :   pari_sp av = avma;
    3589        9408 :   long i = cmpii(shifti(x,1), y);
    3590        9408 :   avma = av; return (i > 0)? subii(x,y): icopy(x);
    3591             : }
    3592             : 
    3593             : /* see lift0 */
    3594             : GEN
    3595         105 : centerlift0(GEN x, long v)
    3596         105 : { return v < 0? centerlift(x): lift0(x,v); }
    3597             : GEN
    3598       13454 : centerlift(GEN x)
    3599             : {
    3600             :   long i, v, lx;
    3601             :   GEN y;
    3602       13454 :   switch(typ(x))
    3603             :   {
    3604         686 :     case t_INT: return icopy(x);
    3605        5313 :     case t_INTMOD: return centerliftii(gel(x,2), gel(x,1));
    3606           7 :     case t_POLMOD: return gcopy(gel(x,2));
    3607             :    case t_POL:
    3608        1421 :       y = cgetg_copy(x, &lx); y[1] = x[1];
    3609        1421 :       for (i=2; i<lx; i++) gel(y,i) = centerlift(gel(x,i));
    3610        1421 :       return normalizepol_lg(y,lx);
    3611             :    case t_SER:
    3612           7 :       if (ser_isexactzero(x)) return lift(x);
    3613           7 :       y = cgetg_copy(x, &lx); y[1] = x[1];
    3614           7 :       for (i=2; i<lx; i++) gel(y,i) = centerlift(gel(x,i));
    3615           7 :       return normalize(y);
    3616             :    case t_COMPLEX: case t_QUAD: case t_RFRAC:
    3617             :    case t_VEC: case t_COL: case t_MAT:
    3618          42 :       y = cgetg_copy(x, &lx);
    3619          42 :       for (i=1; i<lx; i++) gel(y,i) = centerlift(gel(x,i));
    3620          42 :       return y;
    3621             :     case t_PADIC:
    3622        5971 :       if (!signe(gel(x,4))) return gen_0;
    3623        4095 :       v = valp(x);
    3624        4095 :       if (v>=0)
    3625             :       { /* here p^v is an integer */
    3626        4088 :         GEN z =  centerliftii(gel(x,4), gel(x,3));
    3627             :         pari_sp av;
    3628        4088 :         if (!v) return z;
    3629        1974 :         av = avma; y = powiu(gel(x,2),v);
    3630        1974 :         return gerepileuptoint(av, mulii(y,z));
    3631             :       }
    3632           7 :       y = cgetg(3,t_FRAC);
    3633           7 :       gel(y,1) = centerliftii(gel(x,4), gel(x,3));
    3634           7 :       gel(y,2) = powiu(gel(x,2),-v);
    3635           7 :       return y;
    3636           7 :     default: return gcopy(x);
    3637             :   }
    3638             : }
    3639             : 
    3640             : /*******************************************************************/
    3641             : /*                                                                 */
    3642             : /*                      REAL & IMAGINARY PARTS                     */
    3643             : /*                                                                 */
    3644             : /*******************************************************************/
    3645             : 
    3646             : static GEN
    3647     1141785 : op_ReIm(GEN f(GEN), GEN x)
    3648             : {
    3649             :   long lx, i, j;
    3650             :   pari_sp av;
    3651             :   GEN z;
    3652             : 
    3653     1141785 :   switch(typ(x))
    3654             :   {
    3655             :     case t_POL:
    3656        5796 :       z = cgetg_copy(x, &lx); z[1] = x[1];
    3657        5796 :       for (j=2; j<lx; j++) gel(z,j) = f(gel(x,j));
    3658        5796 :       return normalizepol_lg(z, lx);
    3659             : 
    3660             :     case t_SER:
    3661       28295 :       z = cgetg_copy(x, &lx); z[1] = x[1];
    3662       28295 :       for (j=2; j<lx; j++) gel(z,j) = f(gel(x,j));
    3663       28295 :       return normalize(z);
    3664             : 
    3665             :     case t_RFRAC: {
    3666             :       GEN dxb, n, d;
    3667           0 :       av = avma; dxb = gconj(gel(x,2));
    3668           0 :       n = gmul(gel(x,1), dxb);
    3669           0 :       d = gmul(gel(x,2), dxb);
    3670           0 :       return gerepileupto(av, gdiv(f(n), d));
    3671             :     }
    3672             : 
    3673             :     case t_VEC: case t_COL: case t_MAT:
    3674     1107694 :       z = cgetg_copy(x, &lx);
    3675     1107694 :       for (i=1; i<lx; i++) gel(z,i) = f(gel(x,i));
    3676     1107694 :       return z;
    3677             :   }
    3678           0 :   pari_err_TYPE("greal/gimag",x);
    3679           0 :   return NULL; /* not reached */
    3680             : }
    3681             : 
    3682             : GEN
    3683     6461260 : real_i(GEN x)
    3684             : {
    3685     6461260 :   switch(typ(x))
    3686             :   {
    3687             :     case t_INT: case t_REAL: case t_FRAC:
    3688      572621 :       return x;
    3689             :     case t_COMPLEX:
    3690     4778736 :       return gel(x,1);
    3691             :     case t_QUAD:
    3692           0 :       return gel(x,2);
    3693             :   }
    3694     1109903 :   return op_ReIm(real_i,x);
    3695             : }
    3696             : GEN
    3697      351592 : imag_i(GEN x)
    3698             : {
    3699      351592 :   switch(typ(x))
    3700             :   {
    3701             :     case t_INT: case t_REAL: case t_FRAC:
    3702       53720 :       return gen_0;
    3703             :     case t_COMPLEX:
    3704      290848 :       return gel(x,2);
    3705             :     case t_QUAD:
    3706           0 :       return gel(x,3);
    3707             :   }
    3708        7024 :   return op_ReIm(imag_i,x);
    3709             : }
    3710             : GEN
    3711       81265 : greal(GEN x)
    3712             : {
    3713       81265 :   switch(typ(x))
    3714             :   {
    3715             :     case t_INT: case t_REAL:
    3716       34182 :       return mpcopy(x);
    3717             : 
    3718             :     case t_FRAC:
    3719           0 :       return gcopy(x);
    3720             : 
    3721             :     case t_COMPLEX:
    3722       22491 :       return gcopy(gel(x,1));
    3723             : 
    3724             :     case t_QUAD:
    3725           0 :       return gcopy(gel(x,2));
    3726             :   }
    3727       24592 :   return op_ReIm(greal,x);
    3728             : }
    3729             : GEN
    3730        2525 : gimag(GEN x)
    3731             : {
    3732        2525 :   switch(typ(x))
    3733             :   {
    3734             :     case t_INT: case t_REAL: case t_FRAC:
    3735        1176 :       return gen_0;
    3736             : 
    3737             :     case t_COMPLEX:
    3738        1083 :       return gcopy(gel(x,2));
    3739             : 
    3740             :     case t_QUAD:
    3741           0 :       return gcopy(gel(x,3));
    3742             :   }
    3743         266 :   return op_ReIm(gimag,x);
    3744             : }
    3745             : 
    3746             : /* return Re(x * y), x and y scalars */
    3747             : GEN
    3748    11028692 : mulreal(GEN x, GEN y)
    3749             : {
    3750    11028692 :   if (typ(x) == t_COMPLEX)
    3751             :   {
    3752    11014762 :     if (typ(y) == t_COMPLEX)
    3753             :     {
    3754    10893728 :       pari_sp av = avma;
    3755    10893728 :       GEN a = gmul(gel(x,1), gel(y,1));
    3756    10893728 :       GEN b = gmul(gel(x,2), gel(y,2));
    3757    10893728 :       return gerepileupto(av, gsub(a, b));
    3758             :     }
    3759      121034 :     x = gel(x,1);
    3760             :   }
    3761             :   else
    3762       13930 :     if (typ(y) == t_COMPLEX) y = gel(y,1);
    3763      134964 :   return gmul(x,y);
    3764             : }
    3765             : /* Compute Re(x * y), x and y matrices of compatible dimensions
    3766             :  * assume scalar entries */
    3767             : GEN
    3768           0 : RgM_mulreal(GEN x, GEN y)
    3769             : {
    3770           0 :   long i, j, k, l, lx = lg(x), ly = lg(y);
    3771           0 :   GEN z = cgetg(ly,t_MAT);
    3772           0 :   l = (lx == 1)? 1: lgcols(x);
    3773           0 :   for (j=1; j<ly; j++)
    3774             :   {
    3775           0 :     GEN zj = cgetg(l,t_COL), yj = gel(y,j);
    3776           0 :     gel(z,j) = zj;
    3777           0 :     for (i=1; i<l; i++)
    3778             :     {
    3779           0 :       pari_sp av = avma;
    3780           0 :       GEN c = mulreal(gcoeff(x,i,1),gel(yj,1));
    3781           0 :       for (k=2; k<lx; k++) c = gadd(c, mulreal(gcoeff(x,i,k),gel(yj,k)));
    3782           0 :       gel(zj, i) = gerepileupto(av, c);
    3783             :     }
    3784             :   }
    3785           0 :   return z;
    3786             : }
    3787             : 
    3788             : /*******************************************************************/
    3789             : /*                                                                 */
    3790             : /*                     LOGICAL OPERATIONS                          */
    3791             : /*                                                                 */
    3792             : /*******************************************************************/
    3793             : static long
    3794    24203352 : _egal_i(GEN x, GEN y)
    3795             : {
    3796    24203352 :   x = simplify_shallow(x);
    3797    24203352 :   y = simplify_shallow(y);
    3798    24203352 :   if (typ(y) == t_INT)
    3799             :   {
    3800    23901094 :     if (equali1(y)) return gequal1(x);
    3801    23188515 :     if (equalim1(y)) return gequalm1(x);
    3802             :   }
    3803      302258 :   else if (typ(x) == t_INT)
    3804             :   {
    3805          63 :     if (equali1(x)) return gequal1(y);
    3806          42 :     if (equalim1(x)) return gequalm1(y);
    3807             :   }
    3808    23454828 :   return gequal(x, y);
    3809             : }
    3810             : static long
    3811    24203352 : _egal(GEN x, GEN y)
    3812             : {
    3813    24203352 :   pari_sp av = avma;
    3814    24203352 :   long r = _egal_i(x, y);
    3815    24203352 :   avma = av; return r;
    3816             : }
    3817             : 
    3818             : GEN
    3819     6211614 : glt(GEN x, GEN y) { return gcmp(x,y)<0? gen_1: gen_0; }
    3820             : 
    3821             : GEN
    3822     7623459 : gle(GEN x, GEN y) { return gcmp(x,y)<=0? gen_1: gen_0; }
    3823             : 
    3824             : GEN
    3825      124174 : gge(GEN x, GEN y) { return gcmp(x,y)>=0? gen_1: gen_0; }
    3826             : 
    3827             : GEN
    3828      132482 : ggt(GEN x, GEN y) { return gcmp(x,y)>0? gen_1: gen_0; }
    3829             : 
    3830             : GEN
    3831     1218187 : geq(GEN x, GEN y) { return _egal(x,y)? gen_1: gen_0; }
    3832             : 
    3833             : GEN
    3834    22985165 : gne(GEN x, GEN y) { return _egal(x,y)? gen_0: gen_1; }
    3835             : 
    3836             : GEN
    3837      259441 : gnot(GEN x) { return gequal0(x)? gen_1: gen_0; }
    3838             : 
    3839             : /*******************************************************************/
    3840             : /*                                                                 */
    3841             : /*                      FORMAL SIMPLIFICATIONS                     */
    3842             : /*                                                                 */
    3843             : /*******************************************************************/
    3844             : 
    3845             : GEN
    3846       10129 : geval_gp(GEN x, GEN t)
    3847             : {
    3848       10129 :   long lx, i, tx = typ(x);
    3849             :   pari_sp av;
    3850             :   GEN y, z;
    3851             : 
    3852       10129 :   if (is_const_t(tx)) return gcopy(x);
    3853       10115 :   switch(tx)
    3854             :   {
    3855             :     case t_STR:
    3856       10108 :       return localvars_read_str(GSTR(x),t);
    3857             : 
    3858             :     case t_POLMOD:
    3859           0 :       av = avma;
    3860           0 :       return gerepileupto(av, gmodulo(geval_gp(gel(x,2),t),
    3861           0 :                                       geval_gp(gel(x,1),t)));
    3862             : 
    3863             :     case t_POL:
    3864           7 :       lx=lg(x); if (lx==2) return gen_0;
    3865           7 :       z = fetch_var_value(varn(x),t);
    3866           7 :       if (!z) return RgX_copy(x);
    3867           7 :       av = avma; y = geval_gp(gel(x,lx-1),t);
    3868          14 :       for (i=lx-2; i>1; i--)
    3869           7 :         y = gadd(geval_gp(gel(x,i),t), gmul(z,y));
    3870           7 :       return gerepileupto(av, y);
    3871             : 
    3872             :     case t_SER:
    3873           0 :       pari_err_IMPL( "evaluation of a power series");
    3874             : 
    3875             :     case t_RFRAC:
    3876           0 :       av = avma;
    3877           0 :       return gerepileupto(av, gdiv(geval_gp(gel(x,1),t), geval_gp(gel(x,2),t)));
    3878             : 
    3879             :     case t_QFR: case t_QFI: case t_VEC: case t_COL: case t_MAT:
    3880           0 :       y = cgetg_copy(x, &lx);
    3881           0 :       for (i=1; i<lx; i++) gel(y,i) = geval_gp(gel(x,i),t);
    3882           0 :       return y;
    3883             : 
    3884             :     case t_CLOSURE:
    3885           0 :       if (closure_arity(x) || closure_is_variadic(x))
    3886           0 :         pari_err_IMPL("eval on functions with parameters");
    3887           0 :       return closure_evalres(x);
    3888             :   }
    3889           0 :   pari_err_TYPE("geval",x);
    3890           0 :   return NULL; /* not reached */
    3891             : }
    3892             : GEN
    3893           0 : geval(GEN x) { return geval_gp(x,NULL); }
    3894             : 
    3895             : GEN
    3896   311819257 : simplify_shallow(GEN x)
    3897             : {
    3898             :   long i, lx;
    3899             :   GEN y, z;
    3900   311819257 :   if (!x) pari_err_BUG("simplify, NULL input");
    3901             : 
    3902   311819257 :   switch(typ(x))
    3903             :   {
    3904             :     case t_INT: case t_REAL: case t_INTMOD: case t_FRAC: case t_FFELT:
    3905             :     case t_PADIC: case t_QFR: case t_QFI: case t_LIST: case t_STR: case t_VECSMALL:
    3906             :     case t_CLOSURE: case t_ERROR: case t_INFINITY:
    3907   241647216 :       return x;
    3908       37645 :     case t_COMPLEX: return isintzero(gel(x,2))? gel(x,1): x;
    3909         609 :     case t_QUAD:    return isintzero(gel(x,3))? gel(x,2): x;
    3910             : 
    3911       88919 :     case t_POLMOD: y = cgetg(3,t_POLMOD);
    3912       88919 :       z = simplify_shallow(gel(x,1));
    3913       88919 :       if (typ(z) != t_POL) z = scalarpol(z, varn(gel(x,1)));
    3914       88919 :       gel(y,1) = z; /* z must be a t_POL: invalid object otherwise */
    3915       88919 :       gel(y,2) = simplify_shallow(gel(x,2)); return y;
    3916             : 
    3917             :     case t_POL:
    3918    65628659 :       lx = lg(x);
    3919    65628659 :       if (lx==2) return gen_0;
    3920    58401694 :       if (lx==3) return simplify_shallow(gel(x,2));
    3921    54703735 :       y = cgetg(lx,t_POL); y[1] = x[1];
    3922    54703735 :       for (i=2; i<lx; i++) gel(y,i) = simplify_shallow(gel(x,i));
    3923    54703735 :       return y;
    3924             : 
    3925             :     case t_SER:
    3926        1848 :       y = cgetg_copy(x, &lx); y[1] = x[1];
    3927        1848 :       for (i=2; i<lx; i++) gel(y,i) = simplify_shallow(gel(x,i));
    3928        1848 :       return y;
    3929             : 
    3930      628305 :     case t_RFRAC: y = cgetg(3,t_RFRAC);
    3931      628305 :       gel(y,1) = simplify_shallow(gel(x,1));
    3932      628305 :       z = simplify_shallow(gel(x,2));
    3933      628305 :       if (typ(z) != t_POL) return gdiv(gel(y,1), z);
    3934      628305 :       gel(y,2) = z; return y;
    3935             : 
    3936             :     case t_VEC: case t_COL: case t_MAT:
    3937     3786056 :       y = cgetg_copy(x, &lx);
    3938     3786056 :       for (i=1; i<lx; i++) gel(y,i) = simplify_shallow(gel(x,i));
    3939     3786056 :       return y;
    3940             :   }
    3941           0 :   pari_err_BUG("simplify_shallow, type unknown");
    3942           0 :   return NULL; /* not reached */
    3943             : }
    3944             : 
    3945             : GEN
    3946    10837818 : simplify(GEN x)
    3947             : {
    3948    10837818 :   pari_sp av = avma;
    3949    10837818 :   GEN y = simplify_shallow(x);
    3950    10837818 :   return av == avma ? gcopy(y): gerepilecopy(av, y);
    3951             : }
    3952             : 
    3953             : /*******************************************************************/
    3954             : /*                                                                 */
    3955             : /*                EVALUATION OF SOME SIMPLE OBJECTS                */
    3956             : /*                                                                 */
    3957             : /*******************************************************************/
    3958             : /* q is a real symetric matrix, x a RgV. Horner-type evaluation of q(x)
    3959             :  * using (n^2+3n-2)/2 mul */
    3960             : GEN
    3961          21 : qfeval(GEN q, GEN x)
    3962             : {
    3963          21 :   pari_sp av = avma;
    3964          21 :   long i, j, l = lg(q);
    3965             :   GEN z;
    3966          21 :   if (lg(x) != l) pari_err_DIM("qfeval");
    3967          14 :   if (l==1) return gen_0;
    3968          14 :   if (lgcols(q) != l) pari_err_DIM("qfeval");
    3969             :   /* l = lg(x) = lg(q) > 1 */
    3970           7 :   z = gmul(gcoeff(q,1,1), gsqr(gel(x,1)));
    3971          21 :   for (i=2; i<l; i++)
    3972             :   {
    3973          14 :     GEN c = gel(q,i), s;
    3974          14 :     if (isintzero(gel(x,i))) continue;
    3975          14 :     s = gmul(gel(c,1), gel(x,1));
    3976          14 :     for (j=2; j<i; j++) s = gadd(s, gmul(gel(c,j),gel(x,j)));
    3977          14 :     s = gadd(gshift(s,1), gmul(gel(c,i),gel(x,i)));
    3978          14 :     z = gadd(z, gmul(gel(x,i), s));
    3979             :   }
    3980           7 :   return gerepileupto(av,z);
    3981             : }
    3982             : GEN
    3983          56 : qfnorm(GEN x, GEN q)
    3984             : {
    3985          56 :   if (!q) switch(typ(x))
    3986             :   {
    3987           7 :     case t_VEC: case t_COL: return RgV_dotsquare(x);
    3988           7 :     case t_MAT: return gram_matrix(x);
    3989           7 :     default: pari_err_TYPE("qfnorm",x);
    3990             :   }
    3991          35 :   if (typ(q) != t_MAT) pari_err_TYPE("qfnorm",q);
    3992          28 :   switch(typ(x))
    3993             :   {
    3994          21 :     case t_VEC: case t_COL: break;
    3995           7 :     case t_MAT: return qf_apply_RgM(q, x);
    3996           0 :     default: pari_err_TYPE("qfnorm",x);
    3997             :   }
    3998          21 :   return qfeval(q,x);
    3999             : }
    4000             : /* assume q is a real symetric matrix, q(x,y) using n^2+n mul */
    4001             : GEN
    4002          21 : qfevalb(GEN q, GEN x, GEN y)
    4003             : {
    4004          21 :   pari_sp av = avma;
    4005          21 :   long l = lg(q);
    4006          21 :   if (lg(x) != l || lg(y) != l) pari_err_DIM("qfevalb");
    4007          14 :   return gerepileupto(av, RgV_dotproduct(RgV_RgM_mul(x,q), y));
    4008             : }
    4009             : GEN
    4010          42 : qfbil(GEN x, GEN y, GEN q)
    4011             : {
    4012          42 :   if (!is_vec_t(typ(x))) pari_err_TYPE("qfbil",x);
    4013          35 :   if (!is_vec_t(typ(y))) pari_err_TYPE("qfbil",y);
    4014          35 :   if (!q) {
    4015          14 :     if (lg(x) != lg(y)) pari_err_DIM("qfbil");
    4016           7 :     return RgV_dotproduct(x,y);
    4017             :   }
    4018          21 :   if (typ(q) != t_MAT) pari_err_TYPE("qfbil",q);
    4019          21 :   return qfevalb(q,x,y);
    4020             : }
    4021             : 
    4022             : /* q a hermitian complex matrix, x a RgV */
    4023             : GEN
    4024           0 : hqfeval(GEN q, GEN x)
    4025             : {
    4026           0 :   pari_sp av = avma;
    4027           0 :   long i, j, l = lg(q);
    4028             :   GEN z, xc;
    4029             : 
    4030           0 :   if (lg(x) != l) pari_err_DIM("hqfeval");
    4031           0 :   if (l==1) return gen_0;
    4032           0 :   if (lgcols(q) != l) pari_err_DIM("hqfeval");
    4033           0 :   if (l == 2) return gerepileupto(av, gmul(gcoeff(q,1,1), gnorm(gel(x,1))));
    4034             :   /* l = lg(x) = lg(q) > 2 */
    4035           0 :   xc = gconj(x);
    4036           0 :   z = mulreal(gcoeff(q,2,1), gmul(gel(x,2),gel(xc,1)));
    4037           0 :   for (i=3;i<l;i++)
    4038           0 :     for (j=1;j<i;j++)
    4039           0 :       z = gadd(z, mulreal(gcoeff(q,i,j), gmul(gel(x,i),gel(xc,j))));
    4040           0 :   z = gshift(z,1);
    4041           0 :   for (i=1;i<l;i++) z = gadd(z, gmul(gcoeff(q,i,i), gnorm(gel(x,i))));
    4042           0 :   return gerepileupto(av,z);
    4043             : }
    4044             : 
    4045             : static void
    4046      145712 : init_qf_apply(GEN q, GEN M, long *l)
    4047             : {
    4048      145712 :   long k = lg(M);
    4049      145712 :   *l = lg(q);
    4050      145712 :   if (*l == 1) { if (k == 1) return; }
    4051      145705 :   else         { if (k != 1 && lgcols(M) == *l) return; }
    4052           0 :   pari_err_DIM("qf_apply_RgM");
    4053             : }
    4054             : /* Return X = M'.q.M, assuming q is a symetric matrix and M is a
    4055             :  * matrix of compatible dimensions. X_ij are X_ji identical, not copies */
    4056             : GEN
    4057         497 : qf_apply_RgM(GEN q, GEN M)
    4058             : {
    4059         497 :   pari_sp av = avma;
    4060         497 :   long l; init_qf_apply(q, M, &l); if (l == 1) return cgetg(1, t_MAT);
    4061         497 :   return gerepileupto(av, RgM_transmultosym(M, RgM_mul(q, M)));
    4062             : }
    4063             : GEN
    4064      145215 : qf_apply_ZM(GEN q, GEN M)
    4065             : {
    4066      145215 :   pari_sp av = avma;
    4067      145215 :   long l; init_qf_apply(q, M, &l); if (l == 1) return cgetg(1, t_MAT);
    4068      145208 :   return gerepileupto(av, ZM_transmultosym(M, ZM_mul(q, M)));
    4069             : }
    4070             : 
    4071             : GEN
    4072      678865 : poleval(GEN x, GEN y)
    4073             : {
    4074      678865 :   long i, j, imin, tx = typ(x);
    4075      678865 :   pari_sp av0 = avma, av;
    4076             :   GEN p1, p2, r, s;
    4077             : 
    4078      678865 :   if (is_scalar_t(tx)) return gcopy(x);
    4079      676401 :   switch(tx)
    4080             :   {
    4081             :     case t_POL:
    4082      672572 :       i = lg(x)-1; imin = 2; break;
    4083             : 
    4084             :     case t_RFRAC:
    4085        3619 :       p1 = poleval(gel(x,1),y);
    4086        3619 :       p2 = poleval(gel(x,2),y);
    4087        3619 :       return gerepileupto(av0, gdiv(p1,p2));
    4088             : 
    4089             :     case t_VEC: case t_COL:
    4090         210 :       i = lg(x)-1; imin = 1; break;
    4091           0 :     default: pari_err_TYPE("poleval",x);
    4092           0 :       return NULL; /* not reached */
    4093             :   }
    4094      672782 :   if (i<=imin)
    4095      117429 :     return (i==imin)? gcopy(gel(x,imin)): gen_0;
    4096             : 
    4097      555353 :   p1 = gel(x,i); i--;
    4098      555353 :   if (typ(y)!=t_COMPLEX)
    4099             :   {
    4100             : #if 0 /* standard Horner's rule */
    4101             :     for ( ; i>=imin; i--)
    4102             :       p1 = gadd(gmul(p1,y),gel(x,i));
    4103             : #endif
    4104             :     /* specific attention to sparse polynomials */
    4105    11056455 :     for ( ; i>=imin; i=j-1)
    4106             :     {
    4107    11516037 :       for (j=i; isexactzero(gel(x,j)); j--)
    4108      980847 :         if (j==imin)
    4109             :         {
    4110       70567 :           if (i!=j) y = gpowgs(y, i-j+1);
    4111       70567 :           return gerepileupto(av0, gmul(p1,y));
    4112             :         }
    4113    10535190 :       r = (i==j)? y: gpowgs(y, i-j+1);
    4114    10535190 :       p1 = gadd(gmul(p1,r), gel(x,j));
    4115    10535190 :       if (gc_needed(av0,2))
    4116             :       {
    4117          69 :         if (DEBUGMEM>1) pari_warn(warnmem,"poleval: i = %ld",i);
    4118          69 :         p1 = gerepileupto(av0, p1);
    4119             :       }
    4120             :     }
    4121      450698 :     return gerepileupto(av0,p1);
    4122             :   }
    4123             : 
    4124       34088 :   p2 = gel(x,i); i--; r = gtrace(y); s = gneg_i(gnorm(y));
    4125       34088 :   av = avma;
    4126     3247939 :   for ( ; i>=imin; i--)
    4127             :   {
    4128     3213851 :     GEN p3 = gadd(p2, gmul(r, p1));
    4129     3213851 :     p2 = gadd(gel(x,i), gmul(s, p1)); p1 = p3;
    4130     3213851 :     if (gc_needed(av0,2))
    4131             :     {
    4132           0 :       if (DEBUGMEM>1) pari_warn(warnmem,"poleval: i = %ld",i);
    4133           0 :       gerepileall(av, 2, &p1, &p2);
    4134             :     }
    4135             :   }
    4136       34088 :   return gerepileupto(av0, gadd(p2, gmul(y,p1)));
    4137             : }
    4138             : 
    4139             : /* Evaluate a polynomial using Horner. Unstable!
    4140             :  * If ui != NULL, ui = 1/u, evaluate P(1/u)*u^(deg P): useful for |u|>1 */
    4141             : GEN
    4142      277599 : RgX_cxeval(GEN T, GEN u, GEN ui)
    4143             : {
    4144      277599 :   pari_sp ltop = avma;
    4145             :   GEN S;
    4146      277599 :   long n, lim = lg(T)-1;
    4147      277599 :   if (lim == 1) return gen_0;
    4148      277599 :   if (lim == 2) return gcopy(gel(T,2));
    4149      277599 :   if (!ui)
    4150             :   {
    4151      232859 :     n = lim; S = gel(T,n);
    4152      232859 :     for (n--; n >= 2; n--) S = gadd(gmul(u,S), gel(T,n));
    4153             :   }
    4154             :   else
    4155             :   {
    4156       44740 :     n = 2; S = gel(T,2);
    4157       44740 :     for (n++; n <= lim; n++) S = gadd(gmul(ui,S), gel(T,n));
    4158       44740 :     S = gmul(gpowgs(u, lim-2), S);
    4159             :   }
    4160      277599 :   return gerepileupto(ltop, S);
    4161             : }

Generated by: LCOV version 1.11