Code coverage tests

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

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

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

LCOV - code coverage report
Current view: top level - basemath - gen2.c (source / functions) Hit Total Coverage
Test: PARI/GP v2.12.0 lcov report (development 23339-b1c33c51a) Lines: 1322 1497 88.3 %
Date: 2018-12-11 05:41:34 Functions: 137 147 93.2 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : /* Copyright (C) 2000  The PARI group.
       2             : 
       3             : This file is part of the PARI/GP package.
       4             : 
       5             : PARI/GP is free software; you can redistribute it and/or modify it under the
       6             : terms of the GNU General Public License as published by the Free Software
       7             : Foundation. It is distributed in the hope that it will be useful, but WITHOUT
       8             : ANY WARRANTY WHATSOEVER.
       9             : 
      10             : Check the License for details. You should have received a copy of it, along
      11             : with the package; see the file 'COPYING'. If not, write to the Free Software
      12             : Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. */
      13             : 
      14             : /********************************************************************/
      15             : /**                                                                **/
      16             : /**                      GENERIC OPERATIONS                        **/
      17             : /**                        (second part)                           **/
      18             : /**                                                                **/
      19             : /********************************************************************/
      20             : #include "pari.h"
      21             : #include "paripriv.h"
      22             : 
      23             : /*********************************************************************/
      24             : /**                                                                 **/
      25             : /**                MAP FUNCTIONS WITH GIVEN PROTOTYPES              **/
      26             : /**                                                                 **/
      27             : /*********************************************************************/
      28             : GEN
      29         140 : map_proto_G(GEN (*f)(GEN), GEN x)
      30             : {
      31         140 :   if (is_matvec_t(typ(x)))
      32             :   {
      33             :     long lx, i;
      34           0 :     GEN y = cgetg_copy(x, &lx);
      35           0 :     for (i=1; i<lx; i++) gel(y,i) = map_proto_G(f, gel(x,i));
      36           0 :     return y;
      37             :   }
      38         140 :   return f(x);
      39             : }
      40             : 
      41             : GEN
      42     2206783 : map_proto_lG(long (*f)(GEN), GEN x)
      43             : {
      44     2206783 :   if (is_matvec_t(typ(x)))
      45             :   {
      46             :     long lx, i;
      47          28 :     GEN y = cgetg_copy(x, &lx);
      48          28 :     for (i=1; i<lx; i++) gel(y,i) = map_proto_lG(f, gel(x,i));
      49          28 :     return y;
      50             :   }
      51     2198954 :   return stoi(f(x));
      52             : }
      53             : 
      54             : GEN
      55         126 : map_proto_lGL(long (*f)(GEN,long), GEN x, long y)
      56             : {
      57         126 :   if (is_matvec_t(typ(x)))
      58             :   {
      59             :     long l, i;
      60           7 :     GEN t = cgetg_copy(x, &l);
      61           7 :     for (i=1; i<l; i++) gel(t,i) = map_proto_lGL(f,gel(x,i),y);
      62           7 :     return t;
      63             :   }
      64         119 :   return stoi(f(x,y));
      65             : }
      66             : 
      67             : static GEN
      68      610543 : _domul(void *data, GEN x, GEN y)
      69             : {
      70      610543 :   GEN (*mul)(GEN,GEN)=(GEN (*)(GEN,GEN)) data;
      71      610543 :   return mul(x,y);
      72             : }
      73             : 
      74             : GEN
      75      556829 : gassoc_proto(GEN (*f)(GEN,GEN), GEN x, GEN y)
      76             : {
      77      556829 :   if (!y)
      78             :   {
      79      556829 :     pari_sp av = avma;
      80      556829 :     switch(typ(x))
      81             :     {
      82             :       case t_LIST:
      83          21 :         x = list_data(x); if (!x) return gen_1;
      84             :       case t_VEC:
      85      556815 :       case t_COL: break;
      86           7 :       default: pari_err_TYPE("association",x);
      87             :     }
      88      556815 :     return gerepileupto(av, gen_product(x, (void *)f, _domul));
      89             : 
      90             :   }
      91           0 :   return f(x,y);
      92             : }
      93             : /*******************************************************************/
      94             : /*                                                                 */
      95             : /*                    CREATION OF A P-ADIC GEN                     */
      96             : /*                                                                 */
      97             : /*******************************************************************/
      98             : GEN
      99     1580262 : cgetp(GEN x)
     100             : {
     101     1580262 :   GEN y = cgetg(5,t_PADIC);
     102     1580261 :   y[1] = (x[1]&PRECPBITS) | _evalvalp(0);
     103     1580261 :   gel(y,2) = icopy(gel(x,2));
     104     1580270 :   gel(y,3) = icopy(gel(x,3));
     105     1580270 :   gel(y,4) = cgeti(lgefint(gel(x,3))); return y;
     106             : }
     107             : 
     108             : /*******************************************************************/
     109             : /*                                                                 */
     110             : /*                            SIZES                                */
     111             : /*                                                                 */
     112             : /*******************************************************************/
     113             : 
     114             : long
     115     4982824 : glength(GEN x)
     116             : {
     117     4982824 :   long tx = typ(x);
     118     4982824 :   switch(tx)
     119             :   {
     120          84 :     case t_INT:  return lgefint(x)-2;
     121             :     case t_LIST: {
     122          21 :       GEN L = list_data(x);
     123          21 :       return L? lg(L)-1: 0;
     124             :     }
     125          14 :     case t_REAL: return signe(x)? lg(x)-2: 0;
     126           7 :     case t_STR:  return strlen( GSTR(x) );
     127          91 :     case t_VECSMALL: return lg(x)-1;
     128             :   }
     129     4982607 :   return lg(x) - lontyp[tx];
     130             : }
     131             : 
     132             : GEN
     133         119 : matsize(GEN x)
     134             : {
     135         119 :   long L = lg(x) - 1;
     136         119 :   switch(typ(x))
     137             :   {
     138           7 :     case t_VEC: return mkvec2s(1, L);
     139           7 :     case t_COL: return mkvec2s(L, 1);
     140          98 :     case t_MAT: return mkvec2s(L? nbrows(x): 0, L);
     141             :   }
     142           7 :   pari_err_TYPE("matsize",x);
     143             :   return NULL; /* LCOV_EXCL_LINE */
     144             : }
     145             : 
     146             : /*******************************************************************/
     147             : /*                                                                 */
     148             : /*                 CONVERSION GEN --> long                         */
     149             : /*                                                                 */
     150             : /*******************************************************************/
     151             : 
     152             : long
     153          77 : gtolong(GEN x)
     154             : {
     155          77 :   switch(typ(x))
     156             :   {
     157             :     case t_INT:
     158          42 :       return itos(x);
     159             :     case t_REAL:
     160           7 :       return (long)(rtodbl(x) + 0.5);
     161             :     case t_FRAC:
     162           7 :     { pari_sp av = avma; return gc_long(av, itos(ground(x))); }
     163             :     case t_COMPLEX:
     164           7 :       if (gequal0(gel(x,2))) return gtolong(gel(x,1)); break;
     165             :     case t_QUAD:
     166           7 :       if (gequal0(gel(x,3))) return gtolong(gel(x,2)); break;
     167             :   }
     168           7 :   pari_err_TYPE("gtolong",x);
     169             :   return 0; /* LCOV_EXCL_LINE */
     170             : }
     171             : 
     172             : /*******************************************************************/
     173             : /*                                                                 */
     174             : /*                         COMPARISONS                             */
     175             : /*                                                                 */
     176             : /*******************************************************************/
     177             : int
     178   167339567 : isexactzero(GEN g)
     179             : {
     180             :   long i, lx;
     181   167339567 :   switch (typ(g))
     182             :   {
     183             :     case t_INT:
     184   127045856 :       return !signe(g);
     185             :     case t_INTMOD:
     186     1061549 :       return !signe(gel(g,2));
     187             :     case t_COMPLEX:
     188     2897080 :       return isexactzero(gel(g,1)) && isexactzero(gel(g,2));
     189             :     case t_FFELT:
     190     8105303 :       return FF_equal0(g);
     191             :     case t_QUAD:
     192         490 :       return isexactzero(gel(g,2)) && isexactzero(gel(g,3));
     193             :     case t_POLMOD:
     194      689857 :       return isexactzero(gel(g,2));
     195             :     case t_POL:
     196    11506390 :       lx = lg(g); /* cater for Mod(0,2)*x^0 */
     197    11506390 :       return lx == 2 || (lx == 3 && isexactzero(gel(g,2)));
     198             :     case t_RFRAC:
     199      461087 :       return isexactzero(gel(g,1)); /* may occur: Mod(0,2)/x */
     200             :     case t_VEC: case t_COL: case t_MAT:
     201         350 :       for (i=lg(g)-1; i; i--)
     202         252 :         if (!isexactzero(gel(g,i))) return 0;
     203          98 :       return 1;
     204             :   }
     205    15571843 :   return 0;
     206             : }
     207             : GEN
     208    56330295 : gisexactzero(GEN g)
     209             : {
     210             :   long i, lx;
     211             :   GEN a, b;
     212    56330295 :   switch (typ(g))
     213             :   {
     214             :     case t_INT:
     215    16419458 :       return !signe(g)? g: NULL;
     216             :     case t_INTMOD:
     217    10419444 :       return !signe(gel(g,2))? g: NULL;
     218             :     case t_COMPLEX:
     219        2562 :       a = gisexactzero(gel(g,1)); if (!a) return NULL;
     220         602 :       b = gisexactzero(gel(g,2)); if (!b) return NULL;
     221           0 :       return ggcd(a,b);
     222             :     case t_FFELT:
     223       15365 :       return FF_equal0(g)? g: NULL;
     224             :     case t_QUAD:
     225         518 :       a = gisexactzero(gel(g,2)); if (!a) return NULL;
     226          77 :       b = gisexactzero(gel(g,3)); if (!b) return NULL;
     227           7 :       return ggcd(a,b);
     228             :     case t_POLMOD:
     229       45339 :       return gisexactzero(gel(g,2));
     230             :     case t_POL:
     231    28124809 :       lx = lg(g); /* cater for Mod(0,2)*x^0 */
     232    28124809 :       if (lx == 2) return gen_0;
     233    22790891 :       if (lx == 3) return gisexactzero(gel(g,2));
     234    19025436 :       return NULL;
     235             :     case t_RFRAC:
     236     1193898 :       return gisexactzero(gel(g,1)); /* may occur: Mod(0,2)/x */
     237             :     case t_VEC: case t_COL: case t_MAT:
     238           0 :       a = gen_0;
     239           0 :       for (i=lg(g)-1; i; i--)
     240             :       {
     241           0 :         b = gisexactzero(gel(g,i));
     242           0 :         if (!b) return NULL;
     243           0 :         a = ggcd(a, b);
     244             :       }
     245           0 :       return a;
     246             :   }
     247      108902 :   return NULL;
     248             : }
     249             : 
     250             : int
     251   196827826 : isrationalzero(GEN g)
     252             : {
     253             :   long i;
     254   196827826 :   switch (typ(g))
     255             :   {
     256             :     case t_INT:
     257   119074671 :       return !signe(g);
     258             :     case t_COMPLEX:
     259     7462378 :       return isintzero(gel(g,1)) && isintzero(gel(g,2));
     260             :     case t_QUAD:
     261         952 :       return isintzero(gel(g,2)) && isintzero(gel(g,3));
     262             :     case t_POLMOD:
     263     2141474 :       return isrationalzero(gel(g,2));
     264    22812394 :     case t_POL: return lg(g) == 2;
     265             :     case t_VEC: case t_COL: case t_MAT:
     266         252 :       for (i=lg(g)-1; i; i--)
     267         168 :         if (!isrationalzero(gel(g,i))) return 0;
     268          84 :       return 1;
     269             :   }
     270    45335873 :   return 0;
     271             : }
     272             : 
     273             : int
     274   618285115 : gequal0(GEN x)
     275             : {
     276   618285115 :   switch(typ(x))
     277             :   {
     278             :     case t_INT: case t_REAL: case t_POL: case t_SER:
     279   563395675 :       return !signe(x);
     280             : 
     281             :     case t_INTMOD:
     282     3471732 :       return !signe(gel(x,2));
     283             : 
     284             :     case t_FFELT:
     285      551268 :       return FF_equal0(x);
     286             : 
     287             :     case t_COMPLEX:
     288             :      /* is 0 iff norm(x) would be 0 (can happen with Re(x) and Im(x) != 0
     289             :       * only if Re(x) and Im(x) are of type t_REAL). See mp.c:addrr().
     290             :       */
     291    20425789 :       if (gequal0(gel(x,1)))
     292             :       {
     293     4970675 :         if (gequal0(gel(x,2))) return 1;
     294     4737331 :         if (typ(gel(x,1))!=t_REAL || typ(gel(x,2))!=t_REAL) return 0;
     295       67938 :         return (expo(gel(x,1))>=expo(gel(x,2)));
     296             :       }
     297    15455114 :       if (gequal0(gel(x,2)))
     298             :       {
     299      476064 :         if (typ(gel(x,1))!=t_REAL || typ(gel(x,2))!=t_REAL) return 0;
     300      381844 :         return (expo(gel(x,2))>=expo(gel(x,1)));
     301             :       }
     302    14979050 :       return 0;
     303             : 
     304             :     case t_PADIC:
     305      327263 :       return !signe(gel(x,4));
     306             : 
     307             :     case t_QUAD:
     308        1008 :       return gequal0(gel(x,2)) && gequal0(gel(x,3));
     309             : 
     310             :     case t_POLMOD:
     311     9910681 :       return gequal0(gel(x,2));
     312             : 
     313             :     case t_RFRAC:
     314     6012442 :       return gequal0(gel(x,1));
     315             : 
     316             :     case t_VEC: case t_COL: case t_MAT:
     317             :     {
     318             :       long i;
     319     7328619 :       for (i=lg(x)-1; i; i--)
     320     4330650 :         if (!gequal0(gel(x,i))) return 0;
     321     2997969 :       return 1;
     322             :     }
     323             :   }
     324     9941634 :   return 0;
     325             : }
     326             : 
     327             : /* x a t_POL or t_SER, considered as having valuation v; let X(t) = t^(-v) x(t)
     328             :  * return 1 (true) if coeff(X,i) = 0 for all i != 0 and test(coeff(X, 0))
     329             :  * is true. Return 0 (false) otherwise, or if x == 0 */
     330             : static int
     331    13192372 : is_monomial_test(GEN x, long v, int(*test)(GEN))
     332             : {
     333             :   long d, i, l;
     334    13192372 :   if (!signe(x)) return (typ(x) == t_SER && v <= 0);
     335    13126979 :   if (v > 0) return 0;
     336    13126965 :   l = lg(x); d = 2-v;
     337    13126965 :   if (l <= d) return 0;
     338             :   /* 2 <= d < l */
     339    13126965 :   if (!test(gel(x,d))) return 0;
     340     3981062 :   for (i = 2; i < d; i++)
     341          14 :     if (!gequal0(gel(x,i))) return 0;
     342     4398926 :   for (i = d+1; i < l; i++)
     343     1979208 :     if (!gequal0(gel(x,i))) return 0;
     344     2419718 :   return 1;
     345             : }
     346             : static int
     347        2058 : col_test(GEN x, int(*test)(GEN))
     348             : {
     349        2058 :   long i, l = lg(x);
     350        2058 :   if (l == 1 || !test(gel(x,1))) return 0;
     351          42 :   for (i = 2; i < l; i++)
     352          21 :     if (!gequal0(gel(x,i))) return 0;
     353          21 :   return 1;
     354             : }
     355             : static int
     356       16184 : mat_test(GEN x, int(*test)(GEN))
     357             : {
     358       16184 :   long i, j, l = lg(x);
     359       16184 :   if (l == 1) return 1;
     360       16170 :   if (l != lgcols(x)) return 0;
     361       51240 :   for (i = 1; i < l; i++)
     362      134078 :     for (j = 1; j < l; j++)
     363       99008 :       if (i == j) {
     364       35133 :         if (!test(gcoeff(x,i,i))) return 0;
     365             :       } else {
     366       63875 :         if (!gequal0(gcoeff(x,i,j))) return 0;
     367             :       }
     368       16107 :   return 1;
     369             : }
     370             : 
     371             : /* returns 1 whenever x = 1, and 0 otherwise */
     372             : int
     373   155454573 : gequal1(GEN x)
     374             : {
     375   155454573 :   switch(typ(x))
     376             :   {
     377             :     case t_INT:
     378   139812515 :       return equali1(x);
     379             : 
     380             :     case t_REAL:
     381             :     {
     382       67046 :       long s = signe(x);
     383       67046 :       if (!s) return expo(x) >= 0;
     384       66969 :       return s > 0 ? absrnz_equal1(x): 0;
     385             :     }
     386             :     case t_INTMOD:
     387      564564 :       return is_pm1(gel(x,2)) || is_pm1(gel(x,1));
     388             :     case t_POLMOD:
     389      334778 :       return gequal1(gel(x,2)) || gequal1(gel(x,1));
     390             : 
     391             :     case t_FFELT:
     392       15673 :       return FF_equal1(x);
     393             : 
     394             :     case t_FRAC:
     395      389461 :       return 0;
     396             : 
     397             :     case t_COMPLEX:
     398       19073 :       return gequal1(gel(x,1)) && gequal0(gel(x,2));
     399             : 
     400             :     case t_PADIC:
     401        9079 :       return !valp(x) && gequal1(gel(x,4));
     402             : 
     403             :     case t_QUAD:
     404          35 :       return gequal1(gel(x,2)) && gequal0(gel(x,3));
     405             : 
     406    13192162 :     case t_POL: return is_monomial_test(x, 0, &gequal1);
     407          98 :     case t_SER: return is_monomial_test(x, valp(x), &gequal1);
     408             : 
     409     1031924 :     case t_RFRAC: return gequal(gel(x,1), gel(x,2));
     410        2016 :     case t_COL: return col_test(x, &gequal1);
     411       16135 :     case t_MAT: return mat_test(x, &gequal1);
     412             :   }
     413          14 :   return 0;
     414             : }
     415             : 
     416             : /* returns 1 whenever the x = -1, 0 otherwise */
     417             : int
     418      112752 : gequalm1(GEN x)
     419             : {
     420             :   pari_sp av;
     421             :   GEN p1;
     422             : 
     423      112752 :   switch(typ(x))
     424             :   {
     425             :     case t_INT:
     426      104143 :       return equalim1(x);
     427             : 
     428             :     case t_REAL:
     429             :     {
     430        4112 :       long s = signe(x);
     431        4112 :       if (!s) return expo(x) >= 0;
     432        4112 :       return s < 0 ? absrnz_equal1(x): 0;
     433             :     }
     434             :     case t_INTMOD:
     435          21 :       av = avma; return gc_bool(av, equalii(addui(1,gel(x,2)), gel(x,1)));
     436             : 
     437             :     case t_FRAC:
     438          21 :       return 0;
     439             : 
     440             :     case t_FFELT:
     441          42 :       return FF_equalm1(x);
     442             : 
     443             :     case t_COMPLEX:
     444        4126 :       return gequalm1(gel(x,1)) && gequal0(gel(x,2));
     445             : 
     446             :     case t_QUAD:
     447           7 :       return gequalm1(gel(x,2)) && gequal0(gel(x,3));
     448             : 
     449             :     case t_PADIC:
     450           7 :       av = avma; return gc_bool(av, equalii(addui(1,gel(x,4)), gel(x,3)));
     451             : 
     452             :     case t_POLMOD:
     453          35 :       av = avma; p1 = gaddgs(gel(x,2), 1);
     454          35 :       return gc_bool(av, gequal0(p1) || gequal(p1,gel(x,1)));
     455             : 
     456          35 :     case t_POL: return is_monomial_test(x, 0, &gequalm1);
     457          77 :     case t_SER: return is_monomial_test(x, valp(x), &gequalm1);
     458             : 
     459             :     case t_RFRAC:
     460          21 :       av = avma; return gc_bool(av, gequal(gel(x,1), gneg_i(gel(x,2))));
     461          42 :     case t_COL: return col_test(x, &gequalm1);
     462          49 :     case t_MAT: return mat_test(x, &gequalm1);
     463             :   }
     464          14 :   return 0;
     465             : }
     466             : 
     467             : int
     468     2364760 : gequalX(GEN x) { return typ(x) == t_POL && lg(x) == 4
     469     2347407 :                       && isintzero(gel(x,2)) && isint1(gel(x,3)); }
     470             : 
     471             : static int
     472         476 : cmp_str(const char *x, const char *y)
     473             : {
     474         476 :   int f = strcmp(x, y);
     475             :   return f > 0? 1
     476         476 :               : f? -1: 0;
     477             : }
     478             : 
     479             : static int
     480    27486405 : cmp_universal_rec(GEN x, GEN y, long i0)
     481             : {
     482    27486405 :   long i, lx = lg(x), ly = lg(y);
     483    27486405 :   if (lx < ly) return -1;
     484    27484585 :   if (lx > ly) return 1;
     485    41755219 :   for (i = i0; i < lx; i++)
     486             :   {
     487    35580135 :     int f = cmp_universal(gel(x,i), gel(y,i));
     488    35580135 :     if (f) return f;
     489             :   }
     490     6175084 :   return 0;
     491             : }
     492             : /* Universal "meaningless" comparison function. Transitive, returns 0 iff
     493             :  * gidentical(x,y) */
     494             : int
     495    48843480 : cmp_universal(GEN x, GEN y)
     496             : {
     497    48843480 :   long lx, ly, i, tx = typ(x), ty = typ(y);
     498             : 
     499    48843480 :   if (tx < ty) return -1;
     500    48832279 :   if (ty < tx) return 1;
     501    48826113 :   switch(tx)
     502             :   {
     503    20399433 :     case t_INT: return cmpii(x,y);
     504         455 :     case t_STR: return cmp_str(GSTR(x),GSTR(y));
     505             :     case t_REAL:
     506             :     case t_VECSMALL:
     507      939764 :       lx = lg(x);
     508      939764 :       ly = lg(y);
     509      939764 :       if (lx < ly) return -1;
     510      888335 :       if (lx > ly) return 1;
     511     3580802 :       for (i = 1; i < lx; i++)
     512             :       {
     513     3473163 :         if (x[i] < y[i]) return -1;
     514     3088709 :         if (x[i] > y[i]) return 1;
     515             :       }
     516      107639 :       return 0;
     517             : 
     518             :     case t_POL:
     519             :     case t_SER:
     520             :     case t_FFELT:
     521             :     case t_CLOSURE:
     522      899074 :       if (x[1] < y[1]) return -1;
     523      899046 :       if (x[1] > y[1]) return 1;
     524      899018 :       return cmp_universal_rec(x, y, 2);
     525             : 
     526             :     case t_LIST:
     527             :       {
     528          35 :         long tx = list_typ(x), ty = list_typ(y);
     529             :         GEN vx, vy;
     530             :         pari_sp av;
     531          35 :         if (tx < ty) return -1;
     532          35 :         if (tx > ty) return 1;
     533          35 :         vx = list_data(x);
     534          35 :         vy = list_data(y);
     535          35 :         if (!vx) return vy? -1: 0;
     536          35 :         if (!vy) return 1;
     537          35 :         av = avma;
     538          35 :         if (tx == t_LIST_MAP)
     539             :         {
     540          14 :           vx = maptomat_shallow(x);
     541          14 :           vy = maptomat_shallow(y);
     542             :         }
     543          35 :         return gc_int(av, cmp_universal_rec(vx, vy, 1));
     544             :       }
     545             :     default:
     546    26587352 :       return cmp_universal_rec(x, y, lontyp[tx]);
     547             :   }
     548             : }
     549             : 
     550             : static int
     551       81370 : cmpfrac(GEN x, GEN y)
     552             : {
     553       81370 :   pari_sp av = avma;
     554       81370 :   GEN a = gel(x,1), b = gel(x,2);
     555       81370 :   GEN c = gel(y,1), d = gel(y,2);
     556       81370 :   return gc_bool(av, cmpii(mulii(a, d), mulii(b, c)));
     557             : }
     558             : static int
     559        6706 : cmpifrac(GEN a, GEN y)
     560             : {
     561        6706 :   pari_sp av = avma;
     562        6706 :   GEN c = gel(y,1), d = gel(y,2);
     563        6706 :   return gc_int(av, cmpii(mulii(a, d), c));
     564             : }
     565             : static int
     566       64862 : cmprfrac(GEN a, GEN y)
     567             : {
     568       64862 :   pari_sp av = avma;
     569       64862 :   GEN c = gel(y,1), d = gel(y,2);
     570       64862 :   return gc_int(av, cmpri(mulri(a, d), c));
     571             : }
     572             : static int
     573          63 : cmpgen(GEN x, GEN y)
     574             : {
     575          63 :   pari_sp av = avma;
     576          63 :   return gc_int(av, gsigne(gsub(x,y)));
     577             : }
     578             : 
     579             : /* returns the sign of x - y when it makes sense. 0 otherwise */
     580             : int
     581   159471575 : gcmp(GEN x, GEN y)
     582             : {
     583   159471575 :   long tx = typ(x), ty = typ(y);
     584             : 
     585   159471575 :   if (tx == ty) /* generic case */
     586   158997941 :     switch(tx)
     587             :     {
     588    80361087 :       case t_INT:  return cmpii(x, y);
     589    78548676 :       case t_REAL: return cmprr(x, y);
     590       81370 :       case t_FRAC: return cmpfrac(x, y);
     591          14 :       case t_QUAD: return cmpgen(x, y);
     592          21 :       case t_STR:  return cmp_str(GSTR(x), GSTR(y));
     593             :       case t_INFINITY:
     594             :       {
     595       16023 :         long sx = inf_get_sign(x), sy = inf_get_sign(y);
     596       16023 :         if (sx < sy) return -1;
     597          21 :         if (sx > sy) return 1;
     598          14 :         return 0;
     599             :       }
     600             :     }
     601      464384 :   if (ty == t_INFINITY) return -inf_get_sign(y);
     602      405030 :   switch(tx)
     603             :   {
     604             :     case t_INT:
     605       26254 :       switch(ty)
     606             :       {
     607       23041 :         case t_REAL: return cmpir(x, y);
     608        3199 :         case t_FRAC: return cmpifrac(x, y);
     609           7 :         case t_QUAD: return cmpgen(x, y);
     610             :       }
     611           7 :       break;
     612             :     case t_REAL:
     613      319400 :       switch(ty)
     614             :       {
     615      278345 :         case t_INT:  return cmpri(x, y);
     616       41041 :         case t_FRAC: return cmprfrac(x, y);
     617           7 :         case t_QUAD: return cmpgen(x, y);
     618             :       }
     619           7 :       break;
     620             :     case t_FRAC:
     621       27342 :       switch(ty)
     622             :       {
     623        3507 :         case t_INT:  return -cmpifrac(y, x);
     624       23821 :         case t_REAL: return -cmprfrac(y, x);
     625           7 :         case t_QUAD: return cmpgen(x, y);
     626             :       }
     627           7 :       break;
     628             :     case t_QUAD:
     629          28 :       return cmpgen(x, y);
     630       31999 :     case t_INFINITY: return inf_get_sign(x);
     631             :   }
     632          28 :   pari_err_TYPE2("comparison",x,y);
     633             :   return 0;/*LCOV_EXCL_LINE*/
     634             : }
     635             : 
     636             : int
     637       56384 : gcmpsg(long s, GEN y)
     638             : {
     639       56384 :   switch(typ(y))
     640             :   {
     641        7273 :     case t_INT:  return cmpsi(s,y);
     642       45359 :     case t_REAL: return cmpsr(s,y);
     643             :     case t_FRAC: {
     644        3752 :       pari_sp av = avma;
     645        3752 :       return gc_int(av, cmpii(mulsi(s,gel(y,2)), gel(y,1)));
     646             :     }
     647             :     case t_QUAD: {
     648           0 :       pari_sp av = avma;
     649           0 :       return gc_int(av, gsigne(gsubsg(s, y)));
     650             :     }
     651           0 :     case t_INFINITY: return -inf_get_sign(y);
     652             :   }
     653           0 :   pari_err_TYPE2("comparison",stoi(s),y);
     654             :   return 0; /* LCOV_EXCL_LINE */
     655             : }
     656             : 
     657             : static long
     658     6259697 : roughtype(GEN x)
     659             : {
     660     6259697 :   switch(typ(x))
     661             :   {
     662        2100 :     case t_MAT: return t_MAT;
     663       14756 :     case t_VEC: case t_COL: return t_VEC;
     664     6198300 :     case t_VECSMALL: return t_VECSMALL;
     665       44541 :     default: return t_INT;
     666             :   }
     667             : }
     668             : 
     669             : static int lexcmpsg(long x, GEN y);
     670          42 : static int lexcmpgs(GEN x, long y) { return -lexcmpsg(y,x); }
     671             : /* lexcmp(stoi(x),y), y t_VEC/t_COL/t_MAT */
     672             : static int
     673          21 : lexcmp_s_matvec(long x, GEN y)
     674             : {
     675             :   int fl;
     676          21 :   if (lg(y)==1) return 1;
     677          14 :   fl = lexcmpsg(x,gel(y,1));
     678          14 :   if (fl) return fl;
     679           7 :   return -1;
     680             : }
     681             : /* x a scalar, y a t_VEC/t_COL/t_MAT */
     682             : static int
     683         357 : lexcmp_scal_matvec(GEN x, GEN y)
     684             : {
     685             :   int fl;
     686         357 :   if (lg(y)==1) return 1;
     687         357 :   fl = lexcmp(x,gel(y,1));
     688         357 :   if (fl) return fl;
     689           7 :   return -1;
     690             : }
     691             : /* x a scalar, y a t_VECSMALL */
     692             : static int
     693          42 : lexcmp_scal_vecsmall(GEN x, GEN y)
     694             : {
     695             :   int fl;
     696          42 :   if (lg(y)==1) return 1;
     697          42 :   fl = lexcmpgs(x, y[1]);
     698          42 :   if (fl) return fl;
     699           0 :   return -1;
     700             : }
     701             : 
     702             : /* tx = ty = t_MAT, or x and y are both vect_t */
     703             : static int
     704        8162 : lexcmp_similar(GEN x, GEN y)
     705             : {
     706        8162 :   long i, lx = lg(x), ly = lg(y), l = minss(lx,ly);
     707       15827 :   for (i=1; i<l; i++)
     708             :   {
     709       14266 :     int fl = lexcmp(gel(x,i),gel(y,i));
     710       14266 :     if (fl) return fl;
     711             :   }
     712        1561 :   if (lx == ly) return 0;
     713          35 :   return (lx < ly)? -1 : 1;
     714             : }
     715             : /* x a t_VECSMALL, y a t_VEC/t_COL ~ lexcmp_similar */
     716             : static int
     717         154 : lexcmp_vecsmall_vec(GEN x, GEN y)
     718             : {
     719         154 :   long i, lx = lg(x), ly = lg(y), l = minss(lx,ly);
     720         343 :   for (i=1; i<l; i++)
     721             :   {
     722         287 :     int fl = lexcmpsg(x[i], gel(y,i));
     723         287 :     if (fl) return fl;
     724             :   }
     725          56 :   if (lx == ly) return 0;
     726          21 :   return (lx < ly)? -1 : 1;
     727             : }
     728             : 
     729             : /* x t_VEC/t_COL, y t_MAT */
     730             : static int
     731          98 : lexcmp_vec_mat(GEN x, GEN y)
     732             : {
     733             :   int fl;
     734          98 :   if (lg(x)==1) return -1;
     735          98 :   if (lg(y)==1) return 1;
     736          98 :   fl = lexcmp_similar(x,gel(y,1));
     737          98 :   if (fl) return fl;
     738           7 :   return -1;
     739             : }
     740             : /* x t_VECSMALl, y t_MAT ~ lexcmp_vec_mat */
     741             : static int
     742          42 : lexcmp_vecsmall_mat(GEN x, GEN y)
     743             : {
     744             :   int fl;
     745          42 :   if (lg(x)==1) return -1;
     746          42 :   if (lg(y)==1) return 1;
     747          42 :   fl = lexcmp_vecsmall_vec(x, gel(y,1));
     748          42 :   if (fl) return fl;
     749           0 :   return -1;
     750             : }
     751             : 
     752             : /* x a t_VECSMALL, not y */
     753             : static int
     754         196 : lexcmp_vecsmall_other(GEN x, GEN y, long ty)
     755             : {
     756         196 :   switch(ty)
     757             :   {
     758          42 :     case t_MAT: return lexcmp_vecsmall_mat(x, y);
     759         112 :     case t_VEC: return lexcmp_vecsmall_vec(x, y);
     760          42 :     default: return -lexcmp_scal_vecsmall(y, x); /*y scalar*/
     761             :   }
     762             : }
     763             : 
     764             : /* lexcmp(stoi(s), y) */
     765             : static int
     766         343 : lexcmpsg(long x, GEN y)
     767             : {
     768         343 :   switch(roughtype(y))
     769             :   {
     770             :     case t_MAT:
     771             :     case t_VEC:
     772          21 :       return lexcmp_s_matvec(x,y);
     773             :     case t_VECSMALL: /* ~ lexcmp_scal_matvec */
     774          14 :       if (lg(y)==1) return 1;
     775           7 :       return (x > y[1])? 1: -1;
     776         308 :     default: return gcmpsg(x,y);
     777             :   }
     778             : }
     779             : 
     780             : /* as gcmp for vector/matrices, using lexicographic ordering on components */
     781             : static int
     782     3129677 : lexcmp_i(GEN x, GEN y)
     783             : {
     784     3129677 :   const long tx = roughtype(x), ty = roughtype(y);
     785     3129677 :   if (tx == ty)
     786     3129026 :     switch(tx)
     787             :     {
     788             :       case t_MAT:
     789             :       case t_VEC:
     790        8064 :         return lexcmp_similar(x,y);
     791             :       case t_VECSMALL:
     792     3099045 :         return vecsmall_lexcmp(x,y);
     793             :       default:
     794       21917 :         return gcmp(x,y);
     795             :     }
     796         651 :   if (tx == t_VECSMALL) return  lexcmp_vecsmall_other(x,y,ty);
     797         518 :   if (ty == t_VECSMALL) return -lexcmp_vecsmall_other(y,x,tx);
     798             : 
     799         455 :   if (tx == t_INT) return  lexcmp_scal_matvec(x,y); /*scalar*/
     800         203 :   if (ty == t_INT) return -lexcmp_scal_matvec(y,x);
     801             : 
     802          98 :   if (ty==t_MAT) return  lexcmp_vec_mat(x,y);
     803          42 :   /*tx==t_MAT*/  return -lexcmp_vec_mat(y,x);
     804             : }
     805             : int
     806     3129677 : lexcmp(GEN x, GEN y)
     807             : {
     808     3129677 :   pari_sp av = avma;
     809     3129677 :   if (typ(x) == t_COMPLEX)
     810             :   {
     811          63 :     x = mkvec2(gel(x,1), gel(x,2));
     812          63 :     if (typ(y) == t_COMPLEX) y = mkvec2(gel(y,1), gel(y,2));
     813          49 :     else y = mkvec2(y, gen_0);
     814             :   }
     815     3129614 :   else if (typ(y) == t_COMPLEX)
     816             :   {
     817          63 :     x = mkvec2(x, gen_0);
     818          63 :     y = mkvec2(gel(y,1), gel(y,2));
     819             :   }
     820     3129677 :   return gc_int(av, lexcmp_i(x, y));
     821             : }
     822             : 
     823             : /*****************************************************************/
     824             : /*                                                               */
     825             : /*                          EQUALITY                             */
     826             : /*                returns 1 if x == y, 0 otherwise               */
     827             : /*                                                               */
     828             : /*****************************************************************/
     829             : /* x,y t_POL */
     830             : static int
     831      931219 : polidentical(GEN x, GEN y)
     832             : {
     833             :   long lx;
     834      931219 :   if (x[1] != y[1]) return 0;
     835      931128 :   lx = lg(x); if (lg(y) != lg(x)) return 0;
     836      931058 :   for (lx--; lx >= 2; lx--) if (!gidentical(gel(x,lx), gel(y,lx))) return 0;
     837      931044 :   return 1;
     838             : }
     839             : /* x,y t_SER */
     840             : static int
     841          14 : seridentical(GEN x, GEN y) { return polidentical(x,y); }
     842             : /* typ(x) = typ(y) = t_VEC/COL/MAT */
     843             : static int
     844     4053097 : vecidentical(GEN x, GEN y)
     845             : {
     846             :   long i;
     847     4053097 :   if ((x[0] ^ y[0]) & (TYPBITS|LGBITS)) return 0;
     848    10722368 :   for (i = lg(x)-1; i; i--)
     849     7378342 :     if (! gidentical(gel(x,i),gel(y,i)) ) return 0;
     850     3344026 :   return 1;
     851             : }
     852             : static int
     853          21 : identicalrr(GEN x, GEN y)
     854             : {
     855          21 :   long i, lx = lg(x);
     856          21 :   if (lg(y) != lx) return 0;
     857          14 :   if (x[1] != y[1]) return 0;
     858           7 :   i=2; while (i<lx && x[i]==y[i]) i++;
     859           7 :   return (i == lx);
     860             : }
     861             : 
     862             : static int
     863          35 : closure_identical(GEN x, GEN y)
     864             : {
     865          35 :   if (lg(x)!=lg(y) || x[1]!=y[1]) return 0;
     866          21 :   if (!gidentical(gel(x,2),gel(y,2)) || !gidentical(gel(x,3),gel(y,3))
     867           7 :    || !gidentical(gel(x,4),gel(y,4))) return 0;
     868           7 :   if (lg(x)<8) return 1;
     869           0 :   return gidentical(gel(x,7),gel(y,7));
     870             : }
     871             : 
     872             : static int
     873         336 : list_cmp(GEN x, GEN y, int cmp(GEN x, GEN y))
     874             : {
     875         336 :   int t = list_typ(x);
     876             :   GEN vx, vy;
     877         336 :   if (list_typ(y)!=t) return 0;
     878         336 :   vx = list_data(x);
     879         336 :   vy = list_data(y);
     880         336 :   if (!vx) return vy? 0: 1;
     881         322 :   if (!vy) return 0;
     882         308 :   if (lg(vx) != lg(vy)) return 0;
     883         301 :   switch (t)
     884             :   {
     885             :   case t_LIST_MAP:
     886             :     {
     887         280 :       pari_sp av = avma;
     888         280 :       GEN mx  = maptomat_shallow(x), my = maptomat_shallow(y);
     889         280 :       int ret = gidentical(gel(mx, 1), gel(my, 1)) && cmp(gel(mx, 2), gel(my, 2));
     890         280 :       return gc_bool(av, ret);
     891             :     }
     892             :   default:
     893          21 :     return cmp(vx, vy);
     894             :   }
     895             : }
     896             : 
     897             : int
     898    36856848 : gidentical(GEN x, GEN y)
     899             : {
     900             :   long tx;
     901             : 
     902    36856848 :   if (x == y) return 1;
     903    35886916 :   tx = typ(x); if (typ(y) != tx) return 0;
     904    35883724 :   switch(tx)
     905             :   {
     906             :     case t_INT:
     907     7464670 :       return equalii(x,y);
     908             : 
     909             :     case t_REAL:
     910          14 :       return identicalrr(x,y);
     911             : 
     912             :     case t_FRAC: case t_INTMOD:
     913       19677 :       return equalii(gel(x,2), gel(y,2)) && equalii(gel(x,1), gel(y,1));
     914             : 
     915             :     case t_COMPLEX:
     916          14 :       return gidentical(gel(x,2),gel(y,2)) && gidentical(gel(x,1),gel(y,1));
     917             :     case t_PADIC:
     918          14 :       return valp(x) == valp(y)
     919          14 :         && equalii(gel(x,2),gel(y,2))
     920          14 :         && equalii(gel(x,3),gel(y,3))
     921          28 :         && equalii(gel(x,4),gel(y,4));
     922             :     case t_POLMOD:
     923          49 :       return gidentical(gel(x,2),gel(y,2)) && polidentical(gel(x,1),gel(y,1));
     924             :     case t_POL:
     925      931184 :       return polidentical(x,y);
     926             :     case t_SER:
     927          14 :       return seridentical(x,y);
     928             :     case t_FFELT:
     929          14 :       return FF_equal(x,y);
     930             : 
     931             :     case t_QFR:
     932           7 :           if (!identicalrr(gel(x,4),gel(y,4))) return 0; /* fall through */
     933             :     case t_QFI:
     934     2385395 :       return equalii(gel(x,1),gel(y,1))
     935     2385388 :           && equalii(gel(x,2),gel(y,2))
     936     4770776 :           && equalii(gel(x,3),gel(y,3));
     937             : 
     938             :     case t_QUAD:
     939          14 :       return ZX_equal(gel(x,1),gel(y,1))
     940           7 :           && gidentical(gel(x,2),gel(y,2))
     941          14 :           && gidentical(gel(x,3),gel(y,3));
     942             : 
     943             :     case t_RFRAC:
     944           7 :       return gidentical(gel(x,1),gel(y,1)) && gidentical(gel(x,2),gel(y,2));
     945             : 
     946             :     case t_STR:
     947          35 :       return !strcmp(GSTR(x),GSTR(y));
     948             :     case t_VEC: case t_COL: case t_MAT:
     949     4053097 :       return vecidentical(x,y);
     950             :     case t_VECSMALL:
     951    21029309 :       return zv_equal(x,y);
     952             :     case t_CLOSURE:
     953          28 :       return closure_identical(x,y);
     954             :     case t_LIST:
     955         161 :       return list_cmp(x, y, gidentical);
     956          21 :     case t_INFINITY: return gidentical(gel(x,1),gel(y,1));
     957             :   }
     958           0 :   return 0;
     959             : }
     960             : /* x,y t_POL */
     961             : static int
     962     9205307 : polequal(GEN x, GEN y)
     963             : {
     964             :   long lx, ly;
     965     9205307 :   if ((x[1] ^ y[1]) & (VARNBITS | SIGNBITS)) return 0;
     966     9196753 :   lx = lg(x); ly = lg(y);
     967     9196753 :   while (lx > ly) if (!gequal0(gel(x,--lx))) return 0;
     968     9194688 :   while (ly > lx) if (!gequal0(gel(y,--ly))) return 0;
     969     9181444 :   for (lx--; lx >= 2; lx--) if (!gequal(gel(x,lx), gel(y,lx))) return 0;
     970     9151643 :   return 1;
     971             : }
     972             : 
     973             : /* x,y t_POL */
     974             : static int
     975         294 : serequal(GEN x, GEN y)
     976             : {
     977             :   long lx;
     978         294 :   if (varn(x) != varn(y)) return 0;
     979         294 :   if (!signe(x))
     980             :   {
     981         266 :     if (!signe(y)) return 1;
     982           0 :     return valp(y) >= valp(x);
     983             :   }
     984          28 :   if (!signe(y))
     985           7 :     return valp(x) >= valp(y);
     986          21 :   if ((x[1] ^ y[1]) & VALPBITS) return 0;
     987          21 :   lx = minss(lg(x), lg(y));
     988          21 :   for (lx--; lx >= 2; lx--) if (!gequal(gel(x,lx), gel(y,lx))) return 0;
     989          21 :   return 1;
     990             : }
     991             : 
     992             : /* typ(x) = typ(y) = t_VEC/COL/MAT */
     993             : static int
     994     5065697 : vecequal(GEN x, GEN y)
     995             : {
     996             :   long i;
     997     5065697 :   if ((x[0] ^ y[0]) & (TYPBITS|LGBITS)) return 0;
     998    16283018 :   for (i = lg(x)-1; i; i--)
     999    14195065 :     if (! gequal(gel(x,i),gel(y,i)) ) return 0;
    1000     2087953 :   return 1;
    1001             : }
    1002             : 
    1003             : static int
    1004     4952700 : gequal_try(GEN x, GEN y)
    1005             : {
    1006             :   int i;
    1007     4952700 :   pari_CATCH(CATCH_ALL) {
    1008         175 :     GEN E = pari_err_last();
    1009         175 :     switch(err_get_num(E))
    1010             :     {
    1011             :       case e_STACK: case e_MEM: case e_ALARM:
    1012           0 :         pari_err(0, E); /* rethrow */
    1013             :     }
    1014         175 :     return 0;
    1015             :   } pari_TRY {
    1016     4952700 :     i = gequal0(gadd(x, gneg_i(y)));
    1017     4952525 :   } pari_ENDCATCH;
    1018     4952525 :   return i;
    1019             : }
    1020             : 
    1021             : int
    1022   214218052 : gequal(GEN x, GEN y)
    1023             : {
    1024             :   pari_sp av;
    1025             :   long tx, ty;
    1026             :   long i;
    1027             : 
    1028   214218052 :   if (x == y) return 1;
    1029   191467508 :   tx = typ(x);
    1030   191467508 :   ty = typ(y);
    1031   191467508 :   if (tx == ty)
    1032   186514824 :     switch(tx)
    1033             :     {
    1034             :       case t_INT:
    1035   159625526 :         return equalii(x,y);
    1036             : 
    1037             :       case t_REAL:
    1038        2035 :         return equalrr(x,y);
    1039             : 
    1040             :       case t_FRAC: case t_INTMOD:
    1041     5983902 :         return equalii(gel(x,2), gel(y,2)) && equalii(gel(x,1), gel(y,1));
    1042             : 
    1043             :       case t_COMPLEX:
    1044         420 :         return gequal(gel(x,2),gel(y,2)) && gequal(gel(x,1),gel(y,1));
    1045             :       case t_PADIC:
    1046         756 :         if (!equalii(gel(x,2),gel(y,2))) return 0;
    1047         756 :         av = avma; i = gequal0(gsub(x,y)); set_avma(av);
    1048         756 :         return i;
    1049             :       case t_POLMOD:
    1050     4856298 :         if (varn(gel(x,1)) != varn(gel(y,1))) break;
    1051     4856291 :         return gequal(gel(x,2),gel(y,2)) && RgX_equal_var(gel(x,1),gel(y,1));
    1052             :       case t_POL:
    1053     9205310 :         return polequal(x,y);
    1054             :       case t_SER:
    1055         294 :         return serequal(x,y);
    1056             : 
    1057             :       case t_FFELT:
    1058       55398 :         return FF_equal(x,y);
    1059             : 
    1060             :       case t_QFR:
    1061             :       case t_QFI:
    1062     1050134 :         return equalii(gel(x,1),gel(y,1))
    1063      230227 :             && equalii(gel(x,2),gel(y,2))
    1064     1207344 :             && equalii(gel(x,3),gel(y,3));
    1065             : 
    1066             :       case t_QUAD:
    1067           7 :         return ZX_equal(gel(x,1),gel(y,1))
    1068           0 :             && gequal(gel(x,2),gel(y,2))
    1069           7 :             && gequal(gel(x,3),gel(y,3));
    1070             : 
    1071             :       case t_RFRAC:
    1072             :       {
    1073       73717 :         GEN a = gel(x,1), b = gel(x,2), c = gel(y,1), d = gel(y,2);
    1074       73717 :         if (gequal(b,d)) return gequal(a,c); /* simple case */
    1075           0 :         av = avma;
    1076           0 :         a = simplify_shallow(gmul(a,d));
    1077           0 :         b = simplify_shallow(gmul(b,c));
    1078           0 :         return gc_bool(av, gequal(a,b));
    1079             :       }
    1080             : 
    1081             :       case t_STR:
    1082       57013 :         return !strcmp(GSTR(x),GSTR(y));
    1083             :       case t_VEC: case t_COL: case t_MAT:
    1084     5065697 :         return vecequal(x,y);
    1085             :       case t_VECSMALL:
    1086      538125 :         return zv_equal(x,y);
    1087             :       case t_LIST:
    1088         175 :         return list_cmp(x, y, gequal);
    1089             :       case t_CLOSURE:
    1090           7 :         return closure_identical(x,y);
    1091             :       case t_INFINITY:
    1092          28 :         return gequal(gel(x,1),gel(y,1));
    1093             :     }
    1094     4952673 :   (void)&av; av = avma; /* emulate volatile */
    1095     4952673 :   return gc_bool(av, gequal_try(x, y));
    1096             : }
    1097             : 
    1098             : int
    1099       39382 : gequalsg(long s, GEN x)
    1100       39382 : { pari_sp av = avma; return gc_bool(av, gequal(stoi(s), x)); }
    1101             : 
    1102             : /* a and b are t_INT, t_FRAC, t_REAL or t_COMPLEX of those. Check whether
    1103             :  * a-b is invertible */
    1104             : int
    1105        9268 : cx_approx_equal(GEN a, GEN b)
    1106             : {
    1107        9268 :   pari_sp av = avma;
    1108             :   GEN d;
    1109        9268 :   if (a == b) return 1;
    1110        7770 :   d = gsub(a,b);
    1111        7770 :   return gc_bool(av, gequal0(d) || (typ(d)==t_COMPLEX && gequal0(cxnorm(d))));
    1112             : }
    1113             : /*******************************************************************/
    1114             : /*                                                                 */
    1115             : /*                          VALUATION                              */
    1116             : /*             p is either a t_INT or a t_POL.                     */
    1117             : /*  returns the largest exponent of p dividing x when this makes   */
    1118             : /*  sense : error for types real, integermod and polymod if p does */
    1119             : /*  not divide the modulus, q-adic if q!=p.                        */
    1120             : /*                                                                 */
    1121             : /*******************************************************************/
    1122             : 
    1123             : static long
    1124         231 : minval(GEN x, GEN p)
    1125             : {
    1126         231 :   long i,k, val = LONG_MAX, lx = lg(x);
    1127        5789 :   for (i=lontyp[typ(x)]; i<lx; i++)
    1128             :   {
    1129        5558 :     k = gvaluation(gel(x,i),p);
    1130        5558 :     if (k < val) val = k;
    1131             :   }
    1132         231 :   return val;
    1133             : }
    1134             : 
    1135             : static int
    1136          91 : intdvd(GEN x, GEN y, GEN *z) { GEN r; *z = dvmdii(x,y,&r); return (r==gen_0); }
    1137             : 
    1138             : /* x t_FRAC, p t_INT, return v_p(x) */
    1139             : static long
    1140       92813 : ratval(GEN x, GEN p) {
    1141       92813 :   long v = Z_pval(gel(x,2),p);
    1142       92813 :   if (v) return -v;
    1143       10892 :   return Z_pval(gel(x,1),p);
    1144             : }
    1145             : 
    1146             : long
    1147     1416784 : Q_pval(GEN x, GEN p) { return (typ(x) == t_INT)? Z_pval(x, p): ratval(x, p); }
    1148             : 
    1149             : long
    1150      436587 : Q_pvalrem(GEN x, GEN p, GEN *y)
    1151             : {
    1152             :   GEN a, b;
    1153             :   long v;
    1154      436587 :   if (typ(x) == t_INT) return Z_pvalrem(x, p, y);
    1155       78288 :   a = gel(x,1);
    1156       78288 :   b = gel(x,2);
    1157       78288 :   v = Z_pvalrem(b, p, &b);
    1158       78288 :   if (v) { *y = isint1(b)? a: mkfrac(a, b); return -v; }
    1159       48685 :   v = Z_pvalrem(a, p, &a);
    1160       48685 :   *y = mkfrac(a, b); return v;
    1161             : }
    1162             : 
    1163             : long
    1164      204283 : gvaluation(GEN x, GEN p)
    1165             : {
    1166      204283 :   long tx = typ(x), tp = typ(p);
    1167             :   pari_sp av;
    1168             : 
    1169      204283 :   switch(tp)
    1170             :   {
    1171             :     case t_INT:
    1172      196527 :       if (signe(p) && !is_pm1(p)) break;
    1173          28 :       pari_err_DOMAIN("gvaluation", "p", "=", p, p);
    1174             :     case t_POL:
    1175        7749 :       if (degpol(p) > 0) break;
    1176             :     default:
    1177           7 :       pari_err_DOMAIN("gvaluation", "p", "=", p, p);
    1178             :   }
    1179             : 
    1180      204248 :   switch(tx)
    1181             :   {
    1182             :     case t_INT:
    1183       11623 :       if (!signe(x)) return LONG_MAX;
    1184       11518 :       if (tp == t_POL) return 0;
    1185       11224 :       return Z_pval(x,p);
    1186             : 
    1187             :     case t_REAL:
    1188          49 :       if (tp == t_POL) return 0;
    1189          21 :       break;
    1190             : 
    1191             :     case t_FFELT:
    1192          28 :       if (tp == t_POL) return FF_equal0(x)? LONG_MAX: 0;
    1193          14 :       break;
    1194             : 
    1195             :     case t_INTMOD: {
    1196          84 :       GEN a = gel(x,1), b = gel(x,2);
    1197             :       long val;
    1198         154 :       if (tp == t_POL) return signe(b)? 0: LONG_MAX;
    1199          42 :       av = avma;
    1200          42 :       if (!intdvd(a, p, &a)) break;
    1201          28 :       if (!intdvd(b, p, &b)) return gc_long(av,0);
    1202          14 :       val = 1; while (intdvd(a,p,&a) && intdvd(b,p,&b)) val++;
    1203          14 :       return gc_long(av,val);
    1204             :     }
    1205             : 
    1206             :     case t_FRAC:
    1207          42 :       if (tp == t_POL) return 0;
    1208          28 :       return ratval(x, p);
    1209             : 
    1210             :     case t_PADIC:
    1211      184925 :       if (tp == t_POL) return 0;
    1212      184911 :       if (!equalii(p,gel(x,2))) break;
    1213      184904 :       return valp(x);
    1214             : 
    1215             :     case t_POLMOD: {
    1216          35 :       GEN a = gel(x,1), b = gel(x,2);
    1217             :       long v, val;
    1218          35 :       if (tp == t_INT) return gvaluation(b,p);
    1219          21 :       v = varn(p);
    1220          21 :       if (varn(a) != v) return 0;
    1221          21 :       av = avma;
    1222          21 :       a = RgX_divrem(a, p, ONLY_DIVIDES);
    1223          21 :       if (!a) break;
    1224          14 :       if (typ(b) != t_POL || varn(b) != v ||
    1225           7 :           !(b = RgX_divrem(b, p, ONLY_DIVIDES)) ) return gc_long(av,0);
    1226           7 :       val = 1;
    1227          21 :       while ((a = RgX_divrem(a, p, ONLY_DIVIDES)) &&
    1228           7 :              (b = RgX_divrem(b, p, ONLY_DIVIDES)) ) val++;
    1229           7 :       return gc_long(av,val);
    1230             :     }
    1231             :     case t_POL: {
    1232        7161 :       if (tp == t_POL) {
    1233        7028 :         long vp = varn(p), vx = varn(x);
    1234        7028 :         if (vp == vx)
    1235             :         {
    1236             :           long val;
    1237        7021 :           if (RgX_is_monomial(p)) return RgX_val(x) / degpol(p);
    1238           7 :           av = avma;
    1239           7 :           for (val=0; ; val++)
    1240             :           {
    1241           7 :             x = RgX_divrem(x,p,ONLY_DIVIDES);
    1242           7 :             if (!x) return gc_long(av,val);
    1243           0 :             if (gc_needed(av,1))
    1244             :             {
    1245           0 :               if(DEBUGMEM>1) pari_warn(warnmem,"gvaluation");
    1246           0 :               x = gerepilecopy(av, x);
    1247             :             }
    1248             :           }
    1249             :         }
    1250           7 :         if (varncmp(vx, vp) > 0) return 0;
    1251             :       }
    1252         133 :       return minval(x,p);
    1253             :     }
    1254             : 
    1255             :     case t_SER: {
    1256         175 :       if (tp == t_POL) {
    1257         161 :         long vp = varn(p), vx = varn(x);
    1258         161 :         if (vp == vx)
    1259             :         {
    1260         154 :           long val = RgX_val(p);
    1261         154 :           if (!val) pari_err_DOMAIN("gvaluation", "p", "=", p, p);
    1262         147 :           return (long)(valp(x) / val);
    1263             :         }
    1264           7 :         if (varncmp(vx, vp) > 0) return 0;
    1265             :       }
    1266          14 :       return minval(x,p);
    1267             :     }
    1268             : 
    1269             :     case t_RFRAC:
    1270          42 :       return gvaluation(gel(x,1),p) - gvaluation(gel(x,2),p);
    1271             : 
    1272             :     case t_COMPLEX: case t_QUAD: case t_VEC: case t_COL: case t_MAT:
    1273          84 :       return minval(x,p);
    1274             :   }
    1275          63 :   pari_err_OP("valuation", x,p);
    1276             :   return 0; /* LCOV_EXCL_LINE */
    1277             : }
    1278             : GEN
    1279        3675 : gpvaluation(GEN x, GEN p)
    1280             : {
    1281        3675 :   long v = gvaluation(x,p);
    1282        3577 :   return v == LONG_MAX? mkoo(): stoi(v);
    1283             : }
    1284             : 
    1285             : /* x is non-zero */
    1286             : long
    1287    16261809 : u_lvalrem(ulong x, ulong p, ulong *py)
    1288             : {
    1289             :   ulong vx;
    1290    16261809 :   if (p == 2) { vx = vals(x); *py = x >> vx; return vx; }
    1291    13974899 :   for(vx = 0;;)
    1292             :   {
    1293    37015865 :     if (x % p) { *py = x; return vx; }
    1294    11520483 :     x /= p; /* gcc is smart enough to make a single div */
    1295    11520483 :     vx++;
    1296             :   }
    1297             : }
    1298             : long
    1299    10387425 : u_lval(ulong x, ulong p)
    1300             : {
    1301             :   ulong vx;
    1302    10387425 :   if (p == 2) return vals(x);
    1303     9770469 :   for(vx = 0;;)
    1304             :   {
    1305    46530431 :     if (x % p) return vx;
    1306    18379981 :     x /= p; /* gcc is smart enough to make a single div */
    1307    18379981 :     vx++;
    1308             :   }
    1309             : }
    1310             : 
    1311             : long
    1312      351427 : z_lval(long s, ulong p) { return u_lval(labs(s), p); }
    1313             : long
    1314          35 : z_lvalrem(long s, ulong p, long *py)
    1315             : {
    1316             :   long v;
    1317          35 :   if (s < 0)
    1318             :   {
    1319           0 :     ulong u = (ulong)-s;
    1320           0 :     v = u_lvalrem(u, p, &u);
    1321           0 :     *py = -(long)u;
    1322             :   }
    1323             :   else
    1324             :   {
    1325          35 :     ulong u = (ulong)s;
    1326          35 :     v = u_lvalrem(u, p, &u);
    1327          35 :     *py = (long)u;
    1328             :   }
    1329          35 :   return v;
    1330             : }
    1331             : /* assume |p| > 1 */
    1332             : long
    1333       42427 : z_pval(long s, GEN p)
    1334             : {
    1335       42427 :   if (lgefint(p) > 3) return 0;
    1336       42427 :   return z_lval(s, uel(p,2));
    1337             : }
    1338             : /* assume |p| > 1 */
    1339             : long
    1340          35 : z_pvalrem(long s, GEN p, long *py)
    1341             : {
    1342          35 :   if (lgefint(p) > 3) { *py = s; return 0; }
    1343          35 :   return z_lvalrem(s, uel(p,2), py);
    1344             : }
    1345             : 
    1346             : /* return v_q(x) and set *py = x / q^v_q(x), using divide & conquer */
    1347             : static long
    1348     1358640 : Z_pvalrem_DC(GEN x, GEN q, GEN *py)
    1349             : {
    1350     1358640 :   GEN r, z = dvmdii(x, q, &r);
    1351             :   long v;
    1352     1358640 :   if (r != gen_0) { *py = x; return 0; }
    1353      952661 :   if (2 * lgefint(q) <= lgefint(z)+3) /* avoid squaring if pointless */
    1354      939345 :     v = Z_pvalrem_DC(z, sqri(q), py) << 1;
    1355             :   else
    1356       13316 :   { v = 0; *py = z; }
    1357      952661 :   z = dvmdii(*py, q, &r);
    1358      952661 :   if (r != gen_0) return v + 1;
    1359      402941 :   *py = z; return v + 2;
    1360             : }
    1361             : 
    1362             : static const long VAL_DC_THRESHOLD = 16;
    1363             : 
    1364             : long
    1365    10928479 : Z_lval(GEN x, ulong p)
    1366             : {
    1367             :   long vx;
    1368             :   pari_sp av;
    1369    10928479 :   if (p == 2) return vali(x);
    1370     7697647 :   if (lgefint(x) == 3) return u_lval(uel(x,2), p);
    1371      874211 :   av = avma;
    1372      874211 :   for(vx = 0;;)
    1373     5298538 :   {
    1374             :     ulong r;
    1375     6172749 :     GEN q = absdiviu_rem(x, p, &r);
    1376     7046960 :     if (r) break;
    1377     5412066 :     vx++; x = q;
    1378     5412066 :     if (vx == VAL_DC_THRESHOLD) {
    1379      113528 :       if (p == 1) pari_err_DOMAIN("Z_lval", "p", "=", gen_1, gen_1);
    1380      113528 :       vx += Z_pvalrem_DC(x, sqru(p), &x) << 1;
    1381      113528 :       q = absdiviu_rem(x, p, &r); if (!r) vx++;
    1382      113528 :       break;
    1383             :     }
    1384             :   }
    1385      874211 :   return gc_long(av,vx);
    1386             : }
    1387             : long
    1388    14390018 : Z_lvalrem(GEN x, ulong p, GEN *py)
    1389             : {
    1390             :   long vx, sx;
    1391             :   pari_sp av;
    1392    14390018 :   if (p == 2) { vx = vali(x); *py = shifti(x, -vx); return vx; }
    1393     9409838 :   if (lgefint(x) == 3) {
    1394             :     ulong u;
    1395     7227752 :     vx = u_lvalrem(uel(x,2), p, &u);
    1396     7227752 :     *py = signe(x) < 0? utoineg(u): utoipos(u);
    1397     7227753 :     return vx;
    1398             :   }
    1399     2182086 :   av = avma; (void)new_chunk(lgefint(x));
    1400     2182086 :   sx = signe(x);
    1401     2182086 :   for(vx = 0;;)
    1402     7821427 :   {
    1403             :     ulong r;
    1404    10003513 :     GEN q = absdiviu_rem(x, p, &r);
    1405    12185599 :     if (r) break;
    1406     8119060 :     vx++; x = q;
    1407     8119060 :     if (vx == VAL_DC_THRESHOLD) {
    1408      297633 :       if (p == 1) pari_err_DOMAIN("Z_lvalrem", "p", "=", gen_1, gen_1);
    1409      297633 :       vx += Z_pvalrem_DC(x, sqru(p), &x) << 1;
    1410      297633 :       q = absdiviu_rem(x, p, &r); if (!r) { vx++; x = q; }
    1411      297633 :       break;
    1412             :     }
    1413             :   }
    1414     2182086 :   set_avma(av); *py = icopy(x); setsigne(*py, sx); return vx;
    1415             : }
    1416             : 
    1417             : /* Is |q| <= p ? */
    1418             : static int
    1419   193718059 : isless_iu(GEN q, ulong p) {
    1420   193718059 :   long l = lgefint(q);
    1421   193718059 :   return l==2 || (l == 3 && uel(q,2) <= p);
    1422             : }
    1423             : 
    1424             : long
    1425   537274005 : u_lvalrem_stop(ulong *n, ulong p, int *stop)
    1426             : {
    1427   537274005 :   ulong N = *n, q = N / p, r = N % p; /* gcc makes a single div */
    1428   537274005 :   long v = 0;
    1429   537274005 :   if (!r)
    1430             :   {
    1431    38928947 :     do { v++; N = q; q = N / p; r = N % p; } while (!r);
    1432    26885084 :     *n = N;
    1433             :   }
    1434   537274005 :   *stop = q <= p; return v;
    1435             : }
    1436             : /* Assume n > 0. Return v_p(n), set *n := n/p^v_p(n). Set 'stop' if now
    1437             :  * n < p^2 [implies n prime if no prime < p divides n] */
    1438             : long
    1439   577502667 : Z_lvalrem_stop(GEN *n, ulong p, int *stop)
    1440             : {
    1441             :   pari_sp av;
    1442             :   long v;
    1443             :   ulong r;
    1444             :   GEN N, q;
    1445             : 
    1446   577502667 :   if (lgefint(*n) == 3)
    1447             :   {
    1448   383766231 :     r = (*n)[2];
    1449   383766231 :     v = u_lvalrem_stop(&r, p, stop);
    1450   383798781 :     if (v) *n = utoipos(r);
    1451   383803189 :     return v;
    1452             :   }
    1453   193736436 :   av = avma; v = 0; q = absdiviu_rem(*n, p, &r);
    1454   193672089 :   if (r) set_avma(av);
    1455             :   else
    1456             :   {
    1457             :     do {
    1458     1224225 :       v++; N = q;
    1459     1224225 :       if (v == VAL_DC_THRESHOLD)
    1460             :       {
    1461        8134 :         v += Z_pvalrem_DC(N,sqru(p),&N) << 1;
    1462        8134 :         q = absdiviu_rem(N, p, &r); if (!r) { v++; N = q; }
    1463        8134 :         break;
    1464             :       }
    1465     1216091 :       q = absdiviu_rem(N, p, &r);
    1466     1216091 :     } while (!r);
    1467      674993 :     *n = N;
    1468             :   }
    1469   193682394 :   *stop = isless_iu(q,p); return v;
    1470             : }
    1471             : 
    1472             : /* x is a non-zero integer, |p| > 1 */
    1473             : long
    1474    12078341 : Z_pvalrem(GEN x, GEN p, GEN *py)
    1475             : {
    1476             :   long vx;
    1477             :   pari_sp av;
    1478             : 
    1479    12078341 :   if (lgefint(p) == 3) return Z_lvalrem(x, uel(p,2), py);
    1480      133914 :   if (lgefint(x) == 3) { *py = icopy(x); return 0; }
    1481        3705 :   av = avma; vx = 0; (void)new_chunk(lgefint(x));
    1482             :   for(;;)
    1483        9217 :   {
    1484       12922 :     GEN r, q = dvmdii(x,p,&r);
    1485       12922 :     if (r != gen_0) { set_avma(av); *py = icopy(x); return vx; }
    1486        9217 :     vx++; x = q;
    1487             :   }
    1488             : }
    1489             : long
    1490      396854 : u_pvalrem(ulong x, GEN p, ulong *py)
    1491             : {
    1492      396854 :   if (lgefint(p) == 3) return u_lvalrem(x, uel(p,2), py);
    1493         459 :   *py = x; return 0;
    1494             : }
    1495             : long
    1496        2002 : u_pval(ulong x, GEN p)
    1497             : {
    1498        2002 :   if (lgefint(p) == 3) return u_lval(x, uel(p,2));
    1499           0 :   return 0;
    1500             : }
    1501             : long
    1502     6921295 : Z_pval(GEN x, GEN p) {
    1503             :   long vx;
    1504             :   pari_sp av;
    1505             : 
    1506     6921295 :   if (lgefint(p) == 3) return Z_lval(x, uel(p,2));
    1507       76971 :   if (lgefint(x) == 3) return 0;
    1508       70933 :   av = avma; vx = 0;
    1509             :   for(;;)
    1510       20507 :   {
    1511       91440 :     GEN r, q = dvmdii(x,p,&r);
    1512       91440 :     if (r != gen_0) return gc_long(av,vx);
    1513       20507 :     vx++; x = q;
    1514             :   }
    1515             : }
    1516             : 
    1517             : /* return v_p(n!) = [n/p] + [n/p^2] + ... */
    1518             : long
    1519      120609 : factorial_lval(ulong n, ulong p)
    1520             : {
    1521             :   ulong q, v;
    1522      120609 :   if (p == 2) return n - hammingl(n);
    1523       33083 :   q = p; v = 0;
    1524       35148 :   do { v += n/q; q *= p; } while (n >= q);
    1525       33083 :   return (long)v;
    1526             : }
    1527             : 
    1528             : /********** Same for "containers" ZX / ZV / ZC **********/
    1529             : 
    1530             : /* If the t_INT q divides the ZX/ZV x, return the quotient. Otherwise NULL.
    1531             :  * Stack clean; assumes lg(x) > 1 */
    1532             : static GEN
    1533        4368 : gen_Z_divides(GEN x, GEN q, long imin)
    1534             : {
    1535             :   long i, l;
    1536        4368 :   GEN y = cgetg_copy(x, &l);
    1537             : 
    1538        4368 :   y[1] = x[1]; /* Needed for ZX; no-op if ZV, overwritten in first iteration */
    1539       83573 :   for (i = imin; i < l; i++)
    1540             :   {
    1541       81823 :     GEN r, xi = gel(x,i);
    1542       81823 :     if (!signe(xi)) { gel(y,i) = xi; continue; }
    1543       50609 :     gel(y,i) = dvmdii(xi, q, &r);
    1544       50609 :     if (r != gen_0) { set_avma((pari_sp)(y+l)); return NULL; }
    1545             :   }
    1546        1750 :   return y;
    1547             : }
    1548             : /* If q divides the ZX/ZV x, return the quotient. Otherwise NULL.
    1549             :  * Stack clean; assumes lg(x) > 1 */
    1550             : static GEN
    1551        2702 : gen_z_divides(GEN x, ulong q, long imin)
    1552             : {
    1553             :   long i, l;
    1554        2702 :   GEN y = cgetg_copy(x, &l);
    1555             : 
    1556        2702 :   y[1] = x[1]; /* Needed for ZX; no-op if ZV, overwritten in first iteration */
    1557       36673 :   for (i = imin; i < l; i++)
    1558             :   {
    1559             :     ulong r;
    1560       36316 :     GEN xi = gel(x,i);
    1561       36316 :     if (!signe(xi)) { gel(y,i) = xi; continue; }
    1562       22763 :     gel(y,i) = absdiviu_rem(xi, q, &r);
    1563       22763 :     if (r) { set_avma((pari_sp)(y+l)); return NULL; }
    1564       20418 :     affectsign_safe(xi, &gel(y,i));
    1565             :   }
    1566         357 :   return y;
    1567             : }
    1568             : 
    1569             : /* return v_q(x) and set *py = x / q^v_q(x), using divide & conquer */
    1570             : static long
    1571        7026 : gen_pvalrem_DC(GEN x, GEN q, GEN *py, long imin)
    1572             : {
    1573             : 
    1574        7026 :   pari_sp av = avma;
    1575        7026 :   long v, i, l, lz = LONG_MAX;
    1576        7026 :   GEN y = cgetg_copy(x, &l);
    1577             : 
    1578        7026 :   y[1] = x[1];
    1579      121614 :   for (i = imin; i < l; i++)
    1580             :   {
    1581      117246 :     GEN r, xi = gel(x,i);
    1582      117246 :     if (!signe(xi)) { gel(y,i) = xi; continue; }
    1583       74595 :     gel(y,i) = dvmdii(xi, q, &r);
    1584       74595 :     if (r != gen_0) { *py = x; return gc_long(av,0); }
    1585       71937 :     lz = minss(lz, lgefint(gel(y,i)));
    1586             :   }
    1587        4368 :   if (2 * lgefint(q) <= lz+3) /* avoid squaring if pointless */
    1588        4310 :     v = gen_pvalrem_DC(y, sqri(q), py, imin) << 1;
    1589             :   else
    1590          58 :   { v = 0; *py = y; }
    1591             : 
    1592        4368 :   y = gen_Z_divides(*py, q, imin);
    1593        4368 :   if (!y) return v+1;
    1594        1750 :   *py = y; return v+2;
    1595             : }
    1596             : 
    1597             : static long
    1598        5642 : gen_2val(GEN x, long imin)
    1599             : {
    1600        5642 :   long i, lx = lg(x), v = LONG_MAX;
    1601       17824 :   for (i = imin; i < lx; i++)
    1602             :   {
    1603       16466 :     GEN c = gel(x,i);
    1604             :     long w;
    1605       16466 :     if (!signe(c)) continue;
    1606       11829 :     w = vali(c);
    1607       11829 :     if (w < v) { v = w; if (!v) break; }
    1608             :   }
    1609        5642 :   return v;
    1610             : }
    1611             : static long
    1612       12711 : gen_lval(GEN x, ulong p, long imin)
    1613             : {
    1614             :   long i, lx, v;
    1615             :   pari_sp av;
    1616             :   GEN y;
    1617       12711 :   if (p == 2) return gen_2val(x, imin);
    1618        7069 :   av = avma;
    1619        7069 :   lx = lg(x); y = leafcopy(x);
    1620        7209 :   for(v = 0;; v++)
    1621        9841 :     for (i = imin; i < lx; i++)
    1622             :     {
    1623             :       ulong r;
    1624        9561 :       gel(y,i) = absdiviu_rem(gel(y,i), p, &r);
    1625        9561 :       if (r) return gc_long(av,v);
    1626             :     }
    1627             : }
    1628             : long
    1629          42 : ZX_lval(GEN x, ulong p) { return gen_lval(x, p, 2); }
    1630             : long
    1631           0 : ZV_lval(GEN x, ulong p) { return gen_lval(x, p, 1); }
    1632             : 
    1633             : static long
    1634       14889 : gen_pval(GEN x, GEN p, long imin)
    1635             : {
    1636             :   long i, lx, v;
    1637             :   pari_sp av;
    1638             :   GEN y;
    1639       14889 :   if (lgefint(p) == 3) return gen_lval(x, p[2], imin);
    1640        2220 :   av = avma;
    1641        2220 :   lx = lg(x); y = leafcopy(x);
    1642        2220 :   for(v = 0;; v++)
    1643             :   {
    1644        2220 :     if (v == VAL_DC_THRESHOLD)
    1645             :     {
    1646           0 :       if (is_pm1(p)) pari_err_DOMAIN("gen_pval", "p", "=", p, p);
    1647           0 :       v += gen_pvalrem_DC(y, p, &y, imin);
    1648           0 :       return gc_long(av,v);
    1649             :     }
    1650             : 
    1651        2220 :     for (i = imin; i < lx; i++)
    1652             :     {
    1653        2220 :       GEN r; gel(y,i) = dvmdii(gel(y,i), p, &r);
    1654        2220 :       if (r != gen_0) return gc_long(av,v);
    1655             :     }
    1656             :   }
    1657             : }
    1658             : long
    1659        7973 : ZX_pval(GEN x, GEN p) { return gen_pval(x, p, 2); }
    1660             : long
    1661        6916 : ZV_pval(GEN x, GEN p) { return gen_pval(x, p, 1); }
    1662             : /* v = 0 (mod p) */
    1663             : int
    1664         245 : ZV_Z_dvd(GEN v, GEN p)
    1665             : {
    1666         245 :   pari_sp av = avma;
    1667         245 :   long i, l = lg(v);
    1668         889 :   for (i=1; i<l; i++)
    1669         672 :     if (!dvdii(gel(v,i), p)) return gc_long(av,0);
    1670         217 :   return gc_long(av,1);
    1671             : }
    1672             : 
    1673             : static long
    1674      313110 : gen_2valrem(GEN x, GEN *px, long imin)
    1675             : {
    1676      313110 :   long i, lx = lg(x), v = LONG_MAX;
    1677             :   GEN z;
    1678     3318395 :   for (i = imin; i < lx; i++)
    1679             :   {
    1680     3136382 :     GEN c = gel(x,i);
    1681             :     long w;
    1682     3136382 :     if (!signe(c)) continue;
    1683     2993605 :     w = vali(c);
    1684     2993605 :     if (w < v) {
    1685      616212 :       v = w;
    1686      616212 :       if (!v) { *px = x; return 0; } /* early abort */
    1687             :     }
    1688             :   }
    1689      182013 :   z = cgetg_copy(x, &lx); z[1] = x[1];
    1690      182013 :   for (i=imin; i<lx; i++) gel(z,i) = shifti(gel(x,i), -v);
    1691      182013 :   *px = z; return v;
    1692             : }
    1693             : static long
    1694      671719 : gen_lvalrem(GEN x, ulong p, GEN *px, long imin)
    1695             : {
    1696             :   long i, lx, v;
    1697             :   GEN y;
    1698      671719 :   if (p == 2) return gen_2valrem(x, px, imin);
    1699      358609 :   y = cgetg_copy(x, &lx);
    1700      358609 :   y[1] = x[1];
    1701      358609 :   x = leafcopy(x);
    1702      781507 :   for(v = 0;; v++)
    1703             :   {
    1704     1204405 :     if (v == VAL_DC_THRESHOLD)
    1705             :     {
    1706        2702 :       if (p == 1) pari_err_DOMAIN("gen_lvalrem", "p", "=", gen_1, gen_1);
    1707        2702 :       v += gen_pvalrem_DC(x, sqru(p), px, imin) << 1;
    1708        2702 :       x = gen_z_divides(*px, p, imin);
    1709        2702 :       if (x) { *px = x; v++; }
    1710        2702 :       return v;
    1711             :     }
    1712             : 
    1713     6113946 :     for (i = imin; i < lx; i++)
    1714             :     {
    1715     5691048 :       ulong r; gel(y,i) = absdiviu_rem(gel(x,i), p, &r);
    1716     5691048 :       if (r) { *px = x; return v; }
    1717     5335141 :       affectsign_safe(gel(x,i), &gel(y,i));
    1718             :     }
    1719      422898 :     swap(x, y);
    1720             :   }
    1721             : }
    1722             : long
    1723           0 : ZX_lvalrem(GEN x, ulong p, GEN *px) { return gen_lvalrem(x,p,px, 2); }
    1724             : long
    1725           0 : ZV_lvalrem(GEN x, ulong p, GEN *px) { return gen_lvalrem(x,p,px, 1); }
    1726             : 
    1727             : static long
    1728      671923 : gen_pvalrem(GEN x, GEN p, GEN *px, long imin)
    1729             : {
    1730             :   long i, lx, v;
    1731             :   GEN y;
    1732      671923 :   if (lgefint(p) == 3) return gen_lvalrem(x, p[2], px, imin);
    1733         204 :   y = cgetg_copy(x, &lx);
    1734         204 :   y[1] = x[1];
    1735         204 :   x = leafcopy(x);
    1736         930 :   for(v = 0;; v++)
    1737             :   {
    1738        1656 :     if (v == VAL_DC_THRESHOLD)
    1739             :     {
    1740          14 :       if (is_pm1(p)) pari_err_DOMAIN("gen_pvalrem", "p", "=", p, p);
    1741          14 :       return v + gen_pvalrem_DC(x, p, px, imin);
    1742             :     }
    1743             : 
    1744        9153 :     for (i = imin; i < lx; i++)
    1745             :     {
    1746        8427 :       GEN r; gel(y,i) = dvmdii(gel(x,i), p, &r);
    1747        8427 :       if (r != gen_0) { *px = x; return v; }
    1748             :     }
    1749         726 :     swap(x, y);
    1750             :   }
    1751             : }
    1752             : long
    1753      557336 : ZX_pvalrem(GEN x, GEN p, GEN *px) { return gen_pvalrem(x,p,px, 2); }
    1754             : long
    1755      114587 : ZV_pvalrem(GEN x, GEN p, GEN *px) { return gen_pvalrem(x,p,px, 1); }
    1756             : 
    1757             : /*******************************************************************/
    1758             : /*                                                                 */
    1759             : /*                       NEGATION: Create -x                       */
    1760             : /*                                                                 */
    1761             : /*******************************************************************/
    1762             : 
    1763             : GEN
    1764   212181132 : gneg(GEN x)
    1765             : {
    1766             :   long lx, i;
    1767             :   GEN y;
    1768             : 
    1769   212181132 :   switch(typ(x))
    1770             :   {
    1771             :     case t_INT:
    1772    65970038 :       return signe(x)? negi(x): gen_0;
    1773             :     case t_REAL:
    1774   101840491 :       return mpneg(x);
    1775             : 
    1776      191765 :     case t_INTMOD: y=cgetg(3,t_INTMOD);
    1777      191765 :       gel(y,1) = icopy(gel(x,1));
    1778      191765 :       gel(y,2) = signe(gel(x,2))? subii(gel(y,1),gel(x,2)): gen_0;
    1779      191765 :       break;
    1780             : 
    1781             :     case t_FRAC:
    1782      637542 :       y = cgetg(3, t_FRAC);
    1783      637542 :       gel(y,1) = negi(gel(x,1));
    1784      637542 :       gel(y,2) = icopy(gel(x,2)); break;
    1785             : 
    1786             :     case t_COMPLEX:
    1787    41990356 :       y=cgetg(3, t_COMPLEX);
    1788    41990356 :       gel(y,1) = gneg(gel(x,1));
    1789    41990356 :       gel(y,2) = gneg(gel(x,2));
    1790    41990356 :       break;
    1791             : 
    1792             :     case t_POLMOD:
    1793      140909 :       retmkpolmod(gneg(gel(x,2)), RgX_copy(gel(x,1)));
    1794             : 
    1795             :     case t_RFRAC:
    1796      153090 :       y = cgetg(3, t_RFRAC);
    1797      153090 :       gel(y,1) = gneg(gel(x,1));
    1798      153090 :       gel(y,2) = RgX_copy(gel(x,2)); break;
    1799             : 
    1800             :     case t_PADIC:
    1801        7091 :       if (!signe(gel(x,4))) return gcopy(x);
    1802        6090 :       y = cgetg(5, t_PADIC);
    1803        6090 :       y[1] = x[1];
    1804        6090 :       gel(y,2) = icopy(gel(x,2));
    1805        6090 :       gel(y,3) = icopy(gel(x,3));
    1806        6090 :       gel(y,4) = subii(gel(x,3),gel(x,4));
    1807        6090 :       break;
    1808             : 
    1809             :     case t_QUAD:
    1810          56 :       y=cgetg(4,t_QUAD);
    1811          56 :       gel(y,1) = ZX_copy(gel(x,1));
    1812          56 :       gel(y,2) = gneg(gel(x,2));
    1813          56 :       gel(y,3) = gneg(gel(x,3)); break;
    1814             : 
    1815       40013 :     case t_FFELT: return FF_neg(x);
    1816     1099200 :     case t_POL: return RgX_neg(x);
    1817             :     case t_SER:
    1818        1001 :       y = cgetg_copy(x, &lx); y[1] = x[1];
    1819        1001 :       for (i=2; i<lx; i++) gel(y,i) = gneg(gel(x,i));
    1820        1001 :       break;
    1821       32403 :     case t_VEC: return RgV_neg(x);
    1822       73901 :     case t_COL: return RgC_neg(x);
    1823        2513 :     case t_MAT: return RgM_neg(x);
    1824         763 :     case t_INFINITY: return inf_get_sign(x) == 1? mkmoo(): mkoo();
    1825             :     default:
    1826           0 :       pari_err_TYPE("gneg",x);
    1827             :       return NULL; /* LCOV_EXCL_LINE */
    1828             :   }
    1829    42979900 :   return y;
    1830             : }
    1831             : 
    1832             : GEN
    1833    48761062 : gneg_i(GEN x)
    1834             : {
    1835             :   long lx, i;
    1836             :   GEN y;
    1837             : 
    1838    48761062 :   switch(typ(x))
    1839             :   {
    1840             :     case t_INT:
    1841    25947953 :       return signe(x)? negi(x): gen_0;
    1842             :     case t_REAL:
    1843     5167855 :       return mpneg(x);
    1844             : 
    1845     1088929 :     case t_INTMOD: y=cgetg(3,t_INTMOD);
    1846     1088929 :       gel(y,1) = gel(x,1);
    1847     1088929 :       gel(y,2) = signe(gel(x,2))? subii(gel(y,1),gel(x,2)): gen_0;
    1848     1088929 :       break;
    1849             : 
    1850             :     case t_FRAC:
    1851     2540586 :       y = cgetg(3, t_FRAC);
    1852     2540586 :       gel(y,1) = negi(gel(x,1));
    1853     2540586 :       gel(y,2) = gel(x,2); break;
    1854             : 
    1855             :     case t_COMPLEX:
    1856     1956451 :       y = cgetg(3, t_COMPLEX);
    1857     1956451 :       gel(y,1) = gneg_i(gel(x,1));
    1858     1956451 :       gel(y,2) = gneg_i(gel(x,2)); break;
    1859             : 
    1860      124709 :     case t_PADIC: y = cgetg(5,t_PADIC);
    1861      124709 :       y[1] = x[1];
    1862      124709 :       gel(y,2) = gel(x,2);
    1863      124709 :       gel(y,3) = gel(x,3);
    1864      124709 :       gel(y,4) = signe(gel(x,4))? subii(gel(x,3),gel(x,4)): gen_0; break;
    1865             : 
    1866             :     case t_POLMOD:
    1867       81655 :       retmkpolmod(gneg_i(gel(x,2)), RgX_copy(gel(x,1)));
    1868             : 
    1869       85015 :     case t_FFELT: return FF_neg_i(x);
    1870             : 
    1871         637 :     case t_QUAD: y=cgetg(4,t_QUAD);
    1872         637 :       gel(y,1) = gel(x,1);
    1873         637 :       gel(y,2) = gneg_i(gel(x,2));
    1874         637 :       gel(y,3) = gneg_i(gel(x,3)); break;
    1875             : 
    1876             :     case t_VEC: case t_COL: case t_MAT:
    1877       27524 :       y = cgetg_copy(x, &lx);
    1878       27524 :       for (i=1; i<lx; i++) gel(y,i) = gneg_i(gel(x,i));
    1879       27524 :       break;
    1880             : 
    1881             :     case t_POL: case t_SER:
    1882     6700337 :       y = cgetg_copy(x, &lx); y[1]=x[1];
    1883     6700337 :       for (i=2; i<lx; i++) gel(y,i) = gneg_i(gel(x,i));
    1884     6700337 :       break;
    1885             : 
    1886             :     case t_RFRAC:
    1887     5039411 :       y = cgetg(3, t_RFRAC);
    1888     5039411 :       gel(y,1) = gneg_i(gel(x,1));
    1889     5039411 :       gel(y,2) = gel(x,2); break;
    1890             : 
    1891             :     default:
    1892           0 :       pari_err_TYPE("gneg_i",x);
    1893             :       return NULL; /* LCOV_EXCL_LINE */
    1894             :   }
    1895    17478584 :   return y;
    1896             : }
    1897             : 
    1898             : /******************************************************************/
    1899             : /*                                                                */
    1900             : /*                       ABSOLUTE VALUE                           */
    1901             : /*    Create abs(x) if x is integer, real, fraction or complex.   */
    1902             : /*                       Error otherwise.                         */
    1903             : /*                                                                */
    1904             : /******************************************************************/
    1905             : static int
    1906           0 : is_negative(GEN x) {
    1907           0 :   switch(typ(x))
    1908             :   {
    1909             :     case t_INT: case t_REAL:
    1910           0 :       return (signe(x) < 0);
    1911             :     case t_FRAC:
    1912           0 :       return (signe(gel(x,1)) < 0);
    1913             :   }
    1914           0 :   return 0;
    1915             : }
    1916             : 
    1917             : GEN
    1918    10359516 : gabs(GEN x, long prec)
    1919             : {
    1920             :   long lx, i;
    1921             :   pari_sp av, tetpil;
    1922             :   GEN y,p1;
    1923             : 
    1924    10359516 :   switch(typ(x))
    1925             :   {
    1926             :     case t_INT: case t_REAL:
    1927     7788232 :       return mpabs(x);
    1928             : 
    1929             :     case t_FRAC:
    1930        4389 :       return absfrac(x);
    1931             : 
    1932             :     case t_COMPLEX:
    1933     2558467 :       av=avma; p1=cxnorm(x);
    1934     2558467 :       switch(typ(p1))
    1935             :       {
    1936             :         case t_INT:
    1937         847 :           if (!Z_issquareall(p1, &y)) break;
    1938         749 :           return gerepileupto(av, y);
    1939             :         case t_FRAC: {
    1940             :           GEN a,b;
    1941        1540 :           if (!Z_issquareall(gel(p1,1), &a)) break;
    1942         322 :           if (!Z_issquareall(gel(p1,2), &b)) break;
    1943           0 :           return gerepileupto(av, gdiv(a,b));
    1944             :         }
    1945             :       }
    1946     2557718 :       tetpil=avma;
    1947     2557718 :       return gerepile(av,tetpil,gsqrt(p1,prec));
    1948             : 
    1949             :     case t_QUAD:
    1950          21 :       av = avma;
    1951          21 :       return gerepileuptoleaf(av, gabs(quadtofp(x, prec), prec));
    1952             : 
    1953             :     case t_POL:
    1954           0 :       lx = lg(x); if (lx<=2) return RgX_copy(x);
    1955           0 :       return is_negative(gel(x,lx-1))? gneg(x): RgX_copy(x);
    1956             : 
    1957             :     case t_SER:
    1958           7 :      if (!signe(x)) pari_err_DOMAIN("abs", "argument", "=", gen_0, x);
    1959           7 :      if (valp(x)) pari_err_DOMAIN("abs", "series valuation", "!=", gen_0, x);
    1960           0 :      return is_negative(gel(x,2))? gneg(x): gcopy(x);
    1961             : 
    1962             :     case t_VEC: case t_COL: case t_MAT:
    1963        8400 :       y = cgetg_copy(x, &lx);
    1964        8400 :       for (i=1; i<lx; i++) gel(y,i) = gabs(gel(x,i),prec);
    1965        8400 :       return y;
    1966             :   }
    1967           0 :   pari_err_TYPE("gabs",x);
    1968             :   return NULL; /* LCOV_EXCL_LINE */
    1969             : }
    1970             : 
    1971             : GEN
    1972           7 : gmax(GEN x, GEN y) { return gcopy(gmax_shallow(x,y)); }
    1973             : GEN
    1974           0 : gmaxgs(GEN x, long s) { return (gcmpsg(s,x)>=0)? stoi(s): gcopy(x); }
    1975             : 
    1976             : GEN
    1977        1155 : gmin(GEN x, GEN y) { return gcopy(gmin_shallow(x,y)); }
    1978             : GEN
    1979           0 : gmings(GEN x, long s) { return (gcmpsg(s,x)>0)? gcopy(x): stoi(s); }
    1980             : 
    1981             : long
    1982        6759 : vecindexmax(GEN x)
    1983             : {
    1984        6759 :   long lx = lg(x), i0, i;
    1985             :   GEN s;
    1986             : 
    1987        6759 :   if (lx==1) pari_err_DOMAIN("vecindexmax", "empty argument", "=", x,x);
    1988        6759 :   switch(typ(x))
    1989             :   {
    1990             :     case t_VEC: case t_COL:
    1991        6759 :       s = gel(x,i0=1);
    1992       21645 :       for (i=2; i<lx; i++)
    1993       14886 :         if (gcmp(gel(x,i),s) > 0) s = gel(x,i0=i);
    1994        6759 :       return i0;
    1995             :     case t_VECSMALL:
    1996           0 :       return vecsmall_indexmax(x);
    1997           0 :     default: pari_err_TYPE("vecindexmax",x);
    1998             :   }
    1999             :   /* LCOV_EXCL_LINE */
    2000           0 :   return 0;
    2001             : }
    2002             : long
    2003       48976 : vecindexmin(GEN x)
    2004             : {
    2005       48976 :   long lx = lg(x), i0, i;
    2006             :   GEN s;
    2007             : 
    2008       48976 :   if (lx==1) pari_err_DOMAIN("vecindexmin", "empty argument", "=", x,x);
    2009       48976 :   switch(typ(x))
    2010             :   {
    2011             :     case t_VEC: case t_COL:
    2012       48976 :       s = gel(x,i0=1);
    2013      210883 :       for (i=2; i<lx; i++)
    2014      161907 :         if (gcmp(gel(x,i),s) < 0) s = gel(x,i0=i);
    2015       48976 :       return i0;
    2016             :     case t_VECSMALL:
    2017           0 :       return vecsmall_indexmin(x);
    2018           0 :     default: pari_err_TYPE("vecindexmin",x);
    2019             :   }
    2020             :   /* LCOV_EXCL_LINE */
    2021           0 :   return 0;
    2022             : }
    2023             : 
    2024             : GEN
    2025        2826 : vecmax0(GEN x, GEN *pi)
    2026             : {
    2027        2826 :   long i, lx = lg(x), tx = typ(x);
    2028        2826 :   if (!is_matvec_t(tx) && tx != t_VECSMALL) return gcopy(x);
    2029        2812 :   if (lx==1) pari_err_DOMAIN("vecmax", "empty argument", "=", x,x);
    2030        2791 :   switch(typ(x))
    2031             :   {
    2032             :     case t_VEC: case t_COL:
    2033        2352 :       i = vecindexmax(x); if (pi) *pi = utoipos(i);
    2034        2352 :       return gcopy(gel(x,i));
    2035             :     case t_MAT: {
    2036         425 :       long j, i0 = 1, j0 = 1, lx2 = lgcols(x);
    2037             :       GEN s;
    2038         425 :       if (lx2 == 1) pari_err_DOMAIN("vecmax", "empty argument", "=", x,x);
    2039         418 :       s = gcoeff(x,i0,j0); i = 2;
    2040        1660 :       for (j=1; j<lx; j++,i=1)
    2041             :       {
    2042        1242 :         GEN c = gel(x,j);
    2043       24574 :         for (; i<lx2; i++)
    2044       23332 :           if (gcmp(gel(c,i),s) > 0) { s = gel(c,i); j0=j; i0=i; }
    2045             :       }
    2046         418 :       if (pi) *pi = mkvec2(utoipos(i0), utoipos(j0));
    2047         418 :       return gcopy(s);
    2048             :     }
    2049             :     case t_VECSMALL:
    2050          14 :       i = vecsmall_indexmax(x); if (pi) *pi = utoipos(i);
    2051          14 :       return stoi(x[i]);
    2052             :   }
    2053             :   return NULL;/*LCOV_EXCL_LINE*/
    2054             : }
    2055             : GEN
    2056       17014 : vecmin0(GEN x, GEN *pi)
    2057             : {
    2058       17014 :   long i, lx = lg(x), tx = typ(x);
    2059       17014 :   if (!is_matvec_t(tx) && tx != t_VECSMALL) return gcopy(x);
    2060       17000 :   if (lx==1) pari_err_DOMAIN("vecmin", "empty argument", "=", x,x);
    2061       16986 :   switch(typ(x))
    2062             :   {
    2063             :     case t_VEC: case t_COL:
    2064       16958 :       i = vecindexmin(x); if (pi) *pi = utoipos(i);
    2065       16958 :       return gcopy(gel(x,i));
    2066             :     case t_MAT: {
    2067          14 :       long j, i0 = 1, j0 = 1, lx2 = lgcols(x);
    2068             :       GEN s;
    2069          14 :       if (lx2 == 1) pari_err_DOMAIN("vecmin", "empty argument", "=", x,x);
    2070          14 :       s = gcoeff(x,i0,j0); i = 2;
    2071          42 :       for (j=1; j<lx; j++,i=1)
    2072             :       {
    2073          28 :         GEN c = gel(x,j);
    2074          70 :         for (; i<lx2; i++)
    2075          42 :           if (gcmp(gel(c,i),s) < 0) { s = gel(c,i); j0=j; i0=i; }
    2076             :       }
    2077          14 :       if (pi) *pi = mkvec2(utoipos(i0), utoipos(j0));
    2078          14 :       return gcopy(s);
    2079             :     }
    2080             :     case t_VECSMALL:
    2081          14 :       i = vecsmall_indexmin(x); if (pi) *pi = utoipos(i);
    2082          14 :       return stoi(x[i]);
    2083             :   }
    2084             :   return NULL;/*LCOV_EXCL_LINE*/
    2085             : }
    2086             : 
    2087             : GEN
    2088        2679 : vecmax(GEN x) { return vecmax0(x, NULL); }
    2089             : GEN
    2090       16937 : vecmin(GEN x) { return vecmin0(x, NULL); }
    2091             : 
    2092             : /*******************************************************************/
    2093             : /*                                                                 */
    2094             : /*                      AFFECT long --> GEN                        */
    2095             : /*         affect long s to GEN x. Useful for initialization.      */
    2096             : /*                                                                 */
    2097             : /*******************************************************************/
    2098             : 
    2099             : static void
    2100           0 : padicaff0(GEN x)
    2101             : {
    2102           0 :   if (signe(gel(x,4)))
    2103             :   {
    2104           0 :     x[1] = evalvalp(valp(x)+precp(x));
    2105           0 :     affsi(0,gel(x,4));
    2106             :   }
    2107           0 : }
    2108             : 
    2109             : void
    2110        1022 : gaffsg(long s, GEN x)
    2111             : {
    2112        1022 :   switch(typ(x))
    2113             :   {
    2114           0 :     case t_INT: affsi(s,x); break;
    2115        1022 :     case t_REAL: affsr(s,x); break;
    2116           0 :     case t_INTMOD: modsiz(s,gel(x,1),gel(x,2)); break;
    2117           0 :     case t_FRAC: affsi(s,gel(x,1)); affsi(1,gel(x,2)); break;
    2118           0 :     case t_COMPLEX: gaffsg(s,gel(x,1)); gaffsg(0,gel(x,2)); break;
    2119             :     case t_PADIC: {
    2120             :       long vx;
    2121             :       GEN y;
    2122           0 :       if (!s) { padicaff0(x); break; }
    2123           0 :       vx = Z_pvalrem(stoi(s), gel(x,2), &y);
    2124           0 :       setvalp(x,vx); modiiz(y,gel(x,3),gel(x,4));
    2125           0 :       break;
    2126             :     }
    2127           0 :     case t_QUAD: gaffsg(s,gel(x,2)); gaffsg(0,gel(x,3)); break;
    2128           0 :     default: pari_err_TYPE2("=",stoi(s),x);
    2129             :   }
    2130        1022 : }
    2131             : 
    2132             : /*******************************************************************/
    2133             : /*                                                                 */
    2134             : /*                     GENERIC AFFECTATION                         */
    2135             : /*         Affect the content of x to y, whenever possible         */
    2136             : /*                                                                 */
    2137             : /*******************************************************************/
    2138             : /* x PADIC, Y INT, return lift(x * Mod(1,Y)) */
    2139             : GEN
    2140        4165 : padic_to_Fp(GEN x, GEN Y) {
    2141        4165 :   pari_sp av = avma;
    2142        4165 :   GEN p = gel(x,2), z;
    2143        4165 :   long vy, vx = valp(x);
    2144        4165 :   if (!signe(Y)) pari_err_INV("padic_to_Fp",Y);
    2145        4165 :   vy = Z_pvalrem(Y,p, &z);
    2146        4165 :   if (vx < 0 || !gequal1(z)) pari_err_OP("",x, mkintmod(gen_1,Y));
    2147        4151 :   if (vx >= vy) { set_avma(av); return gen_0; }
    2148        3815 :   z = gel(x,4);
    2149        3815 :   if (!signe(z) || vy > vx + precp(x)) pari_err_OP("",x, mkintmod(gen_1,Y));
    2150        3815 :   if (vx) z = mulii(z, powiu(p,vx));
    2151        3815 :   return gerepileuptoint(av, remii(z, Y));
    2152             : }
    2153             : ulong
    2154          77 : padic_to_Fl(GEN x, ulong Y) {
    2155          77 :   GEN p = gel(x,2);
    2156             :   ulong u, z;
    2157          77 :   long vy, vx = valp(x);
    2158          77 :   vy = u_pvalrem(Y,p, &u);
    2159          77 :   if (vx < 0 || u != 1) pari_err_OP("",x, mkintmodu(1,Y));
    2160             :   /* Y = p^vy */
    2161          77 :   if (vx >= vy) return 0;
    2162          70 :   z = umodiu(gel(x,4), Y);
    2163          70 :   if (!z || vy > vx + precp(x)) pari_err_OP("",x, mkintmodu(1,Y));
    2164          70 :   if (vx) {
    2165           0 :     ulong pp = p[2];
    2166           0 :     z = Fl_mul(z, upowuu(pp,vx), Y); /* p^vx < p^vy = Y */
    2167             :   }
    2168          70 :   return z;
    2169             : }
    2170             : 
    2171             : static void
    2172           0 : croak(const char *s) {
    2173             :   char *t;
    2174           0 :   t = stack_sprintf("gaffect [overwriting universal object: %s]",s);
    2175           0 :   pari_err_BUG(t);
    2176           0 : }
    2177             : 
    2178             : void
    2179      199239 : gaffect(GEN x, GEN y)
    2180             : {
    2181      199239 :   long vx, i, lx, ly, tx = typ(x), ty = typ(y);
    2182             :   pari_sp av;
    2183             :   GEN p1, num, den;
    2184             : 
    2185      199239 :   if (tx == ty) switch(tx) {
    2186             :     case t_INT:
    2187      318212 :       if (!is_universal_constant(y)) { affii(x,y); return; }
    2188             :       /* y = gen_0, gnil, gen_1 or gen_2 */
    2189           0 :       if (y==gen_0)  croak("gen_0");
    2190           0 :       if (y==gen_1)  croak("gen_1");
    2191           0 :       if (y==gen_m1) croak("gen_m1");
    2192           0 :       if (y==gen_m2) croak("gen_m2");
    2193           0 :       if (y==gen_2)  croak("gen_2");
    2194           0 :       croak("gnil)");
    2195        4382 :     case t_REAL: affrr(x,y); return;
    2196             :     case t_INTMOD:
    2197           0 :       if (!dvdii(gel(x,1),gel(y,1))) pari_err_OP("",x,y);
    2198           0 :       modiiz(gel(x,2),gel(y,1),gel(y,2)); return;
    2199             :     case t_FRAC:
    2200           0 :       affii(gel(x,1),gel(y,1));
    2201           0 :       affii(gel(x,2),gel(y,2)); return;
    2202             :     case t_COMPLEX:
    2203        1680 :       gaffect(gel(x,1),gel(y,1));
    2204        1680 :       gaffect(gel(x,2),gel(y,2)); return;
    2205             :     case t_PADIC:
    2206           0 :       if (!equalii(gel(x,2),gel(y,2))) pari_err_OP("",x,y);
    2207           0 :       modiiz(gel(x,4),gel(y,3),gel(y,4));
    2208           0 :       setvalp(y,valp(x)); return;
    2209             :     case t_QUAD:
    2210           0 :       if (! ZX_equal(gel(x,1),gel(y,1))) pari_err_OP("",x,y);
    2211           0 :       affii(gel(x,2),gel(y,2));
    2212           0 :       affii(gel(x,3),gel(y,3)); return;
    2213             :     case t_VEC: case t_COL: case t_MAT:
    2214       72160 :       lx = lg(x); if (lx != lg(y)) pari_err_DIM("gaffect");
    2215       72160 :       for (i=1; i<lx; i++) gaffect(gel(x,i),gel(y,i));
    2216       72160 :       return;
    2217             :   }
    2218             : 
    2219             :   /* Various conversions. Avoid them, use specialized routines ! */
    2220             : 
    2221        1022 :   if (!is_const_t(ty)) pari_err_TYPE2("=",x,y);
    2222        1022 :   switch(tx)
    2223             :   {
    2224             :     case t_INT:
    2225           0 :       switch(ty)
    2226             :       {
    2227             :         case t_REAL:
    2228           0 :           affir(x,y); break;
    2229             : 
    2230             :         case t_INTMOD:
    2231           0 :           modiiz(x,gel(y,1),gel(y,2)); break;
    2232             : 
    2233             :         case t_COMPLEX:
    2234           0 :           gaffect(x,gel(y,1)); gaffsg(0,gel(y,2)); break;
    2235             : 
    2236             :         case t_PADIC:
    2237           0 :           if (!signe(x)) { padicaff0(y); break; }
    2238           0 :           av = avma;
    2239           0 :           setvalp(y, Z_pvalrem(x,gel(y,2),&p1));
    2240           0 :           affii(modii(p1,gel(y,3)), gel(y,4));
    2241           0 :           set_avma(av); break;
    2242             : 
    2243           0 :         case t_QUAD: gaffect(x,gel(y,2)); gaffsg(0,gel(y,3)); break;
    2244           0 :         default: pari_err_TYPE2("=",x,y);
    2245             :       }
    2246           0 :       break;
    2247             : 
    2248             :     case t_REAL:
    2249        1022 :       switch(ty)
    2250             :       {
    2251        1022 :         case t_COMPLEX: gaffect(x,gel(y,1)); gaffsg(0,gel(y,2)); break;
    2252           0 :         default: pari_err_TYPE2("=",x,y);
    2253             :       }
    2254        1022 :       break;
    2255             : 
    2256             :     case t_FRAC:
    2257           0 :       switch(ty)
    2258             :       {
    2259           0 :         case t_REAL: rdiviiz(gel(x,1),gel(x,2), y); break;
    2260           0 :         case t_INTMOD: av = avma;
    2261           0 :           p1 = Fp_inv(gel(x,2),gel(y,1));
    2262           0 :           affii(modii(mulii(gel(x,1),p1),gel(y,1)), gel(y,2));
    2263           0 :           set_avma(av); break;
    2264           0 :         case t_COMPLEX: gaffect(x,gel(y,1)); gaffsg(0,gel(y,2)); break;
    2265             :         case t_PADIC:
    2266           0 :           if (!signe(gel(x,1))) { padicaff0(y); break; }
    2267           0 :           num = gel(x,1);
    2268           0 :           den = gel(x,2);
    2269           0 :           av = avma; vx = Z_pvalrem(num, gel(y,2), &num);
    2270           0 :           if (!vx) vx = -Z_pvalrem(den,gel(y,2),&den);
    2271           0 :           setvalp(y,vx);
    2272           0 :           p1 = mulii(num,Fp_inv(den,gel(y,3)));
    2273           0 :           affii(modii(p1,gel(y,3)), gel(y,4)); set_avma(av); break;
    2274           0 :         case t_QUAD: gaffect(x,gel(y,2)); gaffsg(0,gel(y,3)); break;
    2275           0 :         default: pari_err_TYPE2("=",x,y);
    2276             :       }
    2277           0 :       break;
    2278             : 
    2279             :     case t_COMPLEX:
    2280           0 :       if (!gequal0(gel(x,2))) pari_err_TYPE2("=",x,y);
    2281           0 :       gaffect(gel(x,1), y);
    2282           0 :       break;
    2283             : 
    2284             :     case t_PADIC:
    2285           0 :       switch(ty)
    2286             :       {
    2287             :         case t_INTMOD:
    2288           0 :           av = avma; affii(padic_to_Fp(x, gel(y,1)), gel(y,2));
    2289           0 :           set_avma(av); break;
    2290           0 :         default: pari_err_TYPE2("=",x,y);
    2291             :       }
    2292           0 :       break;
    2293             : 
    2294             :     case t_QUAD:
    2295           0 :       switch(ty)
    2296             :       {
    2297             :         case t_INT: case t_INTMOD: case t_FRAC: case t_PADIC:
    2298           0 :           pari_err_TYPE2("=",x,y);
    2299             : 
    2300             :         case t_REAL:
    2301           0 :           av = avma; affgr(quadtofp(x,realprec(y)), y); set_avma(av); break;
    2302             :         case t_COMPLEX:
    2303           0 :           ly = precision(y); if (!ly) pari_err_TYPE2("=",x,y);
    2304           0 :           av = avma; gaffect(quadtofp(x,ly), y); set_avma(av); break;
    2305           0 :         default: pari_err_TYPE2("=",x,y);
    2306             :       }
    2307           0 :     default: pari_err_TYPE2("=",x,y);
    2308             :   }
    2309             : }
    2310             : 
    2311             : /*******************************************************************/
    2312             : /*                                                                 */
    2313             : /*           CONVERSION QUAD --> REAL, COMPLEX OR P-ADIC           */
    2314             : /*                                                                 */
    2315             : /*******************************************************************/
    2316             : GEN
    2317         119 : quadtofp(GEN x, long prec)
    2318             : {
    2319         119 :   GEN z, Q, u = gel(x,2), v = gel(x,3);
    2320             :   pari_sp av;
    2321         119 :   if (prec < LOWDEFAULTPREC) prec = LOWDEFAULTPREC;
    2322         119 :   if (isintzero(v)) return cxcompotor(u, prec);
    2323         119 :   av = avma; Q = gel(x,1);
    2324         119 :   z = itor(quad_disc(x), prec);
    2325         119 :   if (signe(gel(Q,2)) < 0) /* Q[2] = -D/4 or (1-D)/4 */
    2326             :   {
    2327         119 :     z = subri(sqrtr(z), gel(Q,3));
    2328         119 :     shiftr_inplace(z, -1);
    2329             :   }
    2330             :   else
    2331             :   {
    2332           0 :     z = sqrtr_abs(z); shiftr_inplace(z, -1);
    2333           0 :     z = mkcomplex(gmul2n(negi(gel(Q,3)),-1), z);
    2334             :   }/* z = (-b + sqrt(D)) / 2 */
    2335         119 :   return gerepileupto(av, gadd(u, gmul(v,z)));
    2336             : }
    2337             : 
    2338             : static GEN
    2339          14 : qtop(GEN x, GEN p, long d)
    2340             : {
    2341          14 :   GEN z, D, P, b, u = gel(x,2), v = gel(x,3);
    2342             :   pari_sp av;
    2343          14 :   if (gequal0(v)) return cvtop(u, p, d);
    2344          14 :   P = gel(x,1);
    2345          14 :   b = gel(P,3);
    2346          14 :   av = avma; D = quad_disc(x);
    2347          14 :   if (absequaliu(p,2)) d += 2;
    2348          14 :   z = Qp_sqrt(cvtop(D,p,d));
    2349          14 :   if (!z) pari_err_SQRTN("Qp_sqrt",D);
    2350           0 :   z = gmul2n(gsub(z, b), -1);
    2351             : 
    2352           0 :   z = gadd(u, gmul(v, z));
    2353           0 :   if (typ(z) != t_PADIC) /* t_INTMOD for t_QUAD of t_INTMODs... */
    2354           0 :     z = cvtop(z, p, d);
    2355           0 :   return gerepileupto(av, z);
    2356             : }
    2357             : static GEN
    2358          14 : ctop(GEN x, GEN p, long d)
    2359             : {
    2360          14 :   pari_sp av = avma;
    2361          14 :   GEN z, u = gel(x,1), v = gel(x,2);
    2362          14 :   if (isrationalzero(v)) return cvtop(u, p, d);
    2363          14 :   z = Qp_sqrt(cvtop(gen_m1, p, d - gvaluation(v, p))); /* = I */
    2364          14 :   if (!z) pari_err_SQRTN("Qp_sqrt",gen_m1);
    2365             : 
    2366          14 :   z = gadd(u, gmul(v, z));
    2367          14 :   if (typ(z) != t_PADIC) /* t_INTMOD for t_COMPLEX of t_INTMODs... */
    2368           0 :     z = cvtop(z, p, d);
    2369          14 :   return gerepileupto(av, z);
    2370             : }
    2371             : 
    2372             : /* cvtop2(stoi(s), y) */
    2373             : GEN
    2374           0 : cvstop2(long s, GEN y)
    2375             : {
    2376           0 :   GEN z, p = gel(y,2);
    2377           0 :   long v, d = signe(gel(y,4))? precp(y): 0;
    2378           0 :   if (!s) return zeropadic(p, d);
    2379           0 :   v = z_pvalrem(s, p, &s);
    2380           0 :   if (d <= 0) return zeropadic(p, v);
    2381           0 :   z = cgetg(5, t_PADIC);
    2382           0 :   z[1] = evalprecp(d) | evalvalp(v);
    2383           0 :   gel(z,2) = p;
    2384           0 :   gel(z,3) = gel(y,3);
    2385           0 :   gel(z,4) = modsi(s, gel(y,3)); return z;
    2386             : }
    2387             : 
    2388             : /* cvtop(x, gel(y,2), precp(y)), shallow */
    2389             : GEN
    2390      278781 : cvtop2(GEN x, GEN y)
    2391             : {
    2392      278781 :   GEN z, p = gel(y,2);
    2393      278781 :   long v, d = signe(gel(y,4))? precp(y): 0;
    2394      278781 :   switch(typ(x))
    2395             :   {
    2396             :     case t_INT:
    2397      245923 :       if (!signe(x)) return zeropadic(p, d);
    2398      245923 :       if (d <= 0) return zeropadic(p, Z_pval(x,p));
    2399      241128 :       v = Z_pvalrem(x, p, &x);
    2400      241097 :       z = cgetg(5, t_PADIC);
    2401      241117 :       z[1] = evalprecp(d) | evalvalp(v);
    2402      241121 :       gel(z,2) = p;
    2403      241121 :       gel(z,3) = gel(y,3);
    2404      241121 :       gel(z,4) = modii(x, gel(y,3)); return z;
    2405             : 
    2406             :     case t_INTMOD:
    2407           0 :       v = Z_pval(gel(x,1),p); if (v > d) v = d;
    2408           0 :       return cvtop(gel(x,2), p, v);
    2409             : 
    2410             :     case t_FRAC:
    2411             :     {
    2412             :       GEN num, den;
    2413       32837 :       if (d <= 0) return zeropadic(p, Q_pval(x,p));
    2414       31556 :       num = gel(x,1); v = Z_pvalrem(num, p, &num);
    2415       31556 :       den = gel(x,2); if (!v) v = -Z_pvalrem(den, p, &den);
    2416       31556 :       z = cgetg(5, t_PADIC);
    2417       31556 :       z[1] = evalprecp(d) | evalvalp(v);
    2418       31556 :       gel(z,2) = p;
    2419       31556 :       gel(z,3) = gel(y,3);
    2420       31556 :       if (!is_pm1(den)) num = mulii(num, Fp_inv(den, gel(y,3)));
    2421       31556 :       gel(z,4) = modii(num, gel(y,3)); return z;
    2422             :     }
    2423           7 :     case t_COMPLEX: return ctop(x, p, d);
    2424          14 :     case t_QUAD:    return qtop(x, p, d);
    2425             :   }
    2426           0 :   pari_err_TYPE("cvtop2",x);
    2427             :   return NULL; /* LCOV_EXCL_LINE */
    2428             : }
    2429             : 
    2430             : /* assume is_const_t(tx) */
    2431             : GEN
    2432       47605 : cvtop(GEN x, GEN p, long d)
    2433             : {
    2434             :   GEN z;
    2435             :   long v;
    2436             : 
    2437       47605 :   if (typ(p) != t_INT) pari_err_TYPE("cvtop",p);
    2438       47605 :   switch(typ(x))
    2439             :   {
    2440             :     case t_INT:
    2441       32618 :       if (!signe(x)) return zeropadic(p, d);
    2442       31421 :       if (d <= 0) return zeropadic(p, Z_pval(x,p));
    2443       31414 :       v = Z_pvalrem(x, p, &x);
    2444       31414 :       z = cgetg(5, t_PADIC);
    2445       31414 :       z[1] = evalprecp(d) | evalvalp(v);
    2446       31414 :       gel(z,2) = icopy(p);
    2447       31414 :       gel(z,3) = powiu(p, d);
    2448       31414 :       gel(z,4) = modii(x, gel(z,3)); return z; /* not memory-clean */
    2449             : 
    2450             :     case t_INTMOD:
    2451          28 :       v = Z_pval(gel(x,1),p); if (v > d) v = d;
    2452          28 :       return cvtop(gel(x,2), p, v);
    2453             : 
    2454             :     case t_FRAC:
    2455             :     {
    2456             :       GEN num, den;
    2457        7196 :       if (d <= 0) return zeropadic(p, Q_pval(x,p));
    2458        7196 :       num = gel(x,1); v = Z_pvalrem(num, p, &num);
    2459        7196 :       den = gel(x,2); if (!v) v = -Z_pvalrem(den, p, &den);
    2460        7196 :       z = cgetg(5, t_PADIC);
    2461        7196 :       z[1] = evalprecp(d) | evalvalp(v);
    2462        7196 :       gel(z,2) = icopy(p);
    2463        7196 :       gel(z,3) = powiu(p, d);
    2464        7196 :       if (!is_pm1(den)) num = mulii(num, Fp_inv(den, gel(z,3)));
    2465        7196 :       gel(z,4) = modii(num, gel(z,3)); return z; /* not memory-clean */
    2466             :     }
    2467           7 :     case t_COMPLEX: return ctop(x, p, d);
    2468             :     case t_PADIC:
    2469        7756 :       p = gel(x,2); /* override */
    2470        7756 :       if (!signe(gel(x,4))) return zeropadic(p, d);
    2471        7756 :       z = cgetg(5,t_PADIC);
    2472        7756 :       z[1] = x[1]; setprecp(z,d);
    2473        7756 :       gel(z,2) = icopy(p);
    2474        7756 :       gel(z,3) = powiu(p, d);
    2475        7756 :       gel(z,4) = modii(gel(x,4), gel(z,3)); return z;
    2476             : 
    2477           0 :     case t_QUAD: return qtop(x, p, d);
    2478             :   }
    2479           0 :   pari_err_TYPE("cvtop",x);
    2480             :   return NULL; /* LCOV_EXCL_LINE */
    2481             : }
    2482             : 
    2483             : GEN
    2484          70 : gcvtop(GEN x, GEN p, long r)
    2485             : {
    2486             :   long i, lx;
    2487             :   GEN y;
    2488             : 
    2489          70 :   switch(typ(x))
    2490             :   {
    2491             :     case t_POL: case t_SER:
    2492          21 :       y = cgetg_copy(x, &lx); y[1] = x[1];
    2493          21 :       for (i=2; i<lx; i++) gel(y,i) = gcvtop(gel(x,i),p,r);
    2494          21 :       return y;
    2495             :     case t_POLMOD: case t_RFRAC: case t_VEC: case t_COL: case t_MAT:
    2496           0 :       y = cgetg_copy(x, &lx);
    2497           0 :       for (i=1; i<lx; i++) gel(y,i) = gcvtop(gel(x,i),p,r);
    2498           0 :       return y;
    2499             :   }
    2500          49 :   return cvtop(x,p,r);
    2501             : }
    2502             : 
    2503             : long
    2504   127911459 : gexpo_safe(GEN x)
    2505             : {
    2506   127911459 :   long tx = typ(x), lx, e, f, i;
    2507             : 
    2508   127911459 :   switch(tx)
    2509             :   {
    2510             :     case t_INT:
    2511    28086755 :       return expi(x);
    2512             : 
    2513             :     case t_FRAC:
    2514      322559 :       return expi(gel(x,1)) - expi(gel(x,2));
    2515             : 
    2516             :     case t_REAL:
    2517    67284714 :       return expo(x);
    2518             : 
    2519             :     case t_COMPLEX:
    2520    20774461 :       e = gexpo(gel(x,1));
    2521    20774461 :       f = gexpo(gel(x,2)); return maxss(e, f);
    2522             : 
    2523             :     case t_QUAD: {
    2524          35 :       GEN p = gel(x,1); /* mod = X^2 + {0,1}* X - {D/4, (1-D)/4})*/
    2525          35 :       long d = 1 + expi(gel(p,2))/2; /* ~ expo(sqrt(D)) */
    2526          35 :       e = gexpo(gel(x,2));
    2527          35 :       f = gexpo(gel(x,3)) + d; return maxss(e, f);
    2528             :     }
    2529             :     case t_POL: case t_SER:
    2530    10996581 :       lx = lg(x); f = -(long)HIGHEXPOBIT;
    2531    10996581 :       for (i=2; i<lx; i++) { e=gexpo(gel(x,i)); if (e>f) f=e; }
    2532    10996581 :       return f;
    2533             :     case t_VEC: case t_COL: case t_MAT:
    2534      446277 :       lx = lg(x); f = -(long)HIGHEXPOBIT;
    2535      446277 :       for (i=1; i<lx; i++) { e=gexpo(gel(x,i)); if (e>f) f=e; }
    2536      446277 :       return f;
    2537             :   }
    2538          77 :   return -1-(long)HIGHEXPOBIT;
    2539             : }
    2540             : long
    2541   127868927 : gexpo(GEN x)
    2542             : {
    2543   127868927 :   long e = gexpo_safe(x);
    2544   127868927 :   if (e < -(long)HIGHEXPOBIT) pari_err_TYPE("gexpo",x);
    2545   127868920 :   return e;
    2546             : }
    2547             : GEN
    2548        1421 : gpexponent(GEN x)
    2549             : {
    2550        1421 :   long e = gexpo(x);
    2551        1421 :   return e == -(long)HIGHEXPOBIT? mkmoo(): stoi(e);
    2552             : }
    2553             : 
    2554             : long
    2555           7 : sizedigit(GEN x)
    2556             : {
    2557           7 :   return gequal0(x)? 0: (long) ((gexpo(x)+1) * LOG10_2) + 1;
    2558             : }
    2559             : 
    2560             : /* normalize series. avma is not updated */
    2561             : GEN
    2562     7712451 : normalize(GEN x)
    2563             : {
    2564     7712451 :   long i, lx = lg(x), vx=varn(x), vp=valp(x);
    2565             :   GEN y, z;
    2566             : 
    2567     7712451 :   if (typ(x) != t_SER) pari_err_TYPE("normalize",x);
    2568     7712451 :   if (lx == 2) { setsigne(x,0); return x; }
    2569     7712094 :   if (lx == 3) {
    2570      172521 :     z = gel(x,2);
    2571      172521 :     if (!gequal0(z)) { setsigne(x,1); return x; }
    2572       27782 :     if (isrationalzero(z)) return zeroser(vx,vp+1);
    2573        6285 :     if (isexactzero(z)) {
    2574             :       /* dangerous case: already normalized ? */
    2575          21 :       if (!signe(x)) return x;
    2576          14 :       setvalp(x,vp+1); /* no: normalize */
    2577             :     }
    2578        6278 :     setsigne(x,0); return x;
    2579             :   }
    2580     7811492 :   for (i=2; i<lx; i++)
    2581     7764858 :     if (! isrationalzero(gel(x,i))) break;
    2582     7539573 :   if (i == lx) return zeroser(vx,lx-2+vp);
    2583     7492939 :   z = gel(x,i);
    2584     7492939 :   while (i<lx && isexactzero(gel(x,i))) i++;
    2585     7492939 :   if (i == lx)
    2586             :   {
    2587         259 :     i -= 3; y = x + i;
    2588         259 :     stackdummy((pari_sp)y, (pari_sp)x);
    2589         259 :     gel(y,2) = z;
    2590         259 :     y[1] = evalsigne(0) | evalvalp(lx-2+vp) | evalvarn(vx);
    2591         259 :     y[0] = evaltyp(t_SER) | _evallg(3);
    2592         259 :     return y;
    2593             :   }
    2594             : 
    2595     7492680 :   i -= 2; y = x + i; lx -= i;
    2596     7492680 :   y[1] = evalsigne(1) | evalvalp(vp+i) | evalvarn(vx);
    2597     7492680 :   y[0] = evaltyp(t_SER) | evallg(lx);
    2598             : 
    2599     7492680 :   stackdummy((pari_sp)y, (pari_sp)x);
    2600     7512288 :   for (i = 2; i < lx; i++)
    2601     7511135 :     if (!gequal0(gel(y, i))) return y;
    2602        1153 :   setsigne(y, 0); return y;
    2603             : }
    2604             : 
    2605             : GEN
    2606           0 : normalizepol_approx(GEN x, long lx)
    2607             : {
    2608             :   long i;
    2609           0 :   for (i = lx-1; i>1; i--)
    2610           0 :     if (! gequal0(gel(x,i))) break;
    2611           0 :   stackdummy((pari_sp)(x + lg(x)), (pari_sp)(x + i+1));
    2612           0 :   setlg(x, i+1); setsigne(x, i!=1); return x;
    2613             : }
    2614             : 
    2615             : GEN
    2616   202676951 : normalizepol_lg(GEN x, long lx)
    2617             : {
    2618   202676951 :   long i, LX = 0;
    2619   202676951 :   GEN KEEP = NULL;
    2620             : 
    2621   243894666 :   for (i = lx-1; i>1; i--)
    2622             :   {
    2623   227024184 :     GEN z = gel(x,i);
    2624   227024184 :     if (! gequal0(z) ) {
    2625   185806879 :       if (!LX) LX = i+1;
    2626   185806879 :       stackdummy((pari_sp)(x + lg(x)), (pari_sp)(x + LX));
    2627   185808361 :       x[0] = evaltyp(t_POL) | evallg(LX);
    2628   185810584 :       setsigne(x,1); return x;
    2629    41217717 :     } else if (!isexactzero(z)) {
    2630      294830 :       if (!LX) LX = i+1; /* to be kept as leading coeff */
    2631    40922885 :     } else if (!isrationalzero(z))
    2632      693881 :       KEEP = z; /* to be kept iff all other coeffs are exact 0s */
    2633             :   }
    2634    16870482 :   if (!LX) {
    2635    16811846 :     if (KEEP) { /* e.g. Pol(Mod(0,2)) */
    2636      348666 :       gel(x,2) = KEEP;
    2637      348666 :       LX = 3;
    2638             :     } else
    2639    16463180 :       LX = 2; /* Pol(0) */
    2640             :   }
    2641    16870482 :   stackdummy((pari_sp)(x + lg(x)), (pari_sp)(x + LX));
    2642    16870482 :   x[0] = evaltyp(t_POL) | evallg(LX);
    2643    16870482 :   setsigne(x,0); return x;
    2644             : }
    2645             : 
    2646             : /* normalize polynomial x in place */
    2647             : GEN
    2648      237996 : normalizepol(GEN x)
    2649             : {
    2650      237996 :   return normalizepol_lg(x, lg(x));
    2651             : }
    2652             : 
    2653             : int
    2654     4294576 : gsigne(GEN x)
    2655             : {
    2656     4294576 :   switch(typ(x))
    2657             :   {
    2658     4058109 :     case t_INT: case t_REAL: return signe(x);
    2659      233464 :     case t_FRAC: return signe(gel(x,1));
    2660             :     case t_QUAD:
    2661             :     {
    2662         126 :       pari_sp av = avma;
    2663         126 :       GEN T = gel(x,1), a = gel(x,2), b = gel(x,3);
    2664             :       long sa, sb;
    2665         126 :       if (signe(gel(T,2)) > 0) break;
    2666         112 :       a = gmul2n(a,1);
    2667         112 :       if (signe(gel(T,3))) a = gadd(a,b);
    2668             :       /* a + b sqrt(D) > 0 ? */
    2669         112 :       sa = gsigne(a);
    2670         112 :       sb = gsigne(b); if (sa == sb) return gc_int(av,sa);
    2671          91 :       if (sa == 0) return gc_int(av,sb);
    2672          84 :       if (sb == 0) return gc_int(av,sa);
    2673             :       /* different signs, take conjugate expression */
    2674          84 :       sb = gsigne(gsub(gsqr(a), gmul(quad_disc(x), gsqr(b))));
    2675          84 :       return gc_int(av, sb*sa);
    2676             :     }
    2677        2877 :     case t_INFINITY: return inf_get_sign(x);
    2678             :   }
    2679          14 :   pari_err_TYPE("gsigne",x);
    2680             :   return 0; /* LCOV_EXCL_LINE */
    2681             : }
    2682             : 
    2683             : /*******************************************************************/
    2684             : /*                                                                 */
    2685             : /*                              LISTS                              */
    2686             : /*                                                                 */
    2687             : /*******************************************************************/
    2688             : /* make sure L can hold l elements, at least doubling the previous max number
    2689             :  * of components. */
    2690             : static void
    2691      786023 : ensure_nb(GEN L, long l)
    2692             : {
    2693      786023 :   long nmax = list_nmax(L), i, lw;
    2694             :   GEN v, w;
    2695      786023 :   if (l <= nmax) return;
    2696         322 :   if (nmax)
    2697             :   {
    2698         273 :     nmax <<= 1;
    2699         273 :     if (l > nmax) nmax = l;
    2700         273 :     w = list_data(L); lw = lg(w);
    2701         273 :     v = newblock(nmax+1);
    2702         273 :     v[0] = w[0];
    2703         273 :     for (i=1; i < lw; i++) gel(v,i) = gel(w, i);
    2704         273 :     killblock(w);
    2705             :   }
    2706             :   else /* unallocated */
    2707             :   {
    2708          49 :     nmax = 32;
    2709          49 :     if (list_data(L))
    2710           0 :       pari_err(e_MISC, "store list in variable before appending elements");
    2711          49 :     v = newblock(nmax+1);
    2712          49 :     v[0] = evaltyp(t_VEC) | _evallg(1);
    2713             :   }
    2714         322 :   list_data(L) = v;
    2715         322 :   L[1] = evaltyp(list_typ(L))|evallg(nmax);
    2716             : }
    2717             : 
    2718             : void
    2719           7 : listkill(GEN L)
    2720             : {
    2721             : 
    2722           7 :   if (typ(L) != t_LIST) pari_err_TYPE("listkill",L);
    2723           7 :   if (list_nmax(L)) {
    2724           7 :     GEN v = list_data(L);
    2725           7 :     long i, l = lg(v);
    2726           7 :     for (i=1; i<l; i++) gunclone_deep(gel(v,i));
    2727           7 :     killblock(v);
    2728           7 :     L[1] = evaltyp(list_typ(L));
    2729           7 :     list_data(L) = NULL;
    2730             :   }
    2731           7 : }
    2732             : 
    2733             : GEN
    2734         799 : mklist_typ(long t)
    2735             : {
    2736         799 :   GEN L = cgetg(3,t_LIST);
    2737         799 :   L[1] = evaltyp(t);
    2738         799 :   list_data(L) = NULL; return L;
    2739             : }
    2740             : 
    2741             : GEN
    2742         750 : mklist(void)
    2743             : {
    2744         750 :   return mklist_typ(t_LIST_RAW);
    2745             : }
    2746             : 
    2747             : GEN
    2748          42 : mkmap(void)
    2749             : {
    2750          42 :   return mklist_typ(t_LIST_MAP);
    2751             : }
    2752             : 
    2753             : /* return a list with single element x, allocated on stack */
    2754             : GEN
    2755          49 : mklistcopy(GEN x)
    2756             : {
    2757          49 :   GEN y = mklist();
    2758          49 :   list_data(y) = mkveccopy(x);
    2759          49 :   return y;
    2760             : }
    2761             : 
    2762             : GEN
    2763           7 : listcreate_gp(long n)
    2764             : {
    2765           7 :   (void) n; return mklist();
    2766             : }
    2767             : 
    2768             : GEN
    2769      751051 : listput(GEN L, GEN x, long index)
    2770             : {
    2771             :   long l;
    2772             :   GEN z;
    2773             : 
    2774      751051 :   if (index < 0) pari_err_COMPONENT("listput", "<", gen_0, stoi(index));
    2775      751044 :   z = list_data(L);
    2776      751044 :   l = z? lg(z): 1;
    2777             : 
    2778      751044 :   x = gclone(x);
    2779      751044 :   if (!index || index >= l)
    2780             :   {
    2781      751023 :     ensure_nb(L, l);
    2782      751023 :     z = list_data(L); /* it may change ! */
    2783      751023 :     index = l;
    2784      751023 :     l++;
    2785             :   } else
    2786          21 :     gunclone_deep( gel(z, index) );
    2787      751044 :   gel(z,index) = x;
    2788      751044 :   z[0] = evaltyp(t_VEC) | evallg(l); /*must be after gel(z,index) is set*/
    2789      751044 :   return gel(z,index);
    2790             : }
    2791             : 
    2792             : GEN
    2793      700063 : listput0(GEN L, GEN x, long index)
    2794             : {
    2795      700063 :   if (typ(L) != t_LIST || list_typ(L) != t_LIST_RAW)
    2796          14 :     pari_err_TYPE("listput",L);
    2797      700049 :   return listput(L, x, index);
    2798             : }
    2799             : 
    2800             : GEN
    2801       35028 : listinsert(GEN L, GEN x, long index)
    2802             : {
    2803             :   long l, i;
    2804             :   GEN z;
    2805             : 
    2806       35028 :   if (typ(L) != t_LIST || list_typ(L) != t_LIST_RAW)
    2807          14 :     pari_err_TYPE("listinsert",L);
    2808       35014 :   z = list_data(L); l = z? lg(z): 1;
    2809       35014 :   if (index <= 0) pari_err_COMPONENT("listinsert", "<=", gen_0, stoi(index));
    2810       35007 :   if (index > l) pari_err_COMPONENT("listinsert", ">", stoi(l), stoi(index));
    2811       35000 :   ensure_nb(L, l);
    2812       35000 :   BLOCK_SIGINT_START
    2813       35000 :   z = list_data(L);
    2814       35000 :   for (i=l; i > index; i--) gel(z,i) = gel(z,i-1);
    2815       35000 :   z[0] = evaltyp(t_VEC) | evallg(l+1);
    2816       35000 :   gel(z,index) = gclone(x);
    2817       35000 :   BLOCK_SIGINT_END
    2818       35000 :   return gel(z,index);
    2819             : }
    2820             : 
    2821             : void
    2822       21910 : listpop(GEN L, long index)
    2823             : {
    2824             :   long l, i;
    2825             :   GEN z;
    2826             : 
    2827       21910 :   if (typ(L) != t_LIST) pari_err_TYPE("listinsert",L);
    2828       21910 :   if (index < 0) pari_err_COMPONENT("listpop", "<", gen_0, stoi(index));
    2829       21910 :   z = list_data(L);
    2830       21910 :   if (!z || (l = lg(z)-1) == 0) return;
    2831             : 
    2832       21896 :   if (!index || index > l) index = l;
    2833       21896 :   BLOCK_SIGINT_START
    2834       21896 :   gunclone_deep( gel(z, index) );
    2835       21896 :   z[0] = evaltyp(t_VEC) | evallg(l);
    2836       21896 :   for (i=index; i < l; i++) z[i] = z[i+1];
    2837       21896 :   BLOCK_SIGINT_END
    2838             : }
    2839             : 
    2840             : void
    2841          49 : listpop0(GEN L, long index)
    2842             : {
    2843          49 :   if (typ(L) != t_LIST || list_typ(L) != t_LIST_RAW)
    2844          14 :     pari_err_TYPE("listpop",L);
    2845          35 :   listpop(L, index);
    2846          35 : }
    2847             : 
    2848             : /* return a copy fully allocated on stack. gclone from changevalue is
    2849             :  * supposed to malloc() it */
    2850             : GEN
    2851         431 : gtolist(GEN x)
    2852             : {
    2853             :   GEN y;
    2854             : 
    2855         431 :   if (!x) return mklist();
    2856         301 :   switch(typ(x))
    2857             :   {
    2858             :     case t_VEC: case t_COL:
    2859         245 :       y = mklist();
    2860         245 :       if (lg(x) == 1) return y;
    2861         231 :       list_data(y) = gcopy(x);
    2862         231 :       settyp(list_data(y), t_VEC);
    2863         231 :       return y;
    2864             :     case t_LIST:
    2865           7 :       y = mklist();
    2866           7 :       list_data(y) = list_data(x)? gcopy(list_data(x)): NULL;
    2867           7 :       return y;
    2868             :     default:
    2869          49 :       return mklistcopy(x);
    2870             :   }
    2871             : }
    2872             : 
    2873             : void
    2874          21 : listsort(GEN L, long flag)
    2875             : {
    2876             :   long i, l;
    2877          21 :   pari_sp av = avma;
    2878             :   GEN perm, v, vnew;
    2879             : 
    2880          21 :   if (typ(L) != t_LIST) pari_err_TYPE("listsort",L);
    2881          21 :   v = list_data(L); l = v? lg(v): 1;
    2882          21 :   if (l < 3) return;
    2883          21 :   if (flag)
    2884             :   {
    2885             :     long lnew;
    2886          14 :     perm = gen_indexsort_uniq(L, (void*)&cmp_universal, cmp_nodata);
    2887          14 :     lnew = lg(perm); /* may have changed since 'uniq' */
    2888          14 :     vnew = cgetg(lnew,t_VEC);
    2889          56 :     for (i=1; i<lnew; i++) {
    2890          42 :       long c = perm[i];
    2891          42 :       gel(vnew,i) = gel(v,c);
    2892          42 :       gel(v,c) = NULL;
    2893             :     }
    2894          14 :     if (l != lnew) { /* was shortened */
    2895         105 :       for (i=1; i<l; i++)
    2896          91 :         if (gel(v,i)) gunclone_deep(gel(v,i));
    2897          14 :       l = lnew;
    2898             :     }
    2899             :   }
    2900             :   else
    2901             :   {
    2902           7 :     perm = gen_indexsort(L, (void*)&cmp_universal, cmp_nodata);
    2903           7 :     vnew = cgetg(l,t_VEC);
    2904           7 :     for (i=1; i<l; i++) gel(vnew,i) = gel(v,perm[i]);
    2905             :   }
    2906          21 :   for (i=1; i<l; i++) gel(v,i) = gel(vnew,i);
    2907          21 :   v[0] = vnew[0]; set_avma(av);
    2908             : }

Generated by: LCOV version 1.13