Code coverage tests

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

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

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

LCOV - code coverage report
Current view: top level - basemath - gen2.c (source / functions) Hit Total Coverage
Test: PARI/GP v2.14.0 lcov report (development 27775-aca467eab2) Lines: 1566 1757 89.1 %
Date: 2022-07-03 07:33:15 Functions: 146 154 94.8 %
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; either version 2 of the License, or (at your option) any later
       8             : version. It is distributed in the hope that it will be useful, but WITHOUT
       9             : ANY WARRANTY WHATSOEVER.
      10             : 
      11             : Check the License for details. You should have received a copy of it, along
      12             : with the package; see the file 'COPYING'. If not, write to the Free Software
      13             : Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. */
      14             : 
      15             : /********************************************************************/
      16             : /**                                                                **/
      17             : /**                      GENERIC OPERATIONS                        **/
      18             : /**                        (second part)                           **/
      19             : /**                                                                **/
      20             : /********************************************************************/
      21             : #include "pari.h"
      22             : #include "paripriv.h"
      23             : 
      24             : /*********************************************************************/
      25             : /**                                                                 **/
      26             : /**                MAP FUNCTIONS WITH GIVEN PROTOTYPES              **/
      27             : /**                                                                 **/
      28             : /*********************************************************************/
      29             : GEN
      30         455 : map_proto_G(GEN (*f)(GEN), GEN x)
      31             : {
      32         455 :   if (is_matvec_t(typ(x))) pari_APPLY_same(map_proto_G(f, gel(x,i)));
      33         455 :   return f(x);
      34             : }
      35             : 
      36             : GEN
      37    39081418 : map_proto_lG(long (*f)(GEN), GEN x)
      38             : {
      39    39081502 :   if (is_matvec_t(typ(x))) pari_APPLY_same(map_proto_lG(f, gel(x,i)));
      40    39074709 :   return stoi(f(x));
      41             : }
      42             : 
      43             : GEN
      44         126 : map_proto_lGL(long (*f)(GEN,long), GEN x, long y)
      45             : {
      46         154 :   if (is_matvec_t(typ(x))) pari_APPLY_same(map_proto_lGL(f,gel(x,i),y));
      47         119 :   return stoi(f(x,y));
      48             : }
      49             : 
      50             : static GEN
      51     2186284 : _domul(void *data, GEN x, GEN y)
      52             : {
      53     2186284 :   GEN (*mul)(GEN,GEN)=(GEN (*)(GEN,GEN)) data;
      54     2186284 :   return mul(x,y);
      55             : }
      56             : 
      57             : GEN
      58     2131187 : gassoc_proto(GEN (*f)(GEN,GEN), GEN x, GEN y)
      59             : {
      60     2131187 :   if (!y)
      61             :   {
      62     2131187 :     pari_sp av = avma;
      63     2131187 :     switch(typ(x))
      64             :     {
      65          21 :       case t_LIST:
      66          21 :         x = list_data(x); if (!x) return gen_1;
      67             :       case t_VEC:
      68     2131173 :       case t_COL: break;
      69           7 :       default: pari_err_TYPE("association",x);
      70             :     }
      71     2131173 :     return gerepileupto(av, gen_product(x, (void *)f, _domul));
      72             : 
      73             :   }
      74           0 :   return f(x,y);
      75             : }
      76             : /*******************************************************************/
      77             : /*                                                                 */
      78             : /*                    CREATION OF A P-ADIC GEN                     */
      79             : /*                                                                 */
      80             : /*******************************************************************/
      81             : GEN
      82    16295422 : cgetp(GEN x)
      83             : {
      84    16295422 :   GEN y = cgetg(5,t_PADIC);
      85    16295391 :   y[1] = (x[1]&PRECPBITS) | _evalvalp(0);
      86    16295391 :   gel(y,2) = icopy(gel(x,2));
      87    16295381 :   gel(y,3) = icopy(gel(x,3));
      88    16295454 :   gel(y,4) = cgeti(lgefint(gel(x,3))); return y;
      89             : }
      90             : 
      91             : /*******************************************************************/
      92             : /*                                                                 */
      93             : /*                            SIZES                                */
      94             : /*                                                                 */
      95             : /*******************************************************************/
      96             : 
      97             : long
      98     4990662 : glength(GEN x)
      99             : {
     100     4990662 :   long tx = typ(x);
     101     4990662 :   switch(tx)
     102             :   {
     103         126 :     case t_INT:  return lgefint(x)-2;
     104         539 :     case t_LIST: {
     105         539 :       GEN L = list_data(x);
     106         539 :       return L? lg(L)-1: 0;
     107             :     }
     108          14 :     case t_REAL: return signe(x)? lg(x)-2: 0;
     109          11 :     case t_STR:  return strlen( GSTR(x) );
     110          91 :     case t_VECSMALL: return lg(x)-1;
     111             :   }
     112     4989881 :   return lg(x) - lontyp[tx];
     113             : }
     114             : 
     115             : GEN
     116         147 : matsize(GEN x)
     117             : {
     118         147 :   long L = lg(x) - 1;
     119         147 :   switch(typ(x))
     120             :   {
     121           7 :     case t_VEC: return mkvec2s(1, L);
     122           7 :     case t_COL: return mkvec2s(L, 1);
     123         126 :     case t_MAT: return mkvec2s(L? nbrows(x): 0, L);
     124             :   }
     125           7 :   pari_err_TYPE("matsize",x);
     126             :   return NULL; /* LCOV_EXCL_LINE */
     127             : }
     128             : 
     129             : /*******************************************************************/
     130             : /*                                                                 */
     131             : /*                 CONVERSION GEN --> long                         */
     132             : /*                                                                 */
     133             : /*******************************************************************/
     134             : 
     135             : long
     136          77 : gtolong(GEN x)
     137             : {
     138          77 :   switch(typ(x))
     139             :   {
     140          42 :     case t_INT:
     141          42 :       return itos(x);
     142           7 :     case t_REAL:
     143           7 :       return (long)(rtodbl(x) + 0.5);
     144           7 :     case t_FRAC:
     145           7 :     { pari_sp av = avma; return gc_long(av, itos(ground(x))); }
     146           7 :     case t_COMPLEX:
     147           7 :       if (gequal0(gel(x,2))) return gtolong(gel(x,1)); break;
     148           7 :     case t_QUAD:
     149           7 :       if (gequal0(gel(x,3))) return gtolong(gel(x,2)); break;
     150             :   }
     151           7 :   pari_err_TYPE("gtolong",x);
     152             :   return 0; /* LCOV_EXCL_LINE */
     153             : }
     154             : 
     155             : /*******************************************************************/
     156             : /*                                                                 */
     157             : /*                         COMPARISONS                             */
     158             : /*                                                                 */
     159             : /*******************************************************************/
     160             : int
     161   369210138 : isexactzero(GEN g)
     162             : {
     163             :   long i, lx;
     164   369210138 :   switch (typ(g))
     165             :   {
     166   313442639 :     case t_INT:
     167   313442639 :       return !signe(g);
     168     1064727 :     case t_INTMOD:
     169     1064727 :       return !signe(gel(g,2));
     170    14074378 :     case t_COMPLEX:
     171    14074378 :       return isexactzero(gel(g,1)) && isexactzero(gel(g,2));
     172     8105388 :     case t_FFELT:
     173     8105388 :       return FF_equal0(g);
     174         511 :     case t_QUAD:
     175         511 :       return isexactzero(gel(g,2)) && isexactzero(gel(g,3));
     176      261666 :     case t_POLMOD:
     177      261666 :       return isexactzero(gel(g,2));
     178    11995500 :     case t_POL:
     179    11995500 :       lx = lg(g); /* cater for Mod(0,2)*x^0 */
     180    11995500 :       return lx == 2 || (lx == 3 && isexactzero(gel(g,2)));
     181      461640 :     case t_RFRAC:
     182      461640 :       return isexactzero(gel(g,1)); /* may occur: Mod(0,2)/x */
     183       16443 :     case t_VEC: case t_COL: case t_MAT:
     184       16828 :       for (i=lg(g)-1; i; i--)
     185       16681 :         if (!isexactzero(gel(g,i))) return 0;
     186         147 :       return 1;
     187             :   }
     188    19787246 :   return 0;
     189             : }
     190             : GEN
     191    66852060 : gisexactzero(GEN g)
     192             : {
     193             :   long i, lx;
     194             :   GEN a, b;
     195    66852060 :   switch (typ(g))
     196             :   {
     197    26806891 :     case t_INT:
     198    26806891 :       return !signe(g)? g: NULL;
     199    10425205 :     case t_INTMOD:
     200    10425205 :       return !signe(gel(g,2))? g: NULL;
     201        2632 :     case t_COMPLEX:
     202        2632 :       a = gisexactzero(gel(g,1)); if (!a) return NULL;
     203         616 :       b = gisexactzero(gel(g,2)); if (!b) return NULL;
     204           0 :       return ggcd(a,b);
     205       15232 :     case t_FFELT:
     206       15232 :       return FF_equal0(g)? g: NULL;
     207         518 :     case t_QUAD:
     208         518 :       a = gisexactzero(gel(g,2)); if (!a) return NULL;
     209          77 :       b = gisexactzero(gel(g,3)); if (!b) return NULL;
     210           7 :       return ggcd(a,b);
     211       16970 :     case t_POLMOD:
     212       16970 :       return gisexactzero(gel(g,2));
     213    28054537 :     case t_POL:
     214    28054537 :       lx = lg(g); /* cater for Mod(0,2)*x^0 */
     215    28054537 :       if (lx == 2) return gen_0;
     216    22722446 :       if (lx == 3) return gisexactzero(gel(g,2));
     217    18991305 :       return NULL;
     218     1193982 :     case t_RFRAC:
     219     1193982 :       return gisexactzero(gel(g,1)); /* may occur: Mod(0,2)/x */
     220           0 :     case t_VEC: case t_COL: case t_MAT:
     221           0 :       a = gen_0;
     222           0 :       for (i=lg(g)-1; i; i--)
     223             :       {
     224           0 :         b = gisexactzero(gel(g,i));
     225           0 :         if (!b) return NULL;
     226           0 :         a = ggcd(a, b);
     227             :       }
     228           0 :       return a;
     229             :   }
     230      336093 :   return NULL;
     231             : }
     232             : 
     233             : int
     234   464504511 : isrationalzero(GEN g)
     235             : {
     236             :   long i;
     237   464504511 :   switch (typ(g))
     238             :   {
     239   283475966 :     case t_INT:
     240   283475966 :       return !signe(g);
     241    36959026 :     case t_COMPLEX:
     242    36959026 :       return isintzero(gel(g,1)) && isintzero(gel(g,2));
     243        1428 :     case t_QUAD:
     244        1428 :       return isintzero(gel(g,2)) && isintzero(gel(g,3));
     245      489263 :     case t_POLMOD:
     246      489263 :       return isrationalzero(gel(g,2));
     247    22351492 :     case t_POL: return lg(g) == 2;
     248         133 :     case t_VEC: case t_COL: case t_MAT:
     249         448 :       for (i=lg(g)-1; i; i--)
     250         315 :         if (!isrationalzero(gel(g,i))) return 0;
     251         133 :       return 1;
     252             :   }
     253   121227203 :   return 0;
     254             : }
     255             : 
     256             : int
     257  1910806699 : gequal0(GEN x)
     258             : {
     259  1910806699 :   switch(typ(x))
     260             :   {
     261  1767196912 :     case t_INT: case t_REAL: case t_POL: case t_SER:
     262  1767196912 :       return !signe(x);
     263             : 
     264     3916714 :     case t_INTMOD:
     265     3916714 :       return !signe(gel(x,2));
     266             : 
     267      643940 :     case t_FFELT:
     268      643940 :       return FF_equal0(x);
     269             : 
     270    93785060 :     case t_COMPLEX:
     271             :      /* is 0 iff norm(x) would be 0 (can happen with Re(x) and Im(x) != 0
     272             :       * only if Re(x) and Im(x) are of type t_REAL). See mp.c:addrr().
     273             :       */
     274    93785060 :       if (gequal0(gel(x,1)))
     275             :       {
     276     7383811 :         if (gequal0(gel(x,2))) return 1;
     277     6943479 :         if (typ(gel(x,1))!=t_REAL || typ(gel(x,2))!=t_REAL) return 0;
     278      283234 :         return (expo(gel(x,1))>=expo(gel(x,2)));
     279             :       }
     280    86404225 :       if (gequal0(gel(x,2)))
     281             :       {
     282     1607838 :         if (typ(gel(x,1))!=t_REAL || typ(gel(x,2))!=t_REAL) return 0;
     283     1555001 :         return (expo(gel(x,2))>=expo(gel(x,1)));
     284             :       }
     285    84800458 :       return 0;
     286             : 
     287     2772992 :     case t_PADIC:
     288     2772992 :       return !signe(gel(x,4));
     289             : 
     290        1799 :     case t_QUAD:
     291        1799 :       return gequal0(gel(x,2)) && gequal0(gel(x,3));
     292             : 
     293     8033652 :     case t_POLMOD:
     294     8033652 :       return gequal0(gel(x,2));
     295             : 
     296     6108338 :     case t_RFRAC:
     297     6108338 :       return gequal0(gel(x,1));
     298             : 
     299     7497432 :     case t_VEC: case t_COL: case t_MAT:
     300             :     {
     301             :       long i;
     302    20631500 :       for (i=lg(x)-1; i; i--)
     303    16928205 :         if (!gequal0(gel(x,i))) return 0;
     304     3703295 :       return 1;
     305             :     }
     306             :   }
     307    20849860 :   return 0;
     308             : }
     309             : 
     310             : /* x a t_POL or t_SER, return 1 if test(coeff(X,d)) is true and
     311             :  * coeff(X,i) = 0 for all i != d. Return 0 (false) otherwise */
     312             : static int
     313    14732374 : is_monomial_test(GEN x, long d, int(*test)(GEN))
     314             : {
     315    14732374 :   long i, l = lg(x);
     316    14732374 :   if (typ(x) == t_SER)
     317             :   { /* "0" * x^v * (1+O(x)) ?  v <= 0 or null ring */
     318         364 :     if (l == 3 && isexactzero(gel(x,2))) return d >= 2 || test(gel(x,2));
     319         322 :     if (d < 2) return 0; /* v > 0 */
     320             :   }
     321    14732269 :   if (d >= l)
     322             :   {
     323       68137 :     if (typ(x) == t_POL) return 0; /* l = 2 */
     324             :     /* t_SER, v = 2-d <= 0 */
     325          56 :     if (!signe(x)) return 1;
     326             :   }
     327    14664132 :   else if (!test(gel(x,d))) return 0;
     328     7362469 :   for (i = 2; i < l; i++) /* 2 <= d < l */
     329     4975726 :     if (i != d && !gequal0(gel(x,i))) return 0;
     330     2386743 :   return 1;
     331             : }
     332             : static int
     333        2135 : col_test(GEN x, int(*test)(GEN))
     334             : {
     335        2135 :   long i, l = lg(x);
     336        2135 :   if (l == 1 || !test(gel(x,1))) return 0;
     337          42 :   for (i = 2; i < l; i++)
     338          21 :     if (!gequal0(gel(x,i))) return 0;
     339          21 :   return 1;
     340             : }
     341             : static int
     342       16184 : mat_test(GEN x, int(*test)(GEN))
     343             : {
     344       16184 :   long i, j, l = lg(x);
     345       16184 :   if (l == 1) return 1;
     346       16170 :   if (l != lgcols(x)) return 0;
     347       51240 :   for (i = 1; i < l; i++)
     348      134078 :     for (j = 1; j < l; j++)
     349       99008 :       if (i == j) {
     350       35133 :         if (!test(gcoeff(x,i,i))) return 0;
     351             :       } else {
     352       63875 :         if (!gequal0(gcoeff(x,i,j))) return 0;
     353             :       }
     354       16107 :   return 1;
     355             : }
     356             : 
     357             : /* returns 1 whenever x = 1, and 0 otherwise */
     358             : int
     359   297370507 : gequal1(GEN x)
     360             : {
     361   297370507 :   switch(typ(x))
     362             :   {
     363   279104082 :     case t_INT:
     364   279104082 :       return equali1(x);
     365             : 
     366       68145 :     case t_REAL:
     367             :     {
     368       68145 :       long s = signe(x);
     369       68145 :       if (!s) return expo(x) >= 0;
     370       68047 :       return s > 0 ? absrnz_equal1(x): 0;
     371             :     }
     372      582971 :     case t_INTMOD:
     373      582971 :       return is_pm1(gel(x,2)) || is_pm1(gel(x,1));
     374      319005 :     case t_POLMOD:
     375      319005 :       return !degpol(gel(x,1)) || gequal1(gel(x,2));
     376             : 
     377       15526 :     case t_FFELT:
     378       15526 :       return FF_equal1(x);
     379             : 
     380     1218802 :     case t_FRAC:
     381     1218802 :       return 0;
     382             : 
     383       21236 :     case t_COMPLEX:
     384       21236 :       return gequal1(gel(x,1)) && gequal0(gel(x,2));
     385             : 
     386      272895 :     case t_PADIC:
     387      272895 :       if (!signe(gel(x,4))) return valp(x) <= 0;
     388      272860 :       return valp(x) == 0 && gequal1(gel(x,4));
     389             : 
     390          42 :     case t_QUAD:
     391          42 :       return gequal1(gel(x,2)) && gequal0(gel(x,3));
     392             : 
     393    14731942 :     case t_POL: return is_monomial_test(x, 2, &gequal1);
     394         238 :     case t_SER: return is_monomial_test(x, 2 - valp(x), &gequal1);
     395             : 
     396     1032071 :     case t_RFRAC: return gequal(gel(x,1), gel(x,2));
     397        2093 :     case t_COL: return col_test(x, &gequal1);
     398       16135 :     case t_MAT: return mat_test(x, &gequal1);
     399             :   }
     400          30 :   return 0;
     401             : }
     402             : 
     403             : /* returns 1 whenever the x = -1, 0 otherwise */
     404             : int
     405    74210062 : gequalm1(GEN x)
     406             : {
     407             :   pari_sp av;
     408             :   GEN t;
     409             : 
     410    74210062 :   switch(typ(x))
     411             :   {
     412    74205981 :     case t_INT:
     413    74205981 :       return equalim1(x);
     414             : 
     415        1484 :     case t_REAL:
     416             :     {
     417        1484 :       long s = signe(x);
     418        1484 :       if (!s) return expo(x) >= 0;
     419        1477 :       return s < 0 ? absrnz_equal1(x): 0;
     420             :     }
     421          28 :     case t_INTMOD:
     422          28 :       av = avma; return gc_bool(av, equalii(addui(1,gel(x,2)), gel(x,1)));
     423             : 
     424          91 :     case t_FRAC:
     425          91 :       return 0;
     426             : 
     427          42 :     case t_FFELT:
     428          42 :       return FF_equalm1(x);
     429             : 
     430        2016 :     case t_COMPLEX:
     431        2016 :       return gequalm1(gel(x,1)) && gequal0(gel(x,2));
     432             : 
     433           7 :     case t_QUAD:
     434           7 :       return gequalm1(gel(x,2)) && gequal0(gel(x,3));
     435             : 
     436          35 :     case t_PADIC:
     437          35 :       t = gel(x,4); if (!signe(t)) return valp(x) <= 0;
     438           7 :       av = avma; return gc_bool(av, !valp(x) && equalii(addui(1,t), gel(x,3)));
     439             : 
     440          56 :     case t_POLMOD:
     441          56 :       return !degpol(gel(x,1)) || gequalm1(gel(x,2));
     442             : 
     443          70 :     case t_POL: return is_monomial_test(x, 2, &gequalm1);
     444         126 :     case t_SER: return is_monomial_test(x, 2 - valp(x), &gequalm1);
     445             : 
     446          21 :     case t_RFRAC:
     447          21 :       av = avma; return gc_bool(av, gequal(gel(x,1), gneg_i(gel(x,2))));
     448          42 :     case t_COL: return col_test(x, &gequalm1);
     449          49 :     case t_MAT: return mat_test(x, &gequalm1);
     450             :   }
     451          14 :   return 0;
     452             : }
     453             : 
     454             : int
     455     1469875 : gequalX(GEN x) { return typ(x) == t_POL && lg(x) == 4
     456     2949557 :                       && isintzero(gel(x,2)) && isint1(gel(x,3)); }
     457             : 
     458             : static int
     459         483 : cmp_str(const char *x, const char *y)
     460             : {
     461         483 :   int f = strcmp(x, y);
     462             :   return f > 0? 1
     463         483 :               : f? -1: 0;
     464             : }
     465             : 
     466             : static int
     467    38312889 : cmp_universal_rec(GEN x, GEN y, long i0)
     468             : {
     469    38312889 :   long i, lx = lg(x), ly = lg(y);
     470    38312889 :   if (lx < ly) return -1;
     471    38310100 :   if (lx > ly) return 1;
     472    63047354 :   for (i = i0; i < lx; i++)
     473             :   {
     474    55469129 :     int f = cmp_universal(gel(x,i), gel(y,i));
     475    55469129 :     if (f) return f;
     476             :   }
     477     7578225 :   return 0;
     478             : }
     479             : /* Universal "meaningless" comparison function. Transitive, returns 0 iff
     480             :  * gidentical(x,y) */
     481             : int
     482    81996422 : cmp_universal(GEN x, GEN y)
     483             : {
     484    81996422 :   long lx, ly, i, tx = typ(x), ty = typ(y);
     485             : 
     486    81996422 :   if (tx < ty) return -1;
     487    81483909 :   if (ty < tx) return 1;
     488    80966929 :   switch(tx)
     489             :   {
     490    41718514 :     case t_INT: return cmpii(x,y);
     491         462 :     case t_STR: return cmp_str(GSTR(x),GSTR(y));
     492      934976 :     case t_REAL:
     493             :     case t_VECSMALL:
     494      934976 :       lx = lg(x);
     495      934976 :       ly = lg(y);
     496      934976 :       if (lx < ly) return -1;
     497      886704 :       if (lx > ly) return 1;
     498     3586362 :       for (i = 1; i < lx; i++)
     499             :       {
     500     3478730 :         if (x[i] < y[i]) return -1;
     501     3109809 :         if (x[i] > y[i]) return 1;
     502             :       }
     503      107632 :       return 0;
     504             : 
     505       17934 :     case t_POL:
     506             :     {
     507       17934 :       long X = x[1] & (VARNBITS|SIGNBITS);
     508       17934 :       long Y = y[1] & (VARNBITS|SIGNBITS);
     509       17934 :       if (X < Y) return -1;
     510       17913 :       if (X > Y) return 1;
     511       17857 :       return cmp_universal_rec(x, y, 2);
     512             :     }
     513      881076 :     case t_SER:
     514             :     case t_FFELT:
     515             :     case t_CLOSURE:
     516      881076 :       if (x[1] < y[1]) return -1;
     517      881069 :       if (x[1] > y[1]) return 1;
     518      881062 :       return cmp_universal_rec(x, y, 2);
     519             : 
     520          35 :     case t_LIST:
     521             :       {
     522          35 :         long tx = list_typ(x), ty = list_typ(y);
     523             :         GEN vx, vy;
     524             :         pari_sp av;
     525          35 :         if (tx < ty) return -1;
     526          35 :         if (tx > ty) return 1;
     527          35 :         vx = list_data(x);
     528          35 :         vy = list_data(y);
     529          35 :         if (!vx) return vy? -1: 0;
     530          35 :         if (!vy) return 1;
     531          35 :         av = avma;
     532          35 :         if (tx == t_LIST_MAP)
     533             :         {
     534          14 :           vx = maptomat_shallow(x);
     535          14 :           vy = maptomat_shallow(y);
     536             :         }
     537          35 :         return gc_int(av, cmp_universal_rec(vx, vy, 1));
     538             :       }
     539    37413932 :     default:
     540    37413932 :       return cmp_universal_rec(x, y, lontyp[tx]);
     541             :   }
     542             : }
     543             : 
     544             : static int
     545     4384870 : cmpfrac(GEN x, GEN y)
     546             : {
     547     4384870 :   pari_sp av = avma;
     548     4384870 :   GEN a = gel(x,1), b = gel(x,2);
     549     4384870 :   GEN c = gel(y,1), d = gel(y,2);
     550     4384870 :   return gc_bool(av, cmpii(mulii(a, d), mulii(b, c)));
     551             : }
     552             : static int
     553      435302 : cmpifrac(GEN a, GEN y)
     554             : {
     555      435302 :   pari_sp av = avma;
     556      435302 :   GEN c = gel(y,1), d = gel(y,2);
     557      435302 :   return gc_int(av, cmpii(mulii(a, d), c));
     558             : }
     559             : static int
     560       49680 : cmprfrac(GEN a, GEN y)
     561             : {
     562       49680 :   pari_sp av = avma;
     563       49680 :   GEN c = gel(y,1), d = gel(y,2);
     564       49680 :   return gc_int(av, cmpri(mulri(a, d), c));
     565             : }
     566             : static int
     567         161 : cmpgen(GEN x, GEN y)
     568             : {
     569         161 :   pari_sp av = avma;
     570         161 :   return gc_int(av, gsigne(gsub(x,y)));
     571             : }
     572             : 
     573             : /* returns the sign of x - y when it makes sense. 0 otherwise */
     574             : int
     575   256715773 : gcmp(GEN x, GEN y)
     576             : {
     577   256715773 :   long tx = typ(x), ty = typ(y);
     578             : 
     579   256715773 :   if (tx == ty) /* generic case */
     580   255703397 :     switch(tx)
     581             :     {
     582   139627077 :       case t_INT:  return cmpii(x, y);
     583   111605198 :       case t_REAL: return cmprr(x, y);
     584     4384870 :       case t_FRAC: return cmpfrac(x, y);
     585          70 :       case t_QUAD: return cmpgen(x, y);
     586          21 :       case t_STR:  return cmp_str(GSTR(x), GSTR(y));
     587      100956 :       case t_INFINITY:
     588             :       {
     589      100956 :         long sx = inf_get_sign(x), sy = inf_get_sign(y);
     590      100956 :         if (sx < sy) return -1;
     591          21 :         if (sx > sy) return 1;
     592          14 :         return 0;
     593             :       }
     594             :     }
     595      997581 :   if (ty == t_INFINITY) return -inf_get_sign(y);
     596      925328 :   switch(tx)
     597             :   {
     598      384619 :     case t_INT:
     599             :       switch(ty)
     600             :       {
     601       89100 :         case t_REAL: return cmpir(x, y);
     602      295505 :         case t_FRAC: return cmpifrac(x, y);
     603           7 :         case t_QUAD: return cmpgen(x, y);
     604             :       }
     605           7 :       break;
     606      345073 :     case t_REAL:
     607             :       switch(ty)
     608             :       {
     609      336966 :         case t_INT:  return cmpri(x, y);
     610        8086 :         case t_FRAC: return cmprfrac(x, y);
     611          14 :         case t_QUAD: return cmpgen(x, y);
     612             :       }
     613           7 :       break;
     614      181405 :     case t_FRAC:
     615             :       switch(ty)
     616             :       {
     617      139797 :         case t_INT:  return -cmpifrac(y, x);
     618       41594 :         case t_REAL: return -cmprfrac(y, x);
     619           7 :         case t_QUAD: return cmpgen(x, y);
     620             :       }
     621           7 :       break;
     622          63 :     case t_QUAD:
     623          63 :       return cmpgen(x, y);
     624       31464 :     case t_INFINITY: return inf_get_sign(x);
     625             :   }
     626          24 :   pari_err_TYPE2("comparison",x,y);
     627             :   return 0;/*LCOV_EXCL_LINE*/
     628             : }
     629             : 
     630             : int
     631      551950 : gcmpsg(long s, GEN y)
     632             : {
     633      551950 :   switch(typ(y))
     634             :   {
     635        9709 :     case t_INT:  return cmpsi(s,y);
     636      537285 :     case t_REAL: return cmpsr(s,y);
     637        4956 :     case t_FRAC: {
     638        4956 :       pari_sp av = avma;
     639        4956 :       return gc_int(av, cmpii(mulsi(s,gel(y,2)), gel(y,1)));
     640             :     }
     641           0 :     case t_QUAD: {
     642           0 :       pari_sp av = avma;
     643           0 :       return gc_int(av, gsigne(gsubsg(s, y)));
     644             :     }
     645           0 :     case t_INFINITY: return -inf_get_sign(y);
     646             :   }
     647           0 :   pari_err_TYPE2("comparison",stoi(s),y);
     648             :   return 0; /* LCOV_EXCL_LINE */
     649             : }
     650             : 
     651             : static long
     652     1689793 : roughtype(GEN x)
     653             : {
     654     1689793 :   switch(typ(x))
     655             :   {
     656        2100 :     case t_MAT: return t_MAT;
     657       18228 :     case t_VEC: case t_COL: return t_VEC;
     658     1613514 :     case t_VECSMALL: return t_VECSMALL;
     659       55951 :     default: return t_INT;
     660             :   }
     661             : }
     662             : 
     663             : static int lexcmpsg(long x, GEN y);
     664          42 : static int lexcmpgs(GEN x, long y) { return -lexcmpsg(y,x); }
     665             : /* lexcmp(stoi(x),y), y t_VEC/t_COL/t_MAT */
     666             : static int
     667          21 : lexcmp_s_matvec(long x, GEN y)
     668             : {
     669             :   int fl;
     670          21 :   if (lg(y)==1) return 1;
     671          14 :   fl = lexcmpsg(x,gel(y,1));
     672          14 :   if (fl) return fl;
     673           7 :   return -1;
     674             : }
     675             : /* x a scalar, y a t_VEC/t_COL/t_MAT */
     676             : static int
     677         357 : lexcmp_scal_matvec(GEN x, GEN y)
     678             : {
     679             :   int fl;
     680         357 :   if (lg(y)==1) return 1;
     681         357 :   fl = lexcmp(x,gel(y,1));
     682         357 :   if (fl) return fl;
     683           7 :   return -1;
     684             : }
     685             : /* x a scalar, y a t_VECSMALL */
     686             : static int
     687          42 : lexcmp_scal_vecsmall(GEN x, GEN y)
     688             : {
     689             :   int fl;
     690          42 :   if (lg(y)==1) return 1;
     691          42 :   fl = lexcmpgs(x, y[1]);
     692          42 :   if (fl) return fl;
     693           0 :   return -1;
     694             : }
     695             : 
     696             : /* tx = ty = t_MAT, or x and y are both vect_t */
     697             : static int
     698        9898 : lexcmp_similar(GEN x, GEN y)
     699             : {
     700        9898 :   long i, lx = lg(x), ly = lg(y), l = minss(lx,ly);
     701       18298 :   for (i=1; i<l; i++)
     702             :   {
     703       16709 :     int fl = lexcmp(gel(x,i),gel(y,i));
     704       16709 :     if (fl) return fl;
     705             :   }
     706        1589 :   if (lx == ly) return 0;
     707          35 :   return (lx < ly)? -1 : 1;
     708             : }
     709             : /* x a t_VECSMALL, y a t_VEC/t_COL ~ lexcmp_similar */
     710             : static int
     711         154 : lexcmp_vecsmall_vec(GEN x, GEN y)
     712             : {
     713         154 :   long i, lx = lg(x), ly = lg(y), l = minss(lx,ly);
     714         343 :   for (i=1; i<l; i++)
     715             :   {
     716         287 :     int fl = lexcmpsg(x[i], gel(y,i));
     717         287 :     if (fl) return fl;
     718             :   }
     719          56 :   if (lx == ly) return 0;
     720          21 :   return (lx < ly)? -1 : 1;
     721             : }
     722             : 
     723             : /* x t_VEC/t_COL, y t_MAT */
     724             : static int
     725          98 : lexcmp_vec_mat(GEN x, GEN y)
     726             : {
     727             :   int fl;
     728          98 :   if (lg(x)==1) return -1;
     729          98 :   if (lg(y)==1) return 1;
     730          98 :   fl = lexcmp_similar(x,gel(y,1));
     731          98 :   if (fl) return fl;
     732           7 :   return -1;
     733             : }
     734             : /* x t_VECSMALl, y t_MAT ~ lexcmp_vec_mat */
     735             : static int
     736          42 : lexcmp_vecsmall_mat(GEN x, GEN y)
     737             : {
     738             :   int fl;
     739          42 :   if (lg(x)==1) return -1;
     740          42 :   if (lg(y)==1) return 1;
     741          42 :   fl = lexcmp_vecsmall_vec(x, gel(y,1));
     742          42 :   if (fl) return fl;
     743           0 :   return -1;
     744             : }
     745             : 
     746             : /* x a t_VECSMALL, not y */
     747             : static int
     748         196 : lexcmp_vecsmall_other(GEN x, GEN y, long ty)
     749             : {
     750         196 :   switch(ty)
     751             :   {
     752          42 :     case t_MAT: return lexcmp_vecsmall_mat(x, y);
     753         112 :     case t_VEC: return lexcmp_vecsmall_vec(x, y);
     754          42 :     default: return -lexcmp_scal_vecsmall(y, x); /*y scalar*/
     755             :   }
     756             : }
     757             : 
     758             : /* lexcmp(stoi(s), y) */
     759             : static int
     760         343 : lexcmpsg(long x, GEN y)
     761             : {
     762         343 :   switch(roughtype(y))
     763             :   {
     764          21 :     case t_MAT:
     765             :     case t_VEC:
     766          21 :       return lexcmp_s_matvec(x,y);
     767          14 :     case t_VECSMALL: /* ~ lexcmp_scal_matvec */
     768          14 :       if (lg(y)==1) return 1;
     769           7 :       return (x > y[1])? 1: -1;
     770         308 :     default: return gcmpsg(x,y);
     771             :   }
     772             : }
     773             : 
     774             : /* as gcmp for vector/matrices, using lexicographic ordering on components */
     775             : static int
     776      844725 : lexcmp_i(GEN x, GEN y)
     777             : {
     778      844725 :   const long tx = roughtype(x), ty = roughtype(y);
     779      844725 :   if (tx == ty)
     780      844074 :     switch(tx)
     781             :     {
     782        9800 :       case t_MAT:
     783        9800 :       case t_VEC: return lexcmp_similar(x,y);
     784      806652 :       case t_VECSMALL: return vecsmall_lexcmp(x,y);
     785       27622 :       default: return gcmp(x,y);
     786             :     }
     787         651 :   if (tx == t_VECSMALL) return  lexcmp_vecsmall_other(x,y,ty);
     788         518 :   if (ty == t_VECSMALL) return -lexcmp_vecsmall_other(y,x,tx);
     789             : 
     790         455 :   if (tx == t_INT) return  lexcmp_scal_matvec(x,y); /*scalar*/
     791         203 :   if (ty == t_INT) return -lexcmp_scal_matvec(y,x);
     792             : 
     793          98 :   if (ty==t_MAT) return  lexcmp_vec_mat(x,y);
     794          42 :   return -lexcmp_vec_mat(y,x); /*tx==t_MAT*/
     795             : }
     796             : int
     797      844725 : lexcmp(GEN x, GEN y)
     798             : {
     799      844725 :   pari_sp av = avma;
     800      844725 :   if (typ(x) == t_COMPLEX)
     801             :   {
     802         875 :     x = mkvec2(gel(x,1), gel(x,2));
     803         875 :     if (typ(y) == t_COMPLEX) y = mkvec2(gel(y,1), gel(y,2));
     804          49 :     else y = mkvec2(y, gen_0);
     805             :   }
     806      843850 :   else if (typ(y) == t_COMPLEX)
     807             :   {
     808          63 :     x = mkvec2(x, gen_0);
     809          63 :     y = mkvec2(gel(y,1), gel(y,2));
     810             :   }
     811      844725 :   return gc_int(av, lexcmp_i(x, y));
     812             : }
     813             : 
     814             : /*****************************************************************/
     815             : /*                                                               */
     816             : /*                          EQUALITY                             */
     817             : /*                returns 1 if x == y, 0 otherwise               */
     818             : /*                                                               */
     819             : /*****************************************************************/
     820             : /* x,y t_POL */
     821             : static int
     822     3429877 : polidentical(GEN x, GEN y)
     823             : {
     824             :   long lx;
     825     3429877 :   if (x[1] != y[1]) return 0;
     826     3429779 :   lx = lg(x); if (lg(y) != lg(x)) return 0;
     827    14935267 :   for (lx--; lx >= 2; lx--) if (!gidentical(gel(x,lx), gel(y,lx))) return 0;
     828     3429695 :   return 1;
     829             : }
     830             : /* x,y t_SER */
     831             : static int
     832          14 : seridentical(GEN x, GEN y) { return polidentical(x,y); }
     833             : /* typ(x) = typ(y) = t_VEC/COL/MAT */
     834             : static int
     835     5476744 : vecidentical(GEN x, GEN y)
     836             : {
     837             :   long i;
     838     5476744 :   if ((x[0] ^ y[0]) & (TYPBITS|LGBITS)) return 0;
     839    17418503 :   for (i = lg(x)-1; i; i--)
     840    13237508 :     if (! gidentical(gel(x,i),gel(y,i)) ) return 0;
     841     4180995 :   return 1;
     842             : }
     843             : static int
     844         205 : identicalrr(GEN x, GEN y)
     845             : {
     846         205 :   long i, lx = lg(x);
     847         205 :   if (lg(y) != lx) return 0;
     848         205 :   if (x[1] != y[1]) return 0;
     849         773 :   i=2; while (i<lx && x[i]==y[i]) i++;
     850         198 :   return (i == lx);
     851             : }
     852             : 
     853             : static int
     854          70 : closure_identical(GEN x, GEN y)
     855             : {
     856          70 :   if (lg(x)!=lg(y) || x[1]!=y[1]) return 0;
     857          56 :   if (!gidentical(gel(x,2),gel(y,2)) || !gidentical(gel(x,3),gel(y,3))
     858          56 :    || !gidentical(gel(x,4),gel(y,4))) return 0;
     859          42 :   if (lg(x)<8) return 1;
     860           0 :   return gidentical(gel(x,7),gel(y,7));
     861             : }
     862             : 
     863             : static int
     864         343 : list_cmp(GEN x, GEN y, int cmp(GEN x, GEN y))
     865             : {
     866         343 :   int t = list_typ(x);
     867             :   GEN vx, vy;
     868             :   long lvx, lvy;
     869         343 :   if (list_typ(y)!=t) return 0;
     870         343 :   vx = list_data(x);
     871         343 :   vy = list_data(y);
     872         343 :   lvx = vx ? lg(vx): 1;
     873         343 :   lvy = vy ? lg(vy): 1;
     874         343 :   if (lvx==1 && lvy==1) return 1;
     875         329 :   if (lvx != lvy) return 0;
     876         301 :   switch (t)
     877             :   {
     878         280 :   case t_LIST_MAP:
     879             :     {
     880         280 :       pari_sp av = avma;
     881         280 :       GEN mx  = maptomat_shallow(x), my = maptomat_shallow(y);
     882         280 :       int ret = gidentical(gel(mx, 1), gel(my, 1)) && cmp(gel(mx, 2), gel(my, 2));
     883         280 :       return gc_bool(av, ret);
     884             :     }
     885          21 :   default:
     886          21 :     return cmp(vx, vy);
     887             :   }
     888             : }
     889             : 
     890             : int
     891    61803548 : gidentical(GEN x, GEN y)
     892             : {
     893             :   long tx;
     894             : 
     895    61803548 :   if (x == y) return 1;
     896    58006834 :   tx = typ(x); if (typ(y) != tx) return 0;
     897    57722696 :   switch(tx)
     898             :   {
     899    19382131 :     case t_INT:
     900    19382131 :       return equalii(x,y);
     901             : 
     902         205 :     case t_REAL:
     903         205 :       return identicalrr(x,y);
     904             : 
     905       10533 :     case t_FRAC: case t_INTMOD:
     906       10533 :       return equalii(gel(x,2), gel(y,2)) && equalii(gel(x,1), gel(y,1));
     907             : 
     908          58 :     case t_COMPLEX:
     909          58 :       return gidentical(gel(x,2),gel(y,2)) && gidentical(gel(x,1),gel(y,1));
     910          14 :     case t_PADIC:
     911          14 :       return valp(x) == valp(y)
     912          14 :         && equalii(gel(x,2),gel(y,2))
     913          14 :         && equalii(gel(x,3),gel(y,3))
     914          28 :         && equalii(gel(x,4),gel(y,4));
     915        3780 :     case t_POLMOD:
     916        3780 :       return gidentical(gel(x,2),gel(y,2)) && polidentical(gel(x,1),gel(y,1));
     917     3429842 :     case t_POL:
     918     3429842 :       return polidentical(x,y);
     919          14 :     case t_SER:
     920          14 :       return seridentical(x,y);
     921          14 :     case t_FFELT:
     922          14 :       return FF_equal(x,y);
     923             : 
     924      355216 :     case t_QFB:
     925      355216 :       return equalii(gel(x,1),gel(y,1))
     926      355209 :           && equalii(gel(x,2),gel(y,2))
     927      710425 :           && equalii(gel(x,3),gel(y,3));
     928             : 
     929          14 :     case t_QUAD:
     930          14 :       return ZX_equal(gel(x,1),gel(y,1))
     931           7 :           && gidentical(gel(x,2),gel(y,2))
     932          21 :           && gidentical(gel(x,3),gel(y,3));
     933             : 
     934           7 :     case t_RFRAC:
     935           7 :       return gidentical(gel(x,1),gel(y,1)) && gidentical(gel(x,2),gel(y,2));
     936             : 
     937          70 :     case t_STR:
     938          70 :       return !strcmp(GSTR(x),GSTR(y));
     939     5476744 :     case t_VEC: case t_COL: case t_MAT:
     940     5476744 :       return vecidentical(x,y);
     941    29063844 :     case t_VECSMALL:
     942    29063844 :       return zv_equal(x,y);
     943          28 :     case t_CLOSURE:
     944          28 :       return closure_identical(x,y);
     945         161 :     case t_LIST:
     946         161 :       return list_cmp(x, y, gidentical);
     947          21 :     case t_INFINITY: return gidentical(gel(x,1),gel(y,1));
     948             :   }
     949           0 :   return 0;
     950             : }
     951             : /* x,y t_POL in the same variable */
     952             : static int
     953     7174927 : polequal(GEN x, GEN y)
     954             : {
     955             :   long lx, ly;
     956     7174927 :   if (signe(x) != signe(y)) return 0;
     957     7174899 :   lx = lg(x); ly = lg(y);
     958     7174899 :   while (lx > ly) if (!gequal0(gel(x,--lx))) return 0;
     959     7172610 :   while (ly > lx) if (!gequal0(gel(y,--ly))) return 0;
     960    25912037 :   for (lx--; lx >= 2; lx--) if (!gequal(gel(x,lx), gel(y,lx))) return 0;
     961     7128450 :   return 1;
     962             : }
     963             : 
     964             : /* x,y t_SER in the same variable */
     965             : static int
     966         357 : serequal(GEN x, GEN y)
     967             : {
     968             :   long LX, LY, lx, ly, vx, vy;
     969         357 :   if (!signe(x) && !signe(y)) return 1;
     970          56 :   lx = lg(x); vx = valp(x); LX = lx + vx;
     971          56 :   ly = lg(y); vy = valp(y); LY = ly + vy;
     972          56 :   if (LX > LY) lx = LY - vx; else ly = LX - vy;
     973      282877 :   while (lx >= 3 && ly >= 3)
     974      282821 :     if (!gequal(gel(x,--lx), gel(y,--ly))) return 0;
     975          56 :   while(--ly >= 2) if (!gequal0(gel(y,ly))) return 0;
     976          84 :   while(--lx >= 2) if (!gequal0(gel(x,lx))) return 0;
     977          49 :   return 1;
     978             : }
     979             : 
     980             : /* typ(x) = typ(y) = t_VEC/COL/MAT */
     981             : static int
     982     5431629 : vecequal(GEN x, GEN y)
     983             : {
     984             :   long i;
     985     5431629 :   if ((x[0] ^ y[0]) & (TYPBITS|LGBITS)) return 0;
     986    17970266 :   for (i = lg(x)-1; i; i--)
     987    15683032 :     if (! gequal(gel(x,i),gel(y,i)) ) return 0;
     988     2287234 :   return 1;
     989             : }
     990             : 
     991             : static int
     992     1344044 : gequal_try(GEN x, GEN y)
     993             : {
     994             :   int i;
     995     1344044 :   pari_CATCH(CATCH_ALL) {
     996         182 :     GEN E = pari_err_last();
     997         182 :     switch(err_get_num(E))
     998             :     {
     999           0 :       case e_STACK: case e_MEM: case e_ALARM:
    1000           0 :         pari_err(0, E); /* rethrow */
    1001             :     }
    1002         182 :     return 0;
    1003             :   } pari_TRY {
    1004     1344044 :     i = gequal0(gadd(x, gneg_i(y)));
    1005     1343862 :   } pari_ENDCATCH;
    1006     1343862 :   return i;
    1007             : }
    1008             : 
    1009             : int
    1010   211757384 : gequal(GEN x, GEN y)
    1011             : {
    1012             :   pari_sp av;
    1013             :   long tx, ty;
    1014             :   long i;
    1015             : 
    1016   211757384 :   if (x == y) return 1;
    1017   189509300 :   tx = typ(x);
    1018   189509300 :   ty = typ(y);
    1019   189509300 :   if (tx == ty)
    1020   184553176 :     switch(tx)
    1021             :     {
    1022   159301775 :       case t_INT:
    1023   159301775 :         return equalii(x,y);
    1024             : 
    1025        2058 :       case t_REAL:
    1026        2058 :         return equalrr(x,y);
    1027             : 
    1028     6758654 :       case t_FRAC: case t_INTMOD:
    1029     6758654 :         return equalii(gel(x,2), gel(y,2)) && equalii(gel(x,1), gel(y,1));
    1030             : 
    1031         462 :       case t_COMPLEX:
    1032         462 :         return gequal(gel(x,2),gel(y,2)) && gequal(gel(x,1),gel(y,1));
    1033         763 :       case t_PADIC:
    1034         763 :         if (!equalii(gel(x,2),gel(y,2))) return 0;
    1035         763 :         av = avma; i = gequal0(gsub(x,y)); set_avma(av);
    1036         763 :         return i;
    1037     3179518 :       case t_POLMOD:
    1038     3179518 :         if (varn(gel(x,1)) != varn(gel(y,1))) break;
    1039     3179511 :         return gequal(gel(x,2),gel(y,2)) && RgX_equal_var(gel(x,1),gel(y,1));
    1040     7183644 :       case t_POL:
    1041     7183644 :         if (varn(x) != varn(y)) break;
    1042     7174929 :         return polequal(x,y);
    1043         357 :       case t_SER:
    1044         357 :         if (varn(x) != varn(y)) break;
    1045         357 :         return serequal(x,y);
    1046             : 
    1047       55937 :       case t_FFELT:
    1048       55937 :         return FF_equal(x,y);
    1049             : 
    1050     1094551 :       case t_QFB:
    1051     1094551 :         return equalii(gel(x,1),gel(y,1))
    1052      247128 :             && equalii(gel(x,2),gel(y,2))
    1053     1341679 :             && equalii(gel(x,3),gel(y,3));
    1054             : 
    1055           7 :       case t_QUAD:
    1056           7 :         return ZX_equal(gel(x,1),gel(y,1))
    1057           0 :             && gequal(gel(x,2),gel(y,2))
    1058           7 :             && gequal(gel(x,3),gel(y,3));
    1059             : 
    1060       73717 :       case t_RFRAC:
    1061             :       {
    1062       73717 :         GEN a = gel(x,1), b = gel(x,2), c = gel(y,1), d = gel(y,2);
    1063       73717 :         if (gequal(b,d)) return gequal(a,c); /* simple case */
    1064           0 :         av = avma;
    1065           0 :         a = simplify_shallow(gmul(a,d));
    1066           0 :         b = simplify_shallow(gmul(b,c));
    1067           0 :         return gc_bool(av, gequal(a,b));
    1068             :       }
    1069             : 
    1070       63861 :       case t_STR:
    1071       63861 :         return !strcmp(GSTR(x),GSTR(y));
    1072     5431629 :       case t_VEC: case t_COL: case t_MAT:
    1073     5431629 :         return vecequal(x,y);
    1074     1406015 :       case t_VECSMALL:
    1075     1406015 :         return zv_equal(x,y);
    1076         182 :       case t_LIST:
    1077         182 :         return list_cmp(x, y, gequal);
    1078          42 :       case t_CLOSURE:
    1079          42 :         return closure_identical(x,y);
    1080          28 :       case t_INFINITY:
    1081          28 :         return gequal(gel(x,1),gel(y,1));
    1082             :     }
    1083     4964822 :   if (is_noncalc_t(tx) || is_noncalc_t(ty)) return 0;
    1084     4964809 :   if (tx == t_INT && !signe(x)) return gequal0(y);
    1085     4962254 :   if (ty == t_INT && !signe(y)) return gequal0(x);
    1086     1344044 :   (void)&av; av = avma; /* emulate volatile */
    1087     1344044 :   return gc_bool(av, gequal_try(x, y));
    1088             : }
    1089             : 
    1090             : int
    1091       39788 : gequalsg(long s, GEN x)
    1092       39788 : { pari_sp av = avma; return gc_bool(av, gequal(stoi(s), x)); }
    1093             : 
    1094             : /* a and b are t_INT, t_FRAC, t_REAL or t_COMPLEX of those. Check whether
    1095             :  * a-b is invertible */
    1096             : int
    1097       32494 : cx_approx_equal(GEN a, GEN b)
    1098             : {
    1099       32494 :   pari_sp av = avma;
    1100             :   GEN d;
    1101       32494 :   if (a == b) return 1;
    1102       24297 :   d = gsub(a,b);
    1103       24297 :   return gc_bool(av, gequal0(d) || (typ(d)==t_COMPLEX && gequal0(cxnorm(d))));
    1104             : }
    1105             : static int
    1106     1312826 : r_approx0(GEN x, long e) { return e - expo(x) > bit_prec(x); }
    1107             : /* x ~ 0 compared to reference y */
    1108             : int
    1109     1823937 : cx_approx0(GEN x, GEN y)
    1110             : {
    1111             :   GEN a, b;
    1112             :   long e;
    1113     1823937 :   switch(typ(x))
    1114             :   {
    1115         140 :     case t_COMPLEX:
    1116         140 :       a = gel(x,1); b = gel(x,2);
    1117         140 :       if (typ(a) != t_REAL)
    1118             :       {
    1119           0 :         if (!gequal0(a)) return 0;
    1120           0 :         a = NULL;
    1121             :       }
    1122         140 :       else if (!signe(a)) a = NULL;
    1123         140 :       if (typ(b) != t_REAL)
    1124             :       {
    1125           0 :         if (!gequal0(b)) return 0;
    1126           0 :         if (!a) return 1;
    1127           0 :         b = NULL;
    1128             :       }
    1129         140 :       else if (!signe(b))
    1130             :       {
    1131           0 :         if (!a) return 1;
    1132           0 :         b = NULL;
    1133             :       }
    1134             :       /* a or b is != NULL iff it is non-zero t_REAL; one of them is */
    1135         140 :       e = gexpo(y);
    1136         140 :       return (!a || r_approx0(a, e)) && (!b || r_approx0(b, e));
    1137     1312688 :     case t_REAL:
    1138     1312688 :       return !signe(x) || r_approx0(x, gexpo(y));
    1139      511109 :     default:
    1140      511109 :       return gequal0(x);
    1141             :   }
    1142             : }
    1143             : /*******************************************************************/
    1144             : /*                                                                 */
    1145             : /*                          VALUATION                              */
    1146             : /*             p is either a t_INT or a t_POL.                     */
    1147             : /*  returns the largest exponent of p dividing x when this makes   */
    1148             : /*  sense : error for types real, integermod and polymod if p does */
    1149             : /*  not divide the modulus, q-adic if q!=p.                        */
    1150             : /*                                                                 */
    1151             : /*******************************************************************/
    1152             : 
    1153             : static long
    1154         315 : minval(GEN x, GEN p)
    1155             : {
    1156         315 :   long i,k, val = LONG_MAX, lx = lg(x);
    1157        6370 :   for (i=lontyp[typ(x)]; i<lx; i++)
    1158             :   {
    1159        6055 :     k = gvaluation(gel(x,i),p);
    1160        6055 :     if (k < val) val = k;
    1161             :   }
    1162         315 :   return val;
    1163             : }
    1164             : 
    1165             : static int
    1166          91 : intdvd(GEN x, GEN y, GEN *z) { GEN r; *z = dvmdii(x,y,&r); return (r==gen_0); }
    1167             : 
    1168             : /* x t_FRAC, p t_INT, return v_p(x) */
    1169             : static long
    1170      394626 : frac_val(GEN x, GEN p) {
    1171      394626 :   long v = Z_pval(gel(x,2),p);
    1172      394626 :   if (v) return -v;
    1173      394548 :   return Z_pval(gel(x,1),p);
    1174             : }
    1175             : long
    1176     3064666 : Q_pval(GEN x, GEN p)
    1177             : {
    1178     3064666 :   if (lgefint(p) == 3) return Q_lval(x, uel(p,2));
    1179         392 :   return (typ(x)==t_INT)? Z_pval(x, p): frac_val(x, p);
    1180             : }
    1181             : 
    1182             : static long
    1183      425308 : frac_lval(GEN x, ulong p) {
    1184      425308 :   long v = Z_lval(gel(x,2),p);
    1185      425309 :   if (v) return -v;
    1186      338181 :   return Z_lval(gel(x,1),p);
    1187             : }
    1188             : long
    1189     3068996 : Q_lval(GEN x, ulong p){return (typ(x)==t_INT)? Z_lval(x, p): frac_lval(x, p);}
    1190             : 
    1191             : long
    1192     5131663 : Q_pvalrem(GEN x, GEN p, GEN *y)
    1193             : {
    1194             :   GEN a, b;
    1195             :   long v;
    1196     5131663 :   if (lgefint(p) == 3) return Q_lvalrem(x, uel(p,2), y);
    1197        5788 :   if (typ(x) == t_INT) return Z_pvalrem(x, p, y);
    1198           0 :   a = gel(x,1);
    1199           0 :   b = gel(x,2);
    1200           0 :   v = Z_pvalrem(b, p, &b);
    1201           0 :   if (v) { *y = isint1(b)? a: mkfrac(a, b); return -v; }
    1202           0 :   v = Z_pvalrem(a, p, &a);
    1203           0 :   *y = mkfrac(a, b); return v;
    1204             : }
    1205             : long
    1206     5130028 : Q_lvalrem(GEN x, ulong p, GEN *y)
    1207             : {
    1208             :   GEN a, b;
    1209             :   long v;
    1210     5130028 :   if (typ(x) == t_INT) return Z_lvalrem(x, p, y);
    1211      301679 :   a = gel(x,1);
    1212      301679 :   b = gel(x,2);
    1213      301679 :   v = Z_lvalrem(b, p, &b);
    1214      301679 :   if (v) { *y = isint1(b)? a: mkfrac(a, b); return -v; }
    1215       26096 :   v = Z_lvalrem(a, p, &a);
    1216       26096 :   *y = mkfrac(a, b); return v;
    1217             : }
    1218             : 
    1219             : long
    1220     1575098 : gvaluation(GEN x, GEN p)
    1221             : {
    1222     1575098 :   long tx = typ(x), tp;
    1223             :   pari_sp av;
    1224             : 
    1225     1575098 :   if (!p)
    1226          28 :     switch(tx)
    1227             :     {
    1228           7 :       case t_PADIC: return valp(x);
    1229           7 :       case t_POL: return RgX_val(x);
    1230           7 :       case t_SER: return valp(x);
    1231           7 :       default: pari_err_TYPE("gvaluation", x);
    1232             :     }
    1233     1575070 :   tp  = typ(p);
    1234     1575070 :   switch(tp)
    1235             :   {
    1236     1569330 :     case t_INT:
    1237     1569330 :       if (signe(p) && !is_pm1(p)) break;
    1238          28 :       pari_err_DOMAIN("gvaluation", "p", "=", p, p);
    1239        5733 :     case t_POL:
    1240        5733 :       if (degpol(p) > 0) break;
    1241             :     default:
    1242           7 :       pari_err_DOMAIN("gvaluation", "p", "=", p, p);
    1243             :   }
    1244             : 
    1245     1575035 :   switch(tx)
    1246             :   {
    1247      249081 :     case t_INT:
    1248      249081 :       if (!signe(x)) return LONG_MAX;
    1249      248976 :       if (tp == t_POL) return 0;
    1250      248661 :       return Z_pval(x,p);
    1251             : 
    1252          49 :     case t_REAL:
    1253          49 :       if (tp == t_POL) return 0;
    1254          21 :       break;
    1255             : 
    1256          28 :     case t_FFELT:
    1257          28 :       if (tp == t_POL) return FF_equal0(x)? LONG_MAX: 0;
    1258          14 :       break;
    1259             : 
    1260          91 :     case t_INTMOD: {
    1261          91 :       GEN a = gel(x,1), b = gel(x,2);
    1262             :       long val;
    1263         119 :       if (tp == t_POL) return signe(b)? 0: LONG_MAX;
    1264          42 :       av = avma;
    1265          42 :       if (!intdvd(a, p, &a)) break;
    1266          28 :       if (!intdvd(b, p, &b)) return gc_long(av,0);
    1267          14 :       val = 1; while (intdvd(a,p,&a) && intdvd(b,p,&b)) val++;
    1268          14 :       return gc_long(av,val);
    1269             :     }
    1270             : 
    1271      394541 :     case t_FRAC:
    1272      394541 :       if (tp == t_POL) return 0;
    1273      394527 :       return frac_val(x, p);
    1274             : 
    1275      925743 :     case t_PADIC:
    1276      925743 :       if (tp == t_POL) return 0;
    1277      925722 :       if (!equalii(p,gel(x,2))) break;
    1278      925715 :       return valp(x);
    1279             : 
    1280          35 :     case t_POLMOD: {
    1281          35 :       GEN a = gel(x,1), b = gel(x,2);
    1282             :       long v, val;
    1283          35 :       if (tp == t_INT) return gvaluation(b,p);
    1284          21 :       v = varn(p);
    1285          21 :       if (varn(a) != v) return 0;
    1286          21 :       av = avma;
    1287          21 :       a = RgX_divrem(a, p, ONLY_DIVIDES);
    1288          21 :       if (!a) break;
    1289          28 :       if (typ(b) != t_POL || varn(b) != v ||
    1290          21 :           !(b = RgX_divrem(b, p, ONLY_DIVIDES)) ) return gc_long(av,0);
    1291           7 :       val = 1;
    1292          28 :       while ((a = RgX_divrem(a, p, ONLY_DIVIDES)) &&
    1293          21 :              (b = RgX_divrem(b, p, ONLY_DIVIDES)) ) val++;
    1294           7 :       return gc_long(av,val);
    1295             :     }
    1296        4893 :     case t_POL: {
    1297        4893 :       if (tp == t_POL) {
    1298        4704 :         long vp = varn(p), vx = varn(x);
    1299        4704 :         if (vp == vx)
    1300             :         {
    1301             :           long val;
    1302        4690 :           if (RgX_is_monomial(p))
    1303             :           {
    1304        4655 :             val = RgX_val(x); if (val == LONG_MAX) return LONG_MAX;
    1305        4585 :             return val / degpol(p);
    1306             :           }
    1307          35 :           if (!signe(x)) return LONG_MAX;
    1308          21 :           av = avma;
    1309          21 :           for (val=0; ; val++)
    1310             :           {
    1311          35 :             x = RgX_divrem(x,p,ONLY_DIVIDES);
    1312          35 :             if (!x) return gc_long(av,val);
    1313          14 :             if (gc_needed(av,1))
    1314             :             {
    1315           0 :               if(DEBUGMEM>1) pari_warn(warnmem,"gvaluation");
    1316           0 :               x = gerepilecopy(av, x);
    1317             :             }
    1318             :           }
    1319             :         }
    1320          14 :         if (varncmp(vx, vp) > 0) return 0;
    1321             :       }
    1322         196 :       return minval(x,p);
    1323             :     }
    1324             : 
    1325         427 :     case t_SER: {
    1326         427 :       if (tp == t_POL) {
    1327         413 :         long vp = varn(p), vx = varn(x);
    1328         413 :         if (vp == vx)
    1329             :         {
    1330         406 :           long val = RgX_val(p);
    1331         406 :           if (!val) pari_err_DOMAIN("gvaluation", "p", "=", p, p);
    1332         399 :           return (long)(valp(x) / val);
    1333             :         }
    1334           7 :         if (varncmp(vx, vp) > 0) return 0;
    1335             :       }
    1336          14 :       return minval(x,p);
    1337             :     }
    1338             : 
    1339          42 :     case t_RFRAC:
    1340          42 :       return gvaluation(gel(x,1),p) - gvaluation(gel(x,2),p);
    1341             : 
    1342         105 :     case t_COMPLEX: case t_QUAD: case t_VEC: case t_COL: case t_MAT:
    1343         105 :       return minval(x,p);
    1344             :   }
    1345          63 :   pari_err_OP("valuation", x,p);
    1346             :   return 0; /* LCOV_EXCL_LINE */
    1347             : }
    1348             : GEN
    1349        3808 : gpvaluation(GEN x, GEN p)
    1350             : {
    1351        3808 :   long v = gvaluation(x,p);
    1352        3703 :   return v == LONG_MAX? mkoo(): stoi(v);
    1353             : }
    1354             : 
    1355             : /* x is nonzero */
    1356             : long
    1357    50200388 : u_lvalrem(ulong x, ulong p, ulong *py)
    1358             : {
    1359             :   ulong vx;
    1360    50200388 :   if (p == 2) { vx = vals(x); *py = x >> vx; return vx; }
    1361    40250503 :   for(vx = 0;;)
    1362             :   {
    1363    73100092 :     if (x % p) { *py = x; return vx; }
    1364    32849589 :     x /= p; /* gcc is smart enough to make a single div */
    1365    32849589 :     vx++;
    1366             :   }
    1367             : }
    1368             : long
    1369    24393843 : u_lval(ulong x, ulong p)
    1370             : {
    1371             :   ulong vx;
    1372    24393843 :   if (p == 2) return vals(x);
    1373    21219719 :   for(vx = 0;;)
    1374             :   {
    1375    49189245 :     if (x % p) return vx;
    1376    27969526 :     x /= p; /* gcc is smart enough to make a single div */
    1377    27969526 :     vx++;
    1378             :   }
    1379             : }
    1380             : 
    1381             : long
    1382     1789735 : z_lval(long s, ulong p) { return u_lval(labs(s), p); }
    1383             : long
    1384       87210 : z_lvalrem(long s, ulong p, long *py)
    1385             : {
    1386             :   long v;
    1387       87210 :   if (s < 0)
    1388             :   {
    1389           0 :     ulong u = (ulong)-s;
    1390           0 :     v = u_lvalrem(u, p, &u);
    1391           0 :     *py = -(long)u;
    1392             :   }
    1393             :   else
    1394             :   {
    1395       87210 :     ulong u = (ulong)s;
    1396       87210 :     v = u_lvalrem(u, p, &u);
    1397       87210 :     *py = (long)u;
    1398             :   }
    1399       87210 :   return v;
    1400             : }
    1401             : /* assume |p| > 1 */
    1402             : long
    1403     1309893 : z_pval(long s, GEN p)
    1404             : {
    1405     1309893 :   if (lgefint(p) > 3) return 0;
    1406     1309893 :   return z_lval(s, uel(p,2));
    1407             : }
    1408             : /* assume |p| > 1 */
    1409             : long
    1410         266 : z_pvalrem(long s, GEN p, long *py)
    1411             : {
    1412         266 :   if (lgefint(p) > 3) { *py = s; return 0; }
    1413         266 :   return z_lvalrem(s, uel(p,2), py);
    1414             : }
    1415             : 
    1416             : /* return v_q(x) and set *py = x / q^v_q(x), using divide & conquer */
    1417             : static long
    1418     2140629 : Z_pvalrem_DC(GEN x, GEN q, GEN *py)
    1419             : {
    1420     2140629 :   GEN r, z = dvmdii(x, q, &r);
    1421             :   long v;
    1422     2140601 :   if (r != gen_0) { *py = x; return 0; }
    1423     1490799 :   if (2 * lgefint(q) <= lgefint(z)+3) /* avoid squaring if pointless */
    1424     1475194 :     v = Z_pvalrem_DC(z, sqri(q), py) << 1;
    1425             :   else
    1426       15605 :   { v = 0; *py = z; }
    1427     1490788 :   z = dvmdii(*py, q, &r);
    1428     1490849 :   if (r != gen_0) return v + 1;
    1429      631787 :   *py = z; return v + 2;
    1430             : }
    1431             : 
    1432             : static const long VAL_DC_THRESHOLD = 16;
    1433             : 
    1434             : long
    1435    19573967 : Z_lval(GEN x, ulong p)
    1436             : {
    1437             :   long vx;
    1438             :   pari_sp av;
    1439    19573967 :   if (p == 2) return vali(x);
    1440    11214548 :   if (lgefint(x) == 3) return u_lval(uel(x,2), p);
    1441     1715193 :   av = avma;
    1442     1715193 :   for(vx = 0;;)
    1443     8257775 :   {
    1444             :     ulong r;
    1445     9972968 :     GEN q = absdiviu_rem(x, p, &r);
    1446     9973211 :     if (r) break;
    1447     8422590 :     vx++; x = q;
    1448     8422590 :     if (vx == VAL_DC_THRESHOLD) {
    1449      164815 :       if (p == 1) pari_err_DOMAIN("Z_lval", "p", "=", gen_1, gen_1);
    1450      164815 :       vx += Z_pvalrem_DC(x, sqru(p), &x) << 1;
    1451      164815 :       q = absdiviu_rem(x, p, &r); if (!r) vx++;
    1452      164815 :       break;
    1453             :     }
    1454             :   }
    1455     1715436 :   return gc_long(av,vx);
    1456             : }
    1457             : long
    1458    42031347 : Z_lvalrem(GEN x, ulong p, GEN *py)
    1459             : {
    1460             :   long vx, sx;
    1461             :   pari_sp av;
    1462    42031347 :   if (p == 2) { vx = vali(x); *py = shifti(x, -vx); return vx; }
    1463    26442224 :   if (lgefint(x) == 3) {
    1464             :     ulong u;
    1465    19747775 :     vx = u_lvalrem(uel(x,2), p, &u);
    1466    19747795 :     *py = signe(x) < 0? utoineg(u): utoipos(u);
    1467    19747529 :     return vx;
    1468             :   }
    1469     6694449 :   av = avma; (void)new_chunk(lgefint(x));
    1470     6694912 :   sx = signe(x);
    1471     6694912 :   for(vx = 0;;)
    1472    15973504 :   {
    1473             :     ulong r;
    1474    22668416 :     GEN q = absdiviu_rem(x, p, &r);
    1475    22668394 :     if (r) break;
    1476    16445445 :     vx++; x = q;
    1477    16445445 :     if (vx == VAL_DC_THRESHOLD) {
    1478      471941 :       if (p == 1) pari_err_DOMAIN("Z_lvalrem", "p", "=", gen_1, gen_1);
    1479      471941 :       vx += Z_pvalrem_DC(x, sqru(p), &x) << 1;
    1480      471942 :       q = absdiviu_rem(x, p, &r); if (!r) { vx++; x = q; }
    1481      471942 :       break;
    1482             :     }
    1483             :   }
    1484     6694891 :   set_avma(av); *py = icopy(x); setsigne(*py, sx); return vx;
    1485             : }
    1486             : 
    1487             : /* Is |q| <= p ? */
    1488             : static int
    1489   844106764 : isless_iu(GEN q, ulong p) {
    1490   844106764 :   long l = lgefint(q);
    1491   844106764 :   return l==2 || (l == 3 && uel(q,2) <= p);
    1492             : }
    1493             : 
    1494             : long
    1495  3973351308 : u_lvalrem_stop(ulong *n, ulong p, int *stop)
    1496             : {
    1497  3973351308 :   ulong N = *n, q = N / p, r = N % p; /* gcc makes a single div */
    1498  3973351308 :   long v = 0;
    1499  3973351308 :   if (!r)
    1500             :   {
    1501   145575604 :     do { v++; N = q; q = N / p; r = N % p; } while (!r);
    1502   107214785 :     *n = N;
    1503             :   }
    1504  3973351308 :   *stop = q <= p; return v;
    1505             : }
    1506             : /* Assume n > 0. Return v_p(n), set *n := n/p^v_p(n). Set 'stop' if now
    1507             :  * n < p^2 [implies n prime if no prime < p divides n] */
    1508             : long
    1509  4661420277 : Z_lvalrem_stop(GEN *n, ulong p, int *stop)
    1510             : {
    1511             :   pari_sp av;
    1512             :   long v;
    1513             :   ulong r;
    1514             :   GEN N, q;
    1515             : 
    1516  4661420277 :   if (lgefint(*n) == 3)
    1517             :   {
    1518  3816969193 :     r = (*n)[2];
    1519  3816969193 :     v = u_lvalrem_stop(&r, p, stop);
    1520  3817065532 :     if (v) *n = utoipos(r);
    1521  3817048822 :     return v;
    1522             :   }
    1523   844451084 :   av = avma; v = 0; q = absdiviu_rem(*n, p, &r);
    1524   844017104 :   if (r) set_avma(av);
    1525             :   else
    1526             :   {
    1527             :     do {
    1528    23466646 :       v++; N = q;
    1529    23466646 :       if (v == VAL_DC_THRESHOLD)
    1530             :       {
    1531       28704 :         v += Z_pvalrem_DC(N,sqru(p),&N) << 1;
    1532       28704 :         q = absdiviu_rem(N, p, &r); if (!r) { v++; N = q; }
    1533       28704 :         break;
    1534             :       }
    1535    23437942 :       q = absdiviu_rem(N, p, &r);
    1536    23437939 :     } while (!r);
    1537    15724561 :     *n = N;
    1538             :   }
    1539   844048294 :   *stop = isless_iu(q,p); return v;
    1540             : }
    1541             : 
    1542             : /* x is a nonzero integer, |p| > 1 */
    1543             : long
    1544    33991199 : Z_pvalrem(GEN x, GEN p, GEN *py)
    1545             : {
    1546             :   long vx;
    1547             :   pari_sp av;
    1548             : 
    1549    33991199 :   if (lgefint(p) == 3) return Z_lvalrem(x, uel(p,2), py);
    1550       25339 :   if (lgefint(x) == 3) { *py = icopy(x); return 0; }
    1551        7046 :   av = avma; vx = 0; (void)new_chunk(lgefint(x));
    1552             :   for(;;)
    1553       12802 :   {
    1554       19934 :     GEN r, q = dvmdii(x,p,&r);
    1555       19934 :     if (r != gen_0) { set_avma(av); *py = icopy(x); return vx; }
    1556       12802 :     vx++; x = q;
    1557             :   }
    1558             : }
    1559             : long
    1560     2394787 : u_pvalrem(ulong x, GEN p, ulong *py)
    1561             : {
    1562     2394787 :   if (lgefint(p) == 3) return u_lvalrem(x, uel(p,2), py);
    1563         443 :   *py = x; return 0;
    1564             : }
    1565             : long
    1566      135417 : u_pval(ulong x, GEN p)
    1567             : {
    1568      135417 :   if (lgefint(p) == 3) return u_lval(x, uel(p,2));
    1569           0 :   return 0;
    1570             : }
    1571             : long
    1572    12058069 : Z_pval(GEN x, GEN p) {
    1573             :   long vx;
    1574             :   pari_sp av;
    1575             : 
    1576    12058069 :   if (lgefint(p) == 3) return Z_lval(x, uel(p,2));
    1577       11240 :   if (lgefint(x) == 3) return 0;
    1578        6402 :   av = avma; vx = 0;
    1579             :   for(;;)
    1580       24110 :   {
    1581       30512 :     GEN r, q = dvmdii(x,p,&r);
    1582       30540 :     if (r != gen_0) return gc_long(av,vx);
    1583       24110 :     vx++; x = q;
    1584             :   }
    1585             : }
    1586             : 
    1587             : /* return v_p(n!) = [n/p] + [n/p^2] + ... */
    1588             : long
    1589     2500799 : factorial_lval(ulong n, ulong p)
    1590             : {
    1591             :   ulong q, v;
    1592     2500799 :   if (p == 2) return n - hammingl(n);
    1593     1830169 :   q = p; v = 0;
    1594     1854690 :   do { v += n/q; q *= p; } while (n >= q);
    1595     1830169 :   return (long)v;
    1596             : }
    1597             : 
    1598             : /********** Same for "containers" ZX / ZV / ZC **********/
    1599             : 
    1600             : /* If the t_INT q divides the ZX/ZV x, return the quotient. Otherwise NULL.
    1601             :  * Stack clean; assumes lg(x) > 1 */
    1602             : static GEN
    1603        6422 : gen_Z_divides(GEN x, GEN q, long imin)
    1604             : {
    1605             :   long i, l;
    1606        6422 :   GEN y = cgetg_copy(x, &l);
    1607             : 
    1608        6422 :   y[1] = x[1]; /* Needed for ZX; no-op if ZV, overwritten in first iteration */
    1609       89353 :   for (i = imin; i < l; i++)
    1610             :   {
    1611       86845 :     GEN r, xi = gel(x,i);
    1612       86845 :     if (!signe(xi)) { gel(y,i) = xi; continue; }
    1613       55536 :     gel(y,i) = dvmdii(xi, q, &r);
    1614       55536 :     if (r != gen_0) { set_avma((pari_sp)(y+l)); return NULL; }
    1615             :   }
    1616        2508 :   return y;
    1617             : }
    1618             : /* If q divides the ZX/ZV x, return the quotient. Otherwise NULL.
    1619             :  * Stack clean; assumes lg(x) > 1 */
    1620             : static GEN
    1621        4697 : gen_z_divides(GEN x, ulong q, long imin)
    1622             : {
    1623             :   long i, l;
    1624        4697 :   GEN y = cgetg_copy(x, &l);
    1625             : 
    1626        4697 :   y[1] = x[1]; /* Needed for ZX; no-op if ZV, overwritten in first iteration */
    1627       43281 :   for (i = imin; i < l; i++)
    1628             :   {
    1629             :     ulong r;
    1630       42056 :     GEN xi = gel(x,i);
    1631       42056 :     if (!signe(xi)) { gel(y,i) = xi; continue; }
    1632       28401 :     gel(y,i) = absdiviu_rem(xi, q, &r);
    1633       28401 :     if (r) { set_avma((pari_sp)(y+l)); return NULL; }
    1634       24929 :     affectsign_safe(xi, &gel(y,i));
    1635             :   }
    1636        1225 :   return y;
    1637             : }
    1638             : 
    1639             : /* return v_q(x) and set *py = x / q^v_q(x), using divide & conquer */
    1640             : static long
    1641       11081 : gen_pvalrem_DC(GEN x, GEN q, GEN *py, long imin)
    1642             : {
    1643             : 
    1644       11081 :   pari_sp av = avma;
    1645       11081 :   long v, i, l, lz = LONG_MAX;
    1646       11081 :   GEN y = cgetg_copy(x, &l);
    1647             : 
    1648       11081 :   y[1] = x[1];
    1649      135615 :   for (i = imin; i < l; i++)
    1650             :   {
    1651      129193 :     GEN r, xi = gel(x,i);
    1652      129193 :     if (!signe(xi)) { gel(y,i) = xi; continue; }
    1653       86345 :     gel(y,i) = dvmdii(xi, q, &r);
    1654       86345 :     if (r != gen_0) { *py = x; return gc_long(av,0); }
    1655       81686 :     lz = minss(lz, lgefint(gel(y,i)));
    1656             :   }
    1657        6422 :   if (2 * lgefint(q) <= lz+3) /* avoid squaring if pointless */
    1658        6370 :     v = gen_pvalrem_DC(y, sqri(q), py, imin) << 1;
    1659             :   else
    1660          52 :   { v = 0; *py = y; }
    1661             : 
    1662        6422 :   y = gen_Z_divides(*py, q, imin);
    1663        6422 :   if (!y) return v+1;
    1664        2508 :   *py = y; return v+2;
    1665             : }
    1666             : 
    1667             : static long
    1668      768123 : gen_2val(GEN x, long imin)
    1669             : {
    1670      768123 :   long i, lx = lg(x), v = LONG_MAX;
    1671     2900098 :   for (i = imin; i < lx; i++)
    1672             :   {
    1673     2466861 :     GEN c = gel(x,i);
    1674             :     long w;
    1675     2466861 :     if (!signe(c)) continue;
    1676     2258856 :     w = vali(c);
    1677     2258856 :     if (w < v) { v = w; if (!v) break; }
    1678             :   }
    1679      768123 :   return v;
    1680             : }
    1681             : static long
    1682     1270838 : gen_lval(GEN x, ulong p, long imin)
    1683             : {
    1684             :   long i, lx, v;
    1685             :   pari_sp av;
    1686             :   GEN y;
    1687     1270838 :   if (p == 2) return gen_2val(x, imin);
    1688      502715 :   av = avma;
    1689      502715 :   lx = lg(x); y = leafcopy(x);
    1690      502715 :   for(v = 0;; v++)
    1691     2291983 :     for (i = imin; i < lx; i++)
    1692             :     {
    1693             :       ulong r;
    1694     2058631 :       gel(y,i) = absdiviu_rem(gel(y,i), p, &r);
    1695     2058631 :       if (r) return gc_long(av,v);
    1696             :     }
    1697             : }
    1698             : long
    1699      742167 : ZX_lval(GEN x, ulong p) { return gen_lval(x, p, 2); }
    1700             : long
    1701           0 : ZV_lval(GEN x, ulong p) { return gen_lval(x, p, 1); }
    1702             : 
    1703             : long
    1704       28924 : zx_lval(GEN f, long p)
    1705             : {
    1706       28924 :   long i, l = lg(f), x = LONG_MAX;
    1707       30212 :   for(i=2; i<l; i++)
    1708             :   {
    1709             :     long y;
    1710       29470 :     if (f[i] == 0) continue;
    1711       29421 :     y = z_lval(f[i], p);
    1712       29421 :     if (y < x) { x = y; if (x == 0) return x; }
    1713             :   }
    1714         742 :   return x;
    1715             : }
    1716             : 
    1717             : static long
    1718      539007 : gen_pval(GEN x, GEN p, long imin)
    1719             : {
    1720             :   long i, lx, v;
    1721             :   pari_sp av;
    1722             :   GEN y;
    1723      539007 :   if (lgefint(p) == 3) return gen_lval(x, p[2], imin);
    1724       10336 :   av = avma;
    1725       10336 :   lx = lg(x); y = leafcopy(x);
    1726       10336 :   for(v = 0;; v++)
    1727             :   {
    1728       10336 :     if (v == VAL_DC_THRESHOLD)
    1729             :     {
    1730           0 :       if (is_pm1(p)) pari_err_DOMAIN("gen_pval", "p", "=", p, p);
    1731           0 :       v += gen_pvalrem_DC(y, p, &y, imin);
    1732           0 :       return gc_long(av,v);
    1733             :     }
    1734             : 
    1735       10336 :     for (i = imin; i < lx; i++)
    1736             :     {
    1737       10336 :       GEN r; gel(y,i) = dvmdii(gel(y,i), p, &r);
    1738       10336 :       if (r != gen_0) return gc_long(av,v);
    1739             :     }
    1740             :   }
    1741             : }
    1742             : long
    1743      508235 : ZX_pval(GEN x, GEN p) { return gen_pval(x, p, 2); }
    1744             : long
    1745       30772 : ZV_pval(GEN x, GEN p) { return gen_pval(x, p, 1); }
    1746             : /* v = 0 (mod p) */
    1747             : int
    1748         343 : ZV_Z_dvd(GEN v, GEN p)
    1749             : {
    1750         343 :   pari_sp av = avma;
    1751         343 :   long i, l = lg(v);
    1752        1183 :   for (i=1; i<l; i++)
    1753         868 :     if (!dvdii(gel(v,i), p)) return gc_long(av,0);
    1754         315 :   return gc_long(av,1);
    1755             : }
    1756             : 
    1757             : static long
    1758     3425720 : gen_2valrem(GEN x, GEN *px, long imin)
    1759             : {
    1760     3425720 :   long i, lx = lg(x), v = LONG_MAX;
    1761             :   GEN z;
    1762    11847993 :   for (i = imin; i < lx; i++)
    1763             :   {
    1764    10549187 :     GEN c = gel(x,i);
    1765             :     long w;
    1766    10549187 :     if (!signe(c)) continue;
    1767     9698595 :     w = vali(c);
    1768     9698603 :     if (w < v) {
    1769     5035756 :       v = w;
    1770     5035756 :       if (!v) { *px = x; return 0; } /* early abort */
    1771             :     }
    1772             :   }
    1773     1298806 :   z = cgetg_copy(x, &lx); z[1] = x[1];
    1774     8392907 :   for (i=imin; i<lx; i++) gel(z,i) = shifti(gel(x,i), -v);
    1775     1298087 :   *px = z; return v;
    1776             : }
    1777             : static long
    1778     6344706 : gen_lvalrem(GEN x, ulong p, GEN *px, long imin)
    1779             : {
    1780             :   long i, lx, v;
    1781             :   GEN y;
    1782     6344706 :   if (p == 2) return gen_2valrem(x, px, imin);
    1783     2918997 :   y = cgetg_copy(x, &lx);
    1784     2919145 :   y[1] = x[1];
    1785     2919145 :   x = leafcopy(x);
    1786     2918994 :   for(v = 0;; v++)
    1787             :   {
    1788     4218378 :     if (v == VAL_DC_THRESHOLD)
    1789             :     {
    1790        4697 :       if (p == 1) pari_err_DOMAIN("gen_lvalrem", "p", "=", gen_1, gen_1);
    1791        4697 :       v += gen_pvalrem_DC(x, sqru(p), px, imin) << 1;
    1792        4697 :       x = gen_z_divides(*px, p, imin);
    1793        4697 :       if (x) { *px = x; v++; }
    1794        4697 :       return v;
    1795             :     }
    1796             : 
    1797    14179412 :     for (i = imin; i < lx; i++)
    1798             :     {
    1799    12880028 :       ulong r; gel(y,i) = absdiviu_rem(gel(x,i), p, &r);
    1800    12877669 :       if (r) { *px = x; return v; }
    1801     9963337 :       affectsign_safe(gel(x,i), &gel(y,i));
    1802             :     }
    1803     1299384 :     swap(x, y);
    1804             :   }
    1805             : }
    1806             : long
    1807         721 : ZX_lvalrem(GEN x, ulong p, GEN *px) { return gen_lvalrem(x,p,px, 2); }
    1808             : long
    1809           0 : ZV_lvalrem(GEN x, ulong p, GEN *px) { return gen_lvalrem(x,p,px, 1); }
    1810             : 
    1811             : static long
    1812     6357353 : gen_pvalrem(GEN x, GEN p, GEN *px, long imin)
    1813             : {
    1814             :   long i, lx, v;
    1815             :   GEN y;
    1816     6357353 :   if (lgefint(p) == 3) return gen_lvalrem(x, p[2], px, imin);
    1817       13507 :   y = cgetg_copy(x, &lx);
    1818       13589 :   y[1] = x[1];
    1819       13589 :   x = leafcopy(x);
    1820       13589 :   for(v = 0;; v++)
    1821             :   {
    1822       14315 :     if (v == VAL_DC_THRESHOLD)
    1823             :     {
    1824          14 :       if (is_pm1(p)) pari_err_DOMAIN("gen_pvalrem", "p", "=", p, p);
    1825          14 :       return v + gen_pvalrem_DC(x, p, px, imin);
    1826             :     }
    1827             : 
    1828       22552 :     for (i = imin; i < lx; i++)
    1829             :     {
    1830       21826 :       GEN r; gel(y,i) = dvmdii(gel(x,i), p, &r);
    1831       21826 :       if (r != gen_0) { *px = x; return v; }
    1832             :     }
    1833         726 :     swap(x, y);
    1834             :   }
    1835             : }
    1836             : long
    1837     3813372 : ZX_pvalrem(GEN x, GEN p, GEN *px) { return gen_pvalrem(x,p,px, 2); }
    1838             : long
    1839     2543888 : ZV_pvalrem(GEN x, GEN p, GEN *px) { return gen_pvalrem(x,p,px, 1); }
    1840             : 
    1841             : /*******************************************************************/
    1842             : /*                                                                 */
    1843             : /*                       NEGATION: Create -x                       */
    1844             : /*                                                                 */
    1845             : /*******************************************************************/
    1846             : 
    1847             : GEN
    1848   409021158 : gneg(GEN x)
    1849             : {
    1850             :   long lx, i;
    1851             :   GEN y;
    1852             : 
    1853   409021158 :   switch(typ(x))
    1854             :   {
    1855   107659868 :     case t_INT:
    1856   107659868 :       return signe(x)? negi(x): gen_0;
    1857   221415198 :     case t_REAL:
    1858   221415198 :       return mpneg(x);
    1859             : 
    1860      220807 :     case t_INTMOD: y=cgetg(3,t_INTMOD);
    1861      220807 :       gel(y,1) = icopy(gel(x,1));
    1862      220806 :       gel(y,2) = signe(gel(x,2))? subii(gel(y,1),gel(x,2)): gen_0;
    1863      220804 :       break;
    1864             : 
    1865     1730541 :     case t_FRAC:
    1866     1730541 :       y = cgetg(3, t_FRAC);
    1867     1730540 :       gel(y,1) = negi(gel(x,1));
    1868     1730542 :       gel(y,2) = icopy(gel(x,2)); break;
    1869             : 
    1870    72821811 :     case t_COMPLEX:
    1871    72821811 :       y=cgetg(3, t_COMPLEX);
    1872    72823232 :       gel(y,1) = gneg(gel(x,1));
    1873    72825713 :       gel(y,2) = gneg(gel(x,2));
    1874    72825503 :       break;
    1875             : 
    1876      232306 :     case t_POLMOD:
    1877      232306 :       retmkpolmod(gneg(gel(x,2)), RgX_copy(gel(x,1)));
    1878             : 
    1879      153307 :     case t_RFRAC:
    1880      153307 :       y = cgetg(3, t_RFRAC);
    1881      153307 :       gel(y,1) = gneg(gel(x,1));
    1882      153307 :       gel(y,2) = RgX_copy(gel(x,2)); break;
    1883             : 
    1884      118392 :     case t_PADIC:
    1885      118392 :       if (!signe(gel(x,4))) return gcopy(x);
    1886      116257 :       y = cgetg(5, t_PADIC);
    1887      116256 :       y[1] = x[1];
    1888      116256 :       gel(y,2) = icopy(gel(x,2));
    1889      116256 :       gel(y,3) = icopy(gel(x,3));
    1890      116256 :       gel(y,4) = subii(gel(x,3),gel(x,4));
    1891      116255 :       break;
    1892             : 
    1893         133 :     case t_QUAD:
    1894         133 :       y=cgetg(4,t_QUAD);
    1895         133 :       gel(y,1) = ZX_copy(gel(x,1));
    1896         133 :       gel(y,2) = gneg(gel(x,2));
    1897         133 :       gel(y,3) = gneg(gel(x,3)); break;
    1898             : 
    1899       80431 :     case t_FFELT: return FF_neg(x);
    1900     4252116 :     case t_POL: return RgX_neg(x);
    1901        1295 :     case t_SER:
    1902        1295 :       y = cgetg_copy(x, &lx); y[1] = x[1];
    1903       16282 :       for (i=2; i<lx; i++) gel(y,i) = gneg(gel(x,i));
    1904        1295 :       break;
    1905        1183 :     case t_VEC: return RgV_neg(x);
    1906      454083 :     case t_COL: return RgC_neg(x);
    1907         245 :     case t_MAT: return RgM_neg(x);
    1908         770 :     case t_INFINITY: return inf_get_sign(x) == 1? mkmoo(): mkoo();
    1909           0 :     default:
    1910           0 :       pari_err_TYPE("gneg",x);
    1911             :       return NULL; /* LCOV_EXCL_LINE */
    1912             :   }
    1913    75047756 :   return y;
    1914             : }
    1915             : 
    1916             : GEN
    1917   106804281 : gneg_i(GEN x)
    1918             : {
    1919             :   long lx, i;
    1920             :   GEN y;
    1921             : 
    1922   106804281 :   switch(typ(x))
    1923             :   {
    1924    55823112 :     case t_INT:
    1925    55823112 :       return signe(x)? negi(x): gen_0;
    1926    20437460 :     case t_REAL:
    1927    20437460 :       return mpneg(x);
    1928             : 
    1929     1088740 :     case t_INTMOD: y=cgetg(3,t_INTMOD);
    1930     1088740 :       gel(y,1) = gel(x,1);
    1931     1088740 :       gel(y,2) = signe(gel(x,2))? subii(gel(y,1),gel(x,2)): gen_0;
    1932     1088740 :       break;
    1933             : 
    1934     4989409 :     case t_FRAC:
    1935     4989409 :       y = cgetg(3, t_FRAC);
    1936     4989410 :       gel(y,1) = negi(gel(x,1));
    1937     4989426 :       gel(y,2) = gel(x,2); break;
    1938             : 
    1939     7317973 :     case t_COMPLEX:
    1940     7317973 :       y = cgetg(3, t_COMPLEX);
    1941     7318125 :       gel(y,1) = gneg_i(gel(x,1));
    1942     7318211 :       gel(y,2) = gneg_i(gel(x,2)); break;
    1943             : 
    1944     3305494 :     case t_PADIC: y = cgetg(5,t_PADIC);
    1945     3305494 :       y[1] = x[1];
    1946     3305494 :       gel(y,2) = gel(x,2);
    1947     3305494 :       gel(y,3) = gel(x,3);
    1948     3305494 :       gel(y,4) = signe(gel(x,4))? subii(gel(x,3),gel(x,4)): gen_0; break;
    1949             : 
    1950      107911 :     case t_POLMOD:
    1951      107911 :       retmkpolmod(gneg_i(gel(x,2)), RgX_copy(gel(x,1)));
    1952             : 
    1953       84658 :     case t_FFELT: return FF_neg_i(x);
    1954             : 
    1955         672 :     case t_QUAD: y=cgetg(4,t_QUAD);
    1956         672 :       gel(y,1) = gel(x,1);
    1957         672 :       gel(y,2) = gneg_i(gel(x,2));
    1958         672 :       gel(y,3) = gneg_i(gel(x,3)); break;
    1959             : 
    1960        1806 :     case t_VEC: case t_COL: case t_MAT:
    1961        1806 :       y = cgetg_copy(x, &lx);
    1962        9835 :       for (i=1; i<lx; i++) gel(y,i) = gneg_i(gel(x,i));
    1963        1806 :       break;
    1964             : 
    1965     8613339 :     case t_POL: case t_SER:
    1966     8613339 :       y = cgetg_copy(x, &lx); y[1]=x[1];
    1967    36074595 :       for (i=2; i<lx; i++) gel(y,i) = gneg_i(gel(x,i));
    1968     8613135 :       break;
    1969             : 
    1970     5041987 :     case t_RFRAC:
    1971     5041987 :       y = cgetg(3, t_RFRAC);
    1972     5041987 :       gel(y,1) = gneg_i(gel(x,1));
    1973     5042146 :       gel(y,2) = gel(x,2); break;
    1974             : 
    1975           0 :     default:
    1976           0 :       pari_err_TYPE("gneg_i",x);
    1977             :       return NULL; /* LCOV_EXCL_LINE */
    1978             :   }
    1979    30359653 :   return y;
    1980             : }
    1981             : 
    1982             : /******************************************************************/
    1983             : /*                                                                */
    1984             : /*                       ABSOLUTE VALUE                           */
    1985             : /*    Create abs(x) if x is integer, real, fraction or complex.   */
    1986             : /*                       Error otherwise.                         */
    1987             : /*                                                                */
    1988             : /******************************************************************/
    1989             : static int
    1990           0 : is_negative(GEN x) {
    1991           0 :   switch(typ(x))
    1992             :   {
    1993           0 :     case t_INT: case t_REAL:
    1994           0 :       return (signe(x) < 0);
    1995           0 :     case t_FRAC:
    1996           0 :       return (signe(gel(x,1)) < 0);
    1997             :   }
    1998           0 :   return 0;
    1999             : }
    2000             : 
    2001             : GEN
    2002    47791854 : gabs(GEN x, long prec)
    2003             : {
    2004             :   long lx;
    2005             :   pari_sp av;
    2006             :   GEN y, N;
    2007             : 
    2008    47791854 :   switch(typ(x))
    2009             :   {
    2010    31183191 :     case t_INT: case t_REAL:
    2011    31183191 :       return mpabs(x);
    2012             : 
    2013       11438 :     case t_FRAC:
    2014       11438 :       return absfrac(x);
    2015             : 
    2016    16500286 :     case t_COMPLEX:
    2017    16500286 :       av=avma; N=cxnorm(x);
    2018    16481569 :       switch(typ(N))
    2019             :       {
    2020         259 :         case t_INT:
    2021         259 :           if (!Z_issquareall(N, &y)) break;
    2022          98 :           return gerepileupto(av, y);
    2023       20895 :         case t_FRAC: {
    2024             :           GEN a,b;
    2025       34636 :           if (!Z_issquareall(gel(N,1), &a)) break;
    2026       13741 :           if (!Z_issquareall(gel(N,2), &b)) break;
    2027           0 :           return gerepileupto(av, gdiv(a,b));
    2028             :         }
    2029             :       }
    2030    16481471 :       return gerepileupto(av, gsqrt(N,prec));
    2031             : 
    2032          21 :     case t_QUAD:
    2033          21 :       av = avma;
    2034          21 :       return gerepileuptoleaf(av, gabs(quadtofp(x, prec), prec));
    2035             : 
    2036           0 :     case t_POL:
    2037           0 :       lx = lg(x); if (lx<=2) return RgX_copy(x);
    2038           0 :       return is_negative(gel(x,lx-1))? RgX_neg(x): RgX_copy(x);
    2039             : 
    2040           7 :     case t_SER:
    2041           7 :      if (!signe(x)) pari_err_DOMAIN("abs", "argument", "=", gen_0, x);
    2042           7 :      if (valp(x)) pari_err_DOMAIN("abs", "series valuation", "!=", gen_0, x);
    2043           0 :      return is_negative(gel(x,2))? gneg(x): gcopy(x);
    2044             : 
    2045      102205 :     case t_VEC: case t_COL: case t_MAT:
    2046      613033 :       pari_APPLY_same(gabs(gel(x,i),prec));
    2047             :   }
    2048           0 :   pari_err_TYPE("gabs",x);
    2049             :   return NULL; /* LCOV_EXCL_LINE */
    2050             : }
    2051             : 
    2052             : GEN
    2053       78141 : gmax(GEN x, GEN y) { return gcopy(gmax_shallow(x,y)); }
    2054             : GEN
    2055           0 : gmaxgs(GEN x, long s) { return (gcmpsg(s,x)>=0)? stoi(s): gcopy(x); }
    2056             : 
    2057             : GEN
    2058       12124 : gmin(GEN x, GEN y) { return gcopy(gmin_shallow(x,y)); }
    2059             : GEN
    2060           0 : gmings(GEN x, long s) { return (gcmpsg(s,x)>0)? gcopy(x): stoi(s); }
    2061             : 
    2062             : long
    2063      410003 : vecindexmax(GEN x)
    2064             : {
    2065      410003 :   long lx = lg(x), i0, i;
    2066             :   GEN s;
    2067             : 
    2068      410003 :   if (lx==1) pari_err_DOMAIN("vecindexmax", "empty argument", "=", x,x);
    2069      410003 :   switch(typ(x))
    2070             :   {
    2071      410003 :     case t_VEC: case t_COL:
    2072      410003 :       s = gel(x,i0=1);
    2073      914281 :       for (i=2; i<lx; i++)
    2074      504277 :         if (gcmp(gel(x,i),s) > 0) s = gel(x,i0=i);
    2075      410004 :       return i0;
    2076           0 :     case t_VECSMALL:
    2077           0 :       return vecsmall_indexmax(x);
    2078           0 :     default: pari_err_TYPE("vecindexmax",x);
    2079             :   }
    2080             :   /* LCOV_EXCL_LINE */
    2081           0 :   return 0;
    2082             : }
    2083             : long
    2084       54890 : vecindexmin(GEN x)
    2085             : {
    2086       54890 :   long lx = lg(x), i0, i;
    2087             :   GEN s;
    2088             : 
    2089       54890 :   if (lx==1) pari_err_DOMAIN("vecindexmin", "empty argument", "=", x,x);
    2090       54890 :   switch(typ(x))
    2091             :   {
    2092       54890 :     case t_VEC: case t_COL:
    2093       54890 :       s = gel(x,i0=1);
    2094      223187 :       for (i=2; i<lx; i++)
    2095      168297 :         if (gcmp(gel(x,i),s) < 0) s = gel(x,i0=i);
    2096       54890 :       return i0;
    2097           0 :     case t_VECSMALL:
    2098           0 :       return vecsmall_indexmin(x);
    2099           0 :     default: pari_err_TYPE("vecindexmin",x);
    2100             :   }
    2101             :   /* LCOV_EXCL_LINE */
    2102           0 :   return 0;
    2103             : }
    2104             : 
    2105             : GEN
    2106      128130 : vecmax0(GEN x, GEN *pi)
    2107             : {
    2108      128130 :   long i, lx = lg(x), tx = typ(x);
    2109      128130 :   if (!is_matvec_t(tx) && tx != t_VECSMALL) return gcopy(x);
    2110      128116 :   if (lx==1) pari_err_DOMAIN("vecmax", "empty argument", "=", x,x);
    2111      128095 :   switch(typ(x))
    2112             :   {
    2113      127636 :     case t_VEC: case t_COL:
    2114      127636 :       i = vecindexmax(x); if (pi) *pi = utoipos(i);
    2115      127637 :       return gcopy(gel(x,i));
    2116         445 :     case t_MAT: {
    2117         445 :       long j, i0 = 1, j0 = 1, lx2 = lgcols(x);
    2118             :       GEN s;
    2119         445 :       if (lx2 == 1) pari_err_DOMAIN("vecmax", "empty argument", "=", x,x);
    2120         438 :       s = gcoeff(x,i0,j0); i = 2;
    2121        1704 :       for (j=1; j<lx; j++,i=1)
    2122             :       {
    2123        1266 :         GEN c = gel(x,j);
    2124       24638 :         for (; i<lx2; i++)
    2125       23372 :           if (gcmp(gel(c,i),s) > 0) { s = gel(c,i); j0=j; i0=i; }
    2126             :       }
    2127         438 :       if (pi) *pi = mkvec2(utoipos(i0), utoipos(j0));
    2128         438 :       return gcopy(s);
    2129             :     }
    2130          14 :     case t_VECSMALL:
    2131          14 :       i = vecsmall_indexmax(x); if (pi) *pi = utoipos(i);
    2132          14 :       return stoi(x[i]);
    2133             :   }
    2134             :   return NULL;/*LCOV_EXCL_LINE*/
    2135             : }
    2136             : GEN
    2137       20527 : vecmin0(GEN x, GEN *pi)
    2138             : {
    2139       20527 :   long i, lx = lg(x), tx = typ(x);
    2140       20527 :   if (!is_matvec_t(tx) && tx != t_VECSMALL) return gcopy(x);
    2141       20513 :   if (lx==1) pari_err_DOMAIN("vecmin", "empty argument", "=", x,x);
    2142       20499 :   switch(typ(x))
    2143             :   {
    2144       20471 :     case t_VEC: case t_COL:
    2145       20471 :       i = vecindexmin(x); if (pi) *pi = utoipos(i);
    2146       20471 :       return gcopy(gel(x,i));
    2147          14 :     case t_MAT: {
    2148          14 :       long j, i0 = 1, j0 = 1, lx2 = lgcols(x);
    2149             :       GEN s;
    2150          14 :       if (lx2 == 1) pari_err_DOMAIN("vecmin", "empty argument", "=", x,x);
    2151          14 :       s = gcoeff(x,i0,j0); i = 2;
    2152          42 :       for (j=1; j<lx; j++,i=1)
    2153             :       {
    2154          28 :         GEN c = gel(x,j);
    2155          70 :         for (; i<lx2; i++)
    2156          42 :           if (gcmp(gel(c,i),s) < 0) { s = gel(c,i); j0=j; i0=i; }
    2157             :       }
    2158          14 :       if (pi) *pi = mkvec2(utoipos(i0), utoipos(j0));
    2159          14 :       return gcopy(s);
    2160             :     }
    2161          14 :     case t_VECSMALL:
    2162          14 :       i = vecsmall_indexmin(x); if (pi) *pi = utoipos(i);
    2163          14 :       return stoi(x[i]);
    2164             :   }
    2165             :   return NULL;/*LCOV_EXCL_LINE*/
    2166             : }
    2167             : 
    2168             : GEN
    2169       66073 : vecmax(GEN x) { return vecmax0(x, NULL); }
    2170             : GEN
    2171       20450 : vecmin(GEN x) { return vecmin0(x, NULL); }
    2172             : 
    2173             : /*******************************************************************/
    2174             : /*                                                                 */
    2175             : /*                      AFFECT long --> GEN                        */
    2176             : /*         affect long s to GEN x. Useful for initialization.      */
    2177             : /*                                                                 */
    2178             : /*******************************************************************/
    2179             : 
    2180             : static void
    2181           0 : padicaff0(GEN x)
    2182             : {
    2183           0 :   if (signe(gel(x,4)))
    2184             :   {
    2185           0 :     x[1] = evalvalp(valp(x)+precp(x));
    2186           0 :     affsi(0,gel(x,4));
    2187             :   }
    2188           0 : }
    2189             : 
    2190             : void
    2191         966 : gaffsg(long s, GEN x)
    2192             : {
    2193         966 :   switch(typ(x))
    2194             :   {
    2195           0 :     case t_INT: affsi(s,x); break;
    2196         966 :     case t_REAL: affsr(s,x); break;
    2197           0 :     case t_INTMOD: modsiz(s,gel(x,1),gel(x,2)); break;
    2198           0 :     case t_FRAC: affsi(s,gel(x,1)); affsi(1,gel(x,2)); break;
    2199           0 :     case t_COMPLEX: gaffsg(s,gel(x,1)); gaffsg(0,gel(x,2)); break;
    2200           0 :     case t_PADIC: {
    2201             :       long vx;
    2202             :       GEN y;
    2203           0 :       if (!s) { padicaff0(x); break; }
    2204           0 :       vx = Z_pvalrem(stoi(s), gel(x,2), &y);
    2205           0 :       setvalp(x,vx); modiiz(y,gel(x,3),gel(x,4));
    2206           0 :       break;
    2207             :     }
    2208           0 :     case t_QUAD: gaffsg(s,gel(x,2)); gaffsg(0,gel(x,3)); break;
    2209           0 :     default: pari_err_TYPE2("=",stoi(s),x);
    2210             :   }
    2211         966 : }
    2212             : 
    2213             : /*******************************************************************/
    2214             : /*                                                                 */
    2215             : /*                     GENERIC AFFECTATION                         */
    2216             : /*         Affect the content of x to y, whenever possible         */
    2217             : /*                                                                 */
    2218             : /*******************************************************************/
    2219             : /* x PADIC, Y INT, return lift(x * Mod(1,Y)) */
    2220             : GEN
    2221        4543 : padic_to_Fp(GEN x, GEN Y) {
    2222        4543 :   pari_sp av = avma;
    2223        4543 :   GEN p = gel(x,2), z;
    2224        4543 :   long vy, vx = valp(x);
    2225        4543 :   if (!signe(Y)) pari_err_INV("padic_to_Fp",Y);
    2226        4543 :   vy = Z_pvalrem(Y,p, &z);
    2227        4543 :   if (vx < 0 || !gequal1(z)) pari_err_OP("",x, mkintmod(gen_1,Y));
    2228        4529 :   if (vx >= vy) { set_avma(av); return gen_0; }
    2229        4207 :   z = gel(x,4);
    2230        4207 :   if (!signe(z) || vy > vx + precp(x)) pari_err_OP("",x, mkintmod(gen_1,Y));
    2231        4207 :   if (vx) z = mulii(z, powiu(p,vx));
    2232        4207 :   return gerepileuptoint(av, remii(z, Y));
    2233             : }
    2234             : ulong
    2235      217412 : padic_to_Fl(GEN x, ulong Y) {
    2236      217412 :   GEN p = gel(x,2);
    2237             :   ulong u, z;
    2238      217412 :   long vy, vx = valp(x);
    2239      217412 :   vy = u_pvalrem(Y,p, &u);
    2240      217421 :   if (vx < 0 || u != 1) pari_err_OP("",x, mkintmodu(1,Y));
    2241             :   /* Y = p^vy */
    2242      217419 :   if (vx >= vy) return 0;
    2243      212960 :   z = umodiu(gel(x,4), Y);
    2244      212969 :   if (!z || vy > vx + precp(x)) pari_err_OP("",x, mkintmodu(1,Y));
    2245      212969 :   if (vx) {
    2246           0 :     ulong pp = p[2];
    2247           0 :     z = Fl_mul(z, upowuu(pp,vx), Y); /* p^vx < p^vy = Y */
    2248             :   }
    2249      212969 :   return z;
    2250             : }
    2251             : 
    2252             : static void
    2253           0 : croak(const char *s) {
    2254             :   char *t;
    2255           0 :   t = stack_sprintf("gaffect [overwriting universal object: %s]",s);
    2256           0 :   pari_err_BUG(t);
    2257           0 : }
    2258             : 
    2259             : void
    2260      199659 : gaffect(GEN x, GEN y)
    2261             : {
    2262      199659 :   long vx, i, lx, ly, tx = typ(x), ty = typ(y);
    2263             :   pari_sp av;
    2264             :   GEN p1, num, den;
    2265             : 
    2266      199659 :   if (tx == ty) switch(tx) {
    2267      120051 :     case t_INT:
    2268      198693 :       if (!is_universal_constant(y)) { affii(x,y); return; }
    2269             :       /* y = gen_0, gnil, gen_1 or gen_2 */
    2270           0 :       if (y==gen_0)  croak("gen_0");
    2271           0 :       if (y==gen_1)  croak("gen_1");
    2272           0 :       if (y==gen_m1) croak("gen_m1");
    2273           0 :       if (y==gen_m2) croak("gen_m2");
    2274           0 :       if (y==gen_2)  croak("gen_2");
    2275           0 :       croak("gnil)");
    2276        4606 :     case t_REAL: affrr(x,y); return;
    2277           0 :     case t_INTMOD:
    2278           0 :       if (!dvdii(gel(x,1),gel(y,1))) pari_err_OP("",x,y);
    2279           0 :       modiiz(gel(x,2),gel(y,1),gel(y,2)); return;
    2280           0 :     case t_FRAC:
    2281           0 :       affii(gel(x,1),gel(y,1));
    2282           0 :       affii(gel(x,2),gel(y,2)); return;
    2283        1820 :     case t_COMPLEX:
    2284        1820 :       gaffect(gel(x,1),gel(y,1));
    2285        1820 :       gaffect(gel(x,2),gel(y,2)); return;
    2286           0 :     case t_PADIC:
    2287           0 :       if (!equalii(gel(x,2),gel(y,2))) pari_err_OP("",x,y);
    2288           0 :       modiiz(gel(x,4),gel(y,3),gel(y,4));
    2289           0 :       setvalp(y,valp(x)); return;
    2290           0 :     case t_QUAD:
    2291           0 :       if (! ZX_equal(gel(x,1),gel(y,1))) pari_err_OP("",x,y);
    2292           0 :       affii(gel(x,2),gel(y,2));
    2293           0 :       affii(gel(x,3),gel(y,3)); return;
    2294       72216 :     case t_VEC: case t_COL: case t_MAT:
    2295       72216 :       lx = lg(x); if (lx != lg(y)) pari_err_DIM("gaffect");
    2296      192267 :       for (i=1; i<lx; i++) gaffect(gel(x,i),gel(y,i));
    2297       72216 :       return;
    2298             :   }
    2299             : 
    2300             :   /* Various conversions. Avoid them, use specialized routines ! */
    2301             : 
    2302         966 :   if (!is_const_t(ty)) pari_err_TYPE2("=",x,y);
    2303         966 :   switch(tx)
    2304             :   {
    2305           0 :     case t_INT:
    2306             :       switch(ty)
    2307             :       {
    2308           0 :         case t_REAL:
    2309           0 :           affir(x,y); break;
    2310             : 
    2311           0 :         case t_INTMOD:
    2312           0 :           modiiz(x,gel(y,1),gel(y,2)); break;
    2313             : 
    2314           0 :         case t_COMPLEX:
    2315           0 :           gaffect(x,gel(y,1)); gaffsg(0,gel(y,2)); break;
    2316             : 
    2317           0 :         case t_PADIC:
    2318           0 :           if (!signe(x)) { padicaff0(y); break; }
    2319           0 :           av = avma;
    2320           0 :           setvalp(y, Z_pvalrem(x,gel(y,2),&p1));
    2321           0 :           affii(modii(p1,gel(y,3)), gel(y,4));
    2322           0 :           set_avma(av); break;
    2323             : 
    2324           0 :         case t_QUAD: gaffect(x,gel(y,2)); gaffsg(0,gel(y,3)); break;
    2325           0 :         default: pari_err_TYPE2("=",x,y);
    2326             :       }
    2327           0 :       break;
    2328             : 
    2329         966 :     case t_REAL:
    2330             :       switch(ty)
    2331             :       {
    2332         966 :         case t_COMPLEX: gaffect(x,gel(y,1)); gaffsg(0,gel(y,2)); break;
    2333           0 :         default: pari_err_TYPE2("=",x,y);
    2334             :       }
    2335         966 :       break;
    2336             : 
    2337           0 :     case t_FRAC:
    2338             :       switch(ty)
    2339             :       {
    2340           0 :         case t_REAL: rdiviiz(gel(x,1),gel(x,2), y); break;
    2341           0 :         case t_INTMOD: av = avma;
    2342           0 :           p1 = Fp_inv(gel(x,2),gel(y,1));
    2343           0 :           affii(modii(mulii(gel(x,1),p1),gel(y,1)), gel(y,2));
    2344           0 :           set_avma(av); break;
    2345           0 :         case t_COMPLEX: gaffect(x,gel(y,1)); gaffsg(0,gel(y,2)); break;
    2346           0 :         case t_PADIC:
    2347           0 :           if (!signe(gel(x,1))) { padicaff0(y); break; }
    2348           0 :           num = gel(x,1);
    2349           0 :           den = gel(x,2);
    2350           0 :           av = avma; vx = Z_pvalrem(num, gel(y,2), &num);
    2351           0 :           if (!vx) vx = -Z_pvalrem(den,gel(y,2),&den);
    2352           0 :           setvalp(y,vx);
    2353           0 :           p1 = mulii(num,Fp_inv(den,gel(y,3)));
    2354           0 :           affii(modii(p1,gel(y,3)), gel(y,4)); set_avma(av); break;
    2355           0 :         case t_QUAD: gaffect(x,gel(y,2)); gaffsg(0,gel(y,3)); break;
    2356           0 :         default: pari_err_TYPE2("=",x,y);
    2357             :       }
    2358           0 :       break;
    2359             : 
    2360           0 :     case t_COMPLEX:
    2361           0 :       if (!gequal0(gel(x,2))) pari_err_TYPE2("=",x,y);
    2362           0 :       gaffect(gel(x,1), y);
    2363           0 :       break;
    2364             : 
    2365           0 :     case t_PADIC:
    2366             :       switch(ty)
    2367             :       {
    2368           0 :         case t_INTMOD:
    2369           0 :           av = avma; affii(padic_to_Fp(x, gel(y,1)), gel(y,2));
    2370           0 :           set_avma(av); break;
    2371           0 :         default: pari_err_TYPE2("=",x,y);
    2372             :       }
    2373           0 :       break;
    2374             : 
    2375           0 :     case t_QUAD:
    2376             :       switch(ty)
    2377             :       {
    2378           0 :         case t_INT: case t_INTMOD: case t_FRAC: case t_PADIC:
    2379           0 :           pari_err_TYPE2("=",x,y);
    2380             : 
    2381           0 :         case t_REAL:
    2382           0 :           av = avma; affgr(quadtofp(x,realprec(y)), y); set_avma(av); break;
    2383           0 :         case t_COMPLEX:
    2384           0 :           ly = precision(y); if (!ly) pari_err_TYPE2("=",x,y);
    2385           0 :           av = avma; gaffect(quadtofp(x,ly), y); set_avma(av); break;
    2386           0 :         default: pari_err_TYPE2("=",x,y);
    2387             :       }
    2388           0 :     default: pari_err_TYPE2("=",x,y);
    2389             :   }
    2390             : }
    2391             : 
    2392             : /*******************************************************************/
    2393             : /*                                                                 */
    2394             : /*           CONVERSION QUAD --> REAL, COMPLEX OR P-ADIC           */
    2395             : /*                                                                 */
    2396             : /*******************************************************************/
    2397             : GEN
    2398         245 : quadtofp(GEN x, long prec)
    2399             : {
    2400         245 :   GEN b, D, z, u = gel(x,2), v = gel(x,3);
    2401             :   pari_sp av;
    2402         245 :   if (prec < LOWDEFAULTPREC) prec = LOWDEFAULTPREC;
    2403         245 :   if (isintzero(v)) return cxcompotor(u, prec);
    2404         245 :   av = avma; D = quad_disc(x); b = gel(gel(x,1),3); /* 0 or -1 */
    2405             :   /* u + v (-b + sqrt(D)) / 2 */
    2406         245 :   if (!signe(b)) b = NULL;
    2407         245 :   if (b) u = gadd(gmul2n(u,1), v);
    2408         245 :   z = sqrtr_abs(itor(D, prec));
    2409         245 :   if (!b) shiftr_inplace(z, -1);
    2410         245 :   z = gmul(v, z);
    2411         245 :   if (signe(D) < 0)
    2412             :   {
    2413          35 :     z = mkcomplex(cxcompotor(u, prec), z);
    2414          35 :     if (!b) return gerepilecopy(av, z);
    2415           0 :     z = gmul2n(z, -1);
    2416             :   }
    2417             :   else
    2418             :   { /* if (b) x ~ (u + z) / 2 and quadnorm(x) ~ (u^2 - z^2) / 4
    2419             :      * else x ~ u + z and quadnorm(x) ~ u^2 - z^2 */
    2420         210 :     long s = signe(u);
    2421         210 :     if (s == -signe(v)) /* conjugate expression avoids cancellation */
    2422             :     {
    2423          14 :       z = gdiv(quadnorm(x), gsub(u, z));
    2424          14 :       if (b) shiftr_inplace(z, 1);
    2425             :     }
    2426             :     else
    2427             :     {
    2428         196 :       if (s) z = gadd(u, z);
    2429         196 :       if (b) shiftr_inplace(z, -1);
    2430             :     }
    2431             :   }
    2432         210 :   return gerepileupto(av, z);
    2433             : }
    2434             : 
    2435             : static GEN
    2436          28 : qtop(GEN x, GEN p, long d)
    2437             : {
    2438          28 :   GEN z, D, P, b, u = gel(x,2), v = gel(x,3);
    2439             :   pari_sp av;
    2440          28 :   if (gequal0(v)) return cvtop(u, p, d);
    2441          28 :   P = gel(x,1);
    2442          28 :   b = gel(P,3);
    2443          28 :   av = avma; D = quad_disc(x);
    2444          28 :   if (absequaliu(p,2)) d += 2;
    2445          28 :   z = Qp_sqrt(cvtop(D,p,d));
    2446          28 :   if (!z) pari_err_SQRTN("Qp_sqrt",D);
    2447          14 :   z = gmul2n(gsub(z, b), -1);
    2448             : 
    2449          14 :   z = gadd(u, gmul(v, z));
    2450          14 :   if (typ(z) != t_PADIC) /* t_INTMOD for t_QUAD of t_INTMODs... */
    2451           0 :     z = cvtop(z, p, d);
    2452          14 :   return gerepileupto(av, z);
    2453             : }
    2454             : static GEN
    2455          14 : ctop(GEN x, GEN p, long d)
    2456             : {
    2457          14 :   pari_sp av = avma;
    2458          14 :   GEN z, u = gel(x,1), v = gel(x,2);
    2459          14 :   if (isrationalzero(v)) return cvtop(u, p, d);
    2460          14 :   z = Qp_sqrt(cvtop(gen_m1, p, d - gvaluation(v, p))); /* = I */
    2461          14 :   if (!z) pari_err_SQRTN("Qp_sqrt",gen_m1);
    2462             : 
    2463          14 :   z = gadd(u, gmul(v, z));
    2464          14 :   if (typ(z) != t_PADIC) /* t_INTMOD for t_COMPLEX of t_INTMODs... */
    2465           0 :     z = cvtop(z, p, d);
    2466          14 :   return gerepileupto(av, z);
    2467             : }
    2468             : 
    2469             : /* cvtop2(stoi(s), y) */
    2470             : GEN
    2471         266 : cvstop2(long s, GEN y)
    2472             : {
    2473         266 :   GEN z, p = gel(y,2);
    2474         266 :   long v, d = signe(gel(y,4))? precp(y): 0;
    2475         266 :   if (!s) return zeropadic_shallow(p, d);
    2476         266 :   v = z_pvalrem(s, p, &s);
    2477         266 :   if (d <= 0) return zeropadic_shallow(p, v);
    2478         266 :   z = cgetg(5, t_PADIC);
    2479         266 :   z[1] = evalprecp(d) | evalvalp(v);
    2480         266 :   gel(z,2) = p;
    2481         266 :   gel(z,3) = gel(y,3);
    2482         266 :   gel(z,4) = modsi(s, gel(y,3)); return z;
    2483             : }
    2484             : 
    2485             : static GEN
    2486     8543414 : itop2_coprime(GEN x, GEN y, long v, long d)
    2487             : {
    2488     8543414 :   GEN z = cgetg(5, t_PADIC);
    2489     8542714 :   z[1] = evalprecp(d) | evalvalp(v);
    2490     8542538 :   gel(z,2) = gel(y,2);
    2491     8542538 :   gel(z,3) = gel(y,3);
    2492     8542538 :   gel(z,4) = modii(x, gel(y,3)); return z;
    2493             : }
    2494             : /* cvtop(x, gel(y,2), precp(y)), shallow */
    2495             : GEN
    2496     8549536 : cvtop2(GEN x, GEN y)
    2497             : {
    2498     8549536 :   GEN p = gel(y,2);
    2499     8549536 :   long v, d = signe(gel(y,4))? precp(y): 0;
    2500     8549536 :   switch(typ(x))
    2501             :   {
    2502     4920222 :     case t_INT:
    2503     4920222 :       if (!signe(x)) return zeropadic_shallow(p, d);
    2504     4920222 :       if (d <= 0) return zeropadic_shallow(p, Z_pval(x,p));
    2505     4915910 :       v = Z_pvalrem(x, p, &x); return itop2_coprime(x, y, v, d);
    2506             : 
    2507           0 :     case t_INTMOD:
    2508           0 :       v = Z_pval(gel(x,1),p); if (v > d) v = d;
    2509           0 :       return cvtop(gel(x,2), p, v);
    2510             : 
    2511     3629356 :     case t_FRAC:
    2512             :     {
    2513             :       GEN num, den;
    2514     3629356 :       if (d <= 0) return zeropadic_shallow(p, Q_pval(x,p));
    2515     3628075 :       num = gel(x,1); v = Z_pvalrem(num, p, &num);
    2516     3628078 :       den = gel(x,2); if (!v) v = -Z_pvalrem(den, p, &den);
    2517     3628084 :       if (!is_pm1(den)) num = mulii(num, Fp_inv(den, gel(y,3)));
    2518     3628086 :       return itop2_coprime(num, y, v, d);
    2519             :     }
    2520           7 :     case t_COMPLEX: return ctop(x, p, d);
    2521          28 :     case t_QUAD:    return qtop(x, p, d);
    2522         147 :     case t_PADIC:
    2523         147 :       if (!signe(gel(x,4))) return zeropadic_shallow(p, d);
    2524         147 :       if (precp(x) <= d) return x;
    2525          35 :       return itop2_coprime(gel(x,4), y, valp(x), d); /* reduce accuracy */
    2526             :   }
    2527           0 :   pari_err_TYPE("cvtop2",x);
    2528             :   return NULL; /* LCOV_EXCL_LINE */
    2529             : }
    2530             : 
    2531             : /* assume is_const_t(tx) */
    2532             : GEN
    2533      616207 : cvtop(GEN x, GEN p, long d)
    2534             : {
    2535             :   GEN z;
    2536             :   long v;
    2537             : 
    2538      616207 :   if (typ(p) != t_INT) pari_err_TYPE("cvtop",p);
    2539      616207 :   switch(typ(x))
    2540             :   {
    2541       65737 :     case t_INT:
    2542       65737 :       if (!signe(x)) return zeropadic(p, d);
    2543       64519 :       if (d <= 0) return zeropadic(p, Z_pval(x,p));
    2544       64512 :       v = Z_pvalrem(x, p, &x);
    2545       64512 :       z = cgetg(5, t_PADIC);
    2546       64512 :       z[1] = evalprecp(d) | evalvalp(v);
    2547       64512 :       gel(z,2) = icopy(p);
    2548       64513 :       gel(z,3) = powiu(p, d);
    2549       64513 :       gel(z,4) = modii(x, gel(z,3)); return z; /* not memory-clean */
    2550             : 
    2551          28 :     case t_INTMOD:
    2552          28 :       v = Z_pval(gel(x,1),p); if (v > d) v = d;
    2553          28 :       return cvtop(gel(x,2), p, v);
    2554             : 
    2555      273032 :     case t_FRAC:
    2556             :     {
    2557             :       GEN num, den;
    2558      273032 :       if (d <= 0) return zeropadic(p, Q_pval(x,p));
    2559      273018 :       num = gel(x,1); v = Z_pvalrem(num, p, &num);
    2560      273018 :       den = gel(x,2); if (!v) v = -Z_pvalrem(den, p, &den);
    2561      273018 :       z = cgetg(5, t_PADIC);
    2562      273018 :       z[1] = evalprecp(d) | evalvalp(v);
    2563      273018 :       gel(z,2) = icopy(p);
    2564      273018 :       gel(z,3) = powiu(p, d);
    2565      273020 :       if (!is_pm1(den)) num = mulii(num, Fp_inv(den, gel(z,3)));
    2566      273019 :       gel(z,4) = modii(num, gel(z,3)); return z; /* not memory-clean */
    2567             :     }
    2568           7 :     case t_COMPLEX: return ctop(x, p, d);
    2569      277403 :     case t_PADIC:
    2570      277403 :       p = gel(x,2); /* override */
    2571      277403 :       if (!signe(gel(x,4))) return zeropadic(p, d);
    2572      277403 :       z = cgetg(5,t_PADIC);
    2573      277403 :       z[1] = x[1]; setprecp(z,d);
    2574      277403 :       gel(z,2) = icopy(p);
    2575      277403 :       gel(z,3) = powiu(p, d);
    2576      277403 :       gel(z,4) = modii(gel(x,4), gel(z,3)); return z;
    2577             : 
    2578           0 :     case t_QUAD: return qtop(x, p, d);
    2579             :   }
    2580           0 :   pari_err_TYPE("cvtop",x);
    2581             :   return NULL; /* LCOV_EXCL_LINE */
    2582             : }
    2583             : 
    2584             : GEN
    2585         126 : gcvtop(GEN x, GEN p, long r)
    2586             : {
    2587             :   long i, lx;
    2588             :   GEN y;
    2589             : 
    2590         126 :   switch(typ(x))
    2591             :   {
    2592          28 :     case t_POL: case t_SER:
    2593          28 :       y = cgetg_copy(x, &lx); y[1] = x[1];
    2594          98 :       for (i=2; i<lx; i++) gel(y,i) = gcvtop(gel(x,i),p,r);
    2595          28 :       return y;
    2596           0 :     case t_POLMOD: case t_RFRAC: case t_VEC: case t_COL: case t_MAT:
    2597           0 :       pari_APPLY_same(gcvtop(gel(x,i),p,r));
    2598             :   }
    2599          98 :   return cvtop(x,p,r);
    2600             : }
    2601             : 
    2602             : long
    2603   545107080 : gexpo_safe(GEN x)
    2604             : {
    2605   545107080 :   long tx = typ(x), lx, e, f, i;
    2606             : 
    2607   545107080 :   switch(tx)
    2608             :   {
    2609   101771827 :     case t_INT:
    2610   101771827 :       return expi(x);
    2611             : 
    2612      947775 :     case t_FRAC:
    2613      947775 :       return expi(gel(x,1)) - expi(gel(x,2));
    2614             : 
    2615   300988792 :     case t_REAL:
    2616   300988792 :       return expo(x);
    2617             : 
    2618    88484935 :     case t_COMPLEX:
    2619    88484935 :       e = gexpo(gel(x,1));
    2620    88486862 :       f = gexpo(gel(x,2)); return maxss(e, f);
    2621             : 
    2622          84 :     case t_QUAD: {
    2623          84 :       GEN p = gel(x,1); /* mod = X^2 + {0,1}* X - {D/4, (1-D)/4})*/
    2624          84 :       long d = 1 + expi(gel(p,2))/2; /* ~ expo(sqrt(D)) */
    2625          84 :       e = gexpo(gel(x,2));
    2626          84 :       f = gexpo(gel(x,3)) + d; return maxss(e, f);
    2627             :     }
    2628    44952140 :     case t_POL: case t_SER:
    2629    44952140 :       lx = lg(x); f = -(long)HIGHEXPOBIT;
    2630   200639415 :       for (i=2; i<lx; i++) { e=gexpo(gel(x,i)); if (e>f) f=e; }
    2631    44947902 :       return f;
    2632     8100926 :     case t_VEC: case t_COL: case t_MAT:
    2633     8100926 :       lx = lg(x); f = -(long)HIGHEXPOBIT;
    2634    76495307 :       for (i=1; i<lx; i++) { e=gexpo(gel(x,i)); if (e>f) f=e; }
    2635     8100804 :       return f;
    2636             :   }
    2637          48 :   return -1-(long)HIGHEXPOBIT;
    2638             : }
    2639             : long
    2640   544876735 : gexpo(GEN x)
    2641             : {
    2642   544876735 :   long e = gexpo_safe(x);
    2643   544919409 :   if (e < -(long)HIGHEXPOBIT) pari_err_TYPE("gexpo",x);
    2644   544921677 :   return e;
    2645             : }
    2646             : GEN
    2647       88781 : gpexponent(GEN x)
    2648             : {
    2649       88781 :   long e = gexpo(x);
    2650       88781 :   return e == -(long)HIGHEXPOBIT? mkmoo(): stoi(e);
    2651             : }
    2652             : 
    2653             : long
    2654           7 : sizedigit(GEN x)
    2655             : {
    2656           7 :   return gequal0(x)? 0: (long) ((gexpo(x)+1) * LOG10_2) + 1;
    2657             : }
    2658             : 
    2659             : /* normalize series. avma is not updated */
    2660             : GEN
    2661    12817701 : normalizeser(GEN x)
    2662             : {
    2663    12817701 :   long i, lx = lg(x), vx=varn(x), vp=valp(x);
    2664             :   GEN y, z;
    2665             : 
    2666    12817701 :   if (lx == 2) { setsigne(x,0); return x; }
    2667    12817337 :   if (lx == 3) {
    2668      189318 :     z = gel(x,2);
    2669      189318 :     if (!gequal0(z)) { setsigne(x,1); return x; }
    2670       21903 :     if (isrationalzero(z)) return zeroser(vx,vp+1);
    2671        3360 :     if (isexactzero(z)) {
    2672             :       /* dangerous case: already normalized ? */
    2673         245 :       if (!signe(x)) return x;
    2674          35 :       setvalp(x,vp+1); /* no: normalize */
    2675             :     }
    2676        3150 :     setsigne(x,0); return x;
    2677             :   }
    2678    12917032 :   for (i=2; i<lx; i++)
    2679    12870489 :     if (! isrationalzero(gel(x,i))) break;
    2680    12628019 :   if (i == lx) return zeroser(vx,lx-2+vp);
    2681    12581476 :   z = gel(x,i);
    2682    12585277 :   while (i<lx && isexactzero(gel(x,i))) i++;
    2683    12581476 :   if (i == lx)
    2684             :   {
    2685         273 :     i -= 3; y = x + i;
    2686         273 :     stackdummy((pari_sp)y, (pari_sp)x);
    2687         273 :     gel(y,2) = z;
    2688         273 :     y[1] = evalsigne(0) | evalvalp(lx-2+vp) | evalvarn(vx);
    2689         273 :     y[0] = evaltyp(t_SER) | _evallg(3);
    2690         273 :     return y;
    2691             :   }
    2692             : 
    2693    12581203 :   i -= 2; y = x + i; lx -= i;
    2694    12581203 :   y[1] = evalsigne(1) | evalvalp(vp+i) | evalvarn(vx);
    2695    12581203 :   y[0] = evaltyp(t_SER) | evallg(lx);
    2696             : 
    2697    12581203 :   stackdummy((pari_sp)y, (pari_sp)x);
    2698    12611119 :   for (i = 2; i < lx; i++)
    2699    12610181 :     if (!gequal0(gel(y, i))) return y;
    2700         938 :   setsigne(y, 0); return y;
    2701             : }
    2702             : 
    2703             : GEN
    2704           0 : normalizepol_approx(GEN x, long lx)
    2705             : {
    2706             :   long i;
    2707           0 :   for (i = lx-1; i>1; i--)
    2708           0 :     if (! gequal0(gel(x,i))) break;
    2709           0 :   stackdummy((pari_sp)(x + lg(x)), (pari_sp)(x + i+1));
    2710           0 :   setlg(x, i+1); setsigne(x, i!=1); return x;
    2711             : }
    2712             : 
    2713             : GEN
    2714   597549319 : normalizepol_lg(GEN x, long lx)
    2715             : {
    2716   597549319 :   long i, LX = 0;
    2717   597549319 :   GEN KEEP = NULL;
    2718             : 
    2719   793589965 :   for (i = lx-1; i>1; i--)
    2720             :   {
    2721   728794209 :     GEN z = gel(x,i);
    2722   728794209 :     if (! gequal0(z) ) {
    2723   533042215 :       if (!LX) LX = i+1;
    2724   533042215 :       stackdummy((pari_sp)(x + lg(x)), (pari_sp)(x + LX));
    2725   533106653 :       x[0] = evaltyp(t_POL) | evallg(LX);
    2726   533073423 :       setsigne(x,1); return x;
    2727   195756516 :     } else if (!isexactzero(z)) {
    2728      756071 :       if (!LX) LX = i+1; /* to be kept as leading coeff */
    2729   195287247 :     } else if (!isrationalzero(z))
    2730      694036 :       KEEP = z; /* to be kept iff all other coeffs are exact 0s */
    2731             :   }
    2732    64795756 :   if (!LX) {
    2733    64468207 :     if (KEEP) { /* e.g. Pol(Mod(0,2)) */
    2734      347252 :       gel(x,2) = KEEP;
    2735      347252 :       LX = 3;
    2736             :     } else
    2737    64120955 :       LX = 2; /* Pol(0) */
    2738             :   }
    2739    64795756 :   stackdummy((pari_sp)(x + lg(x)), (pari_sp)(x + LX));
    2740    64715106 :   x[0] = evaltyp(t_POL) | evallg(LX);
    2741    64707483 :   setsigne(x,0); return x;
    2742             : }
    2743             : 
    2744             : /* normalize polynomial x in place */
    2745             : GEN
    2746    58581266 : normalizepol(GEN x)
    2747             : {
    2748    58581266 :   return normalizepol_lg(x, lg(x));
    2749             : }
    2750             : 
    2751             : int
    2752    18231356 : gsigne(GEN x)
    2753             : {
    2754    18231356 :   switch(typ(x))
    2755             :   {
    2756    17842123 :     case t_INT: case t_REAL: return signe(x);
    2757      388605 :     case t_FRAC: return signe(gel(x,1));
    2758         623 :     case t_QUAD:
    2759             :     {
    2760         623 :       pari_sp av = avma;
    2761         623 :       GEN T = gel(x,1), a = gel(x,2), b = gel(x,3);
    2762             :       long sa, sb;
    2763         623 :       if (signe(gel(T,2)) > 0) break;
    2764         609 :       a = gmul2n(a,1);
    2765         609 :       if (signe(gel(T,3))) a = gadd(a,b);
    2766             :       /* a + b sqrt(D) > 0 ? */
    2767         609 :       sa = gsigne(a);
    2768         609 :       sb = gsigne(b); if (sa == sb) return gc_int(av,sa);
    2769         224 :       if (sa == 0) return gc_int(av,sb);
    2770         217 :       if (sb == 0) return gc_int(av,sa);
    2771             :       /* different signs, take conjugate expression */
    2772         210 :       sb = gsigne(gsub(gsqr(a), gmul(quad_disc(x), gsqr(b))));
    2773         210 :       return gc_int(av, sb*sa);
    2774             :     }
    2775           7 :     case t_INFINITY: return inf_get_sign(x);
    2776             :   }
    2777          12 :   pari_err_TYPE("gsigne",x);
    2778             :   return 0; /* LCOV_EXCL_LINE */
    2779             : }
    2780             : 
    2781             : /*******************************************************************/
    2782             : /*                                                                 */
    2783             : /*                              LISTS                              */
    2784             : /*                                                                 */
    2785             : /*******************************************************************/
    2786             : /* make sure L can hold l elements, at least doubling the previous max number
    2787             :  * of components. */
    2788             : static void
    2789      791217 : ensure_nb(GEN L, long l)
    2790             : {
    2791      791217 :   long nmax = list_nmax(L), i, lw;
    2792             :   GEN v, w;
    2793      791217 :   if (l <= nmax) return;
    2794         665 :   if (nmax)
    2795             :   {
    2796         273 :     nmax <<= 1;
    2797         273 :     if (l > nmax) nmax = l;
    2798         273 :     w = list_data(L); lw = lg(w);
    2799         273 :     v = newblock(nmax+1);
    2800         273 :     v[0] = w[0];
    2801     1045653 :     for (i=1; i < lw; i++) gel(v,i) = gel(w, i);
    2802         273 :     killblock(w);
    2803             :   }
    2804             :   else /* unallocated */
    2805             :   {
    2806         392 :     nmax = 32;
    2807         392 :     if (list_data(L))
    2808           0 :       pari_err(e_MISC, "store list in variable before appending elements");
    2809         392 :     v = newblock(nmax+1);
    2810         392 :     v[0] = evaltyp(t_VEC) | _evallg(1);
    2811             :   }
    2812         665 :   list_data(L) = v;
    2813         665 :   L[1] = evaltyp(list_typ(L))|evallg(nmax);
    2814             : }
    2815             : 
    2816             : void
    2817           7 : listkill(GEN L)
    2818             : {
    2819             : 
    2820           7 :   if (typ(L) != t_LIST) pari_err_TYPE("listkill",L);
    2821           7 :   if (list_nmax(L)) {
    2822           7 :     GEN v = list_data(L);
    2823           7 :     long i, l = lg(v);
    2824          49 :     for (i=1; i<l; i++) gunclone_deep(gel(v,i));
    2825           7 :     killblock(v);
    2826           7 :     L[1] = evaltyp(list_typ(L));
    2827           7 :     list_data(L) = NULL;
    2828             :   }
    2829           7 : }
    2830             : 
    2831             : GEN
    2832        6345 : mklist_typ(long t)
    2833             : {
    2834        6345 :   GEN L = cgetg(3,t_LIST);
    2835        6345 :   L[1] = evaltyp(t);
    2836        6345 :   list_data(L) = NULL; return L;
    2837             : }
    2838             : 
    2839             : GEN
    2840        6289 : mklist(void)
    2841             : {
    2842        6289 :   return mklist_typ(t_LIST_RAW);
    2843             : }
    2844             : 
    2845             : GEN
    2846          49 : mkmap(void)
    2847             : {
    2848          49 :   return mklist_typ(t_LIST_MAP);
    2849             : }
    2850             : 
    2851             : /* return a list with single element x, allocated on stack */
    2852             : GEN
    2853          56 : mklistcopy(GEN x)
    2854             : {
    2855          56 :   GEN y = mklist();
    2856          56 :   list_data(y) = mkveccopy(x);
    2857          56 :   return y;
    2858             : }
    2859             : 
    2860             : GEN
    2861           7 : listcreate_gp(long n)
    2862             : {
    2863           7 :   (void) n; return mklist();
    2864             : }
    2865             : 
    2866             : GEN
    2867      756371 : listput(GEN L, GEN x, long index)
    2868             : {
    2869             :   long l;
    2870             :   GEN z;
    2871             : 
    2872      756371 :   if (index < 0) pari_err_COMPONENT("listput", "<", gen_0, stoi(index));
    2873      756364 :   z = list_data(L);
    2874      756364 :   l = z? lg(z): 1;
    2875             : 
    2876      756364 :   x = gclone(x);
    2877      756364 :   if (!index || index >= l)
    2878             :   {
    2879      756210 :     ensure_nb(L, l);
    2880      756210 :     z = list_data(L); /* it may change ! */
    2881      756210 :     index = l;
    2882      756210 :     l++;
    2883             :   } else
    2884         154 :     gunclone_deep( gel(z, index) );
    2885      756364 :   gel(z,index) = x;
    2886      756364 :   z[0] = evaltyp(t_VEC) | evallg(l); /*must be after gel(z,index) is set*/
    2887      756364 :   return gel(z,index);
    2888             : }
    2889             : 
    2890             : GEN
    2891      705208 : listput0(GEN L, GEN x, long index)
    2892             : {
    2893      705208 :   if (typ(L) != t_LIST || list_typ(L) != t_LIST_RAW)
    2894          14 :     pari_err_TYPE("listput",L);
    2895      705194 :   return listput(L, x, index);
    2896             : }
    2897             : 
    2898             : GEN
    2899       35028 : listinsert(GEN L, GEN x, long index)
    2900             : {
    2901             :   long l, i;
    2902             :   GEN z;
    2903             : 
    2904       35028 :   if (typ(L) != t_LIST || list_typ(L) != t_LIST_RAW)
    2905          14 :     pari_err_TYPE("listinsert",L);
    2906       35014 :   z = list_data(L); l = z? lg(z): 1;
    2907       35014 :   if (index <= 0) pari_err_COMPONENT("listinsert", "<=", gen_0, stoi(index));
    2908       35007 :   if (index > l) index = l;
    2909       35007 :   ensure_nb(L, l);
    2910       35007 :   BLOCK_SIGINT_START
    2911       35007 :   z = list_data(L);
    2912    87552507 :   for (i=l; i > index; i--) gel(z,i) = gel(z,i-1);
    2913       35007 :   z[0] = evaltyp(t_VEC) | evallg(l+1);
    2914       35007 :   gel(z,index) = gclone(x);
    2915       35007 :   BLOCK_SIGINT_END
    2916       35007 :   return gel(z,index);
    2917             : }
    2918             : 
    2919             : void
    2920       21917 : listpop(GEN L, long index)
    2921             : {
    2922             :   long l, i;
    2923             :   GEN z;
    2924             : 
    2925       21917 :   if (typ(L) != t_LIST) pari_err_TYPE("listinsert",L);
    2926       21917 :   if (index < 0) pari_err_COMPONENT("listpop", "<", gen_0, stoi(index));
    2927       21917 :   z = list_data(L);
    2928       21917 :   if (!z || (l = lg(z)-1) == 0) return;
    2929             : 
    2930       21903 :   if (!index || index > l) index = l;
    2931       21903 :   BLOCK_SIGINT_START
    2932       21903 :   gunclone_deep( gel(z, index) );
    2933       21903 :   z[0] = evaltyp(t_VEC) | evallg(l);
    2934       21910 :   for (i=index; i < l; i++) z[i] = z[i+1];
    2935       21903 :   BLOCK_SIGINT_END
    2936             : }
    2937             : 
    2938             : void
    2939          56 : listpop0(GEN L, long index)
    2940             : {
    2941          56 :   if (typ(L) != t_LIST || list_typ(L) != t_LIST_RAW)
    2942          14 :     pari_err_TYPE("listpop",L);
    2943          42 :   listpop(L, index);
    2944          42 : }
    2945             : 
    2946             : /* return a copy fully allocated on stack. gclone from changevalue is
    2947             :  * supposed to malloc() it */
    2948             : GEN
    2949        5517 : gtolist(GEN x)
    2950             : {
    2951             :   GEN y;
    2952             : 
    2953        5517 :   if (!x) return mklist();
    2954         349 :   switch(typ(x))
    2955             :   {
    2956         286 :     case t_VEC: case t_COL:
    2957         286 :       y = mklist();
    2958         286 :       if (lg(x) == 1) return y;
    2959         265 :       list_data(y) = gcopy(x);
    2960         265 :       settyp(list_data(y), t_VEC);
    2961         265 :       return y;
    2962           7 :     case t_LIST:
    2963           7 :       y = mklist();
    2964           7 :       list_data(y) = list_data(x)? gcopy(list_data(x)): NULL;
    2965           7 :       return y;
    2966          56 :     default:
    2967          56 :       return mklistcopy(x);
    2968             :   }
    2969             : }
    2970             : 
    2971             : void
    2972          21 : listsort(GEN L, long flag)
    2973             : {
    2974             :   long i, l;
    2975          21 :   pari_sp av = avma;
    2976             :   GEN perm, v, vnew;
    2977             : 
    2978          21 :   if (typ(L) != t_LIST) pari_err_TYPE("listsort",L);
    2979          21 :   v = list_data(L); l = v? lg(v): 1;
    2980          21 :   if (l < 3) return;
    2981          21 :   if (flag)
    2982             :   {
    2983             :     long lnew;
    2984          14 :     perm = gen_indexsort_uniq(L, (void*)&cmp_universal, cmp_nodata);
    2985          14 :     lnew = lg(perm); /* may have changed since 'uniq' */
    2986          14 :     vnew = cgetg(lnew,t_VEC);
    2987          56 :     for (i=1; i<lnew; i++) {
    2988          42 :       long c = perm[i];
    2989          42 :       gel(vnew,i) = gel(v,c);
    2990          42 :       gel(v,c) = NULL;
    2991             :     }
    2992          14 :     if (l != lnew) { /* was shortened */
    2993         105 :       for (i=1; i<l; i++)
    2994          91 :         if (gel(v,i)) gunclone_deep(gel(v,i));
    2995          14 :       l = lnew;
    2996             :     }
    2997             :   }
    2998             :   else
    2999             :   {
    3000           7 :     perm = gen_indexsort(L, (void*)&cmp_universal, cmp_nodata);
    3001           7 :     vnew = cgetg(l,t_VEC);
    3002          63 :     for (i=1; i<l; i++) gel(vnew,i) = gel(v,perm[i]);
    3003             :   }
    3004         119 :   for (i=1; i<l; i++) gel(v,i) = gel(vnew,i);
    3005          21 :   v[0] = vnew[0]; set_avma(av);
    3006             : }

Generated by: LCOV version 1.13