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 25406-bf255ab81b) Lines: 1509 1723 87.6 %
Date: 2020-06-04 05:59:24 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      885473 : map_proto_lG(long (*f)(GEN), GEN x)
      43             : {
      44      885473 :   if (is_matvec_t(typ(x)))
      45             :   {
      46             :     long lx, i;
      47          28 :     GEN y = cgetg_copy(x, &lx);
      48         112 :     for (i=1; i<lx; i++) gel(y,i) = map_proto_lG(f, gel(x,i));
      49          28 :     return y;
      50             :   }
      51      869489 :   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          35 :     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      589527 : _domul(void *data, GEN x, GEN y)
      69             : {
      70      589527 :   GEN (*mul)(GEN,GEN)=(GEN (*)(GEN,GEN)) data;
      71      589527 :   return mul(x,y);
      72             : }
      73             : 
      74             : GEN
      75      539119 : gassoc_proto(GEN (*f)(GEN,GEN), GEN x, GEN y)
      76             : {
      77      539119 :   if (!y)
      78             :   {
      79      539119 :     pari_sp av = avma;
      80      539119 :     switch(typ(x))
      81             :     {
      82          21 :       case t_LIST:
      83          21 :         x = list_data(x); if (!x) return gen_1;
      84             :       case t_VEC:
      85      539105 :       case t_COL: break;
      86           7 :       default: pari_err_TYPE("association",x);
      87             :     }
      88      539105 :     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     6052725 : cgetp(GEN x)
     100             : {
     101     6052725 :   GEN y = cgetg(5,t_PADIC);
     102     6052718 :   y[1] = (x[1]&PRECPBITS) | _evalvalp(0);
     103     6052718 :   gel(y,2) = icopy(gel(x,2));
     104     6052731 :   gel(y,3) = icopy(gel(x,3));
     105     6052736 :   gel(y,4) = cgeti(lgefint(gel(x,3))); return y;
     106             : }
     107             : 
     108             : /*******************************************************************/
     109             : /*                                                                 */
     110             : /*                            SIZES                                */
     111             : /*                                                                 */
     112             : /*******************************************************************/
     113             : 
     114             : long
     115     4984842 : glength(GEN x)
     116             : {
     117     4984842 :   long tx = typ(x);
     118     4984842 :   switch(tx)
     119             :   {
     120          84 :     case t_INT:  return lgefint(x)-2;
     121          21 :     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     4984611 :   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          42 :     case t_INT:
     158          42 :       return itos(x);
     159           7 :     case t_REAL:
     160           7 :       return (long)(rtodbl(x) + 0.5);
     161           7 :     case t_FRAC:
     162           7 :     { pari_sp av = avma; return gc_long(av, itos(ground(x))); }
     163           7 :     case t_COMPLEX:
     164           7 :       if (gequal0(gel(x,2))) return gtolong(gel(x,1)); break;
     165           7 :     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   213999897 : isexactzero(GEN g)
     179             : {
     180             :   long i, lx;
     181   213999897 :   switch (typ(g))
     182             :   {
     183   171738857 :     case t_INT:
     184   171738857 :       return !signe(g);
     185     1058448 :     case t_INTMOD:
     186     1058448 :       return !signe(gel(g,2));
     187     3197537 :     case t_COMPLEX:
     188     3197537 :       return isexactzero(gel(g,1)) && isexactzero(gel(g,2));
     189     8107292 :     case t_FFELT:
     190     8107292 :       return FF_equal0(g);
     191         504 :     case t_QUAD:
     192         504 :       return isexactzero(gel(g,2)) && isexactzero(gel(g,3));
     193      698867 :     case t_POLMOD:
     194      698867 :       return isexactzero(gel(g,2));
     195    11538582 :     case t_POL:
     196    11538582 :       lx = lg(g); /* cater for Mod(0,2)*x^0 */
     197    11538582 :       return lx == 2 || (lx == 3 && isexactzero(gel(g,2)));
     198      461143 :     case t_RFRAC:
     199      461143 :       return isexactzero(gel(g,1)); /* may occur: Mod(0,2)/x */
     200       14672 :     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    17183995 :   return 0;
     206             : }
     207             : GEN
     208    56364568 : gisexactzero(GEN g)
     209             : {
     210             :   long i, lx;
     211             :   GEN a, b;
     212    56364568 :   switch (typ(g))
     213             :   {
     214    16416215 :     case t_INT:
     215    16416215 :       return !signe(g)? g: NULL;
     216    10419206 :     case t_INTMOD:
     217    10419206 :       return !signe(gel(g,2))? g: NULL;
     218        2562 :     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       15232 :     case t_FFELT:
     223       15232 :       return FF_equal0(g)? g: NULL;
     224         518 :     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       36576 :     case t_POLMOD:
     229       36576 :       return gisexactzero(gel(g,2));
     230    28110052 :     case t_POL:
     231    28110052 :       lx = lg(g); /* cater for Mod(0,2)*x^0 */
     232    28110052 :       if (lx == 2) return gen_0;
     233    22777863 :       if (lx == 3) return gisexactzero(gel(g,2));
     234    19019242 :       return NULL;
     235     1193940 :     case t_RFRAC:
     236     1193940 :       return gisexactzero(gel(g,1)); /* may occur: Mod(0,2)/x */
     237           0 :     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      170267 :   return NULL;
     248             : }
     249             : 
     250             : int
     251   258480262 : isrationalzero(GEN g)
     252             : {
     253             :   long i;
     254   258480262 :   switch (typ(g))
     255             :   {
     256   161075547 :     case t_INT:
     257   161075547 :       return !signe(g);
     258     9398348 :     case t_COMPLEX:
     259     9398348 :       return isintzero(gel(g,1)) && isintzero(gel(g,2));
     260        1449 :     case t_QUAD:
     261        1449 :       return isintzero(gel(g,2)) && isintzero(gel(g,3));
     262      888189 :     case t_POLMOD:
     263      888189 :       return isrationalzero(gel(g,2));
     264    21602224 :     case t_POL: return lg(g) == 2;
     265         126 :     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    65514379 :   return 0;
     271             : }
     272             : 
     273             : int
     274   720039715 : gequal0(GEN x)
     275             : {
     276   720039715 :   switch(typ(x))
     277             :   {
     278   655785997 :     case t_INT: case t_REAL: case t_POL: case t_SER:
     279   655785997 :       return !signe(x);
     280             : 
     281     3499372 :     case t_INTMOD:
     282     3499372 :       return !signe(gel(x,2));
     283             : 
     284      577162 :     case t_FFELT:
     285      577162 :       return FF_equal0(x);
     286             : 
     287    26292298 :     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    26292298 :       if (gequal0(gel(x,1)))
     292             :       {
     293     5447446 :         if (gequal0(gel(x,2))) return 1;
     294     5380432 :         if (typ(gel(x,1))!=t_REAL || typ(gel(x,2))!=t_REAL) return 0;
     295       79519 :         return (expo(gel(x,1))>=expo(gel(x,2)));
     296             :       }
     297    20845032 :       if (gequal0(gel(x,2)))
     298             :       {
     299      555348 :         if (typ(gel(x,1))!=t_REAL || typ(gel(x,2))!=t_REAL) return 0;
     300      530684 :         return (expo(gel(x,2))>=expo(gel(x,1)));
     301             :       }
     302    20289977 :       return 0;
     303             : 
     304      783330 :     case t_PADIC:
     305      783330 :       return !signe(gel(x,4));
     306             : 
     307        1575 :     case t_QUAD:
     308        1575 :       return gequal0(gel(x,2)) && gequal0(gel(x,3));
     309             : 
     310     8522899 :     case t_POLMOD:
     311     8522899 :       return gequal0(gel(x,2));
     312             : 
     313     5852980 :     case t_RFRAC:
     314     5852980 :       return gequal0(gel(x,1));
     315             : 
     316     4219561 :     case t_VEC: case t_COL: case t_MAT:
     317             :     {
     318             :       long i;
     319     6437279 :       for (i=lg(x)-1; i; i--)
     320     3449623 :         if (!gequal0(gel(x,i))) return 0;
     321     2987656 :       return 1;
     322             :     }
     323             :   }
     324    14504541 :   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    13582971 : is_monomial_test(GEN x, long v, int(*test)(GEN))
     332             : {
     333             :   long d, i, l;
     334    13582971 :   if (!signe(x)) return (typ(x) == t_SER && v <= 0);
     335    13514414 :   if (v > 0) return 0;
     336    13514400 :   l = lg(x); d = 2-v;
     337    13514400 :   if (l <= d) return 0;
     338             :   /* 2 <= d < l */
     339    13514400 :   if (!test(gel(x,d))) return 0;
     340     3946433 :   for (i = 2; i < d; i++)
     341          14 :     if (!gequal0(gel(x,i))) return 0;
     342     4576828 :   for (i = d+1; i < l; i++)
     343     2191406 :     if (!gequal0(gel(x,i))) return 0;
     344     2385422 :   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   161582557 : gequal1(GEN x)
     374             : {
     375   161582557 :   switch(typ(x))
     376             :   {
     377   145197778 :     case t_INT:
     378   145197778 :       return equali1(x);
     379             : 
     380       74067 :     case t_REAL:
     381             :     {
     382       74067 :       long s = signe(x);
     383       74067 :       if (!s) return expo(x) >= 0;
     384       73388 :       return s > 0 ? absrnz_equal1(x): 0;
     385             :     }
     386      565227 :     case t_INTMOD:
     387      565227 :       return is_pm1(gel(x,2)) || is_pm1(gel(x,1));
     388      319474 :     case t_POLMOD:
     389      319474 :       return gequal1(gel(x,2)) || gequal1(gel(x,1));
     390             : 
     391       15533 :     case t_FFELT:
     392       15533 :       return FF_equal1(x);
     393             : 
     394      601745 :     case t_FRAC:
     395      601745 :       return 0;
     396             : 
     397       21012 :     case t_COMPLEX:
     398       21012 :       return gequal1(gel(x,1)) && gequal0(gel(x,2));
     399             : 
     400      154608 :     case t_PADIC:
     401      154608 :       return !valp(x) && gequal1(gel(x,4));
     402             : 
     403          42 :     case t_QUAD:
     404          42 :       return gequal1(gel(x,2)) && gequal0(gel(x,3));
     405             : 
     406    13582698 :     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          32 :   return 0;
     414             : }
     415             : 
     416             : /* returns 1 whenever the x = -1, 0 otherwise */
     417             : int
     418      130733 : gequalm1(GEN x)
     419             : {
     420             :   pari_sp av;
     421             :   GEN p1;
     422             : 
     423      130733 :   switch(typ(x))
     424             :   {
     425      121990 :     case t_INT:
     426      121990 :       return equalim1(x);
     427             : 
     428        6440 :     case t_REAL:
     429             :     {
     430        6440 :       long s = signe(x);
     431        6440 :       if (!s) return expo(x) >= 0;
     432        5838 :       return s < 0 ? absrnz_equal1(x): 0;
     433             :     }
     434          21 :     case t_INTMOD:
     435          21 :       av = avma; return gc_bool(av, equalii(addui(1,gel(x,2)), gel(x,1)));
     436             : 
     437          28 :     case t_FRAC:
     438          28 :       return 0;
     439             : 
     440          42 :     case t_FFELT:
     441          42 :       return FF_equalm1(x);
     442             : 
     443        1925 :     case t_COMPLEX:
     444        1925 :       return gequalm1(gel(x,1)) && gequal0(gel(x,2));
     445             : 
     446           7 :     case t_QUAD:
     447           7 :       return gequalm1(gel(x,2)) && gequal0(gel(x,3));
     448             : 
     449           7 :     case t_PADIC:
     450           7 :       av = avma; return gc_bool(av, equalii(addui(1,gel(x,4)), gel(x,3)));
     451             : 
     452          35 :     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          21 :     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     1190170 : gequalX(GEN x) { return typ(x) == t_POL && lg(x) == 4
     469     2389237 :                       && 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    27747812 : cmp_universal_rec(GEN x, GEN y, long i0)
     481             : {
     482    27747812 :   long i, lx = lg(x), ly = lg(y);
     483    27747812 :   if (lx < ly) return -1;
     484    27745156 :   if (lx > ly) return 1;
     485    42377474 :   for (i = i0; i < lx; i++)
     486             :   {
     487    36180499 :     int f = cmp_universal(gel(x,i), gel(y,i));
     488    36180499 :     if (f) return f;
     489             :   }
     490     6196975 :   return 0;
     491             : }
     492             : /* Universal "meaningless" comparison function. Transitive, returns 0 iff
     493             :  * gidentical(x,y) */
     494             : int
     495    49763008 : cmp_universal(GEN x, GEN y)
     496             : {
     497    49763008 :   long lx, ly, i, tx = typ(x), ty = typ(y);
     498             : 
     499    49763008 :   if (tx < ty) return -1;
     500    49740299 :   if (ty < tx) return 1;
     501    49731158 :   switch(tx)
     502             :   {
     503    21047894 :     case t_INT: return cmpii(x,y);
     504         455 :     case t_STR: return cmp_str(GSTR(x),GSTR(y));
     505      934906 :     case t_REAL:
     506             :     case t_VECSMALL:
     507      934906 :       lx = lg(x);
     508      934906 :       ly = lg(y);
     509      934906 :       if (lx < ly) return -1;
     510      886634 :       if (lx > ly) return 1;
     511     3586269 :       for (i = 1; i < lx; i++)
     512             :       {
     513     3478644 :         if (x[i] < y[i]) return -1;
     514     3109744 :         if (x[i] > y[i]) return 1;
     515             :       }
     516      107625 :       return 0;
     517             : 
     518      898130 :     case t_POL:
     519             :     case t_SER:
     520             :     case t_FFELT:
     521             :     case t_CLOSURE:
     522      898130 :       if (x[1] < y[1]) return -1;
     523      898102 :       if (x[1] > y[1]) return 1;
     524      898039 :       return cmp_universal_rec(x, y, 2);
     525             : 
     526          35 :     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    26849738 :     default:
     546    26849738 :       return cmp_universal_rec(x, y, lontyp[tx]);
     547             :   }
     548             : }
     549             : 
     550             : static int
     551       90096 : cmpfrac(GEN x, GEN y)
     552             : {
     553       90096 :   pari_sp av = avma;
     554       90096 :   GEN a = gel(x,1), b = gel(x,2);
     555       90096 :   GEN c = gel(y,1), d = gel(y,2);
     556       90096 :   return gc_bool(av, cmpii(mulii(a, d), mulii(b, c)));
     557             : }
     558             : static int
     559        7749 : cmpifrac(GEN a, GEN y)
     560             : {
     561        7749 :   pari_sp av = avma;
     562        7749 :   GEN c = gel(y,1), d = gel(y,2);
     563        7749 :   return gc_int(av, cmpii(mulii(a, d), c));
     564             : }
     565             : static int
     566       61320 : cmprfrac(GEN a, GEN y)
     567             : {
     568       61320 :   pari_sp av = avma;
     569       61320 :   GEN c = gel(y,1), d = gel(y,2);
     570       61320 :   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   154202701 : gcmp(GEN x, GEN y)
     582             : {
     583   154202701 :   long tx = typ(x), ty = typ(y);
     584             : 
     585   154202701 :   if (tx == ty) /* generic case */
     586   153757202 :     switch(tx)
     587             :     {
     588    79326627 :       case t_INT:  return cmpii(x, y);
     589    74336485 :       case t_REAL: return cmprr(x, y);
     590       90096 :       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       16303 :       case t_INFINITY:
     594             :       {
     595       16303 :         long sx = inf_get_sign(x), sy = inf_get_sign(y);
     596       16303 :         if (sx < sy) return -1;
     597          21 :         if (sx > sy) return 1;
     598          14 :         return 0;
     599             :       }
     600             :     }
     601      433099 :   if (ty == t_INFINITY) return -inf_get_sign(y);
     602      385403 :   switch(tx)
     603             :   {
     604       30166 :     case t_INT:
     605             :       switch(ty)
     606             :       {
     607       26302 :         case t_REAL: return cmpir(x, y);
     608        3850 :         case t_FRAC: return cmpifrac(x, y);
     609           7 :         case t_QUAD: return cmpgen(x, y);
     610             :       }
     611           7 :       break;
     612      315328 :     case t_REAL:
     613             :       switch(ty)
     614             :       {
     615      277836 :         case t_INT:  return cmpri(x, y);
     616       37471 :         case t_FRAC: return cmprfrac(x, y);
     617          14 :         case t_QUAD: return cmpgen(x, y);
     618             :       }
     619           7 :       break;
     620       27762 :     case t_FRAC:
     621             :       switch(ty)
     622             :       {
     623        3899 :         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          63 :     case t_QUAD:
     629          63 :       return cmpgen(x, y);
     630       31607 :     case t_INFINITY: return inf_get_sign(x);
     631             :   }
     632          24 :   pari_err_TYPE2("comparison",x,y);
     633             :   return 0;/*LCOV_EXCL_LINE*/
     634             : }
     635             : 
     636             : int
     637       75746 : gcmpsg(long s, GEN y)
     638             : {
     639       75746 :   switch(typ(y))
     640             :   {
     641        9380 :     case t_INT:  return cmpsi(s,y);
     642       60577 :     case t_REAL: return cmpsr(s,y);
     643        5789 :     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           0 :     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     6260723 : roughtype(GEN x)
     659             : {
     660     6260723 :   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       45675 :     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          21 :     case t_MAT:
     771             :     case t_VEC:
     772          21 :       return lexcmp_s_matvec(x,y);
     773          14 :     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     3130190 : lexcmp_i(GEN x, GEN y)
     783             : {
     784     3130190 :   const long tx = roughtype(x), ty = roughtype(y);
     785     3130190 :   if (tx == ty)
     786     3129539 :     switch(tx)
     787             :     {
     788        8092 :       case t_MAT:
     789        8092 :       case t_VEC: return lexcmp_similar(x,y);
     790     3098963 :       case t_VECSMALL: return vecsmall_lexcmp(x,y);
     791       22484 :       default: return gcmp(x,y);
     792             :     }
     793         651 :   if (tx == t_VECSMALL) return  lexcmp_vecsmall_other(x,y,ty);
     794         518 :   if (ty == t_VECSMALL) return -lexcmp_vecsmall_other(y,x,tx);
     795             : 
     796         455 :   if (tx == t_INT) return  lexcmp_scal_matvec(x,y); /*scalar*/
     797         203 :   if (ty == t_INT) return -lexcmp_scal_matvec(y,x);
     798             : 
     799          98 :   if (ty==t_MAT) return  lexcmp_vec_mat(x,y);
     800          42 :   return -lexcmp_vec_mat(y,x); /*tx==t_MAT*/
     801             : }
     802             : int
     803     3130190 : lexcmp(GEN x, GEN y)
     804             : {
     805     3130190 :   pari_sp av = avma;
     806     3130190 :   if (typ(x) == t_COMPLEX)
     807             :   {
     808          63 :     x = mkvec2(gel(x,1), gel(x,2));
     809          63 :     if (typ(y) == t_COMPLEX) y = mkvec2(gel(y,1), gel(y,2));
     810          49 :     else y = mkvec2(y, gen_0);
     811             :   }
     812     3130127 :   else if (typ(y) == t_COMPLEX)
     813             :   {
     814          63 :     x = mkvec2(x, gen_0);
     815          63 :     y = mkvec2(gel(y,1), gel(y,2));
     816             :   }
     817     3130190 :   return gc_int(av, lexcmp_i(x, y));
     818             : }
     819             : 
     820             : /*****************************************************************/
     821             : /*                                                               */
     822             : /*                          EQUALITY                             */
     823             : /*                returns 1 if x == y, 0 otherwise               */
     824             : /*                                                               */
     825             : /*****************************************************************/
     826             : /* x,y t_POL */
     827             : static int
     828     3435570 : polidentical(GEN x, GEN y)
     829             : {
     830             :   long lx;
     831     3435570 :   if (x[1] != y[1]) return 0;
     832     3435472 :   lx = lg(x); if (lg(y) != lg(x)) return 0;
     833    14965723 :   for (lx--; lx >= 2; lx--) if (!gidentical(gel(x,lx), gel(y,lx))) return 0;
     834     3435388 :   return 1;
     835             : }
     836             : /* x,y t_SER */
     837             : static int
     838          14 : seridentical(GEN x, GEN y) { return polidentical(x,y); }
     839             : /* typ(x) = typ(y) = t_VEC/COL/MAT */
     840             : static int
     841     4096385 : vecidentical(GEN x, GEN y)
     842             : {
     843             :   long i;
     844     4096385 :   if ((x[0] ^ y[0]) & (TYPBITS|LGBITS)) return 0;
     845    10916009 :   for (i = lg(x)-1; i; i--)
     846     7561626 :     if (! gidentical(gel(x,i),gel(y,i)) ) return 0;
     847     3354383 :   return 1;
     848             : }
     849             : static int
     850         175 : identicalrr(GEN x, GEN y)
     851             : {
     852         175 :   long i, lx = lg(x);
     853         175 :   if (lg(y) != lx) return 0;
     854         168 :   if (x[1] != y[1]) return 0;
     855         616 :   i=2; while (i<lx && x[i]==y[i]) i++;
     856         161 :   return (i == lx);
     857             : }
     858             : 
     859             : static int
     860          70 : closure_identical(GEN x, GEN y)
     861             : {
     862          70 :   if (lg(x)!=lg(y) || x[1]!=y[1]) return 0;
     863          56 :   if (!gidentical(gel(x,2),gel(y,2)) || !gidentical(gel(x,3),gel(y,3))
     864          56 :    || !gidentical(gel(x,4),gel(y,4))) return 0;
     865          42 :   if (lg(x)<8) return 1;
     866           0 :   return gidentical(gel(x,7),gel(y,7));
     867             : }
     868             : 
     869             : static int
     870         336 : list_cmp(GEN x, GEN y, int cmp(GEN x, GEN y))
     871             : {
     872         336 :   int t = list_typ(x);
     873             :   GEN vx, vy;
     874         336 :   if (list_typ(y)!=t) return 0;
     875         336 :   vx = list_data(x);
     876         336 :   vy = list_data(y);
     877         336 :   if (!vx) return vy? 0: 1;
     878         322 :   if (!vy) return 0;
     879         308 :   if (lg(vx) != lg(vy)) return 0;
     880         301 :   switch (t)
     881             :   {
     882         280 :   case t_LIST_MAP:
     883             :     {
     884         280 :       pari_sp av = avma;
     885         280 :       GEN mx  = maptomat_shallow(x), my = maptomat_shallow(y);
     886         280 :       int ret = gidentical(gel(mx, 1), gel(my, 1)) && cmp(gel(mx, 2), gel(my, 2));
     887         280 :       return gc_bool(av, ret);
     888             :     }
     889          21 :   default:
     890          21 :     return cmp(vx, vy);
     891             :   }
     892             : }
     893             : 
     894             : int
     895    56540380 : gidentical(GEN x, GEN y)
     896             : {
     897             :   long tx;
     898             : 
     899    56540380 :   if (x == y) return 1;
     900    55448561 :   tx = typ(x); if (typ(y) != tx) return 0;
     901    55443989 :   switch(tx)
     902             :   {
     903    16156650 :     case t_INT:
     904    16156650 :       return equalii(x,y);
     905             : 
     906         168 :     case t_REAL:
     907         168 :       return identicalrr(x,y);
     908             : 
     909       19069 :     case t_FRAC: case t_INTMOD:
     910       19069 :       return equalii(gel(x,2), gel(y,2)) && equalii(gel(x,1), gel(y,1));
     911             : 
     912          35 :     case t_COMPLEX:
     913          35 :       return gidentical(gel(x,2),gel(y,2)) && gidentical(gel(x,1),gel(y,1));
     914          14 :     case t_PADIC:
     915          14 :       return valp(x) == valp(y)
     916          14 :         && equalii(gel(x,2),gel(y,2))
     917          14 :         && equalii(gel(x,3),gel(y,3))
     918          28 :         && equalii(gel(x,4),gel(y,4));
     919        1066 :     case t_POLMOD:
     920        1066 :       return gidentical(gel(x,2),gel(y,2)) && polidentical(gel(x,1),gel(y,1));
     921     3434903 :     case t_POL:
     922     3434903 :       return polidentical(x,y);
     923          14 :     case t_SER:
     924          14 :       return seridentical(x,y);
     925          14 :     case t_FFELT:
     926          14 :       return FF_equal(x,y);
     927             : 
     928           7 :     case t_QFR:
     929           7 :           if (!identicalrr(gel(x,4),gel(y,4))) return 0; /* fall through */
     930             :     case t_QFI:
     931     2385395 :       return equalii(gel(x,1),gel(y,1))
     932     2385388 :           && equalii(gel(x,2),gel(y,2))
     933     4770783 :           && equalii(gel(x,3),gel(y,3));
     934             : 
     935          14 :     case t_QUAD:
     936          14 :       return ZX_equal(gel(x,1),gel(y,1))
     937           7 :           && gidentical(gel(x,2),gel(y,2))
     938          21 :           && gidentical(gel(x,3),gel(y,3));
     939             : 
     940           7 :     case t_RFRAC:
     941           7 :       return gidentical(gel(x,1),gel(y,1)) && gidentical(gel(x,2),gel(y,2));
     942             : 
     943          70 :     case t_STR:
     944          70 :       return !strcmp(GSTR(x),GSTR(y));
     945     4096385 :     case t_VEC: case t_COL: case t_MAT:
     946     4096385 :       return vecidentical(x,y);
     947    29349968 :     case t_VECSMALL:
     948    29349968 :       return zv_equal(x,y);
     949          28 :     case t_CLOSURE:
     950          28 :       return closure_identical(x,y);
     951         161 :     case t_LIST:
     952         161 :       return list_cmp(x, y, gidentical);
     953          21 :     case t_INFINITY: return gidentical(gel(x,1),gel(y,1));
     954             :   }
     955           0 :   return 0;
     956             : }
     957             : /* x,y t_POL in the same variable */
     958             : static int
     959     8357669 : polequal(GEN x, GEN y)
     960             : {
     961             :   long lx, ly;
     962     8357669 :   if (signe(x) != signe(y)) return 0;
     963     8357641 :   lx = lg(x); ly = lg(y);
     964     8357641 :   while (lx > ly) if (!gequal0(gel(x,--lx))) return 0;
     965     8355506 :   while (ly > lx) if (!gequal0(gel(y,--ly))) return 0;
     966    34470321 :   for (lx--; lx >= 2; lx--) if (!gequal(gel(x,lx), gel(y,lx))) return 0;
     967     8312279 :   return 1;
     968             : }
     969             : 
     970             : /* x,y t_SER in the same variable */
     971             : static int
     972         364 : serequal(GEN x, GEN y)
     973             : {
     974             :   long LX, LY, lx, ly, vx, vy;
     975         364 :   if (!signe(x) && !signe(y)) return 1;
     976          56 :   lx = lg(x); vx = valp(x); LX = lx + vx;
     977          56 :   ly = lg(y); vy = valp(y); LY = ly + vy;
     978          56 :   if (LX > LY) { LX = LY; lx = LX - vx; } else ly = LX - vy;
     979      282877 :   for (lx--, ly--; lx >= 2 && ly >= 2; lx--, ly--)
     980      282821 :     if (!gequal(gel(x,lx), gel(y,ly))) return 0;
     981          56 :   while(--ly >= 2) if (!gequal0(gel(y,ly))) return 0;
     982          56 :   while(--lx >= 2) if (!gequal0(gel(x,lx))) return 0;
     983          49 :   return 1;
     984             : }
     985             : 
     986             : /* typ(x) = typ(y) = t_VEC/COL/MAT */
     987             : static int
     988     5018062 : vecequal(GEN x, GEN y)
     989             : {
     990             :   long i;
     991     5018062 :   if ((x[0] ^ y[0]) & (TYPBITS|LGBITS)) return 0;
     992    16196026 :   for (i = lg(x)-1; i; i--)
     993    14149030 :     if (! gequal(gel(x,i),gel(y,i)) ) return 0;
     994     2046996 :   return 1;
     995             : }
     996             : 
     997             : static int
     998     1342563 : gequal_try(GEN x, GEN y)
     999             : {
    1000             :   int i;
    1001     1342563 :   pari_CATCH(CATCH_ALL) {
    1002         182 :     GEN E = pari_err_last();
    1003         182 :     switch(err_get_num(E))
    1004             :     {
    1005           0 :       case e_STACK: case e_MEM: case e_ALARM:
    1006           0 :         pari_err(0, E); /* rethrow */
    1007             :     }
    1008         182 :     return 0;
    1009             :   } pari_TRY {
    1010     1342563 :     i = gequal0(gadd(x, gneg_i(y)));
    1011     1342381 :   } pari_ENDCATCH;
    1012     1342381 :   return i;
    1013             : }
    1014             : 
    1015             : int
    1016   215729734 : gequal(GEN x, GEN y)
    1017             : {
    1018             :   pari_sp av;
    1019             :   long tx, ty;
    1020             :   long i;
    1021             : 
    1022   215729734 :   if (x == y) return 1;
    1023   192347460 :   tx = typ(x);
    1024   192347460 :   ty = typ(y);
    1025   192347460 :   if (tx == ty)
    1026   187392981 :     switch(tx)
    1027             :     {
    1028   161459114 :       case t_INT:
    1029   161459114 :         return equalii(x,y);
    1030             : 
    1031        1986 :       case t_REAL:
    1032        1986 :         return equalrr(x,y);
    1033             : 
    1034     7193063 :       case t_FRAC: case t_INTMOD:
    1035     7193063 :         return equalii(gel(x,2), gel(y,2)) && equalii(gel(x,1), gel(y,1));
    1036             : 
    1037         420 :       case t_COMPLEX:
    1038         420 :         return gequal(gel(x,2),gel(y,2)) && gequal(gel(x,1),gel(y,1));
    1039         756 :       case t_PADIC:
    1040         756 :         if (!equalii(gel(x,2),gel(y,2))) return 0;
    1041         756 :         av = avma; i = gequal0(gsub(x,y)); set_avma(av);
    1042         756 :         return i;
    1043     3457949 :       case t_POLMOD:
    1044     3457949 :         if (varn(gel(x,1)) != varn(gel(y,1))) break;
    1045     3457942 :         return gequal(gel(x,2),gel(y,2)) && RgX_equal_var(gel(x,1),gel(y,1));
    1046     8366365 :       case t_POL:
    1047     8366365 :         if (varn(x) != varn(y)) break;
    1048     8357671 :         return polequal(x,y);
    1049         364 :       case t_SER:
    1050         364 :         if (varn(x) != varn(y)) break;
    1051         364 :         return serequal(x,y);
    1052             : 
    1053       55937 :       case t_FFELT:
    1054       55937 :         return FF_equal(x,y);
    1055             : 
    1056     1050155 :       case t_QFR:
    1057             :       case t_QFI:
    1058     1050155 :         return equalii(gel(x,1),gel(y,1))
    1059      230248 :             && equalii(gel(x,2),gel(y,2))
    1060     1280403 :             && equalii(gel(x,3),gel(y,3));
    1061             : 
    1062           7 :       case t_QUAD:
    1063           7 :         return ZX_equal(gel(x,1),gel(y,1))
    1064           0 :             && gequal(gel(x,2),gel(y,2))
    1065           7 :             && gequal(gel(x,3),gel(y,3));
    1066             : 
    1067       73717 :       case t_RFRAC:
    1068             :       {
    1069       73717 :         GEN a = gel(x,1), b = gel(x,2), c = gel(y,1), d = gel(y,2);
    1070       73717 :         if (gequal(b,d)) return gequal(a,c); /* simple case */
    1071           0 :         av = avma;
    1072           0 :         a = simplify_shallow(gmul(a,d));
    1073           0 :         b = simplify_shallow(gmul(b,c));
    1074           0 :         return gc_bool(av, gequal(a,b));
    1075             :       }
    1076             : 
    1077       61400 :       case t_STR:
    1078       61400 :         return !strcmp(GSTR(x),GSTR(y));
    1079     5018062 :       case t_VEC: case t_COL: case t_MAT:
    1080     5018062 :         return vecequal(x,y);
    1081      653451 :       case t_VECSMALL:
    1082      653451 :         return zv_equal(x,y);
    1083         175 :       case t_LIST:
    1084         175 :         return list_cmp(x, y, gequal);
    1085          42 :       case t_CLOSURE:
    1086          42 :         return closure_identical(x,y);
    1087          28 :       case t_INFINITY:
    1088          28 :         return gequal(gel(x,1),gel(y,1));
    1089             :     }
    1090     4963170 :   if (is_noncalc_t(tx) || is_noncalc_t(ty)) return 0;
    1091     4963186 :   if (tx == t_INT && !signe(x)) return gequal0(y);
    1092     4960659 :   if (ty == t_INT && !signe(y)) return gequal0(x);
    1093     1342563 :   (void)&av; av = avma; /* emulate volatile */
    1094     1342563 :   return gc_bool(av, gequal_try(x, y));
    1095             : }
    1096             : 
    1097             : int
    1098       39361 : gequalsg(long s, GEN x)
    1099       39361 : { pari_sp av = avma; return gc_bool(av, gequal(stoi(s), x)); }
    1100             : 
    1101             : /* a and b are t_INT, t_FRAC, t_REAL or t_COMPLEX of those. Check whether
    1102             :  * a-b is invertible */
    1103             : int
    1104        9331 : cx_approx_equal(GEN a, GEN b)
    1105             : {
    1106        9331 :   pari_sp av = avma;
    1107             :   GEN d;
    1108        9331 :   if (a == b) return 1;
    1109        7805 :   d = gsub(a,b);
    1110        7805 :   return gc_bool(av, gequal0(d) || (typ(d)==t_COMPLEX && gequal0(cxnorm(d))));
    1111             : }
    1112             : /*******************************************************************/
    1113             : /*                                                                 */
    1114             : /*                          VALUATION                              */
    1115             : /*             p is either a t_INT or a t_POL.                     */
    1116             : /*  returns the largest exponent of p dividing x when this makes   */
    1117             : /*  sense : error for types real, integermod and polymod if p does */
    1118             : /*  not divide the modulus, q-adic if q!=p.                        */
    1119             : /*                                                                 */
    1120             : /*******************************************************************/
    1121             : 
    1122             : static long
    1123         287 : minval(GEN x, GEN p)
    1124             : {
    1125         287 :   long i,k, val = LONG_MAX, lx = lg(x);
    1126        5978 :   for (i=lontyp[typ(x)]; i<lx; i++)
    1127             :   {
    1128        5691 :     k = gvaluation(gel(x,i),p);
    1129        5691 :     if (k < val) val = k;
    1130             :   }
    1131         287 :   return val;
    1132             : }
    1133             : 
    1134             : static int
    1135          91 : intdvd(GEN x, GEN y, GEN *z) { GEN r; *z = dvmdii(x,y,&r); return (r==gen_0); }
    1136             : 
    1137             : /* x t_FRAC, p t_INT, return v_p(x) */
    1138             : static long
    1139       75704 : frac_val(GEN x, GEN p) {
    1140       75704 :   long v = Z_pval(gel(x,2),p);
    1141       75704 :   if (v) return -v;
    1142       75636 :   return Z_pval(gel(x,1),p);
    1143             : }
    1144             : long
    1145     1552614 : Q_pval(GEN x, GEN p)
    1146             : {
    1147     1552614 :   if (lgefint(p) == 3) return Q_lval(x, uel(p,2));
    1148         144 :   return (typ(x)==t_INT)? Z_pval(x, p): frac_val(x, p);
    1149             : }
    1150             : 
    1151             : static long
    1152      140658 : frac_lval(GEN x, ulong p) {
    1153      140658 :   long v = Z_lval(gel(x,2),p);
    1154      140658 :   if (v) return -v;
    1155       55753 :   return Z_lval(gel(x,1),p);
    1156             : }
    1157             : long
    1158     1552473 : Q_lval(GEN x, ulong p){return (typ(x)==t_INT)? Z_lval(x, p): frac_lval(x, p);}
    1159             : 
    1160             : long
    1161     3515660 : Q_pvalrem(GEN x, GEN p, GEN *y)
    1162             : {
    1163             :   GEN a, b;
    1164             :   long v;
    1165     3515660 :   if (lgefint(p) == 3) return Q_lvalrem(x, uel(p,2), y);
    1166         634 :   if (typ(x) == t_INT) return Z_pvalrem(x, p, y);
    1167           0 :   a = gel(x,1);
    1168           0 :   b = gel(x,2);
    1169           0 :   v = Z_pvalrem(b, p, &b);
    1170           0 :   if (v) { *y = isint1(b)? a: mkfrac(a, b); return -v; }
    1171           0 :   v = Z_pvalrem(a, p, &a);
    1172           0 :   *y = mkfrac(a, b); return v;
    1173             : }
    1174             : long
    1175     3515027 : Q_lvalrem(GEN x, ulong p, GEN *y)
    1176             : {
    1177             :   GEN a, b;
    1178             :   long v;
    1179     3515027 :   if (typ(x) == t_INT) return Z_lvalrem(x, p, y);
    1180     1137896 :   a = gel(x,1);
    1181     1137896 :   b = gel(x,2);
    1182     1137896 :   v = Z_lvalrem(b, p, &b);
    1183     1137897 :   if (v) { *y = isint1(b)? a: mkfrac(a, b); return -v; }
    1184      790899 :   v = Z_lvalrem(a, p, &a);
    1185      790899 :   *y = mkfrac(a, b); return v;
    1186             : }
    1187             : 
    1188             : long
    1189      331942 : gvaluation(GEN x, GEN p)
    1190             : {
    1191      331942 :   long tx = typ(x), tp = typ(p);
    1192             :   pari_sp av;
    1193             : 
    1194      331942 :   switch(tp)
    1195             :   {
    1196      327336 :     case t_INT:
    1197      327336 :       if (signe(p) && !is_pm1(p)) break;
    1198          28 :       pari_err_DOMAIN("gvaluation", "p", "=", p, p);
    1199        4599 :     case t_POL:
    1200        4599 :       if (degpol(p) > 0) break;
    1201             :     default:
    1202           7 :       pari_err_DOMAIN("gvaluation", "p", "=", p, p);
    1203             :   }
    1204             : 
    1205      331907 :   switch(tx)
    1206             :   {
    1207       54818 :     case t_INT:
    1208       54818 :       if (!signe(x)) return LONG_MAX;
    1209       54713 :       if (tp == t_POL) return 0;
    1210       54419 :       return Z_pval(x,p);
    1211             : 
    1212          49 :     case t_REAL:
    1213          49 :       if (tp == t_POL) return 0;
    1214          21 :       break;
    1215             : 
    1216          28 :     case t_FFELT:
    1217          28 :       if (tp == t_POL) return FF_equal0(x)? LONG_MAX: 0;
    1218          14 :       break;
    1219             : 
    1220          84 :     case t_INTMOD: {
    1221          84 :       GEN a = gel(x,1), b = gel(x,2);
    1222             :       long val;
    1223         112 :       if (tp == t_POL) return signe(b)? 0: LONG_MAX;
    1224          42 :       av = avma;
    1225          42 :       if (!intdvd(a, p, &a)) break;
    1226          28 :       if (!intdvd(b, p, &b)) return gc_long(av,0);
    1227          14 :       val = 1; while (intdvd(a,p,&a) && intdvd(b,p,&b)) val++;
    1228          14 :       return gc_long(av,val);
    1229             :     }
    1230             : 
    1231       75658 :     case t_FRAC:
    1232       75658 :       if (tp == t_POL) return 0;
    1233       75644 :       return frac_val(x, p);
    1234             : 
    1235      196867 :     case t_PADIC:
    1236      196867 :       if (tp == t_POL) return 0;
    1237      196853 :       if (!equalii(p,gel(x,2))) break;
    1238      196846 :       return valp(x);
    1239             : 
    1240          35 :     case t_POLMOD: {
    1241          35 :       GEN a = gel(x,1), b = gel(x,2);
    1242             :       long v, val;
    1243          35 :       if (tp == t_INT) return gvaluation(b,p);
    1244          21 :       v = varn(p);
    1245          21 :       if (varn(a) != v) return 0;
    1246          21 :       av = avma;
    1247          21 :       a = RgX_divrem(a, p, ONLY_DIVIDES);
    1248          21 :       if (!a) break;
    1249          28 :       if (typ(b) != t_POL || varn(b) != v ||
    1250          21 :           !(b = RgX_divrem(b, p, ONLY_DIVIDES)) ) return gc_long(av,0);
    1251           7 :       val = 1;
    1252          28 :       while ((a = RgX_divrem(a, p, ONLY_DIVIDES)) &&
    1253          21 :              (b = RgX_divrem(b, p, ONLY_DIVIDES)) ) val++;
    1254           7 :       return gc_long(av,val);
    1255             :     }
    1256        4067 :     case t_POL: {
    1257        4067 :       if (tp == t_POL) {
    1258        3878 :         long vp = varn(p), vx = varn(x);
    1259        3878 :         if (vp == vx)
    1260             :         {
    1261             :           long val;
    1262        3871 :           if (RgX_is_monomial(p)) return RgX_val(x) / degpol(p);
    1263           7 :           av = avma;
    1264           7 :           for (val=0; ; val++)
    1265             :           {
    1266           7 :             x = RgX_divrem(x,p,ONLY_DIVIDES);
    1267           7 :             if (!x) return gc_long(av,val);
    1268           0 :             if (gc_needed(av,1))
    1269             :             {
    1270           0 :               if(DEBUGMEM>1) pari_warn(warnmem,"gvaluation");
    1271           0 :               x = gerepilecopy(av, x);
    1272             :             }
    1273             :           }
    1274             :         }
    1275           7 :         if (varncmp(vx, vp) > 0) return 0;
    1276             :       }
    1277         189 :       return minval(x,p);
    1278             :     }
    1279             : 
    1280         175 :     case t_SER: {
    1281         175 :       if (tp == t_POL) {
    1282         161 :         long vp = varn(p), vx = varn(x);
    1283         161 :         if (vp == vx)
    1284             :         {
    1285         154 :           long val = RgX_val(p);
    1286         154 :           if (!val) pari_err_DOMAIN("gvaluation", "p", "=", p, p);
    1287         147 :           return (long)(valp(x) / val);
    1288             :         }
    1289           7 :         if (varncmp(vx, vp) > 0) return 0;
    1290             :       }
    1291          14 :       return minval(x,p);
    1292             :     }
    1293             : 
    1294          42 :     case t_RFRAC:
    1295          42 :       return gvaluation(gel(x,1),p) - gvaluation(gel(x,2),p);
    1296             : 
    1297          84 :     case t_COMPLEX: case t_QUAD: case t_VEC: case t_COL: case t_MAT:
    1298          84 :       return minval(x,p);
    1299             :   }
    1300          63 :   pari_err_OP("valuation", x,p);
    1301             :   return 0; /* LCOV_EXCL_LINE */
    1302             : }
    1303             : GEN
    1304        3717 : gpvaluation(GEN x, GEN p)
    1305             : {
    1306        3717 :   long v = gvaluation(x,p);
    1307        3619 :   return v == LONG_MAX? mkoo(): stoi(v);
    1308             : }
    1309             : 
    1310             : /* x is non-zero */
    1311             : long
    1312    22529485 : u_lvalrem(ulong x, ulong p, ulong *py)
    1313             : {
    1314             :   ulong vx;
    1315    22529485 :   if (p == 2) { vx = vals(x); *py = x >> vx; return vx; }
    1316    19921140 :   for(vx = 0;;)
    1317             :   {
    1318    34295072 :     if (x % p) { *py = x; return vx; }
    1319    14373932 :     x /= p; /* gcc is smart enough to make a single div */
    1320    14373932 :     vx++;
    1321             :   }
    1322             : }
    1323             : long
    1324    12030781 : u_lval(ulong x, ulong p)
    1325             : {
    1326             :   ulong vx;
    1327    12030781 :   if (p == 2) return vals(x);
    1328    11346804 :   for(vx = 0;;)
    1329             :   {
    1330    31082181 :     if (x % p) return vx;
    1331    19735377 :     x /= p; /* gcc is smart enough to make a single div */
    1332    19735377 :     vx++;
    1333             :   }
    1334             : }
    1335             : 
    1336             : long
    1337      938475 : z_lval(long s, ulong p) { return u_lval(labs(s), p); }
    1338             : long
    1339          63 : z_lvalrem(long s, ulong p, long *py)
    1340             : {
    1341             :   long v;
    1342          63 :   if (s < 0)
    1343             :   {
    1344           0 :     ulong u = (ulong)-s;
    1345           0 :     v = u_lvalrem(u, p, &u);
    1346           0 :     *py = -(long)u;
    1347             :   }
    1348             :   else
    1349             :   {
    1350          63 :     ulong u = (ulong)s;
    1351          63 :     v = u_lvalrem(u, p, &u);
    1352          63 :     *py = (long)u;
    1353             :   }
    1354          63 :   return v;
    1355             : }
    1356             : /* assume |p| > 1 */
    1357             : long
    1358      628361 : z_pval(long s, GEN p)
    1359             : {
    1360      628361 :   if (lgefint(p) > 3) return 0;
    1361      628361 :   return z_lval(s, uel(p,2));
    1362             : }
    1363             : /* assume |p| > 1 */
    1364             : long
    1365          63 : z_pvalrem(long s, GEN p, long *py)
    1366             : {
    1367          63 :   if (lgefint(p) > 3) { *py = s; return 0; }
    1368          63 :   return z_lvalrem(s, uel(p,2), py);
    1369             : }
    1370             : 
    1371             : /* return v_q(x) and set *py = x / q^v_q(x), using divide & conquer */
    1372             : static long
    1373     1429422 : Z_pvalrem_DC(GEN x, GEN q, GEN *py)
    1374             : {
    1375     1429422 :   GEN r, z = dvmdii(x, q, &r);
    1376             :   long v;
    1377     1429422 :   if (r != gen_0) { *py = x; return 0; }
    1378     1002455 :   if (2 * lgefint(q) <= lgefint(z)+3) /* avoid squaring if pointless */
    1379      988760 :     v = Z_pvalrem_DC(z, sqri(q), py) << 1;
    1380             :   else
    1381       13695 :   { v = 0; *py = z; }
    1382     1002455 :   z = dvmdii(*py, q, &r);
    1383     1002455 :   if (r != gen_0) return v + 1;
    1384      428037 :   *py = z; return v + 2;
    1385             : }
    1386             : 
    1387             : static const long VAL_DC_THRESHOLD = 16;
    1388             : 
    1389             : long
    1390    11768119 : Z_lval(GEN x, ulong p)
    1391             : {
    1392             :   long vx;
    1393             :   pari_sp av;
    1394    11768119 :   if (p == 2) return vali(x);
    1395     8198862 :   if (lgefint(x) == 3) return u_lval(uel(x,2), p);
    1396     1093418 :   av = avma;
    1397     1093418 :   for(vx = 0;;)
    1398     5838789 :   {
    1399             :     ulong r;
    1400     6932207 :     GEN q = absdiviu_rem(x, p, &r);
    1401     6932212 :     if (r) break;
    1402     5962548 :     vx++; x = q;
    1403     5962548 :     if (vx == VAL_DC_THRESHOLD) {
    1404      123759 :       if (p == 1) pari_err_DOMAIN("Z_lval", "p", "=", gen_1, gen_1);
    1405      123759 :       vx += Z_pvalrem_DC(x, sqru(p), &x) << 1;
    1406      123759 :       q = absdiviu_rem(x, p, &r); if (!r) vx++;
    1407      123759 :       break;
    1408             :     }
    1409             :   }
    1410     1093423 :   return gc_long(av,vx);
    1411             : }
    1412             : long
    1413    22259442 : Z_lvalrem(GEN x, ulong p, GEN *py)
    1414             : {
    1415             :   long vx, sx;
    1416             :   pari_sp av;
    1417    22259442 :   if (p == 2) { vx = vali(x); *py = shifti(x, -vx); return vx; }
    1418    15703330 :   if (lgefint(x) == 3) {
    1419             :     ulong u;
    1420    11404163 :     vx = u_lvalrem(uel(x,2), p, &u);
    1421    11404163 :     *py = signe(x) < 0? utoineg(u): utoipos(u);
    1422    11404163 :     return vx;
    1423             :   }
    1424     4299167 :   av = avma; (void)new_chunk(lgefint(x));
    1425     4299167 :   sx = signe(x);
    1426     4299167 :   for(vx = 0;;)
    1427    10148710 :   {
    1428             :     ulong r;
    1429    14447877 :     GEN q = absdiviu_rem(x, p, &r);
    1430    14447877 :     if (r) break;
    1431    10456307 :     vx++; x = q;
    1432    10456307 :     if (vx == VAL_DC_THRESHOLD) {
    1433      307597 :       if (p == 1) pari_err_DOMAIN("Z_lvalrem", "p", "=", gen_1, gen_1);
    1434      307597 :       vx += Z_pvalrem_DC(x, sqru(p), &x) << 1;
    1435      307597 :       q = absdiviu_rem(x, p, &r); if (!r) { vx++; x = q; }
    1436      307597 :       break;
    1437             :     }
    1438             :   }
    1439     4299167 :   set_avma(av); *py = icopy(x); setsigne(*py, sx); return vx;
    1440             : }
    1441             : 
    1442             : /* Is |q| <= p ? */
    1443             : static int
    1444   206219227 : isless_iu(GEN q, ulong p) {
    1445   206219227 :   long l = lgefint(q);
    1446   206219227 :   return l==2 || (l == 3 && uel(q,2) <= p);
    1447             : }
    1448             : 
    1449             : long
    1450   554079153 : u_lvalrem_stop(ulong *n, ulong p, int *stop)
    1451             : {
    1452   554079153 :   ulong N = *n, q = N / p, r = N % p; /* gcc makes a single div */
    1453   554079153 :   long v = 0;
    1454   554079153 :   if (!r)
    1455             :   {
    1456    40610591 :     do { v++; N = q; q = N / p; r = N % p; } while (!r);
    1457    27523593 :     *n = N;
    1458             :   }
    1459   554079153 :   *stop = q <= p; return v;
    1460             : }
    1461             : /* Assume n > 0. Return v_p(n), set *n := n/p^v_p(n). Set 'stop' if now
    1462             :  * n < p^2 [implies n prime if no prime < p divides n] */
    1463             : long
    1464   606999689 : Z_lvalrem_stop(GEN *n, ulong p, int *stop)
    1465             : {
    1466             :   pari_sp av;
    1467             :   long v;
    1468             :   ulong r;
    1469             :   GEN N, q;
    1470             : 
    1471   606999689 :   if (lgefint(*n) == 3)
    1472             :   {
    1473   400766282 :     r = (*n)[2];
    1474   400766282 :     v = u_lvalrem_stop(&r, p, stop);
    1475   400859499 :     if (v) *n = utoipos(r);
    1476   400848017 :     return v;
    1477             :   }
    1478   206233407 :   av = avma; v = 0; q = absdiviu_rem(*n, p, &r);
    1479   206190446 :   if (r) set_avma(av);
    1480             :   else
    1481             :   {
    1482             :     do {
    1483     1304231 :       v++; N = q;
    1484     1304231 :       if (v == VAL_DC_THRESHOLD)
    1485             :       {
    1486        9306 :         v += Z_pvalrem_DC(N,sqru(p),&N) << 1;
    1487        9306 :         q = absdiviu_rem(N, p, &r); if (!r) { v++; N = q; }
    1488        9306 :         break;
    1489             :       }
    1490     1294925 :       q = absdiviu_rem(N, p, &r);
    1491     1294925 :     } while (!r);
    1492      670112 :     *n = N;
    1493             :   }
    1494   206193622 :   *stop = isless_iu(q,p); return v;
    1495             : }
    1496             : 
    1497             : /* x is a non-zero integer, |p| > 1 */
    1498             : long
    1499    15731276 : Z_pvalrem(GEN x, GEN p, GEN *py)
    1500             : {
    1501             :   long vx;
    1502             :   pari_sp av;
    1503             : 
    1504    15731276 :   if (lgefint(p) == 3) return Z_lvalrem(x, uel(p,2), py);
    1505       14376 :   if (lgefint(x) == 3) { *py = icopy(x); return 0; }
    1506        4058 :   av = avma; vx = 0; (void)new_chunk(lgefint(x));
    1507             :   for(;;)
    1508        9611 :   {
    1509       13671 :     GEN r, q = dvmdii(x,p,&r);
    1510       13671 :     if (r != gen_0) { set_avma(av); *py = icopy(x); return vx; }
    1511        9611 :     vx++; x = q;
    1512             :   }
    1513             : }
    1514             : long
    1515      453139 : u_pvalrem(ulong x, GEN p, ulong *py)
    1516             : {
    1517      453139 :   if (lgefint(p) == 3) return u_lvalrem(x, uel(p,2), py);
    1518         459 :   *py = x; return 0;
    1519             : }
    1520             : long
    1521        2002 : u_pval(ulong x, GEN p)
    1522             : {
    1523        2002 :   if (lgefint(p) == 3) return u_lval(x, uel(p,2));
    1524           0 :   return 0;
    1525             : }
    1526             : long
    1527     6076295 : Z_pval(GEN x, GEN p) {
    1528             :   long vx;
    1529             :   pari_sp av;
    1530             : 
    1531     6076295 :   if (lgefint(p) == 3) return Z_lval(x, uel(p,2));
    1532        4867 :   if (lgefint(x) == 3) return 0;
    1533        3577 :   av = avma; vx = 0;
    1534             :   for(;;)
    1535       20983 :   {
    1536       24560 :     GEN r, q = dvmdii(x,p,&r);
    1537       24560 :     if (r != gen_0) return gc_long(av,vx);
    1538       20983 :     vx++; x = q;
    1539             :   }
    1540             : }
    1541             : 
    1542             : /* return v_p(n!) = [n/p] + [n/p^2] + ... */
    1543             : long
    1544       97392 : factorial_lval(ulong n, ulong p)
    1545             : {
    1546             :   ulong q, v;
    1547       97392 :   if (p == 2) return n - hammingl(n);
    1548       37804 :   q = p; v = 0;
    1549       40413 :   do { v += n/q; q *= p; } while (n >= q);
    1550       37804 :   return (long)v;
    1551             : }
    1552             : 
    1553             : /********** Same for "containers" ZX / ZV / ZC **********/
    1554             : 
    1555             : /* If the t_INT q divides the ZX/ZV x, return the quotient. Otherwise NULL.
    1556             :  * Stack clean; assumes lg(x) > 1 */
    1557             : static GEN
    1558        4499 : gen_Z_divides(GEN x, GEN q, long imin)
    1559             : {
    1560             :   long i, l;
    1561        4499 :   GEN y = cgetg_copy(x, &l);
    1562             : 
    1563        4499 :   y[1] = x[1]; /* Needed for ZX; no-op if ZV, overwritten in first iteration */
    1564       84583 :   for (i = imin; i < l; i++)
    1565             :   {
    1566       82765 :     GEN r, xi = gel(x,i);
    1567       82765 :     if (!signe(xi)) { gel(y,i) = xi; continue; }
    1568       51484 :     gel(y,i) = dvmdii(xi, q, &r);
    1569       51484 :     if (r != gen_0) { set_avma((pari_sp)(y+l)); return NULL; }
    1570             :   }
    1571        1818 :   return y;
    1572             : }
    1573             : /* If q divides the ZX/ZV x, return the quotient. Otherwise NULL.
    1574             :  * Stack clean; assumes lg(x) > 1 */
    1575             : static GEN
    1576        2751 : gen_z_divides(GEN x, ulong q, long imin)
    1577             : {
    1578             :   long i, l;
    1579        2751 :   GEN y = cgetg_copy(x, &l);
    1580             : 
    1581        2751 :   y[1] = x[1]; /* Needed for ZX; no-op if ZV, overwritten in first iteration */
    1582       36967 :   for (i = imin; i < l; i++)
    1583             :   {
    1584             :     ulong r;
    1585       36596 :     GEN xi = gel(x,i);
    1586       36596 :     if (!signe(xi)) { gel(y,i) = xi; continue; }
    1587       23061 :     gel(y,i) = absdiviu_rem(xi, q, &r);
    1588       23061 :     if (r) { set_avma((pari_sp)(y+l)); return NULL; }
    1589       20681 :     affectsign_safe(xi, &gel(y,i));
    1590             :   }
    1591         371 :   return y;
    1592             : }
    1593             : 
    1594             : /* return v_q(x) and set *py = x / q^v_q(x), using divide & conquer */
    1595             : static long
    1596        7205 : gen_pvalrem_DC(GEN x, GEN q, GEN *py, long imin)
    1597             : {
    1598             : 
    1599        7205 :   pari_sp av = avma;
    1600        7205 :   long v, i, l, lz = LONG_MAX;
    1601        7205 :   GEN y = cgetg_copy(x, &l);
    1602             : 
    1603        7205 :   y[1] = x[1];
    1604      123206 :   for (i = imin; i < l; i++)
    1605             :   {
    1606      118707 :     GEN r, xi = gel(x,i);
    1607      118707 :     if (!signe(xi)) { gel(y,i) = xi; continue; }
    1608       76005 :     gel(y,i) = dvmdii(xi, q, &r);
    1609       76005 :     if (r != gen_0) { *py = x; return gc_long(av,0); }
    1610       73299 :     lz = minss(lz, lgefint(gel(y,i)));
    1611             :   }
    1612        4499 :   if (2 * lgefint(q) <= lz+3) /* avoid squaring if pointless */
    1613        4440 :     v = gen_pvalrem_DC(y, sqri(q), py, imin) << 1;
    1614             :   else
    1615          59 :   { v = 0; *py = y; }
    1616             : 
    1617        4499 :   y = gen_Z_divides(*py, q, imin);
    1618        4499 :   if (!y) return v+1;
    1619        1818 :   *py = y; return v+2;
    1620             : }
    1621             : 
    1622             : static long
    1623        5838 : gen_2val(GEN x, long imin)
    1624             : {
    1625        5838 :   long i, lx = lg(x), v = LONG_MAX;
    1626       18006 :   for (i = imin; i < lx; i++)
    1627             :   {
    1628       16655 :     GEN c = gel(x,i);
    1629             :     long w;
    1630       16655 :     if (!signe(c)) continue;
    1631       12004 :     w = vali(c);
    1632       12004 :     if (w < v) { v = w; if (!v) break; }
    1633             :   }
    1634        5838 :   return v;
    1635             : }
    1636             : static long
    1637        8911 : gen_lval(GEN x, ulong p, long imin)
    1638             : {
    1639             :   long i, lx, v;
    1640             :   pari_sp av;
    1641             :   GEN y;
    1642        8911 :   if (p == 2) return gen_2val(x, imin);
    1643        3073 :   av = avma;
    1644        3073 :   lx = lg(x); y = leafcopy(x);
    1645        3073 :   for(v = 0;; v++)
    1646        4515 :     for (i = imin; i < lx; i++)
    1647             :     {
    1648             :       ulong r;
    1649        4466 :       gel(y,i) = absdiviu_rem(gel(y,i), p, &r);
    1650        4466 :       if (r) return gc_long(av,v);
    1651             :     }
    1652             : }
    1653             : long
    1654          42 : ZX_lval(GEN x, ulong p) { return gen_lval(x, p, 2); }
    1655             : long
    1656           0 : ZV_lval(GEN x, ulong p) { return gen_lval(x, p, 1); }
    1657             : 
    1658             : long
    1659           0 : zx_lval(GEN f, long p)
    1660             : {
    1661           0 :   long i, l = lg(f), x = LONG_MAX;
    1662           0 :   for(i=2; i<l; i++)
    1663             :   {
    1664             :     long y;
    1665           0 :     if (f[i] == 0) continue;
    1666           0 :     y = z_lval(f[i], p);
    1667           0 :     if (y < x) { x = y; if (x == 0) return x; }
    1668             :   }
    1669           0 :   return x;
    1670             : }
    1671             : 
    1672             : static long
    1673        8869 : gen_pval(GEN x, GEN p, long imin)
    1674             : {
    1675             :   long i, lx, v;
    1676             :   pari_sp av;
    1677             :   GEN y;
    1678        8869 :   if (lgefint(p) == 3) return gen_lval(x, p[2], imin);
    1679           0 :   av = avma;
    1680           0 :   lx = lg(x); y = leafcopy(x);
    1681           0 :   for(v = 0;; v++)
    1682             :   {
    1683           0 :     if (v == VAL_DC_THRESHOLD)
    1684             :     {
    1685           0 :       if (is_pm1(p)) pari_err_DOMAIN("gen_pval", "p", "=", p, p);
    1686           0 :       v += gen_pvalrem_DC(y, p, &y, imin);
    1687           0 :       return gc_long(av,v);
    1688             :     }
    1689             : 
    1690           0 :     for (i = imin; i < lx; i++)
    1691             :     {
    1692           0 :       GEN r; gel(y,i) = dvmdii(gel(y,i), p, &r);
    1693           0 :       if (r != gen_0) return gc_long(av,v);
    1694             :     }
    1695             :   }
    1696             : }
    1697             : long
    1698        1540 : ZX_pval(GEN x, GEN p) { return gen_pval(x, p, 2); }
    1699             : long
    1700        7329 : ZV_pval(GEN x, GEN p) { return gen_pval(x, p, 1); }
    1701             : /* v = 0 (mod p) */
    1702             : int
    1703         343 : ZV_Z_dvd(GEN v, GEN p)
    1704             : {
    1705         343 :   pari_sp av = avma;
    1706         343 :   long i, l = lg(v);
    1707        1183 :   for (i=1; i<l; i++)
    1708         868 :     if (!dvdii(gel(v,i), p)) return gc_long(av,0);
    1709         315 :   return gc_long(av,1);
    1710             : }
    1711             : 
    1712             : static long
    1713      572861 : gen_2valrem(GEN x, GEN *px, long imin)
    1714             : {
    1715      572861 :   long i, lx = lg(x), v = LONG_MAX;
    1716             :   GEN z;
    1717     4387573 :   for (i = imin; i < lx; i++)
    1718             :   {
    1719     4173578 :     GEN c = gel(x,i);
    1720             :     long w;
    1721     4173578 :     if (!signe(c)) continue;
    1722     3905284 :     w = vali(c);
    1723     3905284 :     if (w < v) {
    1724     1003218 :       v = w;
    1725     1003218 :       if (!v) { *px = x; return 0; } /* early abort */
    1726             :     }
    1727             :   }
    1728      213995 :   z = cgetg_copy(x, &lx); z[1] = x[1];
    1729     3586067 :   for (i=imin; i<lx; i++) gel(z,i) = shifti(gel(x,i), -v);
    1730      213995 :   *px = z; return v;
    1731             : }
    1732             : static long
    1733     1269926 : gen_lvalrem(GEN x, ulong p, GEN *px, long imin)
    1734             : {
    1735             :   long i, lx, v;
    1736             :   GEN y;
    1737     1269926 :   if (p == 2) return gen_2valrem(x, px, imin);
    1738      697065 :   y = cgetg_copy(x, &lx);
    1739      697065 :   y[1] = x[1];
    1740      697065 :   x = leafcopy(x);
    1741      697065 :   for(v = 0;; v++)
    1742             :   {
    1743     1164217 :     if (v == VAL_DC_THRESHOLD)
    1744             :     {
    1745        2751 :       if (p == 1) pari_err_DOMAIN("gen_lvalrem", "p", "=", gen_1, gen_1);
    1746        2751 :       v += gen_pvalrem_DC(x, sqru(p), px, imin) << 1;
    1747        2751 :       x = gen_z_divides(*px, p, imin);
    1748        2751 :       if (x) { *px = x; v++; }
    1749        2751 :       return v;
    1750             :     }
    1751             : 
    1752     6895390 :     for (i = imin; i < lx; i++)
    1753             :     {
    1754     6428238 :       ulong r; gel(y,i) = absdiviu_rem(gel(x,i), p, &r);
    1755     6428238 :       if (r) { *px = x; return v; }
    1756     5733924 :       affectsign_safe(gel(x,i), &gel(y,i));
    1757             :     }
    1758      467152 :     swap(x, y);
    1759             :   }
    1760             : }
    1761             : long
    1762         721 : ZX_lvalrem(GEN x, ulong p, GEN *px) { return gen_lvalrem(x,p,px, 2); }
    1763             : long
    1764           0 : ZV_lvalrem(GEN x, ulong p, GEN *px) { return gen_lvalrem(x,p,px, 1); }
    1765             : 
    1766             : static long
    1767     1283972 : gen_pvalrem(GEN x, GEN p, GEN *px, long imin)
    1768             : {
    1769             :   long i, lx, v;
    1770             :   GEN y;
    1771     1283972 :   if (lgefint(p) == 3) return gen_lvalrem(x, p[2], px, imin);
    1772       14767 :   y = cgetg_copy(x, &lx);
    1773       14767 :   y[1] = x[1];
    1774       14767 :   x = leafcopy(x);
    1775       14767 :   for(v = 0;; v++)
    1776             :   {
    1777       15493 :     if (v == VAL_DC_THRESHOLD)
    1778             :     {
    1779          14 :       if (is_pm1(p)) pari_err_DOMAIN("gen_pvalrem", "p", "=", p, p);
    1780          14 :       return v + gen_pvalrem_DC(x, p, px, imin);
    1781             :     }
    1782             : 
    1783       23730 :     for (i = imin; i < lx; i++)
    1784             :     {
    1785       23004 :       GEN r; gel(y,i) = dvmdii(gel(x,i), p, &r);
    1786       23004 :       if (r != gen_0) { *px = x; return v; }
    1787             :     }
    1788         726 :     swap(x, y);
    1789             :   }
    1790             : }
    1791             : long
    1792      632802 : ZX_pvalrem(GEN x, GEN p, GEN *px) { return gen_pvalrem(x,p,px, 2); }
    1793             : long
    1794      651170 : ZV_pvalrem(GEN x, GEN p, GEN *px) { return gen_pvalrem(x,p,px, 1); }
    1795             : 
    1796             : /*******************************************************************/
    1797             : /*                                                                 */
    1798             : /*                       NEGATION: Create -x                       */
    1799             : /*                                                                 */
    1800             : /*******************************************************************/
    1801             : 
    1802             : GEN
    1803   219597220 : gneg(GEN x)
    1804             : {
    1805             :   long lx, i;
    1806             :   GEN y;
    1807             : 
    1808   219597220 :   switch(typ(x))
    1809             :   {
    1810    70808122 :     case t_INT:
    1811    70808122 :       return signe(x)? negi(x): gen_0;
    1812   104510807 :     case t_REAL:
    1813   104510807 :       return mpneg(x);
    1814             : 
    1815      219415 :     case t_INTMOD: y=cgetg(3,t_INTMOD);
    1816      219415 :       gel(y,1) = icopy(gel(x,1));
    1817      219415 :       gel(y,2) = signe(gel(x,2))? subii(gel(y,1),gel(x,2)): gen_0;
    1818      219415 :       break;
    1819             : 
    1820     1588034 :     case t_FRAC:
    1821     1588034 :       y = cgetg(3, t_FRAC);
    1822     1588034 :       gel(y,1) = negi(gel(x,1));
    1823     1588034 :       gel(y,2) = icopy(gel(x,2)); break;
    1824             : 
    1825    40621430 :     case t_COMPLEX:
    1826    40621430 :       y=cgetg(3, t_COMPLEX);
    1827    40621430 :       gel(y,1) = gneg(gel(x,1));
    1828    40621430 :       gel(y,2) = gneg(gel(x,2));
    1829    40621430 :       break;
    1830             : 
    1831      198419 :     case t_POLMOD:
    1832      198419 :       retmkpolmod(gneg(gel(x,2)), RgX_copy(gel(x,1)));
    1833             : 
    1834      153272 :     case t_RFRAC:
    1835      153272 :       y = cgetg(3, t_RFRAC);
    1836      153272 :       gel(y,1) = gneg(gel(x,1));
    1837      153272 :       gel(y,2) = RgX_copy(gel(x,2)); break;
    1838             : 
    1839        6937 :     case t_PADIC:
    1840        6937 :       if (!signe(gel(x,4))) return gcopy(x);
    1841        5992 :       y = cgetg(5, t_PADIC);
    1842        5992 :       y[1] = x[1];
    1843        5992 :       gel(y,2) = icopy(gel(x,2));
    1844        5992 :       gel(y,3) = icopy(gel(x,3));
    1845        5992 :       gel(y,4) = subii(gel(x,3),gel(x,4));
    1846        5992 :       break;
    1847             : 
    1848         119 :     case t_QUAD:
    1849         119 :       y=cgetg(4,t_QUAD);
    1850         119 :       gel(y,1) = ZX_copy(gel(x,1));
    1851         119 :       gel(y,2) = gneg(gel(x,2));
    1852         119 :       gel(y,3) = gneg(gel(x,3)); break;
    1853             : 
    1854       40706 :     case t_FFELT: return FF_neg(x);
    1855     1367879 :     case t_POL: return RgX_neg(x);
    1856        1540 :     case t_SER:
    1857        1540 :       y = cgetg_copy(x, &lx); y[1] = x[1];
    1858       20195 :       for (i=2; i<lx; i++) gel(y,i) = gneg(gel(x,i));
    1859        1540 :       break;
    1860         987 :     case t_VEC: return RgV_neg(x);
    1861       76279 :     case t_COL: return RgC_neg(x);
    1862        2511 :     case t_MAT: return RgM_neg(x);
    1863         777 :     case t_INFINITY: return inf_get_sign(x) == 1? mkmoo(): mkoo();
    1864           0 :     default:
    1865           0 :       pari_err_TYPE("gneg",x);
    1866             :       return NULL; /* LCOV_EXCL_LINE */
    1867             :   }
    1868    42589802 :   return y;
    1869             : }
    1870             : 
    1871             : GEN
    1872    57060062 : gneg_i(GEN x)
    1873             : {
    1874             :   long lx, i;
    1875             :   GEN y;
    1876             : 
    1877    57060062 :   switch(typ(x))
    1878             :   {
    1879    30670765 :     case t_INT:
    1880    30670765 :       return signe(x)? negi(x): gen_0;
    1881     6354625 :     case t_REAL:
    1882     6354625 :       return mpneg(x);
    1883             : 
    1884     1088082 :     case t_INTMOD: y=cgetg(3,t_INTMOD);
    1885     1088082 :       gel(y,1) = gel(x,1);
    1886     1088082 :       gel(y,2) = signe(gel(x,2))? subii(gel(y,1),gel(x,2)): gen_0;
    1887     1088082 :       break;
    1888             : 
    1889     2945100 :     case t_FRAC:
    1890     2945100 :       y = cgetg(3, t_FRAC);
    1891     2945090 :       gel(y,1) = negi(gel(x,1));
    1892     2945105 :       gel(y,2) = gel(x,2); break;
    1893             : 
    1894     2248834 :     case t_COMPLEX:
    1895     2248834 :       y = cgetg(3, t_COMPLEX);
    1896     2248834 :       gel(y,1) = gneg_i(gel(x,1));
    1897     2248834 :       gel(y,2) = gneg_i(gel(x,2)); break;
    1898             : 
    1899     1744505 :     case t_PADIC: y = cgetg(5,t_PADIC);
    1900     1744505 :       y[1] = x[1];
    1901     1744505 :       gel(y,2) = gel(x,2);
    1902     1744505 :       gel(y,3) = gel(x,3);
    1903     1744505 :       gel(y,4) = signe(gel(x,4))? subii(gel(x,3),gel(x,4)): gen_0; break;
    1904             : 
    1905       77892 :     case t_POLMOD:
    1906       77892 :       retmkpolmod(gneg_i(gel(x,2)), RgX_copy(gel(x,1)));
    1907             : 
    1908       84693 :     case t_FFELT: return FF_neg_i(x);
    1909             : 
    1910         665 :     case t_QUAD: y=cgetg(4,t_QUAD);
    1911         665 :       gel(y,1) = gel(x,1);
    1912         665 :       gel(y,2) = gneg_i(gel(x,2));
    1913         665 :       gel(y,3) = gneg_i(gel(x,3)); break;
    1914             : 
    1915        1806 :     case t_VEC: case t_COL: case t_MAT:
    1916        1806 :       y = cgetg_copy(x, &lx);
    1917        9835 :       for (i=1; i<lx; i++) gel(y,i) = gneg_i(gel(x,i));
    1918        1806 :       break;
    1919             : 
    1920     6803881 :     case t_POL: case t_SER:
    1921     6803881 :       y = cgetg_copy(x, &lx); y[1]=x[1];
    1922    22769458 :       for (i=2; i<lx; i++) gel(y,i) = gneg_i(gel(x,i));
    1923     6803881 :       break;
    1924             : 
    1925     5039215 :     case t_RFRAC:
    1926     5039215 :       y = cgetg(3, t_RFRAC);
    1927     5039215 :       gel(y,1) = gneg_i(gel(x,1));
    1928     5039207 :       gel(y,2) = gel(x,2); break;
    1929             : 
    1930           0 :     default:
    1931           0 :       pari_err_TYPE("gneg_i",x);
    1932             :       return NULL; /* LCOV_EXCL_LINE */
    1933             :   }
    1934    19872085 :   return y;
    1935             : }
    1936             : 
    1937             : /******************************************************************/
    1938             : /*                                                                */
    1939             : /*                       ABSOLUTE VALUE                           */
    1940             : /*    Create abs(x) if x is integer, real, fraction or complex.   */
    1941             : /*                       Error otherwise.                         */
    1942             : /*                                                                */
    1943             : /******************************************************************/
    1944             : static int
    1945           0 : is_negative(GEN x) {
    1946           0 :   switch(typ(x))
    1947             :   {
    1948           0 :     case t_INT: case t_REAL:
    1949           0 :       return (signe(x) < 0);
    1950           0 :     case t_FRAC:
    1951           0 :       return (signe(gel(x,1)) < 0);
    1952             :   }
    1953           0 :   return 0;
    1954             : }
    1955             : 
    1956             : GEN
    1957    13332498 : gabs(GEN x, long prec)
    1958             : {
    1959             :   long lx, i;
    1960             :   pari_sp av, tetpil;
    1961             :   GEN y,p1;
    1962             : 
    1963    13332498 :   switch(typ(x))
    1964             :   {
    1965    10210896 :     case t_INT: case t_REAL:
    1966    10210896 :       return mpabs(x);
    1967             : 
    1968        4368 :     case t_FRAC:
    1969        4368 :       return absfrac(x);
    1970             : 
    1971     3106097 :     case t_COMPLEX:
    1972     3106097 :       av=avma; p1=cxnorm(x);
    1973     3106097 :       switch(typ(p1))
    1974             :       {
    1975         196 :         case t_INT:
    1976         196 :           if (!Z_issquareall(p1, &y)) break;
    1977          98 :           return gerepileupto(av, y);
    1978       16107 :         case t_FRAC: {
    1979             :           GEN a,b;
    1980       26656 :           if (!Z_issquareall(gel(p1,1), &a)) break;
    1981       10549 :           if (!Z_issquareall(gel(p1,2), &b)) break;
    1982           0 :           return gerepileupto(av, gdiv(a,b));
    1983             :         }
    1984             :       }
    1985     3105999 :       tetpil=avma;
    1986     3105999 :       return gerepile(av,tetpil,gsqrt(p1,prec));
    1987             : 
    1988          21 :     case t_QUAD:
    1989          21 :       av = avma;
    1990          21 :       return gerepileuptoleaf(av, gabs(quadtofp(x, prec), prec));
    1991             : 
    1992           0 :     case t_POL:
    1993           0 :       lx = lg(x); if (lx<=2) return RgX_copy(x);
    1994           0 :       return is_negative(gel(x,lx-1))? gneg(x): RgX_copy(x);
    1995             : 
    1996           7 :     case t_SER:
    1997           7 :      if (!signe(x)) pari_err_DOMAIN("abs", "argument", "=", gen_0, x);
    1998           7 :      if (valp(x)) pari_err_DOMAIN("abs", "series valuation", "!=", gen_0, x);
    1999           0 :      return is_negative(gel(x,2))? gneg(x): gcopy(x);
    2000             : 
    2001       11109 :     case t_VEC: case t_COL: case t_MAT:
    2002       11109 :       y = cgetg_copy(x, &lx);
    2003       86520 :       for (i=1; i<lx; i++) gel(y,i) = gabs(gel(x,i),prec);
    2004       11109 :       return y;
    2005             :   }
    2006           0 :   pari_err_TYPE("gabs",x);
    2007             :   return NULL; /* LCOV_EXCL_LINE */
    2008             : }
    2009             : 
    2010             : GEN
    2011           7 : gmax(GEN x, GEN y) { return gcopy(gmax_shallow(x,y)); }
    2012             : GEN
    2013           0 : gmaxgs(GEN x, long s) { return (gcmpsg(s,x)>=0)? stoi(s): gcopy(x); }
    2014             : 
    2015             : GEN
    2016        2331 : gmin(GEN x, GEN y) { return gcopy(gmin_shallow(x,y)); }
    2017             : GEN
    2018           0 : gmings(GEN x, long s) { return (gcmpsg(s,x)>0)? gcopy(x): stoi(s); }
    2019             : 
    2020             : long
    2021      161232 : vecindexmax(GEN x)
    2022             : {
    2023      161232 :   long lx = lg(x), i0, i;
    2024             :   GEN s;
    2025             : 
    2026      161232 :   if (lx==1) pari_err_DOMAIN("vecindexmax", "empty argument", "=", x,x);
    2027      161232 :   switch(typ(x))
    2028             :   {
    2029      161232 :     case t_VEC: case t_COL:
    2030      161232 :       s = gel(x,i0=1);
    2031      187626 :       for (i=2; i<lx; i++)
    2032       26394 :         if (gcmp(gel(x,i),s) > 0) s = gel(x,i0=i);
    2033      161232 :       return i0;
    2034           0 :     case t_VECSMALL:
    2035           0 :       return vecsmall_indexmax(x);
    2036           0 :     default: pari_err_TYPE("vecindexmax",x);
    2037             :   }
    2038             :   /* LCOV_EXCL_LINE */
    2039           0 :   return 0;
    2040             : }
    2041             : long
    2042       50730 : vecindexmin(GEN x)
    2043             : {
    2044       50730 :   long lx = lg(x), i0, i;
    2045             :   GEN s;
    2046             : 
    2047       50730 :   if (lx==1) pari_err_DOMAIN("vecindexmin", "empty argument", "=", x,x);
    2048       50730 :   switch(typ(x))
    2049             :   {
    2050       50730 :     case t_VEC: case t_COL:
    2051       50730 :       s = gel(x,i0=1);
    2052      214909 :       for (i=2; i<lx; i++)
    2053      164179 :         if (gcmp(gel(x,i),s) < 0) s = gel(x,i0=i);
    2054       50730 :       return i0;
    2055           0 :     case t_VECSMALL:
    2056           0 :       return vecsmall_indexmin(x);
    2057           0 :     default: pari_err_TYPE("vecindexmin",x);
    2058             :   }
    2059             :   /* LCOV_EXCL_LINE */
    2060           0 :   return 0;
    2061             : }
    2062             : 
    2063             : GEN
    2064        5605 : vecmax0(GEN x, GEN *pi)
    2065             : {
    2066        5605 :   long i, lx = lg(x), tx = typ(x);
    2067        5605 :   if (!is_matvec_t(tx) && tx != t_VECSMALL) return gcopy(x);
    2068        5591 :   if (lx==1) pari_err_DOMAIN("vecmax", "empty argument", "=", x,x);
    2069        5570 :   switch(typ(x))
    2070             :   {
    2071        5061 :     case t_VEC: case t_COL:
    2072        5061 :       i = vecindexmax(x); if (pi) *pi = utoipos(i);
    2073        5061 :       return gcopy(gel(x,i));
    2074         495 :     case t_MAT: {
    2075         495 :       long j, i0 = 1, j0 = 1, lx2 = lgcols(x);
    2076             :       GEN s;
    2077         495 :       if (lx2 == 1) pari_err_DOMAIN("vecmax", "empty argument", "=", x,x);
    2078         488 :       s = gcoeff(x,i0,j0); i = 2;
    2079        1800 :       for (j=1; j<lx; j++,i=1)
    2080             :       {
    2081        1312 :         GEN c = gel(x,j);
    2082       24644 :         for (; i<lx2; i++)
    2083       23332 :           if (gcmp(gel(c,i),s) > 0) { s = gel(c,i); j0=j; i0=i; }
    2084             :       }
    2085         488 :       if (pi) *pi = mkvec2(utoipos(i0), utoipos(j0));
    2086         488 :       return gcopy(s);
    2087             :     }
    2088          14 :     case t_VECSMALL:
    2089          14 :       i = vecsmall_indexmax(x); if (pi) *pi = utoipos(i);
    2090          14 :       return stoi(x[i]);
    2091             :   }
    2092             :   return NULL;/*LCOV_EXCL_LINE*/
    2093             : }
    2094             : GEN
    2095       18481 : vecmin0(GEN x, GEN *pi)
    2096             : {
    2097       18481 :   long i, lx = lg(x), tx = typ(x);
    2098       18481 :   if (!is_matvec_t(tx) && tx != t_VECSMALL) return gcopy(x);
    2099       18467 :   if (lx==1) pari_err_DOMAIN("vecmin", "empty argument", "=", x,x);
    2100       18453 :   switch(typ(x))
    2101             :   {
    2102       18425 :     case t_VEC: case t_COL:
    2103       18425 :       i = vecindexmin(x); if (pi) *pi = utoipos(i);
    2104       18425 :       return gcopy(gel(x,i));
    2105          14 :     case t_MAT: {
    2106          14 :       long j, i0 = 1, j0 = 1, lx2 = lgcols(x);
    2107             :       GEN s;
    2108          14 :       if (lx2 == 1) pari_err_DOMAIN("vecmin", "empty argument", "=", x,x);
    2109          14 :       s = gcoeff(x,i0,j0); i = 2;
    2110          42 :       for (j=1; j<lx; j++,i=1)
    2111             :       {
    2112          28 :         GEN c = gel(x,j);
    2113          70 :         for (; i<lx2; i++)
    2114          42 :           if (gcmp(gel(c,i),s) < 0) { s = gel(c,i); j0=j; i0=i; }
    2115             :       }
    2116          14 :       if (pi) *pi = mkvec2(utoipos(i0), utoipos(j0));
    2117          14 :       return gcopy(s);
    2118             :     }
    2119          14 :     case t_VECSMALL:
    2120          14 :       i = vecsmall_indexmin(x); if (pi) *pi = utoipos(i);
    2121          14 :       return stoi(x[i]);
    2122             :   }
    2123             :   return NULL;/*LCOV_EXCL_LINE*/
    2124             : }
    2125             : 
    2126             : GEN
    2127        2938 : vecmax(GEN x) { return vecmax0(x, NULL); }
    2128             : GEN
    2129       18404 : vecmin(GEN x) { return vecmin0(x, NULL); }
    2130             : 
    2131             : /*******************************************************************/
    2132             : /*                                                                 */
    2133             : /*                      AFFECT long --> GEN                        */
    2134             : /*         affect long s to GEN x. Useful for initialization.      */
    2135             : /*                                                                 */
    2136             : /*******************************************************************/
    2137             : 
    2138             : static void
    2139           0 : padicaff0(GEN x)
    2140             : {
    2141           0 :   if (signe(gel(x,4)))
    2142             :   {
    2143           0 :     x[1] = evalvalp(valp(x)+precp(x));
    2144           0 :     affsi(0,gel(x,4));
    2145             :   }
    2146           0 : }
    2147             : 
    2148             : void
    2149         966 : gaffsg(long s, GEN x)
    2150             : {
    2151         966 :   switch(typ(x))
    2152             :   {
    2153           0 :     case t_INT: affsi(s,x); break;
    2154         966 :     case t_REAL: affsr(s,x); break;
    2155           0 :     case t_INTMOD: modsiz(s,gel(x,1),gel(x,2)); break;
    2156           0 :     case t_FRAC: affsi(s,gel(x,1)); affsi(1,gel(x,2)); break;
    2157           0 :     case t_COMPLEX: gaffsg(s,gel(x,1)); gaffsg(0,gel(x,2)); break;
    2158           0 :     case t_PADIC: {
    2159             :       long vx;
    2160             :       GEN y;
    2161           0 :       if (!s) { padicaff0(x); break; }
    2162           0 :       vx = Z_pvalrem(stoi(s), gel(x,2), &y);
    2163           0 :       setvalp(x,vx); modiiz(y,gel(x,3),gel(x,4));
    2164           0 :       break;
    2165             :     }
    2166           0 :     case t_QUAD: gaffsg(s,gel(x,2)); gaffsg(0,gel(x,3)); break;
    2167           0 :     default: pari_err_TYPE2("=",stoi(s),x);
    2168             :   }
    2169         966 : }
    2170             : 
    2171             : /*******************************************************************/
    2172             : /*                                                                 */
    2173             : /*                     GENERIC AFFECTATION                         */
    2174             : /*         Affect the content of x to y, whenever possible         */
    2175             : /*                                                                 */
    2176             : /*******************************************************************/
    2177             : /* x PADIC, Y INT, return lift(x * Mod(1,Y)) */
    2178             : GEN
    2179        4417 : padic_to_Fp(GEN x, GEN Y) {
    2180        4417 :   pari_sp av = avma;
    2181        4417 :   GEN p = gel(x,2), z;
    2182        4417 :   long vy, vx = valp(x);
    2183        4417 :   if (!signe(Y)) pari_err_INV("padic_to_Fp",Y);
    2184        4417 :   vy = Z_pvalrem(Y,p, &z);
    2185        4417 :   if (vx < 0 || !gequal1(z)) pari_err_OP("",x, mkintmod(gen_1,Y));
    2186        4403 :   if (vx >= vy) { set_avma(av); return gen_0; }
    2187        4059 :   z = gel(x,4);
    2188        4059 :   if (!signe(z) || vy > vx + precp(x)) pari_err_OP("",x, mkintmod(gen_1,Y));
    2189        4059 :   if (vx) z = mulii(z, powiu(p,vx));
    2190        4059 :   return gerepileuptoint(av, remii(z, Y));
    2191             : }
    2192             : ulong
    2193          77 : padic_to_Fl(GEN x, ulong Y) {
    2194          77 :   GEN p = gel(x,2);
    2195             :   ulong u, z;
    2196          77 :   long vy, vx = valp(x);
    2197          77 :   vy = u_pvalrem(Y,p, &u);
    2198          77 :   if (vx < 0 || u != 1) pari_err_OP("",x, mkintmodu(1,Y));
    2199             :   /* Y = p^vy */
    2200          77 :   if (vx >= vy) return 0;
    2201          70 :   z = umodiu(gel(x,4), Y);
    2202          70 :   if (!z || vy > vx + precp(x)) pari_err_OP("",x, mkintmodu(1,Y));
    2203          70 :   if (vx) {
    2204           0 :     ulong pp = p[2];
    2205           0 :     z = Fl_mul(z, upowuu(pp,vx), Y); /* p^vx < p^vy = Y */
    2206             :   }
    2207          70 :   return z;
    2208             : }
    2209             : 
    2210             : static void
    2211           0 : croak(const char *s) {
    2212             :   char *t;
    2213           0 :   t = stack_sprintf("gaffect [overwriting universal object: %s]",s);
    2214           0 :   pari_err_BUG(t);
    2215           0 : }
    2216             : 
    2217             : void
    2218      199547 : gaffect(GEN x, GEN y)
    2219             : {
    2220      199547 :   long vx, i, lx, ly, tx = typ(x), ty = typ(y);
    2221             :   pari_sp av;
    2222             :   GEN p1, num, den;
    2223             : 
    2224      199547 :   if (tx == ty) switch(tx) {
    2225      119995 :     case t_INT:
    2226      198581 :       if (!is_universal_constant(y)) { affii(x,y); return; }
    2227             :       /* y = gen_0, gnil, gen_1 or gen_2 */
    2228           0 :       if (y==gen_0)  croak("gen_0");
    2229           0 :       if (y==gen_1)  croak("gen_1");
    2230           0 :       if (y==gen_m1) croak("gen_m1");
    2231           0 :       if (y==gen_m2) croak("gen_m2");
    2232           0 :       if (y==gen_2)  croak("gen_2");
    2233           0 :       croak("gnil)");
    2234        4606 :     case t_REAL: affrr(x,y); return;
    2235           0 :     case t_INTMOD:
    2236           0 :       if (!dvdii(gel(x,1),gel(y,1))) pari_err_OP("",x,y);
    2237           0 :       modiiz(gel(x,2),gel(y,1),gel(y,2)); return;
    2238           0 :     case t_FRAC:
    2239           0 :       affii(gel(x,1),gel(y,1));
    2240           0 :       affii(gel(x,2),gel(y,2)); return;
    2241        1820 :     case t_COMPLEX:
    2242        1820 :       gaffect(gel(x,1),gel(y,1));
    2243        1820 :       gaffect(gel(x,2),gel(y,2)); return;
    2244           0 :     case t_PADIC:
    2245           0 :       if (!equalii(gel(x,2),gel(y,2))) pari_err_OP("",x,y);
    2246           0 :       modiiz(gel(x,4),gel(y,3),gel(y,4));
    2247           0 :       setvalp(y,valp(x)); return;
    2248           0 :     case t_QUAD:
    2249           0 :       if (! ZX_equal(gel(x,1),gel(y,1))) pari_err_OP("",x,y);
    2250           0 :       affii(gel(x,2),gel(y,2));
    2251           0 :       affii(gel(x,3),gel(y,3)); return;
    2252       72160 :     case t_VEC: case t_COL: case t_MAT:
    2253       72160 :       lx = lg(x); if (lx != lg(y)) pari_err_DIM("gaffect");
    2254      192155 :       for (i=1; i<lx; i++) gaffect(gel(x,i),gel(y,i));
    2255       72160 :       return;
    2256             :   }
    2257             : 
    2258             :   /* Various conversions. Avoid them, use specialized routines ! */
    2259             : 
    2260         966 :   if (!is_const_t(ty)) pari_err_TYPE2("=",x,y);
    2261         966 :   switch(tx)
    2262             :   {
    2263           0 :     case t_INT:
    2264             :       switch(ty)
    2265             :       {
    2266           0 :         case t_REAL:
    2267           0 :           affir(x,y); break;
    2268             : 
    2269           0 :         case t_INTMOD:
    2270           0 :           modiiz(x,gel(y,1),gel(y,2)); break;
    2271             : 
    2272           0 :         case t_COMPLEX:
    2273           0 :           gaffect(x,gel(y,1)); gaffsg(0,gel(y,2)); break;
    2274             : 
    2275           0 :         case t_PADIC:
    2276           0 :           if (!signe(x)) { padicaff0(y); break; }
    2277           0 :           av = avma;
    2278           0 :           setvalp(y, Z_pvalrem(x,gel(y,2),&p1));
    2279           0 :           affii(modii(p1,gel(y,3)), gel(y,4));
    2280           0 :           set_avma(av); break;
    2281             : 
    2282           0 :         case t_QUAD: gaffect(x,gel(y,2)); gaffsg(0,gel(y,3)); break;
    2283           0 :         default: pari_err_TYPE2("=",x,y);
    2284             :       }
    2285           0 :       break;
    2286             : 
    2287         966 :     case t_REAL:
    2288             :       switch(ty)
    2289             :       {
    2290         966 :         case t_COMPLEX: gaffect(x,gel(y,1)); gaffsg(0,gel(y,2)); break;
    2291           0 :         default: pari_err_TYPE2("=",x,y);
    2292             :       }
    2293         966 :       break;
    2294             : 
    2295           0 :     case t_FRAC:
    2296             :       switch(ty)
    2297             :       {
    2298           0 :         case t_REAL: rdiviiz(gel(x,1),gel(x,2), y); break;
    2299           0 :         case t_INTMOD: av = avma;
    2300           0 :           p1 = Fp_inv(gel(x,2),gel(y,1));
    2301           0 :           affii(modii(mulii(gel(x,1),p1),gel(y,1)), gel(y,2));
    2302           0 :           set_avma(av); break;
    2303           0 :         case t_COMPLEX: gaffect(x,gel(y,1)); gaffsg(0,gel(y,2)); break;
    2304           0 :         case t_PADIC:
    2305           0 :           if (!signe(gel(x,1))) { padicaff0(y); break; }
    2306           0 :           num = gel(x,1);
    2307           0 :           den = gel(x,2);
    2308           0 :           av = avma; vx = Z_pvalrem(num, gel(y,2), &num);
    2309           0 :           if (!vx) vx = -Z_pvalrem(den,gel(y,2),&den);
    2310           0 :           setvalp(y,vx);
    2311           0 :           p1 = mulii(num,Fp_inv(den,gel(y,3)));
    2312           0 :           affii(modii(p1,gel(y,3)), gel(y,4)); set_avma(av); break;
    2313           0 :         case t_QUAD: gaffect(x,gel(y,2)); gaffsg(0,gel(y,3)); break;
    2314           0 :         default: pari_err_TYPE2("=",x,y);
    2315             :       }
    2316           0 :       break;
    2317             : 
    2318           0 :     case t_COMPLEX:
    2319           0 :       if (!gequal0(gel(x,2))) pari_err_TYPE2("=",x,y);
    2320           0 :       gaffect(gel(x,1), y);
    2321           0 :       break;
    2322             : 
    2323           0 :     case t_PADIC:
    2324             :       switch(ty)
    2325             :       {
    2326           0 :         case t_INTMOD:
    2327           0 :           av = avma; affii(padic_to_Fp(x, gel(y,1)), gel(y,2));
    2328           0 :           set_avma(av); break;
    2329           0 :         default: pari_err_TYPE2("=",x,y);
    2330             :       }
    2331           0 :       break;
    2332             : 
    2333           0 :     case t_QUAD:
    2334             :       switch(ty)
    2335             :       {
    2336           0 :         case t_INT: case t_INTMOD: case t_FRAC: case t_PADIC:
    2337           0 :           pari_err_TYPE2("=",x,y);
    2338             : 
    2339           0 :         case t_REAL:
    2340           0 :           av = avma; affgr(quadtofp(x,realprec(y)), y); set_avma(av); break;
    2341           0 :         case t_COMPLEX:
    2342           0 :           ly = precision(y); if (!ly) pari_err_TYPE2("=",x,y);
    2343           0 :           av = avma; gaffect(quadtofp(x,ly), y); set_avma(av); break;
    2344           0 :         default: pari_err_TYPE2("=",x,y);
    2345             :       }
    2346           0 :     default: pari_err_TYPE2("=",x,y);
    2347             :   }
    2348             : }
    2349             : 
    2350             : /*******************************************************************/
    2351             : /*                                                                 */
    2352             : /*           CONVERSION QUAD --> REAL, COMPLEX OR P-ADIC           */
    2353             : /*                                                                 */
    2354             : /*******************************************************************/
    2355             : GEN
    2356         231 : quadtofp(GEN x, long prec)
    2357             : {
    2358         231 :   GEN b, mb2, c, z, Q, u = gel(x,2), v = gel(x,3);
    2359             :   pari_sp av;
    2360         231 :   if (prec < LOWDEFAULTPREC) prec = LOWDEFAULTPREC;
    2361         231 :   if (isintzero(v)) return cxcompotor(u, prec);
    2362         231 :   av = avma; Q = gel(x,1); c = gel(Q,2); b = gel(Q,3);
    2363         231 :   z = sqrtr_abs(itor(quad_disc(x), prec));
    2364         231 :   shiftr_inplace(z, -1);
    2365         231 :   mb2 = signe(b) ? real2n(-1, prec): NULL;
    2366         231 :   if (signe(c) > 0) /* c = -D/4 or (1-D)/4 */
    2367          35 :     z = mkcomplex(mb2? mb2: real_0(prec), z);
    2368         196 :   else if (mb2)
    2369         196 :     z = addrr(z, mb2);
    2370             :   /* z = (-b + sqrt(D)) / 2 */
    2371         231 :   return gerepileupto(av, gadd(u, gmul(v,z)));
    2372             : }
    2373             : 
    2374             : static GEN
    2375          28 : qtop(GEN x, GEN p, long d)
    2376             : {
    2377          28 :   GEN z, D, P, b, u = gel(x,2), v = gel(x,3);
    2378             :   pari_sp av;
    2379          28 :   if (gequal0(v)) return cvtop(u, p, d);
    2380          28 :   P = gel(x,1);
    2381          28 :   b = gel(P,3);
    2382          28 :   av = avma; D = quad_disc(x);
    2383          28 :   if (absequaliu(p,2)) d += 2;
    2384          28 :   z = Qp_sqrt(cvtop(D,p,d));
    2385          28 :   if (!z) pari_err_SQRTN("Qp_sqrt",D);
    2386          14 :   z = gmul2n(gsub(z, b), -1);
    2387             : 
    2388          14 :   z = gadd(u, gmul(v, z));
    2389          14 :   if (typ(z) != t_PADIC) /* t_INTMOD for t_QUAD of t_INTMODs... */
    2390           0 :     z = cvtop(z, p, d);
    2391          14 :   return gerepileupto(av, z);
    2392             : }
    2393             : static GEN
    2394          14 : ctop(GEN x, GEN p, long d)
    2395             : {
    2396          14 :   pari_sp av = avma;
    2397          14 :   GEN z, u = gel(x,1), v = gel(x,2);
    2398          14 :   if (isrationalzero(v)) return cvtop(u, p, d);
    2399          14 :   z = Qp_sqrt(cvtop(gen_m1, p, d - gvaluation(v, p))); /* = I */
    2400          14 :   if (!z) pari_err_SQRTN("Qp_sqrt",gen_m1);
    2401             : 
    2402          14 :   z = gadd(u, gmul(v, z));
    2403          14 :   if (typ(z) != t_PADIC) /* t_INTMOD for t_COMPLEX of t_INTMODs... */
    2404           0 :     z = cvtop(z, p, d);
    2405          14 :   return gerepileupto(av, z);
    2406             : }
    2407             : 
    2408             : /* cvtop2(stoi(s), y) */
    2409             : GEN
    2410           0 : cvstop2(long s, GEN y)
    2411             : {
    2412           0 :   GEN z, p = gel(y,2);
    2413           0 :   long v, d = signe(gel(y,4))? precp(y): 0;
    2414           0 :   if (!s) return zeropadic(p, d);
    2415           0 :   v = z_pvalrem(s, p, &s);
    2416           0 :   if (d <= 0) return zeropadic(p, v);
    2417           0 :   z = cgetg(5, t_PADIC);
    2418           0 :   z[1] = evalprecp(d) | evalvalp(v);
    2419           0 :   gel(z,2) = p;
    2420           0 :   gel(z,3) = gel(y,3);
    2421           0 :   gel(z,4) = modsi(s, gel(y,3)); return z;
    2422             : }
    2423             : 
    2424             : /* cvtop(x, gel(y,2), precp(y)), shallow */
    2425             : GEN
    2426     1700421 : cvtop2(GEN x, GEN y)
    2427             : {
    2428     1700421 :   GEN z, p = gel(y,2);
    2429     1700421 :   long v, d = signe(gel(y,4))? precp(y): 0;
    2430     1700421 :   switch(typ(x))
    2431             :   {
    2432      917473 :     case t_INT:
    2433      917473 :       if (!signe(x)) return zeropadic(p, d);
    2434      917473 :       if (d <= 0) return zeropadic(p, Z_pval(x,p));
    2435      912774 :       v = Z_pvalrem(x, p, &x);
    2436      912696 :       z = cgetg(5, t_PADIC);
    2437      912761 :       z[1] = evalprecp(d) | evalvalp(v);
    2438      912767 :       gel(z,2) = p;
    2439      912767 :       gel(z,3) = gel(y,3);
    2440      912767 :       gel(z,4) = modii(x, gel(y,3)); return z;
    2441             : 
    2442           0 :     case t_INTMOD:
    2443           0 :       v = Z_pval(gel(x,1),p); if (v > d) v = d;
    2444           0 :       return cvtop(gel(x,2), p, v);
    2445             : 
    2446      782914 :     case t_FRAC:
    2447             :     {
    2448             :       GEN num, den;
    2449      782914 :       if (d <= 0) return zeropadic(p, Q_pval(x,p));
    2450      781633 :       num = gel(x,1); v = Z_pvalrem(num, p, &num);
    2451      781633 :       den = gel(x,2); if (!v) v = -Z_pvalrem(den, p, &den);
    2452      781633 :       z = cgetg(5, t_PADIC);
    2453      781633 :       z[1] = evalprecp(d) | evalvalp(v);
    2454      781633 :       gel(z,2) = p;
    2455      781633 :       gel(z,3) = gel(y,3);
    2456      781633 :       if (!is_pm1(den)) num = mulii(num, Fp_inv(den, gel(y,3)));
    2457      781633 :       gel(z,4) = modii(num, gel(y,3)); return z;
    2458             :     }
    2459           7 :     case t_COMPLEX: return ctop(x, p, d);
    2460          28 :     case t_QUAD:    return qtop(x, p, d);
    2461             :   }
    2462           0 :   pari_err_TYPE("cvtop2",x);
    2463             :   return NULL; /* LCOV_EXCL_LINE */
    2464             : }
    2465             : 
    2466             : /* assume is_const_t(tx) */
    2467             : GEN
    2468      348097 : cvtop(GEN x, GEN p, long d)
    2469             : {
    2470             :   GEN z;
    2471             :   long v;
    2472             : 
    2473      348097 :   if (typ(p) != t_INT) pari_err_TYPE("cvtop",p);
    2474      348097 :   switch(typ(x))
    2475             :   {
    2476       39440 :     case t_INT:
    2477       39440 :       if (!signe(x)) return zeropadic(p, d);
    2478       38236 :       if (d <= 0) return zeropadic(p, Z_pval(x,p));
    2479       38229 :       v = Z_pvalrem(x, p, &x);
    2480       38229 :       z = cgetg(5, t_PADIC);
    2481       38229 :       z[1] = evalprecp(d) | evalvalp(v);
    2482       38229 :       gel(z,2) = icopy(p);
    2483       38229 :       gel(z,3) = powiu(p, d);
    2484       38229 :       gel(z,4) = modii(x, gel(z,3)); return z; /* not memory-clean */
    2485             : 
    2486          28 :     case t_INTMOD:
    2487          28 :       v = Z_pval(gel(x,1),p); if (v > d) v = d;
    2488          28 :       return cvtop(gel(x,2), p, v);
    2489             : 
    2490      154031 :     case t_FRAC:
    2491             :     {
    2492             :       GEN num, den;
    2493      154031 :       if (d <= 0) return zeropadic(p, Q_pval(x,p));
    2494      154031 :       num = gel(x,1); v = Z_pvalrem(num, p, &num);
    2495      154031 :       den = gel(x,2); if (!v) v = -Z_pvalrem(den, p, &den);
    2496      154031 :       z = cgetg(5, t_PADIC);
    2497      154031 :       z[1] = evalprecp(d) | evalvalp(v);
    2498      154031 :       gel(z,2) = icopy(p);
    2499      154031 :       gel(z,3) = powiu(p, d);
    2500      154031 :       if (!is_pm1(den)) num = mulii(num, Fp_inv(den, gel(z,3)));
    2501      154031 :       gel(z,4) = modii(num, gel(z,3)); return z; /* not memory-clean */
    2502             :     }
    2503           7 :     case t_COMPLEX: return ctop(x, p, d);
    2504      154591 :     case t_PADIC:
    2505      154591 :       p = gel(x,2); /* override */
    2506      154591 :       if (!signe(gel(x,4))) return zeropadic(p, d);
    2507      154591 :       z = cgetg(5,t_PADIC);
    2508      154591 :       z[1] = x[1]; setprecp(z,d);
    2509      154591 :       gel(z,2) = icopy(p);
    2510      154591 :       gel(z,3) = powiu(p, d);
    2511      154591 :       gel(z,4) = modii(gel(x,4), gel(z,3)); return z;
    2512             : 
    2513           0 :     case t_QUAD: return qtop(x, p, d);
    2514             :   }
    2515           0 :   pari_err_TYPE("cvtop",x);
    2516             :   return NULL; /* LCOV_EXCL_LINE */
    2517             : }
    2518             : 
    2519             : GEN
    2520          70 : gcvtop(GEN x, GEN p, long r)
    2521             : {
    2522             :   long i, lx;
    2523             :   GEN y;
    2524             : 
    2525          70 :   switch(typ(x))
    2526             :   {
    2527          21 :     case t_POL: case t_SER:
    2528          21 :       y = cgetg_copy(x, &lx); y[1] = x[1];
    2529          70 :       for (i=2; i<lx; i++) gel(y,i) = gcvtop(gel(x,i),p,r);
    2530          21 :       return y;
    2531           0 :     case t_POLMOD: case t_RFRAC: case t_VEC: case t_COL: case t_MAT:
    2532           0 :       y = cgetg_copy(x, &lx);
    2533           0 :       for (i=1; i<lx; i++) gel(y,i) = gcvtop(gel(x,i),p,r);
    2534           0 :       return y;
    2535             :   }
    2536          49 :   return cvtop(x,p,r);
    2537             : }
    2538             : 
    2539             : long
    2540   118816197 : gexpo_safe(GEN x)
    2541             : {
    2542   118816197 :   long tx = typ(x), lx, e, f, i;
    2543             : 
    2544   118816197 :   switch(tx)
    2545             :   {
    2546    16576560 :     case t_INT:
    2547    16576560 :       return expi(x);
    2548             : 
    2549      194056 :     case t_FRAC:
    2550      194056 :       return expi(gel(x,1)) - expi(gel(x,2));
    2551             : 
    2552    72142659 :     case t_REAL:
    2553    72142659 :       return expo(x);
    2554             : 
    2555    19667566 :     case t_COMPLEX:
    2556    19667566 :       e = gexpo(gel(x,1));
    2557    19667566 :       f = gexpo(gel(x,2)); return maxss(e, f);
    2558             : 
    2559          77 :     case t_QUAD: {
    2560          77 :       GEN p = gel(x,1); /* mod = X^2 + {0,1}* X - {D/4, (1-D)/4})*/
    2561          77 :       long d = 1 + expi(gel(p,2))/2; /* ~ expo(sqrt(D)) */
    2562          77 :       e = gexpo(gel(x,2));
    2563          77 :       f = gexpo(gel(x,3)) + d; return maxss(e, f);
    2564             :     }
    2565     9747032 :     case t_POL: case t_SER:
    2566     9747032 :       lx = lg(x); f = -(long)HIGHEXPOBIT;
    2567    46717141 :       for (i=2; i<lx; i++) { e=gexpo(gel(x,i)); if (e>f) f=e; }
    2568     9747032 :       return f;
    2569      488203 :     case t_VEC: case t_COL: case t_MAT:
    2570      488203 :       lx = lg(x); f = -(long)HIGHEXPOBIT;
    2571     6953301 :       for (i=1; i<lx; i++) { e=gexpo(gel(x,i)); if (e>f) f=e; }
    2572      488203 :       return f;
    2573             :   }
    2574          44 :   return -1-(long)HIGHEXPOBIT;
    2575             : }
    2576             : long
    2577   118533778 : gexpo(GEN x)
    2578             : {
    2579   118533778 :   long e = gexpo_safe(x);
    2580   118533779 :   if (e < -(long)HIGHEXPOBIT) pari_err_TYPE("gexpo",x);
    2581   118533772 :   return e;
    2582             : }
    2583             : GEN
    2584        8708 : gpexponent(GEN x)
    2585             : {
    2586        8708 :   long e = gexpo(x);
    2587        8708 :   return e == -(long)HIGHEXPOBIT? mkmoo(): stoi(e);
    2588             : }
    2589             : 
    2590             : long
    2591           7 : sizedigit(GEN x)
    2592             : {
    2593           7 :   return gequal0(x)? 0: (long) ((gexpo(x)+1) * LOG10_2) + 1;
    2594             : }
    2595             : 
    2596             : /* normalize series. avma is not updated */
    2597             : GEN
    2598     8237804 : normalize(GEN x)
    2599             : {
    2600     8237804 :   long i, lx = lg(x), vx=varn(x), vp=valp(x);
    2601             :   GEN y, z;
    2602             : 
    2603     8237804 :   if (typ(x) != t_SER) pari_err_TYPE("normalize",x);
    2604     8237804 :   if (lx == 2) { setsigne(x,0); return x; }
    2605     8237440 :   if (lx == 3) {
    2606      169767 :     z = gel(x,2);
    2607      169767 :     if (!gequal0(z)) { setsigne(x,1); return x; }
    2608       21797 :     if (isrationalzero(z)) return zeroser(vx,vp+1);
    2609        3044 :     if (isexactzero(z)) {
    2610             :       /* dangerous case: already normalized ? */
    2611          21 :       if (!signe(x)) return x;
    2612          14 :       setvalp(x,vp+1); /* no: normalize */
    2613             :     }
    2614        3037 :     setsigne(x,0); return x;
    2615             :   }
    2616     8347929 :   for (i=2; i<lx; i++)
    2617     8301036 :     if (! isrationalzero(gel(x,i))) break;
    2618     8067673 :   if (i == lx) return zeroser(vx,lx-2+vp);
    2619     8020780 :   z = gel(x,i);
    2620     8026828 :   while (i<lx && isexactzero(gel(x,i))) i++;
    2621     8020780 :   if (i == lx)
    2622             :   {
    2623         840 :     i -= 3; y = x + i;
    2624         840 :     stackdummy((pari_sp)y, (pari_sp)x);
    2625         840 :     gel(y,2) = z;
    2626         840 :     y[1] = evalsigne(0) | evalvalp(lx-2+vp) | evalvarn(vx);
    2627         840 :     y[0] = evaltyp(t_SER) | _evallg(3);
    2628         840 :     return y;
    2629             :   }
    2630             : 
    2631     8019940 :   i -= 2; y = x + i; lx -= i;
    2632     8019940 :   y[1] = evalsigne(1) | evalvalp(vp+i) | evalvarn(vx);
    2633     8019940 :   y[0] = evaltyp(t_SER) | evallg(lx);
    2634             : 
    2635     8019940 :   stackdummy((pari_sp)y, (pari_sp)x);
    2636     8041411 :   for (i = 2; i < lx; i++)
    2637     8040524 :     if (!gequal0(gel(y, i))) return y;
    2638         887 :   setsigne(y, 0); return y;
    2639             : }
    2640             : 
    2641             : GEN
    2642           0 : normalizepol_approx(GEN x, long lx)
    2643             : {
    2644             :   long i;
    2645           0 :   for (i = lx-1; i>1; i--)
    2646           0 :     if (! gequal0(gel(x,i))) break;
    2647           0 :   stackdummy((pari_sp)(x + lg(x)), (pari_sp)(x + i+1));
    2648           0 :   setlg(x, i+1); setsigne(x, i!=1); return x;
    2649             : }
    2650             : 
    2651             : GEN
    2652   237731227 : normalizepol_lg(GEN x, long lx)
    2653             : {
    2654   237731227 :   long i, LX = 0;
    2655   237731227 :   GEN KEEP = NULL;
    2656             : 
    2657   320891486 :   for (i = lx-1; i>1; i--)
    2658             :   {
    2659   295073756 :     GEN z = gel(x,i);
    2660   295073756 :     if (! gequal0(z) ) {
    2661   211913724 :       if (!LX) LX = i+1;
    2662   211913724 :       stackdummy((pari_sp)(x + lg(x)), (pari_sp)(x + LX));
    2663   211921332 :       x[0] = evaltyp(t_POL) | evallg(LX);
    2664   211923337 :       setsigne(x,1); return x;
    2665    83159625 :     } else if (!isexactzero(z)) {
    2666      238804 :       if (!LX) LX = i+1; /* to be kept as leading coeff */
    2667    82921449 :     } else if (!isrationalzero(z))
    2668      689619 :       KEEP = z; /* to be kept iff all other coeffs are exact 0s */
    2669             :   }
    2670    25817730 :   if (!LX) {
    2671    25745278 :     if (KEEP) { /* e.g. Pol(Mod(0,2)) */
    2672      344312 :       gel(x,2) = KEEP;
    2673      344312 :       LX = 3;
    2674             :     } else
    2675    25400966 :       LX = 2; /* Pol(0) */
    2676             :   }
    2677    25817730 :   stackdummy((pari_sp)(x + lg(x)), (pari_sp)(x + LX));
    2678    25818141 :   x[0] = evaltyp(t_POL) | evallg(LX);
    2679    25818141 :   setsigne(x,0); return x;
    2680             : }
    2681             : 
    2682             : /* normalize polynomial x in place */
    2683             : GEN
    2684    11876432 : normalizepol(GEN x)
    2685             : {
    2686    11876432 :   return normalizepol_lg(x, lg(x));
    2687             : }
    2688             : 
    2689             : int
    2690     5363869 : gsigne(GEN x)
    2691             : {
    2692     5363869 :   switch(typ(x))
    2693             :   {
    2694     5127181 :     case t_INT: case t_REAL: return signe(x);
    2695      236058 :     case t_FRAC: return signe(gel(x,1));
    2696         623 :     case t_QUAD:
    2697             :     {
    2698         623 :       pari_sp av = avma;
    2699         623 :       GEN T = gel(x,1), a = gel(x,2), b = gel(x,3);
    2700             :       long sa, sb;
    2701         623 :       if (signe(gel(T,2)) > 0) break;
    2702         609 :       a = gmul2n(a,1);
    2703         609 :       if (signe(gel(T,3))) a = gadd(a,b);
    2704             :       /* a + b sqrt(D) > 0 ? */
    2705         609 :       sa = gsigne(a);
    2706         609 :       sb = gsigne(b); if (sa == sb) return gc_int(av,sa);
    2707         224 :       if (sa == 0) return gc_int(av,sb);
    2708         217 :       if (sb == 0) return gc_int(av,sa);
    2709             :       /* different signs, take conjugate expression */
    2710         210 :       sb = gsigne(gsub(gsqr(a), gmul(quad_disc(x), gsqr(b))));
    2711         210 :       return gc_int(av, sb*sa);
    2712             :     }
    2713           7 :     case t_INFINITY: return inf_get_sign(x);
    2714             :   }
    2715          14 :   pari_err_TYPE("gsigne",x);
    2716             :   return 0; /* LCOV_EXCL_LINE */
    2717             : }
    2718             : 
    2719             : /*******************************************************************/
    2720             : /*                                                                 */
    2721             : /*                              LISTS                              */
    2722             : /*                                                                 */
    2723             : /*******************************************************************/
    2724             : /* make sure L can hold l elements, at least doubling the previous max number
    2725             :  * of components. */
    2726             : static void
    2727      786275 : ensure_nb(GEN L, long l)
    2728             : {
    2729      786275 :   long nmax = list_nmax(L), i, lw;
    2730             :   GEN v, w;
    2731      786275 :   if (l <= nmax) return;
    2732         399 :   if (nmax)
    2733             :   {
    2734         273 :     nmax <<= 1;
    2735         273 :     if (l > nmax) nmax = l;
    2736         273 :     w = list_data(L); lw = lg(w);
    2737         273 :     v = newblock(nmax+1);
    2738         273 :     v[0] = w[0];
    2739     1045653 :     for (i=1; i < lw; i++) gel(v,i) = gel(w, i);
    2740         273 :     killblock(w);
    2741             :   }
    2742             :   else /* unallocated */
    2743             :   {
    2744         126 :     nmax = 32;
    2745         126 :     if (list_data(L))
    2746           0 :       pari_err(e_MISC, "store list in variable before appending elements");
    2747         126 :     v = newblock(nmax+1);
    2748         126 :     v[0] = evaltyp(t_VEC) | _evallg(1);
    2749             :   }
    2750         399 :   list_data(L) = v;
    2751         399 :   L[1] = evaltyp(list_typ(L))|evallg(nmax);
    2752             : }
    2753             : 
    2754             : void
    2755           7 : listkill(GEN L)
    2756             : {
    2757             : 
    2758           7 :   if (typ(L) != t_LIST) pari_err_TYPE("listkill",L);
    2759           7 :   if (list_nmax(L)) {
    2760           7 :     GEN v = list_data(L);
    2761           7 :     long i, l = lg(v);
    2762          49 :     for (i=1; i<l; i++) gunclone_deep(gel(v,i));
    2763           7 :     killblock(v);
    2764           7 :     L[1] = evaltyp(list_typ(L));
    2765           7 :     list_data(L) = NULL;
    2766             :   }
    2767           7 : }
    2768             : 
    2769             : GEN
    2770        1415 : mklist_typ(long t)
    2771             : {
    2772        1415 :   GEN L = cgetg(3,t_LIST);
    2773        1415 :   L[1] = evaltyp(t);
    2774        1415 :   list_data(L) = NULL; return L;
    2775             : }
    2776             : 
    2777             : GEN
    2778        1359 : mklist(void)
    2779             : {
    2780        1359 :   return mklist_typ(t_LIST_RAW);
    2781             : }
    2782             : 
    2783             : GEN
    2784          49 : mkmap(void)
    2785             : {
    2786          49 :   return mklist_typ(t_LIST_MAP);
    2787             : }
    2788             : 
    2789             : /* return a list with single element x, allocated on stack */
    2790             : GEN
    2791          49 : mklistcopy(GEN x)
    2792             : {
    2793          49 :   GEN y = mklist();
    2794          49 :   list_data(y) = mkveccopy(x);
    2795          49 :   return y;
    2796             : }
    2797             : 
    2798             : GEN
    2799           7 : listcreate_gp(long n)
    2800             : {
    2801           7 :   (void) n; return mklist();
    2802             : }
    2803             : 
    2804             : GEN
    2805      751429 : listput(GEN L, GEN x, long index)
    2806             : {
    2807             :   long l;
    2808             :   GEN z;
    2809             : 
    2810      751429 :   if (index < 0) pari_err_COMPONENT("listput", "<", gen_0, stoi(index));
    2811      751422 :   z = list_data(L);
    2812      751422 :   l = z? lg(z): 1;
    2813             : 
    2814      751422 :   x = gclone(x);
    2815      751422 :   if (!index || index >= l)
    2816             :   {
    2817      751268 :     ensure_nb(L, l);
    2818      751268 :     z = list_data(L); /* it may change ! */
    2819      751268 :     index = l;
    2820      751268 :     l++;
    2821             :   } else
    2822         154 :     gunclone_deep( gel(z, index) );
    2823      751422 :   gel(z,index) = x;
    2824      751422 :   z[0] = evaltyp(t_VEC) | evallg(l); /*must be after gel(z,index) is set*/
    2825      751422 :   return gel(z,index);
    2826             : }
    2827             : 
    2828             : GEN
    2829      700266 : listput0(GEN L, GEN x, long index)
    2830             : {
    2831      700266 :   if (typ(L) != t_LIST || list_typ(L) != t_LIST_RAW)
    2832          14 :     pari_err_TYPE("listput",L);
    2833      700252 :   return listput(L, x, index);
    2834             : }
    2835             : 
    2836             : GEN
    2837       35028 : listinsert(GEN L, GEN x, long index)
    2838             : {
    2839             :   long l, i;
    2840             :   GEN z;
    2841             : 
    2842       35028 :   if (typ(L) != t_LIST || list_typ(L) != t_LIST_RAW)
    2843          14 :     pari_err_TYPE("listinsert",L);
    2844       35014 :   z = list_data(L); l = z? lg(z): 1;
    2845       35014 :   if (index <= 0) pari_err_COMPONENT("listinsert", "<=", gen_0, stoi(index));
    2846       35007 :   if (index > l) index = l;
    2847       35007 :   ensure_nb(L, l);
    2848       35007 :   BLOCK_SIGINT_START
    2849       35007 :   z = list_data(L);
    2850    87552507 :   for (i=l; i > index; i--) gel(z,i) = gel(z,i-1);
    2851       35007 :   z[0] = evaltyp(t_VEC) | evallg(l+1);
    2852       35007 :   gel(z,index) = gclone(x);
    2853       35007 :   BLOCK_SIGINT_END
    2854       35007 :   return gel(z,index);
    2855             : }
    2856             : 
    2857             : void
    2858       21910 : listpop(GEN L, long index)
    2859             : {
    2860             :   long l, i;
    2861             :   GEN z;
    2862             : 
    2863       21910 :   if (typ(L) != t_LIST) pari_err_TYPE("listinsert",L);
    2864       21910 :   if (index < 0) pari_err_COMPONENT("listpop", "<", gen_0, stoi(index));
    2865       21910 :   z = list_data(L);
    2866       21910 :   if (!z || (l = lg(z)-1) == 0) return;
    2867             : 
    2868       21896 :   if (!index || index > l) index = l;
    2869       21896 :   BLOCK_SIGINT_START
    2870       21896 :   gunclone_deep( gel(z, index) );
    2871       21896 :   z[0] = evaltyp(t_VEC) | evallg(l);
    2872       21903 :   for (i=index; i < l; i++) z[i] = z[i+1];
    2873       21896 :   BLOCK_SIGINT_END
    2874             : }
    2875             : 
    2876             : void
    2877          49 : listpop0(GEN L, long index)
    2878             : {
    2879          49 :   if (typ(L) != t_LIST || list_typ(L) != t_LIST_RAW)
    2880          14 :     pari_err_TYPE("listpop",L);
    2881          35 :   listpop(L, index);
    2882          35 : }
    2883             : 
    2884             : /* return a copy fully allocated on stack. gclone from changevalue is
    2885             :  * supposed to malloc() it */
    2886             : GEN
    2887         643 : gtolist(GEN x)
    2888             : {
    2889             :   GEN y;
    2890             : 
    2891         643 :   if (!x) return mklist();
    2892         317 :   switch(typ(x))
    2893             :   {
    2894         261 :     case t_VEC: case t_COL:
    2895         261 :       y = mklist();
    2896         261 :       if (lg(x) == 1) return y;
    2897         247 :       list_data(y) = gcopy(x);
    2898         247 :       settyp(list_data(y), t_VEC);
    2899         247 :       return y;
    2900           7 :     case t_LIST:
    2901           7 :       y = mklist();
    2902           7 :       list_data(y) = list_data(x)? gcopy(list_data(x)): NULL;
    2903           7 :       return y;
    2904          49 :     default:
    2905          49 :       return mklistcopy(x);
    2906             :   }
    2907             : }
    2908             : 
    2909             : void
    2910          21 : listsort(GEN L, long flag)
    2911             : {
    2912             :   long i, l;
    2913          21 :   pari_sp av = avma;
    2914             :   GEN perm, v, vnew;
    2915             : 
    2916          21 :   if (typ(L) != t_LIST) pari_err_TYPE("listsort",L);
    2917          21 :   v = list_data(L); l = v? lg(v): 1;
    2918          21 :   if (l < 3) return;
    2919          21 :   if (flag)
    2920             :   {
    2921             :     long lnew;
    2922          14 :     perm = gen_indexsort_uniq(L, (void*)&cmp_universal, cmp_nodata);
    2923          14 :     lnew = lg(perm); /* may have changed since 'uniq' */
    2924          14 :     vnew = cgetg(lnew,t_VEC);
    2925          56 :     for (i=1; i<lnew; i++) {
    2926          42 :       long c = perm[i];
    2927          42 :       gel(vnew,i) = gel(v,c);
    2928          42 :       gel(v,c) = NULL;
    2929             :     }
    2930          14 :     if (l != lnew) { /* was shortened */
    2931         105 :       for (i=1; i<l; i++)
    2932          91 :         if (gel(v,i)) gunclone_deep(gel(v,i));
    2933          14 :       l = lnew;
    2934             :     }
    2935             :   }
    2936             :   else
    2937             :   {
    2938           7 :     perm = gen_indexsort(L, (void*)&cmp_universal, cmp_nodata);
    2939           7 :     vnew = cgetg(l,t_VEC);
    2940          63 :     for (i=1; i<l; i++) gel(vnew,i) = gel(v,perm[i]);
    2941             :   }
    2942         119 :   for (i=1; i<l; i++) gel(v,i) = gel(vnew,i);
    2943          21 :   v[0] = vnew[0]; set_avma(av);
    2944             : }

Generated by: LCOV version 1.13