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 19053-42ab05e) Lines: 2050 2213 92.6 %
Date: 2016-06-29 Functions: 201 209 96.2 %
Legend: Lines: hit not hit | Branches: + taken - not taken # not executed Branches: 1573 1960 80.3 %

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

Generated by: LCOV version 1.9