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 20296-0a10b35) Lines: 1346 1536 87.6 %
Date: 2017-02-26 05:50:47 Functions: 137 148 92.6 %
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     3687719 : map_proto_lG(long (*f)(GEN), GEN x)
      43             : {
      44     3687719 :   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     3794454 :   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       67891 : _domul(void *data, GEN x, GEN y)
      69             : {
      70       67891 :   GEN (*mul)(GEN,GEN)=(GEN (*)(GEN,GEN)) data;
      71       67891 :   return mul(x,y);
      72             : }
      73             : 
      74             : GEN
      75      105040 : gassoc_proto(GEN (*f)(GEN,GEN), GEN x, GEN y)
      76             : {
      77      105040 :   if (!y)
      78             :   {
      79      105040 :     pari_sp av = avma;
      80      105040 :     switch(typ(x))
      81             :     {
      82             :       case t_LIST:
      83          21 :         x = list_data(x); if (!x) return gen_1;
      84             :       case t_VEC:
      85      105026 :       case t_COL: break;
      86           7 :       default: pari_err_TYPE("association",x);
      87             :     }
      88      105026 :     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     1532948 : cgetp(GEN x)
     100             : {
     101     1532948 :   GEN y = cgetg(5,t_PADIC);
     102     1532953 :   y[1] = (x[1]&PRECPBITS) | _evalvalp(0);
     103     1532953 :   gel(y,2) = icopy(gel(x,2));
     104     1532954 :   gel(y,3) = icopy(gel(x,3));
     105     1532954 :   gel(y,4) = cgeti(lgefint(gel(x,3))); return y;
     106             : }
     107             : 
     108             : /*******************************************************************/
     109             : /*                                                                 */
     110             : /*                            SIZES                                */
     111             : /*                                                                 */
     112             : /*******************************************************************/
     113             : 
     114             : long
     115     4459898 : glength(GEN x)
     116             : {
     117     4459898 :   long tx = typ(x);
     118     4459898 :   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           7 :     case t_STR:  return strlen( GSTR(x) );
     127        5028 :     case t_VECSMALL: return lg(x)-1;
     128             :   }
     129     4454744 :   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     1311678 : greffe_aux(GEN x, long l, long lx, long v)
     153             : {
     154     1311678 :   GEN y = cgetg(l,t_SER);
     155             :   long i;
     156     1311678 :   if (l <= 2) pari_err_BUG("RgX_to_ser (l <= 2)");
     157     1311678 :   y[1] = x[1]; setvalp(y, v);
     158     1311678 :   x += v; lx -= v;
     159     1311678 :   if (lx > l) {
     160      201368 :     for (i = 2; i < l; i++) gel(y,i) = gel(x,i);
     161             :   } else {
     162     1110310 :     for (i = 2; i <lx; i++) gel(y,i) = gel(x,i);
     163     1110310 :     for (     ; i < l; i++) gel(y,i) = gen_0;
     164             :   }
     165     1311678 :   return normalize(y);
     166             : }
     167             : /* enlarge/truncate t_POL x to a t_SER with lg l */
     168             : GEN
     169      971841 : RgX_to_ser(GEN x, long l)
     170             : {
     171      971841 :   if (lg(x) == 2) return zeroser(varn(x), l-2);
     172      971834 :   return greffe_aux(x, l, lg(x), RgX_val(x));
     173             : }
     174             : GEN
     175      339844 : RgX_to_ser_inexact(GEN x, long l)
     176             : {
     177      339844 :   long i, lx = lg(x);
     178      339844 :   int first = 1;
     179             :   /* analogous to RgX_valrem + normalize */
     180      339844 :   if (lx == 2) return zeroser(varn(x), l-2);
     181      339844 :   i = 2;
     182      685449 :   while (i<lx && gequal0(gel(x,i))) {
     183        5761 :     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        5761 :     i++;
     189             :   }
     190      339844 :   return greffe_aux(x, l, lx, i - 2);
     191             : }
     192             : GEN
     193         133 : rfrac_to_ser(GEN x, long l)
     194             : {
     195         133 :   return gdiv(gel(x,1), RgX_to_ser(gel(x,2), l));
     196             : }
     197             : 
     198             : /* R(1/x) + O((1/x)^(l-2)) */
     199             : GEN
     200         112 : rfracrecip_to_ser_absolute(GEN R, long l)
     201             : {
     202         112 :   GEN n = gel(R,1), d = gel(R,2);
     203         112 :   long N = l-2, 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 :   N -= v;
     219         112 :   R = gdiv(n, RgX_to_ser(d, l));
     220         112 :   setvalp(R, valp(R) + degpol(d)-dn-v);
     221         112 :   return R;
     222             : }
     223             : /*******************************************************************/
     224             : /*                                                                 */
     225             : /*                 CONVERSION GEN --> long                         */
     226             : /*                                                                 */
     227             : /*******************************************************************/
     228             : 
     229             : long
     230          77 : gtolong(GEN x)
     231             : {
     232          77 :   switch(typ(x))
     233             :   {
     234             :     case t_INT:
     235          42 :       return itos(x);
     236             :     case t_REAL:
     237           7 :       return (long)(rtodbl(x) + 0.5);
     238             :     case t_FRAC: {
     239           7 :       pari_sp av = avma;
     240           7 :       long y = itos(ground(x));
     241           7 :       avma = av; return y;
     242             :     }
     243             :     case t_COMPLEX:
     244           7 :       if (gequal0(gel(x,2))) return gtolong(gel(x,1)); break;
     245             :     case t_QUAD:
     246           7 :       if (gequal0(gel(x,3))) return gtolong(gel(x,2)); break;
     247             :   }
     248           7 :   pari_err_TYPE("gtolong",x);
     249             :   return 0; /* LCOV_EXCL_LINE */
     250             : }
     251             : 
     252             : /*******************************************************************/
     253             : /*                                                                 */
     254             : /*                         COMPARISONS                             */
     255             : /*                                                                 */
     256             : /*******************************************************************/
     257             : int
     258   201634326 : isexactzero(GEN g)
     259             : {
     260             :   long i, lx;
     261   201634326 :   switch (typ(g))
     262             :   {
     263             :     case t_INT:
     264   151866277 :       return !signe(g);
     265             :     case t_INTMOD:
     266      784048 :       return !signe(gel(g,2));
     267             :     case t_COMPLEX:
     268     1413008 :       return isexactzero(gel(g,1)) && isexactzero(gel(g,2));
     269             :     case t_FFELT:
     270     8047876 :       return FF_equal0(g);
     271             :     case t_QUAD:
     272         371 :       return isexactzero(gel(g,2)) && isexactzero(gel(g,3));
     273             :     case t_POLMOD:
     274       73454 :       return isexactzero(gel(g,2));
     275             :     case t_POL:
     276    28961094 :       lx = lg(g); /* cater for Mod(0,2)*x^0 */
     277    28961094 :       return lx == 2 || (lx == 3 && isexactzero(gel(g,2)));
     278             :     case t_RFRAC:
     279      458193 :       return isexactzero(gel(g,1)); /* may occur: Mod(0,2)/x */
     280             :     case t_VEC: case t_COL: case t_MAT:
     281         203 :       for (i=lg(g)-1; i; i--)
     282         154 :         if (!isexactzero(gel(g,i))) return 0;
     283          49 :       return 1;
     284             :   }
     285    10029942 :   return 0;
     286             : }
     287             : GEN
     288    43259782 : gisexactzero(GEN g)
     289             : {
     290             :   long i, lx;
     291             :   GEN a, b;
     292    43259782 :   switch (typ(g))
     293             :   {
     294             :     case t_INT:
     295    15892358 :       return !signe(g)? g: NULL;
     296             :     case t_INTMOD:
     297       10486 :       return !signe(gel(g,2))? g: NULL;
     298             :     case t_COMPLEX:
     299          77 :       a = gisexactzero(gel(g,1)); if (!a) return NULL;
     300          49 :       b = gisexactzero(gel(g,2)); if (!b) return NULL;
     301           0 :       return ggcd(a,b);
     302             :     case t_FFELT:
     303       20657 :       return FF_equal0(g)? g: NULL;
     304             :     case t_QUAD:
     305         518 :       a = gisexactzero(gel(g,2)); if (!a) return NULL;
     306          77 :       b = gisexactzero(gel(g,3)); if (!b) return NULL;
     307           7 :       return ggcd(a,b);
     308             :     case t_POLMOD:
     309       25417 :       return gisexactzero(gel(g,2));
     310             :     case t_POL:
     311    26074720 :       lx = lg(g); /* cater for Mod(0,2)*x^0 */
     312    26074720 :       if (lx == 2) return gen_0;
     313    20930718 :       if (lx == 3) return gisexactzero(gel(g,2));
     314    19071610 :       return NULL;
     315             :     case t_RFRAC:
     316     1193732 :       return gisexactzero(gel(g,1)); /* may occur: Mod(0,2)/x */
     317             :     case t_VEC: case t_COL: case t_MAT:
     318           0 :       a = gen_0;
     319           0 :       for (i=lg(g)-1; i; i--)
     320             :       {
     321           0 :         b = gisexactzero(gel(g,i));
     322           0 :         if (!b) return NULL;
     323           0 :         a = ggcd(a, b);
     324             :       }
     325           0 :       return a;
     326             :   }
     327       41817 :   return NULL;
     328             : }
     329             : 
     330             : int
     331   279234580 : isrationalzero(GEN g)
     332             : {
     333             :   long i;
     334   279234580 :   switch (typ(g))
     335             :   {
     336             :     case t_INT:
     337   197651888 :       return !signe(g);
     338             :     case t_COMPLEX:
     339     2776451 :       return isintzero(gel(g,1)) && isintzero(gel(g,2));
     340             :     case t_QUAD:
     341         798 :       return isintzero(gel(g,2)) && isintzero(gel(g,3));
     342             :     case t_POLMOD:
     343      549193 :       return isrationalzero(gel(g,2));
     344    36709720 :     case t_POL: return lg(g) == 2;
     345             :     case t_VEC: case t_COL: case t_MAT:
     346         105 :       for (i=lg(g)-1; i; i--)
     347          70 :         if (!isrationalzero(gel(g,i))) return 0;
     348          35 :       return 1;
     349             :   }
     350    41546495 :   return 0;
     351             : }
     352             : 
     353             : int
     354   400062524 : gequal0(GEN x)
     355             : {
     356   400062524 :   switch(typ(x))
     357             :   {
     358             :     case t_INT: case t_REAL: case t_POL: case t_SER:
     359   376983939 :       return !signe(x);
     360             : 
     361             :     case t_INTMOD:
     362     1315942 :       return !signe(gel(x,2));
     363             : 
     364             :     case t_FFELT:
     365      715116 :       return FF_equal0(x);
     366             : 
     367             :     case t_COMPLEX:
     368             :      /* is 0 iff norm(x) would be 0 (can happen with Re(x) and Im(x) != 0
     369             :       * only if Re(x) and Im(x) are of type t_REAL). See mp.c:addrr().
     370             :       */
     371     5256668 :       if (gequal0(gel(x,1)))
     372             :       {
     373      283271 :         if (gequal0(gel(x,2))) return 1;
     374      168019 :         if (typ(gel(x,1))!=t_REAL || typ(gel(x,2))!=t_REAL) return 0;
     375       19120 :         return (expo(gel(x,1))>=expo(gel(x,2)));
     376             :       }
     377     4973397 :       if (gequal0(gel(x,2)))
     378             :       {
     379      198891 :         if (typ(gel(x,1))!=t_REAL || typ(gel(x,2))!=t_REAL) return 0;
     380      143549 :         return (expo(gel(x,2))>=expo(gel(x,1)));
     381             :       }
     382     4774506 :       return 0;
     383             : 
     384             :     case t_PADIC:
     385      322310 :       return !signe(gel(x,4));
     386             : 
     387             :     case t_QUAD:
     388         917 :       return gequal0(gel(x,2)) && gequal0(gel(x,3));
     389             : 
     390             :     case t_POLMOD:
     391      644186 :       return gequal0(gel(x,2));
     392             : 
     393             :     case t_RFRAC:
     394     6008348 :       return gequal0(gel(x,1));
     395             : 
     396             :     case t_VEC: case t_COL: case t_MAT:
     397             :     {
     398             :       long i;
     399     3063887 :       for (i=lg(x)-1; i; i--)
     400     2785222 :         if (!gequal0(gel(x,i))) return 0;
     401      278665 :       return 1;
     402             :     }
     403             :   }
     404     7888168 :   return 0;
     405             : }
     406             : 
     407             : /* x a t_POL or t_SER, considered as having valuation v; let X(t) = t^(-v) x(t)
     408             :  * return 1 (true) if coeff(X,i) = 0 for all i != 0 and test(coeff(X, 0))
     409             :  * is true. Return 0 (false) otherwise, or if x == 0 */
     410             : static int
     411    13077082 : is_monomial_test(GEN x, long v, int(*test)(GEN))
     412             : {
     413             :   long d, i, l;
     414    13077082 :   if (!signe(x)) return (typ(x) == t_SER && v <= 0);
     415    13014244 :   if (v > 0) return 0;
     416    13014230 :   l = lg(x); d = 2-v;
     417    13014230 :   if (l <= d) return 0;
     418             :   /* 2 <= d < l */
     419    13014230 :   if (!test(gel(x,d))) return 0;
     420     3996863 :   for (i = 2; i < d; i++)
     421          14 :     if (!gequal0(gel(x,i))) return 0;
     422     4412353 :   for (i = d+1; i < l; i++)
     423     1969623 :     if (!gequal0(gel(x,i))) return 0;
     424     2442730 :   return 1;
     425             : }
     426             : static int
     427          84 : col_test(GEN x, int(*test)(GEN))
     428             : {
     429          84 :   long i, l = lg(x);
     430          84 :   if (l == 1 || !test(gel(x,1))) return 0;
     431          42 :   for (i = 2; i < l; i++)
     432          21 :     if (!gequal0(gel(x,i))) return 0;
     433          21 :   return 1;
     434             : }
     435             : static int
     436          98 : mat_test(GEN x, int(*test)(GEN))
     437             : {
     438          98 :   long i, j, l = lg(x);
     439          98 :   if (l == 1) return 1;
     440          84 :   if (l != lgcols(x)) return 0;
     441         126 :   for (i = 1; i < l; i++)
     442         196 :     for (j = 1; j < l; j++)
     443         154 :       if (i == j) {
     444         105 :         if (!test(gcoeff(x,i,i))) return 0;
     445             :       } else {
     446          49 :         if (!gequal0(gcoeff(x,i,j))) return 0;
     447             :       }
     448          21 :   return 1;
     449             : }
     450             : 
     451             : /* returns 1 whenever x = 1, and 0 otherwise */
     452             : int
     453   148010036 : gequal1(GEN x)
     454             : {
     455   148010036 :   switch(typ(x))
     456             :   {
     457             :     case t_INT:
     458   132550487 :       return equali1(x);
     459             : 
     460             :     case t_REAL:
     461             :     {
     462      814976 :       long s = signe(x);
     463      814976 :       if (!s) return expo(x) >= 0;
     464      814906 :       return s > 0 ? absrnz_equal1(x): 0;
     465             :     }
     466             :     case t_INTMOD:
     467        1239 :       return is_pm1(gel(x,2)) || is_pm1(gel(x,1));
     468             :     case t_POLMOD:
     469      290559 :       return gequal1(gel(x,2)) || gequal1(gel(x,1));
     470             : 
     471             :     case t_FFELT:
     472        4690 :       return FF_equal1(x);
     473             : 
     474             :     case t_FRAC:
     475      162835 :       return 0;
     476             : 
     477             :     case t_COMPLEX:
     478       69354 :       return gequal1(gel(x,1)) && gequal0(gel(x,2));
     479             : 
     480             :     case t_PADIC:
     481        8995 :       return !valp(x) && gequal1(gel(x,4));
     482             : 
     483             :     case t_QUAD:
     484          35 :       return gequal1(gel(x,2)) && gequal0(gel(x,3));
     485             : 
     486    13074919 :     case t_POL: return is_monomial_test(x, 0, &gequal1);
     487          91 :     case t_SER: return is_monomial_test(x, valp(x), &gequal1);
     488             : 
     489     1031751 :     case t_RFRAC: return gequal(gel(x,1), gel(x,2));
     490          42 :     case t_COL: return col_test(x, &gequal1);
     491          49 :     case t_MAT: return mat_test(x, &gequal1);
     492             :   }
     493          14 :   return 0;
     494             : }
     495             : 
     496             : /* returns 1 whenever the x = -1, 0 otherwise */
     497             : int
     498     1167356 : gequalm1(GEN x)
     499             : {
     500             :   pari_sp av;
     501             :   long y;
     502             :   GEN p1;
     503             : 
     504     1167356 :   switch(typ(x))
     505             :   {
     506             :     case t_INT:
     507      292113 :       return equalim1(x);
     508             : 
     509             :     case t_REAL:
     510             :     {
     511      810268 :       long s = signe(x);
     512      810268 :       if (!s) return expo(x) >= 0;
     513      810268 :       return s < 0 ? absrnz_equal1(x): 0;
     514             :     }
     515             :     case t_INTMOD:
     516          21 :       av=avma; y=equalii(addui(1,gel(x,2)), gel(x,1)); avma=av; return y;
     517             : 
     518             :     case t_FRAC:
     519          14 :       return 0;
     520             : 
     521             :     case t_FFELT:
     522          42 :       return FF_equalm1(x);
     523             : 
     524             :     case t_COMPLEX:
     525       62651 :       return gequalm1(gel(x,1)) && gequal0(gel(x,2));
     526             : 
     527             :     case t_QUAD:
     528           7 :       return gequalm1(gel(x,2)) && gequal0(gel(x,3));
     529             : 
     530             :     case t_PADIC:
     531           7 :       av=avma; y=equalii(addui(1,gel(x,4)), gel(x,3)); avma=av; return y;
     532             : 
     533             :     case t_POLMOD:
     534          35 :       av=avma; p1 = gaddgs(gel(x,2), 1);
     535          35 :       y = gequal0(p1) || gequal(p1,gel(x,1)); avma=av; return y;
     536             : 
     537        1995 :     case t_POL: return is_monomial_test(x, 0, &gequalm1);
     538          77 :     case t_SER: return is_monomial_test(x, valp(x), &gequalm1);
     539             : 
     540             :     case t_RFRAC:
     541          21 :       av=avma; y=gequal(gel(x,1), gneg_i(gel(x,2))); avma=av; return y;
     542          42 :     case t_COL: return col_test(x, &gequalm1);
     543          49 :     case t_MAT: return mat_test(x, &gequalm1);
     544             :   }
     545          14 :   return 0;
     546             : }
     547             : 
     548             : int
     549     2466331 : gequalX(GEN x) { return typ(x) == t_POL && lg(x) == 4
     550     1633968 :                       && isintzero(gel(x,2)) && isint1(gel(x,3)); }
     551             : 
     552             : static int
     553         476 : cmp_str(const char *x, const char *y)
     554             : {
     555         476 :   int f = strcmp(x, y);
     556         476 :   return f > 0? 1
     557         476 :               : f? -1: 0;
     558             : }
     559             : 
     560             : static int
     561    26005371 : cmp_universal_rec(GEN x, GEN y, long i0)
     562             : {
     563    26005371 :   long i, lx = lg(x), ly = lg(y);
     564    26005371 :   if (lx < ly) return -1;
     565    26004363 :   if (lx > ly) return 1;
     566    38984344 :   for (i = i0; i < lx; i++)
     567             :   {
     568    33313168 :     int f = cmp_universal(gel(x,i), gel(y,i));
     569    33313168 :     if (f) return f;
     570             :   }
     571     5671176 :   return 0;
     572             : }
     573             : /* Universal "meaningless" comparison function. Transitive, returns 0 iff
     574             :  * gidentical(x,y) */
     575             : int
     576    45715012 : cmp_universal(GEN x, GEN y)
     577             : {
     578    45715012 :   long lx, ly, i, tx = typ(x), ty = typ(y);
     579             : 
     580    45715012 :   if (tx < ty) return -1;
     581    45709843 :   if (ty < tx) return 1;
     582    45705860 :   switch(tx)
     583             :   {
     584    18760214 :     case t_INT: return cmpii(x,y);
     585         455 :     case t_STR: return cmp_str(GSTR(x),GSTR(y));
     586             :     case t_REAL:
     587             :     case t_VECSMALL:
     588      939764 :       lx = lg(x);
     589      939764 :       ly = lg(y);
     590      939764 :       if (lx < ly) return -1;
     591      888335 :       if (lx > ly) return 1;
     592     3580802 :       for (i = 1; i < lx; i++)
     593             :       {
     594     3473163 :         if (x[i] < y[i]) return -1;
     595     3088709 :         if (x[i] > y[i]) return 1;
     596             :       }
     597      107639 :       return 0;
     598             : 
     599             :     case t_POL:
     600             :     case t_SER:
     601             :     case t_FFELT:
     602             :     case t_CLOSURE:
     603      899213 :       if (x[1] < y[1]) return -1;
     604      899171 :       if (x[1] > y[1]) return 1;
     605      899157 :       return cmp_universal_rec(x, y, 2);
     606             : 
     607             :     case t_LIST:
     608             :       {
     609          21 :         long tx = list_typ(x), ty = list_typ(y);
     610             :         GEN vx, vy;
     611          21 :         if (tx < ty) return -1;
     612          21 :         if (tx > ty) return 1;
     613          21 :         vx = list_data(x);
     614          21 :         vy = list_data(y);
     615          21 :         if (!vx) return vy? -1: 0;
     616          21 :         if (!vy) return 1;
     617          21 :         switch (tx)
     618             :         {
     619             :         case t_LIST_MAP:
     620             :           {
     621           0 :             pari_sp av = avma;
     622           0 :             int ret = cmp_universal_rec(maptomat_shallow(x), maptomat_shallow(y),1);
     623           0 :             avma = av; return ret;
     624             :           }
     625             :         default:
     626          21 :           return cmp_universal_rec(vx, vy, 1);
     627             :         }
     628             :       }
     629             :     default:
     630    25106193 :       return cmp_universal_rec(x, y, lontyp[tx]);
     631             :   }
     632             : }
     633             : 
     634             : static int
     635       39965 : cmpfrac(GEN x, GEN y)
     636             : {
     637       39965 :   pari_sp av = avma;
     638       39965 :   GEN a = gel(x,1), b = gel(x,2);
     639       39965 :   GEN c = gel(y,1), d = gel(y,2);
     640       39965 :   int r = cmpii(mulii(a, d), mulii(b, c));
     641       39965 :   avma = av; return r;
     642             : }
     643             : static int
     644       11431 : cmpifrac(GEN a, GEN y)
     645             : {
     646       11431 :   pari_sp av = avma;
     647       11431 :   GEN c = gel(y,1), d = gel(y,2);
     648       11431 :   int r = cmpii(mulii(a, d), c);
     649       11431 :   avma = av; return r;
     650             : }
     651             : static int
     652       35805 : cmprfrac(GEN a, GEN y)
     653             : {
     654       35805 :   pari_sp av = avma;
     655       35805 :   GEN c = gel(y,1), d = gel(y,2);
     656       35805 :   int r = cmpri(mulri(a, d), c);
     657       35805 :   avma = av; return r;
     658             : }
     659             : static int
     660          42 : cmpgen(GEN x, GEN y)
     661             : {
     662          42 :   pari_sp av = avma;
     663          42 :   int s = gsigne(gsub(x,y));
     664          35 :   avma = av; return s;
     665             : }
     666             : 
     667             : /* returns the sign of x - y when it makes sense. 0 otherwise */
     668             : int
     669   155231361 : gcmp(GEN x, GEN y)
     670             : {
     671   155231361 :   long tx = typ(x), ty = typ(y);
     672             : 
     673   155231361 :   if (tx == ty) /* generic case */
     674   154619911 :     switch(tx)
     675             :     {
     676    76181877 :       case t_INT:  return cmpii(x, y);
     677    78550600 :       case t_REAL: return cmprr(x, y);
     678       39965 :       case t_FRAC: return cmpfrac(x, y);
     679          14 :       case t_QUAD: return cmpgen(x, y);
     680          21 :       case t_STR:  return cmp_str(GSTR(x), GSTR(y));
     681             :       case t_INFINITY:
     682             :       {
     683        6488 :         long sx = inf_get_sign(x), sy = inf_get_sign(y);
     684        6488 :         if (sx < sy) return -1;
     685          21 :         if (sx > sy) return 1;
     686          14 :         return 0;
     687             :       }
     688             :     }
     689      452396 :   if (ty == t_INFINITY) return -inf_get_sign(y);
     690      444812 :   switch(tx)
     691             :   {
     692             :     case t_INT:
     693       21165 :       switch(ty)
     694             :       {
     695       17112 :         case t_REAL: return cmpir(x, y);
     696        4046 :         case t_FRAC: return cmpifrac(x, y);
     697           0 :         case t_QUAD: return cmpgen(x, y);
     698             :       }
     699           7 :       break;
     700             :     case t_REAL:
     701      391851 :       switch(ty)
     702             :       {
     703      379797 :         case t_INT:  return cmpri(x, y);
     704       12047 :         case t_FRAC: return cmprfrac(x, y);
     705           0 :         case t_QUAD: return cmpgen(x, y);
     706             :       }
     707           7 :       break;
     708             :     case t_FRAC:
     709       31150 :       switch(ty)
     710             :       {
     711        7385 :         case t_INT:  return -cmpifrac(y, x);
     712       23758 :         case t_REAL: return -cmprfrac(y, x);
     713           0 :         case t_QUAD: return cmpgen(x, y);
     714             :       }
     715           7 :       break;
     716             :     case t_QUAD:
     717          28 :       return cmpgen(x, y);
     718         611 :     case t_INFINITY: return inf_get_sign(x);
     719             :   }
     720          28 :   pari_err_TYPE2("comparison",x,y);
     721             :   return 0;/*LCOV_EXCL_LINE*/
     722             : }
     723             : 
     724             : int
     725       24184 : gcmpsg(long s, GEN y)
     726             : {
     727       24184 :   long ty = typ(y);
     728       24184 :   switch(ty) {
     729         875 :     case t_INT:  return cmpsi(s,y);
     730       22532 :     case t_REAL: return cmpsr(s,y);
     731             :     case t_FRAC: {
     732         777 :       pari_sp av = avma;
     733         777 :       GEN n = gel(y,1), d = gel(y,2);
     734         777 :       int f = cmpii(mulsi(s,d), n); avma = av; return f;
     735             :     }
     736           0 :     case t_STR: return -1;
     737             :   }
     738           0 :   pari_err_TYPE2("comparison",stoi(s),y);
     739             :   return 0; /* LCOV_EXCL_LINE */
     740             : }
     741             : 
     742             : static long
     743     9786973 : roughtype(GEN x)
     744             : {
     745     9786973 :   switch(typ(x))
     746             :   {
     747        2044 :     case t_MAT: return t_MAT;
     748       20013 :     case t_VEC: case t_COL: return t_VEC;
     749     9723728 :     case t_VECSMALL: return t_VECSMALL;
     750       41188 :     default: return t_INT;
     751             :   }
     752             : }
     753             : 
     754             : static int lexcmpsg(long x, GEN y);
     755          28 : static int lexcmpgs(GEN x, long y) { return -lexcmpsg(y,x); }
     756             : /* lexcmp(stoi(x),y), y t_VEC/t_COL/t_MAT */
     757             : static int
     758          21 : lexcmp_s_matvec(long x, GEN y)
     759             : {
     760             :   int fl;
     761          21 :   if (lg(y)==1) return 1;
     762          14 :   fl = lexcmpsg(x,gel(y,1));
     763          14 :   if (fl) return fl;
     764           7 :   return -1;
     765             : }
     766             : /* x a scalar, y a t_VEC/t_COL/t_MAT */
     767             : static int
     768         224 : lexcmp_scal_matvec(GEN x, GEN y)
     769             : {
     770             :   int fl;
     771         224 :   if (lg(y)==1) return 1;
     772         224 :   fl = lexcmp(x,gel(y,1));
     773         224 :   if (fl) return fl;
     774           0 :   return -1;
     775             : }
     776             : /* x a scalar, y a t_VECSMALL */
     777             : static int
     778          28 : lexcmp_scal_vecsmall(GEN x, GEN y)
     779             : {
     780             :   int fl;
     781          28 :   if (lg(y)==1) return 1;
     782          28 :   fl = lexcmpgs(x, y[1]);
     783          28 :   if (fl) return fl;
     784           0 :   return -1;
     785             : }
     786             : 
     787             : /* tx = ty = t_MAT, or x and y are both vect_t */
     788             : static int
     789       10829 : lexcmp_similar(GEN x, GEN y)
     790             : {
     791       10829 :   long i, lx = lg(x), ly = lg(y), l = minss(lx,ly);
     792       21959 :   for (i=1; i<l; i++)
     793             :   {
     794       20426 :     int fl = lexcmp(gel(x,i),gel(y,i));
     795       20426 :     if (fl) return fl;
     796             :   }
     797        1533 :   if (lx == ly) return 0;
     798          28 :   return (lx < ly)? -1 : 1;
     799             : }
     800             : /* x a t_VECSMALL, y a t_VEC/t_COL ~ lexcmp_similar */
     801             : static int
     802         154 : lexcmp_vecsmall_vec(GEN x, GEN y)
     803             : {
     804         154 :   long i, lx = lg(x), ly = lg(y), l = minss(lx,ly);
     805         343 :   for (i=1; i<l; i++)
     806             :   {
     807         287 :     int fl = lexcmpsg(x[i], gel(y,i));
     808         287 :     if (fl) return fl;
     809             :   }
     810          56 :   if (lx == ly) return 0;
     811          21 :   return (lx < ly)? -1 : 1;
     812             : }
     813             : 
     814             : /* x t_VEC/t_COL, y t_MAT */
     815             : static int
     816          84 : lexcmp_vec_mat(GEN x, GEN y)
     817             : {
     818             :   int fl;
     819          84 :   if (lg(x)==1) return -1;
     820          84 :   if (lg(y)==1) return 1;
     821          84 :   fl = lexcmp_similar(x,gel(y,1));
     822          84 :   if (fl) return fl;
     823           0 :   return -1;
     824             : }
     825             : /* x t_VECSMALl, y t_MAT ~ lexcmp_vec_mat */
     826             : static int
     827          42 : lexcmp_vecsmall_mat(GEN x, GEN y)
     828             : {
     829             :   int fl;
     830          42 :   if (lg(x)==1) return -1;
     831          42 :   if (lg(y)==1) return 1;
     832          42 :   fl = lexcmp_vecsmall_vec(x, gel(y,1));
     833          42 :   if (fl) return fl;
     834           0 :   return -1;
     835             : }
     836             : 
     837             : /* x a t_VECSMALL, not y */
     838             : static int
     839         182 : lexcmp_vecsmall_other(GEN x, GEN y, long ty)
     840             : {
     841         182 :   switch(ty)
     842             :   {
     843          42 :     case t_MAT: return lexcmp_vecsmall_mat(x, y);
     844         112 :     case t_VEC: return lexcmp_vecsmall_vec(x, y);
     845          28 :     default: return -lexcmp_scal_vecsmall(y, x); /*y scalar*/
     846             :   }
     847             : }
     848             : 
     849             : /* lexcmp(stoi(s), y) */
     850             : static int
     851         329 : lexcmpsg(long x, GEN y)
     852             : {
     853         329 :   switch(roughtype(y))
     854             :   {
     855             :     case t_MAT:
     856             :     case t_VEC:
     857          21 :       return lexcmp_s_matvec(x,y);
     858             :     case t_VECSMALL: /* ~ lexcmp_scal_matvec */
     859          14 :       if (lg(y)==1) return 1;
     860           7 :       return (x > y[1])? 1: -1;
     861         294 :     default: return gcmpsg(x,y);
     862             :   }
     863             : }
     864             : 
     865             : /* as gcmp for vector/matrices, using lexicographic ordering on components */
     866             : int
     867     4893322 : lexcmp(GEN x, GEN y)
     868             : {
     869     4893322 :   const long tx = roughtype(x), ty = roughtype(y);
     870     4893322 :   if (tx == ty)
     871     4892832 :     switch(tx)
     872             :     {
     873             :       case t_MAT:
     874             :       case t_VEC:
     875       10745 :         return lexcmp_similar(x,y);
     876             :       case t_VECSMALL:
     877     4861766 :         return vecsmall_lexcmp(x,y);
     878             :       default:
     879       20321 :         return gcmp(x,y);
     880             :     }
     881         490 :   if (tx == t_VECSMALL) return  lexcmp_vecsmall_other(x,y,ty);
     882         371 :   if (ty == t_VECSMALL) return -lexcmp_vecsmall_other(y,x,tx);
     883             : 
     884         308 :   if (tx == t_INT) return  lexcmp_scal_matvec(x,y); /*scalar*/
     885         154 :   if (ty == t_INT) return -lexcmp_scal_matvec(y,x);
     886             : 
     887          84 :   if (ty==t_MAT) return  lexcmp_vec_mat(x,y);
     888          42 :   /*tx==t_MAT*/  return -lexcmp_vec_mat(y,x);
     889             : }
     890             : 
     891             : /*****************************************************************/
     892             : /*                                                               */
     893             : /*                          EQUALITY                             */
     894             : /*                returns 1 if x == y, 0 otherwise               */
     895             : /*                                                               */
     896             : /*****************************************************************/
     897             : /* x,y t_POL */
     898             : static int
     899      749880 : polidentical(GEN x, GEN y)
     900             : {
     901             :   long lx;
     902      749880 :   if (x[1] != y[1]) return 0;
     903      749859 :   lx = lg(x); if (lg(y) != lg(x)) return 0;
     904      749852 :   for (lx--; lx >= 2; lx--) if (!gidentical(gel(x,lx), gel(y,lx))) return 0;
     905      749838 :   return 1;
     906             : }
     907             : /* x,y t_SER */
     908             : static int
     909          14 : seridentical(GEN x, GEN y) { return polidentical(x,y); }
     910             : /* typ(x) = typ(y) = t_VEC/COL/MAT */
     911             : static int
     912     3655631 : vecidentical(GEN x, GEN y)
     913             : {
     914             :   long i;
     915     3655631 :   if ((x[0] ^ y[0]) & (TYPBITS|LGBITS)) return 0;
     916     9761633 :   for (i = lg(x)-1; i; i--)
     917     6717151 :     if (! gidentical(gel(x,i),gel(y,i)) ) return 0;
     918     3044482 :   return 1;
     919             : }
     920             : static int
     921          21 : identicalrr(GEN x, GEN y)
     922             : {
     923          21 :   long i, lx = lg(x);
     924          21 :   if (lg(y) != lx) return 0;
     925          14 :   if (x[1] != y[1]) return 0;
     926           7 :   i=2; while (i<lx && x[i]==y[i]) i++;
     927           7 :   return (i == lx);
     928             : }
     929             : 
     930             : static int
     931          28 : closure_identical(GEN x, GEN y)
     932             : {
     933          28 :   if (lg(x)!=lg(y) || x[1]!=y[1]) return 0;
     934          21 :   if (!gidentical(gel(x,2),gel(y,2)) || !gidentical(gel(x,3),gel(y,3))
     935           7 :    || !gidentical(gel(x,4),gel(y,4))) return 0;
     936           7 :   if (lg(x)<8) return 1;
     937           0 :   return gidentical(gel(x,7),gel(y,7));
     938             : }
     939             : 
     940             : static int
     941         336 : list_cmp(GEN x, GEN y, int cmp(GEN x, GEN y))
     942             : {
     943         336 :   int t = list_typ(x);
     944             :   GEN vx, vy;
     945         336 :   if (list_typ(y)!=t) return 0;
     946         336 :   vx = list_data(x);
     947         336 :   vy = list_data(y);
     948         336 :   if (!vx) return vy? 0: 1;
     949         322 :   if (!vy) return 0;
     950         308 :   if (lg(vx) != lg(vy)) return 0;
     951         301 :   switch (t)
     952             :   {
     953             :   case t_LIST_MAP:
     954             :     {
     955         280 :       pari_sp av = avma;
     956         280 :       GEN mx  = maptomat_shallow(x), my = maptomat_shallow(y);
     957         280 :       int ret = gidentical(gel(mx, 1), gel(my, 1)) && cmp(gel(mx, 2), gel(my, 2));
     958         280 :       avma = av; return ret;
     959             :     }
     960             :   default:
     961          21 :     return cmp(vx, vy);
     962             :   }
     963             : }
     964             : 
     965             : int
     966    35436500 : gidentical(GEN x, GEN y)
     967             : {
     968             :   long tx;
     969             : 
     970    35436500 :   if (x == y) return 1;
     971    34694605 :   tx = typ(x); if (typ(y) != tx) return 0;
     972    34693079 :   switch(tx)
     973             :   {
     974             :     case t_INT:
     975     6530889 :       return equalii(x,y);
     976             : 
     977             :     case t_REAL:
     978          14 :       return identicalrr(x,y);
     979             : 
     980             :     case t_FRAC: case t_INTMOD:
     981       20188 :       return equalii(gel(x,2), gel(y,2)) && equalii(gel(x,1), gel(y,1));
     982             : 
     983             :     case t_COMPLEX:
     984          14 :       return gidentical(gel(x,2),gel(y,2)) && gidentical(gel(x,1),gel(y,1));
     985             :     case t_PADIC:
     986          28 :       return valp(x) == valp(y)
     987          14 :         && equalii(gel(x,2),gel(y,2))
     988          14 :         && equalii(gel(x,3),gel(y,3))
     989          28 :         && equalii(gel(x,4),gel(y,4));
     990             :     case t_POLMOD:
     991          49 :       return gidentical(gel(x,2),gel(y,2)) && polidentical(gel(x,1),gel(y,1));
     992             :     case t_POL:
     993      749845 :       return polidentical(x,y);
     994             :     case t_SER:
     995          14 :       return seridentical(x,y);
     996             :     case t_FFELT:
     997          14 :       return FF_equal(x,y);
     998             : 
     999             :     case t_QFR:
    1000           7 :           if (!identicalrr(gel(x,4),gel(y,4))) return 0; /* fall through */
    1001             :     case t_QFI:
    1002     3906262 :       return equalii(gel(x,1),gel(y,1))
    1003     1953124 :           && equalii(gel(x,2),gel(y,2))
    1004     3906248 :           && equalii(gel(x,3),gel(y,3));
    1005             : 
    1006             :     case t_QUAD:
    1007          28 :       return ZX_equal(gel(x,1),gel(y,1))
    1008           7 :           && gidentical(gel(x,2),gel(y,2))
    1009          14 :           && gidentical(gel(x,3),gel(y,3));
    1010             : 
    1011             :     case t_RFRAC:
    1012           7 :       return gidentical(gel(x,1),gel(y,1)) && gidentical(gel(x,2),gel(y,2));
    1013             : 
    1014             :     case t_STR:
    1015          35 :       return !strcmp(GSTR(x),GSTR(y));
    1016             :     case t_VEC: case t_COL: case t_MAT:
    1017     3655631 :       return vecidentical(x,y);
    1018             :     case t_VECSMALL:
    1019    21783010 :       return zv_equal(x,y);
    1020             :     case t_CLOSURE:
    1021          21 :       return closure_identical(x,y);
    1022             :     case t_LIST:
    1023         161 :       return list_cmp(x, y, gidentical);
    1024          21 :     case t_INFINITY: return gidentical(gel(x,1),gel(y,1));
    1025             :   }
    1026           0 :   return 0;
    1027             : }
    1028             : /* x,y t_POL */
    1029             : static int
    1030      435574 : polequal(GEN x, GEN y)
    1031             : {
    1032             :   long lx, ly;
    1033      435574 :   if ((x[1] ^ y[1]) & (VARNBITS | SIGNBITS)) return 0;
    1034      426635 :   lx = lg(x); ly = lg(y);
    1035      426635 :   while (lx > ly) if (!gequal0(gel(x,--lx))) return 0;
    1036      425382 :   while (ly > lx) if (!gequal0(gel(y,--ly))) return 0;
    1037      413489 :   for (lx--; lx >= 2; lx--) if (!gequal(gel(x,lx), gel(y,lx))) return 0;
    1038      387863 :   return 1;
    1039             : }
    1040             : 
    1041             : /* x,y t_POL */
    1042             : static int
    1043         308 : serequal(GEN x, GEN y)
    1044             : {
    1045             :   long lx;
    1046         308 :   if (varn(x) != varn(y)) return 0;
    1047         308 :   if (!signe(x))
    1048             :   {
    1049         287 :     if (!signe(y)) return 1;
    1050           0 :     return valp(y) >= valp(x);
    1051             :   }
    1052          21 :   if (!signe(y))
    1053           0 :     return valp(x) >= valp(y);
    1054          21 :   if ((x[1] ^ y[1]) & VALPBITS) return 0;
    1055          21 :   lx = minss(lg(x), lg(y));
    1056          21 :   for (lx--; lx >= 2; lx--) if (!gequal(gel(x,lx), gel(y,lx))) return 0;
    1057          21 :   return 1;
    1058             : }
    1059             : 
    1060             : /* typ(x) = typ(y) = t_VEC/COL/MAT */
    1061             : static int
    1062     1115585 : vecequal(GEN x, GEN y)
    1063             : {
    1064             :   long i;
    1065     1115585 :   if ((x[0] ^ y[0]) & (TYPBITS|LGBITS)) return 0;
    1066    11484407 :   for (i = lg(x)-1; i; i--)
    1067    10428198 :     if (! gequal(gel(x,i),gel(y,i)) ) return 0;
    1068     1056209 :   return 1;
    1069             : }
    1070             : 
    1071             : static int
    1072     1719146 : gequal_try(GEN x, GEN y)
    1073             : {
    1074             :   int i;
    1075     1719146 :   pari_CATCH(CATCH_ALL) {
    1076         175 :     GEN E = pari_err_last();
    1077         175 :     switch(err_get_num(E))
    1078             :     {
    1079             :       case e_STACK: case e_MEM: case e_ALARM:
    1080           0 :         pari_err(0, E); /* rethrow */
    1081             :     }
    1082         175 :     return 0;
    1083             :   } pari_TRY {
    1084     1719146 :     i = gequal0(gadd(x, gneg_i(y)));
    1085     1718971 :   } pari_ENDCATCH;
    1086     1718971 :   return i;
    1087             : }
    1088             : 
    1089             : int
    1090    57156036 : gequal(GEN x, GEN y)
    1091             : {
    1092             :   pari_sp av;
    1093             :   long tx, ty;
    1094             :   long i;
    1095             : 
    1096    57156036 :   if (x == y) return 1;
    1097    45796228 :   tx = typ(x);
    1098    45796228 :   ty = typ(y);
    1099    45796228 :   if (tx == ty)
    1100    44077089 :     switch(tx)
    1101             :     {
    1102             :       case t_INT:
    1103    40512142 :         return equalii(x,y);
    1104             : 
    1105             :       case t_REAL:
    1106        1650 :         return equalrr(x,y);
    1107             : 
    1108             :       case t_FRAC: case t_INTMOD:
    1109      287826 :         return equalii(gel(x,2), gel(y,2)) && equalii(gel(x,1), gel(y,1));
    1110             : 
    1111             :       case t_COMPLEX:
    1112         182 :         return gequal(gel(x,2),gel(y,2)) && gequal(gel(x,1),gel(y,1));
    1113             :       case t_PADIC:
    1114         756 :         if (!equalii(gel(x,2),gel(y,2))) return 0;
    1115         756 :         av = avma; i = gequal0(gsub(x,y)); avma = av;
    1116         756 :         return i;
    1117             :       case t_POLMOD:
    1118       24693 :         if (varn(gel(x,1)) != varn(gel(y,1))) break;
    1119       24686 :         return gequal(gel(x,2),gel(y,2)) && RgX_equal_var(gel(x,1),gel(y,1));
    1120             :       case t_POL:
    1121      435574 :         return polequal(x,y);
    1122             :       case t_SER:
    1123         308 :         return serequal(x,y);
    1124             : 
    1125             :       case t_FFELT:
    1126       17091 :         return FF_equal(x,y);
    1127             : 
    1128             :       case t_QFR:
    1129             :       case t_QFI:
    1130     2096040 :         return equalii(gel(x,1),gel(y,1))
    1131      228722 :             && equalii(gel(x,2),gel(y,2))
    1132     1203725 :             && equalii(gel(x,3),gel(y,3));
    1133             : 
    1134             :       case t_QUAD:
    1135          14 :         return ZX_equal(gel(x,1),gel(y,1))
    1136           0 :             && gequal(gel(x,2),gel(y,2))
    1137           7 :             && gequal(gel(x,3),gel(y,3));
    1138             : 
    1139             :       case t_RFRAC:
    1140             :       {
    1141       73717 :         GEN a = gel(x,1), b = gel(x,2), c = gel(y,1), d = gel(y,2);
    1142       73717 :         if (gequal(b,d)) return gequal(a,c); /* simple case */
    1143           0 :         av = avma;
    1144           0 :         i = gequal(simplify_shallow(gmul(a,d)), simplify_shallow(gmul(b,c)));
    1145           0 :         avma = av; return i;
    1146             :       }
    1147             : 
    1148             :       case t_STR:
    1149       36090 :         return !strcmp(GSTR(x),GSTR(y));
    1150             :       case t_VEC: case t_COL: case t_MAT:
    1151     1115585 :         return vecequal(x,y);
    1152             :       case t_VECSMALL:
    1153      523238 :         return zv_equal(x,y);
    1154             :       case t_LIST:
    1155         175 :         return list_cmp(x, y, gequal);
    1156             :       case t_CLOSURE:
    1157           7 :         return closure_identical(x,y);
    1158             :       case t_INFINITY:
    1159          28 :         return gequal(gel(x,1),gel(y,1));
    1160             :     }
    1161             :   (void)&av; /* emulate volatile */
    1162     1719146 :   av = avma; i = gequal_try(x, y);
    1163     1719146 :   avma = av; return i;
    1164             : }
    1165             : 
    1166             : int
    1167       22827 : gequalsg(long s, GEN x)
    1168             : {
    1169       22827 :   pari_sp av = avma;
    1170       22827 :   int f = gequal(stoi(s), x);
    1171       22827 :   avma = av; return f;
    1172             : }
    1173             : /*******************************************************************/
    1174             : /*                                                                 */
    1175             : /*                          VALUATION                              */
    1176             : /*             p is either a t_INT or a t_POL.                     */
    1177             : /*  returns the largest exponent of p dividing x when this makes   */
    1178             : /*  sense : error for types real, integermod and polymod if p does */
    1179             : /*  not divide the modulus, q-adic if q!=p.                        */
    1180             : /*                                                                 */
    1181             : /*******************************************************************/
    1182             : 
    1183             : static long
    1184         224 : minval(GEN x, GEN p)
    1185             : {
    1186         224 :   long i,k, val = LONG_MAX, lx = lg(x);
    1187        5775 :   for (i=lontyp[typ(x)]; i<lx; i++)
    1188             :   {
    1189        5551 :     k = gvaluation(gel(x,i),p);
    1190        5551 :     if (k < val) val = k;
    1191             :   }
    1192         224 :   return val;
    1193             : }
    1194             : 
    1195             : static int
    1196          91 : intdvd(GEN x, GEN y, GEN *z) { GEN r; *z = dvmdii(x,y,&r); return (r==gen_0); }
    1197             : 
    1198             : /* x t_FRAC, p t_INT, return v_p(x) */
    1199             : static long
    1200       57162 : ratval(GEN x, GEN p) {
    1201       57162 :   long v = Z_pval(gel(x,2),p);
    1202       57162 :   if (v) return -v;
    1203        5964 :   return Z_pval(gel(x,1),p);
    1204             : }
    1205             : 
    1206             : long
    1207     1340232 : Q_pval(GEN x, GEN p) { return (typ(x) == t_INT)? Z_pval(x, p): ratval(x, p); }
    1208             : 
    1209             : long
    1210      420850 : Q_pvalrem(GEN x, GEN p, GEN *y)
    1211             : {
    1212             :   GEN a, b;
    1213             :   long v;
    1214      420850 :   if (typ(x) == t_INT) return Z_pvalrem(x, p, y);
    1215       78532 :   a = gel(x,1);
    1216       78532 :   b = gel(x,2);
    1217       78532 :   v = Z_pvalrem(b, p, &b);
    1218       78532 :   if (v) { *y = isint1(b)? a: mkfrac(a, b); return -v; }
    1219       48565 :   v = Z_pvalrem(a, p, &a);
    1220       48565 :   *y = mkfrac(a, b); return v;
    1221             : }
    1222             : 
    1223             : long
    1224      195398 : gvaluation(GEN x, GEN p)
    1225             : {
    1226      195398 :   long tx = typ(x), tp = typ(p);
    1227             :   pari_sp av;
    1228             : 
    1229      195398 :   switch(tp)
    1230             :   {
    1231             :     case t_INT:
    1232      192598 :       if (signe(p) && !is_pm1(p)) break;
    1233          28 :       pari_err_DOMAIN("gvaluation", "p", "=", p, p);
    1234             :     case t_POL:
    1235        2793 :       if (degpol(p) > 0) break;
    1236             :     default:
    1237           7 :       pari_err_DOMAIN("gvaluation", "p", "=", p, p);
    1238             :   }
    1239             : 
    1240      195363 :   switch(tx)
    1241             :   {
    1242             :     case t_INT:
    1243        9268 :       if (!signe(x)) return LONG_MAX;
    1244        9163 :       if (tp == t_POL) return 0;
    1245        8694 :       return Z_pval(x,p);
    1246             : 
    1247             :     case t_REAL:
    1248          49 :       if (tp == t_POL) return 0;
    1249          21 :       break;
    1250             : 
    1251             :     case t_FFELT:
    1252          28 :       if (tp == t_POL) return FF_equal0(x)? LONG_MAX: 0;
    1253          14 :       break;
    1254             : 
    1255             :     case t_INTMOD: {
    1256          77 :       GEN a = gel(x,1), b = gel(x,2);
    1257             :       long val;
    1258         140 :       if (tp == t_POL) return signe(b)? 0: LONG_MAX;
    1259          42 :       av = avma;
    1260          42 :       if (!intdvd(a, p, &a)) break;
    1261          28 :       if (!intdvd(b, p, &b)) { avma = av; return 0; }
    1262          14 :       val = 1; while (intdvd(a,p,&a) && intdvd(b,p,&b)) val++;
    1263          14 :       avma = av; return val;
    1264             :     }
    1265             : 
    1266             :     case t_FRAC:
    1267          42 :       if (tp == t_POL) return 0;
    1268          28 :       return ratval(x, p);
    1269             : 
    1270             :     case t_PADIC:
    1271      183533 :       if (tp == t_POL) return 0;
    1272      183519 :       if (!equalii(p,gel(x,2))) break;
    1273      183512 :       return valp(x);
    1274             : 
    1275             :     case t_POLMOD: {
    1276          35 :       GEN a = gel(x,1), b = gel(x,2);
    1277             :       long v, val;
    1278          35 :       if (tp == t_INT) return gvaluation(b,p);
    1279          21 :       v = varn(p);
    1280          21 :       if (varn(a) != v) return 0;
    1281          21 :       av = avma;
    1282          21 :       a = RgX_divrem(a, p, ONLY_DIVIDES);
    1283          21 :       if (!a) break;
    1284          14 :       if (typ(b) != t_POL || varn(b) != v ||
    1285           7 :           !(b = RgX_divrem(b, p, ONLY_DIVIDES)) ) { avma = av; return 0; }
    1286           7 :       val = 1;
    1287          21 :       while ((a = RgX_divrem(a, p, ONLY_DIVIDES)) &&
    1288           7 :              (b = RgX_divrem(b, p, ONLY_DIVIDES)) ) val++;
    1289           7 :       avma = av; return val;
    1290             :     }
    1291             :     case t_POL: {
    1292        2058 :       if (tp == t_POL) {
    1293        1932 :         long vp = varn(p), vx = varn(x);
    1294        1932 :         if (vp == vx)
    1295             :         {
    1296             :           long val;
    1297        1925 :           if (RgX_is_monomial(p)) return RgX_val(x) / degpol(p);
    1298           7 :           av = avma;
    1299           7 :           for (val=0; ; val++)
    1300             :           {
    1301           7 :             x = RgX_divrem(x,p,ONLY_DIVIDES);
    1302           7 :             if (!x) { avma = av; return val; }
    1303           0 :             if (gc_needed(av,1))
    1304             :             {
    1305           0 :               if(DEBUGMEM>1) pari_warn(warnmem,"gvaluation");
    1306           0 :               x = gerepilecopy(av, x);
    1307             :             }
    1308           0 :           }
    1309             :         }
    1310           7 :         if (varncmp(vx, vp) > 0) return 0;
    1311             :       }
    1312         126 :       return minval(x,p);
    1313             :     }
    1314             : 
    1315             :     case t_SER: {
    1316         175 :       if (tp == t_POL) {
    1317         161 :         long vp = varn(p), vx = varn(x);
    1318         161 :         if (vp == vx)
    1319             :         {
    1320         154 :           long val = RgX_val(p);
    1321         154 :           if (!val) pari_err_DOMAIN("gvaluation", "p", "=", p, p);
    1322         147 :           return (long)(valp(x) / val);
    1323             :         }
    1324           7 :         if (varncmp(vx, vp) > 0) return 0;
    1325             :       }
    1326          14 :       return minval(x,p);
    1327             :     }
    1328             : 
    1329             :     case t_RFRAC:
    1330          14 :       return gvaluation(gel(x,1),p) - gvaluation(gel(x,2),p);
    1331             : 
    1332             :     case t_COMPLEX: case t_QUAD: case t_VEC: case t_COL: case t_MAT:
    1333          84 :       return minval(x,p);
    1334             :   }
    1335          63 :   pari_err_OP("valuation", x,p);
    1336             :   return 0; /* LCOV_EXCL_LINE */
    1337             : }
    1338             : GEN
    1339        3661 : gpvaluation(GEN x, GEN p)
    1340             : {
    1341        3661 :   long v = gvaluation(x,p);
    1342        3563 :   return v == LONG_MAX? mkoo(): stoi(v);
    1343             : }
    1344             : 
    1345             : /* x is non-zero */
    1346             : long
    1347    12035661 : u_lvalrem(ulong x, ulong p, ulong *py)
    1348             : {
    1349             :   ulong vx;
    1350    12035661 :   if (p == 2) { vx = vals(x); *py = x >> vx; return vx; }
    1351     9895177 :   for(vx = 0;;)
    1352             :   {
    1353    20643608 :     if (x % p) { *py = x; return vx; }
    1354    10748431 :     x /= p; /* gcc is smart enough to make a single div */
    1355    10748431 :     vx++;
    1356    10748431 :   }
    1357             : }
    1358             : long
    1359     9471443 : u_lval(ulong x, ulong p)
    1360             : {
    1361             :   ulong vx;
    1362     9471443 :   if (p == 2) return vals(x);
    1363     9035428 :   for(vx = 0;;)
    1364             :   {
    1365    26748465 :     if (x % p) return vx;
    1366    17713037 :     x /= p; /* gcc is smart enough to make a single div */
    1367    17713037 :     vx++;
    1368    17713037 :   }
    1369             : }
    1370             : 
    1371             : long
    1372      196515 : z_lval(long s, ulong p) { return u_lval(labs(s), p); }
    1373             : long
    1374           0 : z_lvalrem(long s, ulong p, long *py)
    1375             : {
    1376             :   long v;
    1377           0 :   if (s < 0)
    1378             :   {
    1379           0 :     ulong u = (ulong)-s;
    1380           0 :     v = u_lvalrem(u, p, &u);
    1381           0 :     *py = -(long)u;
    1382             :   }
    1383             :   else
    1384             :   {
    1385           0 :     ulong u = (ulong)s;
    1386           0 :     v = u_lvalrem(u, p, &u);
    1387           0 :     *py = (long)u;
    1388             :   }
    1389           0 :   return v;
    1390             : }
    1391             : /* assume |p| > 1 */
    1392             : long
    1393       41699 : z_pval(long s, GEN p)
    1394             : {
    1395       41699 :   if (lgefint(p) > 3) return 0;
    1396       41699 :   return z_lval(s, uel(p,2));
    1397             : }
    1398             : /* assume |p| > 1 */
    1399             : long
    1400           0 : z_pvalrem(long s, GEN p, long *py)
    1401             : {
    1402           0 :   if (lgefint(p) > 3) { *py = s; return 0; }
    1403           0 :   return z_lvalrem(s, uel(p,2), py);
    1404             : }
    1405             : 
    1406             : /* return v_q(x) and set *py = x / q^v_q(x), using divide & conquer */
    1407             : static long
    1408     1360637 : Z_pvalrem_DC(GEN x, GEN q, GEN *py)
    1409             : {
    1410     1360637 :   GEN r, z = dvmdii(x, q, &r);
    1411             :   long v;
    1412     1360637 :   if (r != gen_0) { *py = x; return 0; }
    1413      954964 :   if (2 * lgefint(q) <= lgefint(z)+3) /* avoid squaring if pointless */
    1414      941529 :     v = Z_pvalrem_DC(z, sqri(q), py) << 1;
    1415             :   else
    1416       13435 :   { v = 0; *py = z; }
    1417      954964 :   z = dvmdii(*py, q, &r);
    1418      954964 :   if (r != gen_0) return v + 1;
    1419      404997 :   *py = z; return v + 2;
    1420             : }
    1421             : 
    1422             : static const long VAL_DC_THRESHOLD = 16;
    1423             : 
    1424             : long
    1425    10222722 : Z_lval(GEN x, ulong p)
    1426             : {
    1427             :   long vx;
    1428             :   pari_sp av;
    1429    10222722 :   if (p == 2) return vali(x);
    1430     7247956 :   if (lgefint(x) == 3) return u_lval(uel(x,2), p);
    1431      871313 :   av = avma;
    1432      871313 :   for(vx = 0;;)
    1433             :   {
    1434             :     ulong r;
    1435     6182386 :     GEN q = diviu_rem(x, p, &r);
    1436     7053699 :     if (r) break;
    1437     5425958 :     vx++; x = q;
    1438     5425958 :     if (vx == VAL_DC_THRESHOLD) {
    1439      114885 :       if (p == 1) pari_err_DOMAIN("Z_lval", "p", "=", gen_1, gen_1);
    1440      114885 :       vx += Z_pvalrem_DC(x, sqru(p), &x) << 1;
    1441      114885 :       q = diviu_rem(x, p, &r); if (!r) vx++;
    1442      114885 :       break;
    1443             :     }
    1444     5311073 :   }
    1445      871313 :   avma = av; return vx;
    1446             : }
    1447             : long
    1448     7400799 : Z_lvalrem(GEN x, ulong p, GEN *py)
    1449             : {
    1450             :   long vx, sx;
    1451             :   pari_sp av;
    1452     7400799 :   if (p == 2) { vx = vali(x); *py = shifti(x, -vx); return vx; }
    1453     5491749 :   if (lgefint(x) == 3) {
    1454             :     ulong u;
    1455     3328098 :     vx = u_lvalrem(uel(x,2), p, &u);
    1456     3328099 :     *py = signe(x) < 0? utoineg(u): utoipos(u);
    1457     3328097 :     return vx;
    1458             :   }
    1459     2163651 :   av = avma; (void)new_chunk(lgefint(x));
    1460     2163651 :   sx = signe(x);
    1461     2163651 :   for(vx = 0;;)
    1462             :   {
    1463             :     ulong r;
    1464     9874764 :     GEN q = diviu_rem(x, p, &r);
    1465    12038415 :     if (r) break;
    1466     8007702 :     vx++; x = q;
    1467     8007702 :     if (vx == VAL_DC_THRESHOLD) {
    1468      296589 :       if (p == 1) pari_err_DOMAIN("Z_lvalrem", "p", "=", gen_1, gen_1);
    1469      296589 :       vx += Z_pvalrem_DC(x, sqru(p), &x) << 1;
    1470      296589 :       q = diviu_rem(x, p, &r); if (!r) { vx++; x = q; }
    1471      296589 :       break;
    1472             :     }
    1473     7711113 :   }
    1474     2163651 :   avma = av; *py = icopy(x); setsigne(*py, sx); return vx;
    1475             : }
    1476             : 
    1477             : /* Is |q| <= p ? */
    1478             : static int
    1479   171731449 : isless_iu(GEN q, ulong p) {
    1480   171731449 :   long l = lgefint(q);
    1481   171731449 :   return l==2 || (l == 3 && uel(q,2) <= p);
    1482             : }
    1483             : 
    1484             : long
    1485   407246694 : u_lvalrem_stop(ulong *n, ulong p, int *stop)
    1486             : {
    1487   407246694 :   ulong N = *n, q = N / p, r = N % p; /* gcc makes a single div */
    1488   407246694 :   long v = 0;
    1489   407246694 :   if (!r)
    1490             :   {
    1491    30897418 :     do { v++; N = q; q = N / p; r = N % p; } while (!r);
    1492    20273730 :     *n = N;
    1493             :   }
    1494   407246694 :   *stop = q <= p; return v;
    1495             : }
    1496             : /* Assume n > 0. Return v_p(n), set *n := n/p^v_p(n). Set 'stop' if now
    1497             :  * n < p^2 [implies n prime if no prime < p divides n] */
    1498             : long
    1499   474969724 : Z_lvalrem_stop(GEN *n, ulong p, int *stop)
    1500             : {
    1501             :   pari_sp av;
    1502             :   long v;
    1503             :   ulong r;
    1504             :   GEN N, q;
    1505             : 
    1506   474969724 :   if (lgefint(*n) == 3)
    1507             :   {
    1508   303239134 :     r = (*n)[2];
    1509   303239134 :     v = u_lvalrem_stop(&r, p, stop);
    1510   304551040 :     if (v) *n = utoipos(r);
    1511   304548830 :     return v;
    1512             :   }
    1513   171730590 :   av = avma; v = 0; q = diviu_rem(*n, p, &r);
    1514   171730910 :   if (r) avma = av;
    1515             :   else
    1516             :   {
    1517             :     do {
    1518      714375 :       v++; N = q;
    1519      714375 :       if (v == VAL_DC_THRESHOLD)
    1520             :       {
    1521        7634 :         v += Z_pvalrem_DC(N,sqru(p),&N) << 1;
    1522        7634 :         q = diviu_rem(N, p, &r); if (!r) { v++; N = q; }
    1523        7634 :         break;
    1524             :       }
    1525      706741 :       q = diviu_rem(N, p, &r);
    1526      706741 :     } while (!r);
    1527      329812 :     *n = N;
    1528             :   }
    1529   171730910 :   *stop = isless_iu(q,p); return v;
    1530             : }
    1531             : 
    1532             : /* x is a non-zero integer, |p| > 1 */
    1533             : long
    1534     5159967 : Z_pvalrem(GEN x, GEN p, GEN *py)
    1535             : {
    1536             :   long vx;
    1537             :   pari_sp av;
    1538             : 
    1539     5159967 :   if (lgefint(p) == 3) return Z_lvalrem(x, uel(p,2), py);
    1540      122382 :   if (lgefint(x) == 3) { *py = icopy(x); return 0; }
    1541        1992 :   av = avma; vx = 0; (void)new_chunk(lgefint(x));
    1542             :   for(;;)
    1543             :   {
    1544        4304 :     GEN r, q = dvmdii(x,p,&r);
    1545        4304 :     if (r != gen_0) { avma = av; *py = icopy(x); return vx; }
    1546        2312 :     vx++; x = q;
    1547        2312 :   }
    1548             : }
    1549             : long
    1550      380373 : u_pvalrem(ulong x, GEN p, ulong *py)
    1551             : {
    1552      380373 :   if (lgefint(p) == 3) return u_lvalrem(x, uel(p,2), py);
    1553          60 :   *py = x; return 0;
    1554             : }
    1555             : long
    1556        2072 : u_pval(ulong x, GEN p)
    1557             : {
    1558        2072 :   if (lgefint(p) == 3) return u_lval(x, uel(p,2));
    1559           0 :   return 0;
    1560             : }
    1561             : long
    1562     6218720 : Z_pval(GEN x, GEN p) {
    1563             :   long vx;
    1564             :   pari_sp av;
    1565             : 
    1566     6218720 :   if (lgefint(p) == 3) return Z_lval(x, uel(p,2));
    1567       70510 :   if (lgefint(x) == 3) return 0;
    1568       64792 :   av = avma; vx = 0;
    1569             :   for(;;)
    1570             :   {
    1571       82088 :     GEN r, q = dvmdii(x,p,&r);
    1572       82088 :     if (r != gen_0) { avma = av; return vx; }
    1573       17296 :     vx++; x = q;
    1574       17296 :   }
    1575             : }
    1576             : 
    1577             : /* return v_p(n!) = [n/p] + [n/p^2] + ... */
    1578             : long
    1579       65734 : factorial_lval(ulong n, ulong p)
    1580             : {
    1581       65734 :   ulong q = p, v = 0;
    1582      108329 :   do { v += n/q; q *= p; } while (n >= q);
    1583       65734 :   return (long)v;
    1584             : }
    1585             : 
    1586             : /********** Same for "containers" ZX / ZV / ZC **********/
    1587             : 
    1588             : /* If the t_INT q divides the ZX/ZV x, return the quotient. Otherwise NULL.
    1589             :  * Stack clean; assumes lg(x) > 1 */
    1590             : static GEN
    1591        3836 : gen_Z_divides(GEN x, GEN q, long imin)
    1592             : {
    1593             :   long i, l;
    1594        3836 :   GEN y = cgetg_copy(x, &l);
    1595             : 
    1596        3836 :   y[1] = x[1]; /* Needed for ZX; no-op if ZV, overwritten in first iteration */
    1597       80612 :   for (i = imin; i < l; i++)
    1598             :   {
    1599       79142 :     GEN r, xi = gel(x,i);
    1600       79142 :     if (!signe(xi)) { gel(y,i) = xi; continue; }
    1601       48139 :     gel(y,i) = dvmdii(xi, q, &r);
    1602       48139 :     if (r != gen_0) { avma = (pari_sp)(y+l); return NULL; }
    1603             :   }
    1604        1470 :   return y;
    1605             : }
    1606             : /* If q divides the ZX/ZV x, return the quotient. Otherwise NULL.
    1607             :  * Stack clean; assumes lg(x) > 1 */
    1608             : static GEN
    1609        2492 : gen_z_divides(GEN x, ulong q, long imin)
    1610             : {
    1611             :   long i, l;
    1612        2492 :   GEN y = cgetg_copy(x, &l);
    1613             : 
    1614        2492 :   y[1] = x[1]; /* Needed for ZX; no-op if ZV, overwritten in first iteration */
    1615       35476 :   for (i = imin; i < l; i++)
    1616             :   {
    1617             :     ulong r;
    1618       35140 :     GEN xi = gel(x,i);
    1619       35140 :     if (!signe(xi)) { gel(y,i) = xi; continue; }
    1620       21665 :     gel(y,i) = diviu_rem(xi, q, &r);
    1621       21665 :     if (r) { avma = (pari_sp)(y+l); return NULL; }
    1622       19509 :     affectsign_safe(xi, &gel(y,i));
    1623             :   }
    1624         336 :   return y;
    1625             : }
    1626             : 
    1627             : /* return v_q(x) and set *py = x / q^v_q(x), using divide & conquer */
    1628             : static long
    1629        6305 : gen_pvalrem_DC(GEN x, GEN q, GEN *py, long imin)
    1630             : {
    1631             : 
    1632        6305 :   pari_sp av = avma;
    1633        6305 :   long v, i, l, lz = LONG_MAX;
    1634        6305 :   GEN y = cgetg_copy(x, &l);
    1635             : 
    1636        6305 :   y[1] = x[1];
    1637      116854 :   for (i = imin; i < l; i++)
    1638             :   {
    1639      113018 :     GEN r, xi = gel(x,i);
    1640      113018 :     if (!signe(xi)) { gel(y,i) = xi; continue; }
    1641       70649 :     gel(y,i) = dvmdii(xi, q, &r);
    1642       70649 :     if (r != gen_0) { avma = av; *py = x; return 0; }
    1643       68180 :     lz = minss(lz, lgefint(gel(y,i)));
    1644             :   }
    1645        3836 :   if (2 * lgefint(q) <= lz+3) /* avoid squaring if pointless */
    1646        3806 :     v = gen_pvalrem_DC(y, sqri(q), py, imin) << 1;
    1647             :   else
    1648          30 :   { v = 0; *py = y; }
    1649             : 
    1650        3836 :   y = gen_Z_divides(*py, q, imin);
    1651        3836 :   if (!y) return v+1;
    1652        1470 :   *py = y; return v+2;
    1653             : }
    1654             : 
    1655             : static long
    1656         490 : gen_2val(GEN x, long imin)
    1657             : {
    1658         490 :   long i, lx = lg(x), v = LONG_MAX;
    1659         791 :   for (i = imin; i < lx; i++)
    1660             :   {
    1661         749 :     GEN c = gel(x,i);
    1662             :     long w;
    1663         749 :     if (!signe(c)) continue;
    1664         588 :     w = vali(c);
    1665         588 :     if (w < v) { v = w; if (!v) break; }
    1666             :   }
    1667         490 :   return v;
    1668             : }
    1669             : static long
    1670        6884 : gen_lval(GEN x, ulong p, long imin)
    1671             : {
    1672             :   long i, lx, v;
    1673             :   pari_sp av;
    1674             :   GEN y;
    1675        6884 :   if (p == 2) return gen_2val(x, imin);
    1676        6394 :   av = avma;
    1677        6394 :   lx = lg(x); y = leafcopy(x);
    1678        6485 :   for(v = 0;; v++)
    1679        7780 :     for (i = imin; i < lx; i++)
    1680             :     {
    1681        7689 :       ulong r; gel(y,i) = diviu_rem(gel(y,i), p, &r);
    1682        7689 :       if (r) { avma = av; return v; }
    1683          91 :     }
    1684             : }
    1685             : long
    1686          28 : ZX_lval(GEN x, ulong p) { return gen_lval(x, p, 2); }
    1687             : long
    1688           0 : ZV_lval(GEN x, ulong p) { return gen_lval(x, p, 1); }
    1689             : 
    1690             : static long
    1691        9030 : gen_pval(GEN x, GEN p, long imin)
    1692             : {
    1693             :   long i, lx, v;
    1694             :   pari_sp av;
    1695             :   GEN y;
    1696        9030 :   if (lgefint(p) == 3) return gen_lval(x, p[2], imin);
    1697        2174 :   av = avma;
    1698        2174 :   lx = lg(x); y = leafcopy(x);
    1699        2174 :   for(v = 0;; v++)
    1700             :   {
    1701        2174 :     if (v == VAL_DC_THRESHOLD)
    1702             :     {
    1703           0 :       if (is_pm1(p)) pari_err_DOMAIN("gen_pval", "p", "=", p, p);
    1704           0 :       v += gen_pvalrem_DC(y, p, &y, imin);
    1705           0 :       avma = av; return v;
    1706             :     }
    1707             : 
    1708        2174 :     for (i = imin; i < lx; i++)
    1709             :     {
    1710        2174 :       GEN r; gel(y,i) = dvmdii(gel(y,i), p, &r);
    1711        2174 :       if (r != gen_0) { avma = av; return v; }
    1712             :     }
    1713           0 :   }
    1714             : }
    1715             : long
    1716        6307 : ZX_pval(GEN x, GEN p) { return gen_pval(x, p, 2); }
    1717             : long
    1718        2723 : ZV_pval(GEN x, GEN p) { return gen_pval(x, p, 1); }
    1719             : /* v = 0 (mod p) */
    1720             : int
    1721          91 : ZV_Z_dvd(GEN v, GEN p)
    1722             : {
    1723          91 :   pari_sp av = avma;
    1724          91 :   long i, l = lg(v);
    1725         280 :   for (i=1; i<l; i++)
    1726         196 :     if (remii(gel(v,i), p) != gen_0) { avma = av; return 0; }
    1727          84 :   avma = av; return 1;
    1728             : }
    1729             : 
    1730             : static long
    1731      292114 : gen_2valrem(GEN x, GEN *px, long imin)
    1732             : {
    1733      292114 :   long i, lx = lg(x), v = LONG_MAX;
    1734             :   GEN z;
    1735     3208433 :   for (i = imin; i < lx; i++)
    1736             :   {
    1737     3036450 :     GEN c = gel(x,i);
    1738             :     long w;
    1739     3036450 :     if (!signe(c)) continue;
    1740     2902008 :     w = vali(c);
    1741     2902008 :     if (w < v) {
    1742      583048 :       v = w;
    1743      583048 :       if (!v) { *px = x; return 0; } /* early abort */
    1744             :     }
    1745             :   }
    1746      171983 :   z = cgetg_copy(x, &lx); z[1] = x[1];
    1747      171983 :   for (i=imin; i<lx; i++) gel(z,i) = shifti(gel(x,i), -v);
    1748      171983 :   *px = z; return v;
    1749             : }
    1750             : static long
    1751      623563 : gen_lvalrem(GEN x, ulong p, GEN *px, long imin)
    1752             : {
    1753             :   long i, lx, v;
    1754             :   GEN y;
    1755      623563 :   if (p == 2) return gen_2valrem(x, px, imin);
    1756      331449 :   y = cgetg_copy(x, &lx);
    1757      331449 :   y[1] = x[1];
    1758      331449 :   x = leafcopy(x);
    1759      731991 :   for(v = 0;; v++)
    1760             :   {
    1761      731991 :     if (v == VAL_DC_THRESHOLD)
    1762             :     {
    1763        2492 :       if (p == 1) pari_err_DOMAIN("gen_lvalrem", "p", "=", gen_1, gen_1);
    1764        2492 :       v += gen_pvalrem_DC(x, sqru(p), px, imin) << 1;
    1765        2492 :       x = gen_z_divides(*px, p, imin);
    1766        2492 :       if (x) { *px = x; v++; }
    1767        2492 :       return v;
    1768             :     }
    1769             : 
    1770     5927955 :     for (i = imin; i < lx; i++)
    1771             :     {
    1772     5527413 :       ulong r; gel(y,i) = diviu_rem(gel(x,i), p, &r);
    1773     5527413 :       if (r) { *px = x; return v; }
    1774     5198456 :       affectsign_safe(gel(x,i), &gel(y,i));
    1775             :     }
    1776      400542 :     swap(x, y);
    1777      400542 :   }
    1778             : }
    1779             : long
    1780           0 : ZX_lvalrem(GEN x, ulong p, GEN *px) { return gen_lvalrem(x,p,px, 2); }
    1781             : long
    1782           0 : ZV_lvalrem(GEN x, ulong p, GEN *px) { return gen_lvalrem(x,p,px, 1); }
    1783             : 
    1784             : static long
    1785      623599 : gen_pvalrem(GEN x, GEN p, GEN *px, long imin)
    1786             : {
    1787             :   long i, lx, v;
    1788             :   GEN y;
    1789      623599 :   if (lgefint(p) == 3) return gen_lvalrem(x, p[2], px, imin);
    1790          36 :   y = cgetg_copy(x, &lx);
    1791          36 :   y[1] = x[1];
    1792          36 :   x = leafcopy(x);
    1793         160 :   for(v = 0;; v++)
    1794             :   {
    1795         160 :     if (v == VAL_DC_THRESHOLD)
    1796             :     {
    1797           7 :       if (is_pm1(p)) pari_err_DOMAIN("gen_pvalrem", "p", "=", p, p);
    1798           7 :       return v + gen_pvalrem_DC(x, p, px, imin);
    1799             :     }
    1800             : 
    1801        3693 :     for (i = imin; i < lx; i++)
    1802             :     {
    1803        3569 :       GEN r; gel(y,i) = dvmdii(gel(x,i), p, &r);
    1804        3569 :       if (r != gen_0) { *px = x; return v; }
    1805             :     }
    1806         124 :     swap(x, y);
    1807         124 :   }
    1808             : }
    1809             : long
    1810      530306 : ZX_pvalrem(GEN x, GEN p, GEN *px) { return gen_pvalrem(x,p,px, 2); }
    1811             : long
    1812       93293 : ZV_pvalrem(GEN x, GEN p, GEN *px) { return gen_pvalrem(x,p,px, 1); }
    1813             : 
    1814             : /*******************************************************************/
    1815             : /*                                                                 */
    1816             : /*                       NEGATION: Create -x                       */
    1817             : /*                                                                 */
    1818             : /*******************************************************************/
    1819             : 
    1820             : GEN
    1821   191442893 : gneg(GEN x)
    1822             : {
    1823             :   long lx, i;
    1824             :   GEN y;
    1825             : 
    1826   191442893 :   switch(typ(x))
    1827             :   {
    1828             :     case t_INT:
    1829    56548838 :       return signe(x)? negi(x): gen_0;
    1830             :     case t_REAL:
    1831    91490230 :       return mpneg(x);
    1832             : 
    1833      143880 :     case t_INTMOD: y=cgetg(3,t_INTMOD);
    1834      143880 :       gel(y,1) = icopy(gel(x,1));
    1835      143880 :       gel(y,2) = signe(gel(x,2))? subii(gel(y,1),gel(x,2)): gen_0;
    1836      143880 :       break;
    1837             : 
    1838             :     case t_FRAC:
    1839      984877 :       y = cgetg(3, t_FRAC);
    1840      984877 :       gel(y,1) = negi(gel(x,1));
    1841      984877 :       gel(y,2) = icopy(gel(x,2)); break;
    1842             : 
    1843             :     case t_COMPLEX:
    1844    40949339 :       y=cgetg(3, t_COMPLEX);
    1845    40949339 :       gel(y,1) = gneg(gel(x,1));
    1846    40949339 :       gel(y,2) = gneg(gel(x,2));
    1847    40949339 :       break;
    1848             : 
    1849       23221 :     case t_POLMOD: y=cgetg(3,t_POLMOD);
    1850       23221 :       gel(y,1) = RgX_copy(gel(x,1));
    1851       23221 :       gel(y,2) = gneg(gel(x,2)); break;
    1852             : 
    1853             :     case t_RFRAC:
    1854      153076 :       y = cgetg(3, t_RFRAC);
    1855      153076 :       gel(y,1) = gneg(gel(x,1));
    1856      153076 :       gel(y,2) = RgX_copy(gel(x,2)); break;
    1857             : 
    1858             :     case t_PADIC:
    1859        6804 :       if (!signe(gel(x,4))) return gcopy(x);
    1860        5894 :       y = cgetg(5, t_PADIC);
    1861        5894 :       y[1] = x[1];
    1862        5894 :       gel(y,2) = icopy(gel(x,2));
    1863        5894 :       gel(y,3) = icopy(gel(x,3));
    1864        5894 :       gel(y,4) = subii(gel(x,3),gel(x,4));
    1865        5894 :       break;
    1866             : 
    1867             :     case t_QUAD:
    1868          42 :       y=cgetg(4,t_QUAD);
    1869          42 :       gel(y,1) = ZX_copy(gel(x,1));
    1870          42 :       gel(y,2) = gneg(gel(x,2));
    1871          42 :       gel(y,3) = gneg(gel(x,3)); break;
    1872             : 
    1873       21600 :     case t_FFELT: return FF_neg(x);
    1874     1083036 :     case t_POL: return RgX_neg(x);
    1875             :     case t_SER:
    1876        1666 :       y = cgetg_copy(x, &lx); y[1] = x[1];
    1877        1666 :       for (i=2; i<lx; i++) gel(y,i) = gneg(gel(x,i));
    1878        1666 :       break;
    1879        7470 :     case t_VEC: return RgV_neg(x);
    1880       25622 :     case t_COL: return RgC_neg(x);
    1881        2471 :     case t_MAT: return RgM_neg(x);
    1882         721 :     case t_INFINITY: return inf_get_sign(x) == 1? mkmoo(): mkoo();
    1883             :     default:
    1884           0 :       pari_err_TYPE("gneg",x);
    1885             :       return NULL; /* LCOV_EXCL_LINE */
    1886             :   }
    1887    42261995 :   return y;
    1888             : }
    1889             : 
    1890             : GEN
    1891    38648288 : gneg_i(GEN x)
    1892             : {
    1893             :   long lx, i;
    1894             :   GEN y;
    1895             : 
    1896    38648288 :   switch(typ(x))
    1897             :   {
    1898             :     case t_INT:
    1899    21751862 :       return signe(x)? negi(x): gen_0;
    1900             :     case t_REAL:
    1901     3764472 :       return mpneg(x);
    1902             : 
    1903        9707 :     case t_INTMOD: y=cgetg(3,t_INTMOD);
    1904        9707 :       gel(y,1) = gel(x,1);
    1905        9707 :       gel(y,2) = signe(gel(x,2))? subii(gel(y,1),gel(x,2)): gen_0;
    1906        9707 :       break;
    1907             : 
    1908             :     case t_FRAC:
    1909     1028178 :       y = cgetg(3, t_FRAC);
    1910     1028178 :       gel(y,1) = negi(gel(x,1));
    1911     1028178 :       gel(y,2) = gel(x,2); break;
    1912             : 
    1913             :     case t_COMPLEX:
    1914      886045 :       y = cgetg(3, t_COMPLEX);
    1915      886045 :       gel(y,1) = gneg_i(gel(x,1));
    1916      886045 :       gel(y,2) = gneg_i(gel(x,2)); break;
    1917             : 
    1918      123909 :     case t_PADIC: y = cgetg(5,t_PADIC);
    1919      123909 :       y[1] = x[1];
    1920      123909 :       gel(y,2) = gel(x,2);
    1921      123909 :       gel(y,3) = gel(x,3);
    1922      123909 :       gel(y,4) = signe(gel(x,4))? subii(gel(x,3),gel(x,4)): gen_0; break;
    1923             : 
    1924       52076 :     case t_POLMOD: y=cgetg(3,t_POLMOD);
    1925       52076 :       gel(y,1) = gel(x,1);
    1926       52076 :       gel(y,2) = gneg_i(gel(x,2)); break;
    1927             : 
    1928       83618 :     case t_FFELT: return FF_neg_i(x);
    1929             : 
    1930         609 :     case t_QUAD: y=cgetg(4,t_QUAD);
    1931         609 :       gel(y,1) = gel(x,1);
    1932         609 :       gel(y,2) = gneg_i(gel(x,2));
    1933         609 :       gel(y,3) = gneg_i(gel(x,3)); break;
    1934             : 
    1935             :     case t_VEC: case t_COL: case t_MAT:
    1936       40999 :       y = cgetg_copy(x, &lx);
    1937       40999 :       for (i=1; i<lx; i++) gel(y,i) = gneg_i(gel(x,i));
    1938       40999 :       break;
    1939             : 
    1940             :     case t_POL: case t_SER:
    1941     5949421 :       y = cgetg_copy(x, &lx); y[1]=x[1];
    1942     5949421 :       for (i=2; i<lx; i++) gel(y,i) = gneg_i(gel(x,i));
    1943     5949421 :       break;
    1944             : 
    1945             :     case t_RFRAC:
    1946     4957392 :       y = cgetg(3, t_RFRAC);
    1947     4957392 :       gel(y,1) = gneg_i(gel(x,1));
    1948     4957392 :       gel(y,2) = gel(x,2); break;
    1949             : 
    1950             :     default:
    1951           0 :       pari_err_TYPE("gneg_i",x);
    1952             :       return NULL; /* LCOV_EXCL_LINE */
    1953             :   }
    1954    13048336 :   return y;
    1955             : }
    1956             : 
    1957             : /******************************************************************/
    1958             : /*                                                                */
    1959             : /*                       ABSOLUTE VALUE                           */
    1960             : /*    Create abs(x) if x is integer, real, fraction or complex.   */
    1961             : /*                       Error otherwise.                         */
    1962             : /*                                                                */
    1963             : /******************************************************************/
    1964             : static int
    1965           0 : is_negative(GEN x) {
    1966           0 :   switch(typ(x))
    1967             :   {
    1968             :     case t_INT: case t_REAL:
    1969           0 :       return (signe(x) < 0);
    1970             :     case t_FRAC:
    1971           0 :       return (signe(gel(x,1)) < 0);
    1972             :   }
    1973           0 :   return 0;
    1974             : }
    1975             : 
    1976             : GEN
    1977     8066022 : gabs(GEN x, long prec)
    1978             : {
    1979             :   long lx, i;
    1980             :   pari_sp av, tetpil;
    1981             :   GEN y,p1;
    1982             : 
    1983     8066022 :   switch(typ(x))
    1984             :   {
    1985             :     case t_INT: case t_REAL:
    1986     6380224 :       return mpabs(x);
    1987             : 
    1988             :     case t_FRAC:
    1989         315 :       return absfrac(x);
    1990             : 
    1991             :     case t_COMPLEX:
    1992     1676018 :       av=avma; p1=cxnorm(x);
    1993     1676018 :       switch(typ(p1))
    1994             :       {
    1995             :         case t_INT:
    1996         889 :           if (!Z_issquareall(p1, &y)) break;
    1997         693 :           return gerepileupto(av, y);
    1998             :         case t_FRAC: {
    1999             :           GEN a,b;
    2000         112 :           if (!Z_issquareall(gel(p1,1), &a)) break;
    2001          42 :           if (!Z_issquareall(gel(p1,2), &b)) break;
    2002           0 :           return gerepileupto(av, gdiv(a,b));
    2003             :         }
    2004             :       }
    2005     1675325 :       tetpil=avma;
    2006     1675325 :       return gerepile(av,tetpil,gsqrt(p1,prec));
    2007             : 
    2008             :     case t_QUAD:
    2009          21 :       av = avma;
    2010          21 :       return gerepileuptoleaf(av, gabs(quadtofp(x, prec), prec));
    2011             : 
    2012             :     case t_POL:
    2013           0 :       lx = lg(x); if (lx<=2) return RgX_copy(x);
    2014           0 :       return is_negative(gel(x,lx-1))? gneg(x): RgX_copy(x);
    2015             : 
    2016             :     case t_SER:
    2017           7 :      if (!signe(x)) pari_err_DOMAIN("abs", "argument", "=", gen_0, x);
    2018           7 :      if (valp(x)) pari_err_DOMAIN("abs", "series valuation", "!=", gen_0, x);
    2019           0 :      return is_negative(gel(x,2))? gneg(x): gcopy(x);
    2020             : 
    2021             :     case t_VEC: case t_COL: case t_MAT:
    2022        9437 :       y = cgetg_copy(x, &lx);
    2023        9437 :       for (i=1; i<lx; i++) gel(y,i) = gabs(gel(x,i),prec);
    2024        9437 :       return y;
    2025             :   }
    2026           0 :   pari_err_TYPE("gabs",x);
    2027             :   return NULL; /* LCOV_EXCL_LINE */
    2028             : }
    2029             : 
    2030             : GEN
    2031     7830173 : gmax(GEN x, GEN y) { return gcopy(gcmp(x,y)<0? y: x); }
    2032             : GEN
    2033           0 : gmaxgs(GEN x, long s) { return (gcmpsg(s,x)>=0)? stoi(s): gcopy(x); }
    2034             : 
    2035             : GEN
    2036       89345 : gmin(GEN x, GEN y) { return gcopy(gcmp(x,y)<0? x: y); }
    2037             : GEN
    2038           0 : gmings(GEN x, long s) { return (gcmpsg(s,x)>0)? gcopy(x): stoi(s); }
    2039             : 
    2040             : long
    2041        5786 : vecindexmax(GEN x)
    2042             : {
    2043        5786 :   long lx = lg(x), i0, i;
    2044             :   GEN s;
    2045             : 
    2046        5786 :   if (lx==1) pari_err_DOMAIN("vecindexmax", "empty argument", "=", x,x);
    2047        5772 :   switch(typ(x))
    2048             :   {
    2049             :     case t_VEC: case t_COL:
    2050        5772 :       s = gel(x,i0=1);
    2051       20203 :       for (i=2; i<lx; i++)
    2052       14431 :         if (gcmp(gel(x,i),s) > 0) s = gel(x,i0=i);
    2053        5772 :       return i0;
    2054             :     case t_VECSMALL:
    2055           0 :       return vecsmall_indexmax(x);
    2056           0 :     default: pari_err_TYPE("vecindexmax",x);
    2057             :   }
    2058             :   /* LCOV_EXCL_LINE */
    2059           0 :   return 0;
    2060             : }
    2061             : long
    2062        5814 : vecindexmin(GEN x)
    2063             : {
    2064        5814 :   long lx = lg(x), i0, i;
    2065             :   GEN s;
    2066             : 
    2067        5814 :   if (lx==1) pari_err_DOMAIN("vecindexmin", "empty argument", "=", x,x);
    2068        5807 :   switch(typ(x))
    2069             :   {
    2070             :     case t_VEC: case t_COL:
    2071        5807 :       s = gel(x,i0=1);
    2072       11544 :       for (i=2; i<lx; i++)
    2073        5737 :         if (gcmp(gel(x,i),s) < 0) s = gel(x,i0=i);
    2074        5807 :       return i0;
    2075             :     case t_VECSMALL:
    2076           0 :       return vecsmall_indexmin(x);
    2077           0 :     default: pari_err_TYPE("vecindexmin",x);
    2078             :   }
    2079             :   /* LCOV_EXCL_LINE */
    2080           0 :   return 0;
    2081             : }
    2082             : 
    2083             : 
    2084             : GEN
    2085        1832 : vecmax0(GEN x, GEN *pi)
    2086             : {
    2087             :   long i0, j0, i, j;
    2088             :   GEN s;
    2089        1832 :   switch(typ(x))
    2090             :   {
    2091             :     case t_VEC: case t_COL:
    2092        1379 :       i = vecindexmax(x);
    2093        1365 :       if (pi) *pi = utoipos(i);
    2094        1365 :       return gcopy(gel(x, i));
    2095             :     case t_MAT: {
    2096         425 :       long lx2, lx = lg(x);
    2097         425 :       if (lx==1 || (lx2 = lgcols(x)) == 1)
    2098             :       {
    2099           7 :         pari_err_DOMAIN("vecmax", "empty argument", "=", x,x);
    2100             :         return NULL;/*LCOV_EXCL_LINE*/
    2101             :       }
    2102         418 :       s = gcoeff(x,i0=1,j0=1); i = 2;
    2103        1660 :       for (j=1; j<lx; j++,i=1)
    2104             :       {
    2105        1242 :         GEN c = gel(x,j);
    2106       24574 :         for (; i<lx2; i++)
    2107       23332 :           if (gcmp(gel(c,i),s) > 0) { s = gel(c,i); j0=j; i0=i; }
    2108             :       }
    2109         418 :       if (pi) *pi = mkvec2(utoipos(i0), utoipos(j0));
    2110         418 :       return gcopy(s);
    2111             :     }
    2112             :     case t_VECSMALL:
    2113          14 :       i = vecsmall_indexmax(x);
    2114          14 :       if (pi) *pi = utoipos(i);
    2115          14 :       return stoi(x[i]);
    2116             :     default:
    2117          14 :       return gcopy(x);
    2118             :   }
    2119             : }
    2120             : GEN
    2121        5856 : vecmin0(GEN x, GEN *pi)
    2122             : {
    2123             :   long i0, j0, i, j;
    2124             :   GEN s;
    2125        5856 :   switch(typ(x))
    2126             :   {
    2127             :     case t_VEC: case t_COL:
    2128        5814 :       i = vecindexmin(x);
    2129        5807 :       if (pi) *pi = utoipos(i);
    2130        5807 :       return gcopy(gel(x, i));
    2131             :     case t_MAT: {
    2132          14 :       long lx2, lx = lg(x);
    2133          14 :       if (lx==1 || (lx2 = lgcols(x)) == 1)
    2134             :       {
    2135           0 :         pari_err_DOMAIN("vecmin", "empty argument", "=", x,x);
    2136             :         return NULL;/*LCOV_EXCL_LINE*/
    2137             :       }
    2138          14 :       s = gcoeff(x,i0=1,j0=1); i = 2;
    2139          42 :       for (j=1; j<lx; j++,i=1)
    2140             :       {
    2141          28 :         GEN c = gel(x,j);
    2142          70 :         for (; i<lx2; i++)
    2143          42 :           if (gcmp(gel(c,i),s) < 0) { s = gel(c,i); j0=j; i0=i; }
    2144             :       }
    2145          14 :       if (pi) *pi = mkvec2(utoipos(i0), utoipos(j0));
    2146          14 :       return gcopy(s);
    2147             :     }
    2148             :     case t_VECSMALL:
    2149          14 :       i = vecsmall_indexmin(x);
    2150          14 :       if (pi) *pi = utoipos(i);
    2151          14 :       return stoi(x[i]);
    2152             :     default:
    2153          14 :       return gcopy(x);
    2154             :   }
    2155             : }
    2156             : 
    2157             : GEN
    2158        1692 : vecmax(GEN x) { return vecmax0(x, NULL); }
    2159             : GEN
    2160        5786 : vecmin(GEN x) { return vecmin0(x, NULL); }
    2161             : 
    2162             : /*******************************************************************/
    2163             : /*                                                                 */
    2164             : /*                      AFFECT long --> GEN                        */
    2165             : /*         affect long s to GEN x. Useful for initialization.      */
    2166             : /*                                                                 */
    2167             : /*******************************************************************/
    2168             : 
    2169             : static void
    2170           0 : padicaff0(GEN x)
    2171             : {
    2172           0 :   if (signe(gel(x,4)))
    2173             :   {
    2174           0 :     x[1] = evalvalp(valp(x)+precp(x));
    2175           0 :     affsi(0,gel(x,4));
    2176             :   }
    2177           0 : }
    2178             : 
    2179             : void
    2180        1008 : gaffsg(long s, GEN x)
    2181             : {
    2182        1008 :   switch(typ(x))
    2183             :   {
    2184           0 :     case t_INT: affsi(s,x); break;
    2185        1008 :     case t_REAL: affsr(s,x); break;
    2186           0 :     case t_INTMOD: modsiz(s,gel(x,1),gel(x,2)); break;
    2187           0 :     case t_FRAC: affsi(s,gel(x,1)); affsi(1,gel(x,2)); break;
    2188           0 :     case t_COMPLEX: gaffsg(s,gel(x,1)); gaffsg(0,gel(x,2)); break;
    2189             :     case t_PADIC: {
    2190             :       long vx;
    2191             :       GEN y;
    2192           0 :       if (!s) { padicaff0(x); break; }
    2193           0 :       vx = Z_pvalrem(stoi(s), gel(x,2), &y);
    2194           0 :       setvalp(x,vx); modiiz(y,gel(x,3),gel(x,4));
    2195           0 :       break;
    2196             :     }
    2197           0 :     case t_QUAD: gaffsg(s,gel(x,2)); gaffsg(0,gel(x,3)); break;
    2198           0 :     default: pari_err_TYPE2("=",stoi(s),x);
    2199             :   }
    2200        1008 : }
    2201             : 
    2202             : /*******************************************************************/
    2203             : /*                                                                 */
    2204             : /*                     GENERIC AFFECTATION                         */
    2205             : /*         Affect the content of x to y, whenever possible         */
    2206             : /*                                                                 */
    2207             : /*******************************************************************/
    2208             : /* x PADIC, Y INT, return lift(x * Mod(1,Y)) */
    2209             : GEN
    2210        3892 : padic_to_Fp(GEN x, GEN Y) {
    2211        3892 :   pari_sp av = avma;
    2212        3892 :   GEN p = gel(x,2), z;
    2213        3892 :   long vy, vx = valp(x);
    2214        3892 :   if (!signe(Y)) pari_err_INV("padic_to_Fp",Y);
    2215        3892 :   vy = Z_pvalrem(Y,p, &z);
    2216        3892 :   if (vx < 0 || !gequal1(z)) pari_err_OP("",x, mkintmod(gen_1,Y));
    2217        3878 :   if (vx >= vy) { avma = av; return gen_0; }
    2218        3556 :   z = gel(x,4);
    2219        3556 :   if (!signe(z) || vy > vx + precp(x)) pari_err_OP("",x, mkintmod(gen_1,Y));
    2220        3556 :   if (vx) z = mulii(z, powiu(p,vx));
    2221        3556 :   return gerepileuptoint(av, remii(z, Y));
    2222             : }
    2223             : ulong
    2224          77 : padic_to_Fl(GEN x, ulong Y) {
    2225          77 :   GEN p = gel(x,2);
    2226             :   ulong u, z;
    2227          77 :   long vy, vx = valp(x);
    2228          77 :   vy = u_pvalrem(Y,p, &u);
    2229          77 :   if (vx < 0 || u != 1) pari_err_OP("",x, mkintmodu(1,Y));
    2230             :   /* Y = p^vy */
    2231          77 :   if (vx >= vy) return 0;
    2232          70 :   z = umodiu(gel(x,4), Y);
    2233          70 :   if (!z || vy > vx + precp(x)) pari_err_OP("",x, mkintmodu(1,Y));
    2234          70 :   if (vx) {
    2235           0 :     ulong pp = p[2];
    2236           0 :     z = Fl_mul(z, upowuu(pp,vx), Y); /* p^vx < p^vy = Y */
    2237             :   }
    2238          70 :   return z;
    2239             : }
    2240             : 
    2241             : static void
    2242           0 : croak(const char *s) {
    2243             :   char *t;
    2244           0 :   t = stack_sprintf("gaffect [overwriting universal object: %s]",s);
    2245           0 :   pari_err_BUG(t);
    2246           0 : }
    2247             : 
    2248             : void
    2249      245878 : gaffect(GEN x, GEN y)
    2250             : {
    2251      245878 :   long vx, i, lx, ly, tx = typ(x), ty = typ(y);
    2252             :   pari_sp av;
    2253             :   GEN p1, num, den;
    2254             : 
    2255      245878 :   if (tx == ty) switch(tx) {
    2256             :     case t_INT:
    2257      364685 :       if (!is_universal_constant(y)) { affii(x,y); return; }
    2258             :       /* y = gen_0, gnil, gen_1 or gen_2 */
    2259           0 :       if (y==gen_0)  croak("gen_0");
    2260           0 :       if (y==gen_1)  croak("gen_1");
    2261           0 :       if (y==gen_m1) croak("gen_m1");
    2262           0 :       if (y==gen_m2) croak("gen_m2");
    2263           0 :       if (y==gen_2)  croak("gen_2");
    2264           0 :       croak("gnil)");
    2265       51277 :     case t_REAL: affrr(x,y); return;
    2266             :     case t_INTMOD:
    2267           0 :       if (!dvdii(gel(x,1),gel(y,1))) pari_err_OP("",x,y);
    2268           0 :       modiiz(gel(x,2),gel(y,1),gel(y,2)); return;
    2269             :     case t_FRAC:
    2270           0 :       affii(gel(x,1),gel(y,1));
    2271           0 :       affii(gel(x,2),gel(y,2)); return;
    2272             :     case t_COMPLEX:
    2273        1673 :       gaffect(gel(x,1),gel(y,1));
    2274        1673 :       gaffect(gel(x,2),gel(y,2)); return;
    2275             :     case t_PADIC:
    2276           0 :       if (!equalii(gel(x,2),gel(y,2))) pari_err_OP("",x,y);
    2277           0 :       modiiz(gel(x,4),gel(y,3),gel(y,4));
    2278           0 :       setvalp(y,valp(x)); return;
    2279             :     case t_QUAD:
    2280           0 :       if (! ZX_equal(gel(x,1),gel(y,1))) pari_err_OP("",x,y);
    2281           0 :       affii(gel(x,2),gel(y,2));
    2282           0 :       affii(gel(x,3),gel(y,3)); return;
    2283             :     case t_VEC: case t_COL: case t_MAT:
    2284       72077 :       lx = lg(x); if (lx != lg(y)) pari_err_DIM("gaffect");
    2285       72077 :       for (i=1; i<lx; i++) gaffect(gel(x,i),gel(y,i));
    2286       72077 :       return;
    2287             :   }
    2288             : 
    2289             :   /* Various conversions. Avoid them, use specialized routines ! */
    2290             : 
    2291        1022 :   if (!is_const_t(ty)) pari_err_TYPE2("=",x,y);
    2292        1022 :   switch(tx)
    2293             :   {
    2294             :     case t_INT:
    2295           0 :       switch(ty)
    2296             :       {
    2297             :         case t_REAL:
    2298           0 :           affir(x,y); break;
    2299             : 
    2300             :         case t_INTMOD:
    2301           0 :           modiiz(x,gel(y,1),gel(y,2)); break;
    2302             : 
    2303             :         case t_COMPLEX:
    2304           0 :           gaffect(x,gel(y,1)); gaffsg(0,gel(y,2)); break;
    2305             : 
    2306             :         case t_PADIC:
    2307           0 :           if (!signe(x)) { padicaff0(y); break; }
    2308           0 :           av = avma;
    2309           0 :           setvalp(y, Z_pvalrem(x,gel(y,2),&p1));
    2310           0 :           affii(modii(p1,gel(y,3)), gel(y,4));
    2311           0 :           avma = av; break;
    2312             : 
    2313           0 :         case t_QUAD: gaffect(x,gel(y,2)); gaffsg(0,gel(y,3)); break;
    2314           0 :         default: pari_err_TYPE2("=",x,y);
    2315             :       }
    2316           0 :       break;
    2317             : 
    2318             :     case t_REAL:
    2319        1008 :       switch(ty)
    2320             :       {
    2321        1008 :         case t_COMPLEX: gaffect(x,gel(y,1)); gaffsg(0,gel(y,2)); break;
    2322           0 :         default: pari_err_TYPE2("=",x,y);
    2323             :       }
    2324        1008 :       break;
    2325             : 
    2326             :     case t_FRAC:
    2327          14 :       switch(ty)
    2328             :       {
    2329          14 :         case t_REAL: rdiviiz(gel(x,1),gel(x,2), y); break;
    2330           0 :         case t_INTMOD: av = avma;
    2331           0 :           p1 = Fp_inv(gel(x,2),gel(y,1));
    2332           0 :           affii(modii(mulii(gel(x,1),p1),gel(y,1)), gel(y,2));
    2333           0 :           avma = av; break;
    2334           0 :         case t_COMPLEX: gaffect(x,gel(y,1)); gaffsg(0,gel(y,2)); break;
    2335             :         case t_PADIC:
    2336           0 :           if (!signe(gel(x,1))) { padicaff0(y); break; }
    2337           0 :           num = gel(x,1);
    2338           0 :           den = gel(x,2);
    2339           0 :           av = avma; vx = Z_pvalrem(num, gel(y,2), &num);
    2340           0 :           if (!vx) vx = -Z_pvalrem(den,gel(y,2),&den);
    2341           0 :           setvalp(y,vx);
    2342           0 :           p1 = mulii(num,Fp_inv(den,gel(y,3)));
    2343           0 :           affii(modii(p1,gel(y,3)), gel(y,4)); avma = av; break;
    2344           0 :         case t_QUAD: gaffect(x,gel(y,2)); gaffsg(0,gel(y,3)); break;
    2345           0 :         default: pari_err_TYPE2("=",x,y);
    2346             :       }
    2347          14 :       break;
    2348             : 
    2349             :     case t_COMPLEX:
    2350           0 :       if (!gequal0(gel(x,2))) pari_err_TYPE2("=",x,y);
    2351           0 :       gaffect(gel(x,1), y);
    2352           0 :       break;
    2353             : 
    2354             :     case t_PADIC:
    2355           0 :       switch(ty)
    2356             :       {
    2357             :         case t_INTMOD:
    2358           0 :           av = avma; affii(padic_to_Fp(x, gel(y,1)), gel(y,2));
    2359           0 :           avma = av; break;
    2360           0 :         default: pari_err_TYPE2("=",x,y);
    2361             :       }
    2362           0 :       break;
    2363             : 
    2364             :     case t_QUAD:
    2365           0 :       switch(ty)
    2366             :       {
    2367             :         case t_INT: case t_INTMOD: case t_FRAC: case t_PADIC:
    2368           0 :           pari_err_TYPE2("=",x,y);
    2369             : 
    2370             :         case t_REAL:
    2371           0 :           av = avma; affgr(quadtofp(x,realprec(y)), y); avma = av; break;
    2372             :         case t_COMPLEX:
    2373           0 :           ly = precision(y); if (!ly) pari_err_TYPE2("=",x,y);
    2374           0 :           av = avma; gaffect(quadtofp(x,ly), y); avma = av; break;
    2375           0 :         default: pari_err_TYPE2("=",x,y);
    2376             :       }
    2377           0 :     default: pari_err_TYPE2("=",x,y);
    2378             :   }
    2379             : }
    2380             : 
    2381             : /*******************************************************************/
    2382             : /*                                                                 */
    2383             : /*           CONVERSION QUAD --> REAL, COMPLEX OR P-ADIC           */
    2384             : /*                                                                 */
    2385             : /*******************************************************************/
    2386             : GEN
    2387         112 : quadtofp(GEN x, long prec)
    2388             : {
    2389         112 :   GEN z, Q, u = gel(x,2), v = gel(x,3);
    2390             :   pari_sp av;
    2391         112 :   if (prec < LOWDEFAULTPREC) prec = LOWDEFAULTPREC;
    2392         112 :   if (isintzero(v)) return cxcompotor(u, prec);
    2393         112 :   av = avma; Q = gel(x,1);
    2394         112 :   z = itor(quad_disc(x), prec);
    2395         112 :   if (signe(gel(Q,2)) < 0) /* Q[2] = -D/4 or (1-D)/4 */
    2396             :   {
    2397         112 :     z = subri(sqrtr(z), gel(Q,3));
    2398         112 :     shiftr_inplace(z, -1);
    2399             :   }
    2400             :   else
    2401             :   {
    2402           0 :     z = sqrtr_abs(z); shiftr_inplace(z, -1);
    2403           0 :     z = mkcomplex(gmul2n(negi(gel(Q,3)),-1), z);
    2404             :   }/* z = (-b + sqrt(D)) / 2 */
    2405         112 :   return gerepileupto(av, gadd(u, gmul(v,z)));
    2406             : }
    2407             : 
    2408             : static GEN
    2409          14 : qtop(GEN x, GEN p, long d)
    2410             : {
    2411          14 :   GEN z, D, P, b, u = gel(x,2), v = gel(x,3);
    2412             :   pari_sp av;
    2413          14 :   if (gequal0(v)) return cvtop(u, p, d);
    2414          14 :   P = gel(x,1);
    2415          14 :   b = gel(P,3);
    2416          14 :   av = avma; D = quad_disc(x);
    2417          14 :   if (absequaliu(p,2)) d += 2;
    2418          14 :   z = Qp_sqrt(cvtop(D,p,d));
    2419          14 :   if (!z) pari_err_SQRTN("Qp_sqrt",D);
    2420           0 :   z = gmul2n(gsub(z, b), -1);
    2421             : 
    2422           0 :   z = gadd(u, gmul(v, z));
    2423           0 :   if (typ(z) != t_PADIC) /* t_INTMOD for t_QUAD of t_INTMODs... */
    2424           0 :     z = cvtop(z, p, d);
    2425           0 :   return gerepileupto(av, z);
    2426             : }
    2427             : static GEN
    2428          14 : ctop(GEN x, GEN p, long d)
    2429             : {
    2430          14 :   pari_sp av = avma;
    2431          14 :   GEN z, u = gel(x,1), v = gel(x,2);
    2432          14 :   if (isrationalzero(v)) return cvtop(u, p, d);
    2433          14 :   z = Qp_sqrt(cvtop(gen_m1, p, d - gvaluation(v, p))); /* = I */
    2434          14 :   if (!z) pari_err_SQRTN("Qp_sqrt",gen_m1);
    2435             : 
    2436          14 :   z = gadd(u, gmul(v, z));
    2437          14 :   if (typ(z) != t_PADIC) /* t_INTMOD for t_COMPLEX of t_INTMODs... */
    2438           0 :     z = cvtop(z, p, d);
    2439          14 :   return gerepileupto(av, z);
    2440             : }
    2441             : 
    2442             : /* cvtop2(stoi(s), y) */
    2443             : GEN
    2444           0 : cvstop2(long s, GEN y)
    2445             : {
    2446           0 :   GEN z, p = gel(y,2);
    2447           0 :   long v, d = signe(gel(y,4))? precp(y): 0;
    2448           0 :   if (!s) return zeropadic(p, d);
    2449           0 :   v = z_pvalrem(s, p, &s);
    2450           0 :   if (d <= 0) return zeropadic(p, v);
    2451           0 :   z = cgetg(5, t_PADIC);
    2452           0 :   z[1] = evalprecp(d) | evalvalp(v);
    2453           0 :   gel(z,2) = p;
    2454           0 :   gel(z,3) = gel(y,3);
    2455           0 :   gel(z,4) = modsi(s, gel(y,3)); return z;
    2456             : }
    2457             : 
    2458             : /* cvtop(x, gel(y,2), precp(y)), shallow */
    2459             : GEN
    2460      263107 : cvtop2(GEN x, GEN y)
    2461             : {
    2462      263107 :   GEN z, p = gel(y,2);
    2463      263107 :   long v, d = signe(gel(y,4))? precp(y): 0;
    2464      263107 :   switch(typ(x))
    2465             :   {
    2466             :     case t_INT:
    2467      232440 :       if (!signe(x)) return zeropadic(p, d);
    2468      232440 :       if (d <= 0) return zeropadic(p, Z_pval(x,p));
    2469      227995 :       v = Z_pvalrem(x, p, &x);
    2470      227987 :       z = cgetg(5, t_PADIC);
    2471      227996 :       z[1] = evalprecp(d) | evalvalp(v);
    2472      227994 :       gel(z,2) = p;
    2473      227994 :       gel(z,3) = gel(y,3);
    2474      227994 :       gel(z,4) = modii(x, gel(y,3)); return z;
    2475             : 
    2476             :     case t_INTMOD:
    2477           0 :       v = Z_pval(gel(x,1),p); if (v > d) v = d;
    2478           0 :       return cvtop(gel(x,2), p, v);
    2479             : 
    2480             :     case t_FRAC:
    2481             :     {
    2482             :       GEN num, den;
    2483       30646 :       if (d <= 0) return zeropadic(p, Q_pval(x,p));
    2484       29365 :       num = gel(x,1); v = Z_pvalrem(num, p, &num);
    2485       29365 :       den = gel(x,2); if (!v) v = -Z_pvalrem(den, p, &den);
    2486       29365 :       z = cgetg(5, t_PADIC);
    2487       29365 :       z[1] = evalprecp(d) | evalvalp(v);
    2488       29365 :       gel(z,2) = p;
    2489       29365 :       gel(z,3) = gel(y,3);
    2490       29365 :       if (!is_pm1(den)) num = mulii(num, Fp_inv(den, gel(y,3)));
    2491       29365 :       gel(z,4) = modii(num, gel(y,3)); return z;
    2492             :     }
    2493           7 :     case t_COMPLEX: return ctop(x, p, d);
    2494          14 :     case t_QUAD:    return qtop(x, p, d);
    2495             :   }
    2496           0 :   pari_err_TYPE("cvtop2",x);
    2497             :   return NULL; /* LCOV_EXCL_LINE */
    2498             : }
    2499             : 
    2500             : /* assume is_const_t(tx) */
    2501             : GEN
    2502       44991 : cvtop(GEN x, GEN p, long d)
    2503             : {
    2504             :   GEN z;
    2505             :   long v;
    2506             : 
    2507       44991 :   if (typ(p) != t_INT) pari_err_TYPE("cvtop",p);
    2508       44991 :   switch(typ(x))
    2509             :   {
    2510             :     case t_INT:
    2511       30046 :       if (!signe(x)) return zeropadic(p, d);
    2512       28870 :       if (d <= 0) return zeropadic(p, Z_pval(x,p));
    2513       28870 :       v = Z_pvalrem(x, p, &x);
    2514       28870 :       z = cgetg(5, t_PADIC);
    2515       28870 :       z[1] = evalprecp(d) | evalvalp(v);
    2516       28870 :       gel(z,2) = icopy(p);
    2517       28870 :       gel(z,3) = powiu(p, d);
    2518       28870 :       gel(z,4) = modii(x, gel(z,3)); return z; /* not memory-clean */
    2519             : 
    2520             :     case t_INTMOD:
    2521           0 :       v = Z_pval(gel(x,1),p); if (v > d) v = d;
    2522           0 :       return cvtop(gel(x,2), p, v);
    2523             : 
    2524             :     case t_FRAC:
    2525             :     {
    2526             :       GEN num, den;
    2527        7168 :       if (d <= 0) return zeropadic(p, Q_pval(x,p));
    2528        7168 :       num = gel(x,1); v = Z_pvalrem(num, p, &num);
    2529        7168 :       den = gel(x,2); if (!v) v = -Z_pvalrem(den, p, &den);
    2530        7168 :       z = cgetg(5, t_PADIC);
    2531        7168 :       z[1] = evalprecp(d) | evalvalp(v);
    2532        7168 :       gel(z,2) = icopy(p);
    2533        7168 :       gel(z,3) = powiu(p, d);
    2534        7168 :       if (!is_pm1(den)) num = mulii(num, Fp_inv(den, gel(z,3)));
    2535        7168 :       gel(z,4) = modii(num, gel(z,3)); return z; /* not memory-clean */
    2536             :     }
    2537           7 :     case t_COMPLEX: return ctop(x, p, d);
    2538             :     case t_PADIC:
    2539        7770 :       p = gel(x,2); /* override */
    2540        7770 :       if (!signe(gel(x,4))) return zeropadic(p, d);
    2541        7770 :       z = cgetg(5,t_PADIC);
    2542        7770 :       z[1] = x[1]; setprecp(z,d);
    2543        7770 :       gel(z,2) = icopy(p);
    2544        7770 :       gel(z,3) = powiu(p, d);
    2545        7770 :       gel(z,4) = modii(gel(x,4), gel(z,3)); return z;
    2546             : 
    2547           0 :     case t_QUAD: return qtop(x, p, d);
    2548             :   }
    2549           0 :   pari_err_TYPE("cvtop",x);
    2550             :   return NULL; /* LCOV_EXCL_LINE */
    2551             : }
    2552             : 
    2553             : GEN
    2554          28 : gcvtop(GEN x, GEN p, long r)
    2555             : {
    2556             :   long i, lx;
    2557             :   GEN y;
    2558             : 
    2559          28 :   switch(typ(x))
    2560             :   {
    2561             :     case t_POL: case t_SER:
    2562           7 :       y = cgetg_copy(x, &lx); y[1] = x[1];
    2563           7 :       for (i=2; i<lx; i++) gel(y,i) = gcvtop(gel(x,i),p,r);
    2564           7 :       return y;
    2565             :     case t_POLMOD: case t_RFRAC: case t_VEC: case t_COL: case t_MAT:
    2566           0 :       y = cgetg_copy(x, &lx);
    2567           0 :       for (i=1; i<lx; i++) gel(y,i) = gcvtop(gel(x,i),p,r);
    2568           0 :       return y;
    2569             :   }
    2570          21 :   return cvtop(x,p,r);
    2571             : }
    2572             : 
    2573             : long
    2574    67487974 : gexpo(GEN x)
    2575             : {
    2576    67487974 :   long tx = typ(x), lx, e, f, i;
    2577             : 
    2578    67487974 :   switch(tx)
    2579             :   {
    2580             :     case t_INT:
    2581    17673863 :       return expi(x);
    2582             : 
    2583             :     case t_FRAC:
    2584      296521 :       return expi(gel(x,1)) - expi(gel(x,2));
    2585             : 
    2586             :     case t_REAL:
    2587    34087597 :       return expo(x);
    2588             : 
    2589             :     case t_COMPLEX:
    2590     8665024 :       e = gexpo(gel(x,1));
    2591     8665024 :       f = gexpo(gel(x,2)); return maxss(e, f);
    2592             : 
    2593             :     case t_QUAD: {
    2594          21 :       GEN p = gel(x,1); /* mod = X^2 + {0,1}* X - {D/4, (1-D)/4})*/
    2595          21 :       long d = 1 + expi(gel(p,2))/2; /* ~ expo(sqrt(D)) */
    2596          21 :       e = gexpo(gel(x,2));
    2597          21 :       f = gexpo(gel(x,3)) + d; return maxss(e, f);
    2598             :     }
    2599             :     case t_POL: case t_SER:
    2600     6602438 :       lx = lg(x); f = -(long)HIGHEXPOBIT;
    2601     6602438 :       for (i=2; i<lx; i++) { e=gexpo(gel(x,i)); if (e>f) f=e; }
    2602     6602438 :       return f;
    2603             :     case t_VEC: case t_COL: case t_MAT:
    2604      162503 :       lx = lg(x); f = -(long)HIGHEXPOBIT;
    2605      162503 :       for (i=1; i<lx; i++) { e=gexpo(gel(x,i)); if (e>f) f=e; }
    2606      162503 :       return f;
    2607             :   }
    2608           7 :   pari_err_TYPE("gexpo",x);
    2609             :   return 0; /* LCOV_EXCL_LINE */
    2610             : }
    2611             : 
    2612             : long
    2613           7 : sizedigit(GEN x)
    2614             : {
    2615           7 :   return gequal0(x)? 0: (long) ((gexpo(x)+1) * LOG10_2) + 1;
    2616             : }
    2617             : 
    2618             : /* normalize series. avma is not updated */
    2619             : GEN
    2620     5885222 : normalize(GEN x)
    2621             : {
    2622     5885222 :   long i, lx = lg(x), vx=varn(x), vp=valp(x);
    2623             :   GEN y, z;
    2624             : 
    2625     5885222 :   if (typ(x) != t_SER) pari_err_TYPE("normalize",x);
    2626     5885222 :   if (lx == 2) { setsigne(x,0); return x; }
    2627     5884830 :   if (lx == 3) {
    2628       96382 :     z = gel(x,2);
    2629       96382 :     if (!gequal0(z)) { setsigne(x,1); return x; }
    2630        4612 :     if (isrationalzero(z)) return zeroser(vx,vp+1);
    2631        1616 :     if (isexactzero(z)) {
    2632             :       /* dangerous case: already normalized ? */
    2633          14 :       if (!signe(x)) return x;
    2634          14 :       setvalp(x,vp+1); /* no: normalize */
    2635             :     }
    2636        1616 :     setsigne(x,0); return x;
    2637             :   }
    2638     5830018 :   for (i=2; i<lx; i++)
    2639     5827631 :     if (! isrationalzero(gel(x,i))) break;
    2640     5788448 :   if (i == lx) return zeroser(vx,lx-2+vp);
    2641     5786061 :   z = gel(x,i);
    2642     5786061 :   while (i<lx && isexactzero(gel(x,i))) i++;
    2643     5786061 :   if (i == lx)
    2644             :   {
    2645         238 :     i -= 3; y = x + i;
    2646         238 :     stackdummy((pari_sp)y, (pari_sp)x);
    2647         238 :     gel(y,2) = z;
    2648         238 :     y[1] = evalsigne(0) | evalvalp(lx-2+vp) | evalvarn(vx);
    2649         238 :     y[0] = evaltyp(t_SER) | _evallg(3);
    2650         238 :     return y;
    2651             :   }
    2652             : 
    2653     5785823 :   i -= 2; y = x + i; lx -= i;
    2654     5785823 :   y[1] = evalsigne(1) | evalvalp(vp+i) | evalvarn(vx);
    2655     5785823 :   y[0] = evaltyp(t_SER) | evallg(lx);
    2656             : 
    2657     5785823 :   stackdummy((pari_sp)y, (pari_sp)x);
    2658     5798508 :   for (i = 2; i < lx; i++)
    2659     5797901 :     if (!gequal0(gel(y, i))) return y;
    2660         607 :   setsigne(y, 0); return y;
    2661             : }
    2662             : 
    2663             : GEN
    2664         665 : normalizepol_approx(GEN x, long lx)
    2665             : {
    2666             :   long i;
    2667         665 :   for (i = lx-1; i>1; i--)
    2668         665 :     if (! gequal0(gel(x,i))) break;
    2669         665 :   stackdummy((pari_sp)(x + lg(x)), (pari_sp)(x + i+1));
    2670         665 :   setlg(x, i+1); setsigne(x, i!=1); return x;
    2671             : }
    2672             : 
    2673             : GEN
    2674   168205677 : normalizepol_lg(GEN x, long lx)
    2675             : {
    2676   168205677 :   long i, LX = 0;
    2677   168205677 :   GEN KEEP = NULL;
    2678             : 
    2679   211504401 :   for (i = lx-1; i>1; i--)
    2680             :   {
    2681   193927389 :     GEN z = gel(x,i);
    2682   193927389 :     if (! gequal0(z) ) {
    2683   150628047 :       if (!LX) LX = i+1;
    2684   150628047 :       stackdummy((pari_sp)(x + lg(x)), (pari_sp)(x + LX));
    2685   150627647 :       x[0] = evaltyp(t_POL) | evallg(LX);
    2686   150627393 :       setsigne(x,1); return x;
    2687    43298725 :     } else if (!isexactzero(z)) {
    2688      156376 :       if (!LX) LX = i+1; /* to be kept as leading coeff */
    2689    43142348 :     } else if (!isrationalzero(z))
    2690      686896 :       KEEP = z; /* to be kept iff all other coeffs are exact 0s */
    2691             :   }
    2692    17577012 :   if (!LX) {
    2693    17558244 :     if (KEEP) { /* e.g. Pol(Mod(0,2)) */
    2694      330151 :       gel(x,2) = KEEP;
    2695      330151 :       LX = 3;
    2696             :     } else
    2697    17228093 :       LX = 2; /* Pol(0) */
    2698             :   }
    2699    17577012 :   stackdummy((pari_sp)(x + lg(x)), (pari_sp)(x + LX));
    2700    17577012 :   x[0] = evaltyp(t_POL) | evallg(LX);
    2701    17577012 :   setsigne(x,0); return x;
    2702             : }
    2703             : 
    2704             : /* normalize polynomial x in place */
    2705             : GEN
    2706      100784 : normalizepol(GEN x)
    2707             : {
    2708      100784 :   return normalizepol_lg(x, lg(x));
    2709             : }
    2710             : 
    2711             : int
    2712     2962323 : gsigne(GEN x)
    2713             : {
    2714     2962323 :   switch(typ(x))
    2715             :   {
    2716     2926157 :     case t_INT: case t_REAL: return signe(x);
    2717       33569 :     case t_FRAC: return signe(gel(x,1));
    2718             :     case t_QUAD:
    2719             :     {
    2720         112 :       pari_sp av = avma;
    2721         112 :       GEN T = gel(x,1), a = gel(x,2), b = gel(x,3);
    2722             :       long sa, sb;
    2723         112 :       if (signe(gel(T,2)) > 0) break;
    2724          98 :       a = gmul2n(a,1);
    2725          98 :       if (signe(gel(T,3))) a = gadd(a,b);
    2726             :       /* a + b sqrt(D) > 0 ? */
    2727          98 :       sa = gsigne(a);
    2728          98 :       sb = gsigne(b); if (sa == sb) { avma = av; return sa; }
    2729          77 :       if (sa == 0) { avma = av; return sb; }
    2730          70 :       if (sb == 0) { avma = av; return sa; }
    2731             :       /* different signs, take conjugate expression */
    2732          70 :       sb = gsigne(gsub(gsqr(a), gmul(quad_disc(x), gsqr(b))));
    2733          70 :       avma = av; return sb * sa;
    2734             :     }
    2735        2485 :     case t_INFINITY: return inf_get_sign(x);
    2736             :   }
    2737          14 :   pari_err_TYPE("gsigne",x);
    2738             :   return 0; /* LCOV_EXCL_LINE */
    2739             : }
    2740             : 
    2741             : /*******************************************************************/
    2742             : /*                                                                 */
    2743             : /*                              LISTS                              */
    2744             : /*                                                                 */
    2745             : /*******************************************************************/
    2746             : /* make sure L can hold l elements, at least doubling the previous max number
    2747             :  * of components. */
    2748             : static void
    2749      786023 : ensure_nb(GEN L, long l)
    2750             : {
    2751      786023 :   long nmax = list_nmax(L), i, lw;
    2752             :   GEN v, w;
    2753     1572046 :   if (l <= nmax) return;
    2754         322 :   if (nmax)
    2755             :   {
    2756         273 :     nmax <<= 1;
    2757         273 :     if (l > nmax) nmax = l;
    2758         273 :     w = list_data(L); lw = lg(w);
    2759         273 :     v = newblock(nmax+1);
    2760         273 :     v[0] = w[0];
    2761         273 :     for (i=1; i < lw; i++) gel(v,i) = gel(w, i);
    2762         273 :     killblock(w);
    2763             :   }
    2764             :   else /* unallocated */
    2765             :   {
    2766          49 :     nmax = 32;
    2767          49 :     if (list_data(L))
    2768           0 :       pari_err(e_MISC, "store list in variable before appending elements");
    2769          49 :     v = newblock(nmax+1);
    2770          49 :     v[0] = evaltyp(t_VEC) | _evallg(1);
    2771             :   }
    2772         322 :   list_data(L) = v;
    2773         322 :   L[1] = evaltyp(list_typ(L))|evallg(nmax);
    2774             : }
    2775             : 
    2776             : void
    2777           7 : listkill(GEN L)
    2778             : {
    2779             : 
    2780           7 :   if (typ(L) != t_LIST) pari_err_TYPE("listkill",L);
    2781           7 :   if (list_nmax(L)) {
    2782           7 :     GEN v = list_data(L);
    2783           7 :     long i, l = lg(v);
    2784           7 :     for (i=1; i<l; i++) gunclone_deep(gel(v,i));
    2785           7 :     killblock(v);
    2786           7 :     L[1] = evaltyp(list_typ(L));
    2787           7 :     list_data(L) = NULL;
    2788             :   }
    2789           7 : }
    2790             : 
    2791             : GEN
    2792         729 : mklist_typ(long t)
    2793             : {
    2794         729 :   GEN L = cgetg(3,t_LIST);
    2795         729 :   L[1] = evaltyp(t);
    2796         729 :   list_data(L) = NULL; return L;
    2797             : }
    2798             : 
    2799             : GEN
    2800         687 : mklist(void)
    2801             : {
    2802         687 :   return mklist_typ(t_LIST_RAW);
    2803             : }
    2804             : 
    2805             : GEN
    2806          35 : mkmap(void)
    2807             : {
    2808          35 :   return mklist_typ(t_LIST_MAP);
    2809             : }
    2810             : 
    2811             : /* return a list with single element x, allocated on stack */
    2812             : GEN
    2813          49 : mklistcopy(GEN x)
    2814             : {
    2815          49 :   GEN y = mklist();
    2816          49 :   list_data(y) = mkveccopy(x);
    2817          49 :   return y;
    2818             : }
    2819             : 
    2820             : GEN
    2821           7 : listcreate_gp(long n)
    2822             : {
    2823           7 :   (void) n; return mklist();
    2824             : }
    2825             : 
    2826             : GEN
    2827      751051 : listput(GEN L, GEN x, long index)
    2828             : {
    2829             :   long l;
    2830             :   GEN z;
    2831             : 
    2832      751051 :   if (index < 0) pari_err_COMPONENT("listput", "<", gen_0, stoi(index));
    2833      751044 :   z = list_data(L);
    2834      751044 :   l = z? lg(z): 1;
    2835             : 
    2836      751044 :   x = gclone(x);
    2837      751044 :   if (!index || index >= l)
    2838             :   {
    2839      751023 :     ensure_nb(L, l);
    2840      751023 :     z = list_data(L); /* it may change ! */
    2841      751023 :     index = l;
    2842      751023 :     l++;
    2843             :   } else
    2844          21 :     gunclone_deep( gel(z, index) );
    2845      751044 :   gel(z,index) = x;
    2846      751044 :   z[0] = evaltyp(t_VEC) | evallg(l); /*must be after gel(z,index) is set*/
    2847      751044 :   return gel(z,index);
    2848             : }
    2849             : 
    2850             : GEN
    2851      700049 : listput0(GEN L, GEN x, long index)
    2852             : {
    2853      700049 :   if (typ(L) != t_LIST || list_typ(L) != t_LIST_RAW)
    2854           0 :     pari_err_TYPE("listput",L);
    2855      700049 :   return listput(L, x, index);
    2856             : }
    2857             : 
    2858             : GEN
    2859       35014 : listinsert(GEN L, GEN x, long index)
    2860             : {
    2861             :   long l, i;
    2862             :   GEN z;
    2863             : 
    2864       35014 :   if (typ(L) != t_LIST || list_typ(L) != t_LIST_RAW)
    2865           0 :     pari_err_TYPE("listinsert",L);
    2866       35014 :   z = list_data(L); l = z? lg(z): 1;
    2867       35014 :   if (index <= 0) pari_err_COMPONENT("listinsert", "<=", gen_0, stoi(index));
    2868       35007 :   if (index > l) pari_err_COMPONENT("listinsert", ">", stoi(l), stoi(index));
    2869       35000 :   ensure_nb(L, l);
    2870       35000 :   BLOCK_SIGINT_START
    2871       35000 :   z = list_data(L);
    2872       35000 :   for (i=l; i > index; i--) gel(z,i) = gel(z,i-1);
    2873       35000 :   z[0] = evaltyp(t_VEC) | evallg(l+1);
    2874       35000 :   gel(z,index) = gclone(x);
    2875       35000 :   BLOCK_SIGINT_END
    2876       35000 :   return gel(z,index);
    2877             : }
    2878             : 
    2879             : void
    2880       21910 : listpop(GEN L, long index)
    2881             : {
    2882             :   long l, i;
    2883             :   GEN z;
    2884             : 
    2885       21910 :   if (typ(L) != t_LIST) pari_err_TYPE("listinsert",L);
    2886       21910 :   if (index < 0) pari_err_COMPONENT("listpop", "<", gen_0, stoi(index));
    2887       21910 :   z = list_data(L);
    2888       43820 :   if (!z || (l = lg(z)-1) == 0) return;
    2889             : 
    2890       21896 :   if (!index || index > l) index = l;
    2891       21896 :   BLOCK_SIGINT_START
    2892       21896 :   gunclone_deep( gel(z, index) );
    2893       21896 :   z[0] = evaltyp(t_VEC) | evallg(l);
    2894       21896 :   for (i=index; i < l; i++) z[i] = z[i+1];
    2895       21896 :   BLOCK_SIGINT_END
    2896             : }
    2897             : 
    2898             : void
    2899          35 : listpop0(GEN L, long index)
    2900             : {
    2901          35 :   if (typ(L) != t_LIST || list_typ(L) != t_LIST_RAW)
    2902           0 :     pari_err_TYPE("listpop",L);
    2903          35 :   listpop(L, index);
    2904          35 : }
    2905             : 
    2906             : /* return a copy fully allocated on stack. gclone from changevalue is
    2907             :  * supposed to malloc() it */
    2908             : GEN
    2909         410 : gtolist(GEN x)
    2910             : {
    2911             :   GEN y;
    2912             : 
    2913         410 :   if (!x) return mklist();
    2914         287 :   switch(typ(x))
    2915             :   {
    2916             :     case t_VEC: case t_COL:
    2917         238 :       y = mklist();
    2918         238 :       if (lg(x) == 1) return y;
    2919         224 :       list_data(y) = gcopy(x);
    2920         224 :       settyp(list_data(y), t_VEC);
    2921         224 :       return y;
    2922             :     case t_LIST:
    2923           0 :       y = mklist();
    2924           0 :       list_data(y) = list_data(x)? gcopy(list_data(x)): NULL;
    2925           0 :       return y;
    2926             :     default:
    2927          49 :       return mklistcopy(x);
    2928             :   }
    2929             : }
    2930             : 
    2931             : void
    2932          21 : listsort(GEN L, long flag)
    2933             : {
    2934             :   long i, l;
    2935          21 :   pari_sp av = avma;
    2936             :   GEN perm, v, vnew;
    2937             : 
    2938          21 :   if (typ(L) != t_LIST) pari_err_TYPE("listsort",L);
    2939          21 :   v = list_data(L); l = v? lg(v): 1;
    2940          42 :   if (l < 3) return;
    2941          21 :   if (flag)
    2942             :   {
    2943             :     long lnew;
    2944          14 :     perm = gen_indexsort_uniq(L, (void*)&cmp_universal, cmp_nodata);
    2945          14 :     lnew = lg(perm); /* may have changed since 'uniq' */
    2946          14 :     vnew = cgetg(lnew,t_VEC);
    2947          56 :     for (i=1; i<lnew; i++) {
    2948          42 :       long c = perm[i];
    2949          42 :       gel(vnew,i) = gel(v,c);
    2950          42 :       gel(v,c) = NULL;
    2951             :     }
    2952          14 :     if (l != lnew) { /* was shortened */
    2953         105 :       for (i=1; i<l; i++)
    2954          91 :         if (gel(v,i)) gunclone_deep(gel(v,i));
    2955          14 :       l = lnew;
    2956             :     }
    2957             :   }
    2958             :   else
    2959             :   {
    2960           7 :     perm = gen_indexsort(L, (void*)&cmp_universal, cmp_nodata);
    2961           7 :     vnew = cgetg(l,t_VEC);
    2962           7 :     for (i=1; i<l; i++) gel(vnew,i) = gel(v,perm[i]);
    2963             :   }
    2964          21 :   for (i=1; i<l; i++) gel(v,i) = gel(vnew,i);
    2965          21 :   v[0] = vnew[0]; avma = av;
    2966             : }

Generated by: LCOV version 1.11