Code coverage tests

This page documents the degree to which the PARI/GP source code is tested by our public test suite, distributed with the source distribution in directory src/test/. This is measured by the gcov utility; we then process gcov output using the lcov frond-end.

We test a few variants depending on Configure flags on the pari.math.u-bordeaux.fr machine (x86_64 architecture), and agregate them in the final report:

The target is 90% coverage for all mathematical modules (given that branches depending on DEBUGLEVEL or DEBUGMEM are not covered). This script is run to produce the results below.

LCOV - code coverage report
Current view: top level - basemath - gen2.c (source / functions) Hit Total Coverage
Test: PARI/GP v2.10.0 lcov report (development 21348-d75f58f) Lines: 1357 1546 87.8 %
Date: 2017-11-20 06:21:05 Functions: 140 151 92.7 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : /* Copyright (C) 2000  The PARI group.
       2             : 
       3             : This file is part of the PARI/GP package.
       4             : 
       5             : PARI/GP is free software; you can redistribute it and/or modify it under the
       6             : terms of the GNU General Public License as published by the Free Software
       7             : Foundation. It is distributed in the hope that it will be useful, but WITHOUT
       8             : ANY WARRANTY WHATSOEVER.
       9             : 
      10             : Check the License for details. You should have received a copy of it, along
      11             : with the package; see the file 'COPYING'. If not, write to the Free Software
      12             : Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. */
      13             : 
      14             : /********************************************************************/
      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         182 : map_proto_G(GEN (*f)(GEN), GEN x)
      30             : {
      31         182 :   if (is_matvec_t(typ(x)))
      32             :   {
      33             :     long lx, i;
      34           7 :     GEN y = cgetg_copy(x, &lx);
      35           7 :     for (i=1; i<lx; i++) gel(y,i) = map_proto_G(f, gel(x,i));
      36           7 :     return y;
      37             :   }
      38         175 :   return f(x);
      39             : }
      40             : 
      41             : GEN
      42    20842999 : map_proto_lG(long (*f)(GEN), GEN x)
      43             : {
      44    20842999 :   if (is_matvec_t(typ(x)))
      45             :   {
      46             :     long lx, i;
      47          14 :     GEN y = cgetg_copy(x, &lx);
      48          14 :     for (i=1; i<lx; i++) gel(y,i) = map_proto_lG(f, gel(x,i));
      49          14 :     return y;
      50             :   }
      51    20938006 :   return stoi(f(x));
      52             : }
      53             : 
      54             : GEN
      55         126 : map_proto_lGL(long (*f)(GEN,long), GEN x, long y)
      56             : {
      57         126 :   if (is_matvec_t(typ(x)))
      58             :   {
      59             :     long l, i;
      60           7 :     GEN t = cgetg_copy(x, &l);
      61           7 :     for (i=1; i<l; i++) gel(t,i) = map_proto_lGL(f,gel(x,i),y);
      62           7 :     return t;
      63             :   }
      64         119 :   return stoi(f(x,y));
      65             : }
      66             : 
      67             : static GEN
      68      277932 : _domul(void *data, GEN x, GEN y)
      69             : {
      70      277932 :   GEN (*mul)(GEN,GEN)=(GEN (*)(GEN,GEN)) data;
      71      277932 :   return mul(x,y);
      72             : }
      73             : 
      74             : GEN
      75      282560 : gassoc_proto(GEN (*f)(GEN,GEN), GEN x, GEN y)
      76             : {
      77      282560 :   if (!y)
      78             :   {
      79      282560 :     pari_sp av = avma;
      80      282560 :     switch(typ(x))
      81             :     {
      82             :       case t_LIST:
      83          21 :         x = list_data(x); if (!x) return gen_1;
      84             :       case t_VEC:
      85      282546 :       case t_COL: break;
      86           7 :       default: pari_err_TYPE("association",x);
      87             :     }
      88      282546 :     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     1559592 : cgetp(GEN x)
     100             : {
     101     1559592 :   GEN y = cgetg(5,t_PADIC);
     102     1559591 :   y[1] = (x[1]&PRECPBITS) | _evalvalp(0);
     103     1559591 :   gel(y,2) = icopy(gel(x,2));
     104     1559599 :   gel(y,3) = icopy(gel(x,3));
     105     1559603 :   gel(y,4) = cgeti(lgefint(gel(x,3))); return y;
     106             : }
     107             : 
     108             : /*******************************************************************/
     109             : /*                                                                 */
     110             : /*                            SIZES                                */
     111             : /*                                                                 */
     112             : /*******************************************************************/
     113             : 
     114             : long
     115     4532512 : glength(GEN x)
     116             : {
     117     4532512 :   long tx = typ(x);
     118     4532512 :   switch(tx)
     119             :   {
     120          84 :     case t_INT:  return lgefint(x)-2;
     121             :     case t_LIST: {
     122          21 :       GEN L = list_data(x);
     123          21 :       return L? lg(L)-1: 0;
     124             :     }
     125          14 :     case t_REAL: return signe(x)? lg(x)-2: 0;
     126          11 :     case t_STR:  return strlen( GSTR(x) );
     127        5959 :     case t_VECSMALL: return lg(x)-1;
     128             :   }
     129     4526423 :   return lg(x) - lontyp[tx];
     130             : }
     131             : 
     132             : GEN
     133         112 : matsize(GEN x)
     134             : {
     135         112 :   long L = lg(x) - 1;
     136         112 :   switch(typ(x))
     137             :   {
     138           7 :     case t_VEC: return mkvec2s(1, L);
     139           7 :     case t_COL: return mkvec2s(L, 1);
     140          91 :     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 t_POL --> t_SER                     */
     149             : /*                                                                 */
     150             : /*******************************************************************/
     151             : static GEN
     152     1084660 : greffe_aux(GEN x, long l, long lx, long v)
     153             : {
     154     1084660 :   GEN y = cgetg(l,t_SER);
     155             :   long i;
     156     1084660 :   if (l <= 2) pari_err_BUG("RgX_to_ser (l <= 2)");
     157     1084660 :   y[1] = x[1]; setvalp(y, v);
     158     1084660 :   x += v; lx -= v;
     159     1084660 :   if (lx > l) {
     160       53430 :     for (i = 2; i < l; i++) gel(y,i) = gel(x,i);
     161             :   } else {
     162     1031230 :     for (i = 2; i <lx; i++) gel(y,i) = gel(x,i);
     163     1031230 :     for (     ; i < l; i++) gel(y,i) = gen_0;
     164             :   }
     165     1084660 :   return normalize(y);
     166             : }
     167             : /* enlarge/truncate t_POL x to a t_SER with lg l */
     168             : GEN
     169      733224 : RgX_to_ser(GEN x, long l)
     170             : {
     171      733224 :   if (lg(x) == 2) return zeroser(varn(x), l-2);
     172      733217 :   return greffe_aux(x, l, lg(x), RgX_val(x));
     173             : }
     174             : GEN
     175      351443 : RgX_to_ser_inexact(GEN x, long l)
     176             : {
     177      351443 :   long i, lx = lg(x);
     178      351443 :   int first = 1;
     179             :   /* analogous to RgX_valrem + normalize */
     180      351443 :   if (lx == 2) return zeroser(varn(x), l-2);
     181      351443 :   i = 2;
     182      709634 :   while (i<lx && gequal0(gel(x,i))) {
     183        6748 :     if (first && !isexactzero(gel(x,i)))
     184             :     {
     185           7 :       pari_warn(warner,"normalizing a series with 0 leading term");
     186           7 :       first = 0;
     187             :     }
     188        6748 :     i++;
     189             :   }
     190      351443 :   return greffe_aux(x, l, lx, i - 2);
     191             : }
     192             : GEN
     193         224 : rfrac_to_ser(GEN x, long l)
     194             : {
     195         224 :   return gdiv(gel(x,1), RgX_to_ser(gel(x,2), l));
     196             : }
     197             : 
     198             : /* R(1/x) + O(x^N) */
     199             : GEN
     200         112 : rfracrecip_to_ser_absolute(GEN R, long N)
     201             : {
     202         112 :   GEN n = gel(R,1), d = gel(R,2);
     203         112 :   long vx = varn(d), vn, v, dn;
     204             : 
     205         112 :   if (typ(n) != t_POL || varn(n) != vx)
     206             :   {
     207          70 :     vn = 0;
     208          70 :     dn = 0;
     209             :   }
     210             :   else
     211             :   {
     212          42 :     vn = RgX_valrem(n, &n);
     213          42 :     n = RgX_recip(n);
     214          42 :     dn = degpol(n);
     215             :   }
     216         112 :   v = vn - RgX_valrem(d, &d);
     217         112 :   d = RgX_recip(d);
     218         112 :   R = gdiv(n, RgX_to_ser(d, N+2));
     219         112 :   setvalp(R, valp(R) + degpol(d)-dn-v);
     220         112 :   return R;
     221             : }
     222             : /*******************************************************************/
     223             : /*                                                                 */
     224             : /*                 CONVERSION GEN --> long                         */
     225             : /*                                                                 */
     226             : /*******************************************************************/
     227             : 
     228             : long
     229          77 : gtolong(GEN x)
     230             : {
     231          77 :   switch(typ(x))
     232             :   {
     233             :     case t_INT:
     234          42 :       return itos(x);
     235             :     case t_REAL:
     236           7 :       return (long)(rtodbl(x) + 0.5);
     237             :     case t_FRAC: {
     238           7 :       pari_sp av = avma;
     239           7 :       long y = itos(ground(x));
     240           7 :       avma = av; return y;
     241             :     }
     242             :     case t_COMPLEX:
     243           7 :       if (gequal0(gel(x,2))) return gtolong(gel(x,1)); break;
     244             :     case t_QUAD:
     245           7 :       if (gequal0(gel(x,3))) return gtolong(gel(x,2)); break;
     246             :   }
     247           7 :   pari_err_TYPE("gtolong",x);
     248             :   return 0; /* LCOV_EXCL_LINE */
     249             : }
     250             : 
     251             : /*******************************************************************/
     252             : /*                                                                 */
     253             : /*                         COMPARISONS                             */
     254             : /*                                                                 */
     255             : /*******************************************************************/
     256             : int
     257   209659436 : isexactzero(GEN g)
     258             : {
     259             :   long i, lx;
     260   209659436 :   switch (typ(g))
     261             :   {
     262             :     case t_INT:
     263   155227736 :       return !signe(g);
     264             :     case t_INTMOD:
     265     1185400 :       return !signe(gel(g,2));
     266             :     case t_COMPLEX:
     267     2564648 :       return isexactzero(gel(g,1)) && isexactzero(gel(g,2));
     268             :     case t_FFELT:
     269     8105513 :       return FF_equal0(g);
     270             :     case t_QUAD:
     271         371 :       return isexactzero(gel(g,2)) && isexactzero(gel(g,3));
     272             :     case t_POLMOD:
     273      165485 :       return isexactzero(gel(g,2));
     274             :     case t_POL:
     275    29263330 :       lx = lg(g); /* cater for Mod(0,2)*x^0 */
     276    29263330 :       return lx == 2 || (lx == 3 && isexactzero(gel(g,2)));
     277             :     case t_RFRAC:
     278      459834 :       return isexactzero(gel(g,1)); /* may occur: Mod(0,2)/x */
     279             :     case t_VEC: case t_COL: case t_MAT:
     280         350 :       for (i=lg(g)-1; i; i--)
     281         252 :         if (!isexactzero(gel(g,i))) return 0;
     282          98 :       return 1;
     283             :   }
     284    12687007 :   return 0;
     285             : }
     286             : GEN
     287    48213645 : gisexactzero(GEN g)
     288             : {
     289             :   long i, lx;
     290             :   GEN a, b;
     291    48213645 :   switch (typ(g))
     292             :   {
     293             :     case t_INT:
     294    15522957 :       return !signe(g)? g: NULL;
     295             :     case t_INTMOD:
     296     5285266 :       return !signe(gel(g,2))? g: NULL;
     297             :     case t_COMPLEX:
     298         154 :       a = gisexactzero(gel(g,1)); if (!a) return NULL;
     299         126 :       b = gisexactzero(gel(g,2)); if (!b) return NULL;
     300           0 :       return ggcd(a,b);
     301             :     case t_FFELT:
     302       22225 :       return FF_equal0(g)? g: NULL;
     303             :     case t_QUAD:
     304         518 :       a = gisexactzero(gel(g,2)); if (!a) return NULL;
     305          77 :       b = gisexactzero(gel(g,3)); if (!b) return NULL;
     306           7 :       return ggcd(a,b);
     307             :     case t_POLMOD:
     308       48153 :       return gisexactzero(gel(g,2));
     309             :     case t_POL:
     310    26057206 :       lx = lg(g); /* cater for Mod(0,2)*x^0 */
     311    26057206 :       if (lx == 2) return gen_0;
     312    20912349 :       if (lx == 3) return gisexactzero(gel(g,2));
     313    19026458 :       return NULL;
     314             :     case t_RFRAC:
     315     1193716 :       return gisexactzero(gel(g,1)); /* may occur: Mod(0,2)/x */
     316             :     case t_VEC: case t_COL: case t_MAT:
     317           0 :       a = gen_0;
     318           0 :       for (i=lg(g)-1; i; i--)
     319             :       {
     320           0 :         b = gisexactzero(gel(g,i));
     321           0 :         if (!b) return NULL;
     322           0 :         a = ggcd(a, b);
     323             :       }
     324           0 :       return a;
     325             :   }
     326       83450 :   return NULL;
     327             : }
     328             : 
     329             : int
     330   218465078 : isrationalzero(GEN g)
     331             : {
     332             :   long i;
     333   218465078 :   switch (typ(g))
     334             :   {
     335             :     case t_INT:
     336   136976850 :       return !signe(g);
     337             :     case t_COMPLEX:
     338     6137624 :       return isintzero(gel(g,1)) && isintzero(gel(g,2));
     339             :     case t_QUAD:
     340         798 :       return isintzero(gel(g,2)) && isintzero(gel(g,3));
     341             :     case t_POLMOD:
     342      183983 :       return isrationalzero(gel(g,2));
     343    36601669 :     case t_POL: return lg(g) == 2;
     344             :     case t_VEC: case t_COL: case t_MAT:
     345         252 :       for (i=lg(g)-1; i; i--)
     346         168 :         if (!isrationalzero(gel(g,i))) return 0;
     347          84 :       return 1;
     348             :   }
     349    38564070 :   return 0;
     350             : }
     351             : 
     352             : int
     353   516478252 : gequal0(GEN x)
     354             : {
     355   516478252 :   switch(typ(x))
     356             :   {
     357             :     case t_INT: case t_REAL: case t_POL: case t_SER:
     358   483031530 :       return !signe(x);
     359             : 
     360             :     case t_INTMOD:
     361     3172187 :       return !signe(gel(x,2));
     362             : 
     363             :     case t_FFELT:
     364      543038 :       return FF_equal0(x);
     365             : 
     366             :     case t_COMPLEX:
     367             :      /* is 0 iff norm(x) would be 0 (can happen with Re(x) and Im(x) != 0
     368             :       * only if Re(x) and Im(x) are of type t_REAL). See mp.c:addrr().
     369             :       */
     370    11998212 :       if (gequal0(gel(x,1)))
     371             :       {
     372     1429817 :         if (gequal0(gel(x,2))) return 1;
     373     1236332 :         if (typ(gel(x,1))!=t_REAL || typ(gel(x,2))!=t_REAL) return 0;
     374       34870 :         return (expo(gel(x,1))>=expo(gel(x,2)));
     375             :       }
     376    10568395 :       if (gequal0(gel(x,2)))
     377             :       {
     378      355577 :         if (typ(gel(x,1))!=t_REAL || typ(gel(x,2))!=t_REAL) return 0;
     379      280672 :         return (expo(gel(x,2))>=expo(gel(x,1)));
     380             :       }
     381    10212818 :       return 0;
     382             : 
     383             :     case t_PADIC:
     384      324790 :       return !signe(gel(x,4));
     385             : 
     386             :     case t_QUAD:
     387         917 :       return gequal0(gel(x,2)) && gequal0(gel(x,3));
     388             : 
     389             :     case t_POLMOD:
     390     1419666 :       return gequal0(gel(x,2));
     391             : 
     392             :     case t_RFRAC:
     393     6010279 :       return gequal0(gel(x,1));
     394             : 
     395             :     case t_VEC: case t_COL: case t_MAT:
     396             :     {
     397             :       long i;
     398     4066111 :       for (i=lg(x)-1; i; i--)
     399     3742412 :         if (!gequal0(gel(x,i))) return 0;
     400      323699 :       return 1;
     401             :     }
     402             :   }
     403     8634556 :   return 0;
     404             : }
     405             : 
     406             : /* x a t_POL or t_SER, considered as having valuation v; let X(t) = t^(-v) x(t)
     407             :  * return 1 (true) if coeff(X,i) = 0 for all i != 0 and test(coeff(X, 0))
     408             :  * is true. Return 0 (false) otherwise, or if x == 0 */
     409             : static int
     410    13147879 : is_monomial_test(GEN x, long v, int(*test)(GEN))
     411             : {
     412             :   long d, i, l;
     413    13147879 :   if (!signe(x)) return (typ(x) == t_SER && v <= 0);
     414    13085027 :   if (v > 0) return 0;
     415    13085013 :   l = lg(x); d = 2-v;
     416    13085013 :   if (l <= d) return 0;
     417             :   /* 2 <= d < l */
     418    13085013 :   if (!test(gel(x,d))) return 0;
     419     3968268 :   for (i = 2; i < d; i++)
     420          14 :     if (!gequal0(gel(x,i))) return 0;
     421     4384298 :   for (i = d+1; i < l; i++)
     422     1972195 :     if (!gequal0(gel(x,i))) return 0;
     423     2412103 :   return 1;
     424             : }
     425             : static int
     426        2023 : col_test(GEN x, int(*test)(GEN))
     427             : {
     428        2023 :   long i, l = lg(x);
     429        2023 :   if (l == 1 || !test(gel(x,1))) return 0;
     430          42 :   for (i = 2; i < l; i++)
     431          21 :     if (!gequal0(gel(x,i))) return 0;
     432          21 :   return 1;
     433             : }
     434             : static int
     435       16184 : mat_test(GEN x, int(*test)(GEN))
     436             : {
     437       16184 :   long i, j, l = lg(x);
     438       16184 :   if (l == 1) return 1;
     439       16170 :   if (l != lgcols(x)) return 0;
     440       51240 :   for (i = 1; i < l; i++)
     441      134078 :     for (j = 1; j < l; j++)
     442       99008 :       if (i == j) {
     443       35133 :         if (!test(gcoeff(x,i,i))) return 0;
     444             :       } else {
     445       63875 :         if (!gequal0(gcoeff(x,i,j))) return 0;
     446             :       }
     447       16107 :   return 1;
     448             : }
     449             : 
     450             : /* returns 1 whenever x = 1, and 0 otherwise */
     451             : int
     452   154374692 : gequal1(GEN x)
     453             : {
     454   154374692 :   switch(typ(x))
     455             :   {
     456             :     case t_INT:
     457   138303364 :       return equali1(x);
     458             : 
     459             :     case t_REAL:
     460             :     {
     461      806296 :       long s = signe(x);
     462      806296 :       if (!s) return expo(x) >= 0;
     463      806114 :       return s > 0 ? absrnz_equal1(x): 0;
     464             :     }
     465             :     case t_INTMOD:
     466      277872 :       return is_pm1(gel(x,2)) || is_pm1(gel(x,1));
     467             :     case t_POLMOD:
     468      319791 :       return gequal1(gel(x,2)) || gequal1(gel(x,1));
     469             : 
     470             :     case t_FFELT:
     471        8302 :       return FF_equal1(x);
     472             : 
     473             :     case t_FRAC:
     474      366067 :       return 0;
     475             : 
     476             :     case t_COMPLEX:
     477       88879 :       return gequal1(gel(x,1)) && gequal0(gel(x,2));
     478             : 
     479             :     case t_PADIC:
     480        9079 :       return !valp(x) && gequal1(gel(x,4));
     481             : 
     482             :     case t_QUAD:
     483          35 :       return gequal1(gel(x,2)) && gequal0(gel(x,3));
     484             : 
     485    13144883 :     case t_POL: return is_monomial_test(x, 0, &gequal1);
     486          91 :     case t_SER: return is_monomial_test(x, valp(x), &gequal1);
     487             : 
     488     1031903 :     case t_RFRAC: return gequal(gel(x,1), gel(x,2));
     489        1981 :     case t_COL: return col_test(x, &gequal1);
     490       16135 :     case t_MAT: return mat_test(x, &gequal1);
     491             :   }
     492          14 :   return 0;
     493             : }
     494             : 
     495             : /* returns 1 whenever the x = -1, 0 otherwise */
     496             : int
     497     1226378 : gequalm1(GEN x)
     498             : {
     499             :   pari_sp av;
     500             :   long y;
     501             :   GEN p1;
     502             : 
     503     1226378 :   switch(typ(x))
     504             :   {
     505             :     case t_INT:
     506      339541 :       return equalim1(x);
     507             : 
     508             :     case t_REAL:
     509             :     {
     510      801567 :       long s = signe(x);
     511      801567 :       if (!s) return expo(x) >= 0;
     512      801462 :       return s < 0 ? absrnz_equal1(x): 0;
     513             :     }
     514             :     case t_INTMOD:
     515          21 :       av=avma; y=equalii(addui(1,gel(x,2)), gel(x,1)); avma=av; return y;
     516             : 
     517             :     case t_FRAC:
     518          14 :       return 0;
     519             : 
     520             :     case t_FFELT:
     521          42 :       return FF_equalm1(x);
     522             : 
     523             :     case t_COMPLEX:
     524       82113 :       return gequalm1(gel(x,1)) && gequal0(gel(x,2));
     525             : 
     526             :     case t_QUAD:
     527           7 :       return gequalm1(gel(x,2)) && gequal0(gel(x,3));
     528             : 
     529             :     case t_PADIC:
     530           7 :       av=avma; y=equalii(addui(1,gel(x,4)), gel(x,3)); avma=av; return y;
     531             : 
     532             :     case t_POLMOD:
     533          35 :       av=avma; p1 = gaddgs(gel(x,2), 1);
     534          35 :       y = gequal0(p1) || gequal(p1,gel(x,1)); avma=av; return y;
     535             : 
     536        2828 :     case t_POL: return is_monomial_test(x, 0, &gequalm1);
     537          77 :     case t_SER: return is_monomial_test(x, valp(x), &gequalm1);
     538             : 
     539             :     case t_RFRAC:
     540          21 :       av=avma; y=gequal(gel(x,1), gneg_i(gel(x,2))); avma=av; return y;
     541          42 :     case t_COL: return col_test(x, &gequalm1);
     542          49 :     case t_MAT: return mat_test(x, &gequalm1);
     543             :   }
     544          14 :   return 0;
     545             : }
     546             : 
     547             : int
     548     3116379 : gequalX(GEN x) { return typ(x) == t_POL && lg(x) == 4
     549     2061318 :                       && isintzero(gel(x,2)) && isint1(gel(x,3)); }
     550             : 
     551             : static int
     552         476 : cmp_str(const char *x, const char *y)
     553             : {
     554         476 :   int f = strcmp(x, y);
     555         476 :   return f > 0? 1
     556         476 :               : f? -1: 0;
     557             : }
     558             : 
     559             : static int
     560    26166301 : cmp_universal_rec(GEN x, GEN y, long i0)
     561             : {
     562    26166301 :   long i, lx = lg(x), ly = lg(y);
     563    26166301 :   if (lx < ly) return -1;
     564    26164621 :   if (lx > ly) return 1;
     565    38781624 :   for (i = i0; i < lx; i++)
     566             :   {
     567    33101439 :     int f = cmp_universal(gel(x,i), gel(y,i));
     568    33101439 :     if (f) return f;
     569             :   }
     570     5680185 :   return 0;
     571             : }
     572             : /* Universal "meaningless" comparison function. Transitive, returns 0 iff
     573             :  * gidentical(x,y) */
     574             : int
     575    45608388 : cmp_universal(GEN x, GEN y)
     576             : {
     577    45608388 :   long lx, ly, i, tx = typ(x), ty = typ(y);
     578             : 
     579    45608388 :   if (tx < ty) return -1;
     580    45597734 :   if (ty < tx) return 1;
     581    45593261 :   switch(tx)
     582             :   {
     583    18486685 :     case t_INT: return cmpii(x,y);
     584         455 :     case t_STR: return cmp_str(GSTR(x),GSTR(y));
     585             :     case t_REAL:
     586             :     case t_VECSMALL:
     587      939764 :       lx = lg(x);
     588      939764 :       ly = lg(y);
     589      939764 :       if (lx < ly) return -1;
     590      888335 :       if (lx > ly) return 1;
     591     3580802 :       for (i = 1; i < lx; i++)
     592             :       {
     593     3473163 :         if (x[i] < y[i]) return -1;
     594     3088709 :         if (x[i] > y[i]) return 1;
     595             :       }
     596      107639 :       return 0;
     597             : 
     598             :     case t_POL:
     599             :     case t_SER:
     600             :     case t_FFELT:
     601             :     case t_CLOSURE:
     602      903413 :       if (x[1] < y[1]) return -1;
     603      903371 :       if (x[1] > y[1]) return 1;
     604      903357 :       return cmp_universal_rec(x, y, 2);
     605             : 
     606             :     case t_LIST:
     607             :       {
     608          21 :         long tx = list_typ(x), ty = list_typ(y);
     609             :         GEN vx, vy;
     610          21 :         if (tx < ty) return -1;
     611          21 :         if (tx > ty) return 1;
     612          21 :         vx = list_data(x);
     613          21 :         vy = list_data(y);
     614          21 :         if (!vx) return vy? -1: 0;
     615          21 :         if (!vy) return 1;
     616          21 :         switch (tx)
     617             :         {
     618             :         case t_LIST_MAP:
     619             :           {
     620           0 :             pari_sp av = avma;
     621           0 :             int ret = cmp_universal_rec(maptomat_shallow(x), maptomat_shallow(y),1);
     622           0 :             avma = av; return ret;
     623             :           }
     624             :         default:
     625          21 :           return cmp_universal_rec(vx, vy, 1);
     626             :         }
     627             :       }
     628             :     default:
     629    25262923 :       return cmp_universal_rec(x, y, lontyp[tx]);
     630             :   }
     631             : }
     632             : 
     633             : static int
     634       40546 : cmpfrac(GEN x, GEN y)
     635             : {
     636       40546 :   pari_sp av = avma;
     637       40546 :   GEN a = gel(x,1), b = gel(x,2);
     638       40546 :   GEN c = gel(y,1), d = gel(y,2);
     639       40546 :   int r = cmpii(mulii(a, d), mulii(b, c));
     640       40546 :   avma = av; return r;
     641             : }
     642             : static int
     643       10871 : cmpifrac(GEN a, GEN y)
     644             : {
     645       10871 :   pari_sp av = avma;
     646       10871 :   GEN c = gel(y,1), d = gel(y,2);
     647       10871 :   int r = cmpii(mulii(a, d), c);
     648       10871 :   avma = av; return r;
     649             : }
     650             : static int
     651       35812 : cmprfrac(GEN a, GEN y)
     652             : {
     653       35812 :   pari_sp av = avma;
     654       35812 :   GEN c = gel(y,1), d = gel(y,2);
     655       35812 :   int r = cmpri(mulri(a, d), c);
     656       35812 :   avma = av; return r;
     657             : }
     658             : static int
     659          42 : cmpgen(GEN x, GEN y)
     660             : {
     661          42 :   pari_sp av = avma;
     662          42 :   int s = gsigne(gsub(x,y));
     663          35 :   avma = av; return s;
     664             : }
     665             : 
     666             : /* returns the sign of x - y when it makes sense. 0 otherwise */
     667             : int
     668   179828143 : gcmp(GEN x, GEN y)
     669             : {
     670   179828143 :   long tx = typ(x), ty = typ(y);
     671             : 
     672   179828143 :   if (tx == ty) /* generic case */
     673   179386903 :     switch(tx)
     674             :     {
     675   109993981 :       case t_INT:  return cmpii(x, y);
     676    69442983 :       case t_REAL: return cmprr(x, y);
     677       40546 :       case t_FRAC: return cmpfrac(x, y);
     678          14 :       case t_QUAD: return cmpgen(x, y);
     679          21 :       case t_STR:  return cmp_str(GSTR(x), GSTR(y));
     680             :       case t_INFINITY:
     681             :       {
     682       12971 :         long sx = inf_get_sign(x), sy = inf_get_sign(y);
     683       12971 :         if (sx < sy) return -1;
     684          21 :         if (sx > sy) return 1;
     685          14 :         return 0;
     686             :       }
     687             :     }
     688      337627 :   if (ty == t_INFINITY) return -inf_get_sign(y);
     689      326193 :   switch(tx)
     690             :   {
     691             :     case t_INT:
     692       22208 :       switch(ty)
     693             :       {
     694       18736 :         case t_REAL: return cmpir(x, y);
     695        3465 :         case t_FRAC: return cmpifrac(x, y);
     696           0 :         case t_QUAD: return cmpgen(x, y);
     697             :       }
     698           7 :       break;
     699             :     case t_REAL:
     700      272108 :       switch(ty)
     701             :       {
     702      260040 :         case t_INT:  return cmpri(x, y);
     703       12061 :         case t_FRAC: return cmprfrac(x, y);
     704           0 :         case t_QUAD: return cmpgen(x, y);
     705             :       }
     706           7 :       break;
     707             :     case t_FRAC:
     708       31164 :       switch(ty)
     709             :       {
     710        7406 :         case t_INT:  return -cmpifrac(y, x);
     711       23751 :         case t_REAL: return -cmprfrac(y, x);
     712           0 :         case t_QUAD: return cmpgen(x, y);
     713             :       }
     714           7 :       break;
     715             :     case t_QUAD:
     716          28 :       return cmpgen(x, y);
     717         678 :     case t_INFINITY: return inf_get_sign(x);
     718             :   }
     719          28 :   pari_err_TYPE2("comparison",x,y);
     720             :   return 0;/*LCOV_EXCL_LINE*/
     721             : }
     722             : 
     723             : int
     724       24394 : gcmpsg(long s, GEN y)
     725             : {
     726       24394 :   long ty = typ(y);
     727       24394 :   switch(ty) {
     728        1043 :     case t_INT:  return cmpsi(s,y);
     729       22539 :     case t_REAL: return cmpsr(s,y);
     730             :     case t_FRAC: {
     731         812 :       pari_sp av = avma;
     732         812 :       GEN n = gel(y,1), d = gel(y,2);
     733         812 :       int f = cmpii(mulsi(s,d), n); avma = av; return f;
     734             :     }
     735           0 :     case t_STR: return -1;
     736             :   }
     737           0 :   pari_err_TYPE2("comparison",stoi(s),y);
     738             :   return 0; /* LCOV_EXCL_LINE */
     739             : }
     740             : 
     741             : static long
     742     5852411 : roughtype(GEN x)
     743             : {
     744     5852411 :   switch(typ(x))
     745             :   {
     746        2044 :     case t_MAT: return t_MAT;
     747       20013 :     case t_VEC: case t_COL: return t_VEC;
     748     5783356 :     case t_VECSMALL: return t_VECSMALL;
     749       46998 :     default: return t_INT;
     750             :   }
     751             : }
     752             : 
     753             : static int lexcmpsg(long x, GEN y);
     754          28 : static int lexcmpgs(GEN x, long y) { return -lexcmpsg(y,x); }
     755             : /* lexcmp(stoi(x),y), y t_VEC/t_COL/t_MAT */
     756             : static int
     757          21 : lexcmp_s_matvec(long x, GEN y)
     758             : {
     759             :   int fl;
     760          21 :   if (lg(y)==1) return 1;
     761          14 :   fl = lexcmpsg(x,gel(y,1));
     762          14 :   if (fl) return fl;
     763           7 :   return -1;
     764             : }
     765             : /* x a scalar, y a t_VEC/t_COL/t_MAT */
     766             : static int
     767         224 : lexcmp_scal_matvec(GEN x, GEN y)
     768             : {
     769             :   int fl;
     770         224 :   if (lg(y)==1) return 1;
     771         224 :   fl = lexcmp(x,gel(y,1));
     772         224 :   if (fl) return fl;
     773           0 :   return -1;
     774             : }
     775             : /* x a scalar, y a t_VECSMALL */
     776             : static int
     777          28 : lexcmp_scal_vecsmall(GEN x, GEN y)
     778             : {
     779             :   int fl;
     780          28 :   if (lg(y)==1) return 1;
     781          28 :   fl = lexcmpgs(x, y[1]);
     782          28 :   if (fl) return fl;
     783           0 :   return -1;
     784             : }
     785             : 
     786             : /* tx = ty = t_MAT, or x and y are both vect_t */
     787             : static int
     788       10829 : lexcmp_similar(GEN x, GEN y)
     789             : {
     790       10829 :   long i, lx = lg(x), ly = lg(y), l = minss(lx,ly);
     791       21959 :   for (i=1; i<l; i++)
     792             :   {
     793       20426 :     int fl = lexcmp(gel(x,i),gel(y,i));
     794       20426 :     if (fl) return fl;
     795             :   }
     796        1533 :   if (lx == ly) return 0;
     797          28 :   return (lx < ly)? -1 : 1;
     798             : }
     799             : /* x a t_VECSMALL, y a t_VEC/t_COL ~ lexcmp_similar */
     800             : static int
     801         154 : lexcmp_vecsmall_vec(GEN x, GEN y)
     802             : {
     803         154 :   long i, lx = lg(x), ly = lg(y), l = minss(lx,ly);
     804         343 :   for (i=1; i<l; i++)
     805             :   {
     806         287 :     int fl = lexcmpsg(x[i], gel(y,i));
     807         287 :     if (fl) return fl;
     808             :   }
     809          56 :   if (lx == ly) return 0;
     810          21 :   return (lx < ly)? -1 : 1;
     811             : }
     812             : 
     813             : /* x t_VEC/t_COL, y t_MAT */
     814             : static int
     815          84 : lexcmp_vec_mat(GEN x, GEN y)
     816             : {
     817             :   int fl;
     818          84 :   if (lg(x)==1) return -1;
     819          84 :   if (lg(y)==1) return 1;
     820          84 :   fl = lexcmp_similar(x,gel(y,1));
     821          84 :   if (fl) return fl;
     822           0 :   return -1;
     823             : }
     824             : /* x t_VECSMALl, y t_MAT ~ lexcmp_vec_mat */
     825             : static int
     826          42 : lexcmp_vecsmall_mat(GEN x, GEN y)
     827             : {
     828             :   int fl;
     829          42 :   if (lg(x)==1) return -1;
     830          42 :   if (lg(y)==1) return 1;
     831          42 :   fl = lexcmp_vecsmall_vec(x, gel(y,1));
     832          42 :   if (fl) return fl;
     833           0 :   return -1;
     834             : }
     835             : 
     836             : /* x a t_VECSMALL, not y */
     837             : static int
     838         182 : lexcmp_vecsmall_other(GEN x, GEN y, long ty)
     839             : {
     840         182 :   switch(ty)
     841             :   {
     842          42 :     case t_MAT: return lexcmp_vecsmall_mat(x, y);
     843         112 :     case t_VEC: return lexcmp_vecsmall_vec(x, y);
     844          28 :     default: return -lexcmp_scal_vecsmall(y, x); /*y scalar*/
     845             :   }
     846             : }
     847             : 
     848             : /* lexcmp(stoi(s), y) */
     849             : static int
     850         329 : lexcmpsg(long x, GEN y)
     851             : {
     852         329 :   switch(roughtype(y))
     853             :   {
     854             :     case t_MAT:
     855             :     case t_VEC:
     856          21 :       return lexcmp_s_matvec(x,y);
     857             :     case t_VECSMALL: /* ~ lexcmp_scal_matvec */
     858          14 :       if (lg(y)==1) return 1;
     859           7 :       return (x > y[1])? 1: -1;
     860         294 :     default: return gcmpsg(x,y);
     861             :   }
     862             : }
     863             : 
     864             : /* as gcmp for vector/matrices, using lexicographic ordering on components */
     865             : int
     866     2926041 : lexcmp(GEN x, GEN y)
     867             : {
     868     2926041 :   const long tx = roughtype(x), ty = roughtype(y);
     869     2926041 :   if (tx == ty)
     870     2925551 :     switch(tx)
     871             :     {
     872             :       case t_MAT:
     873             :       case t_VEC:
     874       10745 :         return lexcmp_similar(x,y);
     875             :       case t_VECSMALL:
     876     2891580 :         return vecsmall_lexcmp(x,y);
     877             :       default:
     878       23226 :         return gcmp(x,y);
     879             :     }
     880         490 :   if (tx == t_VECSMALL) return  lexcmp_vecsmall_other(x,y,ty);
     881         371 :   if (ty == t_VECSMALL) return -lexcmp_vecsmall_other(y,x,tx);
     882             : 
     883         308 :   if (tx == t_INT) return  lexcmp_scal_matvec(x,y); /*scalar*/
     884         154 :   if (ty == t_INT) return -lexcmp_scal_matvec(y,x);
     885             : 
     886          84 :   if (ty==t_MAT) return  lexcmp_vec_mat(x,y);
     887          42 :   /*tx==t_MAT*/  return -lexcmp_vec_mat(y,x);
     888             : }
     889             : 
     890             : /*****************************************************************/
     891             : /*                                                               */
     892             : /*                          EQUALITY                             */
     893             : /*                returns 1 if x == y, 0 otherwise               */
     894             : /*                                                               */
     895             : /*****************************************************************/
     896             : /* x,y t_POL */
     897             : static int
     898      879866 : polidentical(GEN x, GEN y)
     899             : {
     900             :   long lx;
     901      879866 :   if (x[1] != y[1]) return 0;
     902      879810 :   lx = lg(x); if (lg(y) != lg(x)) return 0;
     903      879782 :   for (lx--; lx >= 2; lx--) if (!gidentical(gel(x,lx), gel(y,lx))) return 0;
     904      879768 :   return 1;
     905             : }
     906             : /* x,y t_SER */
     907             : static int
     908          14 : seridentical(GEN x, GEN y) { return polidentical(x,y); }
     909             : /* typ(x) = typ(y) = t_VEC/COL/MAT */
     910             : static int
     911     3879421 : vecidentical(GEN x, GEN y)
     912             : {
     913             :   long i;
     914     3879421 :   if ((x[0] ^ y[0]) & (TYPBITS|LGBITS)) return 0;
     915    10342738 :   for (i = lg(x)-1; i; i--)
     916     7075047 :     if (! gidentical(gel(x,i),gel(y,i)) ) return 0;
     917     3267691 :   return 1;
     918             : }
     919             : static int
     920          21 : identicalrr(GEN x, GEN y)
     921             : {
     922          21 :   long i, lx = lg(x);
     923          21 :   if (lg(y) != lx) return 0;
     924          14 :   if (x[1] != y[1]) return 0;
     925           7 :   i=2; while (i<lx && x[i]==y[i]) i++;
     926           7 :   return (i == lx);
     927             : }
     928             : 
     929             : static int
     930          28 : closure_identical(GEN x, GEN y)
     931             : {
     932          28 :   if (lg(x)!=lg(y) || x[1]!=y[1]) return 0;
     933          21 :   if (!gidentical(gel(x,2),gel(y,2)) || !gidentical(gel(x,3),gel(y,3))
     934           7 :    || !gidentical(gel(x,4),gel(y,4))) return 0;
     935           7 :   if (lg(x)<8) return 1;
     936           0 :   return gidentical(gel(x,7),gel(y,7));
     937             : }
     938             : 
     939             : static int
     940         336 : list_cmp(GEN x, GEN y, int cmp(GEN x, GEN y))
     941             : {
     942         336 :   int t = list_typ(x);
     943             :   GEN vx, vy;
     944         336 :   if (list_typ(y)!=t) return 0;
     945         336 :   vx = list_data(x);
     946         336 :   vy = list_data(y);
     947         336 :   if (!vx) return vy? 0: 1;
     948         322 :   if (!vy) return 0;
     949         308 :   if (lg(vx) != lg(vy)) return 0;
     950         301 :   switch (t)
     951             :   {
     952             :   case t_LIST_MAP:
     953             :     {
     954         280 :       pari_sp av = avma;
     955         280 :       GEN mx  = maptomat_shallow(x), my = maptomat_shallow(y);
     956         280 :       int ret = gidentical(gel(mx, 1), gel(my, 1)) && cmp(gel(mx, 2), gel(my, 2));
     957         280 :       avma = av; return ret;
     958             :     }
     959             :   default:
     960          21 :     return cmp(vx, vy);
     961             :   }
     962             : }
     963             : 
     964             : int
     965    35276361 : gidentical(GEN x, GEN y)
     966             : {
     967             :   long tx;
     968             : 
     969    35276361 :   if (x == y) return 1;
     970    34408109 :   tx = typ(x); if (typ(y) != tx) return 0;
     971    34405827 :   switch(tx)
     972             :   {
     973             :     case t_INT:
     974     7058956 :       return equalii(x,y);
     975             : 
     976             :     case t_REAL:
     977          14 :       return identicalrr(x,y);
     978             : 
     979             :     case t_FRAC: case t_INTMOD:
     980       19607 :       return equalii(gel(x,2), gel(y,2)) && equalii(gel(x,1), gel(y,1));
     981             : 
     982             :     case t_COMPLEX:
     983          14 :       return gidentical(gel(x,2),gel(y,2)) && gidentical(gel(x,1),gel(y,1));
     984             :     case t_PADIC:
     985          28 :       return valp(x) == valp(y)
     986          14 :         && equalii(gel(x,2),gel(y,2))
     987          14 :         && equalii(gel(x,3),gel(y,3))
     988          28 :         && equalii(gel(x,4),gel(y,4));
     989             :     case t_POLMOD:
     990          49 :       return gidentical(gel(x,2),gel(y,2)) && polidentical(gel(x,1),gel(y,1));
     991             :     case t_POL:
     992      879831 :       return polidentical(x,y);
     993             :     case t_SER:
     994          14 :       return seridentical(x,y);
     995             :     case t_FFELT:
     996          14 :       return FF_equal(x,y);
     997             : 
     998             :     case t_QFR:
     999           7 :           if (!identicalrr(gel(x,4),gel(y,4))) return 0; /* fall through */
    1000             :     case t_QFI:
    1001     4529186 :       return equalii(gel(x,1),gel(y,1))
    1002     2264585 :           && equalii(gel(x,2),gel(y,2))
    1003     4529170 :           && equalii(gel(x,3),gel(y,3));
    1004             : 
    1005             :     case t_QUAD:
    1006          28 :       return ZX_equal(gel(x,1),gel(y,1))
    1007           7 :           && gidentical(gel(x,2),gel(y,2))
    1008          14 :           && gidentical(gel(x,3),gel(y,3));
    1009             : 
    1010             :     case t_RFRAC:
    1011           7 :       return gidentical(gel(x,1),gel(y,1)) && gidentical(gel(x,2),gel(y,2));
    1012             : 
    1013             :     case t_STR:
    1014          35 :       return !strcmp(GSTR(x),GSTR(y));
    1015             :     case t_VEC: case t_COL: case t_MAT:
    1016     3879421 :       return vecidentical(x,y);
    1017             :     case t_VECSMALL:
    1018    20303033 :       return zv_equal(x,y);
    1019             :     case t_CLOSURE:
    1020          21 :       return closure_identical(x,y);
    1021             :     case t_LIST:
    1022         161 :       return list_cmp(x, y, gidentical);
    1023          21 :     case t_INFINITY: return gidentical(gel(x,1),gel(y,1));
    1024             :   }
    1025           0 :   return 0;
    1026             : }
    1027             : /* x,y t_POL */
    1028             : static int
    1029     2163812 : polequal(GEN x, GEN y)
    1030             : {
    1031             :   long lx, ly;
    1032     2163812 :   if ((x[1] ^ y[1]) & (VARNBITS | SIGNBITS)) return 0;
    1033     2155258 :   lx = lg(x); ly = lg(y);
    1034     2155258 :   while (lx > ly) if (!gequal0(gel(x,--lx))) return 0;
    1035     2153473 :   while (ly > lx) if (!gequal0(gel(y,--ly))) return 0;
    1036     2141083 :   for (lx--; lx >= 2; lx--) if (!gequal(gel(x,lx), gel(y,lx))) return 0;
    1037     2111460 :   return 1;
    1038             : }
    1039             : 
    1040             : /* x,y t_POL */
    1041             : static int
    1042         308 : serequal(GEN x, GEN y)
    1043             : {
    1044             :   long lx;
    1045         308 :   if (varn(x) != varn(y)) return 0;
    1046         308 :   if (!signe(x))
    1047             :   {
    1048         287 :     if (!signe(y)) return 1;
    1049           0 :     return valp(y) >= valp(x);
    1050             :   }
    1051          21 :   if (!signe(y))
    1052           0 :     return valp(x) >= valp(y);
    1053          21 :   if ((x[1] ^ y[1]) & VALPBITS) return 0;
    1054          21 :   lx = minss(lg(x), lg(y));
    1055          21 :   for (lx--; lx >= 2; lx--) if (!gequal(gel(x,lx), gel(y,lx))) return 0;
    1056          21 :   return 1;
    1057             : }
    1058             : 
    1059             : /* typ(x) = typ(y) = t_VEC/COL/MAT */
    1060             : static int
    1061     3414167 : vecequal(GEN x, GEN y)
    1062             : {
    1063             :   long i;
    1064     3414167 :   if ((x[0] ^ y[0]) & (TYPBITS|LGBITS)) return 0;
    1065    13893025 :   for (i = lg(x)-1; i; i--)
    1066    12015318 :     if (! gequal(gel(x,i),gel(y,i)) ) return 0;
    1067     1877707 :   return 1;
    1068             : }
    1069             : 
    1070             : static int
    1071     2272076 : gequal_try(GEN x, GEN y)
    1072             : {
    1073             :   int i;
    1074     2272076 :   pari_CATCH(CATCH_ALL) {
    1075         175 :     GEN E = pari_err_last();
    1076         175 :     switch(err_get_num(E))
    1077             :     {
    1078             :       case e_STACK: case e_MEM: case e_ALARM:
    1079           0 :         pari_err(0, E); /* rethrow */
    1080             :     }
    1081         175 :     return 0;
    1082             :   } pari_TRY {
    1083     2272076 :     i = gequal0(gadd(x, gneg_i(y)));
    1084     2271901 :   } pari_ENDCATCH;
    1085     2271901 :   return i;
    1086             : }
    1087             : 
    1088             : int
    1089   115610257 : gequal(GEN x, GEN y)
    1090             : {
    1091             :   pari_sp av;
    1092             :   long tx, ty;
    1093             :   long i;
    1094             : 
    1095   115610257 :   if (x == y) return 1;
    1096   103251304 :   tx = typ(x);
    1097   103251304 :   ty = typ(y);
    1098   103251304 :   if (tx == ty)
    1099   100979249 :     switch(tx)
    1100             :     {
    1101             :       case t_INT:
    1102    88375273 :         return equalii(x,y);
    1103             : 
    1104             :       case t_REAL:
    1105        1643 :         return equalrr(x,y);
    1106             : 
    1107             :       case t_FRAC: case t_INTMOD:
    1108     5046420 :         return equalii(gel(x,2), gel(y,2)) && equalii(gel(x,1), gel(y,1));
    1109             : 
    1110             :       case t_COMPLEX:
    1111         196 :         return gequal(gel(x,2),gel(y,2)) && gequal(gel(x,1),gel(y,1));
    1112             :       case t_PADIC:
    1113         756 :         if (!equalii(gel(x,2),gel(y,2))) return 0;
    1114         756 :         av = avma; i = gequal0(gsub(x,y)); avma = av;
    1115         756 :         return i;
    1116             :       case t_POLMOD:
    1117      231615 :         if (varn(gel(x,1)) != varn(gel(y,1))) break;
    1118      231594 :         return gequal(gel(x,2),gel(y,2)) && RgX_equal_var(gel(x,1),gel(y,1));
    1119             :       case t_POL:
    1120     2163812 :         return polequal(x,y);
    1121             :       case t_SER:
    1122         308 :         return serequal(x,y);
    1123             : 
    1124             :       case t_FFELT:
    1125       39151 :         return FF_equal(x,y);
    1126             : 
    1127             :       case t_QFR:
    1128             :       case t_QFI:
    1129     2098896 :         return equalii(gel(x,1),gel(y,1))
    1130      229856 :             && equalii(gel(x,2),gel(y,2))
    1131     1206287 :             && equalii(gel(x,3),gel(y,3));
    1132             : 
    1133             :       case t_QUAD:
    1134          14 :         return ZX_equal(gel(x,1),gel(y,1))
    1135           0 :             && gequal(gel(x,2),gel(y,2))
    1136           7 :             && gequal(gel(x,3),gel(y,3));
    1137             : 
    1138             :       case t_RFRAC:
    1139             :       {
    1140       73717 :         GEN a = gel(x,1), b = gel(x,2), c = gel(y,1), d = gel(y,2);
    1141       73717 :         if (gequal(b,d)) return gequal(a,c); /* simple case */
    1142           0 :         av = avma;
    1143           0 :         i = gequal(simplify_shallow(gmul(a,d)), simplify_shallow(gmul(b,c)));
    1144           0 :         avma = av; return i;
    1145             :       }
    1146             : 
    1147             :       case t_STR:
    1148       55235 :         return !strcmp(GSTR(x),GSTR(y));
    1149             :       case t_VEC: case t_COL: case t_MAT:
    1150     3414167 :         return vecequal(x,y);
    1151             :       case t_VECSMALL:
    1152      527291 :         return zv_equal(x,y);
    1153             :       case t_LIST:
    1154         175 :         return list_cmp(x, y, gequal);
    1155             :       case t_CLOSURE:
    1156           7 :         return closure_identical(x,y);
    1157             :       case t_INFINITY:
    1158          28 :         return gequal(gel(x,1),gel(y,1));
    1159             :     }
    1160             :   (void)&av; /* emulate volatile */
    1161     2272076 :   av = avma; i = gequal_try(x, y);
    1162     2272076 :   avma = av; return i;
    1163             : }
    1164             : 
    1165             : int
    1166       25375 : gequalsg(long s, GEN x)
    1167             : {
    1168       25375 :   pari_sp av = avma;
    1169       25375 :   int f = gequal(stoi(s), x);
    1170       25375 :   avma = av; return f;
    1171             : }
    1172             : 
    1173             : /* a and b are t_INT, t_FRAC, t_REAL or t_COMPLEX of those. Check whether
    1174             :  * a-b is invertible */
    1175             : int
    1176        9471 : cx_approx_equal(GEN a, GEN b)
    1177             : {
    1178        9471 :   pari_sp av = avma;
    1179             :   GEN d;
    1180             :   int r;
    1181        9471 :   if (a == b) return 1;
    1182        7868 :   d = gsub(a,b);
    1183        7868 :   r = (gequal0(d) || (typ(d) == t_COMPLEX && gequal0(cxnorm(d))));
    1184        7868 :   avma = av; return r;
    1185             : }
    1186             : /*******************************************************************/
    1187             : /*                                                                 */
    1188             : /*                          VALUATION                              */
    1189             : /*             p is either a t_INT or a t_POL.                     */
    1190             : /*  returns the largest exponent of p dividing x when this makes   */
    1191             : /*  sense : error for types real, integermod and polymod if p does */
    1192             : /*  not divide the modulus, q-adic if q!=p.                        */
    1193             : /*                                                                 */
    1194             : /*******************************************************************/
    1195             : 
    1196             : static long
    1197         231 : minval(GEN x, GEN p)
    1198             : {
    1199         231 :   long i,k, val = LONG_MAX, lx = lg(x);
    1200        5789 :   for (i=lontyp[typ(x)]; i<lx; i++)
    1201             :   {
    1202        5558 :     k = gvaluation(gel(x,i),p);
    1203        5558 :     if (k < val) val = k;
    1204             :   }
    1205         231 :   return val;
    1206             : }
    1207             : 
    1208             : static int
    1209          91 : intdvd(GEN x, GEN y, GEN *z) { GEN r; *z = dvmdii(x,y,&r); return (r==gen_0); }
    1210             : 
    1211             : /* x t_FRAC, p t_INT, return v_p(x) */
    1212             : static long
    1213       84350 : ratval(GEN x, GEN p) {
    1214       84350 :   long v = Z_pval(gel(x,2),p);
    1215       84350 :   if (v) return -v;
    1216        9205 :   return Z_pval(gel(x,1),p);
    1217             : }
    1218             : 
    1219             : long
    1220     1392749 : Q_pval(GEN x, GEN p) { return (typ(x) == t_INT)? Z_pval(x, p): ratval(x, p); }
    1221             : 
    1222             : long
    1223      438105 : Q_pvalrem(GEN x, GEN p, GEN *y)
    1224             : {
    1225             :   GEN a, b;
    1226             :   long v;
    1227      438105 :   if (typ(x) == t_INT) return Z_pvalrem(x, p, y);
    1228       78410 :   a = gel(x,1);
    1229       78410 :   b = gel(x,2);
    1230       78410 :   v = Z_pvalrem(b, p, &b);
    1231       78410 :   if (v) { *y = isint1(b)? a: mkfrac(a, b); return -v; }
    1232       48457 :   v = Z_pvalrem(a, p, &a);
    1233       48457 :   *y = mkfrac(a, b); return v;
    1234             : }
    1235             : 
    1236             : long
    1237      198525 : gvaluation(GEN x, GEN p)
    1238             : {
    1239      198525 :   long tx = typ(x), tp = typ(p);
    1240             :   pari_sp av;
    1241             : 
    1242      198525 :   switch(tp)
    1243             :   {
    1244             :     case t_INT:
    1245      195480 :       if (signe(p) && !is_pm1(p)) break;
    1246          28 :       pari_err_DOMAIN("gvaluation", "p", "=", p, p);
    1247             :     case t_POL:
    1248        3038 :       if (degpol(p) > 0) break;
    1249             :     default:
    1250           7 :       pari_err_DOMAIN("gvaluation", "p", "=", p, p);
    1251             :   }
    1252             : 
    1253      198490 :   switch(tx)
    1254             :   {
    1255             :     case t_INT:
    1256       11721 :       if (!signe(x)) return LONG_MAX;
    1257       11616 :       if (tp == t_POL) return 0;
    1258       11224 :       return Z_pval(x,p);
    1259             : 
    1260             :     case t_REAL:
    1261          49 :       if (tp == t_POL) return 0;
    1262          21 :       break;
    1263             : 
    1264             :     case t_FFELT:
    1265          28 :       if (tp == t_POL) return FF_equal0(x)? LONG_MAX: 0;
    1266          14 :       break;
    1267             : 
    1268             :     case t_INTMOD: {
    1269          77 :       GEN a = gel(x,1), b = gel(x,2);
    1270             :       long val;
    1271         140 :       if (tp == t_POL) return signe(b)? 0: LONG_MAX;
    1272          42 :       av = avma;
    1273          42 :       if (!intdvd(a, p, &a)) break;
    1274          28 :       if (!intdvd(b, p, &b)) { avma = av; return 0; }
    1275          14 :       val = 1; while (intdvd(a,p,&a) && intdvd(b,p,&b)) val++;
    1276          14 :       avma = av; return val;
    1277             :     }
    1278             : 
    1279             :     case t_FRAC:
    1280          42 :       if (tp == t_POL) return 0;
    1281          28 :       return ratval(x, p);
    1282             : 
    1283             :     case t_PADIC:
    1284      183878 :       if (tp == t_POL) return 0;
    1285      183864 :       if (!equalii(p,gel(x,2))) break;
    1286      183857 :       return valp(x);
    1287             : 
    1288             :     case t_POLMOD: {
    1289          35 :       GEN a = gel(x,1), b = gel(x,2);
    1290             :       long v, val;
    1291          35 :       if (tp == t_INT) return gvaluation(b,p);
    1292          21 :       v = varn(p);
    1293          21 :       if (varn(a) != v) return 0;
    1294          21 :       av = avma;
    1295          21 :       a = RgX_divrem(a, p, ONLY_DIVIDES);
    1296          21 :       if (!a) break;
    1297          14 :       if (typ(b) != t_POL || varn(b) != v ||
    1298           7 :           !(b = RgX_divrem(b, p, ONLY_DIVIDES)) ) { avma = av; return 0; }
    1299           7 :       val = 1;
    1300          21 :       while ((a = RgX_divrem(a, p, ONLY_DIVIDES)) &&
    1301           7 :              (b = RgX_divrem(b, p, ONLY_DIVIDES)) ) val++;
    1302           7 :       avma = av; return val;
    1303             :     }
    1304             :     case t_POL: {
    1305        2373 :       if (tp == t_POL) {
    1306        2240 :         long vp = varn(p), vx = varn(x);
    1307        2240 :         if (vp == vx)
    1308             :         {
    1309             :           long val;
    1310        2233 :           if (RgX_is_monomial(p)) return RgX_val(x) / degpol(p);
    1311           7 :           av = avma;
    1312           7 :           for (val=0; ; val++)
    1313             :           {
    1314           7 :             x = RgX_divrem(x,p,ONLY_DIVIDES);
    1315           7 :             if (!x) { avma = av; return val; }
    1316           0 :             if (gc_needed(av,1))
    1317             :             {
    1318           0 :               if(DEBUGMEM>1) pari_warn(warnmem,"gvaluation");
    1319           0 :               x = gerepilecopy(av, x);
    1320             :             }
    1321           0 :           }
    1322             :         }
    1323           7 :         if (varncmp(vx, vp) > 0) return 0;
    1324             :       }
    1325         133 :       return minval(x,p);
    1326             :     }
    1327             : 
    1328             :     case t_SER: {
    1329         175 :       if (tp == t_POL) {
    1330         161 :         long vp = varn(p), vx = varn(x);
    1331         161 :         if (vp == vx)
    1332             :         {
    1333         154 :           long val = RgX_val(p);
    1334         154 :           if (!val) pari_err_DOMAIN("gvaluation", "p", "=", p, p);
    1335         147 :           return (long)(valp(x) / val);
    1336             :         }
    1337           7 :         if (varncmp(vx, vp) > 0) return 0;
    1338             :       }
    1339          14 :       return minval(x,p);
    1340             :     }
    1341             : 
    1342             :     case t_RFRAC:
    1343          28 :       return gvaluation(gel(x,1),p) - gvaluation(gel(x,2),p);
    1344             : 
    1345             :     case t_COMPLEX: case t_QUAD: case t_VEC: case t_COL: case t_MAT:
    1346          84 :       return minval(x,p);
    1347             :   }
    1348          63 :   pari_err_OP("valuation", x,p);
    1349             :   return 0; /* LCOV_EXCL_LINE */
    1350             : }
    1351             : GEN
    1352        3661 : gpvaluation(GEN x, GEN p)
    1353             : {
    1354        3661 :   long v = gvaluation(x,p);
    1355        3563 :   return v == LONG_MAX? mkoo(): stoi(v);
    1356             : }
    1357             : 
    1358             : /* x is non-zero */
    1359             : long
    1360    12619928 : u_lvalrem(ulong x, ulong p, ulong *py)
    1361             : {
    1362             :   ulong vx;
    1363    12619928 :   if (p == 2) { vx = vals(x); *py = x >> vx; return vx; }
    1364    10444687 :   for(vx = 0;;)
    1365             :   {
    1366    21235554 :     if (x % p) { *py = x; return vx; }
    1367    10790867 :     x /= p; /* gcc is smart enough to make a single div */
    1368    10790867 :     vx++;
    1369    10790867 :   }
    1370             : }
    1371             : long
    1372    10005485 : u_lval(ulong x, ulong p)
    1373             : {
    1374             :   ulong vx;
    1375    10005485 :   if (p == 2) return vals(x);
    1376     9431630 :   for(vx = 0;;)
    1377             :   {
    1378    27477696 :     if (x % p) return vx;
    1379    18046066 :     x /= p; /* gcc is smart enough to make a single div */
    1380    18046066 :     vx++;
    1381    18046066 :   }
    1382             : }
    1383             : 
    1384             : long
    1385      345350 : z_lval(long s, ulong p) { return u_lval(labs(s), p); }
    1386             : long
    1387           0 : z_lvalrem(long s, ulong p, long *py)
    1388             : {
    1389             :   long v;
    1390           0 :   if (s < 0)
    1391             :   {
    1392           0 :     ulong u = (ulong)-s;
    1393           0 :     v = u_lvalrem(u, p, &u);
    1394           0 :     *py = -(long)u;
    1395             :   }
    1396             :   else
    1397             :   {
    1398           0 :     ulong u = (ulong)s;
    1399           0 :     v = u_lvalrem(u, p, &u);
    1400           0 :     *py = (long)u;
    1401             :   }
    1402           0 :   return v;
    1403             : }
    1404             : /* assume |p| > 1 */
    1405             : long
    1406       42009 : z_pval(long s, GEN p)
    1407             : {
    1408       42009 :   if (lgefint(p) > 3) return 0;
    1409       42009 :   return z_lval(s, uel(p,2));
    1410             : }
    1411             : /* assume |p| > 1 */
    1412             : long
    1413           0 : z_pvalrem(long s, GEN p, long *py)
    1414             : {
    1415           0 :   if (lgefint(p) > 3) { *py = s; return 0; }
    1416           0 :   return z_lvalrem(s, uel(p,2), py);
    1417             : }
    1418             : 
    1419             : /* return v_q(x) and set *py = x / q^v_q(x), using divide & conquer */
    1420             : static long
    1421     1365150 : Z_pvalrem_DC(GEN x, GEN q, GEN *py)
    1422             : {
    1423     1365150 :   GEN r, z = dvmdii(x, q, &r);
    1424             :   long v;
    1425     1365150 :   if (r != gen_0) { *py = x; return 0; }
    1426      958079 :   if (2 * lgefint(q) <= lgefint(z)+3) /* avoid squaring if pointless */
    1427      944543 :     v = Z_pvalrem_DC(z, sqri(q), py) << 1;
    1428             :   else
    1429       13536 :   { v = 0; *py = z; }
    1430      958079 :   z = dvmdii(*py, q, &r);
    1431      958079 :   if (r != gen_0) return v + 1;
    1432      406011 :   *py = z; return v + 2;
    1433             : }
    1434             : 
    1435             : static const long VAL_DC_THRESHOLD = 16;
    1436             : 
    1437             : long
    1438    10748421 : Z_lval(GEN x, ulong p)
    1439             : {
    1440             :   long vx;
    1441             :   pari_sp av;
    1442    10748421 :   if (p == 2) return vali(x);
    1443     7586032 :   if (lgefint(x) == 3) return u_lval(uel(x,2), p);
    1444      873844 :   av = avma;
    1445      873844 :   for(vx = 0;;)
    1446             :   {
    1447             :     ulong r;
    1448     6198698 :     GEN q = diviu_rem(x, p, &r);
    1449     7072542 :     if (r) break;
    1450     5440062 :     vx++; x = q;
    1451     5440062 :     if (vx == VAL_DC_THRESHOLD) {
    1452      115208 :       if (p == 1) pari_err_DOMAIN("Z_lval", "p", "=", gen_1, gen_1);
    1453      115208 :       vx += Z_pvalrem_DC(x, sqru(p), &x) << 1;
    1454      115208 :       q = diviu_rem(x, p, &r); if (!r) vx++;
    1455      115208 :       break;
    1456             :     }
    1457     5324854 :   }
    1458      873844 :   avma = av; return vx;
    1459             : }
    1460             : long
    1461     8327244 : Z_lvalrem(GEN x, ulong p, GEN *py)
    1462             : {
    1463             :   long vx, sx;
    1464             :   pari_sp av;
    1465     8327244 :   if (p == 2) { vx = vali(x); *py = shifti(x, -vx); return vx; }
    1466     6102294 :   if (lgefint(x) == 3) {
    1467             :     ulong u;
    1468     3934899 :     vx = u_lvalrem(uel(x,2), p, &u);
    1469     3934898 :     *py = signe(x) < 0? utoineg(u): utoipos(u);
    1470     3934895 :     return vx;
    1471             :   }
    1472     2167395 :   av = avma; (void)new_chunk(lgefint(x));
    1473     2167395 :   sx = signe(x);
    1474     2167395 :   for(vx = 0;;)
    1475             :   {
    1476             :     ulong r;
    1477     9902435 :     GEN q = diviu_rem(x, p, &r);
    1478    12069830 :     if (r) break;
    1479     8032636 :     vx++; x = q;
    1480     8032636 :     if (vx == VAL_DC_THRESHOLD) {
    1481      297596 :       if (p == 1) pari_err_DOMAIN("Z_lvalrem", "p", "=", gen_1, gen_1);
    1482      297596 :       vx += Z_pvalrem_DC(x, sqru(p), &x) << 1;
    1483      297596 :       q = diviu_rem(x, p, &r); if (!r) { vx++; x = q; }
    1484      297596 :       break;
    1485             :     }
    1486     7735040 :   }
    1487     2167395 :   avma = av; *py = icopy(x); setsigne(*py, sx); return vx;
    1488             : }
    1489             : 
    1490             : /* Is |q| <= p ? */
    1491             : static int
    1492   171507983 : isless_iu(GEN q, ulong p) {
    1493   171507983 :   long l = lgefint(q);
    1494   171507983 :   return l==2 || (l == 3 && uel(q,2) <= p);
    1495             : }
    1496             : 
    1497             : long
    1498   390775199 : u_lvalrem_stop(ulong *n, ulong p, int *stop)
    1499             : {
    1500   390775199 :   ulong N = *n, q = N / p, r = N % p; /* gcc makes a single div */
    1501   390775199 :   long v = 0;
    1502   390775199 :   if (!r)
    1503             :   {
    1504    32015701 :     do { v++; N = q; q = N / p; r = N % p; } while (!r);
    1505    21079972 :     *n = N;
    1506             :   }
    1507   390775199 :   *stop = q <= p; return v;
    1508             : }
    1509             : /* Assume n > 0. Return v_p(n), set *n := n/p^v_p(n). Set 'stop' if now
    1510             :  * n < p^2 [implies n prime if no prime < p divides n] */
    1511             : long
    1512   446282120 : Z_lvalrem_stop(GEN *n, ulong p, int *stop)
    1513             : {
    1514             :   pari_sp av;
    1515             :   long v;
    1516             :   ulong r;
    1517             :   GEN N, q;
    1518             : 
    1519   446282120 :   if (lgefint(*n) == 3)
    1520             :   {
    1521   274776378 :     r = (*n)[2];
    1522   274776378 :     v = u_lvalrem_stop(&r, p, stop);
    1523   275344270 :     if (v) *n = utoipos(r);
    1524   275343924 :     return v;
    1525             :   }
    1526   171505742 :   av = avma; v = 0; q = diviu_rem(*n, p, &r);
    1527   171505922 :   if (r) avma = av;
    1528             :   else
    1529             :   {
    1530             :     do {
    1531      657736 :       v++; N = q;
    1532      657736 :       if (v == VAL_DC_THRESHOLD)
    1533             :       {
    1534        7803 :         v += Z_pvalrem_DC(N,sqru(p),&N) << 1;
    1535        7803 :         q = diviu_rem(N, p, &r); if (!r) { v++; N = q; }
    1536        7803 :         break;
    1537             :       }
    1538      649933 :       q = diviu_rem(N, p, &r);
    1539      649933 :     } while (!r);
    1540      268086 :     *n = N;
    1541             :   }
    1542   171505922 :   *stop = isless_iu(q,p); return v;
    1543             : }
    1544             : 
    1545             : /* x is a non-zero integer, |p| > 1 */
    1546             : long
    1547     6031312 : Z_pvalrem(GEN x, GEN p, GEN *py)
    1548             : {
    1549             :   long vx;
    1550             :   pari_sp av;
    1551             : 
    1552     6031312 :   if (lgefint(p) == 3) return Z_lvalrem(x, uel(p,2), py);
    1553      122690 :   if (lgefint(x) == 3) { *py = icopy(x); return 0; }
    1554        1981 :   av = avma; vx = 0; (void)new_chunk(lgefint(x));
    1555             :   for(;;)
    1556             :   {
    1557        4298 :     GEN r, q = dvmdii(x,p,&r);
    1558        4298 :     if (r != gen_0) { avma = av; *py = icopy(x); return vx; }
    1559        2317 :     vx++; x = q;
    1560        2317 :   }
    1561             : }
    1562             : long
    1563      383467 : u_pvalrem(ulong x, GEN p, ulong *py)
    1564             : {
    1565      383467 :   if (lgefint(p) == 3) return u_lvalrem(x, uel(p,2), py);
    1566         116 :   *py = x; return 0;
    1567             : }
    1568             : long
    1569        2072 : u_pval(ulong x, GEN p)
    1570             : {
    1571        2072 :   if (lgefint(p) == 3) return u_lval(x, uel(p,2));
    1572           0 :   return 0;
    1573             : }
    1574             : long
    1575     6740358 : Z_pval(GEN x, GEN p) {
    1576             :   long vx;
    1577             :   pari_sp av;
    1578             : 
    1579     6740358 :   if (lgefint(p) == 3) return Z_lval(x, uel(p,2));
    1580       70432 :   if (lgefint(x) == 3) return 0;
    1581       64773 :   av = avma; vx = 0;
    1582             :   for(;;)
    1583             :   {
    1584       82040 :     GEN r, q = dvmdii(x,p,&r);
    1585       82040 :     if (r != gen_0) { avma = av; return vx; }
    1586       17267 :     vx++; x = q;
    1587       17267 :   }
    1588             : }
    1589             : 
    1590             : /* return v_p(n!) = [n/p] + [n/p^2] + ... */
    1591             : long
    1592       66539 : factorial_lval(ulong n, ulong p)
    1593             : {
    1594       66539 :   ulong q = p, v = 0;
    1595      109463 :   do { v += n/q; q *= p; } while (n >= q);
    1596       66539 :   return (long)v;
    1597             : }
    1598             : 
    1599             : /********** Same for "containers" ZX / ZV / ZC **********/
    1600             : 
    1601             : /* If the t_INT q divides the ZX/ZV x, return the quotient. Otherwise NULL.
    1602             :  * Stack clean; assumes lg(x) > 1 */
    1603             : static GEN
    1604        3962 : gen_Z_divides(GEN x, GEN q, long imin)
    1605             : {
    1606             :   long i, l;
    1607        3962 :   GEN y = cgetg_copy(x, &l);
    1608             : 
    1609        3962 :   y[1] = x[1]; /* Needed for ZX; no-op if ZV, overwritten in first iteration */
    1610       81683 :   for (i = imin; i < l; i++)
    1611             :   {
    1612       80164 :     GEN r, xi = gel(x,i);
    1613       80164 :     if (!signe(xi)) { gel(y,i) = xi; continue; }
    1614       48958 :     gel(y,i) = dvmdii(xi, q, &r);
    1615       48958 :     if (r != gen_0) { avma = (pari_sp)(y+l); return NULL; }
    1616             :   }
    1617        1519 :   return y;
    1618             : }
    1619             : /* If q divides the ZX/ZV x, return the quotient. Otherwise NULL.
    1620             :  * Stack clean; assumes lg(x) > 1 */
    1621             : static GEN
    1622        2541 : gen_z_divides(GEN x, ulong q, long imin)
    1623             : {
    1624             :   long i, l;
    1625        2541 :   GEN y = cgetg_copy(x, &l);
    1626             : 
    1627        2541 :   y[1] = x[1]; /* Needed for ZX; no-op if ZV, overwritten in first iteration */
    1628       36078 :   for (i = imin; i < l; i++)
    1629             :   {
    1630             :     ulong r;
    1631       35721 :     GEN xi = gel(x,i);
    1632       35721 :     if (!signe(xi)) { gel(y,i) = xi; continue; }
    1633       22162 :     gel(y,i) = diviu_rem(xi, q, &r);
    1634       22162 :     if (r) { avma = (pari_sp)(y+l); return NULL; }
    1635       19978 :     affectsign_safe(xi, &gel(y,i));
    1636             :   }
    1637         357 :   return y;
    1638             : }
    1639             : 
    1640             : /* return v_q(x) and set *py = x / q^v_q(x), using divide & conquer */
    1641             : static long
    1642        6466 : gen_pvalrem_DC(GEN x, GEN q, GEN *py, long imin)
    1643             : {
    1644             : 
    1645        6466 :   pari_sp av = avma;
    1646        6466 :   long v, i, l, lz = LONG_MAX;
    1647        6466 :   GEN y = cgetg_copy(x, &l);
    1648             : 
    1649        6466 :   y[1] = x[1];
    1650      118688 :   for (i = imin; i < l; i++)
    1651             :   {
    1652      114726 :     GEN r, xi = gel(x,i);
    1653      114726 :     if (!signe(xi)) { gel(y,i) = xi; continue; }
    1654       72098 :     gel(y,i) = dvmdii(xi, q, &r);
    1655       72098 :     if (r != gen_0) { avma = av; *py = x; return 0; }
    1656       69594 :     lz = minss(lz, lgefint(gel(y,i)));
    1657             :   }
    1658        3962 :   if (2 * lgefint(q) <= lz+3) /* avoid squaring if pointless */
    1659        3918 :     v = gen_pvalrem_DC(y, sqri(q), py, imin) << 1;
    1660             :   else
    1661          44 :   { v = 0; *py = y; }
    1662             : 
    1663        3962 :   y = gen_Z_divides(*py, q, imin);
    1664        3962 :   if (!y) return v+1;
    1665        1519 :   *py = y; return v+2;
    1666             : }
    1667             : 
    1668             : static long
    1669        3920 : gen_2val(GEN x, long imin)
    1670             : {
    1671        3920 :   long i, lx = lg(x), v = LONG_MAX;
    1672        7289 :   for (i = imin; i < lx; i++)
    1673             :   {
    1674        7247 :     GEN c = gel(x,i);
    1675             :     long w;
    1676        7247 :     if (!signe(c)) continue;
    1677        4346 :     w = vali(c);
    1678        4346 :     if (w < v) { v = w; if (!v) break; }
    1679             :   }
    1680        3920 :   return v;
    1681             : }
    1682             : static long
    1683       10615 : gen_lval(GEN x, ulong p, long imin)
    1684             : {
    1685             :   long i, lx, v;
    1686             :   pari_sp av;
    1687             :   GEN y;
    1688       10615 :   if (p == 2) return gen_2val(x, imin);
    1689        6695 :   av = avma;
    1690        6695 :   lx = lg(x); y = leafcopy(x);
    1691        6786 :   for(v = 0;; v++)
    1692        8214 :     for (i = imin; i < lx; i++)
    1693             :     {
    1694        8123 :       ulong r; gel(y,i) = diviu_rem(gel(y,i), p, &r);
    1695        8123 :       if (r) { avma = av; return v; }
    1696          91 :     }
    1697             : }
    1698             : long
    1699          28 : ZX_lval(GEN x, ulong p) { return gen_lval(x, p, 2); }
    1700             : long
    1701           0 : ZV_lval(GEN x, ulong p) { return gen_lval(x, p, 1); }
    1702             : 
    1703             : static long
    1704       12761 : gen_pval(GEN x, GEN p, long imin)
    1705             : {
    1706             :   long i, lx, v;
    1707             :   pari_sp av;
    1708             :   GEN y;
    1709       12761 :   if (lgefint(p) == 3) return gen_lval(x, p[2], imin);
    1710        2174 :   av = avma;
    1711        2174 :   lx = lg(x); y = leafcopy(x);
    1712        2174 :   for(v = 0;; v++)
    1713             :   {
    1714        2174 :     if (v == VAL_DC_THRESHOLD)
    1715             :     {
    1716           0 :       if (is_pm1(p)) pari_err_DOMAIN("gen_pval", "p", "=", p, p);
    1717           0 :       v += gen_pvalrem_DC(y, p, &y, imin);
    1718           0 :       avma = av; return v;
    1719             :     }
    1720             : 
    1721        2174 :     for (i = imin; i < lx; i++)
    1722             :     {
    1723        2174 :       GEN r; gel(y,i) = dvmdii(gel(y,i), p, &r);
    1724        2174 :       if (r != gen_0) { avma = av; return v; }
    1725             :     }
    1726           0 :   }
    1727             : }
    1728             : long
    1729        6307 : ZX_pval(GEN x, GEN p) { return gen_pval(x, p, 2); }
    1730             : long
    1731        6454 : ZV_pval(GEN x, GEN p) { return gen_pval(x, p, 1); }
    1732             : /* v = 0 (mod p) */
    1733             : int
    1734         217 : ZV_Z_dvd(GEN v, GEN p)
    1735             : {
    1736         217 :   pari_sp av = avma;
    1737         217 :   long i, l = lg(v);
    1738         805 :   for (i=1; i<l; i++)
    1739         616 :     if (remii(gel(v,i), p) != gen_0) { avma = av; return 0; }
    1740         189 :   avma = av; return 1;
    1741             : }
    1742             : 
    1743             : static long
    1744      299443 : gen_2valrem(GEN x, GEN *px, long imin)
    1745             : {
    1746      299443 :   long i, lx = lg(x), v = LONG_MAX;
    1747             :   GEN z;
    1748     3233801 :   for (i = imin; i < lx; i++)
    1749             :   {
    1750     3059046 :     GEN c = gel(x,i);
    1751             :     long w;
    1752     3059046 :     if (!signe(c)) continue;
    1753     2922294 :     w = vali(c);
    1754     2922294 :     if (w < v) {
    1755      594024 :       v = w;
    1756      594024 :       if (!v) { *px = x; return 0; } /* early abort */
    1757             :     }
    1758             :   }
    1759      174755 :   z = cgetg_copy(x, &lx); z[1] = x[1];
    1760      174755 :   for (i=imin; i<lx; i++) gel(z,i) = shifti(gel(x,i), -v);
    1761      174755 :   *px = z; return v;
    1762             : }
    1763             : static long
    1764      642253 : gen_lvalrem(GEN x, ulong p, GEN *px, long imin)
    1765             : {
    1766             :   long i, lx, v;
    1767             :   GEN y;
    1768      642253 :   if (p == 2) return gen_2valrem(x, px, imin);
    1769      342810 :   y = cgetg_copy(x, &lx);
    1770      342810 :   y[1] = x[1];
    1771      342810 :   x = leafcopy(x);
    1772      754573 :   for(v = 0;; v++)
    1773             :   {
    1774      754573 :     if (v == VAL_DC_THRESHOLD)
    1775             :     {
    1776        2541 :       if (p == 1) pari_err_DOMAIN("gen_lvalrem", "p", "=", gen_1, gen_1);
    1777        2541 :       v += gen_pvalrem_DC(x, sqru(p), px, imin) << 1;
    1778        2541 :       x = gen_z_divides(*px, p, imin);
    1779        2541 :       if (x) { *px = x; v++; }
    1780        2541 :       return v;
    1781             :     }
    1782             : 
    1783     6038728 :     for (i = imin; i < lx; i++)
    1784             :     {
    1785     5626965 :       ulong r; gel(y,i) = diviu_rem(gel(x,i), p, &r);
    1786     5626965 :       if (r) { *px = x; return v; }
    1787     5286696 :       affectsign_safe(gel(x,i), &gel(y,i));
    1788             :     }
    1789      411763 :     swap(x, y);
    1790      411763 :   }
    1791             : }
    1792             : long
    1793           0 : ZX_lvalrem(GEN x, ulong p, GEN *px) { return gen_lvalrem(x,p,px, 2); }
    1794             : long
    1795           0 : ZV_lvalrem(GEN x, ulong p, GEN *px) { return gen_lvalrem(x,p,px, 1); }
    1796             : 
    1797             : static long
    1798      642289 : gen_pvalrem(GEN x, GEN p, GEN *px, long imin)
    1799             : {
    1800             :   long i, lx, v;
    1801             :   GEN y;
    1802      642289 :   if (lgefint(p) == 3) return gen_lvalrem(x, p[2], px, imin);
    1803          36 :   y = cgetg_copy(x, &lx);
    1804          36 :   y[1] = x[1];
    1805          36 :   x = leafcopy(x);
    1806         160 :   for(v = 0;; v++)
    1807             :   {
    1808         160 :     if (v == VAL_DC_THRESHOLD)
    1809             :     {
    1810           7 :       if (is_pm1(p)) pari_err_DOMAIN("gen_pvalrem", "p", "=", p, p);
    1811           7 :       return v + gen_pvalrem_DC(x, p, px, imin);
    1812             :     }
    1813             : 
    1814        3693 :     for (i = imin; i < lx; i++)
    1815             :     {
    1816        3569 :       GEN r; gel(y,i) = dvmdii(gel(x,i), p, &r);
    1817        3569 :       if (r != gen_0) { *px = x; return v; }
    1818             :     }
    1819         124 :     swap(x, y);
    1820         124 :   }
    1821             : }
    1822             : long
    1823      535542 : ZX_pvalrem(GEN x, GEN p, GEN *px) { return gen_pvalrem(x,p,px, 2); }
    1824             : long
    1825      106747 : ZV_pvalrem(GEN x, GEN p, GEN *px) { return gen_pvalrem(x,p,px, 1); }
    1826             : 
    1827             : /*******************************************************************/
    1828             : /*                                                                 */
    1829             : /*                       NEGATION: Create -x                       */
    1830             : /*                                                                 */
    1831             : /*******************************************************************/
    1832             : 
    1833             : GEN
    1834   192046184 : gneg(GEN x)
    1835             : {
    1836             :   long lx, i;
    1837             :   GEN y;
    1838             : 
    1839   192046184 :   switch(typ(x))
    1840             :   {
    1841             :     case t_INT:
    1842    59833635 :       return signe(x)? negi(x): gen_0;
    1843             :     case t_REAL:
    1844    92023393 :       return mpneg(x);
    1845             : 
    1846      247506 :     case t_INTMOD: y=cgetg(3,t_INTMOD);
    1847      247506 :       gel(y,1) = icopy(gel(x,1));
    1848      247506 :       gel(y,2) = signe(gel(x,2))? subii(gel(y,1),gel(x,2)): gen_0;
    1849      247506 :       break;
    1850             : 
    1851             :     case t_FRAC:
    1852      525489 :       y = cgetg(3, t_FRAC);
    1853      525489 :       gel(y,1) = negi(gel(x,1));
    1854      525489 :       gel(y,2) = icopy(gel(x,2)); break;
    1855             : 
    1856             :     case t_COMPLEX:
    1857    38011166 :       y=cgetg(3, t_COMPLEX);
    1858    38011166 :       gel(y,1) = gneg(gel(x,1));
    1859    38011166 :       gel(y,2) = gneg(gel(x,2));
    1860    38011166 :       break;
    1861             : 
    1862      107583 :     case t_POLMOD: y=cgetg(3,t_POLMOD);
    1863      107583 :       gel(y,1) = RgX_copy(gel(x,1));
    1864      107583 :       gel(y,2) = gneg(gel(x,2)); break;
    1865             : 
    1866             :     case t_RFRAC:
    1867      153076 :       y = cgetg(3, t_RFRAC);
    1868      153076 :       gel(y,1) = gneg(gel(x,1));
    1869      153076 :       gel(y,2) = RgX_copy(gel(x,2)); break;
    1870             : 
    1871             :     case t_PADIC:
    1872        7021 :       if (!signe(gel(x,4))) return gcopy(x);
    1873        6027 :       y = cgetg(5, t_PADIC);
    1874        6027 :       y[1] = x[1];
    1875        6027 :       gel(y,2) = icopy(gel(x,2));
    1876        6027 :       gel(y,3) = icopy(gel(x,3));
    1877        6027 :       gel(y,4) = subii(gel(x,3),gel(x,4));
    1878        6027 :       break;
    1879             : 
    1880             :     case t_QUAD:
    1881          42 :       y=cgetg(4,t_QUAD);
    1882          42 :       gel(y,1) = ZX_copy(gel(x,1));
    1883          42 :       gel(y,2) = gneg(gel(x,2));
    1884          42 :       gel(y,3) = gneg(gel(x,3)); break;
    1885             : 
    1886       35806 :     case t_FFELT: return FF_neg(x);
    1887     1005004 :     case t_POL: return RgX_neg(x);
    1888             :     case t_SER:
    1889        1029 :       y = cgetg_copy(x, &lx); y[1] = x[1];
    1890        1029 :       for (i=2; i<lx; i++) gel(y,i) = gneg(gel(x,i));
    1891        1029 :       break;
    1892       22681 :     case t_VEC: return RgV_neg(x);
    1893       69547 :     case t_COL: return RgC_neg(x);
    1894        2485 :     case t_MAT: return RgM_neg(x);
    1895         721 :     case t_INFINITY: return inf_get_sign(x) == 1? mkmoo(): mkoo();
    1896             :     default:
    1897           0 :       pari_err_TYPE("gneg",x);
    1898             :       return NULL; /* LCOV_EXCL_LINE */
    1899             :   }
    1900    39051918 :   return y;
    1901             : }
    1902             : 
    1903             : GEN
    1904    40012040 : gneg_i(GEN x)
    1905             : {
    1906             :   long lx, i;
    1907             :   GEN y;
    1908             : 
    1909    40012040 :   switch(typ(x))
    1910             :   {
    1911             :     case t_INT:
    1912    20973518 :       return signe(x)? negi(x): gen_0;
    1913             :     case t_REAL:
    1914     4612618 :       return mpneg(x);
    1915             : 
    1916      544266 :     case t_INTMOD: y=cgetg(3,t_INTMOD);
    1917      544266 :       gel(y,1) = gel(x,1);
    1918      544266 :       gel(y,2) = signe(gel(x,2))? subii(gel(y,1),gel(x,2)): gen_0;
    1919      544266 :       break;
    1920             : 
    1921             :     case t_FRAC:
    1922     1063292 :       y = cgetg(3, t_FRAC);
    1923     1063292 :       gel(y,1) = negi(gel(x,1));
    1924     1063292 :       gel(y,2) = gel(x,2); break;
    1925             : 
    1926             :     case t_COMPLEX:
    1927     1331490 :       y = cgetg(3, t_COMPLEX);
    1928     1331490 :       gel(y,1) = gneg_i(gel(x,1));
    1929     1331490 :       gel(y,2) = gneg_i(gel(x,2)); break;
    1930             : 
    1931      124799 :     case t_PADIC: y = cgetg(5,t_PADIC);
    1932      124799 :       y[1] = x[1];
    1933      124799 :       gel(y,2) = gel(x,2);
    1934      124799 :       gel(y,3) = gel(x,3);
    1935      124799 :       gel(y,4) = signe(gel(x,4))? subii(gel(x,3),gel(x,4)): gen_0; break;
    1936             : 
    1937       56616 :     case t_POLMOD: y=cgetg(3,t_POLMOD);
    1938       56616 :       gel(y,1) = gel(x,1);
    1939       56616 :       gel(y,2) = gneg_i(gel(x,2)); break;
    1940             : 
    1941       84861 :     case t_FFELT: return FF_neg_i(x);
    1942             : 
    1943         609 :     case t_QUAD: y=cgetg(4,t_QUAD);
    1944         609 :       gel(y,1) = gel(x,1);
    1945         609 :       gel(y,2) = gneg_i(gel(x,2));
    1946         609 :       gel(y,3) = gneg_i(gel(x,3)); break;
    1947             : 
    1948             :     case t_VEC: case t_COL: case t_MAT:
    1949       17640 :       y = cgetg_copy(x, &lx);
    1950       17640 :       for (i=1; i<lx; i++) gel(y,i) = gneg_i(gel(x,i));
    1951       17640 :       break;
    1952             : 
    1953             :     case t_POL: case t_SER:
    1954     6203926 :       y = cgetg_copy(x, &lx); y[1]=x[1];
    1955     6203926 :       for (i=2; i<lx; i++) gel(y,i) = gneg_i(gel(x,i));
    1956     6203926 :       break;
    1957             : 
    1958             :     case t_RFRAC:
    1959     4998405 :       y = cgetg(3, t_RFRAC);
    1960     4998405 :       gel(y,1) = gneg_i(gel(x,1));
    1961     4998405 :       gel(y,2) = gel(x,2); break;
    1962             : 
    1963             :     default:
    1964           0 :       pari_err_TYPE("gneg_i",x);
    1965             :       return NULL; /* LCOV_EXCL_LINE */
    1966             :   }
    1967    14341043 :   return y;
    1968             : }
    1969             : 
    1970             : /******************************************************************/
    1971             : /*                                                                */
    1972             : /*                       ABSOLUTE VALUE                           */
    1973             : /*    Create abs(x) if x is integer, real, fraction or complex.   */
    1974             : /*                       Error otherwise.                         */
    1975             : /*                                                                */
    1976             : /******************************************************************/
    1977             : static int
    1978           0 : is_negative(GEN x) {
    1979           0 :   switch(typ(x))
    1980             :   {
    1981             :     case t_INT: case t_REAL:
    1982           0 :       return (signe(x) < 0);
    1983             :     case t_FRAC:
    1984           0 :       return (signe(gel(x,1)) < 0);
    1985             :   }
    1986           0 :   return 0;
    1987             : }
    1988             : 
    1989             : GEN
    1990     9267563 : gabs(GEN x, long prec)
    1991             : {
    1992             :   long lx, i;
    1993             :   pari_sp av, tetpil;
    1994             :   GEN y,p1;
    1995             : 
    1996     9267563 :   switch(typ(x))
    1997             :   {
    1998             :     case t_INT: case t_REAL:
    1999     7110898 :       return mpabs(x);
    2000             : 
    2001             :     case t_FRAC:
    2002        3773 :       return absfrac(x);
    2003             : 
    2004             :     case t_COMPLEX:
    2005     2144506 :       av=avma; p1=cxnorm(x);
    2006     2144506 :       switch(typ(p1))
    2007             :       {
    2008             :         case t_INT:
    2009         889 :           if (!Z_issquareall(p1, &y)) break;
    2010         693 :           return gerepileupto(av, y);
    2011             :         case t_FRAC: {
    2012             :           GEN a,b;
    2013         112 :           if (!Z_issquareall(gel(p1,1), &a)) break;
    2014          42 :           if (!Z_issquareall(gel(p1,2), &b)) break;
    2015           0 :           return gerepileupto(av, gdiv(a,b));
    2016             :         }
    2017             :       }
    2018     2143813 :       tetpil=avma;
    2019     2143813 :       return gerepile(av,tetpil,gsqrt(p1,prec));
    2020             : 
    2021             :     case t_QUAD:
    2022          21 :       av = avma;
    2023          21 :       return gerepileuptoleaf(av, gabs(quadtofp(x, prec), prec));
    2024             : 
    2025             :     case t_POL:
    2026           0 :       lx = lg(x); if (lx<=2) return RgX_copy(x);
    2027           0 :       return is_negative(gel(x,lx-1))? gneg(x): RgX_copy(x);
    2028             : 
    2029             :     case t_SER:
    2030           7 :      if (!signe(x)) pari_err_DOMAIN("abs", "argument", "=", gen_0, x);
    2031           7 :      if (valp(x)) pari_err_DOMAIN("abs", "series valuation", "!=", gen_0, x);
    2032           0 :      return is_negative(gel(x,2))? gneg(x): gcopy(x);
    2033             : 
    2034             :     case t_VEC: case t_COL: case t_MAT:
    2035        8358 :       y = cgetg_copy(x, &lx);
    2036        8358 :       for (i=1; i<lx; i++) gel(y,i) = gabs(gel(x,i),prec);
    2037        8358 :       return y;
    2038             :   }
    2039           0 :   pari_err_TYPE("gabs",x);
    2040             :   return NULL; /* LCOV_EXCL_LINE */
    2041             : }
    2042             : 
    2043             : GEN
    2044     7832420 : gmax(GEN x, GEN y) { return gcopy(gcmp(x,y)<0? y: x); }
    2045             : GEN
    2046           0 : gmaxgs(GEN x, long s) { return (gcmpsg(s,x)>=0)? stoi(s): gcopy(x); }
    2047             : 
    2048             : GEN
    2049       92168 : gmin(GEN x, GEN y) { return gcopy(gcmp(x,y)<0? x: y); }
    2050             : GEN
    2051           0 : gmings(GEN x, long s) { return (gcmpsg(s,x)>0)? gcopy(x): stoi(s); }
    2052             : 
    2053             : long
    2054        6556 : vecindexmax(GEN x)
    2055             : {
    2056        6556 :   long lx = lg(x), i0, i;
    2057             :   GEN s;
    2058             : 
    2059        6556 :   if (lx==1) pari_err_DOMAIN("vecindexmax", "empty argument", "=", x,x);
    2060        6556 :   switch(typ(x))
    2061             :   {
    2062             :     case t_VEC: case t_COL:
    2063        6556 :       s = gel(x,i0=1);
    2064       21351 :       for (i=2; i<lx; i++)
    2065       14795 :         if (gcmp(gel(x,i),s) > 0) s = gel(x,i0=i);
    2066        6556 :       return i0;
    2067             :     case t_VECSMALL:
    2068           0 :       return vecsmall_indexmax(x);
    2069           0 :     default: pari_err_TYPE("vecindexmax",x);
    2070             :   }
    2071             :   /* LCOV_EXCL_LINE */
    2072           0 :   return 0;
    2073             : }
    2074             : long
    2075        8369 : vecindexmin(GEN x)
    2076             : {
    2077        8369 :   long lx = lg(x), i0, i;
    2078             :   GEN s;
    2079             : 
    2080        8369 :   if (lx==1) pari_err_DOMAIN("vecindexmin", "empty argument", "=", x,x);
    2081        8369 :   switch(typ(x))
    2082             :   {
    2083             :     case t_VEC: case t_COL:
    2084        8369 :       s = gel(x,i0=1);
    2085       21960 :       for (i=2; i<lx; i++)
    2086       13591 :         if (gcmp(gel(x,i),s) < 0) s = gel(x,i0=i);
    2087        8369 :       return i0;
    2088             :     case t_VECSMALL:
    2089           0 :       return vecsmall_indexmin(x);
    2090           0 :     default: pari_err_TYPE("vecindexmin",x);
    2091             :   }
    2092             :   /* LCOV_EXCL_LINE */
    2093           0 :   return 0;
    2094             : }
    2095             : 
    2096             : GEN
    2097        2623 : vecmax0(GEN x, GEN *pi)
    2098             : {
    2099        2623 :   long i, lx = lg(x), tx = typ(x);
    2100        2623 :   if (!is_matvec_t(tx) && tx != t_VECSMALL) return gcopy(x);
    2101        2609 :   if (lx==1) pari_err_DOMAIN("vecmax", "empty argument", "=", x,x);
    2102        2588 :   switch(typ(x))
    2103             :   {
    2104             :     case t_VEC: case t_COL:
    2105        2149 :       i = vecindexmax(x); if (pi) *pi = utoipos(i);
    2106        2149 :       return gcopy(gel(x,i));
    2107             :     case t_MAT: {
    2108         425 :       long j, i0 = 1, j0 = 1, lx2 = lgcols(x);
    2109             :       GEN s;
    2110         425 :       if (lx2 == 1) pari_err_DOMAIN("vecmin", "empty argument", "=", x,x);
    2111         418 :       s = gcoeff(x,i0,j0); i = 2;
    2112        1660 :       for (j=1; j<lx; j++,i=1)
    2113             :       {
    2114        1242 :         GEN c = gel(x,j);
    2115       24574 :         for (; i<lx2; i++)
    2116       23332 :           if (gcmp(gel(c,i),s) > 0) { s = gel(c,i); j0=j; i0=i; }
    2117             :       }
    2118         418 :       if (pi) *pi = mkvec2(utoipos(i0), utoipos(j0));
    2119         418 :       return gcopy(s);
    2120             :     }
    2121             :     case t_VECSMALL:
    2122          14 :       i = vecsmall_indexmax(x); if (pi) *pi = utoipos(i);
    2123          14 :       return stoi(x[i]);
    2124             :   }
    2125             :   return NULL;/*LCOV_EXCL_LINE*/
    2126             : }
    2127             : GEN
    2128        8425 : vecmin0(GEN x, GEN *pi)
    2129             : {
    2130        8425 :   long i, lx = lg(x), tx = typ(x);
    2131        8425 :   if (!is_matvec_t(tx) && tx != t_VECSMALL) return gcopy(x);
    2132        8411 :   if (lx==1) pari_err_DOMAIN("vecmin", "empty argument", "=", x,x);
    2133        8397 :   switch(typ(x))
    2134             :   {
    2135             :     case t_VEC: case t_COL:
    2136        8369 :       i = vecindexmin(x); if (pi) *pi = utoipos(i);
    2137        8369 :       return gcopy(gel(x,i));
    2138             :     case t_MAT: {
    2139          14 :       long j, i0 = 1, j0 = 1, lx2 = lgcols(x);
    2140             :       GEN s;
    2141          14 :       if (lx2 == 1) pari_err_DOMAIN("vecmin", "empty argument", "=", x,x);
    2142          14 :       s = gcoeff(x,i0,j0); i = 2;
    2143          42 :       for (j=1; j<lx; j++,i=1)
    2144             :       {
    2145          28 :         GEN c = gel(x,j);
    2146          70 :         for (; i<lx2; i++)
    2147          42 :           if (gcmp(gel(c,i),s) < 0) { s = gel(c,i); j0=j; i0=i; }
    2148             :       }
    2149          14 :       if (pi) *pi = mkvec2(utoipos(i0), utoipos(j0));
    2150          14 :       return gcopy(s);
    2151             :     }
    2152             :     case t_VECSMALL:
    2153          14 :       i = vecsmall_indexmin(x); if (pi) *pi = utoipos(i);
    2154          14 :       return stoi(x[i]);
    2155             :   }
    2156             :   return NULL;/*LCOV_EXCL_LINE*/
    2157             : }
    2158             : 
    2159             : GEN
    2160        2476 : vecmax(GEN x) { return vecmax0(x, NULL); }
    2161             : GEN
    2162        8348 : vecmin(GEN x) { return vecmin0(x, NULL); }
    2163             : 
    2164             : /*******************************************************************/
    2165             : /*                                                                 */
    2166             : /*                      AFFECT long --> GEN                        */
    2167             : /*         affect long s to GEN x. Useful for initialization.      */
    2168             : /*                                                                 */
    2169             : /*******************************************************************/
    2170             : 
    2171             : static void
    2172           0 : padicaff0(GEN x)
    2173             : {
    2174           0 :   if (signe(gel(x,4)))
    2175             :   {
    2176           0 :     x[1] = evalvalp(valp(x)+precp(x));
    2177           0 :     affsi(0,gel(x,4));
    2178             :   }
    2179           0 : }
    2180             : 
    2181             : void
    2182        1008 : gaffsg(long s, GEN x)
    2183             : {
    2184        1008 :   switch(typ(x))
    2185             :   {
    2186           0 :     case t_INT: affsi(s,x); break;
    2187        1008 :     case t_REAL: affsr(s,x); break;
    2188           0 :     case t_INTMOD: modsiz(s,gel(x,1),gel(x,2)); break;
    2189           0 :     case t_FRAC: affsi(s,gel(x,1)); affsi(1,gel(x,2)); break;
    2190           0 :     case t_COMPLEX: gaffsg(s,gel(x,1)); gaffsg(0,gel(x,2)); break;
    2191             :     case t_PADIC: {
    2192             :       long vx;
    2193             :       GEN y;
    2194           0 :       if (!s) { padicaff0(x); break; }
    2195           0 :       vx = Z_pvalrem(stoi(s), gel(x,2), &y);
    2196           0 :       setvalp(x,vx); modiiz(y,gel(x,3),gel(x,4));
    2197           0 :       break;
    2198             :     }
    2199           0 :     case t_QUAD: gaffsg(s,gel(x,2)); gaffsg(0,gel(x,3)); break;
    2200           0 :     default: pari_err_TYPE2("=",stoi(s),x);
    2201             :   }
    2202        1008 : }
    2203             : 
    2204             : /*******************************************************************/
    2205             : /*                                                                 */
    2206             : /*                     GENERIC AFFECTATION                         */
    2207             : /*         Affect the content of x to y, whenever possible         */
    2208             : /*                                                                 */
    2209             : /*******************************************************************/
    2210             : /* x PADIC, Y INT, return lift(x * Mod(1,Y)) */
    2211             : GEN
    2212        4193 : padic_to_Fp(GEN x, GEN Y) {
    2213        4193 :   pari_sp av = avma;
    2214        4193 :   GEN p = gel(x,2), z;
    2215        4193 :   long vy, vx = valp(x);
    2216        4193 :   if (!signe(Y)) pari_err_INV("padic_to_Fp",Y);
    2217        4193 :   vy = Z_pvalrem(Y,p, &z);
    2218        4193 :   if (vx < 0 || !gequal1(z)) pari_err_OP("",x, mkintmod(gen_1,Y));
    2219        4179 :   if (vx >= vy) { avma = av; return gen_0; }
    2220        3822 :   z = gel(x,4);
    2221        3822 :   if (!signe(z) || vy > vx + precp(x)) pari_err_OP("",x, mkintmod(gen_1,Y));
    2222        3822 :   if (vx) z = mulii(z, powiu(p,vx));
    2223        3822 :   return gerepileuptoint(av, remii(z, Y));
    2224             : }
    2225             : ulong
    2226          77 : padic_to_Fl(GEN x, ulong Y) {
    2227          77 :   GEN p = gel(x,2);
    2228             :   ulong u, z;
    2229          77 :   long vy, vx = valp(x);
    2230          77 :   vy = u_pvalrem(Y,p, &u);
    2231          77 :   if (vx < 0 || u != 1) pari_err_OP("",x, mkintmodu(1,Y));
    2232             :   /* Y = p^vy */
    2233          77 :   if (vx >= vy) return 0;
    2234          70 :   z = umodiu(gel(x,4), Y);
    2235          70 :   if (!z || vy > vx + precp(x)) pari_err_OP("",x, mkintmodu(1,Y));
    2236          70 :   if (vx) {
    2237           0 :     ulong pp = p[2];
    2238           0 :     z = Fl_mul(z, upowuu(pp,vx), Y); /* p^vx < p^vy = Y */
    2239             :   }
    2240          70 :   return z;
    2241             : }
    2242             : 
    2243             : static void
    2244           0 : croak(const char *s) {
    2245             :   char *t;
    2246           0 :   t = stack_sprintf("gaffect [overwriting universal object: %s]",s);
    2247           0 :   pari_err_BUG(t);
    2248           0 : }
    2249             : 
    2250             : void
    2251      245878 : gaffect(GEN x, GEN y)
    2252             : {
    2253      245878 :   long vx, i, lx, ly, tx = typ(x), ty = typ(y);
    2254             :   pari_sp av;
    2255             :   GEN p1, num, den;
    2256             : 
    2257      245878 :   if (tx == ty) switch(tx) {
    2258             :     case t_INT:
    2259      364685 :       if (!is_universal_constant(y)) { affii(x,y); return; }
    2260             :       /* y = gen_0, gnil, gen_1 or gen_2 */
    2261           0 :       if (y==gen_0)  croak("gen_0");
    2262           0 :       if (y==gen_1)  croak("gen_1");
    2263           0 :       if (y==gen_m1) croak("gen_m1");
    2264           0 :       if (y==gen_m2) croak("gen_m2");
    2265           0 :       if (y==gen_2)  croak("gen_2");
    2266           0 :       croak("gnil)");
    2267       51277 :     case t_REAL: affrr(x,y); return;
    2268             :     case t_INTMOD:
    2269           0 :       if (!dvdii(gel(x,1),gel(y,1))) pari_err_OP("",x,y);
    2270           0 :       modiiz(gel(x,2),gel(y,1),gel(y,2)); return;
    2271             :     case t_FRAC:
    2272           0 :       affii(gel(x,1),gel(y,1));
    2273           0 :       affii(gel(x,2),gel(y,2)); return;
    2274             :     case t_COMPLEX:
    2275        1673 :       gaffect(gel(x,1),gel(y,1));
    2276        1673 :       gaffect(gel(x,2),gel(y,2)); return;
    2277             :     case t_PADIC:
    2278           0 :       if (!equalii(gel(x,2),gel(y,2))) pari_err_OP("",x,y);
    2279           0 :       modiiz(gel(x,4),gel(y,3),gel(y,4));
    2280           0 :       setvalp(y,valp(x)); return;
    2281             :     case t_QUAD:
    2282           0 :       if (! ZX_equal(gel(x,1),gel(y,1))) pari_err_OP("",x,y);
    2283           0 :       affii(gel(x,2),gel(y,2));
    2284           0 :       affii(gel(x,3),gel(y,3)); return;
    2285             :     case t_VEC: case t_COL: case t_MAT:
    2286       72077 :       lx = lg(x); if (lx != lg(y)) pari_err_DIM("gaffect");
    2287       72077 :       for (i=1; i<lx; i++) gaffect(gel(x,i),gel(y,i));
    2288       72077 :       return;
    2289             :   }
    2290             : 
    2291             :   /* Various conversions. Avoid them, use specialized routines ! */
    2292             : 
    2293        1022 :   if (!is_const_t(ty)) pari_err_TYPE2("=",x,y);
    2294        1022 :   switch(tx)
    2295             :   {
    2296             :     case t_INT:
    2297           0 :       switch(ty)
    2298             :       {
    2299             :         case t_REAL:
    2300           0 :           affir(x,y); break;
    2301             : 
    2302             :         case t_INTMOD:
    2303           0 :           modiiz(x,gel(y,1),gel(y,2)); break;
    2304             : 
    2305             :         case t_COMPLEX:
    2306           0 :           gaffect(x,gel(y,1)); gaffsg(0,gel(y,2)); break;
    2307             : 
    2308             :         case t_PADIC:
    2309           0 :           if (!signe(x)) { padicaff0(y); break; }
    2310           0 :           av = avma;
    2311           0 :           setvalp(y, Z_pvalrem(x,gel(y,2),&p1));
    2312           0 :           affii(modii(p1,gel(y,3)), gel(y,4));
    2313           0 :           avma = av; break;
    2314             : 
    2315           0 :         case t_QUAD: gaffect(x,gel(y,2)); gaffsg(0,gel(y,3)); break;
    2316           0 :         default: pari_err_TYPE2("=",x,y);
    2317             :       }
    2318           0 :       break;
    2319             : 
    2320             :     case t_REAL:
    2321        1008 :       switch(ty)
    2322             :       {
    2323        1008 :         case t_COMPLEX: gaffect(x,gel(y,1)); gaffsg(0,gel(y,2)); break;
    2324           0 :         default: pari_err_TYPE2("=",x,y);
    2325             :       }
    2326        1008 :       break;
    2327             : 
    2328             :     case t_FRAC:
    2329          14 :       switch(ty)
    2330             :       {
    2331          14 :         case t_REAL: rdiviiz(gel(x,1),gel(x,2), y); break;
    2332           0 :         case t_INTMOD: av = avma;
    2333           0 :           p1 = Fp_inv(gel(x,2),gel(y,1));
    2334           0 :           affii(modii(mulii(gel(x,1),p1),gel(y,1)), gel(y,2));
    2335           0 :           avma = av; break;
    2336           0 :         case t_COMPLEX: gaffect(x,gel(y,1)); gaffsg(0,gel(y,2)); break;
    2337             :         case t_PADIC:
    2338           0 :           if (!signe(gel(x,1))) { padicaff0(y); break; }
    2339           0 :           num = gel(x,1);
    2340           0 :           den = gel(x,2);
    2341           0 :           av = avma; vx = Z_pvalrem(num, gel(y,2), &num);
    2342           0 :           if (!vx) vx = -Z_pvalrem(den,gel(y,2),&den);
    2343           0 :           setvalp(y,vx);
    2344           0 :           p1 = mulii(num,Fp_inv(den,gel(y,3)));
    2345           0 :           affii(modii(p1,gel(y,3)), gel(y,4)); avma = av; break;
    2346           0 :         case t_QUAD: gaffect(x,gel(y,2)); gaffsg(0,gel(y,3)); break;
    2347           0 :         default: pari_err_TYPE2("=",x,y);
    2348             :       }
    2349          14 :       break;
    2350             : 
    2351             :     case t_COMPLEX:
    2352           0 :       if (!gequal0(gel(x,2))) pari_err_TYPE2("=",x,y);
    2353           0 :       gaffect(gel(x,1), y);
    2354           0 :       break;
    2355             : 
    2356             :     case t_PADIC:
    2357           0 :       switch(ty)
    2358             :       {
    2359             :         case t_INTMOD:
    2360           0 :           av = avma; affii(padic_to_Fp(x, gel(y,1)), gel(y,2));
    2361           0 :           avma = av; break;
    2362           0 :         default: pari_err_TYPE2("=",x,y);
    2363             :       }
    2364           0 :       break;
    2365             : 
    2366             :     case t_QUAD:
    2367           0 :       switch(ty)
    2368             :       {
    2369             :         case t_INT: case t_INTMOD: case t_FRAC: case t_PADIC:
    2370           0 :           pari_err_TYPE2("=",x,y);
    2371             : 
    2372             :         case t_REAL:
    2373           0 :           av = avma; affgr(quadtofp(x,realprec(y)), y); avma = av; break;
    2374             :         case t_COMPLEX:
    2375           0 :           ly = precision(y); if (!ly) pari_err_TYPE2("=",x,y);
    2376           0 :           av = avma; gaffect(quadtofp(x,ly), y); avma = av; break;
    2377           0 :         default: pari_err_TYPE2("=",x,y);
    2378             :       }
    2379           0 :     default: pari_err_TYPE2("=",x,y);
    2380             :   }
    2381             : }
    2382             : 
    2383             : /*******************************************************************/
    2384             : /*                                                                 */
    2385             : /*           CONVERSION QUAD --> REAL, COMPLEX OR P-ADIC           */
    2386             : /*                                                                 */
    2387             : /*******************************************************************/
    2388             : GEN
    2389         112 : quadtofp(GEN x, long prec)
    2390             : {
    2391         112 :   GEN z, Q, u = gel(x,2), v = gel(x,3);
    2392             :   pari_sp av;
    2393         112 :   if (prec < LOWDEFAULTPREC) prec = LOWDEFAULTPREC;
    2394         112 :   if (isintzero(v)) return cxcompotor(u, prec);
    2395         112 :   av = avma; Q = gel(x,1);
    2396         112 :   z = itor(quad_disc(x), prec);
    2397         112 :   if (signe(gel(Q,2)) < 0) /* Q[2] = -D/4 or (1-D)/4 */
    2398             :   {
    2399         112 :     z = subri(sqrtr(z), gel(Q,3));
    2400         112 :     shiftr_inplace(z, -1);
    2401             :   }
    2402             :   else
    2403             :   {
    2404           0 :     z = sqrtr_abs(z); shiftr_inplace(z, -1);
    2405           0 :     z = mkcomplex(gmul2n(negi(gel(Q,3)),-1), z);
    2406             :   }/* z = (-b + sqrt(D)) / 2 */
    2407         112 :   return gerepileupto(av, gadd(u, gmul(v,z)));
    2408             : }
    2409             : 
    2410             : static GEN
    2411          14 : qtop(GEN x, GEN p, long d)
    2412             : {
    2413          14 :   GEN z, D, P, b, u = gel(x,2), v = gel(x,3);
    2414             :   pari_sp av;
    2415          14 :   if (gequal0(v)) return cvtop(u, p, d);
    2416          14 :   P = gel(x,1);
    2417          14 :   b = gel(P,3);
    2418          14 :   av = avma; D = quad_disc(x);
    2419          14 :   if (absequaliu(p,2)) d += 2;
    2420          14 :   z = Qp_sqrt(cvtop(D,p,d));
    2421          14 :   if (!z) pari_err_SQRTN("Qp_sqrt",D);
    2422           0 :   z = gmul2n(gsub(z, b), -1);
    2423             : 
    2424           0 :   z = gadd(u, gmul(v, z));
    2425           0 :   if (typ(z) != t_PADIC) /* t_INTMOD for t_QUAD of t_INTMODs... */
    2426           0 :     z = cvtop(z, p, d);
    2427           0 :   return gerepileupto(av, z);
    2428             : }
    2429             : static GEN
    2430          14 : ctop(GEN x, GEN p, long d)
    2431             : {
    2432          14 :   pari_sp av = avma;
    2433          14 :   GEN z, u = gel(x,1), v = gel(x,2);
    2434          14 :   if (isrationalzero(v)) return cvtop(u, p, d);
    2435          14 :   z = Qp_sqrt(cvtop(gen_m1, p, d - gvaluation(v, p))); /* = I */
    2436          14 :   if (!z) pari_err_SQRTN("Qp_sqrt",gen_m1);
    2437             : 
    2438          14 :   z = gadd(u, gmul(v, z));
    2439          14 :   if (typ(z) != t_PADIC) /* t_INTMOD for t_COMPLEX of t_INTMODs... */
    2440           0 :     z = cvtop(z, p, d);
    2441          14 :   return gerepileupto(av, z);
    2442             : }
    2443             : 
    2444             : /* cvtop2(stoi(s), y) */
    2445             : GEN
    2446           0 : cvstop2(long s, GEN y)
    2447             : {
    2448           0 :   GEN z, p = gel(y,2);
    2449           0 :   long v, d = signe(gel(y,4))? precp(y): 0;
    2450           0 :   if (!s) return zeropadic(p, d);
    2451           0 :   v = z_pvalrem(s, p, &s);
    2452           0 :   if (d <= 0) return zeropadic(p, v);
    2453           0 :   z = cgetg(5, t_PADIC);
    2454           0 :   z[1] = evalprecp(d) | evalvalp(v);
    2455           0 :   gel(z,2) = p;
    2456           0 :   gel(z,3) = gel(y,3);
    2457           0 :   gel(z,4) = modsi(s, gel(y,3)); return z;
    2458             : }
    2459             : 
    2460             : /* cvtop(x, gel(y,2), precp(y)), shallow */
    2461             : GEN
    2462      281394 : cvtop2(GEN x, GEN y)
    2463             : {
    2464      281394 :   GEN z, p = gel(y,2);
    2465      281394 :   long v, d = signe(gel(y,4))? precp(y): 0;
    2466      281394 :   switch(typ(x))
    2467             :   {
    2468             :     case t_INT:
    2469      249831 :       if (!signe(x)) return zeropadic(p, d);
    2470      249831 :       if (d <= 0) return zeropadic(p, Z_pval(x,p));
    2471      245274 :       v = Z_pvalrem(x, p, &x);
    2472      245281 :       z = cgetg(5, t_PADIC);
    2473      245288 :       z[1] = evalprecp(d) | evalvalp(v);
    2474      245288 :       gel(z,2) = p;
    2475      245288 :       gel(z,3) = gel(y,3);
    2476      245288 :       gel(z,4) = modii(x, gel(y,3)); return z;
    2477             : 
    2478             :     case t_INTMOD:
    2479           0 :       v = Z_pval(gel(x,1),p); if (v > d) v = d;
    2480           0 :       return cvtop(gel(x,2), p, v);
    2481             : 
    2482             :     case t_FRAC:
    2483             :     {
    2484             :       GEN num, den;
    2485       31542 :       if (d <= 0) return zeropadic(p, Q_pval(x,p));
    2486       30261 :       num = gel(x,1); v = Z_pvalrem(num, p, &num);
    2487       30261 :       den = gel(x,2); if (!v) v = -Z_pvalrem(den, p, &den);
    2488       30261 :       z = cgetg(5, t_PADIC);
    2489       30261 :       z[1] = evalprecp(d) | evalvalp(v);
    2490       30261 :       gel(z,2) = p;
    2491       30261 :       gel(z,3) = gel(y,3);
    2492       30261 :       if (!is_pm1(den)) num = mulii(num, Fp_inv(den, gel(y,3)));
    2493       30261 :       gel(z,4) = modii(num, gel(y,3)); return z;
    2494             :     }
    2495           7 :     case t_COMPLEX: return ctop(x, p, d);
    2496          14 :     case t_QUAD:    return qtop(x, p, d);
    2497             :   }
    2498           0 :   pari_err_TYPE("cvtop2",x);
    2499             :   return NULL; /* LCOV_EXCL_LINE */
    2500             : }
    2501             : 
    2502             : /* assume is_const_t(tx) */
    2503             : GEN
    2504       46791 : cvtop(GEN x, GEN p, long d)
    2505             : {
    2506             :   GEN z;
    2507             :   long v;
    2508             : 
    2509       46791 :   if (typ(p) != t_INT) pari_err_TYPE("cvtop",p);
    2510       46791 :   switch(typ(x))
    2511             :   {
    2512             :     case t_INT:
    2513       31916 :       if (!signe(x)) return zeropadic(p, d);
    2514       30740 :       if (d <= 0) return zeropadic(p, Z_pval(x,p));
    2515       30740 :       v = Z_pvalrem(x, p, &x);
    2516       30740 :       z = cgetg(5, t_PADIC);
    2517       30740 :       z[1] = evalprecp(d) | evalvalp(v);
    2518       30740 :       gel(z,2) = icopy(p);
    2519       30740 :       gel(z,3) = powiu(p, d);
    2520       30740 :       gel(z,4) = modii(x, gel(z,3)); return z; /* not memory-clean */
    2521             : 
    2522             :     case t_INTMOD:
    2523           0 :       v = Z_pval(gel(x,1),p); if (v > d) v = d;
    2524           0 :       return cvtop(gel(x,2), p, v);
    2525             : 
    2526             :     case t_FRAC:
    2527             :     {
    2528             :       GEN num, den;
    2529        7140 :       if (d <= 0) return zeropadic(p, Q_pval(x,p));
    2530        7140 :       num = gel(x,1); v = Z_pvalrem(num, p, &num);
    2531        7140 :       den = gel(x,2); if (!v) v = -Z_pvalrem(den, p, &den);
    2532        7140 :       z = cgetg(5, t_PADIC);
    2533        7140 :       z[1] = evalprecp(d) | evalvalp(v);
    2534        7140 :       gel(z,2) = icopy(p);
    2535        7140 :       gel(z,3) = powiu(p, d);
    2536        7140 :       if (!is_pm1(den)) num = mulii(num, Fp_inv(den, gel(z,3)));
    2537        7140 :       gel(z,4) = modii(num, gel(z,3)); return z; /* not memory-clean */
    2538             :     }
    2539           7 :     case t_COMPLEX: return ctop(x, p, d);
    2540             :     case t_PADIC:
    2541        7728 :       p = gel(x,2); /* override */
    2542        7728 :       if (!signe(gel(x,4))) return zeropadic(p, d);
    2543        7728 :       z = cgetg(5,t_PADIC);
    2544        7728 :       z[1] = x[1]; setprecp(z,d);
    2545        7728 :       gel(z,2) = icopy(p);
    2546        7728 :       gel(z,3) = powiu(p, d);
    2547        7728 :       gel(z,4) = modii(gel(x,4), gel(z,3)); return z;
    2548             : 
    2549           0 :     case t_QUAD: return qtop(x, p, d);
    2550             :   }
    2551           0 :   pari_err_TYPE("cvtop",x);
    2552             :   return NULL; /* LCOV_EXCL_LINE */
    2553             : }
    2554             : 
    2555             : GEN
    2556          28 : gcvtop(GEN x, GEN p, long r)
    2557             : {
    2558             :   long i, lx;
    2559             :   GEN y;
    2560             : 
    2561          28 :   switch(typ(x))
    2562             :   {
    2563             :     case t_POL: case t_SER:
    2564           7 :       y = cgetg_copy(x, &lx); y[1] = x[1];
    2565           7 :       for (i=2; i<lx; i++) gel(y,i) = gcvtop(gel(x,i),p,r);
    2566           7 :       return y;
    2567             :     case t_POLMOD: case t_RFRAC: case t_VEC: case t_COL: case t_MAT:
    2568           0 :       y = cgetg_copy(x, &lx);
    2569           0 :       for (i=1; i<lx; i++) gel(y,i) = gcvtop(gel(x,i),p,r);
    2570           0 :       return y;
    2571             :   }
    2572          21 :   return cvtop(x,p,r);
    2573             : }
    2574             : 
    2575             : long
    2576    86627473 : gexpo_safe(GEN x)
    2577             : {
    2578    86627473 :   long tx = typ(x), lx, e, f, i;
    2579             : 
    2580    86627473 :   switch(tx)
    2581             :   {
    2582             :     case t_INT:
    2583    22955477 :       return expi(x);
    2584             : 
    2585             :     case t_FRAC:
    2586      308286 :       return expi(gel(x,1)) - expi(gel(x,2));
    2587             : 
    2588             :     case t_REAL:
    2589    42195026 :       return expo(x);
    2590             : 
    2591             :     case t_COMPLEX:
    2592    12040974 :       e = gexpo(gel(x,1));
    2593    12040974 :       f = gexpo(gel(x,2)); return maxss(e, f);
    2594             : 
    2595             :     case t_QUAD: {
    2596          28 :       GEN p = gel(x,1); /* mod = X^2 + {0,1}* X - {D/4, (1-D)/4})*/
    2597          28 :       long d = 1 + expi(gel(p,2))/2; /* ~ expo(sqrt(D)) */
    2598          28 :       e = gexpo(gel(x,2));
    2599          28 :       f = gexpo(gel(x,3)) + d; return maxss(e, f);
    2600             :     }
    2601             :     case t_POL: case t_SER:
    2602     8875675 :       lx = lg(x); f = -(long)HIGHEXPOBIT;
    2603     8875675 :       for (i=2; i<lx; i++) { e=gexpo(gel(x,i)); if (e>f) f=e; }
    2604     8875675 :       return f;
    2605             :     case t_VEC: case t_COL: case t_MAT:
    2606      251930 :       lx = lg(x); f = -(long)HIGHEXPOBIT;
    2607      251930 :       for (i=1; i<lx; i++) { e=gexpo(gel(x,i)); if (e>f) f=e; }
    2608      251930 :       return f;
    2609             :   }
    2610          77 :   return -1-(long)HIGHEXPOBIT;
    2611             : }
    2612             : long
    2613    86591402 : gexpo(GEN x)
    2614             : {
    2615    86591402 :   long e = gexpo_safe(x);
    2616    86591402 :   if (e < -(long)HIGHEXPOBIT) pari_err_TYPE("gexpo",x);
    2617    86591395 :   return e;
    2618             : }
    2619             : GEN
    2620          63 : gpexponent(GEN x)
    2621             : {
    2622          63 :   long e = gexpo(x);
    2623          63 :   return e == -(long)HIGHEXPOBIT? mkmoo(): stoi(e);
    2624             : }
    2625             : 
    2626             : long
    2627           7 : sizedigit(GEN x)
    2628             : {
    2629           7 :   return gequal0(x)? 0: (long) ((gexpo(x)+1) * LOG10_2) + 1;
    2630             : }
    2631             : 
    2632             : /* normalize series. avma is not updated */
    2633             : GEN
    2634     5413946 : normalize(GEN x)
    2635             : {
    2636     5413946 :   long i, lx = lg(x), vx=varn(x), vp=valp(x);
    2637             :   GEN y, z;
    2638             : 
    2639     5413946 :   if (typ(x) != t_SER) pari_err_TYPE("normalize",x);
    2640     5413946 :   if (lx == 2) { setsigne(x,0); return x; }
    2641     5413554 :   if (lx == 3) {
    2642      102591 :     z = gel(x,2);
    2643      102591 :     if (!gequal0(z)) { setsigne(x,1); return x; }
    2644        4626 :     if (isrationalzero(z)) return zeroser(vx,vp+1);
    2645        1882 :     if (isexactzero(z)) {
    2646             :       /* dangerous case: already normalized ? */
    2647          21 :       if (!signe(x)) return x;
    2648          14 :       setvalp(x,vp+1); /* no: normalize */
    2649             :     }
    2650        1875 :     setsigne(x,0); return x;
    2651             :   }
    2652     5357230 :   for (i=2; i<lx; i++)
    2653     5354801 :     if (! isrationalzero(gel(x,i))) break;
    2654     5310963 :   if (i == lx) return zeroser(vx,lx-2+vp);
    2655     5308534 :   z = gel(x,i);
    2656     5308534 :   while (i<lx && isexactzero(gel(x,i))) i++;
    2657     5308534 :   if (i == lx)
    2658             :   {
    2659         245 :     i -= 3; y = x + i;
    2660         245 :     stackdummy((pari_sp)y, (pari_sp)x);
    2661         245 :     gel(y,2) = z;
    2662         245 :     y[1] = evalsigne(0) | evalvalp(lx-2+vp) | evalvarn(vx);
    2663         245 :     y[0] = evaltyp(t_SER) | _evallg(3);
    2664         245 :     return y;
    2665             :   }
    2666             : 
    2667     5308289 :   i -= 2; y = x + i; lx -= i;
    2668     5308289 :   y[1] = evalsigne(1) | evalvalp(vp+i) | evalvarn(vx);
    2669     5308289 :   y[0] = evaltyp(t_SER) | evallg(lx);
    2670             : 
    2671     5308289 :   stackdummy((pari_sp)y, (pari_sp)x);
    2672     5320522 :   for (i = 2; i < lx; i++)
    2673     5319915 :     if (!gequal0(gel(y, i))) return y;
    2674         607 :   setsigne(y, 0); return y;
    2675             : }
    2676             : 
    2677             : GEN
    2678       60942 : normalizepol_approx(GEN x, long lx)
    2679             : {
    2680             :   long i;
    2681       60942 :   for (i = lx-1; i>1; i--)
    2682       60942 :     if (! gequal0(gel(x,i))) break;
    2683       60942 :   stackdummy((pari_sp)(x + lg(x)), (pari_sp)(x + i+1));
    2684       60942 :   setlg(x, i+1); setsigne(x, i!=1); return x;
    2685             : }
    2686             : 
    2687             : GEN
    2688   181281289 : normalizepol_lg(GEN x, long lx)
    2689             : {
    2690   181281289 :   long i, LX = 0;
    2691   181281289 :   GEN KEEP = NULL;
    2692             : 
    2693   226342491 :   for (i = lx-1; i>1; i--)
    2694             :   {
    2695   208181853 :     GEN z = gel(x,i);
    2696   208181853 :     if (! gequal0(z) ) {
    2697   163121512 :       if (!LX) LX = i+1;
    2698   163121512 :       stackdummy((pari_sp)(x + lg(x)), (pari_sp)(x + LX));
    2699   163119243 :       x[0] = evaltyp(t_POL) | evallg(LX);
    2700   163117617 :       setsigne(x,1); return x;
    2701    45061205 :     } else if (!isexactzero(z)) {
    2702      259971 :       if (!LX) LX = i+1; /* to be kept as leading coeff */
    2703    44801231 :     } else if (!isrationalzero(z))
    2704      659693 :       KEEP = z; /* to be kept iff all other coeffs are exact 0s */
    2705             :   }
    2706    18160638 :   if (!LX) {
    2707    18118260 :     if (KEEP) { /* e.g. Pol(Mod(0,2)) */
    2708      369743 :       gel(x,2) = KEEP;
    2709      369743 :       LX = 3;
    2710             :     } else
    2711    17748517 :       LX = 2; /* Pol(0) */
    2712             :   }
    2713    18160638 :   stackdummy((pari_sp)(x + lg(x)), (pari_sp)(x + LX));
    2714    18160638 :   x[0] = evaltyp(t_POL) | evallg(LX);
    2715    18160638 :   setsigne(x,0); return x;
    2716             : }
    2717             : 
    2718             : /* normalize polynomial x in place */
    2719             : GEN
    2720      160671 : normalizepol(GEN x)
    2721             : {
    2722      160671 :   return normalizepol_lg(x, lg(x));
    2723             : }
    2724             : 
    2725             : int
    2726     3415515 : gsigne(GEN x)
    2727             : {
    2728     3415515 :   switch(typ(x))
    2729             :   {
    2730     3222339 :     case t_INT: case t_REAL: return signe(x);
    2731      190467 :     case t_FRAC: return signe(gel(x,1));
    2732             :     case t_QUAD:
    2733             :     {
    2734         112 :       pari_sp av = avma;
    2735         112 :       GEN T = gel(x,1), a = gel(x,2), b = gel(x,3);
    2736             :       long sa, sb;
    2737         112 :       if (signe(gel(T,2)) > 0) break;
    2738          98 :       a = gmul2n(a,1);
    2739          98 :       if (signe(gel(T,3))) a = gadd(a,b);
    2740             :       /* a + b sqrt(D) > 0 ? */
    2741          98 :       sa = gsigne(a);
    2742          98 :       sb = gsigne(b); if (sa == sb) { avma = av; return sa; }
    2743          77 :       if (sa == 0) { avma = av; return sb; }
    2744          70 :       if (sb == 0) { avma = av; return sa; }
    2745             :       /* different signs, take conjugate expression */
    2746          70 :       sb = gsigne(gsub(gsqr(a), gmul(quad_disc(x), gsqr(b))));
    2747          70 :       avma = av; return sb * sa;
    2748             :     }
    2749        2597 :     case t_INFINITY: return inf_get_sign(x);
    2750             :   }
    2751          14 :   pari_err_TYPE("gsigne",x);
    2752             :   return 0; /* LCOV_EXCL_LINE */
    2753             : }
    2754             : 
    2755             : /*******************************************************************/
    2756             : /*                                                                 */
    2757             : /*                              LISTS                              */
    2758             : /*                                                                 */
    2759             : /*******************************************************************/
    2760             : /* make sure L can hold l elements, at least doubling the previous max number
    2761             :  * of components. */
    2762             : static void
    2763      786023 : ensure_nb(GEN L, long l)
    2764             : {
    2765      786023 :   long nmax = list_nmax(L), i, lw;
    2766             :   GEN v, w;
    2767     1572046 :   if (l <= nmax) return;
    2768         322 :   if (nmax)
    2769             :   {
    2770         273 :     nmax <<= 1;
    2771         273 :     if (l > nmax) nmax = l;
    2772         273 :     w = list_data(L); lw = lg(w);
    2773         273 :     v = newblock(nmax+1);
    2774         273 :     v[0] = w[0];
    2775         273 :     for (i=1; i < lw; i++) gel(v,i) = gel(w, i);
    2776         273 :     killblock(w);
    2777             :   }
    2778             :   else /* unallocated */
    2779             :   {
    2780          49 :     nmax = 32;
    2781          49 :     if (list_data(L))
    2782           0 :       pari_err(e_MISC, "store list in variable before appending elements");
    2783          49 :     v = newblock(nmax+1);
    2784          49 :     v[0] = evaltyp(t_VEC) | _evallg(1);
    2785             :   }
    2786         322 :   list_data(L) = v;
    2787         322 :   L[1] = evaltyp(list_typ(L))|evallg(nmax);
    2788             : }
    2789             : 
    2790             : void
    2791           7 : listkill(GEN L)
    2792             : {
    2793             : 
    2794           7 :   if (typ(L) != t_LIST) pari_err_TYPE("listkill",L);
    2795           7 :   if (list_nmax(L)) {
    2796           7 :     GEN v = list_data(L);
    2797           7 :     long i, l = lg(v);
    2798           7 :     for (i=1; i<l; i++) gunclone_deep(gel(v,i));
    2799           7 :     killblock(v);
    2800           7 :     L[1] = evaltyp(list_typ(L));
    2801           7 :     list_data(L) = NULL;
    2802             :   }
    2803           7 : }
    2804             : 
    2805             : GEN
    2806         787 : mklist_typ(long t)
    2807             : {
    2808         787 :   GEN L = cgetg(3,t_LIST);
    2809         787 :   L[1] = evaltyp(t);
    2810         787 :   list_data(L) = NULL; return L;
    2811             : }
    2812             : 
    2813             : GEN
    2814         745 : mklist(void)
    2815             : {
    2816         745 :   return mklist_typ(t_LIST_RAW);
    2817             : }
    2818             : 
    2819             : GEN
    2820          35 : mkmap(void)
    2821             : {
    2822          35 :   return mklist_typ(t_LIST_MAP);
    2823             : }
    2824             : 
    2825             : /* return a list with single element x, allocated on stack */
    2826             : GEN
    2827          49 : mklistcopy(GEN x)
    2828             : {
    2829          49 :   GEN y = mklist();
    2830          49 :   list_data(y) = mkveccopy(x);
    2831          49 :   return y;
    2832             : }
    2833             : 
    2834             : GEN
    2835           7 : listcreate_gp(long n)
    2836             : {
    2837           7 :   (void) n; return mklist();
    2838             : }
    2839             : 
    2840             : GEN
    2841      751051 : listput(GEN L, GEN x, long index)
    2842             : {
    2843             :   long l;
    2844             :   GEN z;
    2845             : 
    2846      751051 :   if (index < 0) pari_err_COMPONENT("listput", "<", gen_0, stoi(index));
    2847      751044 :   z = list_data(L);
    2848      751044 :   l = z? lg(z): 1;
    2849             : 
    2850      751044 :   x = gclone(x);
    2851      751044 :   if (!index || index >= l)
    2852             :   {
    2853      751023 :     ensure_nb(L, l);
    2854      751023 :     z = list_data(L); /* it may change ! */
    2855      751023 :     index = l;
    2856      751023 :     l++;
    2857             :   } else
    2858          21 :     gunclone_deep( gel(z, index) );
    2859      751044 :   gel(z,index) = x;
    2860      751044 :   z[0] = evaltyp(t_VEC) | evallg(l); /*must be after gel(z,index) is set*/
    2861      751044 :   return gel(z,index);
    2862             : }
    2863             : 
    2864             : GEN
    2865      700049 : listput0(GEN L, GEN x, long index)
    2866             : {
    2867      700049 :   if (typ(L) != t_LIST || list_typ(L) != t_LIST_RAW)
    2868           0 :     pari_err_TYPE("listput",L);
    2869      700049 :   return listput(L, x, index);
    2870             : }
    2871             : 
    2872             : GEN
    2873       35014 : listinsert(GEN L, GEN x, long index)
    2874             : {
    2875             :   long l, i;
    2876             :   GEN z;
    2877             : 
    2878       35014 :   if (typ(L) != t_LIST || list_typ(L) != t_LIST_RAW)
    2879           0 :     pari_err_TYPE("listinsert",L);
    2880       35014 :   z = list_data(L); l = z? lg(z): 1;
    2881       35014 :   if (index <= 0) pari_err_COMPONENT("listinsert", "<=", gen_0, stoi(index));
    2882       35007 :   if (index > l) pari_err_COMPONENT("listinsert", ">", stoi(l), stoi(index));
    2883       35000 :   ensure_nb(L, l);
    2884       35000 :   BLOCK_SIGINT_START
    2885       35000 :   z = list_data(L);
    2886       35000 :   for (i=l; i > index; i--) gel(z,i) = gel(z,i-1);
    2887       35000 :   z[0] = evaltyp(t_VEC) | evallg(l+1);
    2888       35000 :   gel(z,index) = gclone(x);
    2889       35000 :   BLOCK_SIGINT_END
    2890       35000 :   return gel(z,index);
    2891             : }
    2892             : 
    2893             : void
    2894       21910 : listpop(GEN L, long index)
    2895             : {
    2896             :   long l, i;
    2897             :   GEN z;
    2898             : 
    2899       21910 :   if (typ(L) != t_LIST) pari_err_TYPE("listinsert",L);
    2900       21910 :   if (index < 0) pari_err_COMPONENT("listpop", "<", gen_0, stoi(index));
    2901       21910 :   z = list_data(L);
    2902       43820 :   if (!z || (l = lg(z)-1) == 0) return;
    2903             : 
    2904       21896 :   if (!index || index > l) index = l;
    2905       21896 :   BLOCK_SIGINT_START
    2906       21896 :   gunclone_deep( gel(z, index) );
    2907       21896 :   z[0] = evaltyp(t_VEC) | evallg(l);
    2908       21896 :   for (i=index; i < l; i++) z[i] = z[i+1];
    2909       21896 :   BLOCK_SIGINT_END
    2910             : }
    2911             : 
    2912             : void
    2913          35 : listpop0(GEN L, long index)
    2914             : {
    2915          35 :   if (typ(L) != t_LIST || list_typ(L) != t_LIST_RAW)
    2916           0 :     pari_err_TYPE("listpop",L);
    2917          35 :   listpop(L, index);
    2918          35 : }
    2919             : 
    2920             : /* return a copy fully allocated on stack. gclone from changevalue is
    2921             :  * supposed to malloc() it */
    2922             : GEN
    2923         418 : gtolist(GEN x)
    2924             : {
    2925             :   GEN y;
    2926             : 
    2927         418 :   if (!x) return mklist();
    2928         287 :   switch(typ(x))
    2929             :   {
    2930             :     case t_VEC: case t_COL:
    2931         238 :       y = mklist();
    2932         238 :       if (lg(x) == 1) return y;
    2933         224 :       list_data(y) = gcopy(x);
    2934         224 :       settyp(list_data(y), t_VEC);
    2935         224 :       return y;
    2936             :     case t_LIST:
    2937           0 :       y = mklist();
    2938           0 :       list_data(y) = list_data(x)? gcopy(list_data(x)): NULL;
    2939           0 :       return y;
    2940             :     default:
    2941          49 :       return mklistcopy(x);
    2942             :   }
    2943             : }
    2944             : 
    2945             : void
    2946          21 : listsort(GEN L, long flag)
    2947             : {
    2948             :   long i, l;
    2949          21 :   pari_sp av = avma;
    2950             :   GEN perm, v, vnew;
    2951             : 
    2952          21 :   if (typ(L) != t_LIST) pari_err_TYPE("listsort",L);
    2953          21 :   v = list_data(L); l = v? lg(v): 1;
    2954          42 :   if (l < 3) return;
    2955          21 :   if (flag)
    2956             :   {
    2957             :     long lnew;
    2958          14 :     perm = gen_indexsort_uniq(L, (void*)&cmp_universal, cmp_nodata);
    2959          14 :     lnew = lg(perm); /* may have changed since 'uniq' */
    2960          14 :     vnew = cgetg(lnew,t_VEC);
    2961          56 :     for (i=1; i<lnew; i++) {
    2962          42 :       long c = perm[i];
    2963          42 :       gel(vnew,i) = gel(v,c);
    2964          42 :       gel(v,c) = NULL;
    2965             :     }
    2966          14 :     if (l != lnew) { /* was shortened */
    2967         105 :       for (i=1; i<l; i++)
    2968          91 :         if (gel(v,i)) gunclone_deep(gel(v,i));
    2969          14 :       l = lnew;
    2970             :     }
    2971             :   }
    2972             :   else
    2973             :   {
    2974           7 :     perm = gen_indexsort(L, (void*)&cmp_universal, cmp_nodata);
    2975           7 :     vnew = cgetg(l,t_VEC);
    2976           7 :     for (i=1; i<l; i++) gel(vnew,i) = gel(v,perm[i]);
    2977             :   }
    2978          21 :   for (i=1; i<l; i++) gel(v,i) = gel(vnew,i);
    2979          21 :   v[0] = vnew[0]; avma = av;
    2980             : }

Generated by: LCOV version 1.11