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 to exceed 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 - gen2.c (source / functions) Hit Total Coverage
Test: PARI/GP v2.12.1 lcov report (development 24961-b01324313d) Lines: 1343 1524 88.1 %
Date: 2020-01-21 05:55:55 Functions: 141 151 93.4 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : /* Copyright (C) 2000  The PARI group.
       2             : 
       3             : This file is part of the PARI/GP package.
       4             : 
       5             : PARI/GP is free software; you can redistribute it and/or modify it under the
       6             : terms of the GNU General Public License as published by the Free Software
       7             : Foundation. It is distributed in the hope that it will be useful, but WITHOUT
       8             : ANY WARRANTY WHATSOEVER.
       9             : 
      10             : Check the License for details. You should have received a copy of it, along
      11             : with the package; see the file 'COPYING'. If not, write to the Free Software
      12             : Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. */
      13             : 
      14             : /********************************************************************/
      15             : /**                                                                **/
      16             : /**                      GENERIC OPERATIONS                        **/
      17             : /**                        (second part)                           **/
      18             : /**                                                                **/
      19             : /********************************************************************/
      20             : #include "pari.h"
      21             : #include "paripriv.h"
      22             : 
      23             : /*********************************************************************/
      24             : /**                                                                 **/
      25             : /**                MAP FUNCTIONS WITH GIVEN PROTOTYPES              **/
      26             : /**                                                                 **/
      27             : /*********************************************************************/
      28             : GEN
      29         140 : map_proto_G(GEN (*f)(GEN), GEN x)
      30             : {
      31         140 :   if (is_matvec_t(typ(x)))
      32             :   {
      33             :     long lx, i;
      34           0 :     GEN y = cgetg_copy(x, &lx);
      35           0 :     for (i=1; i<lx; i++) gel(y,i) = map_proto_G(f, gel(x,i));
      36           0 :     return y;
      37             :   }
      38         140 :   return f(x);
      39             : }
      40             : 
      41             : GEN
      42     1782006 : map_proto_lG(long (*f)(GEN), GEN x)
      43             : {
      44     1782006 :   if (is_matvec_t(typ(x)))
      45             :   {
      46             :     long lx, i;
      47          28 :     GEN y = cgetg_copy(x, &lx);
      48          28 :     for (i=1; i<lx; i++) gel(y,i) = map_proto_lG(f, gel(x,i));
      49          28 :     return y;
      50             :   }
      51     1811193 :   return stoi(f(x));
      52             : }
      53             : 
      54             : GEN
      55         126 : map_proto_lGL(long (*f)(GEN,long), GEN x, long y)
      56             : {
      57         126 :   if (is_matvec_t(typ(x)))
      58             :   {
      59             :     long l, i;
      60           7 :     GEN t = cgetg_copy(x, &l);
      61           7 :     for (i=1; i<l; i++) gel(t,i) = map_proto_lGL(f,gel(x,i),y);
      62           7 :     return t;
      63             :   }
      64         119 :   return stoi(f(x,y));
      65             : }
      66             : 
      67             : static GEN
      68      646302 : _domul(void *data, GEN x, GEN y)
      69             : {
      70      646302 :   GEN (*mul)(GEN,GEN)=(GEN (*)(GEN,GEN)) data;
      71      646302 :   return mul(x,y);
      72             : }
      73             : 
      74             : GEN
      75      586528 : gassoc_proto(GEN (*f)(GEN,GEN), GEN x, GEN y)
      76             : {
      77      586528 :   if (!y)
      78             :   {
      79      586528 :     pari_sp av = avma;
      80      586528 :     switch(typ(x))
      81             :     {
      82             :       case t_LIST:
      83          21 :         x = list_data(x); if (!x) return gen_1;
      84             :       case t_VEC:
      85      586514 :       case t_COL: break;
      86           7 :       default: pari_err_TYPE("association",x);
      87             :     }
      88      586514 :     return gerepileupto(av, gen_product(x, (void *)f, _domul));
      89             : 
      90             :   }
      91           0 :   return f(x,y);
      92             : }
      93             : /*******************************************************************/
      94             : /*                                                                 */
      95             : /*                    CREATION OF A P-ADIC GEN                     */
      96             : /*                                                                 */
      97             : /*******************************************************************/
      98             : GEN
      99     6218629 : cgetp(GEN x)
     100             : {
     101     6218629 :   GEN y = cgetg(5,t_PADIC);
     102     6218636 :   y[1] = (x[1]&PRECPBITS) | _evalvalp(0);
     103     6218636 :   gel(y,2) = icopy(gel(x,2));
     104     6218643 :   gel(y,3) = icopy(gel(x,3));
     105     6218650 :   gel(y,4) = cgeti(lgefint(gel(x,3))); return y;
     106             : }
     107             : 
     108             : /*******************************************************************/
     109             : /*                                                                 */
     110             : /*                            SIZES                                */
     111             : /*                                                                 */
     112             : /*******************************************************************/
     113             : 
     114             : long
     115     4986025 : glength(GEN x)
     116             : {
     117     4986025 :   long tx = typ(x);
     118     4986025 :   switch(tx)
     119             :   {
     120          84 :     case t_INT:  return lgefint(x)-2;
     121             :     case t_LIST: {
     122          21 :       GEN L = list_data(x);
     123          21 :       return L? lg(L)-1: 0;
     124             :     }
     125          14 :     case t_REAL: return signe(x)? lg(x)-2: 0;
     126          21 :     case t_STR:  return strlen( GSTR(x) );
     127          91 :     case t_VECSMALL: return lg(x)-1;
     128             :   }
     129     4985794 :   return lg(x) - lontyp[tx];
     130             : }
     131             : 
     132             : GEN
     133         133 : matsize(GEN x)
     134             : {
     135         133 :   long L = lg(x) - 1;
     136         133 :   switch(typ(x))
     137             :   {
     138           7 :     case t_VEC: return mkvec2s(1, L);
     139           7 :     case t_COL: return mkvec2s(L, 1);
     140         112 :     case t_MAT: return mkvec2s(L? nbrows(x): 0, L);
     141             :   }
     142           7 :   pari_err_TYPE("matsize",x);
     143             :   return NULL; /* LCOV_EXCL_LINE */
     144             : }
     145             : 
     146             : /*******************************************************************/
     147             : /*                                                                 */
     148             : /*                 CONVERSION GEN --> long                         */
     149             : /*                                                                 */
     150             : /*******************************************************************/
     151             : 
     152             : long
     153          77 : gtolong(GEN x)
     154             : {
     155          77 :   switch(typ(x))
     156             :   {
     157             :     case t_INT:
     158          42 :       return itos(x);
     159             :     case t_REAL:
     160           7 :       return (long)(rtodbl(x) + 0.5);
     161             :     case t_FRAC:
     162           7 :     { pari_sp av = avma; return gc_long(av, itos(ground(x))); }
     163             :     case t_COMPLEX:
     164           7 :       if (gequal0(gel(x,2))) return gtolong(gel(x,1)); break;
     165             :     case t_QUAD:
     166           7 :       if (gequal0(gel(x,3))) return gtolong(gel(x,2)); break;
     167             :   }
     168           7 :   pari_err_TYPE("gtolong",x);
     169             :   return 0; /* LCOV_EXCL_LINE */
     170             : }
     171             : 
     172             : /*******************************************************************/
     173             : /*                                                                 */
     174             : /*                         COMPARISONS                             */
     175             : /*                                                                 */
     176             : /*******************************************************************/
     177             : int
     178   211623891 : isexactzero(GEN g)
     179             : {
     180             :   long i, lx;
     181   211623891 :   switch (typ(g))
     182             :   {
     183             :     case t_INT:
     184   170891753 :       return !signe(g);
     185             :     case t_INTMOD:
     186     1058364 :       return !signe(gel(g,2));
     187             :     case t_COMPLEX:
     188     3224053 :       return isexactzero(gel(g,1)) && isexactzero(gel(g,2));
     189             :     case t_FFELT:
     190     8107250 :       return FF_equal0(g);
     191             :     case t_QUAD:
     192         504 :       return isexactzero(gel(g,2)) && isexactzero(gel(g,3));
     193             :     case t_POLMOD:
     194      700281 :       return isexactzero(gel(g,2));
     195             :     case t_POL:
     196    11533003 :       lx = lg(g); /* cater for Mod(0,2)*x^0 */
     197    11533003 :       return lx == 2 || (lx == 3 && isexactzero(gel(g,2)));
     198             :     case t_RFRAC:
     199      461143 :       return isexactzero(gel(g,1)); /* may occur: Mod(0,2)/x */
     200             :     case t_VEC: case t_COL: case t_MAT:
     201       15036 :       for (i=lg(g)-1; i; i--)
     202       14896 :         if (!isexactzero(gel(g,i))) return 0;
     203         140 :       return 1;
     204             :   }
     205    15632868 :   return 0;
     206             : }
     207             : GEN
     208    56346159 : gisexactzero(GEN g)
     209             : {
     210             :   long i, lx;
     211             :   GEN a, b;
     212    56346159 :   switch (typ(g))
     213             :   {
     214             :     case t_INT:
     215    16413293 :       return !signe(g)? g: NULL;
     216             :     case t_INTMOD:
     217    10419206 :       return !signe(gel(g,2))? g: NULL;
     218             :     case t_COMPLEX:
     219        2562 :       a = gisexactzero(gel(g,1)); if (!a) return NULL;
     220         602 :       b = gisexactzero(gel(g,2)); if (!b) return NULL;
     221           0 :       return ggcd(a,b);
     222             :     case t_FFELT:
     223       15232 :       return FF_equal0(g)? g: NULL;
     224             :     case t_QUAD:
     225         518 :       a = gisexactzero(gel(g,2)); if (!a) return NULL;
     226          77 :       b = gisexactzero(gel(g,3)); if (!b) return NULL;
     227           7 :       return ggcd(a,b);
     228             :     case t_POLMOD:
     229       35540 :       return gisexactzero(gel(g,2));
     230             :     case t_POL:
     231    28106720 :       lx = lg(g); /* cater for Mod(0,2)*x^0 */
     232    28106720 :       if (lx == 2) return gen_0;
     233    22774531 :       if (lx == 3) return gisexactzero(gel(g,2));
     234    19017520 :       return NULL;
     235             :     case t_RFRAC:
     236     1193940 :       return gisexactzero(gel(g,1)); /* may occur: Mod(0,2)/x */
     237             :     case t_VEC: case t_COL: case t_MAT:
     238           0 :       a = gen_0;
     239           0 :       for (i=lg(g)-1; i; i--)
     240             :       {
     241           0 :         b = gisexactzero(gel(g,i));
     242           0 :         if (!b) return NULL;
     243           0 :         a = ggcd(a, b);
     244             :       }
     245           0 :       return a;
     246             :   }
     247      159148 :   return NULL;
     248             : }
     249             : 
     250             : int
     251   253691602 : isrationalzero(GEN g)
     252             : {
     253             :   long i;
     254   253691602 :   switch (typ(g))
     255             :   {
     256             :     case t_INT:
     257   160267518 :       return !signe(g);
     258             :     case t_COMPLEX:
     259     9469900 :       return isintzero(gel(g,1)) && isintzero(gel(g,2));
     260             :     case t_QUAD:
     261        1449 :       return isintzero(gel(g,2)) && isintzero(gel(g,3));
     262             :     case t_POLMOD:
     263      891180 :       return isrationalzero(gel(g,2));
     264    21582890 :     case t_POL: return lg(g) == 2;
     265             :     case t_VEC: case t_COL: case t_MAT:
     266         420 :       for (i=lg(g)-1; i; i--)
     267         294 :         if (!isrationalzero(gel(g,i))) return 0;
     268         126 :       return 1;
     269             :   }
     270    61478539 :   return 0;
     271             : }
     272             : 
     273             : int
     274   709939801 : gequal0(GEN x)
     275             : {
     276   709939801 :   switch(typ(x))
     277             :   {
     278             :     case t_INT: case t_REAL: case t_POL: case t_SER:
     279   647324829 :       return !signe(x);
     280             : 
     281             :     case t_INTMOD:
     282     3498946 :       return !signe(gel(x,2));
     283             : 
     284             :     case t_FFELT:
     285      577072 :       return FF_equal0(x);
     286             : 
     287             :     case t_COMPLEX:
     288             :      /* is 0 iff norm(x) would be 0 (can happen with Re(x) and Im(x) != 0
     289             :       * only if Re(x) and Im(x) are of type t_REAL). See mp.c:addrr().
     290             :       */
     291    24658349 :       if (gequal0(gel(x,1)))
     292             :       {
     293     5299610 :         if (gequal0(gel(x,2))) return 1;
     294     5235517 :         if (typ(gel(x,1))!=t_REAL || typ(gel(x,2))!=t_REAL) return 0;
     295       75216 :         return (expo(gel(x,1))>=expo(gel(x,2)));
     296             :       }
     297    19361195 :       if (gequal0(gel(x,2)))
     298             :       {
     299      554986 :         if (typ(gel(x,1))!=t_REAL || typ(gel(x,2))!=t_REAL) return 0;
     300      530301 :         return (expo(gel(x,2))>=expo(gel(x,1)));
     301             :       }
     302    18809421 :       return 0;
     303             : 
     304             :     case t_PADIC:
     305      778979 :       return !signe(gel(x,4));
     306             : 
     307             :     case t_QUAD:
     308        1575 :       return gequal0(gel(x,2)) && gequal0(gel(x,3));
     309             : 
     310             :     case t_POLMOD:
     311     8531186 :       return gequal0(gel(x,2));
     312             : 
     313             :     case t_RFRAC:
     314     5852903 :       return gequal0(gel(x,1));
     315             : 
     316             :     case t_VEC: case t_COL: case t_MAT:
     317             :     {
     318             :       long i;
     319     6400558 :       for (i=lg(x)-1; i; i--)
     320     3411912 :         if (!gequal0(gel(x,i))) return 0;
     321     2988646 :       return 1;
     322             :     }
     323             :   }
     324    14504212 :   return 0;
     325             : }
     326             : 
     327             : /* x a t_POL or t_SER, considered as having valuation v; let X(t) = t^(-v) x(t)
     328             :  * return 1 (true) if coeff(X,i) = 0 for all i != 0 and test(coeff(X, 0))
     329             :  * is true. Return 0 (false) otherwise, or if x == 0 */
     330             : static int
     331    13570316 : is_monomial_test(GEN x, long v, int(*test)(GEN))
     332             : {
     333             :   long d, i, l;
     334    13570316 :   if (!signe(x)) return (typ(x) == t_SER && v <= 0);
     335    13501759 :   if (v > 0) return 0;
     336    13501745 :   l = lg(x); d = 2-v;
     337    13501745 :   if (l <= d) return 0;
     338             :   /* 2 <= d < l */
     339    13501745 :   if (!test(gel(x,d))) return 0;
     340     3948974 :   for (i = 2; i < d; i++)
     341          14 :     if (!gequal0(gel(x,i))) return 0;
     342     4579369 :   for (i = d+1; i < l; i++)
     343     2191378 :     if (!gequal0(gel(x,i))) return 0;
     344     2387991 :   return 1;
     345             : }
     346             : static int
     347        2135 : col_test(GEN x, int(*test)(GEN))
     348             : {
     349        2135 :   long i, l = lg(x);
     350        2135 :   if (l == 1 || !test(gel(x,1))) return 0;
     351          42 :   for (i = 2; i < l; i++)
     352          21 :     if (!gequal0(gel(x,i))) return 0;
     353          21 :   return 1;
     354             : }
     355             : static int
     356       16184 : mat_test(GEN x, int(*test)(GEN))
     357             : {
     358       16184 :   long i, j, l = lg(x);
     359       16184 :   if (l == 1) return 1;
     360       16170 :   if (l != lgcols(x)) return 0;
     361       51240 :   for (i = 1; i < l; i++)
     362      134078 :     for (j = 1; j < l; j++)
     363       99008 :       if (i == j) {
     364       35133 :         if (!test(gcoeff(x,i,i))) return 0;
     365             :       } else {
     366       63875 :         if (!gequal0(gcoeff(x,i,j))) return 0;
     367             :       }
     368       16107 :   return 1;
     369             : }
     370             : 
     371             : /* returns 1 whenever x = 1, and 0 otherwise */
     372             : int
     373   161585547 : gequal1(GEN x)
     374             : {
     375   161585547 :   switch(typ(x))
     376             :   {
     377             :     case t_INT:
     378   145226263 :       return equali1(x);
     379             : 
     380             :     case t_REAL:
     381             :     {
     382       67431 :       long s = signe(x);
     383       67431 :       if (!s) return expo(x) >= 0;
     384       67354 :       return s > 0 ? absrnz_equal1(x): 0;
     385             :     }
     386             :     case t_INTMOD:
     387      565219 :       return is_pm1(gel(x,2)) || is_pm1(gel(x,1));
     388             :     case t_POLMOD:
     389      319493 :       return gequal1(gel(x,2)) || gequal1(gel(x,1));
     390             : 
     391             :     case t_FFELT:
     392       15533 :       return FF_equal1(x);
     393             : 
     394             :     case t_FRAC:
     395      593904 :       return 0;
     396             : 
     397             :     case t_COMPLEX:
     398       19465 :       return gequal1(gel(x,1)) && gequal0(gel(x,2));
     399             : 
     400             :     case t_PADIC:
     401      157778 :       return !valp(x) && gequal1(gel(x,4));
     402             : 
     403             :     case t_QUAD:
     404          42 :       return gequal1(gel(x,2)) && gequal0(gel(x,3));
     405             : 
     406    13570043 :     case t_POL: return is_monomial_test(x, 0, &gequal1);
     407         161 :     case t_SER: return is_monomial_test(x, valp(x), &gequal1);
     408             : 
     409     1031952 :     case t_RFRAC: return gequal(gel(x,1), gel(x,2));
     410        2093 :     case t_COL: return col_test(x, &gequal1);
     411       16135 :     case t_MAT: return mat_test(x, &gequal1);
     412             :   }
     413          35 :   return 0;
     414             : }
     415             : 
     416             : /* returns 1 whenever the x = -1, 0 otherwise */
     417             : int
     418      130691 : gequalm1(GEN x)
     419             : {
     420             :   pari_sp av;
     421             :   GEN p1;
     422             : 
     423      130691 :   switch(typ(x))
     424             :   {
     425             :     case t_INT:
     426      127002 :       return equalim1(x);
     427             : 
     428             :     case t_REAL:
     429             :     {
     430        1365 :       long s = signe(x);
     431        1365 :       if (!s) return expo(x) >= 0;
     432        1365 :       return s < 0 ? absrnz_equal1(x): 0;
     433             :     }
     434             :     case t_INTMOD:
     435          21 :       av = avma; return gc_bool(av, equalii(addui(1,gel(x,2)), gel(x,1)));
     436             : 
     437             :     case t_FRAC:
     438          49 :       return 0;
     439             : 
     440             :     case t_FFELT:
     441          42 :       return FF_equalm1(x);
     442             : 
     443             :     case t_COMPLEX:
     444        1925 :       return gequalm1(gel(x,1)) && gequal0(gel(x,2));
     445             : 
     446             :     case t_QUAD:
     447           7 :       return gequalm1(gel(x,2)) && gequal0(gel(x,3));
     448             : 
     449             :     case t_PADIC:
     450           7 :       av = avma; return gc_bool(av, equalii(addui(1,gel(x,4)), gel(x,3)));
     451             : 
     452             :     case t_POLMOD:
     453          35 :       av = avma; p1 = gaddgs(gel(x,2), 1);
     454          35 :       return gc_bool(av, gequal0(p1) || gequal(p1,gel(x,1)));
     455             : 
     456          35 :     case t_POL: return is_monomial_test(x, 0, &gequalm1);
     457          77 :     case t_SER: return is_monomial_test(x, valp(x), &gequalm1);
     458             : 
     459             :     case t_RFRAC:
     460          21 :       av = avma; return gc_bool(av, gequal(gel(x,1), gneg_i(gel(x,2))));
     461          42 :     case t_COL: return col_test(x, &gequalm1);
     462          49 :     case t_MAT: return mat_test(x, &gequalm1);
     463             :   }
     464          14 :   return 0;
     465             : }
     466             : 
     467             : int
     468     2377563 : gequalX(GEN x) { return typ(x) == t_POL && lg(x) == 4
     469     2358989 :                       && isintzero(gel(x,2)) && isint1(gel(x,3)); }
     470             : 
     471             : static int
     472         476 : cmp_str(const char *x, const char *y)
     473             : {
     474         476 :   int f = strcmp(x, y);
     475             :   return f > 0? 1
     476         476 :               : f? -1: 0;
     477             : }
     478             : 
     479             : static int
     480    27764252 : cmp_universal_rec(GEN x, GEN y, long i0)
     481             : {
     482    27764252 :   long i, lx = lg(x), ly = lg(y);
     483    27764252 :   if (lx < ly) return -1;
     484    27761596 :   if (lx > ly) return 1;
     485    42476684 :   for (i = i0; i < lx; i++)
     486             :   {
     487    36271122 :     int f = cmp_universal(gel(x,i), gel(y,i));
     488    36271122 :     if (f) return f;
     489             :   }
     490     6205562 :   return 0;
     491             : }
     492             : /* Universal "meaningless" comparison function. Transitive, returns 0 iff
     493             :  * gidentical(x,y) */
     494             : int
     495    49867341 : cmp_universal(GEN x, GEN y)
     496             : {
     497    49867341 :   long lx, ly, i, tx = typ(x), ty = typ(y);
     498             : 
     499    49867341 :   if (tx < ty) return -1;
     500    49844660 :   if (ty < tx) return 1;
     501    49834052 :   switch(tx)
     502             :   {
     503    21132640 :     case t_INT: return cmpii(x,y);
     504         455 :     case t_STR: return cmp_str(GSTR(x),GSTR(y));
     505             :     case t_REAL:
     506             :     case t_VECSMALL:
     507      936621 :       lx = lg(x);
     508      936621 :       ly = lg(y);
     509      936621 :       if (lx < ly) return -1;
     510      888349 :       if (lx > ly) return 1;
     511     3593129 :       for (i = 1; i < lx; i++)
     512             :       {
     513     3483789 :         if (x[i] < y[i]) return -1;
     514     3114889 :         if (x[i] > y[i]) return 1;
     515             :       }
     516      109340 :       return 0;
     517             : 
     518             :     case t_POL:
     519             :     case t_SER:
     520             :     case t_FFELT:
     521             :     case t_CLOSURE:
     522      898218 :       if (x[1] < y[1]) return -1;
     523      898190 :       if (x[1] > y[1]) return 1;
     524      898134 :       return cmp_universal_rec(x, y, 2);
     525             : 
     526             :     case t_LIST:
     527             :       {
     528          35 :         long tx = list_typ(x), ty = list_typ(y);
     529             :         GEN vx, vy;
     530             :         pari_sp av;
     531          35 :         if (tx < ty) return -1;
     532          35 :         if (tx > ty) return 1;
     533          35 :         vx = list_data(x);
     534          35 :         vy = list_data(y);
     535          35 :         if (!vx) return vy? -1: 0;
     536          35 :         if (!vy) return 1;
     537          35 :         av = avma;
     538          35 :         if (tx == t_LIST_MAP)
     539             :         {
     540          14 :           vx = maptomat_shallow(x);
     541          14 :           vy = maptomat_shallow(y);
     542             :         }
     543          35 :         return gc_int(av, cmp_universal_rec(vx, vy, 1));
     544             :       }
     545             :     default:
     546    26866083 :       return cmp_universal_rec(x, y, lontyp[tx]);
     547             :   }
     548             : }
     549             : 
     550             : static int
     551       87934 : cmpfrac(GEN x, GEN y)
     552             : {
     553       87934 :   pari_sp av = avma;
     554       87934 :   GEN a = gel(x,1), b = gel(x,2);
     555       87934 :   GEN c = gel(y,1), d = gel(y,2);
     556       87934 :   return gc_bool(av, cmpii(mulii(a, d), mulii(b, c)));
     557             : }
     558             : static int
     559        7574 : cmpifrac(GEN a, GEN y)
     560             : {
     561        7574 :   pari_sp av = avma;
     562        7574 :   GEN c = gel(y,1), d = gel(y,2);
     563        7574 :   return gc_int(av, cmpii(mulii(a, d), c));
     564             : }
     565             : static int
     566       65135 : cmprfrac(GEN a, GEN y)
     567             : {
     568       65135 :   pari_sp av = avma;
     569       65135 :   GEN c = gel(y,1), d = gel(y,2);
     570       65135 :   return gc_int(av, cmpri(mulri(a, d), c));
     571             : }
     572             : static int
     573         161 : cmpgen(GEN x, GEN y)
     574             : {
     575         161 :   pari_sp av = avma;
     576         161 :   return gc_int(av, gsigne(gsub(x,y)));
     577             : }
     578             : 
     579             : /* returns the sign of x - y when it makes sense. 0 otherwise */
     580             : int
     581   154831552 : gcmp(GEN x, GEN y)
     582             : {
     583   154831552 :   long tx = typ(x), ty = typ(y);
     584             : 
     585   154831552 :   if (tx == ty) /* generic case */
     586   154367005 :     switch(tx)
     587             :     {
     588    80022359 :       case t_INT:  return cmpii(x, y);
     589    74248436 :       case t_REAL: return cmprr(x, y);
     590       87934 :       case t_FRAC: return cmpfrac(x, y);
     591          70 :       case t_QUAD: return cmpgen(x, y);
     592          21 :       case t_STR:  return cmp_str(GSTR(x), GSTR(y));
     593             :       case t_INFINITY:
     594             :       {
     595       15576 :         long sx = inf_get_sign(x), sy = inf_get_sign(y);
     596       15576 :         if (sx < sy) return -1;
     597          21 :         if (sx > sy) return 1;
     598          14 :         return 0;
     599             :       }
     600             :     }
     601      457156 :   if (ty == t_INFINITY) return -inf_get_sign(y);
     602      409512 :   switch(tx)
     603             :   {
     604             :     case t_INT:
     605       28829 :       switch(ty)
     606             :       {
     607       25049 :         case t_REAL: return cmpir(x, y);
     608        3766 :         case t_FRAC: return cmpifrac(x, y);
     609           7 :         case t_QUAD: return cmpgen(x, y);
     610             :       }
     611           7 :       break;
     612             :     case t_REAL:
     613      321335 :       switch(ty)
     614             :       {
     615      280028 :         case t_INT:  return cmpri(x, y);
     616       41286 :         case t_FRAC: return cmprfrac(x, y);
     617          14 :         case t_QUAD: return cmpgen(x, y);
     618             :       }
     619           7 :       break;
     620             :     case t_FRAC:
     621       27671 :       switch(ty)
     622             :       {
     623        3808 :         case t_INT:  return -cmpifrac(y, x);
     624       23849 :         case t_REAL: return -cmprfrac(y, x);
     625           7 :         case t_QUAD: return cmpgen(x, y);
     626             :       }
     627           7 :       break;
     628             :     case t_QUAD:
     629          63 :       return cmpgen(x, y);
     630       31607 :     case t_INFINITY: return inf_get_sign(x);
     631             :   }
     632          28 :   pari_err_TYPE2("comparison",x,y);
     633             :   return 0;/*LCOV_EXCL_LINE*/
     634             : }
     635             : 
     636             : int
     637       74150 : gcmpsg(long s, GEN y)
     638             : {
     639       74150 :   switch(typ(y))
     640             :   {
     641        9324 :     case t_INT:  return cmpsi(s,y);
     642       59037 :     case t_REAL: return cmpsr(s,y);
     643             :     case t_FRAC: {
     644        5789 :       pari_sp av = avma;
     645        5789 :       return gc_int(av, cmpii(mulsi(s,gel(y,2)), gel(y,1)));
     646             :     }
     647             :     case t_QUAD: {
     648           0 :       pari_sp av = avma;
     649           0 :       return gc_int(av, gsigne(gsubsg(s, y)));
     650             :     }
     651           0 :     case t_INFINITY: return -inf_get_sign(y);
     652             :   }
     653           0 :   pari_err_TYPE2("comparison",stoi(s),y);
     654             :   return 0; /* LCOV_EXCL_LINE */
     655             : }
     656             : 
     657             : static long
     658     6260359 : roughtype(GEN x)
     659             : {
     660     6260359 :   switch(typ(x))
     661             :   {
     662        2100 :     case t_MAT: return t_MAT;
     663       14812 :     case t_VEC: case t_COL: return t_VEC;
     664     6198136 :     case t_VECSMALL: return t_VECSMALL;
     665       45311 :     default: return t_INT;
     666             :   }
     667             : }
     668             : 
     669             : static int lexcmpsg(long x, GEN y);
     670          42 : static int lexcmpgs(GEN x, long y) { return -lexcmpsg(y,x); }
     671             : /* lexcmp(stoi(x),y), y t_VEC/t_COL/t_MAT */
     672             : static int
     673          21 : lexcmp_s_matvec(long x, GEN y)
     674             : {
     675             :   int fl;
     676          21 :   if (lg(y)==1) return 1;
     677          14 :   fl = lexcmpsg(x,gel(y,1));
     678          14 :   if (fl) return fl;
     679           7 :   return -1;
     680             : }
     681             : /* x a scalar, y a t_VEC/t_COL/t_MAT */
     682             : static int
     683         357 : lexcmp_scal_matvec(GEN x, GEN y)
     684             : {
     685             :   int fl;
     686         357 :   if (lg(y)==1) return 1;
     687         357 :   fl = lexcmp(x,gel(y,1));
     688         357 :   if (fl) return fl;
     689           7 :   return -1;
     690             : }
     691             : /* x a scalar, y a t_VECSMALL */
     692             : static int
     693          42 : lexcmp_scal_vecsmall(GEN x, GEN y)
     694             : {
     695             :   int fl;
     696          42 :   if (lg(y)==1) return 1;
     697          42 :   fl = lexcmpgs(x, y[1]);
     698          42 :   if (fl) return fl;
     699           0 :   return -1;
     700             : }
     701             : 
     702             : /* tx = ty = t_MAT, or x and y are both vect_t */
     703             : static int
     704        8190 : lexcmp_similar(GEN x, GEN y)
     705             : {
     706        8190 :   long i, lx = lg(x), ly = lg(y), l = minss(lx,ly);
     707       15813 :   for (i=1; i<l; i++)
     708             :   {
     709       14259 :     int fl = lexcmp(gel(x,i),gel(y,i));
     710       14259 :     if (fl) return fl;
     711             :   }
     712        1554 :   if (lx == ly) return 0;
     713          35 :   return (lx < ly)? -1 : 1;
     714             : }
     715             : /* x a t_VECSMALL, y a t_VEC/t_COL ~ lexcmp_similar */
     716             : static int
     717         154 : lexcmp_vecsmall_vec(GEN x, GEN y)
     718             : {
     719         154 :   long i, lx = lg(x), ly = lg(y), l = minss(lx,ly);
     720         343 :   for (i=1; i<l; i++)
     721             :   {
     722         287 :     int fl = lexcmpsg(x[i], gel(y,i));
     723         287 :     if (fl) return fl;
     724             :   }
     725          56 :   if (lx == ly) return 0;
     726          21 :   return (lx < ly)? -1 : 1;
     727             : }
     728             : 
     729             : /* x t_VEC/t_COL, y t_MAT */
     730             : static int
     731          98 : lexcmp_vec_mat(GEN x, GEN y)
     732             : {
     733             :   int fl;
     734          98 :   if (lg(x)==1) return -1;
     735          98 :   if (lg(y)==1) return 1;
     736          98 :   fl = lexcmp_similar(x,gel(y,1));
     737          98 :   if (fl) return fl;
     738           7 :   return -1;
     739             : }
     740             : /* x t_VECSMALl, y t_MAT ~ lexcmp_vec_mat */
     741             : static int
     742          42 : lexcmp_vecsmall_mat(GEN x, GEN y)
     743             : {
     744             :   int fl;
     745          42 :   if (lg(x)==1) return -1;
     746          42 :   if (lg(y)==1) return 1;
     747          42 :   fl = lexcmp_vecsmall_vec(x, gel(y,1));
     748          42 :   if (fl) return fl;
     749           0 :   return -1;
     750             : }
     751             : 
     752             : /* x a t_VECSMALL, not y */
     753             : static int
     754         196 : lexcmp_vecsmall_other(GEN x, GEN y, long ty)
     755             : {
     756         196 :   switch(ty)
     757             :   {
     758          42 :     case t_MAT: return lexcmp_vecsmall_mat(x, y);
     759         112 :     case t_VEC: return lexcmp_vecsmall_vec(x, y);
     760          42 :     default: return -lexcmp_scal_vecsmall(y, x); /*y scalar*/
     761             :   }
     762             : }
     763             : 
     764             : /* lexcmp(stoi(s), y) */
     765             : static int
     766         343 : lexcmpsg(long x, GEN y)
     767             : {
     768         343 :   switch(roughtype(y))
     769             :   {
     770             :     case t_MAT:
     771             :     case t_VEC:
     772          21 :       return lexcmp_s_matvec(x,y);
     773             :     case t_VECSMALL: /* ~ lexcmp_scal_matvec */
     774          14 :       if (lg(y)==1) return 1;
     775           7 :       return (x > y[1])? 1: -1;
     776         308 :     default: return gcmpsg(x,y);
     777             :   }
     778             : }
     779             : 
     780             : /* as gcmp for vector/matrices, using lexicographic ordering on components */
     781             : static int
     782     3130008 : lexcmp_i(GEN x, GEN y)
     783             : {
     784     3130008 :   const long tx = roughtype(x), ty = roughtype(y);
     785     3130008 :   if (tx == ty)
     786     3129357 :     switch(tx)
     787             :     {
     788             :       case t_MAT:
     789             :       case t_VEC:
     790        8092 :         return lexcmp_similar(x,y);
     791             :       case t_VECSMALL:
     792     3098963 :         return vecsmall_lexcmp(x,y);
     793             :       default:
     794       22302 :         return gcmp(x,y);
     795             :     }
     796         651 :   if (tx == t_VECSMALL) return  lexcmp_vecsmall_other(x,y,ty);
     797         518 :   if (ty == t_VECSMALL) return -lexcmp_vecsmall_other(y,x,tx);
     798             : 
     799         455 :   if (tx == t_INT) return  lexcmp_scal_matvec(x,y); /*scalar*/
     800         203 :   if (ty == t_INT) return -lexcmp_scal_matvec(y,x);
     801             : 
     802          98 :   if (ty==t_MAT) return  lexcmp_vec_mat(x,y);
     803          42 :   /*tx==t_MAT*/  return -lexcmp_vec_mat(y,x);
     804             : }
     805             : int
     806     3130008 : lexcmp(GEN x, GEN y)
     807             : {
     808     3130008 :   pari_sp av = avma;
     809     3130008 :   if (typ(x) == t_COMPLEX)
     810             :   {
     811          63 :     x = mkvec2(gel(x,1), gel(x,2));
     812          63 :     if (typ(y) == t_COMPLEX) y = mkvec2(gel(y,1), gel(y,2));
     813          49 :     else y = mkvec2(y, gen_0);
     814             :   }
     815     3129945 :   else if (typ(y) == t_COMPLEX)
     816             :   {
     817          63 :     x = mkvec2(x, gen_0);
     818          63 :     y = mkvec2(gel(y,1), gel(y,2));
     819             :   }
     820     3130008 :   return gc_int(av, lexcmp_i(x, y));
     821             : }
     822             : 
     823             : /*****************************************************************/
     824             : /*                                                               */
     825             : /*                          EQUALITY                             */
     826             : /*                returns 1 if x == y, 0 otherwise               */
     827             : /*                                                               */
     828             : /*****************************************************************/
     829             : /* x,y t_POL */
     830             : static int
     831     3435584 : polidentical(GEN x, GEN y)
     832             : {
     833             :   long lx;
     834     3435584 :   if (x[1] != y[1]) return 0;
     835     3435486 :   lx = lg(x); if (lg(y) != lg(x)) return 0;
     836     3435416 :   for (lx--; lx >= 2; lx--) if (!gidentical(gel(x,lx), gel(y,lx))) return 0;
     837     3435402 :   return 1;
     838             : }
     839             : /* x,y t_SER */
     840             : static int
     841          14 : seridentical(GEN x, GEN y) { return polidentical(x,y); }
     842             : /* typ(x) = typ(y) = t_VEC/COL/MAT */
     843             : static int
     844     4093668 : vecidentical(GEN x, GEN y)
     845             : {
     846             :   long i;
     847     4093668 :   if ((x[0] ^ y[0]) & (TYPBITS|LGBITS)) return 0;
     848    10902258 :   for (i = lg(x)-1; i; i--)
     849     7549706 :     if (! gidentical(gel(x,i),gel(y,i)) ) return 0;
     850     3352552 :   return 1;
     851             : }
     852             : static int
     853          21 : identicalrr(GEN x, GEN y)
     854             : {
     855          21 :   long i, lx = lg(x);
     856          21 :   if (lg(y) != lx) return 0;
     857          14 :   if (x[1] != y[1]) return 0;
     858           7 :   i=2; while (i<lx && x[i]==y[i]) i++;
     859           7 :   return (i == lx);
     860             : }
     861             : 
     862             : static int
     863          35 : closure_identical(GEN x, GEN y)
     864             : {
     865          35 :   if (lg(x)!=lg(y) || x[1]!=y[1]) return 0;
     866          21 :   if (!gidentical(gel(x,2),gel(y,2)) || !gidentical(gel(x,3),gel(y,3))
     867           7 :    || !gidentical(gel(x,4),gel(y,4))) return 0;
     868           7 :   if (lg(x)<8) return 1;
     869           0 :   return gidentical(gel(x,7),gel(y,7));
     870             : }
     871             : 
     872             : static int
     873         336 : list_cmp(GEN x, GEN y, int cmp(GEN x, GEN y))
     874             : {
     875         336 :   int t = list_typ(x);
     876             :   GEN vx, vy;
     877         336 :   if (list_typ(y)!=t) return 0;
     878         336 :   vx = list_data(x);
     879         336 :   vy = list_data(y);
     880         336 :   if (!vx) return vy? 0: 1;
     881         322 :   if (!vy) return 0;
     882         308 :   if (lg(vx) != lg(vy)) return 0;
     883         301 :   switch (t)
     884             :   {
     885             :   case t_LIST_MAP:
     886             :     {
     887         280 :       pari_sp av = avma;
     888         280 :       GEN mx  = maptomat_shallow(x), my = maptomat_shallow(y);
     889         280 :       int ret = gidentical(gel(mx, 1), gel(my, 1)) && cmp(gel(mx, 2), gel(my, 2));
     890         280 :       return gc_bool(av, ret);
     891             :     }
     892             :   default:
     893          21 :     return cmp(vx, vy);
     894             :   }
     895             : }
     896             : 
     897             : int
     898    56528887 : gidentical(GEN x, GEN y)
     899             : {
     900             :   long tx;
     901             : 
     902    56528887 :   if (x == y) return 1;
     903    55438315 :   tx = typ(x); if (typ(y) != tx) return 0;
     904    55433872 :   switch(tx)
     905             :   {
     906             :     case t_INT:
     907    16149975 :       return equalii(x,y);
     908             : 
     909             :     case t_REAL:
     910          14 :       return identicalrr(x,y);
     911             : 
     912             :     case t_FRAC: case t_INTMOD:
     913       19711 :       return equalii(gel(x,2), gel(y,2)) && equalii(gel(x,1), gel(y,1));
     914             : 
     915             :     case t_COMPLEX:
     916          14 :       return gidentical(gel(x,2),gel(y,2)) && gidentical(gel(x,1),gel(y,1));
     917             :     case t_PADIC:
     918          14 :       return valp(x) == valp(y)
     919          14 :         && equalii(gel(x,2),gel(y,2))
     920          14 :         && equalii(gel(x,3),gel(y,3))
     921          28 :         && equalii(gel(x,4),gel(y,4));
     922             :     case t_POLMOD:
     923        1113 :       return gidentical(gel(x,2),gel(y,2)) && polidentical(gel(x,1),gel(y,1));
     924             :     case t_POL:
     925     3434877 :       return polidentical(x,y);
     926             :     case t_SER:
     927          14 :       return seridentical(x,y);
     928             :     case t_FFELT:
     929          14 :       return FF_equal(x,y);
     930             : 
     931             :     case t_QFR:
     932           7 :           if (!identicalrr(gel(x,4),gel(y,4))) return 0; /* fall through */
     933             :     case t_QFI:
     934     2385395 :       return equalii(gel(x,1),gel(y,1))
     935     2385388 :           && equalii(gel(x,2),gel(y,2))
     936     4770776 :           && equalii(gel(x,3),gel(y,3));
     937             : 
     938             :     case t_QUAD:
     939          14 :       return ZX_equal(gel(x,1),gel(y,1))
     940           7 :           && gidentical(gel(x,2),gel(y,2))
     941          14 :           && gidentical(gel(x,3),gel(y,3));
     942             : 
     943             :     case t_RFRAC:
     944           7 :       return gidentical(gel(x,1),gel(y,1)) && gidentical(gel(x,2),gel(y,2));
     945             : 
     946             :     case t_STR:
     947          35 :       return !strcmp(GSTR(x),GSTR(y));
     948             :     case t_VEC: case t_COL: case t_MAT:
     949     4093668 :       return vecidentical(x,y);
     950             :     case t_VECSMALL:
     951    29348790 :       return zv_equal(x,y);
     952             :     case t_CLOSURE:
     953          28 :       return closure_identical(x,y);
     954             :     case t_LIST:
     955         161 :       return list_cmp(x, y, gidentical);
     956          21 :     case t_INFINITY: return gidentical(gel(x,1),gel(y,1));
     957             :   }
     958           0 :   return 0;
     959             : }
     960             : /* x,y t_POL */
     961             : static int
     962     8377405 : polequal(GEN x, GEN y)
     963             : {
     964             :   long lx, ly;
     965     8377405 :   if ((x[1] ^ y[1]) & (VARNBITS | SIGNBITS)) return 0;
     966     8368683 :   lx = lg(x); ly = lg(y);
     967     8368683 :   while (lx > ly) if (!gequal0(gel(x,--lx))) return 0;
     968     8366548 :   while (ly > lx) if (!gequal0(gel(y,--ly))) return 0;
     969     8353276 :   for (lx--; lx >= 2; lx--) if (!gequal(gel(x,lx), gel(y,lx))) return 0;
     970     8323306 :   return 1;
     971             : }
     972             : 
     973             : /* x,y t_POL */
     974             : static int
     975         336 : serequal(GEN x, GEN y)
     976             : {
     977             :   long lx;
     978         336 :   if (varn(x) != varn(y)) return 0;
     979         336 :   if (!signe(x))
     980             :   {
     981         308 :     if (!signe(y)) return 1;
     982           0 :     return valp(y) >= valp(x);
     983             :   }
     984          28 :   if (!signe(y))
     985           7 :     return valp(x) >= valp(y);
     986          21 :   if ((x[1] ^ y[1]) & VALPBITS) return 0;
     987          21 :   lx = minss(lg(x), lg(y));
     988          21 :   for (lx--; lx >= 2; lx--) if (!gequal(gel(x,lx), gel(y,lx))) return 0;
     989          21 :   return 1;
     990             : }
     991             : 
     992             : /* typ(x) = typ(y) = t_VEC/COL/MAT */
     993             : static int
     994     5067677 : vecequal(GEN x, GEN y)
     995             : {
     996             :   long i;
     997     5067677 :   if ((x[0] ^ y[0]) & (TYPBITS|LGBITS)) return 0;
     998    16373388 :   for (i = lg(x)-1; i; i--)
     999    14283973 :     if (! gequal(gel(x,i),gel(y,i)) ) return 0;
    1000     2089415 :   return 1;
    1001             : }
    1002             : 
    1003             : static int
    1004     1333862 : gequal_try(GEN x, GEN y)
    1005             : {
    1006             :   int i;
    1007     1333862 :   pari_CATCH(CATCH_ALL) {
    1008         182 :     GEN E = pari_err_last();
    1009         182 :     switch(err_get_num(E))
    1010             :     {
    1011             :       case e_STACK: case e_MEM: case e_ALARM:
    1012           0 :         pari_err(0, E); /* rethrow */
    1013             :     }
    1014         182 :     return 0;
    1015             :   } pari_TRY {
    1016     1333862 :     i = gequal0(gadd(x, gneg_i(y)));
    1017     1333680 :   } pari_ENDCATCH;
    1018     1333680 :   return i;
    1019             : }
    1020             : 
    1021             : int
    1022   216036973 : gequal(GEN x, GEN y)
    1023             : {
    1024             :   pari_sp av;
    1025             :   long tx, ty;
    1026             :   long i;
    1027             : 
    1028   216036973 :   if (x == y) return 1;
    1029   192594154 :   tx = typ(x);
    1030   192594154 :   ty = typ(y);
    1031   192594154 :   if (tx == ty)
    1032   187639682 :     switch(tx)
    1033             :     {
    1034             :       case t_INT:
    1035   161643227 :         return equalii(x,y);
    1036             : 
    1037             :       case t_REAL:
    1038        1986 :         return equalrr(x,y);
    1039             : 
    1040             :       case t_FRAC: case t_INTMOD:
    1041     7192958 :         return equalii(gel(x,2), gel(y,2)) && equalii(gel(x,1), gel(y,1));
    1042             : 
    1043             :       case t_COMPLEX:
    1044         420 :         return gequal(gel(x,2),gel(y,2)) && gequal(gel(x,1),gel(y,1));
    1045             :       case t_PADIC:
    1046         756 :         if (!equalii(gel(x,2),gel(y,2))) return 0;
    1047         756 :         av = avma; i = gequal0(gsub(x,y)); set_avma(av);
    1048         756 :         return i;
    1049             :       case t_POLMOD:
    1050     3457893 :         if (varn(gel(x,1)) != varn(gel(y,1))) break;
    1051     3457886 :         return gequal(gel(x,2),gel(y,2)) && RgX_equal_var(gel(x,1),gel(y,1));
    1052             :       case t_POL:
    1053     8377406 :         return polequal(x,y);
    1054             :       case t_SER:
    1055         336 :         return serequal(x,y);
    1056             : 
    1057             :       case t_FFELT:
    1058       55888 :         return FF_equal(x,y);
    1059             : 
    1060             :       case t_QFR:
    1061             :       case t_QFI:
    1062     1050134 :         return equalii(gel(x,1),gel(y,1))
    1063      230227 :             && equalii(gel(x,2),gel(y,2))
    1064     1207344 :             && equalii(gel(x,3),gel(y,3));
    1065             : 
    1066             :       case t_QUAD:
    1067           7 :         return ZX_equal(gel(x,1),gel(y,1))
    1068           0 :             && gequal(gel(x,2),gel(y,2))
    1069           7 :             && gequal(gel(x,3),gel(y,3));
    1070             : 
    1071             :       case t_RFRAC:
    1072             :       {
    1073       73717 :         GEN a = gel(x,1), b = gel(x,2), c = gel(y,1), d = gel(y,2);
    1074       73717 :         if (gequal(b,d)) return gequal(a,c); /* simple case */
    1075           0 :         av = avma;
    1076           0 :         a = simplify_shallow(gmul(a,d));
    1077           0 :         b = simplify_shallow(gmul(b,c));
    1078           0 :         return gc_bool(av, gequal(a,b));
    1079             :       }
    1080             : 
    1081             :       case t_STR:
    1082       61401 :         return !strcmp(GSTR(x),GSTR(y));
    1083             :       case t_VEC: case t_COL: case t_MAT:
    1084     5067677 :         return vecequal(x,y);
    1085             :       case t_VECSMALL:
    1086      655677 :         return zv_equal(x,y);
    1087             :       case t_LIST:
    1088         175 :         return list_cmp(x, y, gequal);
    1089             :       case t_CLOSURE:
    1090           7 :         return closure_identical(x,y);
    1091             :       case t_INFINITY:
    1092          28 :         return gequal(gel(x,1),gel(y,1));
    1093             :     }
    1094     4954468 :   if (is_noncalc_t(tx) || is_noncalc_t(ty)) return 0;
    1095     4954485 :   if (tx == t_INT && !signe(x)) return gequal0(y);
    1096     4951958 :   if (ty == t_INT && !signe(y)) return gequal0(x);
    1097     1333862 :   (void)&av; av = avma; /* emulate volatile */
    1098     1333862 :   return gc_bool(av, gequal_try(x, y));
    1099             : }
    1100             : 
    1101             : int
    1102       39354 : gequalsg(long s, GEN x)
    1103       39354 : { pari_sp av = avma; return gc_bool(av, gequal(stoi(s), x)); }
    1104             : 
    1105             : /* a and b are t_INT, t_FRAC, t_REAL or t_COMPLEX of those. Check whether
    1106             :  * a-b is invertible */
    1107             : int
    1108        9331 : cx_approx_equal(GEN a, GEN b)
    1109             : {
    1110        9331 :   pari_sp av = avma;
    1111             :   GEN d;
    1112        9331 :   if (a == b) return 1;
    1113        7805 :   d = gsub(a,b);
    1114        7805 :   return gc_bool(av, gequal0(d) || (typ(d)==t_COMPLEX && gequal0(cxnorm(d))));
    1115             : }
    1116             : /*******************************************************************/
    1117             : /*                                                                 */
    1118             : /*                          VALUATION                              */
    1119             : /*             p is either a t_INT or a t_POL.                     */
    1120             : /*  returns the largest exponent of p dividing x when this makes   */
    1121             : /*  sense : error for types real, integermod and polymod if p does */
    1122             : /*  not divide the modulus, q-adic if q!=p.                        */
    1123             : /*                                                                 */
    1124             : /*******************************************************************/
    1125             : 
    1126             : static long
    1127         287 : minval(GEN x, GEN p)
    1128             : {
    1129         287 :   long i,k, val = LONG_MAX, lx = lg(x);
    1130        5978 :   for (i=lontyp[typ(x)]; i<lx; i++)
    1131             :   {
    1132        5691 :     k = gvaluation(gel(x,i),p);
    1133        5691 :     if (k < val) val = k;
    1134             :   }
    1135         287 :   return val;
    1136             : }
    1137             : 
    1138             : static int
    1139          91 : intdvd(GEN x, GEN y, GEN *z) { GEN r; *z = dvmdii(x,y,&r); return (r==gen_0); }
    1140             : 
    1141             : /* x t_FRAC, p t_INT, return v_p(x) */
    1142             : static long
    1143       70508 : frac_val(GEN x, GEN p) {
    1144       70508 :   long v = Z_pval(gel(x,2),p);
    1145       70508 :   if (v) return -v;
    1146       70440 :   return Z_pval(gel(x,1),p);
    1147             : }
    1148             : long
    1149     1541486 : Q_pval(GEN x, GEN p)
    1150             : {
    1151     1541486 :   if (lgefint(p) == 3) return Q_lval(x, uel(p,2));
    1152         139 :   return (typ(x)==t_INT)? Z_pval(x, p): frac_val(x, p);
    1153             : }
    1154             : 
    1155             : static long
    1156      143782 : frac_lval(GEN x, ulong p) {
    1157      143782 :   long v = Z_lval(gel(x,2),p);
    1158      143782 :   if (v) return -v;
    1159       58702 :   return Z_lval(gel(x,1),p);
    1160             : }
    1161             : long
    1162     1541352 : Q_lval(GEN x, ulong p){return (typ(x)==t_INT)? Z_lval(x, p): frac_lval(x, p);}
    1163             : 
    1164             : long
    1165     3718190 : Q_pvalrem(GEN x, GEN p, GEN *y)
    1166             : {
    1167             :   GEN a, b;
    1168             :   long v;
    1169     3718190 :   if (lgefint(p) == 3) return Q_lvalrem(x, uel(p,2), y);
    1170         634 :   if (typ(x) == t_INT) return Z_pvalrem(x, p, y);
    1171           0 :   a = gel(x,1);
    1172           0 :   b = gel(x,2);
    1173           0 :   v = Z_pvalrem(b, p, &b);
    1174           0 :   if (v) { *y = isint1(b)? a: mkfrac(a, b); return -v; }
    1175           0 :   v = Z_pvalrem(a, p, &a);
    1176           0 :   *y = mkfrac(a, b); return v;
    1177             : }
    1178             : long
    1179     3717557 : Q_lvalrem(GEN x, ulong p, GEN *y)
    1180             : {
    1181             :   GEN a, b;
    1182             :   long v;
    1183     3717557 :   if (typ(x) == t_INT) return Z_lvalrem(x, p, y);
    1184     1297622 :   a = gel(x,1);
    1185     1297622 :   b = gel(x,2);
    1186     1297622 :   v = Z_lvalrem(b, p, &b);
    1187     1297622 :   if (v) { *y = isint1(b)? a: mkfrac(a, b); return -v; }
    1188      825105 :   v = Z_lvalrem(a, p, &a);
    1189      825105 :   *y = mkfrac(a, b); return v;
    1190             : }
    1191             : 
    1192             : long
    1193      324941 : gvaluation(GEN x, GEN p)
    1194             : {
    1195      324941 :   long tx = typ(x), tp = typ(p);
    1196             :   pari_sp av;
    1197             : 
    1198      324941 :   switch(tp)
    1199             :   {
    1200             :     case t_INT:
    1201      320335 :       if (signe(p) && !is_pm1(p)) break;
    1202          28 :       pari_err_DOMAIN("gvaluation", "p", "=", p, p);
    1203             :     case t_POL:
    1204        4599 :       if (degpol(p) > 0) break;
    1205             :     default:
    1206           7 :       pari_err_DOMAIN("gvaluation", "p", "=", p, p);
    1207             :   }
    1208             : 
    1209      324906 :   switch(tx)
    1210             :   {
    1211             :     case t_INT:
    1212       57308 :       if (!signe(x)) return LONG_MAX;
    1213       57203 :       if (tp == t_POL) return 0;
    1214       56909 :       return Z_pval(x,p);
    1215             : 
    1216             :     case t_REAL:
    1217          49 :       if (tp == t_POL) return 0;
    1218          21 :       break;
    1219             : 
    1220             :     case t_FFELT:
    1221          28 :       if (tp == t_POL) return FF_equal0(x)? LONG_MAX: 0;
    1222          14 :       break;
    1223             : 
    1224             :     case t_INTMOD: {
    1225          84 :       GEN a = gel(x,1), b = gel(x,2);
    1226             :       long val;
    1227         154 :       if (tp == t_POL) return signe(b)? 0: LONG_MAX;
    1228          42 :       av = avma;
    1229          42 :       if (!intdvd(a, p, &a)) break;
    1230          28 :       if (!intdvd(b, p, &b)) return gc_long(av,0);
    1231          14 :       val = 1; while (intdvd(a,p,&a) && intdvd(b,p,&b)) val++;
    1232          14 :       return gc_long(av,val);
    1233             :     }
    1234             : 
    1235             :     case t_FRAC:
    1236       70462 :       if (tp == t_POL) return 0;
    1237       70448 :       return frac_val(x, p);
    1238             : 
    1239             :     case t_PADIC:
    1240      192572 :       if (tp == t_POL) return 0;
    1241      192558 :       if (!equalii(p,gel(x,2))) break;
    1242      192551 :       return valp(x);
    1243             : 
    1244             :     case t_POLMOD: {
    1245          35 :       GEN a = gel(x,1), b = gel(x,2);
    1246             :       long v, val;
    1247          35 :       if (tp == t_INT) return gvaluation(b,p);
    1248          21 :       v = varn(p);
    1249          21 :       if (varn(a) != v) return 0;
    1250          21 :       av = avma;
    1251          21 :       a = RgX_divrem(a, p, ONLY_DIVIDES);
    1252          21 :       if (!a) break;
    1253          14 :       if (typ(b) != t_POL || varn(b) != v ||
    1254           7 :           !(b = RgX_divrem(b, p, ONLY_DIVIDES)) ) return gc_long(av,0);
    1255           7 :       val = 1;
    1256          21 :       while ((a = RgX_divrem(a, p, ONLY_DIVIDES)) &&
    1257           7 :              (b = RgX_divrem(b, p, ONLY_DIVIDES)) ) val++;
    1258           7 :       return gc_long(av,val);
    1259             :     }
    1260             :     case t_POL: {
    1261        4067 :       if (tp == t_POL) {
    1262        3878 :         long vp = varn(p), vx = varn(x);
    1263        3878 :         if (vp == vx)
    1264             :         {
    1265             :           long val;
    1266        3871 :           if (RgX_is_monomial(p)) return RgX_val(x) / degpol(p);
    1267           7 :           av = avma;
    1268           7 :           for (val=0; ; val++)
    1269             :           {
    1270           7 :             x = RgX_divrem(x,p,ONLY_DIVIDES);
    1271           7 :             if (!x) return gc_long(av,val);
    1272           0 :             if (gc_needed(av,1))
    1273             :             {
    1274           0 :               if(DEBUGMEM>1) pari_warn(warnmem,"gvaluation");
    1275           0 :               x = gerepilecopy(av, x);
    1276             :             }
    1277             :           }
    1278             :         }
    1279           7 :         if (varncmp(vx, vp) > 0) return 0;
    1280             :       }
    1281         189 :       return minval(x,p);
    1282             :     }
    1283             : 
    1284             :     case t_SER: {
    1285         175 :       if (tp == t_POL) {
    1286         161 :         long vp = varn(p), vx = varn(x);
    1287         161 :         if (vp == vx)
    1288             :         {
    1289         154 :           long val = RgX_val(p);
    1290         154 :           if (!val) pari_err_DOMAIN("gvaluation", "p", "=", p, p);
    1291         147 :           return (long)(valp(x) / val);
    1292             :         }
    1293           7 :         if (varncmp(vx, vp) > 0) return 0;
    1294             :       }
    1295          14 :       return minval(x,p);
    1296             :     }
    1297             : 
    1298             :     case t_RFRAC:
    1299          42 :       return gvaluation(gel(x,1),p) - gvaluation(gel(x,2),p);
    1300             : 
    1301             :     case t_COMPLEX: case t_QUAD: case t_VEC: case t_COL: case t_MAT:
    1302          84 :       return minval(x,p);
    1303             :   }
    1304          63 :   pari_err_OP("valuation", x,p);
    1305             :   return 0; /* LCOV_EXCL_LINE */
    1306             : }
    1307             : GEN
    1308        3717 : gpvaluation(GEN x, GEN p)
    1309             : {
    1310        3717 :   long v = gvaluation(x,p);
    1311        3619 :   return v == LONG_MAX? mkoo(): stoi(v);
    1312             : }
    1313             : 
    1314             : /* x is non-zero */
    1315             : long
    1316    22906573 : u_lvalrem(ulong x, ulong p, ulong *py)
    1317             : {
    1318             :   ulong vx;
    1319    22906573 :   if (p == 2) { vx = vals(x); *py = x >> vx; return vx; }
    1320    20296669 :   for(vx = 0;;)
    1321             :   {
    1322    49031189 :     if (x % p) { *py = x; return vx; }
    1323    14367260 :     x /= p; /* gcc is smart enough to make a single div */
    1324    14367260 :     vx++;
    1325             :   }
    1326             : }
    1327             : long
    1328    11942742 : u_lval(ulong x, ulong p)
    1329             : {
    1330             :   ulong vx;
    1331    11942742 :   if (p == 2) return vals(x);
    1332    11260799 :   for(vx = 0;;)
    1333             :   {
    1334    50561373 :     if (x % p) return vx;
    1335    19650287 :     x /= p; /* gcc is smart enough to make a single div */
    1336    19650287 :     vx++;
    1337             :   }
    1338             : }
    1339             : 
    1340             : long
    1341      926387 : z_lval(long s, ulong p) { return u_lval(labs(s), p); }
    1342             : long
    1343          63 : z_lvalrem(long s, ulong p, long *py)
    1344             : {
    1345             :   long v;
    1346          63 :   if (s < 0)
    1347             :   {
    1348           0 :     ulong u = (ulong)-s;
    1349           0 :     v = u_lvalrem(u, p, &u);
    1350           0 :     *py = -(long)u;
    1351             :   }
    1352             :   else
    1353             :   {
    1354          63 :     ulong u = (ulong)s;
    1355          63 :     v = u_lvalrem(u, p, &u);
    1356          63 :     *py = (long)u;
    1357             :   }
    1358          63 :   return v;
    1359             : }
    1360             : /* assume |p| > 1 */
    1361             : long
    1362      616630 : z_pval(long s, GEN p)
    1363             : {
    1364      616630 :   if (lgefint(p) > 3) return 0;
    1365      616630 :   return z_lval(s, uel(p,2));
    1366             : }
    1367             : /* assume |p| > 1 */
    1368             : long
    1369          63 : z_pvalrem(long s, GEN p, long *py)
    1370             : {
    1371          63 :   if (lgefint(p) > 3) { *py = s; return 0; }
    1372          63 :   return z_lvalrem(s, uel(p,2), py);
    1373             : }
    1374             : 
    1375             : /* return v_q(x) and set *py = x / q^v_q(x), using divide & conquer */
    1376             : static long
    1377     1426622 : Z_pvalrem_DC(GEN x, GEN q, GEN *py)
    1378             : {
    1379     1426622 :   GEN r, z = dvmdii(x, q, &r);
    1380             :   long v;
    1381     1426622 :   if (r != gen_0) { *py = x; return 0; }
    1382     1001619 :   if (2 * lgefint(q) <= lgefint(z)+3) /* avoid squaring if pointless */
    1383      986684 :     v = Z_pvalrem_DC(z, sqri(q), py) << 1;
    1384             :   else
    1385       14935 :   { v = 0; *py = z; }
    1386     1001619 :   z = dvmdii(*py, q, &r);
    1387     1001619 :   if (r != gen_0) return v + 1;
    1388      425963 :   *py = z; return v + 2;
    1389             : }
    1390             : 
    1391             : static const long VAL_DC_THRESHOLD = 16;
    1392             : 
    1393             : long
    1394    11664376 : Z_lval(GEN x, ulong p)
    1395             : {
    1396             :   long vx;
    1397             :   pari_sp av;
    1398    11664376 :   if (p == 2) return vali(x);
    1399     8145894 :   if (lgefint(x) == 3) return u_lval(uel(x,2), p);
    1400     1098775 :   av = avma;
    1401     1098775 :   for(vx = 0;;)
    1402     5827444 :   {
    1403             :     ulong r;
    1404     6926219 :     GEN q = absdiviu_rem(x, p, &r);
    1405     8024994 :     if (r) break;
    1406     5951862 :     vx++; x = q;
    1407     5951862 :     if (vx == VAL_DC_THRESHOLD) {
    1408      124418 :       if (p == 1) pari_err_DOMAIN("Z_lval", "p", "=", gen_1, gen_1);
    1409      124418 :       vx += Z_pvalrem_DC(x, sqru(p), &x) << 1;
    1410      124418 :       q = absdiviu_rem(x, p, &r); if (!r) vx++;
    1411      124418 :       break;
    1412             :     }
    1413             :   }
    1414     1098775 :   return gc_long(av,vx);
    1415             : }
    1416             : long
    1417    22435736 : Z_lvalrem(GEN x, ulong p, GEN *py)
    1418             : {
    1419             :   long vx, sx;
    1420             :   pari_sp av;
    1421    22435736 :   if (p == 2) { vx = vali(x); *py = shifti(x, -vx); return vx; }
    1422    16080245 :   if (lgefint(x) == 3) {
    1423             :     ulong u;
    1424    11754225 :     vx = u_lvalrem(uel(x,2), p, &u);
    1425    11754225 :     *py = signe(x) < 0? utoineg(u): utoipos(u);
    1426    11754225 :     return vx;
    1427             :   }
    1428     4326020 :   av = avma; (void)new_chunk(lgefint(x));
    1429     4326020 :   sx = signe(x);
    1430     4326020 :   for(vx = 0;;)
    1431    10132485 :   {
    1432             :     ulong r;
    1433    14458505 :     GEN q = absdiviu_rem(x, p, &r);
    1434    18784525 :     if (r) break;
    1435    10438876 :     vx++; x = q;
    1436    10438876 :     if (vx == VAL_DC_THRESHOLD) {
    1437      306391 :       if (p == 1) pari_err_DOMAIN("Z_lvalrem", "p", "=", gen_1, gen_1);
    1438      306391 :       vx += Z_pvalrem_DC(x, sqru(p), &x) << 1;
    1439      306391 :       q = absdiviu_rem(x, p, &r); if (!r) { vx++; x = q; }
    1440      306391 :       break;
    1441             :     }
    1442             :   }
    1443     4326020 :   set_avma(av); *py = icopy(x); setsigne(*py, sx); return vx;
    1444             : }
    1445             : 
    1446             : /* Is |q| <= p ? */
    1447             : static int
    1448   202696652 : isless_iu(GEN q, ulong p) {
    1449   202696652 :   long l = lgefint(q);
    1450   202696652 :   return l==2 || (l == 3 && uel(q,2) <= p);
    1451             : }
    1452             : 
    1453             : long
    1454   544501130 : u_lvalrem_stop(ulong *n, ulong p, int *stop)
    1455             : {
    1456   544501130 :   ulong N = *n, q = N / p, r = N % p; /* gcc makes a single div */
    1457   544501130 :   long v = 0;
    1458   544501130 :   if (!r)
    1459             :   {
    1460    40085436 :     do { v++; N = q; q = N / p; r = N % p; } while (!r);
    1461    27201277 :     *n = N;
    1462             :   }
    1463   544501130 :   *stop = q <= p; return v;
    1464             : }
    1465             : /* Assume n > 0. Return v_p(n), set *n := n/p^v_p(n). Set 'stop' if now
    1466             :  * n < p^2 [implies n prime if no prime < p divides n] */
    1467             : long
    1468   593868616 : Z_lvalrem_stop(GEN *n, ulong p, int *stop)
    1469             : {
    1470             :   pari_sp av;
    1471             :   long v;
    1472             :   ulong r;
    1473             :   GEN N, q;
    1474             : 
    1475   593868616 :   if (lgefint(*n) == 3)
    1476             :   {
    1477   391161036 :     r = (*n)[2];
    1478   391161036 :     v = u_lvalrem_stop(&r, p, stop);
    1479   391245382 :     if (v) *n = utoipos(r);
    1480   391249284 :     return v;
    1481             :   }
    1482   202707580 :   av = avma; v = 0; q = absdiviu_rem(*n, p, &r);
    1483   202664647 :   if (r) set_avma(av);
    1484             :   else
    1485             :   {
    1486             :     do {
    1487     1247230 :       v++; N = q;
    1488     1247230 :       if (v == VAL_DC_THRESHOLD)
    1489             :       {
    1490        9129 :         v += Z_pvalrem_DC(N,sqru(p),&N) << 1;
    1491        9129 :         q = absdiviu_rem(N, p, &r); if (!r) { v++; N = q; }
    1492        9129 :         break;
    1493             :       }
    1494     1238101 :       q = absdiviu_rem(N, p, &r);
    1495     1238101 :     } while (!r);
    1496      643536 :     *n = N;
    1497             :   }
    1498   202668524 :   *stop = isless_iu(q,p); return v;
    1499             : }
    1500             : 
    1501             : /* x is a non-zero integer, |p| > 1 */
    1502             : long
    1503    15600217 : Z_pvalrem(GEN x, GEN p, GEN *py)
    1504             : {
    1505             :   long vx;
    1506             :   pari_sp av;
    1507             : 
    1508    15600217 :   if (lgefint(p) == 3) return Z_lvalrem(x, uel(p,2), py);
    1509      134825 :   if (lgefint(x) == 3) { *py = icopy(x); return 0; }
    1510        3938 :   av = avma; vx = 0; (void)new_chunk(lgefint(x));
    1511             :   for(;;)
    1512        9527 :   {
    1513       13465 :     GEN r, q = dvmdii(x,p,&r);
    1514       13465 :     if (r != gen_0) { set_avma(av); *py = icopy(x); return vx; }
    1515        9527 :     vx++; x = q;
    1516             :   }
    1517             : }
    1518             : long
    1519      450132 : u_pvalrem(ulong x, GEN p, ulong *py)
    1520             : {
    1521      450132 :   if (lgefint(p) == 3) return u_lvalrem(x, uel(p,2), py);
    1522         459 :   *py = x; return 0;
    1523             : }
    1524             : long
    1525        2002 : u_pval(ulong x, GEN p)
    1526             : {
    1527        2002 :   if (lgefint(p) == 3) return u_lval(x, uel(p,2));
    1528           0 :   return 0;
    1529             : }
    1530             : long
    1531     6052546 : Z_pval(GEN x, GEN p) {
    1532             :   long vx;
    1533             :   pari_sp av;
    1534             : 
    1535     6052546 :   if (lgefint(p) == 3) return Z_lval(x, uel(p,2));
    1536       77869 :   if (lgefint(x) == 3) return 0;
    1537       71133 :   av = avma; vx = 0;
    1538             :   for(;;)
    1539       20825 :   {
    1540       91958 :     GEN r, q = dvmdii(x,p,&r);
    1541       91958 :     if (r != gen_0) return gc_long(av,vx);
    1542       20825 :     vx++; x = q;
    1543             :   }
    1544             : }
    1545             : 
    1546             : /* return v_p(n!) = [n/p] + [n/p^2] + ... */
    1547             : long
    1548      137436 : factorial_lval(ulong n, ulong p)
    1549             : {
    1550             :   ulong q, v;
    1551      137436 :   if (p == 2) return n - hammingl(n);
    1552       37518 :   q = p; v = 0;
    1553       40088 :   do { v += n/q; q *= p; } while (n >= q);
    1554       37518 :   return (long)v;
    1555             : }
    1556             : 
    1557             : /********** Same for "containers" ZX / ZV / ZC **********/
    1558             : 
    1559             : /* If the t_INT q divides the ZX/ZV x, return the quotient. Otherwise NULL.
    1560             :  * Stack clean; assumes lg(x) > 1 */
    1561             : static GEN
    1562        4487 : gen_Z_divides(GEN x, GEN q, long imin)
    1563             : {
    1564             :   long i, l;
    1565        4487 :   GEN y = cgetg_copy(x, &l);
    1566             : 
    1567        4487 :   y[1] = x[1]; /* Needed for ZX; no-op if ZV, overwritten in first iteration */
    1568       84511 :   for (i = imin; i < l; i++)
    1569             :   {
    1570       82691 :     GEN r, xi = gel(x,i);
    1571       82691 :     if (!signe(xi)) { gel(y,i) = xi; continue; }
    1572       51384 :     gel(y,i) = dvmdii(xi, q, &r);
    1573       51384 :     if (r != gen_0) { set_avma((pari_sp)(y+l)); return NULL; }
    1574             :   }
    1575        1820 :   return y;
    1576             : }
    1577             : /* If q divides the ZX/ZV x, return the quotient. Otherwise NULL.
    1578             :  * Stack clean; assumes lg(x) > 1 */
    1579             : static GEN
    1580        2751 : gen_z_divides(GEN x, ulong q, long imin)
    1581             : {
    1582             :   long i, l;
    1583        2751 :   GEN y = cgetg_copy(x, &l);
    1584             : 
    1585        2751 :   y[1] = x[1]; /* Needed for ZX; no-op if ZV, overwritten in first iteration */
    1586       36967 :   for (i = imin; i < l; i++)
    1587             :   {
    1588             :     ulong r;
    1589       36596 :     GEN xi = gel(x,i);
    1590       36596 :     if (!signe(xi)) { gel(y,i) = xi; continue; }
    1591       23051 :     gel(y,i) = absdiviu_rem(xi, q, &r);
    1592       23051 :     if (r) { set_avma((pari_sp)(y+l)); return NULL; }
    1593       20671 :     affectsign_safe(xi, &gel(y,i));
    1594             :   }
    1595         371 :   return y;
    1596             : }
    1597             : 
    1598             : /* return v_q(x) and set *py = x / q^v_q(x), using divide & conquer */
    1599             : static long
    1600        7193 : gen_pvalrem_DC(GEN x, GEN q, GEN *py, long imin)
    1601             : {
    1602             : 
    1603        7193 :   pari_sp av = avma;
    1604        7193 :   long v, i, l, lz = LONG_MAX;
    1605        7193 :   GEN y = cgetg_copy(x, &l);
    1606             : 
    1607        7193 :   y[1] = x[1];
    1608      123146 :   for (i = imin; i < l; i++)
    1609             :   {
    1610      118659 :     GEN r, xi = gel(x,i);
    1611      118659 :     if (!signe(xi)) { gel(y,i) = xi; continue; }
    1612       75923 :     gel(y,i) = dvmdii(xi, q, &r);
    1613       75923 :     if (r != gen_0) { *py = x; return gc_long(av,0); }
    1614       73217 :     lz = minss(lz, lgefint(gel(y,i)));
    1615             :   }
    1616        4487 :   if (2 * lgefint(q) <= lz+3) /* avoid squaring if pointless */
    1617        4428 :     v = gen_pvalrem_DC(y, sqri(q), py, imin) << 1;
    1618             :   else
    1619          59 :   { v = 0; *py = y; }
    1620             : 
    1621        4487 :   y = gen_Z_divides(*py, q, imin);
    1622        4487 :   if (!y) return v+1;
    1623        1820 :   *py = y; return v+2;
    1624             : }
    1625             : 
    1626             : static long
    1627        5845 : gen_2val(GEN x, long imin)
    1628             : {
    1629        5845 :   long i, lx = lg(x), v = LONG_MAX;
    1630       18034 :   for (i = imin; i < lx; i++)
    1631             :   {
    1632       16676 :     GEN c = gel(x,i);
    1633             :     long w;
    1634       16676 :     if (!signe(c)) continue;
    1635       12011 :     w = vali(c);
    1636       12011 :     if (w < v) { v = w; if (!v) break; }
    1637             :   }
    1638        5845 :   return v;
    1639             : }
    1640             : static long
    1641       13180 : gen_lval(GEN x, ulong p, long imin)
    1642             : {
    1643             :   long i, lx, v;
    1644             :   pari_sp av;
    1645             :   GEN y;
    1646       13180 :   if (p == 2) return gen_2val(x, imin);
    1647        7335 :   av = avma;
    1648        7335 :   lx = lg(x); y = leafcopy(x);
    1649        7475 :   for(v = 0;; v++)
    1650       10198 :     for (i = imin; i < lx; i++)
    1651             :     {
    1652             :       ulong r;
    1653        9918 :       gel(y,i) = absdiviu_rem(gel(y,i), p, &r);
    1654        9918 :       if (r) return gc_long(av,v);
    1655             :     }
    1656             : }
    1657             : long
    1658          42 : ZX_lval(GEN x, ulong p) { return gen_lval(x, p, 2); }
    1659             : long
    1660           0 : ZV_lval(GEN x, ulong p) { return gen_lval(x, p, 1); }
    1661             : 
    1662             : long
    1663           0 : zx_lval(GEN f, long p)
    1664             : {
    1665           0 :   long i, l = lg(f), x = LONG_MAX;
    1666           0 :   for(i=2; i<l; i++)
    1667             :   {
    1668             :     long y;
    1669           0 :     if (f[i] == 0) continue;
    1670           0 :     y = z_lval(f[i], p);
    1671           0 :     if (y < x) { x = y; if (x == 0) return x; }
    1672             :   }
    1673           0 :   return x;
    1674             : }
    1675             : 
    1676             : static long
    1677       15358 : gen_pval(GEN x, GEN p, long imin)
    1678             : {
    1679             :   long i, lx, v;
    1680             :   pari_sp av;
    1681             :   GEN y;
    1682       15358 :   if (lgefint(p) == 3) return gen_lval(x, p[2], imin);
    1683        2220 :   av = avma;
    1684        2220 :   lx = lg(x); y = leafcopy(x);
    1685        2220 :   for(v = 0;; v++)
    1686             :   {
    1687        2220 :     if (v == VAL_DC_THRESHOLD)
    1688             :     {
    1689           0 :       if (is_pm1(p)) pari_err_DOMAIN("gen_pval", "p", "=", p, p);
    1690           0 :       v += gen_pvalrem_DC(y, p, &y, imin);
    1691           0 :       return gc_long(av,v);
    1692             :     }
    1693             : 
    1694        2220 :     for (i = imin; i < lx; i++)
    1695             :     {
    1696        2220 :       GEN r; gel(y,i) = dvmdii(gel(y,i), p, &r);
    1697        2220 :       if (r != gen_0) return gc_long(av,v);
    1698             :     }
    1699             :   }
    1700             : }
    1701             : long
    1702        8001 : ZX_pval(GEN x, GEN p) { return gen_pval(x, p, 2); }
    1703             : long
    1704        7357 : ZV_pval(GEN x, GEN p) { return gen_pval(x, p, 1); }
    1705             : /* v = 0 (mod p) */
    1706             : int
    1707         343 : ZV_Z_dvd(GEN v, GEN p)
    1708             : {
    1709         343 :   pari_sp av = avma;
    1710         343 :   long i, l = lg(v);
    1711        1183 :   for (i=1; i<l; i++)
    1712         868 :     if (!dvdii(gel(v,i), p)) return gc_long(av,0);
    1713         315 :   return gc_long(av,1);
    1714             : }
    1715             : 
    1716             : static long
    1717      380973 : gen_2valrem(GEN x, GEN *px, long imin)
    1718             : {
    1719      380973 :   long i, lx = lg(x), v = LONG_MAX;
    1720             :   GEN z;
    1721     4055523 :   for (i = imin; i < lx; i++)
    1722             :   {
    1723     3842313 :     GEN c = gel(x,i);
    1724             :     long w;
    1725     3842313 :     if (!signe(c)) continue;
    1726     3621292 :     w = vali(c);
    1727     3621292 :     if (w < v) {
    1728      743684 :       v = w;
    1729      743684 :       if (!v) { *px = x; return 0; } /* early abort */
    1730             :     }
    1731             :   }
    1732      213210 :   z = cgetg_copy(x, &lx); z[1] = x[1];
    1733      213210 :   for (i=imin; i<lx; i++) gel(z,i) = shifti(gel(x,i), -v);
    1734      213210 :   *px = z; return v;
    1735             : }
    1736             : static long
    1737      961220 : gen_lvalrem(GEN x, ulong p, GEN *px, long imin)
    1738             : {
    1739             :   long i, lx, v;
    1740             :   GEN y;
    1741      961220 :   if (p == 2) return gen_2valrem(x, px, imin);
    1742      580247 :   y = cgetg_copy(x, &lx);
    1743      580247 :   y[1] = x[1];
    1744      580247 :   x = leafcopy(x);
    1745     1044980 :   for(v = 0;; v++)
    1746             :   {
    1747     1509713 :     if (v == VAL_DC_THRESHOLD)
    1748             :     {
    1749        2751 :       if (p == 1) pari_err_DOMAIN("gen_lvalrem", "p", "=", gen_1, gen_1);
    1750        2751 :       v += gen_pvalrem_DC(x, sqru(p), px, imin) << 1;
    1751        2751 :       x = gen_z_divides(*px, p, imin);
    1752        2751 :       if (x) { *px = x; v++; }
    1753        2751 :       return v;
    1754             :     }
    1755             : 
    1756     6742168 :     for (i = imin; i < lx; i++)
    1757             :     {
    1758     6277435 :       ulong r; gel(y,i) = absdiviu_rem(gel(x,i), p, &r);
    1759     6277435 :       if (r) { *px = x; return v; }
    1760     5699939 :       affectsign_safe(gel(x,i), &gel(y,i));
    1761             :     }
    1762      464733 :     swap(x, y);
    1763             :   }
    1764             : }
    1765             : long
    1766         721 : ZX_lvalrem(GEN x, ulong p, GEN *px) { return gen_lvalrem(x,p,px, 2); }
    1767             : long
    1768           0 : ZV_lvalrem(GEN x, ulong p, GEN *px) { return gen_lvalrem(x,p,px, 1); }
    1769             : 
    1770             : static long
    1771      960703 : gen_pvalrem(GEN x, GEN p, GEN *px, long imin)
    1772             : {
    1773             :   long i, lx, v;
    1774             :   GEN y;
    1775      960703 :   if (lgefint(p) == 3) return gen_lvalrem(x, p[2], px, imin);
    1776         204 :   y = cgetg_copy(x, &lx);
    1777         204 :   y[1] = x[1];
    1778         204 :   x = leafcopy(x);
    1779         930 :   for(v = 0;; v++)
    1780             :   {
    1781        1656 :     if (v == VAL_DC_THRESHOLD)
    1782             :     {
    1783          14 :       if (is_pm1(p)) pari_err_DOMAIN("gen_pvalrem", "p", "=", p, p);
    1784          14 :       return v + gen_pvalrem_DC(x, p, px, imin);
    1785             :     }
    1786             : 
    1787        9153 :     for (i = imin; i < lx; i++)
    1788             :     {
    1789        8427 :       GEN r; gel(y,i) = dvmdii(gel(x,i), p, &r);
    1790        8427 :       if (r != gen_0) { *px = x; return v; }
    1791             :     }
    1792         726 :     swap(x, y);
    1793             :   }
    1794             : }
    1795             : long
    1796      629671 : ZX_pvalrem(GEN x, GEN p, GEN *px) { return gen_pvalrem(x,p,px, 2); }
    1797             : long
    1798      331032 : ZV_pvalrem(GEN x, GEN p, GEN *px) { return gen_pvalrem(x,p,px, 1); }
    1799             : 
    1800             : /*******************************************************************/
    1801             : /*                                                                 */
    1802             : /*                       NEGATION: Create -x                       */
    1803             : /*                                                                 */
    1804             : /*******************************************************************/
    1805             : 
    1806             : GEN
    1807   219776009 : gneg(GEN x)
    1808             : {
    1809             :   long lx, i;
    1810             :   GEN y;
    1811             : 
    1812   219776009 :   switch(typ(x))
    1813             :   {
    1814             :     case t_INT:
    1815    70997288 :       return signe(x)? negi(x): gen_0;
    1816             :     case t_REAL:
    1817   104469736 :       return mpneg(x);
    1818             : 
    1819      219415 :     case t_INTMOD: y=cgetg(3,t_INTMOD);
    1820      219415 :       gel(y,1) = icopy(gel(x,1));
    1821      219415 :       gel(y,2) = signe(gel(x,2))? subii(gel(y,1),gel(x,2)): gen_0;
    1822      219415 :       break;
    1823             : 
    1824             :     case t_FRAC:
    1825     1596771 :       y = cgetg(3, t_FRAC);
    1826     1596771 :       gel(y,1) = negi(gel(x,1));
    1827     1596771 :       gel(y,2) = icopy(gel(x,2)); break;
    1828             : 
    1829             :     case t_COMPLEX:
    1830    40629173 :       y=cgetg(3, t_COMPLEX);
    1831    40629173 :       gel(y,1) = gneg(gel(x,1));
    1832    40629173 :       gel(y,2) = gneg(gel(x,2));
    1833    40629173 :       break;
    1834             : 
    1835             :     case t_POLMOD:
    1836      201188 :       retmkpolmod(gneg(gel(x,2)), RgX_copy(gel(x,1)));
    1837             : 
    1838             :     case t_RFRAC:
    1839      153272 :       y = cgetg(3, t_RFRAC);
    1840      153272 :       gel(y,1) = gneg(gel(x,1));
    1841      153272 :       gel(y,2) = RgX_copy(gel(x,2)); break;
    1842             : 
    1843             :     case t_PADIC:
    1844        6937 :       if (!signe(gel(x,4))) return gcopy(x);
    1845        5992 :       y = cgetg(5, t_PADIC);
    1846        5992 :       y[1] = x[1];
    1847        5992 :       gel(y,2) = icopy(gel(x,2));
    1848        5992 :       gel(y,3) = icopy(gel(x,3));
    1849        5992 :       gel(y,4) = subii(gel(x,3),gel(x,4));
    1850        5992 :       break;
    1851             : 
    1852             :     case t_QUAD:
    1853         119 :       y=cgetg(4,t_QUAD);
    1854         119 :       gel(y,1) = ZX_copy(gel(x,1));
    1855         119 :       gel(y,2) = gneg(gel(x,2));
    1856         119 :       gel(y,3) = gneg(gel(x,3)); break;
    1857             : 
    1858       40706 :     case t_FFELT: return FF_neg(x);
    1859     1373374 :     case t_POL: return RgX_neg(x);
    1860             :     case t_SER:
    1861        1540 :       y = cgetg_copy(x, &lx); y[1] = x[1];
    1862        1540 :       for (i=2; i<lx; i++) gel(y,i) = gneg(gel(x,i));
    1863        1540 :       break;
    1864         980 :     case t_VEC: return RgV_neg(x);
    1865       82236 :     case t_COL: return RgC_neg(x);
    1866        2511 :     case t_MAT: return RgM_neg(x);
    1867         763 :     case t_INFINITY: return inf_get_sign(x) == 1? mkmoo(): mkoo();
    1868             :     default:
    1869           0 :       pari_err_TYPE("gneg",x);
    1870             :       return NULL; /* LCOV_EXCL_LINE */
    1871             :   }
    1872    42606282 :   return y;
    1873             : }
    1874             : 
    1875             : GEN
    1876    55763262 : gneg_i(GEN x)
    1877             : {
    1878             :   long lx, i;
    1879             :   GEN y;
    1880             : 
    1881    55763262 :   switch(typ(x))
    1882             :   {
    1883             :     case t_INT:
    1884    29737444 :       return signe(x)? negi(x): gen_0;
    1885             :     case t_REAL:
    1886     6050082 :       return mpneg(x);
    1887             : 
    1888     1088075 :     case t_INTMOD: y=cgetg(3,t_INTMOD);
    1889     1088075 :       gel(y,1) = gel(x,1);
    1890     1088075 :       gel(y,2) = signe(gel(x,2))? subii(gel(y,1),gel(x,2)): gen_0;
    1891     1088075 :       break;
    1892             : 
    1893             :     case t_FRAC:
    1894     2881127 :       y = cgetg(3, t_FRAC);
    1895     2881127 :       gel(y,1) = negi(gel(x,1));
    1896     2881127 :       gel(y,2) = gel(x,2); break;
    1897             : 
    1898             :     case t_COMPLEX:
    1899     2243282 :       y = cgetg(3, t_COMPLEX);
    1900     2243282 :       gel(y,1) = gneg_i(gel(x,1));
    1901     2243282 :       gel(y,2) = gneg_i(gel(x,2)); break;
    1902             : 
    1903     1775413 :     case t_PADIC: y = cgetg(5,t_PADIC);
    1904     1775413 :       y[1] = x[1];
    1905     1775413 :       gel(y,2) = gel(x,2);
    1906     1775413 :       gel(y,3) = gel(x,3);
    1907     1775413 :       gel(y,4) = signe(gel(x,4))? subii(gel(x,3),gel(x,4)): gen_0; break;
    1908             : 
    1909             :     case t_POLMOD:
    1910       78501 :       retmkpolmod(gneg_i(gel(x,2)), RgX_copy(gel(x,1)));
    1911             : 
    1912       84693 :     case t_FFELT: return FF_neg_i(x);
    1913             : 
    1914         665 :     case t_QUAD: y=cgetg(4,t_QUAD);
    1915         665 :       gel(y,1) = gel(x,1);
    1916         665 :       gel(y,2) = gneg_i(gel(x,2));
    1917         665 :       gel(y,3) = gneg_i(gel(x,3)); break;
    1918             : 
    1919             :     case t_VEC: case t_COL: case t_MAT:
    1920       28483 :       y = cgetg_copy(x, &lx);
    1921       28483 :       for (i=1; i<lx; i++) gel(y,i) = gneg_i(gel(x,i));
    1922       28483 :       break;
    1923             : 
    1924             :     case t_POL: case t_SER:
    1925     6756282 :       y = cgetg_copy(x, &lx); y[1]=x[1];
    1926     6756282 :       for (i=2; i<lx; i++) gel(y,i) = gneg_i(gel(x,i));
    1927     6756282 :       break;
    1928             : 
    1929             :     case t_RFRAC:
    1930     5039215 :       y = cgetg(3, t_RFRAC);
    1931     5039215 :       gel(y,1) = gneg_i(gel(x,1));
    1932     5039215 :       gel(y,2) = gel(x,2); break;
    1933             : 
    1934             :     default:
    1935           0 :       pari_err_TYPE("gneg_i",x);
    1936             :       return NULL; /* LCOV_EXCL_LINE */
    1937             :   }
    1938    19812542 :   return y;
    1939             : }
    1940             : 
    1941             : /******************************************************************/
    1942             : /*                                                                */
    1943             : /*                       ABSOLUTE VALUE                           */
    1944             : /*    Create abs(x) if x is integer, real, fraction or complex.   */
    1945             : /*                       Error otherwise.                         */
    1946             : /*                                                                */
    1947             : /******************************************************************/
    1948             : static int
    1949           0 : is_negative(GEN x) {
    1950           0 :   switch(typ(x))
    1951             :   {
    1952             :     case t_INT: case t_REAL:
    1953           0 :       return (signe(x) < 0);
    1954             :     case t_FRAC:
    1955           0 :       return (signe(gel(x,1)) < 0);
    1956             :   }
    1957           0 :   return 0;
    1958             : }
    1959             : 
    1960             : GEN
    1961    13208583 : gabs(GEN x, long prec)
    1962             : {
    1963             :   long lx, i;
    1964             :   pari_sp av, tetpil;
    1965             :   GEN y,p1;
    1966             : 
    1967    13208583 :   switch(typ(x))
    1968             :   {
    1969             :     case t_INT: case t_REAL:
    1970    10012937 :       return mpabs(x);
    1971             : 
    1972             :     case t_FRAC:
    1973        4368 :       return absfrac(x);
    1974             : 
    1975             :     case t_COMPLEX:
    1976     3180197 :       av=avma; p1=cxnorm(x);
    1977     3180197 :       switch(typ(p1))
    1978             :       {
    1979             :         case t_INT:
    1980         196 :           if (!Z_issquareall(p1, &y)) break;
    1981          98 :           return gerepileupto(av, y);
    1982             :         case t_FRAC: {
    1983             :           GEN a,b;
    1984       32214 :           if (!Z_issquareall(gel(p1,1), &a)) break;
    1985       10549 :           if (!Z_issquareall(gel(p1,2), &b)) break;
    1986           0 :           return gerepileupto(av, gdiv(a,b));
    1987             :         }
    1988             :       }
    1989     3180099 :       tetpil=avma;
    1990     3180099 :       return gerepile(av,tetpil,gsqrt(p1,prec));
    1991             : 
    1992             :     case t_QUAD:
    1993          21 :       av = avma;
    1994          21 :       return gerepileuptoleaf(av, gabs(quadtofp(x, prec), prec));
    1995             : 
    1996             :     case t_POL:
    1997           0 :       lx = lg(x); if (lx<=2) return RgX_copy(x);
    1998           0 :       return is_negative(gel(x,lx-1))? gneg(x): RgX_copy(x);
    1999             : 
    2000             :     case t_SER:
    2001           7 :      if (!signe(x)) pari_err_DOMAIN("abs", "argument", "=", gen_0, x);
    2002           7 :      if (valp(x)) pari_err_DOMAIN("abs", "series valuation", "!=", gen_0, x);
    2003           0 :      return is_negative(gel(x,2))? gneg(x): gcopy(x);
    2004             : 
    2005             :     case t_VEC: case t_COL: case t_MAT:
    2006       11053 :       y = cgetg_copy(x, &lx);
    2007       11053 :       for (i=1; i<lx; i++) gel(y,i) = gabs(gel(x,i),prec);
    2008       11053 :       return y;
    2009             :   }
    2010           0 :   pari_err_TYPE("gabs",x);
    2011             :   return NULL; /* LCOV_EXCL_LINE */
    2012             : }
    2013             : 
    2014             : GEN
    2015           7 : gmax(GEN x, GEN y) { return gcopy(gmax_shallow(x,y)); }
    2016             : GEN
    2017           0 : gmaxgs(GEN x, long s) { return (gcmpsg(s,x)>=0)? stoi(s): gcopy(x); }
    2018             : 
    2019             : GEN
    2020        1603 : gmin(GEN x, GEN y) { return gcopy(gmin_shallow(x,y)); }
    2021             : GEN
    2022           0 : gmings(GEN x, long s) { return (gcmpsg(s,x)>0)? gcopy(x): stoi(s); }
    2023             : 
    2024             : long
    2025        9608 : vecindexmax(GEN x)
    2026             : {
    2027        9608 :   long lx = lg(x), i0, i;
    2028             :   GEN s;
    2029             : 
    2030        9608 :   if (lx==1) pari_err_DOMAIN("vecindexmax", "empty argument", "=", x,x);
    2031        9608 :   switch(typ(x))
    2032             :   {
    2033             :     case t_VEC: case t_COL:
    2034        9608 :       s = gel(x,i0=1);
    2035       26692 :       for (i=2; i<lx; i++)
    2036       17084 :         if (gcmp(gel(x,i),s) > 0) s = gel(x,i0=i);
    2037        9608 :       return i0;
    2038             :     case t_VECSMALL:
    2039           0 :       return vecsmall_indexmax(x);
    2040           0 :     default: pari_err_TYPE("vecindexmax",x);
    2041             :   }
    2042             :   /* LCOV_EXCL_LINE */
    2043           0 :   return 0;
    2044             : }
    2045             : long
    2046       50541 : vecindexmin(GEN x)
    2047             : {
    2048       50541 :   long lx = lg(x), i0, i;
    2049             :   GEN s;
    2050             : 
    2051       50541 :   if (lx==1) pari_err_DOMAIN("vecindexmin", "empty argument", "=", x,x);
    2052       50541 :   switch(typ(x))
    2053             :   {
    2054             :     case t_VEC: case t_COL:
    2055       50541 :       s = gel(x,i0=1);
    2056      214671 :       for (i=2; i<lx; i++)
    2057      164130 :         if (gcmp(gel(x,i),s) < 0) s = gel(x,i0=i);
    2058       50541 :       return i0;
    2059             :     case t_VECSMALL:
    2060           0 :       return vecsmall_indexmin(x);
    2061           0 :     default: pari_err_TYPE("vecindexmin",x);
    2062             :   }
    2063             :   /* LCOV_EXCL_LINE */
    2064           0 :   return 0;
    2065             : }
    2066             : 
    2067             : GEN
    2068        5605 : vecmax0(GEN x, GEN *pi)
    2069             : {
    2070        5605 :   long i, lx = lg(x), tx = typ(x);
    2071        5605 :   if (!is_matvec_t(tx) && tx != t_VECSMALL) return gcopy(x);
    2072        5591 :   if (lx==1) pari_err_DOMAIN("vecmax", "empty argument", "=", x,x);
    2073        5570 :   switch(typ(x))
    2074             :   {
    2075             :     case t_VEC: case t_COL:
    2076        5061 :       i = vecindexmax(x); if (pi) *pi = utoipos(i);
    2077        5061 :       return gcopy(gel(x,i));
    2078             :     case t_MAT: {
    2079         495 :       long j, i0 = 1, j0 = 1, lx2 = lgcols(x);
    2080             :       GEN s;
    2081         495 :       if (lx2 == 1) pari_err_DOMAIN("vecmax", "empty argument", "=", x,x);
    2082         488 :       s = gcoeff(x,i0,j0); i = 2;
    2083        1800 :       for (j=1; j<lx; j++,i=1)
    2084             :       {
    2085        1312 :         GEN c = gel(x,j);
    2086       24644 :         for (; i<lx2; i++)
    2087       23332 :           if (gcmp(gel(c,i),s) > 0) { s = gel(c,i); j0=j; i0=i; }
    2088             :       }
    2089         488 :       if (pi) *pi = mkvec2(utoipos(i0), utoipos(j0));
    2090         488 :       return gcopy(s);
    2091             :     }
    2092             :     case t_VECSMALL:
    2093          14 :       i = vecsmall_indexmax(x); if (pi) *pi = utoipos(i);
    2094          14 :       return stoi(x[i]);
    2095             :   }
    2096             :   return NULL;/*LCOV_EXCL_LINE*/
    2097             : }
    2098             : GEN
    2099       18474 : vecmin0(GEN x, GEN *pi)
    2100             : {
    2101       18474 :   long i, lx = lg(x), tx = typ(x);
    2102       18474 :   if (!is_matvec_t(tx) && tx != t_VECSMALL) return gcopy(x);
    2103       18460 :   if (lx==1) pari_err_DOMAIN("vecmin", "empty argument", "=", x,x);
    2104       18446 :   switch(typ(x))
    2105             :   {
    2106             :     case t_VEC: case t_COL:
    2107       18418 :       i = vecindexmin(x); if (pi) *pi = utoipos(i);
    2108       18418 :       return gcopy(gel(x,i));
    2109             :     case t_MAT: {
    2110          14 :       long j, i0 = 1, j0 = 1, lx2 = lgcols(x);
    2111             :       GEN s;
    2112          14 :       if (lx2 == 1) pari_err_DOMAIN("vecmin", "empty argument", "=", x,x);
    2113          14 :       s = gcoeff(x,i0,j0); i = 2;
    2114          42 :       for (j=1; j<lx; j++,i=1)
    2115             :       {
    2116          28 :         GEN c = gel(x,j);
    2117          70 :         for (; i<lx2; i++)
    2118          42 :           if (gcmp(gel(c,i),s) < 0) { s = gel(c,i); j0=j; i0=i; }
    2119             :       }
    2120          14 :       if (pi) *pi = mkvec2(utoipos(i0), utoipos(j0));
    2121          14 :       return gcopy(s);
    2122             :     }
    2123             :     case t_VECSMALL:
    2124          14 :       i = vecsmall_indexmin(x); if (pi) *pi = utoipos(i);
    2125          14 :       return stoi(x[i]);
    2126             :   }
    2127             :   return NULL;/*LCOV_EXCL_LINE*/
    2128             : }
    2129             : 
    2130             : GEN
    2131        2938 : vecmax(GEN x) { return vecmax0(x, NULL); }
    2132             : GEN
    2133       18397 : vecmin(GEN x) { return vecmin0(x, NULL); }
    2134             : 
    2135             : /*******************************************************************/
    2136             : /*                                                                 */
    2137             : /*                      AFFECT long --> GEN                        */
    2138             : /*         affect long s to GEN x. Useful for initialization.      */
    2139             : /*                                                                 */
    2140             : /*******************************************************************/
    2141             : 
    2142             : static void
    2143           0 : padicaff0(GEN x)
    2144             : {
    2145           0 :   if (signe(gel(x,4)))
    2146             :   {
    2147           0 :     x[1] = evalvalp(valp(x)+precp(x));
    2148           0 :     affsi(0,gel(x,4));
    2149             :   }
    2150           0 : }
    2151             : 
    2152             : void
    2153         966 : gaffsg(long s, GEN x)
    2154             : {
    2155         966 :   switch(typ(x))
    2156             :   {
    2157           0 :     case t_INT: affsi(s,x); break;
    2158         966 :     case t_REAL: affsr(s,x); break;
    2159           0 :     case t_INTMOD: modsiz(s,gel(x,1),gel(x,2)); break;
    2160           0 :     case t_FRAC: affsi(s,gel(x,1)); affsi(1,gel(x,2)); break;
    2161           0 :     case t_COMPLEX: gaffsg(s,gel(x,1)); gaffsg(0,gel(x,2)); break;
    2162             :     case t_PADIC: {
    2163             :       long vx;
    2164             :       GEN y;
    2165           0 :       if (!s) { padicaff0(x); break; }
    2166           0 :       vx = Z_pvalrem(stoi(s), gel(x,2), &y);
    2167           0 :       setvalp(x,vx); modiiz(y,gel(x,3),gel(x,4));
    2168           0 :       break;
    2169             :     }
    2170           0 :     case t_QUAD: gaffsg(s,gel(x,2)); gaffsg(0,gel(x,3)); break;
    2171           0 :     default: pari_err_TYPE2("=",stoi(s),x);
    2172             :   }
    2173         966 : }
    2174             : 
    2175             : /*******************************************************************/
    2176             : /*                                                                 */
    2177             : /*                     GENERIC AFFECTATION                         */
    2178             : /*         Affect the content of x to y, whenever possible         */
    2179             : /*                                                                 */
    2180             : /*******************************************************************/
    2181             : /* x PADIC, Y INT, return lift(x * Mod(1,Y)) */
    2182             : GEN
    2183        4417 : padic_to_Fp(GEN x, GEN Y) {
    2184        4417 :   pari_sp av = avma;
    2185        4417 :   GEN p = gel(x,2), z;
    2186        4417 :   long vy, vx = valp(x);
    2187        4417 :   if (!signe(Y)) pari_err_INV("padic_to_Fp",Y);
    2188        4417 :   vy = Z_pvalrem(Y,p, &z);
    2189        4417 :   if (vx < 0 || !gequal1(z)) pari_err_OP("",x, mkintmod(gen_1,Y));
    2190        4403 :   if (vx >= vy) { set_avma(av); return gen_0; }
    2191        4074 :   z = gel(x,4);
    2192        4074 :   if (!signe(z) || vy > vx + precp(x)) pari_err_OP("",x, mkintmod(gen_1,Y));
    2193        4074 :   if (vx) z = mulii(z, powiu(p,vx));
    2194        4074 :   return gerepileuptoint(av, remii(z, Y));
    2195             : }
    2196             : ulong
    2197          77 : padic_to_Fl(GEN x, ulong Y) {
    2198          77 :   GEN p = gel(x,2);
    2199             :   ulong u, z;
    2200          77 :   long vy, vx = valp(x);
    2201          77 :   vy = u_pvalrem(Y,p, &u);
    2202          77 :   if (vx < 0 || u != 1) pari_err_OP("",x, mkintmodu(1,Y));
    2203             :   /* Y = p^vy */
    2204          77 :   if (vx >= vy) return 0;
    2205          70 :   z = umodiu(gel(x,4), Y);
    2206          70 :   if (!z || vy > vx + precp(x)) pari_err_OP("",x, mkintmodu(1,Y));
    2207          70 :   if (vx) {
    2208           0 :     ulong pp = p[2];
    2209           0 :     z = Fl_mul(z, upowuu(pp,vx), Y); /* p^vx < p^vy = Y */
    2210             :   }
    2211          70 :   return z;
    2212             : }
    2213             : 
    2214             : static void
    2215           0 : croak(const char *s) {
    2216             :   char *t;
    2217           0 :   t = stack_sprintf("gaffect [overwriting universal object: %s]",s);
    2218           0 :   pari_err_BUG(t);
    2219           0 : }
    2220             : 
    2221             : void
    2222      199547 : gaffect(GEN x, GEN y)
    2223             : {
    2224      199547 :   long vx, i, lx, ly, tx = typ(x), ty = typ(y);
    2225             :   pari_sp av;
    2226             :   GEN p1, num, den;
    2227             : 
    2228      199547 :   if (tx == ty) switch(tx) {
    2229             :     case t_INT:
    2230      318576 :       if (!is_universal_constant(y)) { affii(x,y); return; }
    2231             :       /* y = gen_0, gnil, gen_1 or gen_2 */
    2232           0 :       if (y==gen_0)  croak("gen_0");
    2233           0 :       if (y==gen_1)  croak("gen_1");
    2234           0 :       if (y==gen_m1) croak("gen_m1");
    2235           0 :       if (y==gen_m2) croak("gen_m2");
    2236           0 :       if (y==gen_2)  croak("gen_2");
    2237           0 :       croak("gnil)");
    2238        4606 :     case t_REAL: affrr(x,y); return;
    2239             :     case t_INTMOD:
    2240           0 :       if (!dvdii(gel(x,1),gel(y,1))) pari_err_OP("",x,y);
    2241           0 :       modiiz(gel(x,2),gel(y,1),gel(y,2)); return;
    2242             :     case t_FRAC:
    2243           0 :       affii(gel(x,1),gel(y,1));
    2244           0 :       affii(gel(x,2),gel(y,2)); return;
    2245             :     case t_COMPLEX:
    2246        1820 :       gaffect(gel(x,1),gel(y,1));
    2247        1820 :       gaffect(gel(x,2),gel(y,2)); return;
    2248             :     case t_PADIC:
    2249           0 :       if (!equalii(gel(x,2),gel(y,2))) pari_err_OP("",x,y);
    2250           0 :       modiiz(gel(x,4),gel(y,3),gel(y,4));
    2251           0 :       setvalp(y,valp(x)); return;
    2252             :     case t_QUAD:
    2253           0 :       if (! ZX_equal(gel(x,1),gel(y,1))) pari_err_OP("",x,y);
    2254           0 :       affii(gel(x,2),gel(y,2));
    2255           0 :       affii(gel(x,3),gel(y,3)); return;
    2256             :     case t_VEC: case t_COL: case t_MAT:
    2257       72160 :       lx = lg(x); if (lx != lg(y)) pari_err_DIM("gaffect");
    2258       72160 :       for (i=1; i<lx; i++) gaffect(gel(x,i),gel(y,i));
    2259       72160 :       return;
    2260             :   }
    2261             : 
    2262             :   /* Various conversions. Avoid them, use specialized routines ! */
    2263             : 
    2264         966 :   if (!is_const_t(ty)) pari_err_TYPE2("=",x,y);
    2265         966 :   switch(tx)
    2266             :   {
    2267             :     case t_INT:
    2268           0 :       switch(ty)
    2269             :       {
    2270             :         case t_REAL:
    2271           0 :           affir(x,y); break;
    2272             : 
    2273             :         case t_INTMOD:
    2274           0 :           modiiz(x,gel(y,1),gel(y,2)); break;
    2275             : 
    2276             :         case t_COMPLEX:
    2277           0 :           gaffect(x,gel(y,1)); gaffsg(0,gel(y,2)); break;
    2278             : 
    2279             :         case t_PADIC:
    2280           0 :           if (!signe(x)) { padicaff0(y); break; }
    2281           0 :           av = avma;
    2282           0 :           setvalp(y, Z_pvalrem(x,gel(y,2),&p1));
    2283           0 :           affii(modii(p1,gel(y,3)), gel(y,4));
    2284           0 :           set_avma(av); break;
    2285             : 
    2286           0 :         case t_QUAD: gaffect(x,gel(y,2)); gaffsg(0,gel(y,3)); break;
    2287           0 :         default: pari_err_TYPE2("=",x,y);
    2288             :       }
    2289           0 :       break;
    2290             : 
    2291             :     case t_REAL:
    2292         966 :       switch(ty)
    2293             :       {
    2294         966 :         case t_COMPLEX: gaffect(x,gel(y,1)); gaffsg(0,gel(y,2)); break;
    2295           0 :         default: pari_err_TYPE2("=",x,y);
    2296             :       }
    2297         966 :       break;
    2298             : 
    2299             :     case t_FRAC:
    2300           0 :       switch(ty)
    2301             :       {
    2302           0 :         case t_REAL: rdiviiz(gel(x,1),gel(x,2), y); break;
    2303           0 :         case t_INTMOD: av = avma;
    2304           0 :           p1 = Fp_inv(gel(x,2),gel(y,1));
    2305           0 :           affii(modii(mulii(gel(x,1),p1),gel(y,1)), gel(y,2));
    2306           0 :           set_avma(av); break;
    2307           0 :         case t_COMPLEX: gaffect(x,gel(y,1)); gaffsg(0,gel(y,2)); break;
    2308             :         case t_PADIC:
    2309           0 :           if (!signe(gel(x,1))) { padicaff0(y); break; }
    2310           0 :           num = gel(x,1);
    2311           0 :           den = gel(x,2);
    2312           0 :           av = avma; vx = Z_pvalrem(num, gel(y,2), &num);
    2313           0 :           if (!vx) vx = -Z_pvalrem(den,gel(y,2),&den);
    2314           0 :           setvalp(y,vx);
    2315           0 :           p1 = mulii(num,Fp_inv(den,gel(y,3)));
    2316           0 :           affii(modii(p1,gel(y,3)), gel(y,4)); set_avma(av); break;
    2317           0 :         case t_QUAD: gaffect(x,gel(y,2)); gaffsg(0,gel(y,3)); break;
    2318           0 :         default: pari_err_TYPE2("=",x,y);
    2319             :       }
    2320           0 :       break;
    2321             : 
    2322             :     case t_COMPLEX:
    2323           0 :       if (!gequal0(gel(x,2))) pari_err_TYPE2("=",x,y);
    2324           0 :       gaffect(gel(x,1), y);
    2325           0 :       break;
    2326             : 
    2327             :     case t_PADIC:
    2328           0 :       switch(ty)
    2329             :       {
    2330             :         case t_INTMOD:
    2331           0 :           av = avma; affii(padic_to_Fp(x, gel(y,1)), gel(y,2));
    2332           0 :           set_avma(av); break;
    2333           0 :         default: pari_err_TYPE2("=",x,y);
    2334             :       }
    2335           0 :       break;
    2336             : 
    2337             :     case t_QUAD:
    2338           0 :       switch(ty)
    2339             :       {
    2340             :         case t_INT: case t_INTMOD: case t_FRAC: case t_PADIC:
    2341           0 :           pari_err_TYPE2("=",x,y);
    2342             : 
    2343             :         case t_REAL:
    2344           0 :           av = avma; affgr(quadtofp(x,realprec(y)), y); set_avma(av); break;
    2345             :         case t_COMPLEX:
    2346           0 :           ly = precision(y); if (!ly) pari_err_TYPE2("=",x,y);
    2347           0 :           av = avma; gaffect(quadtofp(x,ly), y); set_avma(av); break;
    2348           0 :         default: pari_err_TYPE2("=",x,y);
    2349             :       }
    2350           0 :     default: pari_err_TYPE2("=",x,y);
    2351             :   }
    2352             : }
    2353             : 
    2354             : /*******************************************************************/
    2355             : /*                                                                 */
    2356             : /*           CONVERSION QUAD --> REAL, COMPLEX OR P-ADIC           */
    2357             : /*                                                                 */
    2358             : /*******************************************************************/
    2359             : GEN
    2360         231 : quadtofp(GEN x, long prec)
    2361             : {
    2362         231 :   GEN b, mb2, c, z, Q, u = gel(x,2), v = gel(x,3);
    2363             :   pari_sp av;
    2364         231 :   if (prec < LOWDEFAULTPREC) prec = LOWDEFAULTPREC;
    2365         231 :   if (isintzero(v)) return cxcompotor(u, prec);
    2366         231 :   av = avma; Q = gel(x,1); c = gel(Q,2); b = gel(Q,3);
    2367         231 :   z = sqrtr_abs(itor(quad_disc(x), prec));
    2368         231 :   shiftr_inplace(z, -1);
    2369         231 :   mb2 = signe(b) ? real2n(-1, prec): NULL;
    2370         231 :   if (signe(c) > 0) /* c = -D/4 or (1-D)/4 */
    2371          35 :     z = mkcomplex(mb2? mb2: real_0(prec), z);
    2372         196 :   else if (mb2)
    2373         196 :     z = addrr(z, mb2);
    2374             :   /* z = (-b + sqrt(D)) / 2 */
    2375         231 :   return gerepileupto(av, gadd(u, gmul(v,z)));
    2376             : }
    2377             : 
    2378             : static GEN
    2379          28 : qtop(GEN x, GEN p, long d)
    2380             : {
    2381          28 :   GEN z, D, P, b, u = gel(x,2), v = gel(x,3);
    2382             :   pari_sp av;
    2383          28 :   if (gequal0(v)) return cvtop(u, p, d);
    2384          28 :   P = gel(x,1);
    2385          28 :   b = gel(P,3);
    2386          28 :   av = avma; D = quad_disc(x);
    2387          28 :   if (absequaliu(p,2)) d += 2;
    2388          28 :   z = Qp_sqrt(cvtop(D,p,d));
    2389          28 :   if (!z) pari_err_SQRTN("Qp_sqrt",D);
    2390          14 :   z = gmul2n(gsub(z, b), -1);
    2391             : 
    2392          14 :   z = gadd(u, gmul(v, z));
    2393          14 :   if (typ(z) != t_PADIC) /* t_INTMOD for t_QUAD of t_INTMODs... */
    2394           0 :     z = cvtop(z, p, d);
    2395          14 :   return gerepileupto(av, z);
    2396             : }
    2397             : static GEN
    2398          14 : ctop(GEN x, GEN p, long d)
    2399             : {
    2400          14 :   pari_sp av = avma;
    2401          14 :   GEN z, u = gel(x,1), v = gel(x,2);
    2402          14 :   if (isrationalzero(v)) return cvtop(u, p, d);
    2403          14 :   z = Qp_sqrt(cvtop(gen_m1, p, d - gvaluation(v, p))); /* = I */
    2404          14 :   if (!z) pari_err_SQRTN("Qp_sqrt",gen_m1);
    2405             : 
    2406          14 :   z = gadd(u, gmul(v, z));
    2407          14 :   if (typ(z) != t_PADIC) /* t_INTMOD for t_COMPLEX of t_INTMODs... */
    2408           0 :     z = cvtop(z, p, d);
    2409          14 :   return gerepileupto(av, z);
    2410             : }
    2411             : 
    2412             : /* cvtop2(stoi(s), y) */
    2413             : GEN
    2414           0 : cvstop2(long s, GEN y)
    2415             : {
    2416           0 :   GEN z, p = gel(y,2);
    2417           0 :   long v, d = signe(gel(y,4))? precp(y): 0;
    2418           0 :   if (!s) return zeropadic(p, d);
    2419           0 :   v = z_pvalrem(s, p, &s);
    2420           0 :   if (d <= 0) return zeropadic(p, v);
    2421           0 :   z = cgetg(5, t_PADIC);
    2422           0 :   z[1] = evalprecp(d) | evalvalp(v);
    2423           0 :   gel(z,2) = p;
    2424           0 :   gel(z,3) = gel(y,3);
    2425           0 :   gel(z,4) = modsi(s, gel(y,3)); return z;
    2426             : }
    2427             : 
    2428             : /* cvtop(x, gel(y,2), precp(y)), shallow */
    2429             : GEN
    2430     1686400 : cvtop2(GEN x, GEN y)
    2431             : {
    2432     1686400 :   GEN z, p = gel(y,2);
    2433     1686400 :   long v, d = signe(gel(y,4))? precp(y): 0;
    2434     1686400 :   switch(typ(x))
    2435             :   {
    2436             :     case t_INT:
    2437      938967 :       if (!signe(x)) return zeropadic(p, d);
    2438      938967 :       if (d <= 0) return zeropadic(p, Z_pval(x,p));
    2439      934270 :       v = Z_pvalrem(x, p, &x);
    2440      934190 :       z = cgetg(5, t_PADIC);
    2441      934262 :       z[1] = evalprecp(d) | evalvalp(v);
    2442      934264 :       gel(z,2) = p;
    2443      934264 :       gel(z,3) = gel(y,3);
    2444      934264 :       gel(z,4) = modii(x, gel(y,3)); return z;
    2445             : 
    2446             :     case t_INTMOD:
    2447           0 :       v = Z_pval(gel(x,1),p); if (v > d) v = d;
    2448           0 :       return cvtop(gel(x,2), p, v);
    2449             : 
    2450             :     case t_FRAC:
    2451             :     {
    2452             :       GEN num, den;
    2453      747398 :       if (d <= 0) return zeropadic(p, Q_pval(x,p));
    2454      746117 :       num = gel(x,1); v = Z_pvalrem(num, p, &num);
    2455      746117 :       den = gel(x,2); if (!v) v = -Z_pvalrem(den, p, &den);
    2456      746117 :       z = cgetg(5, t_PADIC);
    2457      746117 :       z[1] = evalprecp(d) | evalvalp(v);
    2458      746117 :       gel(z,2) = p;
    2459      746117 :       gel(z,3) = gel(y,3);
    2460      746117 :       if (!is_pm1(den)) num = mulii(num, Fp_inv(den, gel(y,3)));
    2461      746117 :       gel(z,4) = modii(num, gel(y,3)); return z;
    2462             :     }
    2463           7 :     case t_COMPLEX: return ctop(x, p, d);
    2464          28 :     case t_QUAD:    return qtop(x, p, d);
    2465             :   }
    2466           0 :   pari_err_TYPE("cvtop2",x);
    2467             :   return NULL; /* LCOV_EXCL_LINE */
    2468             : }
    2469             : 
    2470             : /* assume is_const_t(tx) */
    2471             : GEN
    2472      354698 : cvtop(GEN x, GEN p, long d)
    2473             : {
    2474             :   GEN z;
    2475             :   long v;
    2476             : 
    2477      354698 :   if (typ(p) != t_INT) pari_err_TYPE("cvtop",p);
    2478      354698 :   switch(typ(x))
    2479             :   {
    2480             :     case t_INT:
    2481       39539 :       if (!signe(x)) return zeropadic(p, d);
    2482       38335 :       if (d <= 0) return zeropadic(p, Z_pval(x,p));
    2483       38328 :       v = Z_pvalrem(x, p, &x);
    2484       38328 :       z = cgetg(5, t_PADIC);
    2485       38328 :       z[1] = evalprecp(d) | evalvalp(v);
    2486       38328 :       gel(z,2) = icopy(p);
    2487       38328 :       gel(z,3) = powiu(p, d);
    2488       38327 :       gel(z,4) = modii(x, gel(z,3)); return z; /* not memory-clean */
    2489             : 
    2490             :     case t_INTMOD:
    2491          28 :       v = Z_pval(gel(x,1),p); if (v > d) v = d;
    2492          28 :       return cvtop(gel(x,2), p, v);
    2493             : 
    2494             :     case t_FRAC:
    2495             :     {
    2496             :       GEN num, den;
    2497      157282 :       if (d <= 0) return zeropadic(p, Q_pval(x,p));
    2498      157282 :       num = gel(x,1); v = Z_pvalrem(num, p, &num);
    2499      157282 :       den = gel(x,2); if (!v) v = -Z_pvalrem(den, p, &den);
    2500      157282 :       z = cgetg(5, t_PADIC);
    2501      157282 :       z[1] = evalprecp(d) | evalvalp(v);
    2502      157282 :       gel(z,2) = icopy(p);
    2503      157282 :       gel(z,3) = powiu(p, d);
    2504      157282 :       if (!is_pm1(den)) num = mulii(num, Fp_inv(den, gel(z,3)));
    2505      157282 :       gel(z,4) = modii(num, gel(z,3)); return z; /* not memory-clean */
    2506             :     }
    2507           7 :     case t_COMPLEX: return ctop(x, p, d);
    2508             :     case t_PADIC:
    2509      157842 :       p = gel(x,2); /* override */
    2510      157842 :       if (!signe(gel(x,4))) return zeropadic(p, d);
    2511      157842 :       z = cgetg(5,t_PADIC);
    2512      157842 :       z[1] = x[1]; setprecp(z,d);
    2513      157842 :       gel(z,2) = icopy(p);
    2514      157842 :       gel(z,3) = powiu(p, d);
    2515      157842 :       gel(z,4) = modii(gel(x,4), gel(z,3)); return z;
    2516             : 
    2517           0 :     case t_QUAD: return qtop(x, p, d);
    2518             :   }
    2519           0 :   pari_err_TYPE("cvtop",x);
    2520             :   return NULL; /* LCOV_EXCL_LINE */
    2521             : }
    2522             : 
    2523             : GEN
    2524          70 : gcvtop(GEN x, GEN p, long r)
    2525             : {
    2526             :   long i, lx;
    2527             :   GEN y;
    2528             : 
    2529          70 :   switch(typ(x))
    2530             :   {
    2531             :     case t_POL: case t_SER:
    2532          21 :       y = cgetg_copy(x, &lx); y[1] = x[1];
    2533          21 :       for (i=2; i<lx; i++) gel(y,i) = gcvtop(gel(x,i),p,r);
    2534          21 :       return y;
    2535             :     case t_POLMOD: case t_RFRAC: case t_VEC: case t_COL: case t_MAT:
    2536           0 :       y = cgetg_copy(x, &lx);
    2537           0 :       for (i=1; i<lx; i++) gel(y,i) = gcvtop(gel(x,i),p,r);
    2538           0 :       return y;
    2539             :   }
    2540          49 :   return cvtop(x,p,r);
    2541             : }
    2542             : 
    2543             : long
    2544   117973383 : gexpo_safe(GEN x)
    2545             : {
    2546   117973383 :   long tx = typ(x), lx, e, f, i;
    2547             : 
    2548   117973383 :   switch(tx)
    2549             :   {
    2550             :     case t_INT:
    2551    16422486 :       return expi(x);
    2552             : 
    2553             :     case t_FRAC:
    2554      313310 :       return expi(gel(x,1)) - expi(gel(x,2));
    2555             : 
    2556             :     case t_REAL:
    2557    71343151 :       return expo(x);
    2558             : 
    2559             :     case t_COMPLEX:
    2560    19714226 :       e = gexpo(gel(x,1));
    2561    19714226 :       f = gexpo(gel(x,2)); return maxss(e, f);
    2562             : 
    2563             :     case t_QUAD: {
    2564          77 :       GEN p = gel(x,1); /* mod = X^2 + {0,1}* X - {D/4, (1-D)/4})*/
    2565          77 :       long d = 1 + expi(gel(p,2))/2; /* ~ expo(sqrt(D)) */
    2566          77 :       e = gexpo(gel(x,2));
    2567          77 :       f = gexpo(gel(x,3)) + d; return maxss(e, f);
    2568             :     }
    2569             :     case t_POL: case t_SER:
    2570     9673243 :       lx = lg(x); f = -(long)HIGHEXPOBIT;
    2571     9673243 :       for (i=2; i<lx; i++) { e=gexpo(gel(x,i)); if (e>f) f=e; }
    2572     9673243 :       return f;
    2573             :     case t_VEC: case t_COL: case t_MAT:
    2574      506841 :       lx = lg(x); f = -(long)HIGHEXPOBIT;
    2575      506841 :       for (i=1; i<lx; i++) { e=gexpo(gel(x,i)); if (e>f) f=e; }
    2576      506841 :       return f;
    2577             :   }
    2578          49 :   return -1-(long)HIGHEXPOBIT;
    2579             : }
    2580             : long
    2581   117932013 : gexpo(GEN x)
    2582             : {
    2583   117932013 :   long e = gexpo_safe(x);
    2584   117932013 :   if (e < -(long)HIGHEXPOBIT) pari_err_TYPE("gexpo",x);
    2585   117932006 :   return e;
    2586             : }
    2587             : GEN
    2588        4795 : gpexponent(GEN x)
    2589             : {
    2590        4795 :   long e = gexpo(x);
    2591        4795 :   return e == -(long)HIGHEXPOBIT? mkmoo(): stoi(e);
    2592             : }
    2593             : 
    2594             : long
    2595           7 : sizedigit(GEN x)
    2596             : {
    2597           7 :   return gequal0(x)? 0: (long) ((gexpo(x)+1) * LOG10_2) + 1;
    2598             : }
    2599             : 
    2600             : /* normalize series. avma is not updated */
    2601             : GEN
    2602     7351156 : normalize(GEN x)
    2603             : {
    2604     7351156 :   long i, lx = lg(x), vx=varn(x), vp=valp(x);
    2605             :   GEN y, z;
    2606             : 
    2607     7351156 :   if (typ(x) != t_SER) pari_err_TYPE("normalize",x);
    2608     7351156 :   if (lx == 2) { setsigne(x,0); return x; }
    2609     7350792 :   if (lx == 3) {
    2610      168731 :     z = gel(x,2);
    2611      168731 :     if (!gequal0(z)) { setsigne(x,1); return x; }
    2612       21790 :     if (isrationalzero(z)) return zeroser(vx,vp+1);
    2613        3044 :     if (isexactzero(z)) {
    2614             :       /* dangerous case: already normalized ? */
    2615          21 :       if (!signe(x)) return x;
    2616          14 :       setvalp(x,vp+1); /* no: normalize */
    2617             :     }
    2618        3037 :     setsigne(x,0); return x;
    2619             :   }
    2620     7461533 :   for (i=2; i<lx; i++)
    2621     7414640 :     if (! isrationalzero(gel(x,i))) break;
    2622     7182061 :   if (i == lx) return zeroser(vx,lx-2+vp);
    2623     7135168 :   z = gel(x,i);
    2624     7135168 :   while (i<lx && isexactzero(gel(x,i))) i++;
    2625     7135168 :   if (i == lx)
    2626             :   {
    2627         840 :     i -= 3; y = x + i;
    2628         840 :     stackdummy((pari_sp)y, (pari_sp)x);
    2629         840 :     gel(y,2) = z;
    2630         840 :     y[1] = evalsigne(0) | evalvalp(lx-2+vp) | evalvarn(vx);
    2631         840 :     y[0] = evaltyp(t_SER) | _evallg(3);
    2632         840 :     return y;
    2633             :   }
    2634             : 
    2635     7134328 :   i -= 2; y = x + i; lx -= i;
    2636     7134328 :   y[1] = evalsigne(1) | evalvalp(vp+i) | evalvarn(vx);
    2637     7134328 :   y[0] = evaltyp(t_SER) | evallg(lx);
    2638             : 
    2639     7134328 :   stackdummy((pari_sp)y, (pari_sp)x);
    2640     7156065 :   for (i = 2; i < lx; i++)
    2641     7155122 :     if (!gequal0(gel(y, i))) return y;
    2642         943 :   setsigne(y, 0); return y;
    2643             : }
    2644             : 
    2645             : GEN
    2646           0 : normalizepol_approx(GEN x, long lx)
    2647             : {
    2648             :   long i;
    2649           0 :   for (i = lx-1; i>1; i--)
    2650           0 :     if (! gequal0(gel(x,i))) break;
    2651           0 :   stackdummy((pari_sp)(x + lg(x)), (pari_sp)(x + i+1));
    2652           0 :   setlg(x, i+1); setsigne(x, i!=1); return x;
    2653             : }
    2654             : 
    2655             : GEN
    2656   234037579 : normalizepol_lg(GEN x, long lx)
    2657             : {
    2658   234037579 :   long i, LX = 0;
    2659   234037579 :   GEN KEEP = NULL;
    2660             : 
    2661   316745175 :   for (i = lx-1; i>1; i--)
    2662             :   {
    2663   291086241 :     GEN z = gel(x,i);
    2664   291086241 :     if (! gequal0(z) ) {
    2665   208378775 :       if (!LX) LX = i+1;
    2666   208378775 :       stackdummy((pari_sp)(x + lg(x)), (pari_sp)(x + LX));
    2667   208382043 :       x[0] = evaltyp(t_POL) | evallg(LX);
    2668   208385078 :       setsigne(x,1); return x;
    2669    82707596 :     } else if (!isexactzero(z)) {
    2670      228051 :       if (!LX) LX = i+1; /* to be kept as leading coeff */
    2671    82479546 :     } else if (!isrationalzero(z))
    2672      689486 :       KEEP = z; /* to be kept iff all other coeffs are exact 0s */
    2673             :   }
    2674    25658934 :   if (!LX) {
    2675    25590561 :     if (KEEP) { /* e.g. Pol(Mod(0,2)) */
    2676      344305 :       gel(x,2) = KEEP;
    2677      344305 :       LX = 3;
    2678             :     } else
    2679    25246256 :       LX = 2; /* Pol(0) */
    2680             :   }
    2681    25658934 :   stackdummy((pari_sp)(x + lg(x)), (pari_sp)(x + LX));
    2682    25658933 :   x[0] = evaltyp(t_POL) | evallg(LX);
    2683    25658933 :   setsigne(x,0); return x;
    2684             : }
    2685             : 
    2686             : /* normalize polynomial x in place */
    2687             : GEN
    2688    11841961 : normalizepol(GEN x)
    2689             : {
    2690    11841961 :   return normalizepol_lg(x, lg(x));
    2691             : }
    2692             : 
    2693             : int
    2694     4969726 : gsigne(GEN x)
    2695             : {
    2696     4969726 :   switch(typ(x))
    2697             :   {
    2698     4736857 :     case t_INT: case t_REAL: return signe(x);
    2699      232239 :     case t_FRAC: return signe(gel(x,1));
    2700             :     case t_QUAD:
    2701             :     {
    2702         623 :       pari_sp av = avma;
    2703         623 :       GEN T = gel(x,1), a = gel(x,2), b = gel(x,3);
    2704             :       long sa, sb;
    2705         623 :       if (signe(gel(T,2)) > 0) break;
    2706         609 :       a = gmul2n(a,1);
    2707         609 :       if (signe(gel(T,3))) a = gadd(a,b);
    2708             :       /* a + b sqrt(D) > 0 ? */
    2709         609 :       sa = gsigne(a);
    2710         609 :       sb = gsigne(b); if (sa == sb) return gc_int(av,sa);
    2711         224 :       if (sa == 0) return gc_int(av,sb);
    2712         217 :       if (sb == 0) return gc_int(av,sa);
    2713             :       /* different signs, take conjugate expression */
    2714         210 :       sb = gsigne(gsub(gsqr(a), gmul(quad_disc(x), gsqr(b))));
    2715         210 :       return gc_int(av, sb*sa);
    2716             :     }
    2717           7 :     case t_INFINITY: return inf_get_sign(x);
    2718             :   }
    2719          14 :   pari_err_TYPE("gsigne",x);
    2720             :   return 0; /* LCOV_EXCL_LINE */
    2721             : }
    2722             : 
    2723             : /*******************************************************************/
    2724             : /*                                                                 */
    2725             : /*                              LISTS                              */
    2726             : /*                                                                 */
    2727             : /*******************************************************************/
    2728             : /* make sure L can hold l elements, at least doubling the previous max number
    2729             :  * of components. */
    2730             : static void
    2731      786275 : ensure_nb(GEN L, long l)
    2732             : {
    2733      786275 :   long nmax = list_nmax(L), i, lw;
    2734             :   GEN v, w;
    2735      786275 :   if (l <= nmax) return;
    2736         399 :   if (nmax)
    2737             :   {
    2738         273 :     nmax <<= 1;
    2739         273 :     if (l > nmax) nmax = l;
    2740         273 :     w = list_data(L); lw = lg(w);
    2741         273 :     v = newblock(nmax+1);
    2742         273 :     v[0] = w[0];
    2743         273 :     for (i=1; i < lw; i++) gel(v,i) = gel(w, i);
    2744         273 :     killblock(w);
    2745             :   }
    2746             :   else /* unallocated */
    2747             :   {
    2748         126 :     nmax = 32;
    2749         126 :     if (list_data(L))
    2750           0 :       pari_err(e_MISC, "store list in variable before appending elements");
    2751         126 :     v = newblock(nmax+1);
    2752         126 :     v[0] = evaltyp(t_VEC) | _evallg(1);
    2753             :   }
    2754         399 :   list_data(L) = v;
    2755         399 :   L[1] = evaltyp(list_typ(L))|evallg(nmax);
    2756             : }
    2757             : 
    2758             : void
    2759           7 : listkill(GEN L)
    2760             : {
    2761             : 
    2762           7 :   if (typ(L) != t_LIST) pari_err_TYPE("listkill",L);
    2763           7 :   if (list_nmax(L)) {
    2764           7 :     GEN v = list_data(L);
    2765           7 :     long i, l = lg(v);
    2766           7 :     for (i=1; i<l; i++) gunclone_deep(gel(v,i));
    2767           7 :     killblock(v);
    2768           7 :     L[1] = evaltyp(list_typ(L));
    2769           7 :     list_data(L) = NULL;
    2770             :   }
    2771           7 : }
    2772             : 
    2773             : GEN
    2774        1401 : mklist_typ(long t)
    2775             : {
    2776        1401 :   GEN L = cgetg(3,t_LIST);
    2777        1401 :   L[1] = evaltyp(t);
    2778        1401 :   list_data(L) = NULL; return L;
    2779             : }
    2780             : 
    2781             : GEN
    2782        1345 : mklist(void)
    2783             : {
    2784        1345 :   return mklist_typ(t_LIST_RAW);
    2785             : }
    2786             : 
    2787             : GEN
    2788          49 : mkmap(void)
    2789             : {
    2790          49 :   return mklist_typ(t_LIST_MAP);
    2791             : }
    2792             : 
    2793             : /* return a list with single element x, allocated on stack */
    2794             : GEN
    2795          49 : mklistcopy(GEN x)
    2796             : {
    2797          49 :   GEN y = mklist();
    2798          49 :   list_data(y) = mkveccopy(x);
    2799          49 :   return y;
    2800             : }
    2801             : 
    2802             : GEN
    2803           7 : listcreate_gp(long n)
    2804             : {
    2805           7 :   (void) n; return mklist();
    2806             : }
    2807             : 
    2808             : GEN
    2809      751429 : listput(GEN L, GEN x, long index)
    2810             : {
    2811             :   long l;
    2812             :   GEN z;
    2813             : 
    2814      751429 :   if (index < 0) pari_err_COMPONENT("listput", "<", gen_0, stoi(index));
    2815      751422 :   z = list_data(L);
    2816      751422 :   l = z? lg(z): 1;
    2817             : 
    2818      751422 :   x = gclone(x);
    2819      751422 :   if (!index || index >= l)
    2820             :   {
    2821      751268 :     ensure_nb(L, l);
    2822      751268 :     z = list_data(L); /* it may change ! */
    2823      751268 :     index = l;
    2824      751268 :     l++;
    2825             :   } else
    2826         154 :     gunclone_deep( gel(z, index) );
    2827      751422 :   gel(z,index) = x;
    2828      751422 :   z[0] = evaltyp(t_VEC) | evallg(l); /*must be after gel(z,index) is set*/
    2829      751422 :   return gel(z,index);
    2830             : }
    2831             : 
    2832             : GEN
    2833      700266 : listput0(GEN L, GEN x, long index)
    2834             : {
    2835      700266 :   if (typ(L) != t_LIST || list_typ(L) != t_LIST_RAW)
    2836          14 :     pari_err_TYPE("listput",L);
    2837      700252 :   return listput(L, x, index);
    2838             : }
    2839             : 
    2840             : GEN
    2841       35028 : listinsert(GEN L, GEN x, long index)
    2842             : {
    2843             :   long l, i;
    2844             :   GEN z;
    2845             : 
    2846       35028 :   if (typ(L) != t_LIST || list_typ(L) != t_LIST_RAW)
    2847          14 :     pari_err_TYPE("listinsert",L);
    2848       35014 :   z = list_data(L); l = z? lg(z): 1;
    2849       35014 :   if (index <= 0) pari_err_COMPONENT("listinsert", "<=", gen_0, stoi(index));
    2850       35007 :   if (index > l) index = l;
    2851       35007 :   ensure_nb(L, l);
    2852       35007 :   BLOCK_SIGINT_START
    2853       35007 :   z = list_data(L);
    2854       35007 :   for (i=l; i > index; i--) gel(z,i) = gel(z,i-1);
    2855       35007 :   z[0] = evaltyp(t_VEC) | evallg(l+1);
    2856       35007 :   gel(z,index) = gclone(x);
    2857       35007 :   BLOCK_SIGINT_END
    2858       35007 :   return gel(z,index);
    2859             : }
    2860             : 
    2861             : void
    2862       21910 : listpop(GEN L, long index)
    2863             : {
    2864             :   long l, i;
    2865             :   GEN z;
    2866             : 
    2867       21910 :   if (typ(L) != t_LIST) pari_err_TYPE("listinsert",L);
    2868       21910 :   if (index < 0) pari_err_COMPONENT("listpop", "<", gen_0, stoi(index));
    2869       21910 :   z = list_data(L);
    2870       21910 :   if (!z || (l = lg(z)-1) == 0) return;
    2871             : 
    2872       21896 :   if (!index || index > l) index = l;
    2873       21896 :   BLOCK_SIGINT_START
    2874       21896 :   gunclone_deep( gel(z, index) );
    2875       21896 :   z[0] = evaltyp(t_VEC) | evallg(l);
    2876       21896 :   for (i=index; i < l; i++) z[i] = z[i+1];
    2877       21896 :   BLOCK_SIGINT_END
    2878             : }
    2879             : 
    2880             : void
    2881          49 : listpop0(GEN L, long index)
    2882             : {
    2883          49 :   if (typ(L) != t_LIST || list_typ(L) != t_LIST_RAW)
    2884          14 :     pari_err_TYPE("listpop",L);
    2885          35 :   listpop(L, index);
    2886          35 : }
    2887             : 
    2888             : /* return a copy fully allocated on stack. gclone from changevalue is
    2889             :  * supposed to malloc() it */
    2890             : GEN
    2891         627 : gtolist(GEN x)
    2892             : {
    2893             :   GEN y;
    2894             : 
    2895         627 :   if (!x) return mklist();
    2896         308 :   switch(typ(x))
    2897             :   {
    2898             :     case t_VEC: case t_COL:
    2899         252 :       y = mklist();
    2900         252 :       if (lg(x) == 1) return y;
    2901         238 :       list_data(y) = gcopy(x);
    2902         238 :       settyp(list_data(y), t_VEC);
    2903         238 :       return y;
    2904             :     case t_LIST:
    2905           7 :       y = mklist();
    2906           7 :       list_data(y) = list_data(x)? gcopy(list_data(x)): NULL;
    2907           7 :       return y;
    2908             :     default:
    2909          49 :       return mklistcopy(x);
    2910             :   }
    2911             : }
    2912             : 
    2913             : void
    2914          21 : listsort(GEN L, long flag)
    2915             : {
    2916             :   long i, l;
    2917          21 :   pari_sp av = avma;
    2918             :   GEN perm, v, vnew;
    2919             : 
    2920          21 :   if (typ(L) != t_LIST) pari_err_TYPE("listsort",L);
    2921          21 :   v = list_data(L); l = v? lg(v): 1;
    2922          21 :   if (l < 3) return;
    2923          21 :   if (flag)
    2924             :   {
    2925             :     long lnew;
    2926          14 :     perm = gen_indexsort_uniq(L, (void*)&cmp_universal, cmp_nodata);
    2927          14 :     lnew = lg(perm); /* may have changed since 'uniq' */
    2928          14 :     vnew = cgetg(lnew,t_VEC);
    2929          56 :     for (i=1; i<lnew; i++) {
    2930          42 :       long c = perm[i];
    2931          42 :       gel(vnew,i) = gel(v,c);
    2932          42 :       gel(v,c) = NULL;
    2933             :     }
    2934          14 :     if (l != lnew) { /* was shortened */
    2935         105 :       for (i=1; i<l; i++)
    2936          91 :         if (gel(v,i)) gunclone_deep(gel(v,i));
    2937          14 :       l = lnew;
    2938             :     }
    2939             :   }
    2940             :   else
    2941             :   {
    2942           7 :     perm = gen_indexsort(L, (void*)&cmp_universal, cmp_nodata);
    2943           7 :     vnew = cgetg(l,t_VEC);
    2944           7 :     for (i=1; i<l; i++) gel(vnew,i) = gel(v,perm[i]);
    2945             :   }
    2946          21 :   for (i=1; i<l; i++) gel(v,i) = gel(vnew,i);
    2947          21 :   v[0] = vnew[0]; set_avma(av);
    2948             : }

Generated by: LCOV version 1.13