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.16.2 lcov report (development 29464-65cd88daf0) Lines: 1585 1801 88.0 %
Date: 2024-07-23 09:03:50 Functions: 149 161 92.5 %
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         462 : map_proto_G(GEN (*f)(GEN), GEN x)
      31             : {
      32         462 :   if (is_matvec_t(typ(x))) pari_APPLY_same(map_proto_G(f, gel(x,i)));
      33         462 :   return f(x);
      34             : }
      35             : 
      36             : GEN
      37    37212943 : map_proto_lG(long (*f)(GEN), GEN x)
      38             : {
      39    37213027 :   if (is_matvec_t(typ(x))) pari_APPLY_same(map_proto_lG(f, gel(x,i)));
      40    37217192 :   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     2204941 : _domul(void *data, GEN x, GEN y)
      52             : {
      53     2204941 :   GEN (*mul)(GEN,GEN)=(GEN (*)(GEN,GEN)) data;
      54     2204941 :   return mul(x,y);
      55             : }
      56             : 
      57             : GEN
      58     2418437 : gassoc_proto(GEN (*f)(GEN,GEN), GEN x, GEN y)
      59             : {
      60     2418437 :   if (!y)
      61             :   {
      62     2418437 :     pari_sp av = avma;
      63     2418437 :     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     2418423 :       case t_COL: break;
      69           7 :       default: pari_err_TYPE("association",x);
      70             :     }
      71     2418423 :     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    16899413 : cgetp(GEN x)
      83             : {
      84    16899413 :   GEN y = cgetg(5,t_PADIC);
      85    16899418 :   y[1] = (x[1]&PRECPBITS) | _evalvalp(0);
      86    16899418 :   gel(y,2) = icopy(gel(x,2));
      87    16899363 :   gel(y,3) = icopy(gel(x,3));
      88    16899412 :   gel(y,4) = cgeti(lgefint(gel(x,3))); return y;
      89             : }
      90             : 
      91             : /*******************************************************************/
      92             : /*                                                                 */
      93             : /*                            SIZES                                */
      94             : /*                                                                 */
      95             : /*******************************************************************/
      96             : 
      97             : long
      98     5141966 : glength(GEN x)
      99             : {
     100     5141966 :   long tx = typ(x);
     101     5141966 :   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     5141185 :   return lg(x) - lontyp[tx];
     113             : }
     114             : 
     115             : long
     116           0 : gtranslength(GEN x)
     117             : {
     118           0 :   switch(typ(x))
     119             :   {
     120           0 :     case t_VEC: case t_COL:
     121           0 :       return lg(x)-1;
     122           0 :     case t_MAT:
     123           0 :       return lg(x)==1 ? 0: nbrows(x);
     124           0 :     default:
     125           0 :       pari_err_TYPE("trans",x);
     126             :       return 0; /* LCOV_EXCL_LINE */
     127             :   }
     128             : }
     129             : 
     130             : GEN
     131         203 : matsize(GEN x)
     132             : {
     133         203 :   long L = lg(x) - 1;
     134         203 :   switch(typ(x))
     135             :   {
     136           7 :     case t_VEC: return mkvec2s(1, L);
     137           7 :     case t_COL: return mkvec2s(L, 1);
     138         182 :     case t_MAT: return mkvec2s(L? nbrows(x): 0, L);
     139             :   }
     140           7 :   pari_err_TYPE("matsize",x);
     141             :   return NULL; /* LCOV_EXCL_LINE */
     142             : }
     143             : 
     144             : /*******************************************************************/
     145             : /*                                                                 */
     146             : /*                 CONVERSION GEN --> long                         */
     147             : /*                                                                 */
     148             : /*******************************************************************/
     149             : 
     150             : long
     151          77 : gtolong(GEN x)
     152             : {
     153          77 :   switch(typ(x))
     154             :   {
     155          42 :     case t_INT:
     156          42 :       return itos(x);
     157           7 :     case t_REAL:
     158           7 :       return (long)(rtodbl(x) + 0.5);
     159           7 :     case t_FRAC:
     160           7 :     { pari_sp av = avma; return gc_long(av, itos(ground(x))); }
     161           7 :     case t_COMPLEX:
     162           7 :       if (gequal0(gel(x,2))) return gtolong(gel(x,1)); break;
     163           7 :     case t_QUAD:
     164           7 :       if (gequal0(gel(x,3))) return gtolong(gel(x,2)); break;
     165             :   }
     166           7 :   pari_err_TYPE("gtolong",x);
     167             :   return 0; /* LCOV_EXCL_LINE */
     168             : }
     169             : 
     170             : /*******************************************************************/
     171             : /*                                                                 */
     172             : /*                         COMPARISONS                             */
     173             : /*                                                                 */
     174             : /*******************************************************************/
     175             : static void
     176         189 : chk_true_err()
     177             : {
     178         189 :   GEN E = pari_err_last();
     179         189 :   switch(err_get_num(E))
     180             :   {
     181           0 :     case e_STACK: case e_MEM: case e_ALARM:
     182           0 :       pari_err(0, E); /* rethrow */
     183             :   }
     184         189 : }
     185             : /* x - y == 0 or undefined */
     186             : static int
     187     3196114 : gequal_try(GEN x, GEN y)
     188             : {
     189             :   int i;
     190     3196114 :   pari_CATCH(CATCH_ALL) { chk_true_err(); return 0; }
     191     3196114 :   pari_TRY { i = gequal0(gadd(x, gneg_i(y))); } pari_ENDCATCH;
     192     3195932 :   return i;
     193             : }
     194             : /* x + y == 0 or undefined */
     195             : static int
     196          28 : gmequal_try(GEN x, GEN y)
     197             : {
     198             :   int i;
     199          28 :   pari_CATCH(CATCH_ALL) { chk_true_err(); return 0; }
     200          28 :   pari_TRY { i = gequal0(gadd(x, y)); } pari_ENDCATCH;
     201          21 :   return i;
     202             : }
     203             : 
     204             : int
     205   450645210 : isexactzero(GEN g)
     206             : {
     207             :   long i, lx;
     208   450645210 :   switch (typ(g))
     209             :   {
     210   392710788 :     case t_INT:
     211   392710788 :       return !signe(g);
     212     1242198 :     case t_INTMOD:
     213     1242198 :       return !signe(gel(g,2));
     214    14809508 :     case t_COMPLEX:
     215    14809508 :       return isexactzero(gel(g,1)) && isexactzero(gel(g,2));
     216     8107278 :     case t_FFELT:
     217     8107278 :       return FF_equal0(g);
     218         511 :     case t_QUAD:
     219         511 :       return isexactzero(gel(g,2)) && isexactzero(gel(g,3));
     220      290159 :     case t_POLMOD:
     221      290159 :       return isexactzero(gel(g,2));
     222    12069531 :     case t_POL:
     223    12069531 :       lx = lg(g); /* cater for Mod(0,2)*x^0 */
     224    12069531 :       return lx == 2 || (lx == 3 && isexactzero(gel(g,2)));
     225      462452 :     case t_RFRAC:
     226      462452 :       return isexactzero(gel(g,1)); /* may occur: Mod(0,2)/x */
     227       43435 :     case t_VEC: case t_COL: case t_MAT:
     228       43820 :       for (i=lg(g)-1; i; i--)
     229       43673 :         if (!isexactzero(gel(g,i))) return 0;
     230         147 :       return 1;
     231             :   }
     232    20909350 :   return 0;
     233             : }
     234             : GEN
     235    63700610 : gisexactzero(GEN g)
     236             : {
     237             :   long i, lx;
     238             :   GEN a, b;
     239    63700610 :   switch (typ(g))
     240             :   {
     241    26747734 :     case t_INT:
     242    26747734 :       return !signe(g)? g: NULL;
     243     7065821 :     case t_INTMOD:
     244     7065821 :       return !signe(gel(g,2))? g: NULL;
     245        2632 :     case t_COMPLEX:
     246        2632 :       a = gisexactzero(gel(g,1)); if (!a) return NULL;
     247         616 :       b = gisexactzero(gel(g,2)); if (!b) return NULL;
     248           0 :       return ggcd(a,b);
     249       20608 :     case t_FFELT:
     250       20608 :       return FF_equal0(g)? g: NULL;
     251         518 :     case t_QUAD:
     252         518 :       a = gisexactzero(gel(g,2)); if (!a) return NULL;
     253          77 :       b = gisexactzero(gel(g,3)); if (!b) return NULL;
     254           7 :       return ggcd(a,b);
     255       17004 :     case t_POLMOD:
     256       17004 :       return gisexactzero(gel(g,2));
     257    28070039 :     case t_POL:
     258    28070039 :       lx = lg(g); /* cater for Mod(0,2)*x^0 */
     259    28070039 :       if (lx == 2) return gen_0;
     260    22748693 :       if (lx == 3) return gisexactzero(gel(g,2));
     261    19027341 :       return NULL;
     262     1190027 :     case t_RFRAC:
     263     1190027 :       return gisexactzero(gel(g,1)); /* may occur: Mod(0,2)/x */
     264           0 :     case t_VEC: case t_COL: case t_MAT:
     265           0 :       a = gen_0;
     266           0 :       for (i=lg(g)-1; i; i--)
     267             :       {
     268           0 :         b = gisexactzero(gel(g,i));
     269           0 :         if (!b) return NULL;
     270           0 :         a = ggcd(a, b);
     271             :       }
     272           0 :       return a;
     273             :   }
     274      586227 :   return NULL;
     275             : }
     276             : 
     277             : int
     278   547477370 : isrationalzero(GEN g)
     279             : {
     280             :   long i;
     281   547477370 :   switch (typ(g))
     282             :   {
     283   341117111 :     case t_INT:
     284   341117111 :       return !signe(g);
     285    39268372 :     case t_COMPLEX:
     286    39268372 :       return isintzero(gel(g,1)) && isintzero(gel(g,2));
     287        1428 :     case t_QUAD:
     288        1428 :       return isintzero(gel(g,2)) && isintzero(gel(g,3));
     289      491697 :     case t_POLMOD:
     290      491697 :       return isrationalzero(gel(g,2));
     291    22393593 :     case t_POL: return lg(g) == 2;
     292         133 :     case t_VEC: case t_COL: case t_MAT:
     293         448 :       for (i=lg(g)-1; i; i--)
     294         315 :         if (!isrationalzero(gel(g,i))) return 0;
     295         133 :       return 1;
     296             :   }
     297   144205036 :   return 0;
     298             : }
     299             : 
     300             : int
     301  2250449715 : gequal0(GEN x)
     302             : {
     303  2250449715 :   switch(typ(x))
     304             :   {
     305  2087069826 :     case t_INT: case t_REAL: case t_POL: case t_SER:
     306  2087069826 :       return !signe(x);
     307             : 
     308     7844630 :     case t_INTMOD:
     309     7844630 :       return !signe(gel(x,2));
     310             : 
     311      649358 :     case t_FFELT:
     312      649358 :       return FF_equal0(x);
     313             : 
     314   105019848 :     case t_COMPLEX:
     315             :      /* is 0 iff norm(x) would be 0 (can happen with Re(x) and Im(x) != 0
     316             :       * only if Re(x) and Im(x) are of type t_REAL). See mp.c:addrr().
     317             :       */
     318   105019848 :       if (gequal0(gel(x,1)))
     319             :       {
     320     8087049 :         if (gequal0(gel(x,2))) return 1;
     321     7706036 :         if (typ(gel(x,1))!=t_REAL || typ(gel(x,2))!=t_REAL) return 0;
     322      268446 :         return (expo(gel(x,1))>=expo(gel(x,2)));
     323             :       }
     324    96933005 :       if (gequal0(gel(x,2)))
     325             :       {
     326     1647442 :         if (typ(gel(x,1))!=t_REAL || typ(gel(x,2))!=t_REAL) return 0;
     327     1563492 :         return (expo(gel(x,2))>=expo(gel(x,1)));
     328             :       }
     329    95289037 :       return 0;
     330             : 
     331     2046360 :     case t_PADIC:
     332     2046360 :       return !signe(gel(x,4));
     333             : 
     334        1806 :     case t_QUAD:
     335        1806 :       return gequal0(gel(x,2)) && gequal0(gel(x,3));
     336             : 
     337     8474597 :     case t_POLMOD:
     338     8474597 :       return gequal0(gel(x,2));
     339             : 
     340     6103921 :     case t_RFRAC:
     341     6103921 :       return gequal0(gel(x,1));
     342             : 
     343     9907177 :     case t_VEC: case t_COL: case t_MAT:
     344             :     {
     345             :       long i;
     346    22822085 :       for (i=lg(x)-1; i; i--)
     347    19043030 :         if (!gequal0(gel(x,i))) return 0;
     348     3779055 :       return 1;
     349             :     }
     350             :   }
     351    23332192 :   return 0;
     352             : }
     353             : 
     354             : /* x a t_POL or t_SER, return 1 if test(coeff(X,d)) is true and
     355             :  * coeff(X,i) = 0 for all i != d. Return 0 (false) otherwise */
     356             : static int
     357    14684241 : is_monomial_test(GEN x, long d, int(*test)(GEN))
     358             : {
     359    14684241 :   long i, l = lg(x);
     360    14684241 :   if (typ(x) == t_SER)
     361             :   { /* "0" * x^v * (1+O(x)) ?  v <= 0 or null ring */
     362         602 :     if (l == 3 && isexactzero(gel(x,2))) return d >= 2 || test(gel(x,2));
     363         553 :     if (d < 2) return 0; /* v > 0 */
     364             :   }
     365    14684010 :   if (d >= l)
     366             :   {
     367       60079 :     if (typ(x) == t_POL) return 0; /* l = 2 */
     368             :     /* t_SER, v = 2-d <= 0 */
     369          56 :     if (!signe(x)) return 1;
     370             :   }
     371    14623931 :   else if (!test(gel(x,d))) return 0;
     372     7356739 :   for (i = 2; i < l; i++) /* 2 <= d < l */
     373     4976497 :     if (i != d && !gequal0(gel(x,i))) return 0;
     374     2380242 :   return 1;
     375             : }
     376             : static int
     377      292411 : col_test(GEN x, int(*test)(GEN))
     378             : {
     379      292411 :   long i, l = lg(x);
     380      292411 :   if (l == 1 || !test(gel(x,1))) return 0;
     381          70 :   for (i = 2; i < l; i++)
     382          42 :     if (!gequal0(gel(x,i))) return 0;
     383          28 :   return 1;
     384             : }
     385             : static int
     386       16268 : mat_test(GEN x, int(*test)(GEN))
     387             : {
     388       16268 :   long i, j, l = lg(x);
     389       16268 :   if (l == 1) return 1;
     390       16254 :   if (l != lgcols(x)) return 0;
     391       51569 :   for (i = 1; i < l; i++)
     392      135142 :     for (j = 1; j < l; j++)
     393       99827 :       if (i == j) {
     394       35378 :         if (!test(gcoeff(x,i,i))) return 0;
     395             :       } else {
     396       64449 :         if (!gequal0(gcoeff(x,i,j))) return 0;
     397             :       }
     398       16191 :   return 1;
     399             : }
     400             : 
     401             : /* returns 1 whenever x = 1, and 0 otherwise */
     402             : int
     403   312962655 : gequal1(GEN x)
     404             : {
     405   312962655 :   switch(typ(x))
     406             :   {
     407   293960078 :     case t_INT:
     408   293960078 :       return equali1(x);
     409             : 
     410       68558 :     case t_REAL:
     411             :     {
     412       68558 :       long s = signe(x);
     413       68558 :       if (!s) return expo(x) >= 0;
     414       68460 :       return s > 0 ? absrnz_equal1(x): 0;
     415             :     }
     416      632413 :     case t_INTMOD:
     417      632413 :       return is_pm1(gel(x,2)) || is_pm1(gel(x,1));
     418      393540 :     case t_POLMOD:
     419      393540 :       return !degpol(gel(x,1)) || gequal1(gel(x,2));
     420             : 
     421       16891 :     case t_FFELT:
     422       16891 :       return FF_equal1(x);
     423             : 
     424     1682390 :     case t_FRAC:
     425     1682390 :       return 0;
     426             : 
     427       21488 :     case t_COMPLEX:
     428       21488 :       return gequal1(gel(x,1)) && gequal0(gel(x,2));
     429             : 
     430      166225 :     case t_PADIC:
     431      166225 :       if (!signe(gel(x,4))) return valp(x) <= 0;
     432      166183 :       return valp(x) == 0 && gequal1(gel(x,4));
     433             : 
     434          42 :     case t_QUAD:
     435          42 :       return gequal1(gel(x,2)) && gequal0(gel(x,3));
     436             : 
     437    14683569 :     case t_POL: return is_monomial_test(x, 2, &gequal1);
     438         476 :     case t_SER: return is_monomial_test(x, 2 - valser(x), &gequal1);
     439             : 
     440     1028389 :     case t_RFRAC: return gequal(gel(x,1), gel(x,2));
     441      292362 :     case t_COL: return col_test(x, &gequal1);
     442       16156 :     case t_MAT: return mat_test(x, &gequal1);
     443             :   }
     444          78 :   return 0;
     445             : }
     446             : 
     447             : /* returns 1 whenever the x = -1, 0 otherwise */
     448             : int
     449    74232864 : gequalm1(GEN x)
     450             : {
     451             :   pari_sp av;
     452             :   GEN t;
     453             : 
     454    74232864 :   switch(typ(x))
     455             :   {
     456    74224027 :     case t_INT:
     457    74224027 :       return equalim1(x);
     458             : 
     459        1484 :     case t_REAL:
     460             :     {
     461        1484 :       long s = signe(x);
     462        1484 :       if (!s) return expo(x) >= 0;
     463        1477 :       return s < 0 ? absrnz_equal1(x): 0;
     464             :     }
     465        4602 :     case t_INTMOD:
     466        4602 :       av = avma; return gc_bool(av, equalii(addui(1,gel(x,2)), gel(x,1)));
     467             : 
     468         154 :     case t_FRAC:
     469         154 :       return 0;
     470             : 
     471          42 :     case t_FFELT:
     472          42 :       return FF_equalm1(x);
     473             : 
     474        2044 :     case t_COMPLEX:
     475        2044 :       return gequalm1(gel(x,1)) && gequal0(gel(x,2));
     476             : 
     477           7 :     case t_QUAD:
     478           7 :       return gequalm1(gel(x,2)) && gequal0(gel(x,3));
     479             : 
     480          49 :     case t_PADIC:
     481          49 :       t = gel(x,4); if (!signe(t)) return valp(x) <= 0;
     482          21 :       av = avma; return gc_bool(av, !valp(x) && equalii(addui(1,t), gel(x,3)));
     483             : 
     484          56 :     case t_POLMOD:
     485          56 :       return !degpol(gel(x,1)) || gequalm1(gel(x,2));
     486             : 
     487          70 :     case t_POL: return is_monomial_test(x, 2, &gequalm1);
     488         126 :     case t_SER: return is_monomial_test(x, 2 - valser(x), &gequalm1);
     489             : 
     490          28 :     case t_RFRAC:
     491          28 :       av = avma; return gc_bool(av, gmequal_try(gel(x,1), gel(x,2)));
     492          49 :     case t_COL: return col_test(x, &gequalm1);
     493         112 :     case t_MAT: return mat_test(x, &gequalm1);
     494             :   }
     495          14 :   return 0;
     496             : }
     497             : 
     498             : int
     499     1469514 : gequalX(GEN x) { return typ(x) == t_POL && lg(x) == 4
     500     2953836 :                       && isintzero(gel(x,2)) && isint1(gel(x,3)); }
     501             : 
     502             : static int
     503         672 : cmp_str(const char *x, const char *y)
     504             : {
     505         672 :   int f = strcmp(x, y);
     506             :   return f > 0? 1
     507         672 :               : f? -1: 0;
     508             : }
     509             : 
     510             : static int
     511    39093928 : cmp_universal_rec(GEN x, GEN y, long i0)
     512             : {
     513    39093928 :   long i, lx = lg(x), ly = lg(y);
     514    39093928 :   if (lx < ly) return -1;
     515    39091153 :   if (lx > ly) return 1;
     516    68764521 :   for (i = i0; i < lx; i++)
     517             :   {
     518    59875256 :     int f = cmp_universal(gel(x,i), gel(y,i));
     519    59875256 :     if (f) return f;
     520             :   }
     521     8889265 :   return 0;
     522             : }
     523             : /* Universal "meaningless" comparison function. Transitive, returns 0 iff
     524             :  * gidentical(x,y) */
     525             : int
     526    84343355 : cmp_universal(GEN x, GEN y)
     527             : {
     528    84343355 :   long lx, ly, i, tx = typ(x), ty = typ(y);
     529             : 
     530    84343355 :   if (tx < ty) return -1;
     531    83983252 :   if (ty < tx) return 1;
     532    83456891 :   switch(tx)
     533             :   {
     534    43427251 :     case t_INT: return cmpii(x,y);
     535         651 :     case t_STR: return cmp_str(GSTR(x),GSTR(y));
     536      934976 :     case t_REAL:
     537             :     case t_VECSMALL:
     538      934976 :       lx = lg(x);
     539      934976 :       ly = lg(y);
     540      934976 :       if (lx < ly) return -1;
     541      886704 :       if (lx > ly) return 1;
     542     3586363 :       for (i = 1; i < lx; i++)
     543             :       {
     544     3478731 :         if (x[i] < y[i]) return -1;
     545     3109810 :         if (x[i] > y[i]) return 1;
     546             :       }
     547      107632 :       return 0;
     548             : 
     549      771626 :     case t_POL:
     550             :     {
     551      771626 :       long X = x[1] & (VARNBITS|SIGNBITS);
     552      771626 :       long Y = y[1] & (VARNBITS|SIGNBITS);
     553      771626 :       if (X < Y) return -1;
     554      771605 :       if (X > Y) return 1;
     555      771549 :       return cmp_universal_rec(x, y, 2);
     556             :     }
     557      881076 :     case t_SER:
     558             :     case t_FFELT:
     559             :     case t_CLOSURE:
     560      881076 :       if (x[1] < y[1]) return -1;
     561      881069 :       if (x[1] > y[1]) return 1;
     562      881062 :       return cmp_universal_rec(x, y, 2);
     563             : 
     564          35 :     case t_LIST:
     565             :       {
     566          35 :         long tx = list_typ(x), ty = list_typ(y);
     567             :         GEN vx, vy;
     568             :         pari_sp av;
     569          35 :         if (tx < ty) return -1;
     570          35 :         if (tx > ty) return 1;
     571          35 :         vx = list_data(x);
     572          35 :         vy = list_data(y);
     573          35 :         if (!vx) return vy? -1: 0;
     574          35 :         if (!vy) return 1;
     575          35 :         av = avma;
     576          35 :         if (tx == t_LIST_MAP)
     577             :         {
     578          14 :           vx = maptomat_shallow(x);
     579          14 :           vy = maptomat_shallow(y);
     580             :         }
     581          35 :         return gc_int(av, cmp_universal_rec(vx, vy, 1));
     582             :       }
     583    37441276 :     default:
     584    37441276 :       return cmp_universal_rec(x, y, lontyp[tx]);
     585             :   }
     586             : }
     587             : 
     588             : static int
     589     4588483 : cmpfrac(GEN x, GEN y)
     590             : {
     591     4588483 :   pari_sp av = avma;
     592     4588483 :   GEN a = gel(x,1), b = gel(x,2);
     593     4588483 :   GEN c = gel(y,1), d = gel(y,2);
     594     4588483 :   return gc_bool(av, cmpii(mulii(a, d), mulii(b, c)));
     595             : }
     596             : static int
     597      455541 : cmpifrac(GEN a, GEN y)
     598             : {
     599      455541 :   pari_sp av = avma;
     600      455541 :   GEN c = gel(y,1), d = gel(y,2);
     601      455541 :   return gc_int(av, cmpii(mulii(a, d), c));
     602             : }
     603             : static int
     604       81133 : cmprfrac(GEN a, GEN y)
     605             : {
     606       81133 :   pari_sp av = avma;
     607       81133 :   GEN c = gel(y,1), d = gel(y,2);
     608       81133 :   return gc_int(av, cmpri(mulri(a, d), c));
     609             : }
     610             : static int
     611         161 : cmpgen(GEN x, GEN y)
     612             : {
     613         161 :   pari_sp av = avma;
     614         161 :   return gc_int(av, gsigne(gsub(x,y)));
     615             : }
     616             : 
     617             : /* returns the sign of x - y when it makes sense. 0 otherwise */
     618             : int
     619   289202882 : gcmp(GEN x, GEN y)
     620             : {
     621   289202882 :   long tx = typ(x), ty = typ(y);
     622             : 
     623   289202882 :   if (tx == ty) /* generic case */
     624   280486895 :     switch(tx)
     625             :     {
     626   153291166 :       case t_INT:  return cmpii(x, y);
     627   122520508 :       case t_REAL: return cmprr(x, y);
     628     4588483 :       case t_FRAC: return cmpfrac(x, y);
     629          70 :       case t_QUAD: return cmpgen(x, y);
     630          21 :       case t_STR:  return cmp_str(GSTR(x), GSTR(y));
     631      101768 :       case t_INFINITY:
     632             :       {
     633      101768 :         long sx = inf_get_sign(x), sy = inf_get_sign(y);
     634      101769 :         if (sx < sy) return -1;
     635          42 :         if (sx > sy) return 1;
     636          14 :         return 0;
     637             :       }
     638             :     }
     639     8700866 :   if (ty == t_INFINITY) return -inf_get_sign(y);
     640     8628077 :   switch(tx)
     641             :   {
     642     8046616 :     case t_INT:
     643             :       switch(ty)
     644             :       {
     645     7733848 :         case t_REAL: return cmpir(x, y);
     646      312754 :         case t_FRAC: return cmpifrac(x, y);
     647           7 :         case t_QUAD: return cmpgen(x, y);
     648             :       }
     649           7 :       break;
     650      379099 :     case t_REAL:
     651             :       switch(ty)
     652             :       {
     653      342245 :         case t_INT:  return cmpri(x, y);
     654       36833 :         case t_FRAC: return cmprfrac(x, y);
     655          14 :         case t_QUAD: return cmpgen(x, y);
     656             :       }
     657           7 :       break;
     658      187101 :     case t_FRAC:
     659             :       switch(ty)
     660             :       {
     661      142787 :         case t_INT:  return -cmpifrac(y, x);
     662       44300 :         case t_REAL: return -cmprfrac(y, x);
     663           7 :         case t_QUAD: return cmpgen(x, y);
     664             :       }
     665           7 :       break;
     666          63 :     case t_QUAD:
     667          63 :       return cmpgen(x, y);
     668       31653 :     case t_INFINITY: return inf_get_sign(x);
     669             :   }
     670          24 :   pari_err_TYPE2("comparison",x,y);
     671             :   return 0;/*LCOV_EXCL_LINE*/
     672             : }
     673             : 
     674             : int
     675      616386 : gcmpsg(long s, GEN y)
     676             : {
     677      616386 :   switch(typ(y))
     678             :   {
     679       12208 :     case t_INT:  return cmpsi(s,y);
     680      599005 :     case t_REAL: return cmpsr(s,y);
     681        5173 :     case t_FRAC: {
     682        5173 :       pari_sp av = avma;
     683        5173 :       return gc_int(av, cmpii(mulsi(s,gel(y,2)), gel(y,1)));
     684             :     }
     685           0 :     case t_QUAD: {
     686           0 :       pari_sp av = avma;
     687           0 :       return gc_int(av, gsigne(gsubsg(s, y)));
     688             :     }
     689           0 :     case t_INFINITY: return -inf_get_sign(y);
     690             :   }
     691           0 :   pari_err_TYPE2("comparison",stoi(s),y);
     692             :   return 0; /* LCOV_EXCL_LINE */
     693             : }
     694             : 
     695             : static long
     696     3232603 : roughtype(GEN x)
     697             : {
     698     3232603 :   switch(typ(x))
     699             :   {
     700        2114 :     case t_MAT: return t_MAT;
     701      742370 :     case t_VEC: case t_COL: return t_VEC;
     702     1613554 :     case t_VECSMALL: return t_VECSMALL;
     703      874565 :     default: return t_INT;
     704             :   }
     705             : }
     706             : 
     707             : static int lexcmpsg(long x, GEN y);
     708          42 : static int lexcmpgs(GEN x, long y) { return -lexcmpsg(y,x); }
     709             : /* lexcmp(stoi(x),y), y t_VEC/t_COL/t_MAT */
     710             : static int
     711          21 : lexcmp_s_matvec(long x, GEN y)
     712             : {
     713             :   int fl;
     714          21 :   if (lg(y)==1) return 1;
     715          14 :   fl = lexcmpsg(x,gel(y,1));
     716          14 :   if (fl) return fl;
     717           7 :   return -1;
     718             : }
     719             : /* x a scalar, y a t_VEC/t_COL/t_MAT */
     720             : static int
     721         357 : lexcmp_scal_matvec(GEN x, GEN y)
     722             : {
     723             :   int fl;
     724         357 :   if (lg(y)==1) return 1;
     725         357 :   fl = lexcmp(x,gel(y,1));
     726         357 :   if (fl) return fl;
     727           7 :   return -1;
     728             : }
     729             : /* x a scalar, y a t_VECSMALL */
     730             : static int
     731          42 : lexcmp_scal_vecsmall(GEN x, GEN y)
     732             : {
     733             :   int fl;
     734          42 :   if (lg(y)==1) return 1;
     735          42 :   fl = lexcmpgs(x, y[1]);
     736          42 :   if (fl) return fl;
     737           0 :   return -1;
     738             : }
     739             : 
     740             : /* tx = ty = t_MAT, or x and y are both vect_t */
     741             : static int
     742      371977 : lexcmp_similar(GEN x, GEN y)
     743             : {
     744      371977 :   long i, lx = lg(x), ly = lg(y), l = minss(lx,ly);
     745      456831 :   for (i=1; i<l; i++)
     746             :   {
     747      425205 :     int fl = lexcmp(gel(x,i),gel(y,i));
     748      425205 :     if (fl) return fl;
     749             :   }
     750       31626 :   if (lx == ly) return 0;
     751          35 :   return (lx < ly)? -1 : 1;
     752             : }
     753             : /* x a t_VECSMALL, y a t_VEC/t_COL ~ lexcmp_similar */
     754             : static int
     755         154 : lexcmp_vecsmall_vec(GEN x, GEN y)
     756             : {
     757         154 :   long i, lx = lg(x), ly = lg(y), l = minss(lx,ly);
     758         343 :   for (i=1; i<l; i++)
     759             :   {
     760         287 :     int fl = lexcmpsg(x[i], gel(y,i));
     761         287 :     if (fl) return fl;
     762             :   }
     763          56 :   if (lx == ly) return 0;
     764          21 :   return (lx < ly)? -1 : 1;
     765             : }
     766             : 
     767             : /* x t_VEC/t_COL, y t_MAT */
     768             : static int
     769          98 : lexcmp_vec_mat(GEN x, GEN y)
     770             : {
     771             :   int fl;
     772          98 :   if (lg(x)==1) return -1;
     773          98 :   if (lg(y)==1) return 1;
     774          98 :   fl = lexcmp_similar(x,gel(y,1));
     775          98 :   if (fl) return fl;
     776           7 :   return -1;
     777             : }
     778             : /* x t_VECSMALl, y t_MAT ~ lexcmp_vec_mat */
     779             : static int
     780          42 : lexcmp_vecsmall_mat(GEN x, GEN y)
     781             : {
     782             :   int fl;
     783          42 :   if (lg(x)==1) return -1;
     784          42 :   if (lg(y)==1) return 1;
     785          42 :   fl = lexcmp_vecsmall_vec(x, gel(y,1));
     786          42 :   if (fl) return fl;
     787           0 :   return -1;
     788             : }
     789             : 
     790             : /* x a t_VECSMALL, not y */
     791             : static int
     792         196 : lexcmp_vecsmall_other(GEN x, GEN y, long ty)
     793             : {
     794         196 :   switch(ty)
     795             :   {
     796          42 :     case t_MAT: return lexcmp_vecsmall_mat(x, y);
     797         112 :     case t_VEC: return lexcmp_vecsmall_vec(x, y);
     798          42 :     default: return -lexcmp_scal_vecsmall(y, x); /*y scalar*/
     799             :   }
     800             : }
     801             : 
     802             : /* lexcmp(stoi(s), y) */
     803             : static int
     804         343 : lexcmpsg(long x, GEN y)
     805             : {
     806         343 :   switch(roughtype(y))
     807             :   {
     808          21 :     case t_MAT:
     809             :     case t_VEC:
     810          21 :       return lexcmp_s_matvec(x,y);
     811          14 :     case t_VECSMALL: /* ~ lexcmp_scal_matvec */
     812          14 :       if (lg(y)==1) return 1;
     813           7 :       return (x > y[1])? 1: -1;
     814         308 :     default: return gcmpsg(x,y);
     815             :   }
     816             : }
     817             : 
     818             : /* as gcmp for vector/matrices, using lexicographic ordering on components */
     819             : static int
     820     1616130 : lexcmp_i(GEN x, GEN y)
     821             : {
     822     1616130 :   const long tx = roughtype(x), ty = roughtype(y);
     823     1616133 :   if (tx == ty)
     824     1615482 :     switch(tx)
     825             :     {
     826      371879 :       case t_MAT:
     827      371879 :       case t_VEC: return lexcmp_similar(x,y);
     828      806672 :       case t_VECSMALL: return vecsmall_lexcmp(x,y);
     829      436931 :       default: return gcmp(x,y);
     830             :     }
     831         651 :   if (tx == t_VECSMALL) return  lexcmp_vecsmall_other(x,y,ty);
     832         518 :   if (ty == t_VECSMALL) return -lexcmp_vecsmall_other(y,x,tx);
     833             : 
     834         455 :   if (tx == t_INT) return  lexcmp_scal_matvec(x,y); /*scalar*/
     835         203 :   if (ty == t_INT) return -lexcmp_scal_matvec(y,x);
     836             : 
     837          98 :   if (ty==t_MAT) return  lexcmp_vec_mat(x,y);
     838          42 :   return -lexcmp_vec_mat(y,x); /*tx==t_MAT*/
     839             : }
     840             : int
     841     1616130 : lexcmp(GEN x, GEN y)
     842             : {
     843     1616130 :   pari_sp av = avma;
     844     1616130 :   if (typ(x) == t_COMPLEX)
     845             :   {
     846         875 :     x = mkvec2(gel(x,1), gel(x,2));
     847         875 :     if (typ(y) == t_COMPLEX) y = mkvec2(gel(y,1), gel(y,2));
     848          49 :     else y = mkvec2(y, gen_0);
     849             :   }
     850     1615255 :   else if (typ(y) == t_COMPLEX)
     851             :   {
     852          63 :     x = mkvec2(x, gen_0);
     853          63 :     y = mkvec2(gel(y,1), gel(y,2));
     854             :   }
     855     1616130 :   return gc_int(av, lexcmp_i(x, y));
     856             : }
     857             : 
     858             : /*****************************************************************/
     859             : /*                                                               */
     860             : /*                          EQUALITY                             */
     861             : /*                returns 1 if x == y, 0 otherwise               */
     862             : /*                                                               */
     863             : /*****************************************************************/
     864             : /* x,y t_POL */
     865             : static int
     866     3432196 : polidentical(GEN x, GEN y)
     867             : {
     868             :   long lx;
     869     3432196 :   if (x[1] != y[1]) return 0;
     870     3432098 :   lx = lg(x); if (lg(y) != lg(x)) return 0;
     871    14948834 :   for (lx--; lx >= 2; lx--) if (!gidentical(gel(x,lx), gel(y,lx))) return 0;
     872     3432007 :   return 1;
     873             : }
     874             : /* x,y t_SER */
     875             : static int
     876          14 : seridentical(GEN x, GEN y) { return polidentical(x,y); }
     877             : /* typ(x) = typ(y) = t_VEC/COL/MAT */
     878             : static int
     879     5249391 : vecidentical(GEN x, GEN y)
     880             : {
     881             :   long i;
     882     5249391 :   if ((x[0] ^ y[0]) & (TYPBITS|LGBITS)) return 0;
     883    16801694 :   for (i = lg(x)-1; i; i--)
     884    12831420 :     if (! gidentical(gel(x,i),gel(y,i)) ) return 0;
     885     3970274 :   return 1;
     886             : }
     887             : static int
     888        1547 : identicalrr(GEN x, GEN y)
     889             : {
     890        1547 :   long i, lx = lg(x);
     891        1547 :   if (lg(y) != lx) return 0;
     892        1547 :   if (x[1] != y[1]) return 0;
     893        5465 :   i=2; while (i<lx && x[i]==y[i]) i++;
     894        1540 :   return (i == lx);
     895             : }
     896             : 
     897             : static int
     898          70 : closure_identical(GEN x, GEN y)
     899             : {
     900          70 :   if (lg(x)!=lg(y) || x[1]!=y[1]) return 0;
     901          56 :   if (!gidentical(gel(x,2),gel(y,2)) || !gidentical(gel(x,3),gel(y,3))
     902          56 :    || !gidentical(gel(x,4),gel(y,4))) return 0;
     903          42 :   if (lg(x)<8) return 1;
     904           0 :   return gidentical(gel(x,7),gel(y,7));
     905             : }
     906             : 
     907             : static int
     908         343 : list_cmp(GEN x, GEN y, int cmp(GEN x, GEN y))
     909             : {
     910         343 :   int t = list_typ(x);
     911             :   GEN vx, vy;
     912             :   long lvx, lvy;
     913         343 :   if (list_typ(y)!=t) return 0;
     914         343 :   vx = list_data(x);
     915         343 :   vy = list_data(y);
     916         343 :   lvx = vx ? lg(vx): 1;
     917         343 :   lvy = vy ? lg(vy): 1;
     918         343 :   if (lvx==1 && lvy==1) return 1;
     919         329 :   if (lvx != lvy) return 0;
     920         301 :   switch (t)
     921             :   {
     922         280 :   case t_LIST_MAP:
     923             :     {
     924         280 :       pari_sp av = avma;
     925         280 :       GEN mx  = maptomat_shallow(x), my = maptomat_shallow(y);
     926         280 :       int ret = gidentical(gel(mx, 1), gel(my, 1)) && cmp(gel(mx, 2), gel(my, 2));
     927         280 :       return gc_bool(av, ret);
     928             :     }
     929          21 :   default:
     930          21 :     return cmp(vx, vy);
     931             :   }
     932             : }
     933             : 
     934             : int
     935    61987935 : gidentical(GEN x, GEN y)
     936             : {
     937             :   long tx;
     938             : 
     939    61987935 :   if (x == y) return 1;
     940    58284070 :   tx = typ(x); if (typ(y) != tx) return 0;
     941    58051733 :   switch(tx)
     942             :   {
     943    19066375 :     case t_INT:
     944    19066375 :       return equalii(x,y);
     945             : 
     946        1547 :     case t_REAL:
     947        1547 :       return identicalrr(x,y);
     948             : 
     949      794008 :     case t_FRAC: case t_INTMOD:
     950      794008 :       return equalii(gel(x,2), gel(y,2)) && equalii(gel(x,1), gel(y,1));
     951             : 
     952         343 :     case t_COMPLEX:
     953         343 :       return gidentical(gel(x,2),gel(y,2)) && gidentical(gel(x,1),gel(y,1));
     954          14 :     case t_PADIC:
     955          14 :       return valp(x) == valp(y)
     956          14 :         && equalii(gel(x,2),gel(y,2))
     957          14 :         && equalii(gel(x,3),gel(y,3))
     958          28 :         && equalii(gel(x,4),gel(y,4));
     959        3843 :     case t_POLMOD:
     960        3843 :       return gidentical(gel(x,2),gel(y,2)) && polidentical(gel(x,1),gel(y,1));
     961     3432161 :     case t_POL:
     962     3432161 :       return polidentical(x,y);
     963          14 :     case t_SER:
     964          14 :       return seridentical(x,y);
     965        3024 :     case t_FFELT:
     966        3024 :       return FF_equal(x,y);
     967             : 
     968      401624 :     case t_QFB:
     969      401624 :       return equalii(gel(x,1),gel(y,1))
     970      401617 :           && equalii(gel(x,2),gel(y,2))
     971      803241 :           && equalii(gel(x,3),gel(y,3));
     972             : 
     973          14 :     case t_QUAD:
     974          14 :       return ZX_equal(gel(x,1),gel(y,1))
     975           7 :           && gidentical(gel(x,2),gel(y,2))
     976          21 :           && gidentical(gel(x,3),gel(y,3));
     977             : 
     978           7 :     case t_RFRAC:
     979           7 :       return gidentical(gel(x,1),gel(y,1)) && gidentical(gel(x,2),gel(y,2));
     980             : 
     981          70 :     case t_STR:
     982          70 :       return !strcmp(GSTR(x),GSTR(y));
     983     5249391 :     case t_VEC: case t_COL: case t_MAT:
     984     5249391 :       return vecidentical(x,y);
     985    29099088 :     case t_VECSMALL:
     986    29099088 :       return zv_equal(x,y);
     987          28 :     case t_CLOSURE:
     988          28 :       return closure_identical(x,y);
     989         161 :     case t_LIST:
     990         161 :       return list_cmp(x, y, gidentical);
     991          21 :     case t_INFINITY: return gidentical(gel(x,1),gel(y,1));
     992             :   }
     993           0 :   return 0;
     994             : }
     995             : /* x,y t_POL in the same variable */
     996             : static int
     997     7446898 : polequal(GEN x, GEN y)
     998             : {
     999             :   long lx, ly;
    1000             :   /* Can't do that: Mod(0,1)*x^0 == x^0
    1001             :   if (signe(x) != signe(y)) return 0; */
    1002     7446898 :   lx = lg(x); ly = lg(y);
    1003     7446898 :   while (lx > ly) if (!gequal0(gel(x,--lx))) return 0;
    1004     7443349 :   while (ly > lx) if (!gequal0(gel(y,--ly))) return 0;
    1005    29586253 :   for (lx--; lx >= 2; lx--) if (!gequal(gel(x,lx), gel(y,lx))) return 0;
    1006     7371334 :   return 1;
    1007             : }
    1008             : 
    1009             : /* x,y t_SER in the same variable */
    1010             : static int
    1011         420 : serequal(GEN x, GEN y)
    1012             : {
    1013             :   long LX, LY, lx, ly, vx, vy;
    1014         420 :   if (!signe(x) && !signe(y)) return 1;
    1015          56 :   lx = lg(x); vx = valser(x); LX = lx + vx;
    1016          56 :   ly = lg(y); vy = valser(y); LY = ly + vy;
    1017          56 :   if (LX > LY) lx = LY - vx; else ly = LX - vy;
    1018      282877 :   while (lx >= 3 && ly >= 3)
    1019      282821 :     if (!gequal(gel(x,--lx), gel(y,--ly))) return 0;
    1020          56 :   while(--ly >= 2) if (!gequal0(gel(y,ly))) return 0;
    1021          84 :   while(--lx >= 2) if (!gequal0(gel(x,lx))) return 0;
    1022          49 :   return 1;
    1023             : }
    1024             : 
    1025             : /* typ(x) = typ(y) = t_VEC/COL/MAT */
    1026             : static int
    1027     5625496 : vecequal(GEN x, GEN y)
    1028             : {
    1029             :   long i;
    1030     5625496 :   if ((x[0] ^ y[0]) & (TYPBITS|LGBITS)) return 0;
    1031    18529867 :   for (i = lg(x)-1; i; i--)
    1032    16149283 :     if (! gequal(gel(x,i),gel(y,i)) ) return 0;
    1033     2380584 :   return 1;
    1034             : }
    1035             : 
    1036             : int
    1037   232594514 : gequal(GEN x, GEN y)
    1038             : {
    1039             :   pari_sp av;
    1040             :   long tx, ty;
    1041             :   long i;
    1042             : 
    1043   232594514 :   if (x == y) return 1;
    1044   203005980 :   tx = typ(x);
    1045   203005980 :   ty = typ(y);
    1046   203005980 :   if (tx == ty)
    1047   195211437 :     switch(tx)
    1048             :     {
    1049   169351931 :       case t_INT:
    1050   169351931 :         return equalii(x,y);
    1051             : 
    1052       20327 :       case t_REAL:
    1053       20327 :         return equalrr(x,y);
    1054             : 
    1055     6838731 :       case t_FRAC: case t_INTMOD:
    1056     6838731 :         return equalii(gel(x,2), gel(y,2)) && equalii(gel(x,1), gel(y,1));
    1057             : 
    1058        1288 :       case t_COMPLEX:
    1059        1288 :         return gequal(gel(x,2),gel(y,2)) && gequal(gel(x,1),gel(y,1));
    1060         763 :       case t_PADIC:
    1061         763 :         if (!equalii(gel(x,2),gel(y,2))) return 0;
    1062         763 :         av = avma; i = gequal0(gsub(x,y)); set_avma(av);
    1063         763 :         return i;
    1064     3209303 :       case t_POLMOD:
    1065     3209303 :         if (varn(gel(x,1)) != varn(gel(y,1))) break;
    1066     3209296 :         return gequal(gel(x,2),gel(y,2)) && RgX_equal_var(gel(x,1),gel(y,1));
    1067     7455390 :       case t_POL:
    1068     7455390 :         if (varn(x) != varn(y)) break;
    1069     7446899 :         return polequal(x,y);
    1070         420 :       case t_SER:
    1071         420 :         if (varn(x) != varn(y)) break;
    1072         420 :         return serequal(x,y);
    1073             : 
    1074       56098 :       case t_FFELT:
    1075       56098 :         return FF_equal(x,y);
    1076             : 
    1077     1097034 :       case t_QFB:
    1078     1097034 :         return equalii(gel(x,1),gel(y,1))
    1079      247773 :             && equalii(gel(x,2),gel(y,2))
    1080     1344807 :             && equalii(gel(x,3),gel(y,3));
    1081             : 
    1082           7 :       case t_QUAD:
    1083           7 :         return ZX_equal(gel(x,1),gel(y,1))
    1084           0 :             && gequal(gel(x,2),gel(y,2))
    1085           7 :             && gequal(gel(x,3),gel(y,3));
    1086             : 
    1087       73717 :       case t_RFRAC:
    1088             :       {
    1089       73717 :         GEN a = gel(x,1), b = gel(x,2), c = gel(y,1), d = gel(y,2);
    1090       73717 :         if (gequal(b,d)) return gequal(a,c); /* simple case */
    1091           0 :         av = avma;
    1092           0 :         a = simplify_shallow(gmul(a,d));
    1093           0 :         b = simplify_shallow(gmul(b,c));
    1094           0 :         return gc_bool(av, gequal(a,b));
    1095             :       }
    1096             : 
    1097       64925 :       case t_STR:
    1098       64925 :         return !strcmp(GSTR(x),GSTR(y));
    1099     5625496 :       case t_VEC: case t_COL: case t_MAT:
    1100     5625496 :         return vecequal(x,y);
    1101     1415775 :       case t_VECSMALL:
    1102     1415775 :         return zv_equal(x,y);
    1103         182 :       case t_LIST:
    1104         182 :         return list_cmp(x, y, gequal);
    1105          42 :       case t_CLOSURE:
    1106          42 :         return closure_identical(x,y);
    1107          28 :       case t_INFINITY:
    1108          28 :         return gequal(gel(x,1),gel(y,1));
    1109             :     }
    1110     7803021 :   if (is_noncalc_t(tx) || is_noncalc_t(ty)) return 0;
    1111     7803073 :   if (tx == t_INT && !signe(x)) return gequal0(y);
    1112     7799839 :   if (ty == t_INT && !signe(y)) return gequal0(x);
    1113     3196114 :   (void)&av; av = avma; /* emulate volatile */
    1114     3196114 :   return gc_bool(av, gequal_try(x, y));
    1115             : }
    1116             : 
    1117             : int
    1118       43988 : gequalsg(long s, GEN x)
    1119       43988 : { pari_sp av = avma; return gc_bool(av, gequal(stoi(s), x)); }
    1120             : 
    1121             : /* a and b are t_INT, t_FRAC, t_REAL or t_COMPLEX of those. Check whether
    1122             :  * a-b is invertible */
    1123             : int
    1124       53397 : cx_approx_equal(GEN a, GEN b)
    1125             : {
    1126       53397 :   pari_sp av = avma;
    1127             :   GEN d;
    1128       53397 :   if (a == b) return 1;
    1129       24486 :   d = gsub(a,b);
    1130       24486 :   return gc_bool(av, gequal0(d) || (typ(d)==t_COMPLEX && gequal0(cxnorm(d))));
    1131             : }
    1132             : static int
    1133     1322077 : r_approx0(GEN x, long e) { return e - expo(x) > bit_prec(x); }
    1134             : /* x ~ 0 compared to reference y */
    1135             : int
    1136     1849462 : cx_approx0(GEN x, GEN y)
    1137             : {
    1138             :   GEN a, b;
    1139             :   long e;
    1140     1849462 :   switch(typ(x))
    1141             :   {
    1142         469 :     case t_COMPLEX:
    1143         469 :       a = gel(x,1); b = gel(x,2);
    1144         469 :       if (typ(a) != t_REAL)
    1145             :       {
    1146          14 :         if (!gequal0(a)) return 0;
    1147           0 :         a = NULL;
    1148             :       }
    1149         455 :       else if (!signe(a)) a = NULL;
    1150         455 :       if (typ(b) != t_REAL)
    1151             :       {
    1152           0 :         if (!gequal0(b)) return 0;
    1153           0 :         if (!a) return 1;
    1154           0 :         b = NULL;
    1155             :       }
    1156         455 :       else if (!signe(b))
    1157             :       {
    1158           7 :         if (!a) return 1;
    1159           7 :         b = NULL;
    1160             :       }
    1161             :       /* a or b is != NULL iff it is non-zero t_REAL; one of them is */
    1162         455 :       e = gexpo(y);
    1163         455 :       return (!a || r_approx0(a, e)) && (!b || r_approx0(b, e));
    1164     1321614 :     case t_REAL:
    1165     1321614 :       return !signe(x) || r_approx0(x, gexpo(y));
    1166      527379 :     default:
    1167      527379 :       return gequal0(x);
    1168             :   }
    1169             : }
    1170             : /*******************************************************************/
    1171             : /*                                                                 */
    1172             : /*                          VALUATION                              */
    1173             : /*             p is either a t_INT or a t_POL.                     */
    1174             : /*  returns the largest exponent of p dividing x when this makes   */
    1175             : /*  sense : error for types real, integermod and polymod if p does */
    1176             : /*  not divide the modulus, q-adic if q!=p.                        */
    1177             : /*                                                                 */
    1178             : /*******************************************************************/
    1179             : 
    1180             : static long
    1181         336 : minval(GEN x, GEN p)
    1182             : {
    1183         336 :   long i,k, val = LONG_MAX, lx = lg(x);
    1184        6538 :   for (i=lontyp[typ(x)]; i<lx; i++)
    1185             :   {
    1186        6202 :     k = gvaluation(gel(x,i),p);
    1187        6202 :     if (k < val) val = k;
    1188             :   }
    1189         336 :   return val;
    1190             : }
    1191             : 
    1192             : static int
    1193          91 : intdvd(GEN x, GEN y, GEN *z) { GEN r; *z = dvmdii(x,y,&r); return (r==gen_0); }
    1194             : 
    1195             : /* x t_FRAC, p t_INT, return v_p(x) */
    1196             : static long
    1197      292597 : frac_val(GEN x, GEN p) {
    1198      292597 :   long v = Z_pval(gel(x,2),p);
    1199      292597 :   if (v) return -v;
    1200      292454 :   return Z_pval(gel(x,1),p);
    1201             : }
    1202             : long
    1203     9292950 : Q_pval(GEN x, GEN p)
    1204             : {
    1205     9292950 :   if (lgefint(p) == 3) return Q_lval(x, uel(p,2));
    1206         565 :   return (typ(x)==t_INT)? Z_pval(x, p): frac_val(x, p);
    1207             : }
    1208             : 
    1209             : static long
    1210      390866 : frac_lval(GEN x, ulong p) {
    1211      390866 :   long v = Z_lval(gel(x,2),p);
    1212      390866 :   if (v) return -v;
    1213      221197 :   return Z_lval(gel(x,1),p);
    1214             : }
    1215             : long
    1216     9297133 : Q_lval(GEN x, ulong p){return (typ(x)==t_INT)? Z_lval(x, p): frac_lval(x, p);}
    1217             : 
    1218             : long
    1219     6270430 : Q_pvalrem(GEN x, GEN p, GEN *y)
    1220             : {
    1221             :   GEN a, b;
    1222             :   long v;
    1223     6270430 :   if (lgefint(p) == 3) return Q_lvalrem(x, uel(p,2), y);
    1224        5808 :   if (typ(x) == t_INT) return Z_pvalrem(x, p, y);
    1225           0 :   a = gel(x,1);
    1226           0 :   b = gel(x,2);
    1227           0 :   v = Z_pvalrem(b, p, &b);
    1228           0 :   if (v) { *y = isint1(b)? a: mkfrac(a, b); return -v; }
    1229           0 :   v = Z_pvalrem(a, p, &a);
    1230           0 :   *y = mkfrac(a, b); return v;
    1231             : }
    1232             : long
    1233     6268832 : Q_lvalrem(GEN x, ulong p, GEN *y)
    1234             : {
    1235             :   GEN a, b;
    1236             :   long v;
    1237     6268832 :   if (typ(x) == t_INT) return Z_lvalrem(x, p, y);
    1238      398334 :   a = gel(x,1);
    1239      398334 :   b = gel(x,2);
    1240      398334 :   v = Z_lvalrem(b, p, &b);
    1241      398336 :   if (v) { *y = isint1(b)? a: mkfrac(a, b); return -v; }
    1242      228910 :   v = Z_lvalrem(a, p, &a);
    1243      228910 :   *y = mkfrac(a, b); return v;
    1244             : }
    1245             : 
    1246             : long
    1247     1166387 : gvaluation(GEN x, GEN p)
    1248             : {
    1249     1166387 :   long tx = typ(x), tp;
    1250             :   pari_sp av;
    1251             : 
    1252     1166387 :   if (!p)
    1253          28 :     switch(tx)
    1254             :     {
    1255           7 :       case t_PADIC: return valp(x);
    1256           7 :       case t_POL: return RgX_val(x);
    1257           7 :       case t_SER: return valser(x);
    1258           7 :       default: pari_err_TYPE("gvaluation", x);
    1259             :     }
    1260     1166359 :   tp  = typ(p);
    1261     1166359 :   switch(tp)
    1262             :   {
    1263     1159359 :     case t_INT:
    1264     1159359 :       if (signe(p) && !is_pm1(p)) break;
    1265          28 :       pari_err_DOMAIN("gvaluation", "p", "=", p, p);
    1266        6993 :     case t_POL:
    1267        6993 :       if (degpol(p) > 0) break;
    1268             :     default:
    1269           7 :       pari_err_DOMAIN("gvaluation", "p", "=", p, p);
    1270             :   }
    1271             : 
    1272     1166324 :   switch(tx)
    1273             :   {
    1274      145061 :     case t_INT:
    1275      145061 :       if (!signe(x)) return LONG_MAX;
    1276      144956 :       if (tp == t_POL) return 0;
    1277      144634 :       return Z_pval(x,p);
    1278             : 
    1279          49 :     case t_REAL:
    1280          49 :       if (tp == t_POL) return 0;
    1281          21 :       break;
    1282             : 
    1283          28 :     case t_FFELT:
    1284          28 :       if (tp == t_POL) return FF_equal0(x)? LONG_MAX: 0;
    1285          14 :       break;
    1286             : 
    1287         105 :     case t_INTMOD: {
    1288         105 :       GEN a = gel(x,1), b = gel(x,2);
    1289             :       long val;
    1290         133 :       if (tp == t_POL) return signe(b)? 0: LONG_MAX;
    1291          42 :       av = avma;
    1292          42 :       if (!intdvd(a, p, &a)) break;
    1293          28 :       if (!intdvd(b, p, &b)) return gc_long(av,0);
    1294          14 :       val = 1; while (intdvd(a,p,&a) && intdvd(b,p,&b)) val++;
    1295          14 :       return gc_long(av,val);
    1296             :     }
    1297             : 
    1298      292509 :     case t_FRAC:
    1299      292509 :       if (tp == t_POL) return 0;
    1300      292495 :       return frac_val(x, p);
    1301             : 
    1302      721817 :     case t_PADIC:
    1303      721817 :       if (tp == t_POL) return 0;
    1304      721796 :       if (!equalii(p,gel(x,2))) break;
    1305      721789 :       return valp(x);
    1306             : 
    1307          35 :     case t_POLMOD: {
    1308          35 :       GEN a = gel(x,1), b = gel(x,2);
    1309             :       long v, val;
    1310          35 :       if (tp == t_INT) return gvaluation(b,p);
    1311          21 :       v = varn(p);
    1312          21 :       if (varn(a) != v) return 0;
    1313          21 :       av = avma;
    1314          21 :       a = RgX_divrem(a, p, ONLY_DIVIDES);
    1315          21 :       if (!a) break;
    1316          28 :       if (typ(b) != t_POL || varn(b) != v ||
    1317          21 :           !(b = RgX_divrem(b, p, ONLY_DIVIDES)) ) return gc_long(av,0);
    1318           7 :       val = 1;
    1319          28 :       while ((a = RgX_divrem(a, p, ONLY_DIVIDES)) &&
    1320          21 :              (b = RgX_divrem(b, p, ONLY_DIVIDES)) ) val++;
    1321           7 :       return gc_long(av,val);
    1322             :     }
    1323        6055 :     case t_POL: {
    1324        6055 :       if (tp == t_POL) {
    1325        5866 :         long vp = varn(p), vx = varn(x);
    1326        5866 :         if (vp == vx)
    1327             :         {
    1328             :           long val;
    1329        5852 :           if (RgX_is_monomial(p))
    1330             :           {
    1331        5817 :             val = RgX_val(x); if (val == LONG_MAX) return LONG_MAX;
    1332        5740 :             return val / degpol(p);
    1333             :           }
    1334          35 :           if (!signe(x)) return LONG_MAX;
    1335          21 :           av = avma;
    1336          21 :           for (val=0; ; val++)
    1337             :           {
    1338          35 :             x = RgX_divrem(x,p,ONLY_DIVIDES);
    1339          35 :             if (!x) return gc_long(av,val);
    1340          14 :             if (gc_needed(av,1))
    1341             :             {
    1342           0 :               if(DEBUGMEM>1) pari_warn(warnmem,"gvaluation");
    1343           0 :               x = gerepilecopy(av, x);
    1344             :             }
    1345             :           }
    1346             :         }
    1347          14 :         if (varncmp(vx, vp) > 0) return 0;
    1348             :       }
    1349         196 :       return minval(x,p);
    1350             :     }
    1351             : 
    1352         490 :     case t_SER: {
    1353         490 :       if (tp == t_POL) {
    1354         476 :         long vp = varn(p), vx = varn(x);
    1355         476 :         if (vp == vx)
    1356             :         {
    1357         469 :           long val = RgX_val(p);
    1358         469 :           if (!val) pari_err_DOMAIN("gvaluation", "p", "=", p, p);
    1359         462 :           return (long)(valser(x) / val);
    1360             :         }
    1361           7 :         if (varncmp(vx, vp) > 0) return 0;
    1362             :       }
    1363          14 :       return minval(x,p);
    1364             :     }
    1365             : 
    1366          49 :     case t_RFRAC:
    1367          49 :       return gvaluation(gel(x,1),p) - gvaluation(gel(x,2),p);
    1368             : 
    1369         126 :     case t_COMPLEX: case t_QUAD: case t_VEC: case t_COL: case t_MAT:
    1370         126 :       return minval(x,p);
    1371             :   }
    1372          63 :   pari_err_OP("valuation", x,p);
    1373             :   return 0; /* LCOV_EXCL_LINE */
    1374             : }
    1375             : GEN
    1376        3808 : gpvaluation(GEN x, GEN p)
    1377             : {
    1378        3808 :   long v = gvaluation(x,p);
    1379        3703 :   return v == LONG_MAX? mkoo(): stoi(v);
    1380             : }
    1381             : 
    1382             : /* x is nonzero */
    1383             : long
    1384    77933579 : u_lvalrem(ulong x, ulong p, ulong *py)
    1385             : {
    1386             :   ulong vx;
    1387    77933579 :   if (p == 2) { vx = vals(x); *py = x >> vx; return vx; }
    1388    67946530 :   for(vx = 0;;)
    1389             :   {
    1390   118790300 :     if (x % p) { *py = x; return vx; }
    1391    50843770 :     x /= p; /* gcc is smart enough to make a single div */
    1392    50843770 :     vx++;
    1393             :   }
    1394             : }
    1395             : long
    1396    65767367 : u_lval(ulong x, ulong p)
    1397             : {
    1398             :   ulong vx;
    1399    65767367 :   if (p == 2) return vals(x);
    1400    62484876 :   for(vx = 0;;)
    1401             :   {
    1402   101349358 :     if (x % p) return vx;
    1403    38864482 :     x /= p; /* gcc is smart enough to make a single div */
    1404    38864482 :     vx++;
    1405             :   }
    1406             : }
    1407             : 
    1408             : long
    1409     1822480 : z_lval(long s, ulong p) { return u_lval(labs(s), p); }
    1410             : long
    1411       87344 : z_lvalrem(long s, ulong p, long *py)
    1412             : {
    1413             :   long v;
    1414       87344 :   if (s < 0)
    1415             :   {
    1416           0 :     ulong u = (ulong)-s;
    1417           0 :     v = u_lvalrem(u, p, &u);
    1418           0 :     *py = -(long)u;
    1419             :   }
    1420             :   else
    1421             :   {
    1422       87344 :     ulong u = (ulong)s;
    1423       87344 :     v = u_lvalrem(u, p, &u);
    1424       87343 :     *py = (long)u;
    1425             :   }
    1426       87343 :   return v;
    1427             : }
    1428             : /* assume |p| > 1 */
    1429             : long
    1430     1317737 : z_pval(long s, GEN p)
    1431             : {
    1432     1317737 :   if (lgefint(p) > 3) return 0;
    1433     1317737 :   return z_lval(s, uel(p,2));
    1434             : }
    1435             : /* assume |p| > 1 */
    1436             : long
    1437         399 : z_pvalrem(long s, GEN p, long *py)
    1438             : {
    1439         399 :   if (lgefint(p) > 3) { *py = s; return 0; }
    1440         399 :   return z_lvalrem(s, uel(p,2), py);
    1441             : }
    1442             : 
    1443             : /* return v_q(x) and set *py = x / q^v_q(x), using divide & conquer */
    1444             : static long
    1445     2095696 : Z_pvalrem_DC(GEN x, GEN q, GEN *py)
    1446             : {
    1447     2095696 :   GEN r, z = dvmdii(x, q, &r);
    1448             :   long v;
    1449     2095656 :   if (r != gen_0) { *py = x; return 0; }
    1450     1446710 :   if (2 * lgefint(q) <= lgefint(z)+3) /* avoid squaring if pointless */
    1451     1430401 :     v = Z_pvalrem_DC(z, sqri(q), py) << 1;
    1452             :   else
    1453       16309 :   { v = 0; *py = z; }
    1454     1446695 :   z = dvmdii(*py, q, &r);
    1455     1446752 :   if (r != gen_0) return v + 1;
    1456      602053 :   *py = z; return v + 2;
    1457             : }
    1458             : 
    1459             : static const long VAL_DC_THRESHOLD = 16;
    1460             : 
    1461             : long
    1462    62675486 : Z_lval(GEN x, ulong p)
    1463             : {
    1464             :   long vx;
    1465             :   pari_sp av;
    1466    62675486 :   if (p == 2) return vali(x);
    1467    48366037 :   if (lgefint(x) == 3) return u_lval(uel(x,2), p);
    1468     2155928 :   av = avma;
    1469     2155928 :   for(vx = 0;;)
    1470    10398939 :   {
    1471             :     ulong r;
    1472    12554867 :     GEN q = absdiviu_rem(x, p, &r);
    1473    12555498 :     if (r) break;
    1474    10574986 :     vx++; x = q;
    1475    10574986 :     if (vx == VAL_DC_THRESHOLD) {
    1476      176047 :       if (p == 1) pari_err_DOMAIN("Z_lval", "p", "=", gen_1, gen_1);
    1477      176047 :       vx += Z_pvalrem_DC(x, sqru(p), &x) << 1;
    1478      176047 :       q = absdiviu_rem(x, p, &r); if (!r) vx++;
    1479      176047 :       break;
    1480             :     }
    1481             :   }
    1482     2156559 :   return gc_long(av,vx);
    1483             : }
    1484             : long
    1485    59487679 : Z_lvalrem(GEN x, ulong p, GEN *py)
    1486             : {
    1487             :   long vx, sx;
    1488             :   pari_sp av;
    1489    59487679 :   if (p == 2) { vx = vali(x); *py = shifti(x, -vx); return vx; }
    1490    46063460 :   if (lgefint(x) == 3) {
    1491             :     ulong u;
    1492    40012891 :     vx = u_lvalrem(uel(x,2), p, &u);
    1493    40012941 :     *py = signe(x) < 0? utoineg(u): utoipos(u);
    1494    40013004 :     return vx;
    1495             :   }
    1496     6050569 :   av = avma; (void)new_chunk(lgefint(x));
    1497     6050981 :   sx = signe(x);
    1498     6050981 :   for(vx = 0;;)
    1499    16391403 :   {
    1500             :     ulong r;
    1501    22442384 :     GEN q = absdiviu_rem(x, p, &r);
    1502    22442378 :     if (r) break;
    1503    16880070 :     vx++; x = q;
    1504    16880070 :     if (vx == VAL_DC_THRESHOLD) {
    1505      488667 :       if (p == 1) pari_err_DOMAIN("Z_lvalrem", "p", "=", gen_1, gen_1);
    1506      488667 :       vx += Z_pvalrem_DC(x, sqru(p), &x) << 1;
    1507      488657 :       q = absdiviu_rem(x, p, &r); if (!r) { vx++; x = q; }
    1508      488664 :       break;
    1509             :     }
    1510             :   }
    1511     6050972 :   set_avma(av); *py = icopy(x); setsigne(*py, sx); return vx;
    1512             : }
    1513             : 
    1514             : /* Is |q| <= p ? */
    1515             : static int
    1516    22167035 : isless_iu(GEN q, ulong p) {
    1517    22167035 :   long l = lgefint(q);
    1518    22167035 :   return l==2 || (l == 3 && uel(q,2) <= p);
    1519             : }
    1520             : 
    1521             : long
    1522   248094585 : u_lvalrem_stop(ulong *n, ulong p, int *stop)
    1523             : {
    1524   248094585 :   ulong N = *n, q = N / p, r = N % p; /* gcc makes a single div */
    1525   248094585 :   long v = 0;
    1526   248094585 :   if (!r)
    1527             :   {
    1528    29350007 :     do { v++; N = q; q = N / p; r = N % p; } while (!r);
    1529    20625731 :     *n = N;
    1530             :   }
    1531   248094585 :   *stop = q <= p; return v;
    1532             : }
    1533             : /* Assume n > 0. Return v_p(n), set *n := n/p^v_p(n). Set 'stop' if now
    1534             :  * n < p^2 [implies n prime if no prime < p divides n] */
    1535             : long
    1536   156130950 : Z_lvalrem_stop(GEN *n, ulong p, int *stop)
    1537             : {
    1538             :   pari_sp av;
    1539             :   long v;
    1540             :   ulong r;
    1541             :   GEN N, q;
    1542             : 
    1543   156130950 :   if (lgefint(*n) == 3)
    1544             :   {
    1545   133964753 :     r = (*n)[2];
    1546   133964753 :     v = u_lvalrem_stop(&r, p, stop);
    1547   133970037 :     if (v) *n = utoipos(r);
    1548   133967585 :     return v;
    1549             :   }
    1550    22166197 :   av = avma; v = 0; q = absdiviu_rem(*n, p, &r);
    1551    22167053 :   if (r) set_avma(av);
    1552             :   else
    1553             :   {
    1554             :     do {
    1555      263520 :       v++; N = q;
    1556      263520 :       if (v == VAL_DC_THRESHOLD)
    1557             :       {
    1558         607 :         v += Z_pvalrem_DC(N,sqru(p),&N) << 1;
    1559         607 :         q = absdiviu_rem(N, p, &r); if (!r) { v++; N = q; }
    1560         607 :         break;
    1561             :       }
    1562      262913 :       q = absdiviu_rem(N, p, &r);
    1563      262913 :     } while (!r);
    1564      222468 :     *n = N;
    1565             :   }
    1566    22167047 :   *stop = isless_iu(q,p); return v;
    1567             : }
    1568             : 
    1569             : /* x is a nonzero integer, |p| > 1 */
    1570             : long
    1571    49639680 : Z_pvalrem(GEN x, GEN p, GEN *py)
    1572             : {
    1573             :   long vx;
    1574             :   pari_sp av;
    1575             : 
    1576    49639680 :   if (lgefint(p) == 3) return Z_lvalrem(x, uel(p,2), py);
    1577       25593 :   if (lgefint(x) == 3) { *py = icopy(x); return 0; }
    1578        8305 :   av = avma; vx = 0; (void)new_chunk(lgefint(x));
    1579             :   for(;;)
    1580       14222 :   {
    1581       22626 :     GEN r, q = dvmdii(x,p,&r);
    1582       22626 :     if (r != gen_0) { set_avma(av); *py = icopy(x); return vx; }
    1583       14222 :     vx++; x = q;
    1584             :   }
    1585             : }
    1586             : long
    1587     2593539 : u_pvalrem(ulong x, GEN p, ulong *py)
    1588             : {
    1589     2593539 :   if (lgefint(p) == 3) return u_lvalrem(x, uel(p,2), py);
    1590         555 :   *py = x; return 0;
    1591             : }
    1592             : long
    1593      136904 : u_pval(ulong x, GEN p)
    1594             : {
    1595      136904 :   if (lgefint(p) == 3) return u_lval(x, uel(p,2));
    1596           0 :   return 0;
    1597             : }
    1598             : long
    1599    47068830 : Z_pval(GEN x, GEN p) {
    1600             :   long vx;
    1601             :   pari_sp av;
    1602             : 
    1603    47068830 :   if (lgefint(p) == 3) return Z_lval(x, uel(p,2));
    1604       33026 :   if (lgefint(x) == 3) return 0;
    1605        8014 :   av = avma; vx = 0;
    1606             :   for(;;)
    1607       25479 :   {
    1608       33493 :     GEN r, q = dvmdii(x,p,&r);
    1609       33494 :     if (r != gen_0) return gc_long(av,vx);
    1610       25479 :     vx++; x = q;
    1611             :   }
    1612             : }
    1613             : 
    1614             : /* return v_p(n!) = [n/p] + [n/p^2] + ... */
    1615             : long
    1616     1982948 : factorial_lval(ulong n, ulong p)
    1617             : {
    1618             :   ulong q, v;
    1619     1982948 :   if (p == 2) return n - hammingl(n);
    1620     1314880 :   q = p; v = 0;
    1621     1443404 :   do { v += n/q; q *= p; } while (n >= q);
    1622     1314880 :   return (long)v;
    1623             : }
    1624             : 
    1625             : /********** Same for "containers" ZX / ZV / ZC **********/
    1626             : 
    1627             : /* If the t_INT q divides the ZX/ZV x, return the quotient. Otherwise NULL.
    1628             :  * Stack clean; assumes lg(x) > 1 */
    1629             : static GEN
    1630        6574 : gen_Z_divides(GEN x, GEN q, long imin)
    1631             : {
    1632             :   long i, l;
    1633        6574 :   GEN y = cgetg_copy(x, &l);
    1634             : 
    1635        6574 :   y[1] = x[1]; /* Needed for ZX; no-op if ZV, overwritten in first iteration */
    1636       88538 :   for (i = imin; i < l; i++)
    1637             :   {
    1638       85954 :     GEN r, xi = gel(x,i);
    1639       85954 :     if (!signe(xi)) { gel(y,i) = xi; continue; }
    1640       55384 :     gel(y,i) = dvmdii(xi, q, &r);
    1641       55384 :     if (r != gen_0) { set_avma((pari_sp)(y+l)); return NULL; }
    1642             :   }
    1643        2584 :   return y;
    1644             : }
    1645             : /* If q divides the ZX/ZV x, return the quotient. Otherwise NULL.
    1646             :  * Stack clean; assumes lg(x) > 1 */
    1647             : static GEN
    1648        4879 : gen_z_divides(GEN x, ulong q, long imin)
    1649             : {
    1650             :   long i, l;
    1651        4879 :   GEN y = cgetg_copy(x, &l);
    1652             : 
    1653        4879 :   y[1] = x[1]; /* Needed for ZX; no-op if ZV, overwritten in first iteration */
    1654       43224 :   for (i = imin; i < l; i++)
    1655             :   {
    1656             :     ulong r;
    1657       41923 :     GEN xi = gel(x,i);
    1658       41923 :     if (!signe(xi)) { gel(y,i) = xi; continue; }
    1659       28609 :     gel(y,i) = absdiviu_rem(xi, q, &r);
    1660       28609 :     if (r) { set_avma((pari_sp)(y+l)); return NULL; }
    1661       25031 :     affectsign_safe(xi, &gel(y,i));
    1662             :   }
    1663        1301 :   return y;
    1664             : }
    1665             : 
    1666             : /* return v_q(x) and set *py = x / q^v_q(x), using divide & conquer */
    1667             : static long
    1668       11416 : gen_pvalrem_DC(GEN x, GEN q, GEN *py, long imin)
    1669             : {
    1670             : 
    1671       11416 :   pari_sp av = avma;
    1672       11416 :   long v, i, l, lz = LONG_MAX;
    1673       11416 :   GEN y = cgetg_copy(x, &l);
    1674             : 
    1675       11416 :   y[1] = x[1];
    1676      134510 :   for (i = imin; i < l; i++)
    1677             :   {
    1678      127936 :     GEN r, xi = gel(x,i);
    1679      127936 :     if (!signe(xi)) { gel(y,i) = xi; continue; }
    1680       86124 :     gel(y,i) = dvmdii(xi, q, &r);
    1681       86124 :     if (r != gen_0) { *py = x; return gc_long(av,0); }
    1682       81282 :     lz = minss(lz, lgefint(gel(y,i)));
    1683             :   }
    1684        6574 :   if (2 * lgefint(q) <= lz+3) /* avoid squaring if pointless */
    1685        6523 :     v = gen_pvalrem_DC(y, sqri(q), py, imin) << 1;
    1686             :   else
    1687          51 :   { v = 0; *py = y; }
    1688             : 
    1689        6574 :   y = gen_Z_divides(*py, q, imin);
    1690        6574 :   if (!y) return v+1;
    1691        2584 :   *py = y; return v+2;
    1692             : }
    1693             : 
    1694             : static long
    1695      772500 : gen_2val(GEN x, long imin)
    1696             : {
    1697      772500 :   long i, lx = lg(x), v = LONG_MAX;
    1698     2917458 :   for (i = imin; i < lx; i++)
    1699             :   {
    1700     2481561 :     GEN c = gel(x,i);
    1701             :     long w;
    1702     2481561 :     if (!signe(c)) continue;
    1703     2269060 :     w = vali(c);
    1704     2269060 :     if (w < v) { v = w; if (!v) break; }
    1705             :   }
    1706      772500 :   return v;
    1707             : }
    1708             : static long
    1709      864689 : gen_lval(GEN x, ulong p, long imin)
    1710             : {
    1711             :   long i, lx, v;
    1712             :   pari_sp av;
    1713             :   GEN y;
    1714      864689 :   if (p == 2) return gen_2val(x, imin);
    1715       92189 :   av = avma;
    1716       92189 :   lx = lg(x); y = leafcopy(x);
    1717      269882 :   for(v = 0;; v++)
    1718     1358869 :     for (i = imin; i < lx; i++)
    1719             :     {
    1720             :       ulong r;
    1721     1181176 :       gel(y,i) = absdiviu_rem(gel(y,i), p, &r);
    1722     1181176 :       if (r) return gc_long(av,v);
    1723             :     }
    1724             : }
    1725             : long
    1726      746096 : ZX_lval(GEN x, ulong p) { return gen_lval(x, p, 2); }
    1727             : long
    1728           0 : ZV_lval(GEN x, ulong p) { return gen_lval(x, p, 1); }
    1729             : 
    1730             : long
    1731       28931 : zx_lval(GEN f, long p)
    1732             : {
    1733       28931 :   long i, l = lg(f), x = LONG_MAX;
    1734       30219 :   for(i=2; i<l; i++)
    1735             :   {
    1736             :     long y;
    1737       29477 :     if (f[i] == 0) continue;
    1738       29428 :     y = z_lval(f[i], p);
    1739       29428 :     if (y < x) { x = y; if (x == 0) return x; }
    1740             :   }
    1741         742 :   return x;
    1742             : }
    1743             : 
    1744             : static long
    1745      128911 : gen_pval(GEN x, GEN p, long imin)
    1746             : {
    1747             :   long i, lx, v;
    1748             :   pari_sp av;
    1749             :   GEN y;
    1750      128911 :   if (lgefint(p) == 3) return gen_lval(x, p[2], imin);
    1751       10318 :   av = avma;
    1752       10318 :   lx = lg(x); y = leafcopy(x);
    1753       10318 :   for(v = 0;; v++)
    1754             :   {
    1755       10318 :     if (v == VAL_DC_THRESHOLD)
    1756             :     {
    1757           0 :       if (is_pm1(p)) pari_err_DOMAIN("gen_pval", "p", "=", p, p);
    1758           0 :       v += gen_pvalrem_DC(y, p, &y, imin);
    1759           0 :       return gc_long(av,v);
    1760             :     }
    1761             : 
    1762       10318 :     for (i = imin; i < lx; i++)
    1763             :     {
    1764       10318 :       GEN r; gel(y,i) = dvmdii(gel(y,i), p, &r);
    1765       10318 :       if (r != gen_0) return gc_long(av,v);
    1766             :     }
    1767             :   }
    1768             : }
    1769             : long
    1770       96382 : ZX_pval(GEN x, GEN p) { return gen_pval(x, p, 2); }
    1771             : long
    1772       32529 : ZV_pval(GEN x, GEN p) { return gen_pval(x, p, 1); }
    1773             : /* v = 0 (mod p) */
    1774             : int
    1775         609 : ZV_Z_dvd(GEN v, GEN p)
    1776             : {
    1777         609 :   pari_sp av = avma;
    1778         609 :   long i, l = lg(v);
    1779        1883 :   for (i=1; i<l; i++)
    1780        1386 :     if (!dvdii(gel(v,i), p)) return gc_long(av,0);
    1781         497 :   return gc_long(av,1);
    1782             : }
    1783             : 
    1784             : static long
    1785     4759225 : gen_2valrem(GEN x, GEN *px, long imin)
    1786             : {
    1787     4759225 :   long i, lx = lg(x), v = LONG_MAX;
    1788             :   GEN z;
    1789    13714795 :   for (i = imin; i < lx; i++)
    1790             :   {
    1791    12405499 :     GEN c = gel(x,i);
    1792             :     long w;
    1793    12405499 :     if (!signe(c)) continue;
    1794    11519872 :     w = vali(c);
    1795    11519990 :     if (w < v) {
    1796     6835173 :       v = w;
    1797     6835173 :       if (!v) { *px = x; return 0; } /* early abort */
    1798             :     }
    1799             :   }
    1800     1309296 :   z = cgetg_copy(x, &lx); z[1] = x[1];
    1801     8401073 :   for (i=imin; i<lx; i++) gel(z,i) = shifti(gel(x,i), -v);
    1802     1309097 :   *px = z; return v;
    1803             : }
    1804             : static long
    1805     8151522 : gen_lvalrem(GEN x, ulong p, GEN *px, long imin)
    1806             : {
    1807             :   long i, lx, v;
    1808             :   GEN y;
    1809     8151522 :   if (p == 2) return gen_2valrem(x, px, imin);
    1810     3392354 :   y = cgetg_copy(x, &lx);
    1811     3392524 :   y[1] = x[1];
    1812     3392524 :   x = leafcopy(x);
    1813     3392140 :   for(v = 0;; v++)
    1814             :   {
    1815     4754333 :     if (v == VAL_DC_THRESHOLD)
    1816             :     {
    1817        4879 :       if (p == 1) pari_err_DOMAIN("gen_lvalrem", "p", "=", gen_1, gen_1);
    1818        4879 :       v += gen_pvalrem_DC(x, sqru(p), px, imin) << 1;
    1819        4879 :       x = gen_z_divides(*px, p, imin);
    1820        4879 :       if (x) { *px = x; v++; }
    1821        4879 :       return v;
    1822             :     }
    1823             : 
    1824    15146354 :     for (i = imin; i < lx; i++)
    1825             :     {
    1826    13784161 :       ulong r; gel(y,i) = absdiviu_rem(gel(x,i), p, &r);
    1827    13783943 :       if (r) { *px = x; return v; }
    1828    10396345 :       affectsign_safe(gel(x,i), &gel(y,i));
    1829             :     }
    1830     1362193 :     swap(x, y);
    1831             :   }
    1832             : }
    1833             : long
    1834         721 : ZX_lvalrem(GEN x, ulong p, GEN *px) { return gen_lvalrem(x,p,px, 2); }
    1835             : long
    1836           0 : ZV_lvalrem(GEN x, ulong p, GEN *px) { return gen_lvalrem(x,p,px, 1); }
    1837             : 
    1838             : static long
    1839     8163655 : gen_pvalrem(GEN x, GEN p, GEN *px, long imin)
    1840             : {
    1841             :   long i, lx, v;
    1842             :   GEN y;
    1843     8163655 :   if (lgefint(p) == 3) return gen_lvalrem(x, p[2], px, imin);
    1844       12892 :   y = cgetg_copy(x, &lx);
    1845       12895 :   y[1] = x[1];
    1846       12895 :   x = leafcopy(x);
    1847       12895 :   for(v = 0;; v++)
    1848             :   {
    1849       13684 :     if (v == VAL_DC_THRESHOLD)
    1850             :     {
    1851          14 :       if (is_pm1(p)) pari_err_DOMAIN("gen_pvalrem", "p", "=", p, p);
    1852          14 :       return v + gen_pvalrem_DC(x, p, px, imin);
    1853             :     }
    1854             : 
    1855       22334 :     for (i = imin; i < lx; i++)
    1856             :     {
    1857       21545 :       GEN r; gel(y,i) = dvmdii(gel(x,i), p, &r);
    1858       21545 :       if (r != gen_0) { *px = x; return v; }
    1859             :     }
    1860         789 :     swap(x, y);
    1861             :   }
    1862             : }
    1863             : long
    1864     4234602 : ZX_pvalrem(GEN x, GEN p, GEN *px) { return gen_pvalrem(x,p,px, 2); }
    1865             : long
    1866     3929052 : ZV_pvalrem(GEN x, GEN p, GEN *px) { return gen_pvalrem(x,p,px, 1); }
    1867             : 
    1868             : static long
    1869           0 : ZX_gen_pvalrem(GEN x, GEN p, GEN *px, long imin)
    1870             : {
    1871             :   long i, lx, v;
    1872             :   GEN y;
    1873           0 :   y = cgetg_copy(x, &lx);
    1874           0 :   y[1] = x[1];
    1875           0 :   x = leafcopy(x);
    1876           0 :   for (i = imin; i < lx; i++)
    1877           0 :     if (typ(gel(x, i)) != t_INT)
    1878             :     {
    1879           0 :       gel(x, i) = leafcopy(gel(x,i));
    1880           0 :       gel(y, i) = leafcopy(gel(x,i));
    1881             :     }
    1882           0 :   for(v = 0;; v++)
    1883             :   {
    1884             : #if 0
    1885             :     if (v == VAL_DC_THRESHOLD) /* TODO */
    1886             :     {
    1887             :       if (is_pm1(p)) pari_err_DOMAIN("ZX_gen_pvalrem", "p", "=", p, p);
    1888             :       return v + ZX_gen_pvalrem_DC(x, p, px, imin);
    1889             :     }
    1890             : #endif
    1891             : 
    1892           0 :     for (i = imin; i < lx; i++)
    1893             :     {
    1894           0 :       GEN r, xi = gel(x,i);
    1895           0 :       if (typ(xi) == t_INT)
    1896             :       {
    1897           0 :         gel(y,i) = dvmdii(xi, p, &r);
    1898           0 :         if (r != gen_0) { *px = x; return v; }
    1899             :       } else
    1900             :       {
    1901           0 :         long j, lxi = lg(xi);
    1902           0 :         for(j = 2; j < lxi; j++)
    1903             :         {
    1904           0 :           gmael(y,i,j) = dvmdii(gel(xi,j), p, &r);
    1905           0 :           if (r != gen_0) { *px = x; return v; }
    1906             :         }
    1907             :       }
    1908             :     }
    1909           0 :     swap(x, y);
    1910             :   }
    1911             : }
    1912             : 
    1913             : long
    1914           0 : ZXX_pvalrem(GEN x, GEN p, GEN *px) { return ZX_gen_pvalrem(x,p,px, 2); }
    1915             : long
    1916           0 : ZXV_pvalrem(GEN x, GEN p, GEN *px) { return ZX_gen_pvalrem(x,p,px, 1); }
    1917             : 
    1918             : /*******************************************************************/
    1919             : /*                                                                 */
    1920             : /*                       NEGATION: Create -x                       */
    1921             : /*                                                                 */
    1922             : /*******************************************************************/
    1923             : 
    1924             : GEN
    1925   454813385 : gneg(GEN x)
    1926             : {
    1927             :   long lx, i;
    1928             :   GEN y;
    1929             : 
    1930   454813385 :   switch(typ(x))
    1931             :   {
    1932   129417209 :     case t_INT:
    1933   129417209 :       return signe(x)? negi(x): gen_0;
    1934   240571474 :     case t_REAL:
    1935   240571474 :       return mpneg(x);
    1936             : 
    1937      222129 :     case t_INTMOD: y=cgetg(3,t_INTMOD);
    1938      222129 :       gel(y,1) = icopy(gel(x,1));
    1939      222129 :       gel(y,2) = signe(gel(x,2))? subii(gel(y,1),gel(x,2)): gen_0;
    1940      222127 :       break;
    1941             : 
    1942     2610017 :     case t_FRAC:
    1943     2610017 :       y = cgetg(3, t_FRAC);
    1944     2610017 :       gel(y,1) = negi(gel(x,1));
    1945     2610017 :       gel(y,2) = icopy(gel(x,2)); break;
    1946             : 
    1947    75602188 :     case t_COMPLEX:
    1948    75602188 :       y=cgetg(3, t_COMPLEX);
    1949    75603279 :       gel(y,1) = gneg(gel(x,1));
    1950    75604894 :       gel(y,2) = gneg(gel(x,2));
    1951    75604887 :       break;
    1952             : 
    1953      246917 :     case t_POLMOD:
    1954      246917 :       retmkpolmod(gneg(gel(x,2)), RgX_copy(gel(x,1)));
    1955             : 
    1956      153363 :     case t_RFRAC:
    1957      153363 :       y = cgetg(3, t_RFRAC);
    1958      153363 :       gel(y,1) = gneg(gel(x,1));
    1959      153363 :       gel(y,2) = RgX_copy(gel(x,2)); break;
    1960             : 
    1961      650282 :     case t_PADIC:
    1962      650282 :       if (!signe(gel(x,4))) return gcopy(x);
    1963      646663 :       y = cgetg(5, t_PADIC);
    1964      646662 :       y[1] = x[1];
    1965      646662 :       gel(y,2) = icopy(gel(x,2));
    1966      646663 :       gel(y,3) = icopy(gel(x,3));
    1967      646663 :       gel(y,4) = subii(gel(x,3),gel(x,4));
    1968      646660 :       break;
    1969             : 
    1970         133 :     case t_QUAD:
    1971         133 :       y=cgetg(4,t_QUAD);
    1972         133 :       gel(y,1) = ZX_copy(gel(x,1));
    1973         133 :       gel(y,2) = gneg(gel(x,2));
    1974         133 :       gel(y,3) = gneg(gel(x,3)); break;
    1975             : 
    1976       80424 :     case t_FFELT: return FF_neg(x);
    1977     4891815 :     case t_POL: return RgX_neg(x);
    1978        1379 :     case t_SER:
    1979        1379 :       y = cgetg_copy(x, &lx); y[1] = x[1];
    1980       16688 :       for (i=2; i<lx; i++) gel(y,i) = gneg(gel(x,i));
    1981        1379 :       break;
    1982        1533 :     case t_VEC: return RgV_neg(x);
    1983      462214 :     case t_COL: return RgC_neg(x);
    1984         315 :     case t_MAT: return RgM_neg(x);
    1985         777 :     case t_INFINITY: return inf_get_sign(x) == 1? mkmoo(): mkoo();
    1986           0 :     default:
    1987           0 :       pari_err_TYPE("gneg",x);
    1988             :       return NULL; /* LCOV_EXCL_LINE */
    1989             :   }
    1990    79238526 :   return y;
    1991             : }
    1992             : 
    1993             : GEN
    1994   129127860 : gneg_i(GEN x)
    1995             : {
    1996             :   long lx, i;
    1997             :   GEN y;
    1998             : 
    1999   129127860 :   switch(typ(x))
    2000             :   {
    2001    66043195 :     case t_INT:
    2002    66043195 :       return signe(x)? negi(x): gen_0;
    2003    29617210 :     case t_REAL:
    2004    29617210 :       return mpneg(x);
    2005             : 
    2006      717747 :     case t_INTMOD: y=cgetg(3,t_INTMOD);
    2007      717747 :       gel(y,1) = gel(x,1);
    2008      717747 :       gel(y,2) = signe(gel(x,2))? subii(gel(y,1),gel(x,2)): gen_0;
    2009      717747 :       break;
    2010             : 
    2011     5126666 :     case t_FRAC:
    2012     5126666 :       y = cgetg(3, t_FRAC);
    2013     5126665 :       gel(y,1) = negi(gel(x,1));
    2014     5126666 :       gel(y,2) = gel(x,2); break;
    2015             : 
    2016    10678752 :     case t_COMPLEX:
    2017    10678752 :       y = cgetg(3, t_COMPLEX);
    2018    10678824 :       gel(y,1) = gneg_i(gel(x,1));
    2019    10678881 :       gel(y,2) = gneg_i(gel(x,2)); break;
    2020             : 
    2021     2015113 :     case t_PADIC: y = cgetg(5,t_PADIC);
    2022     2015113 :       y[1] = x[1];
    2023     2015113 :       gel(y,2) = gel(x,2);
    2024     2015113 :       gel(y,3) = gel(x,3);
    2025     2015113 :       gel(y,4) = signe(gel(x,4))? subii(gel(x,3),gel(x,4)): gen_0; break;
    2026             : 
    2027      143196 :     case t_POLMOD:
    2028      143196 :       retmkpolmod(gneg_i(gel(x,2)), RgX_copy(gel(x,1)));
    2029             : 
    2030       84504 :     case t_FFELT: return FF_neg_i(x);
    2031             : 
    2032         672 :     case t_QUAD: y=cgetg(4,t_QUAD);
    2033         672 :       gel(y,1) = gel(x,1);
    2034         672 :       gel(y,2) = gneg_i(gel(x,2));
    2035         672 :       gel(y,3) = gneg_i(gel(x,3)); break;
    2036             : 
    2037        2478 :     case t_VEC: case t_COL: case t_MAT:
    2038        2478 :       y = cgetg_copy(x, &lx);
    2039       13594 :       for (i=1; i<lx; i++) gel(y,i) = gneg_i(gel(x,i));
    2040        2478 :       break;
    2041             : 
    2042     9660894 :     case t_POL: case t_SER:
    2043     9660894 :       y = cgetg_copy(x, &lx); y[1]=x[1];
    2044    40349497 :       for (i=2; i<lx; i++) gel(y,i) = gneg_i(gel(x,i));
    2045     9660749 :       break;
    2046             : 
    2047     5044843 :     case t_RFRAC:
    2048     5044843 :       y = cgetg(3, t_RFRAC);
    2049     5044843 :       gel(y,1) = gneg_i(gel(x,1));
    2050     5044917 :       gel(y,2) = gel(x,2); break;
    2051             : 
    2052           0 :     default:
    2053           0 :       pari_err_TYPE("gneg_i",x);
    2054             :       return NULL; /* LCOV_EXCL_LINE */
    2055             :   }
    2056    33247236 :   return y;
    2057             : }
    2058             : 
    2059             : /******************************************************************/
    2060             : /*                                                                */
    2061             : /*                       ABSOLUTE VALUE                           */
    2062             : /*    Create abs(x) if x is integer, real, fraction or complex.   */
    2063             : /*                       Error otherwise.                         */
    2064             : /*                                                                */
    2065             : /******************************************************************/
    2066             : static int
    2067           0 : is_negative(GEN x) {
    2068           0 :   switch(typ(x))
    2069             :   {
    2070           0 :     case t_INT: case t_REAL:
    2071           0 :       return (signe(x) < 0);
    2072           0 :     case t_FRAC:
    2073           0 :       return (signe(gel(x,1)) < 0);
    2074             :   }
    2075           0 :   return 0;
    2076             : }
    2077             : 
    2078             : GEN
    2079    50287502 : gabs(GEN x, long prec)
    2080             : {
    2081             :   long lx;
    2082             :   pari_sp av;
    2083             :   GEN y, N;
    2084             : 
    2085    50287502 :   switch(typ(x))
    2086             :   {
    2087    32336631 :     case t_INT: case t_REAL:
    2088    32336631 :       return mpabs(x);
    2089             : 
    2090       12776 :     case t_FRAC:
    2091       12776 :       return absfrac(x);
    2092             : 
    2093    17840792 :     case t_COMPLEX:
    2094    17840792 :       av=avma; N=cxnorm(x);
    2095    17822666 :       switch(typ(N))
    2096             :       {
    2097         266 :         case t_INT:
    2098         266 :           if (!Z_issquareall(N, &y)) break;
    2099         105 :           return gerepileupto(av, y);
    2100       21735 :         case t_FRAC: {
    2101             :           GEN a,b;
    2102       36036 :           if (!Z_issquareall(gel(N,1), &a)) break;
    2103       14301 :           if (!Z_issquareall(gel(N,2), &b)) break;
    2104           0 :           return gerepileupto(av, gdiv(a,b));
    2105             :         }
    2106             :       }
    2107    17822561 :       return gerepileupto(av, gsqrt(N,prec));
    2108             : 
    2109          21 :     case t_QUAD:
    2110          21 :       av = avma;
    2111          21 :       return gerepileuptoleaf(av, gabs(quadtofp(x, prec), prec));
    2112             : 
    2113           0 :     case t_POL:
    2114           0 :       lx = lg(x); if (lx<=2) return RgX_copy(x);
    2115           0 :       return is_negative(gel(x,lx-1))? RgX_neg(x): RgX_copy(x);
    2116             : 
    2117           7 :     case t_SER:
    2118           7 :      if (!signe(x)) pari_err_DOMAIN("abs", "argument", "=", gen_0, x);
    2119           7 :      if (valser(x)) pari_err_DOMAIN("abs", "series valuation", "!=", gen_0, x);
    2120           0 :      return is_negative(gel(x,2))? gneg(x): gcopy(x);
    2121             : 
    2122      102342 :     case t_VEC: case t_COL: case t_MAT:
    2123      613600 :       pari_APPLY_same(gabs(gel(x,i),prec));
    2124             : 
    2125          14 :     case t_INFINITY:
    2126          14 :       return mkoo();
    2127             :   }
    2128           0 :   pari_err_TYPE("gabs",x);
    2129             :   return NULL; /* LCOV_EXCL_LINE */
    2130             : }
    2131             : 
    2132             : GEN
    2133       79268 : gmax(GEN x, GEN y) { return gcopy(gmax_shallow(x,y)); }
    2134             : GEN
    2135           0 : gmaxgs(GEN x, long s) { return (gcmpsg(s,x)>=0)? stoi(s): gcopy(x); }
    2136             : 
    2137             : GEN
    2138       12180 : gmin(GEN x, GEN y) { return gcopy(gmin_shallow(x,y)); }
    2139             : GEN
    2140           0 : gmings(GEN x, long s) { return (gcmpsg(s,x)>0)? gcopy(x): stoi(s); }
    2141             : 
    2142             : long
    2143      503128 : vecindexmax(GEN x)
    2144             : {
    2145      503128 :   long lx = lg(x), i0, i;
    2146             :   GEN s;
    2147             : 
    2148      503128 :   if (lx==1) pari_err_DOMAIN("vecindexmax", "empty argument", "=", x,x);
    2149      503128 :   switch(typ(x))
    2150             :   {
    2151      503128 :     case t_VEC: case t_COL:
    2152      503128 :       s = gel(x,i0=1);
    2153     1502037 :       for (i=2; i<lx; i++)
    2154      998902 :         if (gcmp(gel(x,i),s) > 0) s = gel(x,i0=i);
    2155      503135 :       return i0;
    2156           0 :     case t_VECSMALL:
    2157           0 :       return vecsmall_indexmax(x);
    2158           0 :     default: pari_err_TYPE("vecindexmax",x);
    2159             :   }
    2160             :   /* LCOV_EXCL_LINE */
    2161           0 :   return 0;
    2162             : }
    2163             : long
    2164      181317 : vecindexmin(GEN x)
    2165             : {
    2166      181317 :   long lx = lg(x), i0, i;
    2167             :   GEN s;
    2168             : 
    2169      181317 :   if (lx==1) pari_err_DOMAIN("vecindexmin", "empty argument", "=", x,x);
    2170      181317 :   switch(typ(x))
    2171             :   {
    2172      181317 :     case t_VEC: case t_COL:
    2173      181317 :       s = gel(x,i0=1);
    2174      943613 :       for (i=2; i<lx; i++)
    2175      762296 :         if (gcmp(gel(x,i),s) < 0) s = gel(x,i0=i);
    2176      181317 :       return i0;
    2177           0 :     case t_VECSMALL:
    2178           0 :       return vecsmall_indexmin(x);
    2179           0 :     default: pari_err_TYPE("vecindexmin",x);
    2180             :   }
    2181             :   /* LCOV_EXCL_LINE */
    2182           0 :   return 0;
    2183             : }
    2184             : 
    2185             : GEN
    2186      226716 : vecmax0(GEN x, GEN *pi)
    2187             : {
    2188      226716 :   long i, lx = lg(x), tx = typ(x);
    2189      226716 :   if (!is_matvec_t(tx) && tx != t_VECSMALL
    2190          49 :       && (tx != t_LIST || list_typ(x) != t_LIST_RAW)) return gcopy(x);
    2191      226695 :   if (tx == t_LIST)
    2192          28 :   { if (list_data(x)) { x = list_data(x); lx = lg(x); } else lx = 1; }
    2193      226695 :   if (lx==1) pari_err_DOMAIN("vecmax", "empty argument", "=", x,x);
    2194      226653 :   switch(typ(x))
    2195             :   {
    2196      226162 :     case t_VEC: case t_COL:
    2197      226162 :       i = vecindexmax(x); if (pi) *pi = utoipos(i);
    2198      226165 :       return gcopy(gel(x,i));
    2199         470 :     case t_MAT: {
    2200         470 :       long j, i0 = 1, j0 = 1, lx2 = lgcols(x);
    2201             :       GEN s;
    2202         470 :       if (lx2 == 1) pari_err_DOMAIN("vecmax", "empty argument", "=", x,x);
    2203         463 :       s = gcoeff(x,i0,j0); i = 2;
    2204        1779 :       for (j=1; j<lx; j++,i=1)
    2205             :       {
    2206        1316 :         GEN c = gel(x,j);
    2207       24763 :         for (; i<lx2; i++)
    2208       23447 :           if (gcmp(gel(c,i),s) > 0) { s = gel(c,i); j0=j; i0=i; }
    2209             :       }
    2210         463 :       if (pi) *pi = mkvec2(utoipos(i0), utoipos(j0));
    2211         463 :       return gcopy(s);
    2212             :     }
    2213          21 :     case t_VECSMALL:
    2214          21 :       i = vecsmall_indexmax(x); if (pi) *pi = utoipos(i);
    2215          21 :       return stoi(x[i]);
    2216             :   }
    2217             :   return NULL;/*LCOV_EXCL_LINE*/
    2218             : }
    2219             : GEN
    2220      146667 : vecmin0(GEN x, GEN *pi)
    2221             : {
    2222      146667 :   long i, lx = lg(x), tx = typ(x);
    2223      146667 :   if (!is_matvec_t(tx) && tx != t_VECSMALL
    2224          49 :       && (tx != t_LIST || list_typ(x) != t_LIST_RAW)) return gcopy(x);
    2225      146646 :   if (tx == t_LIST)
    2226          28 :   { if (list_data(x)) { x = list_data(x); lx = lg(x); } else lx = 1; }
    2227      146646 :   if (lx==1) pari_err_DOMAIN("vecmin", "empty argument", "=", x,x);
    2228      146611 :   switch(typ(x))
    2229             :   {
    2230      146569 :     case t_VEC: case t_COL:
    2231      146569 :       i = vecindexmin(x); if (pi) *pi = utoipos(i);
    2232      146569 :       return gcopy(gel(x,i));
    2233          21 :     case t_MAT: {
    2234          21 :       long j, i0 = 1, j0 = 1, lx2 = lgcols(x);
    2235             :       GEN s;
    2236          21 :       if (lx2 == 1) pari_err_DOMAIN("vecmin", "empty argument", "=", x,x);
    2237          21 :       s = gcoeff(x,i0,j0); i = 2;
    2238          63 :       for (j=1; j<lx; j++,i=1)
    2239             :       {
    2240          42 :         GEN c = gel(x,j);
    2241         105 :         for (; i<lx2; i++)
    2242          63 :           if (gcmp(gel(c,i),s) < 0) { s = gel(c,i); j0=j; i0=i; }
    2243             :       }
    2244          21 :       if (pi) *pi = mkvec2(utoipos(i0), utoipos(j0));
    2245          21 :       return gcopy(s);
    2246             :     }
    2247          21 :     case t_VECSMALL:
    2248          21 :       i = vecsmall_indexmin(x); if (pi) *pi = utoipos(i);
    2249          21 :       return stoi(x[i]);
    2250             :   }
    2251             :   return NULL;/*LCOV_EXCL_LINE*/
    2252             : }
    2253             : 
    2254             : GEN
    2255       66117 : vecmax(GEN x) { return vecmax0(x, NULL); }
    2256             : GEN
    2257       34499 : vecmin(GEN x) { return vecmin0(x, NULL); }
    2258             : 
    2259             : /*******************************************************************/
    2260             : /*                                                                 */
    2261             : /*                      AFFECT long --> GEN                        */
    2262             : /*         affect long s to GEN x. Useful for initialization.      */
    2263             : /*                                                                 */
    2264             : /*******************************************************************/
    2265             : 
    2266             : static void
    2267           0 : padicaff0(GEN x)
    2268             : {
    2269           0 :   if (signe(gel(x,4)))
    2270             :   {
    2271           0 :     x[1] = evalvalp(valp(x)+precp(x));
    2272           0 :     affsi(0,gel(x,4));
    2273             :   }
    2274           0 : }
    2275             : 
    2276             : void
    2277       91826 : gaffsg(long s, GEN x)
    2278             : {
    2279       91826 :   switch(typ(x))
    2280             :   {
    2281       90916 :     case t_INT: affsi(s,x); break;
    2282         910 :     case t_REAL: affsr(s,x); break;
    2283           0 :     case t_INTMOD: modsiz(s,gel(x,1),gel(x,2)); break;
    2284           0 :     case t_FRAC: affsi(s,gel(x,1)); affsi(1,gel(x,2)); break;
    2285           0 :     case t_COMPLEX: gaffsg(s,gel(x,1)); gaffsg(0,gel(x,2)); break;
    2286           0 :     case t_PADIC: {
    2287             :       long vx;
    2288             :       GEN y;
    2289           0 :       if (!s) { padicaff0(x); break; }
    2290           0 :       vx = Z_pvalrem(stoi(s), gel(x,2), &y);
    2291           0 :       setvalp(x,vx); modiiz(y,gel(x,3),gel(x,4));
    2292           0 :       break;
    2293             :     }
    2294           0 :     case t_QUAD: gaffsg(s,gel(x,2)); gaffsg(0,gel(x,3)); break;
    2295           0 :     default: pari_err_TYPE2("=",stoi(s),x);
    2296             :   }
    2297       91826 : }
    2298             : 
    2299             : /*******************************************************************/
    2300             : /*                                                                 */
    2301             : /*                     GENERIC AFFECTATION                         */
    2302             : /*         Affect the content of x to y, whenever possible         */
    2303             : /*                                                                 */
    2304             : /*******************************************************************/
    2305             : /* x PADIC, Y INT, return lift(x * Mod(1,Y)) */
    2306             : GEN
    2307        4466 : padic_to_Fp(GEN x, GEN Y) {
    2308        4466 :   pari_sp av = avma;
    2309        4466 :   GEN p = gel(x,2), z;
    2310        4466 :   long vy, vx = valp(x);
    2311        4466 :   if (!signe(Y)) pari_err_INV("padic_to_Fp",Y);
    2312        4466 :   vy = Z_pvalrem(Y,p, &z);
    2313        4466 :   if (vx < 0 || !gequal1(z)) pari_err_OP("",x, mkintmod(gen_1,Y));
    2314        4445 :   if (vx >= vy) { set_avma(av); return gen_0; }
    2315        4088 :   z = gel(x,4);
    2316        4088 :   if (!signe(z) || vy > vx + precp(x)) pari_err_OP("",x, mkintmod(gen_1,Y));
    2317        4088 :   if (vx) z = mulii(z, powiu(p,vx));
    2318        4088 :   return gerepileuptoint(av, remii(z, Y));
    2319             : }
    2320             : ulong
    2321      421697 : padic_to_Fl(GEN x, ulong Y) {
    2322      421697 :   GEN p = gel(x,2);
    2323             :   ulong u, z;
    2324      421697 :   long vy, vx = valp(x);
    2325      421697 :   vy = u_pvalrem(Y,p, &u);
    2326      421701 :   if (vx < 0 || u != 1) pari_err_OP("",x, mkintmodu(1,Y));
    2327             :   /* Y = p^vy */
    2328      421701 :   if (vx >= vy) return 0;
    2329      375991 :   z = umodiu(gel(x,4), Y);
    2330      375996 :   if (!z || vy > vx + precp(x)) pari_err_OP("",x, mkintmodu(1,Y));
    2331      375995 :   if (vx) {
    2332           0 :     ulong pp = p[2];
    2333           0 :     z = Fl_mul(z, upowuu(pp,vx), Y); /* p^vx < p^vy = Y */
    2334             :   }
    2335      375995 :   return z;
    2336             : }
    2337             : 
    2338             : static void
    2339           0 : croak(const char *s) {
    2340             :   char *t;
    2341           0 :   t = stack_sprintf("gaffect [overwriting universal object: %s]",s);
    2342           0 :   pari_err_BUG(t);
    2343           0 : }
    2344             : 
    2345             : void
    2346      664508 : gaffect(GEN x, GEN y)
    2347             : {
    2348      664508 :   long vx, i, lx, ly, tx = typ(x), ty = typ(y);
    2349             :   pari_sp av;
    2350             :   GEN p1, num, den;
    2351             : 
    2352      664508 :   if (tx == ty) switch(tx) {
    2353      215615 :     case t_INT:
    2354      572682 :       if (!is_universal_constant(y)) { affii(x,y); return; }
    2355             :       /* y = gen_0, gnil, gen_1 or gen_2 */
    2356           0 :       if (y==gen_0)  croak("gen_0");
    2357           0 :       if (y==gen_1)  croak("gen_1");
    2358           0 :       if (y==gen_m1) croak("gen_m1");
    2359           0 :       if (y==gen_m2) croak("gen_m2");
    2360           0 :       if (y==gen_2)  croak("gen_2");
    2361           0 :       croak("gnil)");
    2362      188930 :     case t_REAL: affrr(x,y); return;
    2363           0 :     case t_INTMOD:
    2364           0 :       if (!dvdii(gel(x,1),gel(y,1))) pari_err_OP("",x,y);
    2365           0 :       modiiz(gel(x,2),gel(y,1),gel(y,2)); return;
    2366           0 :     case t_FRAC:
    2367           0 :       affii(gel(x,1),gel(y,1));
    2368           0 :       affii(gel(x,2),gel(y,2)); return;
    2369       95424 :     case t_COMPLEX:
    2370       95424 :       gaffect(gel(x,1),gel(y,1));
    2371       95424 :       gaffect(gel(x,2),gel(y,2)); return;
    2372           0 :     case t_PADIC:
    2373           0 :       if (!equalii(gel(x,2),gel(y,2))) pari_err_OP("",x,y);
    2374           0 :       modiiz(gel(x,4),gel(y,3),gel(y,4));
    2375           0 :       setvalp(y,valp(x)); return;
    2376           0 :     case t_QUAD:
    2377           0 :       if (! ZX_equal(gel(x,1),gel(y,1))) pari_err_OP("",x,y);
    2378           0 :       affii(gel(x,2),gel(y,2));
    2379           0 :       affii(gel(x,3),gel(y,3)); return;
    2380       72713 :     case t_VEC: case t_COL: case t_MAT:
    2381       72713 :       lx = lg(x); if (lx != lg(y)) pari_err_DIM("gaffect");
    2382      194584 :       for (i=1; i<lx; i++) gaffect(gel(x,i),gel(y,i));
    2383       72713 :       return;
    2384             :   }
    2385             : 
    2386             :   /* Various conversions. Avoid them, use specialized routines ! */
    2387             : 
    2388       91826 :   if (!is_const_t(ty)) pari_err_TYPE2("=",x,y);
    2389       91826 :   switch(tx)
    2390             :   {
    2391           0 :     case t_INT:
    2392             :       switch(ty)
    2393             :       {
    2394           0 :         case t_REAL:
    2395           0 :           affir(x,y); break;
    2396             : 
    2397           0 :         case t_INTMOD:
    2398           0 :           modiiz(x,gel(y,1),gel(y,2)); break;
    2399             : 
    2400           0 :         case t_COMPLEX:
    2401           0 :           gaffect(x,gel(y,1)); gaffsg(0,gel(y,2)); break;
    2402             : 
    2403           0 :         case t_PADIC:
    2404           0 :           if (!signe(x)) { padicaff0(y); break; }
    2405           0 :           av = avma;
    2406           0 :           setvalp(y, Z_pvalrem(x,gel(y,2),&p1));
    2407           0 :           affii(modii(p1,gel(y,3)), gel(y,4));
    2408           0 :           set_avma(av); break;
    2409             : 
    2410           0 :         case t_QUAD: gaffect(x,gel(y,2)); gaffsg(0,gel(y,3)); break;
    2411           0 :         default: pari_err_TYPE2("=",x,y);
    2412             :       }
    2413           0 :       break;
    2414             : 
    2415       91826 :     case t_REAL:
    2416             :       switch(ty)
    2417             :       {
    2418       91826 :         case t_COMPLEX: gaffect(x,gel(y,1)); gaffsg(0,gel(y,2)); break;
    2419           0 :         default: pari_err_TYPE2("=",x,y);
    2420             :       }
    2421       91826 :       break;
    2422             : 
    2423           0 :     case t_FRAC:
    2424             :       switch(ty)
    2425             :       {
    2426           0 :         case t_REAL: rdiviiz(gel(x,1),gel(x,2), y); break;
    2427           0 :         case t_INTMOD: av = avma;
    2428           0 :           p1 = Fp_inv(gel(x,2),gel(y,1));
    2429           0 :           affii(modii(mulii(gel(x,1),p1),gel(y,1)), gel(y,2));
    2430           0 :           set_avma(av); break;
    2431           0 :         case t_COMPLEX: gaffect(x,gel(y,1)); gaffsg(0,gel(y,2)); break;
    2432           0 :         case t_PADIC:
    2433           0 :           if (!signe(gel(x,1))) { padicaff0(y); break; }
    2434           0 :           num = gel(x,1);
    2435           0 :           den = gel(x,2);
    2436           0 :           av = avma; vx = Z_pvalrem(num, gel(y,2), &num);
    2437           0 :           if (!vx) vx = -Z_pvalrem(den,gel(y,2),&den);
    2438           0 :           setvalp(y,vx);
    2439           0 :           p1 = mulii(num,Fp_inv(den,gel(y,3)));
    2440           0 :           affii(modii(p1,gel(y,3)), gel(y,4)); set_avma(av); break;
    2441           0 :         case t_QUAD: gaffect(x,gel(y,2)); gaffsg(0,gel(y,3)); break;
    2442           0 :         default: pari_err_TYPE2("=",x,y);
    2443             :       }
    2444           0 :       break;
    2445             : 
    2446           0 :     case t_COMPLEX:
    2447           0 :       if (!gequal0(gel(x,2))) pari_err_TYPE2("=",x,y);
    2448           0 :       gaffect(gel(x,1), y);
    2449           0 :       break;
    2450             : 
    2451           0 :     case t_PADIC:
    2452             :       switch(ty)
    2453             :       {
    2454           0 :         case t_INTMOD:
    2455           0 :           av = avma; affii(padic_to_Fp(x, gel(y,1)), gel(y,2));
    2456           0 :           set_avma(av); break;
    2457           0 :         default: pari_err_TYPE2("=",x,y);
    2458             :       }
    2459           0 :       break;
    2460             : 
    2461           0 :     case t_QUAD:
    2462             :       switch(ty)
    2463             :       {
    2464           0 :         case t_INT: case t_INTMOD: case t_FRAC: case t_PADIC:
    2465           0 :           pari_err_TYPE2("=",x,y);
    2466             : 
    2467           0 :         case t_REAL:
    2468           0 :           av = avma; affgr(quadtofp(x,realprec(y)), y); set_avma(av); break;
    2469           0 :         case t_COMPLEX:
    2470           0 :           ly = precision(y); if (!ly) pari_err_TYPE2("=",x,y);
    2471           0 :           av = avma; gaffect(quadtofp(x,ly), y); set_avma(av); break;
    2472           0 :         default: pari_err_TYPE2("=",x,y);
    2473             :       }
    2474           0 :     default: pari_err_TYPE2("=",x,y);
    2475             :   }
    2476             : }
    2477             : 
    2478             : /*******************************************************************/
    2479             : /*                                                                 */
    2480             : /*           CONVERSION QUAD --> REAL, COMPLEX OR P-ADIC           */
    2481             : /*                                                                 */
    2482             : /*******************************************************************/
    2483             : GEN
    2484         252 : quadtofp(GEN x, long prec)
    2485             : {
    2486         252 :   GEN b, D, z, u = gel(x,2), v = gel(x,3);
    2487             :   pari_sp av;
    2488         252 :   if (prec < LOWDEFAULTPREC) prec = LOWDEFAULTPREC;
    2489         252 :   if (isintzero(v)) return cxcompotor(u, prec);
    2490         252 :   av = avma; D = quad_disc(x); b = gel(gel(x,1),3); /* 0 or -1 */
    2491             :   /* u + v (-b + sqrt(D)) / 2 */
    2492         252 :   if (!signe(b)) b = NULL;
    2493         252 :   if (b) u = gadd(gmul2n(u,1), v);
    2494         252 :   z = sqrtr_abs(itor(D, prec));
    2495         252 :   if (!b) shiftr_inplace(z, -1);
    2496         252 :   z = gmul(v, z);
    2497         252 :   if (signe(D) < 0)
    2498             :   {
    2499          35 :     z = mkcomplex(cxcompotor(u, prec), z);
    2500          35 :     if (!b) return gerepilecopy(av, z);
    2501           0 :     z = gmul2n(z, -1);
    2502             :   }
    2503             :   else
    2504             :   { /* if (b) x ~ (u + z) / 2 and quadnorm(x) ~ (u^2 - z^2) / 4
    2505             :      * else x ~ u + z and quadnorm(x) ~ u^2 - z^2 */
    2506         217 :     long s = gsigne(u);
    2507         217 :     if (s == -gsigne(v)) /* conjugate expression avoids cancellation */
    2508             :     {
    2509          14 :       z = gdiv(quadnorm(x), gsub(u, z));
    2510          14 :       if (b) shiftr_inplace(z, 1);
    2511             :     }
    2512             :     else
    2513             :     {
    2514         203 :       if (s) z = gadd(u, z);
    2515         203 :       if (b) shiftr_inplace(z, -1);
    2516             :     }
    2517             :   }
    2518         217 :   return gerepileupto(av, z);
    2519             : }
    2520             : 
    2521             : static GEN
    2522          28 : qtop(GEN x, GEN p, long d)
    2523             : {
    2524          28 :   GEN z, D, P, b, u = gel(x,2), v = gel(x,3);
    2525             :   pari_sp av;
    2526          28 :   if (gequal0(v)) return cvtop(u, p, d);
    2527          28 :   P = gel(x,1);
    2528          28 :   b = gel(P,3);
    2529          28 :   av = avma; D = quad_disc(x);
    2530          28 :   if (absequaliu(p,2)) d += 2;
    2531          28 :   z = Qp_sqrt(cvtop(D,p,d));
    2532          28 :   if (!z) pari_err_SQRTN("Qp_sqrt",D);
    2533          14 :   z = gmul2n(gsub(z, b), -1);
    2534             : 
    2535          14 :   z = gadd(u, gmul(v, z));
    2536          14 :   if (typ(z) != t_PADIC) /* t_INTMOD for t_QUAD of t_INTMODs... */
    2537           0 :     z = cvtop(z, p, d);
    2538          14 :   return gerepileupto(av, z);
    2539             : }
    2540             : static GEN
    2541          14 : ctop(GEN x, GEN p, long d)
    2542             : {
    2543          14 :   pari_sp av = avma;
    2544          14 :   GEN z, u = gel(x,1), v = gel(x,2);
    2545          14 :   if (isrationalzero(v)) return cvtop(u, p, d);
    2546          14 :   z = Qp_sqrt(cvtop(gen_m1, p, d - gvaluation(v, p))); /* = I */
    2547          14 :   if (!z) pari_err_SQRTN("Qp_sqrt",gen_m1);
    2548             : 
    2549          14 :   z = gadd(u, gmul(v, z));
    2550          14 :   if (typ(z) != t_PADIC) /* t_INTMOD for t_COMPLEX of t_INTMODs... */
    2551           0 :     z = cvtop(z, p, d);
    2552          14 :   return gerepileupto(av, z);
    2553             : }
    2554             : 
    2555             : /* cvtop2(stoi(s), y) */
    2556             : GEN
    2557         399 : cvstop2(long s, GEN y)
    2558             : {
    2559         399 :   GEN z, p = gel(y,2);
    2560         399 :   long v, d = signe(gel(y,4))? precp(y): 0;
    2561         399 :   if (!s) return zeropadic_shallow(p, d);
    2562         399 :   v = z_pvalrem(s, p, &s);
    2563         399 :   if (d <= 0) return zeropadic_shallow(p, v);
    2564         399 :   z = cgetg(5, t_PADIC);
    2565         399 :   z[1] = evalprecp(d) | evalvalp(v);
    2566         399 :   gel(z,2) = p;
    2567         399 :   gel(z,3) = gel(y,3);
    2568         399 :   gel(z,4) = modsi(s, gel(y,3)); return z;
    2569             : }
    2570             : 
    2571             : static GEN
    2572    17608699 : itop2_coprime(GEN x, GEN y, long v, long d)
    2573             : {
    2574    17608699 :   GEN z = cgetg(5, t_PADIC);
    2575    17608160 :   z[1] = evalprecp(d) | evalvalp(v);
    2576    17607972 :   gel(z,2) = gel(y,2);
    2577    17607972 :   gel(z,3) = gel(y,3);
    2578    17607972 :   gel(z,4) = modii(x, gel(y,3)); return z;
    2579             : }
    2580             : /* cvtop(x, gel(y,2), precp(y)), shallow */
    2581             : GEN
    2582    17615405 : cvtop2(GEN x, GEN y)
    2583             : {
    2584    17615405 :   GEN p = gel(y,2);
    2585    17615405 :   long v, d = signe(gel(y,4))? precp(y): 0;
    2586    17615405 :   switch(typ(x))
    2587             :   {
    2588    14818339 :     case t_INT:
    2589    14818339 :       if (!signe(x)) return zeropadic_shallow(p, d);
    2590    14818339 :       if (d <= 0) return zeropadic_shallow(p, Z_pval(x,p));
    2591    14813950 :       v = Z_pvalrem(x, p, &x); return itop2_coprime(x, y, v, d);
    2592             : 
    2593           0 :     case t_INTMOD:
    2594           0 :       v = Z_pval(gel(x,1),p); if (v > d) v = d;
    2595           0 :       return cvtop(gel(x,2), p, v);
    2596             : 
    2597     2796315 :     case t_FRAC:
    2598             :     {
    2599             :       GEN num, den;
    2600     2796315 :       if (d <= 0) return zeropadic_shallow(p, Q_pval(x,p));
    2601     2795034 :       num = gel(x,1); v = Z_pvalrem(num, p, &num);
    2602     2795034 :       den = gel(x,2); if (!v) v = -Z_pvalrem(den, p, &den);
    2603     2795033 :       if (!is_pm1(den)) num = mulii(num, Fp_inv(den, gel(y,3)));
    2604     2795028 :       return itop2_coprime(num, y, v, d);
    2605             :     }
    2606           7 :     case t_COMPLEX: return ctop(x, p, d);
    2607          28 :     case t_QUAD:    return qtop(x, p, d);
    2608         931 :     case t_PADIC:
    2609         931 :       if (!signe(gel(x,4))) return zeropadic_shallow(p, d);
    2610         931 :       if (precp(x) <= d) return x;
    2611          35 :       return itop2_coprime(gel(x,4), y, valp(x), d); /* reduce accuracy */
    2612             :   }
    2613           0 :   pari_err_TYPE("cvtop2",x);
    2614             :   return NULL; /* LCOV_EXCL_LINE */
    2615             : }
    2616             : 
    2617             : /* assume is_const_t(tx) */
    2618             : GEN
    2619      600442 : cvtop(GEN x, GEN p, long d)
    2620             : {
    2621             :   GEN z;
    2622             :   long v;
    2623             : 
    2624      600442 :   if (typ(p) != t_INT) pari_err_TYPE("cvtop",p);
    2625      600444 :   switch(typ(x))
    2626             :   {
    2627      268175 :     case t_INT:
    2628      268175 :       if (!signe(x)) return zeropadic(p, d);
    2629      266957 :       if (d <= 0) return zeropadic(p, Z_pval(x,p));
    2630      266901 :       v = Z_pvalrem(x, p, &x);
    2631      266901 :       z = cgetg(5, t_PADIC);
    2632      266901 :       z[1] = evalprecp(d) | evalvalp(v);
    2633      266901 :       gel(z,2) = icopy(p);
    2634      266901 :       gel(z,3) = powiu(p, d);
    2635      266901 :       gel(z,4) = modii(x, gel(z,3)); return z; /* not memory-clean */
    2636             : 
    2637          28 :     case t_INTMOD:
    2638          28 :       v = Z_pval(gel(x,1),p); if (v > d) v = d;
    2639          28 :       return cvtop(gel(x,2), p, v);
    2640             : 
    2641      163019 :     case t_FRAC:
    2642             :     {
    2643             :       GEN num, den;
    2644      163019 :       if (d <= 0) return zeropadic(p, Q_pval(x,p));
    2645      163005 :       num = gel(x,1); v = Z_pvalrem(num, p, &num);
    2646      163005 :       den = gel(x,2); if (!v) v = -Z_pvalrem(den, p, &den);
    2647      163005 :       z = cgetg(5, t_PADIC);
    2648      163005 :       z[1] = evalprecp(d) | evalvalp(v);
    2649      163005 :       gel(z,2) = icopy(p);
    2650      163005 :       gel(z,3) = powiu(p, d);
    2651      163005 :       if (!is_pm1(den)) num = mulii(num, Fp_inv(den, gel(z,3)));
    2652      163005 :       gel(z,4) = modii(num, gel(z,3)); return z; /* not memory-clean */
    2653             :     }
    2654           7 :     case t_COMPLEX: return ctop(x, p, d);
    2655      169215 :     case t_PADIC:
    2656      169215 :       p = gel(x,2); /* override */
    2657      169215 :       if (!signe(gel(x,4))) return zeropadic(p, d);
    2658      169138 :       z = cgetg(5,t_PADIC);
    2659      169138 :       z[1] = x[1]; setprecp(z,d);
    2660      169138 :       gel(z,2) = icopy(p);
    2661      169138 :       gel(z,3) = powiu(p, d);
    2662      169138 :       gel(z,4) = modii(gel(x,4), gel(z,3)); return z;
    2663             : 
    2664           0 :     case t_QUAD: return qtop(x, p, d);
    2665             :   }
    2666           0 :   pari_err_TYPE("cvtop",x);
    2667             :   return NULL; /* LCOV_EXCL_LINE */
    2668             : }
    2669             : 
    2670             : GEN
    2671         126 : gcvtop(GEN x, GEN p, long r)
    2672             : {
    2673             :   long i, lx;
    2674             :   GEN y;
    2675             : 
    2676         126 :   switch(typ(x))
    2677             :   {
    2678          28 :     case t_POL: case t_SER:
    2679          28 :       y = cgetg_copy(x, &lx); y[1] = x[1];
    2680          98 :       for (i=2; i<lx; i++) gel(y,i) = gcvtop(gel(x,i),p,r);
    2681          28 :       return y;
    2682           0 :     case t_POLMOD: case t_RFRAC: case t_VEC: case t_COL: case t_MAT:
    2683           0 :       pari_APPLY_same(gcvtop(gel(x,i),p,r));
    2684             :   }
    2685          98 :   return cvtop(x,p,r);
    2686             : }
    2687             : 
    2688             : long
    2689   817685129 : gexpo_safe(GEN x)
    2690             : {
    2691   817685129 :   long tx = typ(x), lx, e, f, i;
    2692             : 
    2693   817685129 :   switch(tx)
    2694             :   {
    2695   167264698 :     case t_INT:
    2696   167264698 :       return expi(x);
    2697             : 
    2698     1094614 :     case t_FRAC:
    2699     1094614 :       return expi(gel(x,1)) - expi(gel(x,2));
    2700             : 
    2701   454530218 :     case t_REAL:
    2702   454530218 :       return expo(x);
    2703             : 
    2704    86929188 :     case t_COMPLEX:
    2705    86929188 :       e = gexpo(gel(x,1));
    2706    86929323 :       f = gexpo(gel(x,2)); return maxss(e, f);
    2707             : 
    2708          91 :     case t_QUAD: {
    2709          91 :       GEN p = gel(x,1); /* mod = X^2 + {0,1}* X - {D/4, (1-D)/4})*/
    2710          91 :       long d = 1 + expi(gel(p,2))/2; /* ~ expo(sqrt(D)) */
    2711          91 :       e = gexpo(gel(x,2));
    2712          91 :       f = gexpo(gel(x,3)) + d; return maxss(e, f);
    2713             :     }
    2714    76527728 :     case t_POL: case t_SER:
    2715    76527728 :       lx = lg(x); f = -(long)HIGHEXPOBIT;
    2716   305897019 :       for (i=2; i<lx; i++) { e=gexpo(gel(x,i)); if (e>f) f=e; }
    2717    76523577 :       return f;
    2718    31446052 :     case t_VEC: case t_COL: case t_MAT:
    2719    31446052 :       lx = lg(x); f = -(long)HIGHEXPOBIT;
    2720   217468658 :       for (i=1; i<lx; i++) { e=gexpo(gel(x,i)); if (e>f) f=e; }
    2721    31445941 :       return f;
    2722             :   }
    2723          48 :   return -1-(long)HIGHEXPOBIT;
    2724             : }
    2725             : long
    2726   817449561 : gexpo(GEN x)
    2727             : {
    2728   817449561 :   long e = gexpo_safe(x);
    2729   817449931 :   if (e < -(long)HIGHEXPOBIT) pari_err_TYPE("gexpo",x);
    2730   817451499 :   return e;
    2731             : }
    2732             : GEN
    2733       89627 : gpexponent(GEN x)
    2734             : {
    2735       89627 :   long e = gexpo(x);
    2736       89627 :   return e == -(long)HIGHEXPOBIT? mkmoo(): stoi(e);
    2737             : }
    2738             : 
    2739             : long
    2740           7 : sizedigit(GEN x)
    2741             : {
    2742           7 :   return gequal0(x)? 0: (long) ((gexpo(x)+1) * LOG10_2) + 1;
    2743             : }
    2744             : 
    2745             : /* normalize series. avma is not updated */
    2746             : GEN
    2747    13402030 : normalizeser(GEN x)
    2748             : {
    2749    13402030 :   long i, lx = lg(x), vx=varn(x), vp=valser(x);
    2750             :   GEN y, z;
    2751             : 
    2752    13402030 :   if (lx == 2) { setsigne(x,0); return x; }
    2753    13401666 :   if (lx == 3) {
    2754      199387 :     z = gel(x,2);
    2755      199387 :     if (!gequal0(z)) { setsigne(x,1); return x; }
    2756       23730 :     if (isrationalzero(z)) return zeroser(vx,vp+1);
    2757        4277 :     if (isexactzero(z)) {
    2758             :       /* dangerous case: already normalized ? */
    2759         252 :       if (!signe(x)) return x;
    2760          35 :       setvalser(x,vp+1); /* no: normalize */
    2761             :     }
    2762        4060 :     setsigne(x,0); return x;
    2763             :   }
    2764    13496395 :   for (i=2; i<lx; i++)
    2765    13449663 :     if (! isrationalzero(gel(x,i))) break;
    2766    13202279 :   if (i == lx) return zeroser(vx,lx-2+vp);
    2767    13155547 :   z = gel(x,i);
    2768    13159348 :   while (i<lx && isexactzero(gel(x,i))) i++;
    2769    13155547 :   if (i == lx)
    2770             :   {
    2771         273 :     i -= 3; y = x + i;
    2772         273 :     stackdummy((pari_sp)y, (pari_sp)x);
    2773         273 :     gel(y,2) = z;
    2774         273 :     y[1] = evalsigne(0) | evalvalser(lx-2+vp) | evalvarn(vx);
    2775         273 :     y[0] = evaltyp(t_SER) | _evallg(3);
    2776         273 :     return y;
    2777             :   }
    2778             : 
    2779    13155274 :   i -= 2; y = x + i; lx -= i;
    2780    13155274 :   y[1] = evalsigne(1) | evalvalser(vp+i) | evalvarn(vx);
    2781    13155274 :   y[0] = evaltyp(t_SER) | _evallg(lx);
    2782             : 
    2783    13155274 :   stackdummy((pari_sp)y, (pari_sp)x);
    2784    13184301 :   for (i = 2; i < lx; i++)
    2785    13183412 :     if (!gequal0(gel(y, i))) return y;
    2786         889 :   setsigne(y, 0); return y;
    2787             : }
    2788             : 
    2789             : GEN
    2790           0 : normalizepol_approx(GEN x, long lx)
    2791             : {
    2792             :   long i;
    2793           0 :   for (i = lx-1; i>1; i--)
    2794           0 :     if (! gequal0(gel(x,i))) break;
    2795           0 :   stackdummy((pari_sp)(x + lg(x)), (pari_sp)(x + i+1));
    2796           0 :   setlg(x, i+1); setsigne(x, i!=1); return x;
    2797             : }
    2798             : 
    2799             : GEN
    2800   767805020 : normalizepol_lg(GEN x, long lx)
    2801             : {
    2802   767805020 :   long i, LX = 0;
    2803   767805020 :   GEN KEEP = NULL;
    2804             : 
    2805  1018783713 :   for (i = lx-1; i>1; i--)
    2806             :   {
    2807   914825858 :     GEN z = gel(x,i);
    2808   914825858 :     if (! gequal0(z) ) {
    2809   664030884 :       if (!LX) LX = i+1;
    2810   664030884 :       stackdummy((pari_sp)(x + lg(x)), (pari_sp)(x + LX));
    2811   664016038 :       x[0] = evaltyp(t_POL) | _evallg(LX);
    2812   664016038 :       setsigne(x,1); return x;
    2813   250765227 :     } else if (!isexactzero(z)) {
    2814      964259 :       if (!LX) LX = i+1; /* to be kept as leading coeff */
    2815   250017155 :     } else if (!isrationalzero(z))
    2816      832720 :       KEEP = z; /* to be kept iff all other coeffs are exact 0s */
    2817             :   }
    2818   103957855 :   if (!LX) {
    2819   103477570 :     if (KEEP) { /* e.g. Pol(Mod(0,2)) */
    2820      348358 :       gel(x,2) = KEEP;
    2821      348358 :       LX = 3;
    2822             :     } else
    2823   103129212 :       LX = 2; /* Pol(0) */
    2824             :   }
    2825   103957855 :   stackdummy((pari_sp)(x + lg(x)), (pari_sp)(x + LX));
    2826   103877604 :   x[0] = evaltyp(t_POL) | _evallg(LX);
    2827   103877604 :   setsigne(x,0); return x;
    2828             : }
    2829             : 
    2830             : /* normalize polynomial x in place */
    2831             : GEN
    2832    98845837 : normalizepol(GEN x)
    2833             : {
    2834    98845837 :   return normalizepol_lg(x, lg(x));
    2835             : }
    2836             : 
    2837             : int
    2838    74531826 : gsigne(GEN x)
    2839             : {
    2840    74531826 :   switch(typ(x))
    2841             :   {
    2842    74151675 :     case t_INT: case t_REAL: return signe(x);
    2843      379516 :     case t_FRAC: return signe(gel(x,1));
    2844         623 :     case t_QUAD:
    2845             :     {
    2846         623 :       pari_sp av = avma;
    2847         623 :       GEN T = gel(x,1), a = gel(x,2), b = gel(x,3);
    2848             :       long sa, sb;
    2849         623 :       if (signe(gel(T,2)) > 0) break;
    2850         609 :       a = gmul2n(a,1);
    2851         609 :       if (signe(gel(T,3))) a = gadd(a,b);
    2852             :       /* a + b sqrt(D) > 0 ? */
    2853         609 :       sa = gsigne(a);
    2854         609 :       sb = gsigne(b); if (sa == sb) return gc_int(av,sa);
    2855         224 :       if (sa == 0) return gc_int(av,sb);
    2856         217 :       if (sb == 0) return gc_int(av,sa);
    2857             :       /* different signs, take conjugate expression */
    2858         210 :       sb = gsigne(gsub(gsqr(a), gmul(quad_disc(x), gsqr(b))));
    2859         210 :       return gc_int(av, sb*sa);
    2860             :     }
    2861          14 :     case t_INFINITY: return inf_get_sign(x);
    2862             :   }
    2863          12 :   pari_err_TYPE("gsigne",x);
    2864             :   return 0; /* LCOV_EXCL_LINE */
    2865             : }
    2866             : 
    2867             : /*******************************************************************/
    2868             : /*                                                                 */
    2869             : /*                              LISTS                              */
    2870             : /*                                                                 */
    2871             : /*******************************************************************/
    2872             : /* make sure L can hold l elements, at least doubling the previous max number
    2873             :  * of components. */
    2874             : static void
    2875      791252 : ensure_nb(GEN L, long l)
    2876             : {
    2877      791252 :   long nmax = list_nmax(L), i, lw;
    2878             :   GEN v, w;
    2879      791252 :   if (l <= nmax) return;
    2880         679 :   if (nmax)
    2881             :   {
    2882         273 :     nmax <<= 1;
    2883         273 :     if (l > nmax) nmax = l;
    2884         273 :     w = list_data(L); lw = lg(w);
    2885         273 :     v = newblock(nmax+1);
    2886         273 :     v[0] = w[0];
    2887     1045653 :     for (i=1; i < lw; i++) gel(v,i) = gel(w, i);
    2888         273 :     killblock(w);
    2889             :   }
    2890             :   else /* unallocated */
    2891             :   {
    2892         406 :     nmax = 32;
    2893         406 :     if (list_data(L))
    2894           0 :       pari_err(e_MISC, "store list in variable before appending elements");
    2895         406 :     v = newblock(nmax+1);
    2896         406 :     v[0] = evaltyp(t_VEC) | _evallg(1);
    2897             :   }
    2898         679 :   list_data(L) = v;
    2899         679 :   L[1] = evaltyp(list_typ(L))|evallg(nmax);
    2900             : }
    2901             : 
    2902             : void
    2903           7 : listkill(GEN L)
    2904             : {
    2905             : 
    2906           7 :   if (typ(L) != t_LIST) pari_err_TYPE("listkill",L);
    2907           7 :   if (list_nmax(L)) {
    2908           7 :     GEN v = list_data(L);
    2909           7 :     long i, l = lg(v);
    2910          49 :     for (i=1; i<l; i++) gunclone_deep(gel(v,i));
    2911           7 :     killblock(v);
    2912           7 :     L[1] = evaltyp(list_typ(L));
    2913           7 :     list_data(L) = NULL;
    2914             :   }
    2915           7 : }
    2916             : 
    2917             : GEN
    2918        6548 : mklist_typ(long t)
    2919             : {
    2920        6548 :   GEN L = cgetg(3,t_LIST);
    2921        6548 :   L[1] = evaltyp(t);
    2922        6548 :   list_data(L) = NULL; return L;
    2923             : }
    2924             : 
    2925             : GEN
    2926        6492 : mklist(void)
    2927             : {
    2928        6492 :   return mklist_typ(t_LIST_RAW);
    2929             : }
    2930             : 
    2931             : GEN
    2932          49 : mkmap(void)
    2933             : {
    2934          49 :   return mklist_typ(t_LIST_MAP);
    2935             : }
    2936             : 
    2937             : /* return a list with single element x, allocated on stack */
    2938             : GEN
    2939          63 : mklistcopy(GEN x)
    2940             : {
    2941          63 :   GEN y = mklist();
    2942          63 :   list_data(y) = mkveccopy(x);
    2943          63 :   return y;
    2944             : }
    2945             : 
    2946             : GEN
    2947           7 : listcreate_gp(long n)
    2948             : {
    2949           7 :   (void) n; return mklist();
    2950             : }
    2951             : 
    2952             : GEN
    2953      756406 : listput(GEN L, GEN x, long index)
    2954             : {
    2955             :   long l;
    2956             :   GEN z;
    2957             : 
    2958      756406 :   if (index < 0) pari_err_COMPONENT("listput", "<", gen_0, stoi(index));
    2959      756399 :   z = list_data(L);
    2960      756399 :   l = z? lg(z): 1;
    2961             : 
    2962      756399 :   x = gclone(x);
    2963      756399 :   if (!index || index >= l)
    2964             :   {
    2965      756245 :     ensure_nb(L, l);
    2966      756245 :     z = list_data(L); /* it may change ! */
    2967      756245 :     index = l;
    2968      756245 :     l++;
    2969             :   } else
    2970         154 :     gunclone_deep( gel(z, index) );
    2971      756399 :   gel(z,index) = x;
    2972      756399 :   z[0] = evaltyp(t_VEC) | evallg(l); /*must be after gel(z,index) is set*/
    2973      756399 :   return gel(z,index);
    2974             : }
    2975             : 
    2976             : GEN
    2977      705236 : listput0(GEN L, GEN x, long index)
    2978             : {
    2979      705236 :   if (typ(L) != t_LIST || list_typ(L) != t_LIST_RAW)
    2980          14 :     pari_err_TYPE("listput",L);
    2981      705222 :   (void) listput(L, x, index);
    2982      705215 :   return x;
    2983             : }
    2984             : 
    2985             : GEN
    2986       35014 : listinsert(GEN L, GEN x, long index)
    2987             : {
    2988             :   long l, i;
    2989             :   GEN z;
    2990             : 
    2991       35014 :   z = list_data(L); l = z? lg(z): 1;
    2992       35014 :   if (index <= 0) pari_err_COMPONENT("listinsert", "<=", gen_0, stoi(index));
    2993       35007 :   if (index > l) index = l;
    2994       35007 :   ensure_nb(L, l);
    2995       35007 :   BLOCK_SIGINT_START
    2996       35007 :   z = list_data(L);
    2997    87552507 :   for (i=l; i > index; i--) gel(z,i) = gel(z,i-1);
    2998       35007 :   z[0] = evaltyp(t_VEC) | evallg(l+1);
    2999       35007 :   gel(z,index) = gclone(x);
    3000       35007 :   BLOCK_SIGINT_END
    3001       35007 :   return gel(z,index);
    3002             : }
    3003             : 
    3004             : GEN
    3005       35028 : listinsert0(GEN L, GEN x, long index)
    3006             : {
    3007       35028 :   if (typ(L) != t_LIST || list_typ(L) != t_LIST_RAW)
    3008          14 :     pari_err_TYPE("listinsert",L);
    3009       35014 :   (void) listinsert(L, x, index);
    3010       35007 :   return x;
    3011             : }
    3012             : 
    3013             : void
    3014       21917 : listpop(GEN L, long index)
    3015             : {
    3016             :   long l, i;
    3017             :   GEN z;
    3018             : 
    3019       21917 :   if (typ(L) != t_LIST) pari_err_TYPE("listinsert",L);
    3020       21917 :   if (index < 0) pari_err_COMPONENT("listpop", "<", gen_0, stoi(index));
    3021       21917 :   z = list_data(L);
    3022       21917 :   if (!z || (l = lg(z)-1) == 0) return;
    3023             : 
    3024       21903 :   if (!index || index > l) index = l;
    3025       21903 :   BLOCK_SIGINT_START
    3026       21903 :   gunclone_deep( gel(z, index) );
    3027       21903 :   z[0] = evaltyp(t_VEC) | _evallg(l);
    3028       21910 :   for (i=index; i < l; i++) z[i] = z[i+1];
    3029       21903 :   BLOCK_SIGINT_END
    3030             : }
    3031             : 
    3032             : void
    3033          56 : listpop0(GEN L, long index)
    3034             : {
    3035          56 :   if (typ(L) != t_LIST || list_typ(L) != t_LIST_RAW)
    3036          14 :     pari_err_TYPE("listpop",L);
    3037          42 :   listpop(L, index);
    3038          42 : }
    3039             : 
    3040             : /* return a copy fully allocated on stack. gclone from changevalue is
    3041             :  * supposed to malloc() it */
    3042             : GEN
    3043        5580 : gtolist(GEN x)
    3044             : {
    3045             :   GEN y;
    3046             : 
    3047        5580 :   if (!x) return mklist();
    3048         370 :   switch(typ(x))
    3049             :   {
    3050         300 :     case t_VEC: case t_COL:
    3051         300 :       y = mklist();
    3052         300 :       if (lg(x) == 1) return y;
    3053         279 :       list_data(y) = gcopy(x);
    3054         279 :       settyp(list_data(y), t_VEC);
    3055         279 :       return y;
    3056           7 :     case t_LIST:
    3057           7 :       y = mklist();
    3058           7 :       list_data(y) = list_data(x)? gcopy(list_data(x)): NULL;
    3059           7 :       return y;
    3060          63 :     default:
    3061          63 :       return mklistcopy(x);
    3062             :   }
    3063             : }
    3064             : 
    3065             : void
    3066          21 : listsort(GEN L, long flag)
    3067             : {
    3068             :   long i, l;
    3069          21 :   pari_sp av = avma;
    3070             :   GEN perm, v, vnew;
    3071             : 
    3072          21 :   if (typ(L) != t_LIST) pari_err_TYPE("listsort",L);
    3073          21 :   v = list_data(L); l = v? lg(v): 1;
    3074          21 :   if (l < 3) return;
    3075          21 :   if (flag)
    3076             :   {
    3077             :     long lnew;
    3078          14 :     perm = gen_indexsort_uniq(L, (void*)&cmp_universal, cmp_nodata);
    3079          14 :     lnew = lg(perm); /* may have changed since 'uniq' */
    3080          14 :     vnew = cgetg(lnew,t_VEC);
    3081          56 :     for (i=1; i<lnew; i++) {
    3082          42 :       long c = perm[i];
    3083          42 :       gel(vnew,i) = gel(v,c);
    3084          42 :       gel(v,c) = NULL;
    3085             :     }
    3086          14 :     if (l != lnew) { /* was shortened */
    3087         105 :       for (i=1; i<l; i++)
    3088          91 :         if (gel(v,i)) gunclone_deep(gel(v,i));
    3089          14 :       l = lnew;
    3090             :     }
    3091             :   }
    3092             :   else
    3093             :   {
    3094           7 :     perm = gen_indexsort(L, (void*)&cmp_universal, cmp_nodata);
    3095           7 :     vnew = cgetg(l,t_VEC);
    3096          63 :     for (i=1; i<l; i++) gel(vnew,i) = gel(v,perm[i]);
    3097             :   }
    3098         119 :   for (i=1; i<l; i++) gel(v,i) = gel(vnew,i);
    3099          21 :   v[0] = vnew[0]; set_avma(av);
    3100             : }

Generated by: LCOV version 1.16