Code coverage tests

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

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

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

LCOV - code coverage report
Current view: top level - basemath - gen2.c (source / functions) Hit Total Coverage
Test: PARI/GP v2.10.0 lcov report (development 22303-eb3e11d) Lines: 1321 1507 87.7 %
Date: 2018-04-20 06:16:30 Functions: 135 146 92.5 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : /* Copyright (C) 2000  The PARI group.
       2             : 
       3             : This file is part of the PARI/GP package.
       4             : 
       5             : PARI/GP is free software; you can redistribute it and/or modify it under the
       6             : terms of the GNU General Public License as published by the Free Software
       7             : Foundation. 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    22750210 : map_proto_lG(long (*f)(GEN), GEN x)
      43             : {
      44    22750210 :   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    22886076 :   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      290762 : _domul(void *data, GEN x, GEN y)
      69             : {
      70      290762 :   GEN (*mul)(GEN,GEN)=(GEN (*)(GEN,GEN)) data;
      71      290762 :   return mul(x,y);
      72             : }
      73             : 
      74             : GEN
      75      309398 : gassoc_proto(GEN (*f)(GEN,GEN), GEN x, GEN y)
      76             : {
      77      309398 :   if (!y)
      78             :   {
      79      309398 :     pari_sp av = avma;
      80      309398 :     switch(typ(x))
      81             :     {
      82             :       case t_LIST:
      83          21 :         x = list_data(x); if (!x) return gen_1;
      84             :       case t_VEC:
      85      309384 :       case t_COL: break;
      86           7 :       default: pari_err_TYPE("association",x);
      87             :     }
      88      309384 :     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     1569919 : cgetp(GEN x)
     100             : {
     101     1569919 :   GEN y = cgetg(5,t_PADIC);
     102     1569920 :   y[1] = (x[1]&PRECPBITS) | _evalvalp(0);
     103     1569920 :   gel(y,2) = icopy(gel(x,2));
     104     1569921 :   gel(y,3) = icopy(gel(x,3));
     105     1569926 :   gel(y,4) = cgeti(lgefint(gel(x,3))); return y;
     106             : }
     107             : 
     108             : /*******************************************************************/
     109             : /*                                                                 */
     110             : /*                            SIZES                                */
     111             : /*                                                                 */
     112             : /*******************************************************************/
     113             : 
     114             : long
     115     4561611 : glength(GEN x)
     116             : {
     117     4561611 :   long tx = typ(x);
     118     4561611 :   switch(tx)
     119             :   {
     120          84 :     case t_INT:  return lgefint(x)-2;
     121             :     case t_LIST: {
     122          21 :       GEN L = list_data(x);
     123          21 :       return L? lg(L)-1: 0;
     124             :     }
     125          14 :     case t_REAL: return signe(x)? lg(x)-2: 0;
     126          11 :     case t_STR:  return strlen( GSTR(x) );
     127        6029 :     case t_VECSMALL: return lg(x)-1;
     128             :   }
     129     4555452 :   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;
     163           7 :       long y = itos(ground(x));
     164           7 :       avma = av; return y;
     165             :     }
     166             :     case t_COMPLEX:
     167           7 :       if (gequal0(gel(x,2))) return gtolong(gel(x,1)); break;
     168             :     case t_QUAD:
     169           7 :       if (gequal0(gel(x,3))) return gtolong(gel(x,2)); break;
     170             :   }
     171           7 :   pari_err_TYPE("gtolong",x);
     172             :   return 0; /* LCOV_EXCL_LINE */
     173             : }
     174             : 
     175             : /*******************************************************************/
     176             : /*                                                                 */
     177             : /*                         COMPARISONS                             */
     178             : /*                                                                 */
     179             : /*******************************************************************/
     180             : int
     181   211646041 : isexactzero(GEN g)
     182             : {
     183             :   long i, lx;
     184   211646041 :   switch (typ(g))
     185             :   {
     186             :     case t_INT:
     187   156351055 :       return !signe(g);
     188             :     case t_INTMOD:
     189     1123205 :       return !signe(gel(g,2));
     190             :     case t_COMPLEX:
     191     2788308 :       return isexactzero(gel(g,1)) && isexactzero(gel(g,2));
     192             :     case t_FFELT:
     193     8107375 :       return FF_equal0(g);
     194             :     case t_QUAD:
     195         399 :       return isexactzero(gel(g,2)) && isexactzero(gel(g,3));
     196             :     case t_POLMOD:
     197      158297 :       return isexactzero(gel(g,2));
     198             :     case t_POL:
     199    29283116 :       lx = lg(g); /* cater for Mod(0,2)*x^0 */
     200    29283116 :       return lx == 2 || (lx == 3 && isexactzero(gel(g,2)));
     201             :     case t_RFRAC:
     202      459806 :       return isexactzero(gel(g,1)); /* may occur: Mod(0,2)/x */
     203             :     case t_VEC: case t_COL: case t_MAT:
     204         350 :       for (i=lg(g)-1; i; i--)
     205         252 :         if (!isexactzero(gel(g,i))) return 0;
     206          98 :       return 1;
     207             :   }
     208    13374368 :   return 0;
     209             : }
     210             : GEN
     211    48247132 : gisexactzero(GEN g)
     212             : {
     213             :   long i, lx;
     214             :   GEN a, b;
     215    48247132 :   switch (typ(g))
     216             :   {
     217             :     case t_INT:
     218    15536270 :       return !signe(g)? g: NULL;
     219             :     case t_INTMOD:
     220     5284048 :       return !signe(gel(g,2))? g: NULL;
     221             :     case t_COMPLEX:
     222        2562 :       a = gisexactzero(gel(g,1)); if (!a) return NULL;
     223         602 :       b = gisexactzero(gel(g,2)); if (!b) return NULL;
     224           0 :       return ggcd(a,b);
     225             :     case t_FFELT:
     226       22225 :       return FF_equal0(g)? g: NULL;
     227             :     case t_QUAD:
     228         518 :       a = gisexactzero(gel(g,2)); if (!a) return NULL;
     229          77 :       b = gisexactzero(gel(g,3)); if (!b) return NULL;
     230           7 :       return ggcd(a,b);
     231             :     case t_POLMOD:
     232       50253 :       return gisexactzero(gel(g,2));
     233             :     case t_POL:
     234    26064885 :       lx = lg(g); /* cater for Mod(0,2)*x^0 */
     235    26064885 :       if (lx == 2) return gen_0;
     236    20919545 :       if (lx == 3) return gisexactzero(gel(g,2));
     237    19029713 :       return NULL;
     238             :     case t_RFRAC:
     239     1193716 :       return gisexactzero(gel(g,1)); /* may occur: Mod(0,2)/x */
     240             :     case t_VEC: case t_COL: case t_MAT:
     241           0 :       a = gen_0;
     242           0 :       for (i=lg(g)-1; i; i--)
     243             :       {
     244           0 :         b = gisexactzero(gel(g,i));
     245           0 :         if (!b) return NULL;
     246           0 :         a = ggcd(a, b);
     247             :       }
     248           0 :       return a;
     249             :   }
     250       92655 :   return NULL;
     251             : }
     252             : 
     253             : int
     254   222408135 : isrationalzero(GEN g)
     255             : {
     256             :   long i;
     257   222408135 :   switch (typ(g))
     258             :   {
     259             :     case t_INT:
     260   138532887 :       return !signe(g);
     261             :     case t_COMPLEX:
     262     5875336 :       return isintzero(gel(g,1)) && isintzero(gel(g,2));
     263             :     case t_QUAD:
     264         798 :       return isintzero(gel(g,2)) && isintzero(gel(g,3));
     265             :     case t_POLMOD:
     266      174660 :       return isrationalzero(gel(g,2));
     267    36640987 :     case t_POL: return lg(g) == 2;
     268             :     case t_VEC: case t_COL: case t_MAT:
     269         252 :       for (i=lg(g)-1; i; i--)
     270         168 :         if (!isrationalzero(gel(g,i))) return 0;
     271          84 :       return 1;
     272             :   }
     273    41183383 :   return 0;
     274             : }
     275             : 
     276             : int
     277   524425440 : gequal0(GEN x)
     278             : {
     279   524425440 :   switch(typ(x))
     280             :   {
     281             :     case t_INT: case t_REAL: case t_POL: case t_SER:
     282   493631580 :       return !signe(x);
     283             : 
     284             :     case t_INTMOD:
     285     2943394 :       return !signe(gel(x,2));
     286             : 
     287             :     case t_FFELT:
     288      549045 :       return FF_equal0(x);
     289             : 
     290             :     case t_COMPLEX:
     291             :      /* is 0 iff norm(x) would be 0 (can happen with Re(x) and Im(x) != 0
     292             :       * only if Re(x) and Im(x) are of type t_REAL). See mp.c:addrr().
     293             :       */
     294    11234171 :       if (gequal0(gel(x,1)))
     295             :       {
     296     1201724 :         if (gequal0(gel(x,2))) return 1;
     297     1002465 :         if (typ(gel(x,1))!=t_REAL || typ(gel(x,2))!=t_REAL) return 0;
     298       49716 :         return (expo(gel(x,1))>=expo(gel(x,2)));
     299             :       }
     300    10032447 :       if (gequal0(gel(x,2)))
     301             :       {
     302      449151 :         if (typ(gel(x,1))!=t_REAL || typ(gel(x,2))!=t_REAL) return 0;
     303      358008 :         return (expo(gel(x,2))>=expo(gel(x,1)));
     304             :       }
     305     9583296 :       return 0;
     306             : 
     307             :     case t_PADIC:
     308      329508 :       return !signe(gel(x,4));
     309             : 
     310             :     case t_QUAD:
     311         924 :       return gequal0(gel(x,2)) && gequal0(gel(x,3));
     312             : 
     313             :     case t_POLMOD:
     314     1410544 :       return gequal0(gel(x,2));
     315             : 
     316             :     case t_RFRAC:
     317     6010223 :       return gequal0(gel(x,1));
     318             : 
     319             :     case t_VEC: case t_COL: case t_MAT:
     320             :     {
     321             :       long i;
     322     4167124 :       for (i=lg(x)-1; i; i--)
     323     3834668 :         if (!gequal0(gel(x,i))) return 0;
     324      332456 :       return 1;
     325             :     }
     326             :   }
     327     6958475 :   return 0;
     328             : }
     329             : 
     330             : /* x a t_POL or t_SER, considered as having valuation v; let X(t) = t^(-v) x(t)
     331             :  * return 1 (true) if coeff(X,i) = 0 for all i != 0 and test(coeff(X, 0))
     332             :  * is true. Return 0 (false) otherwise, or if x == 0 */
     333             : static int
     334    13140186 : is_monomial_test(GEN x, long v, int(*test)(GEN))
     335             : {
     336             :   long d, i, l;
     337    13140186 :   if (!signe(x)) return (typ(x) == t_SER && v <= 0);
     338    13077327 :   if (v > 0) return 0;
     339    13077313 :   l = lg(x); d = 2-v;
     340    13077313 :   if (l <= d) return 0;
     341             :   /* 2 <= d < l */
     342    13077313 :   if (!test(gel(x,d))) return 0;
     343     3964438 :   for (i = 2; i < d; i++)
     344          14 :     if (!gequal0(gel(x,i))) return 0;
     345     4380671 :   for (i = d+1; i < l; i++)
     346     1972565 :     if (!gequal0(gel(x,i))) return 0;
     347     2408106 :   return 1;
     348             : }
     349             : static int
     350        2058 : col_test(GEN x, int(*test)(GEN))
     351             : {
     352        2058 :   long i, l = lg(x);
     353        2058 :   if (l == 1 || !test(gel(x,1))) return 0;
     354          42 :   for (i = 2; i < l; i++)
     355          21 :     if (!gequal0(gel(x,i))) return 0;
     356          21 :   return 1;
     357             : }
     358             : static int
     359       16184 : mat_test(GEN x, int(*test)(GEN))
     360             : {
     361       16184 :   long i, j, l = lg(x);
     362       16184 :   if (l == 1) return 1;
     363       16170 :   if (l != lgcols(x)) return 0;
     364       51240 :   for (i = 1; i < l; i++)
     365      134078 :     for (j = 1; j < l; j++)
     366       99008 :       if (i == j) {
     367       35133 :         if (!test(gcoeff(x,i,i))) return 0;
     368             :       } else {
     369       63875 :         if (!gequal0(gcoeff(x,i,j))) return 0;
     370             :       }
     371       16107 :   return 1;
     372             : }
     373             : 
     374             : /* returns 1 whenever x = 1, and 0 otherwise */
     375             : int
     376   150927343 : gequal1(GEN x)
     377             : {
     378   150927343 :   switch(typ(x))
     379             :   {
     380             :     case t_INT:
     381   135605696 :       return equali1(x);
     382             : 
     383             :     case t_REAL:
     384             :     {
     385       38318 :       long s = signe(x);
     386       38318 :       if (!s) return expo(x) >= 0;
     387       38241 :       return s > 0 ? absrnz_equal1(x): 0;
     388             :     }
     389             :     case t_INTMOD:
     390      277935 :       return is_pm1(gel(x,2)) || is_pm1(gel(x,1));
     391             :     case t_POLMOD:
     392      319630 :       return gequal1(gel(x,2)) || gequal1(gel(x,1));
     393             : 
     394             :     case t_FFELT:
     395        7686 :       return FF_equal1(x);
     396             : 
     397             :     case t_FRAC:
     398      467573 :       return 0;
     399             : 
     400             :     case t_COMPLEX:
     401       11018 :       return gequal1(gel(x,1)) && gequal0(gel(x,2));
     402             : 
     403             :     case t_PADIC:
     404        9310 :       return !valp(x) && gequal1(gel(x,4));
     405             : 
     406             :     case t_QUAD:
     407          35 :       return gequal1(gel(x,2)) && gequal0(gel(x,3));
     408             : 
     409    13139983 :     case t_POL: return is_monomial_test(x, 0, &gequal1);
     410          91 :     case t_SER: return is_monomial_test(x, valp(x), &gequal1);
     411             : 
     412     1031903 :     case t_RFRAC: return gequal(gel(x,1), gel(x,2));
     413        2016 :     case t_COL: return col_test(x, &gequal1);
     414       16135 :     case t_MAT: return mat_test(x, &gequal1);
     415             :   }
     416          14 :   return 0;
     417             : }
     418             : 
     419             : /* returns 1 whenever the x = -1, 0 otherwise */
     420             : int
     421      102444 : gequalm1(GEN x)
     422             : {
     423             :   pari_sp av;
     424             :   long y;
     425             :   GEN p1;
     426             : 
     427      102444 :   switch(typ(x))
     428             :   {
     429             :     case t_INT:
     430       93856 :       return equalim1(x);
     431             : 
     432             :     case t_REAL:
     433             :     {
     434        4112 :       long s = signe(x);
     435        4112 :       if (!s) return expo(x) >= 0;
     436        4112 :       return s < 0 ? absrnz_equal1(x): 0;
     437             :     }
     438             :     case t_INTMOD:
     439          21 :       av=avma; y=equalii(addui(1,gel(x,2)), gel(x,1)); avma=av; return y;
     440             : 
     441             :     case t_FRAC:
     442          14 :       return 0;
     443             : 
     444             :     case t_FFELT:
     445          42 :       return FF_equalm1(x);
     446             : 
     447             :     case t_COMPLEX:
     448        4112 :       return gequalm1(gel(x,1)) && gequal0(gel(x,2));
     449             : 
     450             :     case t_QUAD:
     451           7 :       return gequalm1(gel(x,2)) && gequal0(gel(x,3));
     452             : 
     453             :     case t_PADIC:
     454           7 :       av=avma; y=equalii(addui(1,gel(x,4)), gel(x,3)); avma=av; return y;
     455             : 
     456             :     case t_POLMOD:
     457          35 :       av=avma; p1 = gaddgs(gel(x,2), 1);
     458          35 :       y = gequal0(p1) || gequal(p1,gel(x,1)); avma=av; return y;
     459             : 
     460          35 :     case t_POL: return is_monomial_test(x, 0, &gequalm1);
     461          77 :     case t_SER: return is_monomial_test(x, valp(x), &gequalm1);
     462             : 
     463             :     case t_RFRAC:
     464          21 :       av=avma; y=gequal(gel(x,1), gneg_i(gel(x,2))); avma=av; return y;
     465          42 :     case t_COL: return col_test(x, &gequalm1);
     466          49 :     case t_MAT: return mat_test(x, &gequalm1);
     467             :   }
     468          14 :   return 0;
     469             : }
     470             : 
     471             : int
     472     3128259 : gequalX(GEN x) { return typ(x) == t_POL && lg(x) == 4
     473     2069156 :                       && isintzero(gel(x,2)) && isint1(gel(x,3)); }
     474             : 
     475             : static int
     476         476 : cmp_str(const char *x, const char *y)
     477             : {
     478         476 :   int f = strcmp(x, y);
     479         476 :   return f > 0? 1
     480         476 :               : f? -1: 0;
     481             : }
     482             : 
     483             : static int
     484    27112668 : cmp_universal_rec(GEN x, GEN y, long i0)
     485             : {
     486    27112668 :   long i, lx = lg(x), ly = lg(y);
     487    27112668 :   if (lx < ly) return -1;
     488    27111065 :   if (lx > ly) return 1;
     489    40656590 :   for (i = i0; i < lx; i++)
     490             :   {
     491    34518164 :     int f = cmp_universal(gel(x,i), gel(y,i));
     492    34518164 :     if (f) return f;
     493             :   }
     494     6138426 :   return 0;
     495             : }
     496             : /* Universal "meaningless" comparison function. Transitive, returns 0 iff
     497             :  * gidentical(x,y) */
     498             : int
     499    47430387 : cmp_universal(GEN x, GEN y)
     500             : {
     501    47430387 :   long lx, ly, i, tx = typ(x), ty = typ(y);
     502             : 
     503    47430387 :   if (tx < ty) return -1;
     504    47419515 :   if (ty < tx) return 1;
     505    47414987 :   switch(tx)
     506             :   {
     507    19362037 :     case t_INT: return cmpii(x,y);
     508         455 :     case t_STR: return cmp_str(GSTR(x),GSTR(y));
     509             :     case t_REAL:
     510             :     case t_VECSMALL:
     511      939764 :       lx = lg(x);
     512      939764 :       ly = lg(y);
     513      939764 :       if (lx < ly) return -1;
     514      888335 :       if (lx > ly) return 1;
     515     3580802 :       for (i = 1; i < lx; i++)
     516             :       {
     517     3473163 :         if (x[i] < y[i]) return -1;
     518     3088709 :         if (x[i] > y[i]) return 1;
     519             :       }
     520      107639 :       return 0;
     521             : 
     522             :     case t_POL:
     523             :     case t_SER:
     524             :     case t_FFELT:
     525             :     case t_CLOSURE:
     526      903315 :       if (x[1] < y[1]) return -1;
     527      903294 :       if (x[1] > y[1]) return 1;
     528      903252 :       return cmp_universal_rec(x, y, 2);
     529             : 
     530             :     case t_LIST:
     531             :       {
     532          35 :         long tx = list_typ(x), ty = list_typ(y);
     533             :         GEN vx, vy;
     534          35 :         if (tx < ty) return -1;
     535          35 :         if (tx > ty) return 1;
     536          35 :         vx = list_data(x);
     537          35 :         vy = list_data(y);
     538          35 :         if (!vx) return vy? -1: 0;
     539          35 :         if (!vy) return 1;
     540          35 :         switch (tx)
     541             :         {
     542             :         case t_LIST_MAP:
     543             :           {
     544          14 :             pari_sp av = avma;
     545          14 :             int ret = cmp_universal_rec(maptomat_shallow(x), maptomat_shallow(y),1);
     546          14 :             avma = av; return ret;
     547             :           }
     548             :         default:
     549          21 :           return cmp_universal_rec(vx, vy, 1);
     550             :         }
     551             :       }
     552             :     default:
     553    26209381 :       return cmp_universal_rec(x, y, lontyp[tx]);
     554             :   }
     555             : }
     556             : 
     557             : static int
     558       83806 : cmpfrac(GEN x, GEN y)
     559             : {
     560       83806 :   pari_sp av = avma;
     561       83806 :   GEN a = gel(x,1), b = gel(x,2);
     562       83806 :   GEN c = gel(y,1), d = gel(y,2);
     563       83806 :   int r = cmpii(mulii(a, d), mulii(b, c));
     564       83806 :   avma = av; return r;
     565             : }
     566             : static int
     567       13146 : cmpifrac(GEN a, GEN y)
     568             : {
     569       13146 :   pari_sp av = avma;
     570       13146 :   GEN c = gel(y,1), d = gel(y,2);
     571       13146 :   int r = cmpii(mulii(a, d), c);
     572       13146 :   avma = av; return r;
     573             : }
     574             : static int
     575       35868 : cmprfrac(GEN a, GEN y)
     576             : {
     577       35868 :   pari_sp av = avma;
     578       35868 :   GEN c = gel(y,1), d = gel(y,2);
     579       35868 :   int r = cmpri(mulri(a, d), c);
     580       35868 :   avma = av; return r;
     581             : }
     582             : static int
     583          63 : cmpgen(GEN x, GEN y)
     584             : {
     585          63 :   pari_sp av = avma;
     586          63 :   int s = gsigne(gsub(x,y));
     587          56 :   avma = av; return s;
     588             : }
     589             : 
     590             : /* returns the sign of x - y when it makes sense. 0 otherwise */
     591             : int
     592   193711930 : gcmp(GEN x, GEN y)
     593             : {
     594   193711930 :   long tx = typ(x), ty = typ(y);
     595             : 
     596   193711930 :   if (tx == ty) /* generic case */
     597   193216769 :     switch(tx)
     598             :     {
     599   114921566 :       case t_INT:  return cmpii(x, y);
     600    78348400 :       case t_REAL: return cmprr(x, y);
     601       83806 :       case t_FRAC: return cmpfrac(x, y);
     602          14 :       case t_QUAD: return cmpgen(x, y);
     603          21 :       case t_STR:  return cmp_str(GSTR(x), GSTR(y));
     604             :       case t_INFINITY:
     605             :       {
     606       13027 :         long sx = inf_get_sign(x), sy = inf_get_sign(y);
     607       13027 :         if (sx < sy) return -1;
     608          21 :         if (sx > sy) return 1;
     609          14 :         return 0;
     610             :       }
     611             :     }
     612      345096 :   if (ty == t_INFINITY) return -inf_get_sign(y);
     613      331807 :   switch(tx)
     614             :   {
     615             :     case t_INT:
     616       27255 :       switch(ty)
     617             :       {
     618       21907 :         case t_REAL: return cmpir(x, y);
     619        5334 :         case t_FRAC: return cmpifrac(x, y);
     620           7 :         case t_QUAD: return cmpgen(x, y);
     621             :       }
     622           7 :       break;
     623             :     case t_REAL:
     624      272241 :       switch(ty)
     625             :       {
     626      260110 :         case t_INT:  return cmpri(x, y);
     627       12117 :         case t_FRAC: return cmprfrac(x, y);
     628           7 :         case t_QUAD: return cmpgen(x, y);
     629             :       }
     630           7 :       break;
     631             :     case t_FRAC:
     632       31577 :       switch(ty)
     633             :       {
     634        7812 :         case t_INT:  return -cmpifrac(y, x);
     635       23751 :         case t_REAL: return -cmprfrac(y, x);
     636           7 :         case t_QUAD: return cmpgen(x, y);
     637             :       }
     638           7 :       break;
     639             :     case t_QUAD:
     640          28 :       return cmpgen(x, y);
     641         699 :     case t_INFINITY: return inf_get_sign(x);
     642             :   }
     643          28 :   pari_err_TYPE2("comparison",x,y);
     644             :   return 0;/*LCOV_EXCL_LINE*/
     645             : }
     646             : 
     647             : int
     648       26277 : gcmpsg(long s, GEN y)
     649             : {
     650       26277 :   switch(typ(y))
     651             :   {
     652        1260 :     case t_INT:  return cmpsi(s,y);
     653       23659 :     case t_REAL: return cmpsr(s,y);
     654             :     case t_FRAC: {
     655        1358 :       pari_sp av = avma;
     656        1358 :       GEN n = gel(y,1), d = gel(y,2);
     657        1358 :       int f = cmpii(mulsi(s,d), n); avma = av; return f;
     658             :     }
     659             :     case t_QUAD: {
     660           0 :       pari_sp av = avma;
     661           0 :       int f = gsigne(gsubsg(s, y)); avma = av; return f;
     662             :     }
     663           0 :     case t_INFINITY: return -inf_get_sign(y);
     664             :   }
     665           0 :   pari_err_TYPE2("comparison",stoi(s),y);
     666             :   return 0; /* LCOV_EXCL_LINE */
     667             : }
     668             : 
     669             : static long
     670     5840245 : roughtype(GEN x)
     671             : {
     672     5840245 :   switch(typ(x))
     673             :   {
     674        2058 :     case t_MAT: return t_MAT;
     675       14434 :     case t_VEC: case t_COL: return t_VEC;
     676     5789012 :     case t_VECSMALL: return t_VECSMALL;
     677       34741 :     default: return t_INT;
     678             :   }
     679             : }
     680             : 
     681             : static int lexcmpsg(long x, GEN y);
     682          28 : static int lexcmpgs(GEN x, long y) { return -lexcmpsg(y,x); }
     683             : /* lexcmp(stoi(x),y), y t_VEC/t_COL/t_MAT */
     684             : static int
     685          21 : lexcmp_s_matvec(long x, GEN y)
     686             : {
     687             :   int fl;
     688          21 :   if (lg(y)==1) return 1;
     689          14 :   fl = lexcmpsg(x,gel(y,1));
     690          14 :   if (fl) return fl;
     691           7 :   return -1;
     692             : }
     693             : /* x a scalar, y a t_VEC/t_COL/t_MAT */
     694             : static int
     695         245 : lexcmp_scal_matvec(GEN x, GEN y)
     696             : {
     697             :   int fl;
     698         245 :   if (lg(y)==1) return 1;
     699         245 :   fl = lexcmp(x,gel(y,1));
     700         245 :   if (fl) return fl;
     701           7 :   return -1;
     702             : }
     703             : /* x a scalar, y a t_VECSMALL */
     704             : static int
     705          28 : lexcmp_scal_vecsmall(GEN x, GEN y)
     706             : {
     707             :   int fl;
     708          28 :   if (lg(y)==1) return 1;
     709          28 :   fl = lexcmpgs(x, y[1]);
     710          28 :   if (fl) return fl;
     711           0 :   return -1;
     712             : }
     713             : 
     714             : /* tx = ty = t_MAT, or x and y are both vect_t */
     715             : static int
     716        8036 : lexcmp_similar(GEN x, GEN y)
     717             : {
     718        8036 :   long i, lx = lg(x), ly = lg(y), l = minss(lx,ly);
     719       15659 :   for (i=1; i<l; i++)
     720             :   {
     721       14112 :     int fl = lexcmp(gel(x,i),gel(y,i));
     722       14112 :     if (fl) return fl;
     723             :   }
     724        1547 :   if (lx == ly) return 0;
     725          35 :   return (lx < ly)? -1 : 1;
     726             : }
     727             : /* x a t_VECSMALL, y a t_VEC/t_COL ~ lexcmp_similar */
     728             : static int
     729         154 : lexcmp_vecsmall_vec(GEN x, GEN y)
     730             : {
     731         154 :   long i, lx = lg(x), ly = lg(y), l = minss(lx,ly);
     732         343 :   for (i=1; i<l; i++)
     733             :   {
     734         287 :     int fl = lexcmpsg(x[i], gel(y,i));
     735         287 :     if (fl) return fl;
     736             :   }
     737          56 :   if (lx == ly) return 0;
     738          21 :   return (lx < ly)? -1 : 1;
     739             : }
     740             : 
     741             : /* x t_VEC/t_COL, y t_MAT */
     742             : static int
     743          98 : lexcmp_vec_mat(GEN x, GEN y)
     744             : {
     745             :   int fl;
     746          98 :   if (lg(x)==1) return -1;
     747          98 :   if (lg(y)==1) return 1;
     748          98 :   fl = lexcmp_similar(x,gel(y,1));
     749          98 :   if (fl) return fl;
     750           7 :   return -1;
     751             : }
     752             : /* x t_VECSMALl, y t_MAT ~ lexcmp_vec_mat */
     753             : static int
     754          42 : lexcmp_vecsmall_mat(GEN x, GEN y)
     755             : {
     756             :   int fl;
     757          42 :   if (lg(x)==1) return -1;
     758          42 :   if (lg(y)==1) return 1;
     759          42 :   fl = lexcmp_vecsmall_vec(x, gel(y,1));
     760          42 :   if (fl) return fl;
     761           0 :   return -1;
     762             : }
     763             : 
     764             : /* x a t_VECSMALL, not y */
     765             : static int
     766         182 : lexcmp_vecsmall_other(GEN x, GEN y, long ty)
     767             : {
     768         182 :   switch(ty)
     769             :   {
     770          42 :     case t_MAT: return lexcmp_vecsmall_mat(x, y);
     771         112 :     case t_VEC: return lexcmp_vecsmall_vec(x, y);
     772          28 :     default: return -lexcmp_scal_vecsmall(y, x); /*y scalar*/
     773             :   }
     774             : }
     775             : 
     776             : /* lexcmp(stoi(s), y) */
     777             : static int
     778         329 : lexcmpsg(long x, GEN y)
     779             : {
     780         329 :   switch(roughtype(y))
     781             :   {
     782             :     case t_MAT:
     783             :     case t_VEC:
     784          21 :       return lexcmp_s_matvec(x,y);
     785             :     case t_VECSMALL: /* ~ lexcmp_scal_matvec */
     786          14 :       if (lg(y)==1) return 1;
     787           7 :       return (x > y[1])? 1: -1;
     788         294 :     default: return gcmpsg(x,y);
     789             :   }
     790             : }
     791             : 
     792             : /* as gcmp for vector/matrices, using lexicographic ordering on components */
     793             : int
     794     2919958 : lexcmp(GEN x, GEN y)
     795             : {
     796     2919958 :   const long tx = roughtype(x), ty = roughtype(y);
     797     2919958 :   if (tx == ty)
     798     2919433 :     switch(tx)
     799             :     {
     800             :       case t_MAT:
     801             :       case t_VEC:
     802        7938 :         return lexcmp_similar(x,y);
     803             :       case t_VECSMALL:
     804     2894408 :         return vecsmall_lexcmp(x,y);
     805             :       default:
     806       17087 :         return gcmp(x,y);
     807             :     }
     808         525 :   if (tx == t_VECSMALL) return  lexcmp_vecsmall_other(x,y,ty);
     809         406 :   if (ty == t_VECSMALL) return -lexcmp_vecsmall_other(y,x,tx);
     810             : 
     811         343 :   if (tx == t_INT) return  lexcmp_scal_matvec(x,y); /*scalar*/
     812         168 :   if (ty == t_INT) return -lexcmp_scal_matvec(y,x);
     813             : 
     814          98 :   if (ty==t_MAT) return  lexcmp_vec_mat(x,y);
     815          42 :   /*tx==t_MAT*/  return -lexcmp_vec_mat(y,x);
     816             : }
     817             : 
     818             : /*****************************************************************/
     819             : /*                                                               */
     820             : /*                          EQUALITY                             */
     821             : /*                returns 1 if x == y, 0 otherwise               */
     822             : /*                                                               */
     823             : /*****************************************************************/
     824             : /* x,y t_POL */
     825             : static int
     826      908958 : polidentical(GEN x, GEN y)
     827             : {
     828             :   long lx;
     829      908958 :   if (x[1] != y[1]) return 0;
     830      908867 :   lx = lg(x); if (lg(y) != lg(x)) return 0;
     831      908797 :   for (lx--; lx >= 2; lx--) if (!gidentical(gel(x,lx), gel(y,lx))) return 0;
     832      908783 :   return 1;
     833             : }
     834             : /* x,y t_SER */
     835             : static int
     836          14 : seridentical(GEN x, GEN y) { return polidentical(x,y); }
     837             : /* typ(x) = typ(y) = t_VEC/COL/MAT */
     838             : static int
     839     4050689 : vecidentical(GEN x, GEN y)
     840             : {
     841             :   long i;
     842     4050689 :   if ((x[0] ^ y[0]) & (TYPBITS|LGBITS)) return 0;
     843    10717363 :   for (i = lg(x)-1; i; i--)
     844     7374555 :     if (! gidentical(gel(x,i),gel(y,i)) ) return 0;
     845     3342808 :   return 1;
     846             : }
     847             : static int
     848          21 : identicalrr(GEN x, GEN y)
     849             : {
     850          21 :   long i, lx = lg(x);
     851          21 :   if (lg(y) != lx) return 0;
     852          14 :   if (x[1] != y[1]) return 0;
     853           7 :   i=2; while (i<lx && x[i]==y[i]) i++;
     854           7 :   return (i == lx);
     855             : }
     856             : 
     857             : static int
     858          35 : closure_identical(GEN x, GEN y)
     859             : {
     860          35 :   if (lg(x)!=lg(y) || x[1]!=y[1]) return 0;
     861          21 :   if (!gidentical(gel(x,2),gel(y,2)) || !gidentical(gel(x,3),gel(y,3))
     862           7 :    || !gidentical(gel(x,4),gel(y,4))) return 0;
     863           7 :   if (lg(x)<8) return 1;
     864           0 :   return gidentical(gel(x,7),gel(y,7));
     865             : }
     866             : 
     867             : static int
     868         336 : list_cmp(GEN x, GEN y, int cmp(GEN x, GEN y))
     869             : {
     870         336 :   int t = list_typ(x);
     871             :   GEN vx, vy;
     872         336 :   if (list_typ(y)!=t) return 0;
     873         336 :   vx = list_data(x);
     874         336 :   vy = list_data(y);
     875         336 :   if (!vx) return vy? 0: 1;
     876         322 :   if (!vy) return 0;
     877         308 :   if (lg(vx) != lg(vy)) return 0;
     878         301 :   switch (t)
     879             :   {
     880             :   case t_LIST_MAP:
     881             :     {
     882         280 :       pari_sp av = avma;
     883         280 :       GEN mx  = maptomat_shallow(x), my = maptomat_shallow(y);
     884         280 :       int ret = gidentical(gel(mx, 1), gel(my, 1)) && cmp(gel(mx, 2), gel(my, 2));
     885         280 :       avma = av; return ret;
     886             :     }
     887             :   default:
     888          21 :     return cmp(vx, vy);
     889             :   }
     890             : }
     891             : 
     892             : int
     893    36628425 : gidentical(GEN x, GEN y)
     894             : {
     895             :   long tx;
     896             : 
     897    36628425 :   if (x == y) return 1;
     898    35662357 :   tx = typ(x); if (typ(y) != tx) return 0;
     899    35660075 :   switch(tx)
     900             :   {
     901             :     case t_INT:
     902     7333598 :       return equalii(x,y);
     903             : 
     904             :     case t_REAL:
     905          14 :       return identicalrr(x,y);
     906             : 
     907             :     case t_FRAC: case t_INTMOD:
     908       19586 :       return equalii(gel(x,2), gel(y,2)) && equalii(gel(x,1), gel(y,1));
     909             : 
     910             :     case t_COMPLEX:
     911          14 :       return gidentical(gel(x,2),gel(y,2)) && gidentical(gel(x,1),gel(y,1));
     912             :     case t_PADIC:
     913          28 :       return valp(x) == valp(y)
     914          14 :         && equalii(gel(x,2),gel(y,2))
     915          14 :         && equalii(gel(x,3),gel(y,3))
     916          28 :         && equalii(gel(x,4),gel(y,4));
     917             :     case t_POLMOD:
     918          49 :       return gidentical(gel(x,2),gel(y,2)) && polidentical(gel(x,1),gel(y,1));
     919             :     case t_POL:
     920      908923 :       return polidentical(x,y);
     921             :     case t_SER:
     922          14 :       return seridentical(x,y);
     923             :     case t_FFELT:
     924          14 :       return FF_equal(x,y);
     925             : 
     926             :     case t_QFR:
     927           7 :           if (!identicalrr(gel(x,4),gel(y,4))) return 0; /* fall through */
     928             :     case t_QFI:
     929     4736308 :       return equalii(gel(x,1),gel(y,1))
     930     2368147 :           && equalii(gel(x,2),gel(y,2))
     931     4736294 :           && equalii(gel(x,3),gel(y,3));
     932             : 
     933             :     case t_QUAD:
     934          28 :       return ZX_equal(gel(x,1),gel(y,1))
     935           7 :           && gidentical(gel(x,2),gel(y,2))
     936          14 :           && gidentical(gel(x,3),gel(y,3));
     937             : 
     938             :     case t_RFRAC:
     939           7 :       return gidentical(gel(x,1),gel(y,1)) && gidentical(gel(x,2),gel(y,2));
     940             : 
     941             :     case t_STR:
     942          35 :       return !strcmp(GSTR(x),GSTR(y));
     943             :     case t_VEC: case t_COL: case t_MAT:
     944     4050689 :       return vecidentical(x,y);
     945             :     case t_VECSMALL:
     946    20978733 :       return zv_equal(x,y);
     947             :     case t_CLOSURE:
     948          28 :       return closure_identical(x,y);
     949             :     case t_LIST:
     950         161 :       return list_cmp(x, y, gidentical);
     951          21 :     case t_INFINITY: return gidentical(gel(x,1),gel(y,1));
     952             :   }
     953           0 :   return 0;
     954             : }
     955             : /* x,y t_POL */
     956             : static int
     957     3525440 : polequal(GEN x, GEN y)
     958             : {
     959             :   long lx, ly;
     960     3525440 :   if ((x[1] ^ y[1]) & (VARNBITS | SIGNBITS)) return 0;
     961     3516886 :   lx = lg(x); ly = lg(y);
     962     3516886 :   while (lx > ly) if (!gequal0(gel(x,--lx))) return 0;
     963     3515094 :   while (ly > lx) if (!gequal0(gel(y,--ly))) return 0;
     964     3502004 :   for (lx--; lx >= 2; lx--) if (!gequal(gel(x,lx), gel(y,lx))) return 0;
     965     3471387 :   return 1;
     966             : }
     967             : 
     968             : /* x,y t_POL */
     969             : static int
     970         315 : serequal(GEN x, GEN y)
     971             : {
     972             :   long lx;
     973         315 :   if (varn(x) != varn(y)) return 0;
     974         315 :   if (!signe(x))
     975             :   {
     976         294 :     if (!signe(y)) return 1;
     977           0 :     return valp(y) >= valp(x);
     978             :   }
     979          21 :   if (!signe(y))
     980           0 :     return valp(x) >= valp(y);
     981          21 :   if ((x[1] ^ y[1]) & VALPBITS) return 0;
     982          21 :   lx = minss(lg(x), lg(y));
     983          21 :   for (lx--; lx >= 2; lx--) if (!gequal(gel(x,lx), gel(y,lx))) return 0;
     984          21 :   return 1;
     985             : }
     986             : 
     987             : /* typ(x) = typ(y) = t_VEC/COL/MAT */
     988             : static int
     989     3614731 : vecequal(GEN x, GEN y)
     990             : {
     991             :   long i;
     992     3614731 :   if ((x[0] ^ y[0]) & (TYPBITS|LGBITS)) return 0;
     993    14594747 :   for (i = lg(x)-1; i; i--)
     994    12545314 :     if (! gequal(gel(x,i),gel(y,i)) ) return 0;
     995     2049433 :   return 1;
     996             : }
     997             : 
     998             : static int
     999     2282128 : gequal_try(GEN x, GEN y)
    1000             : {
    1001             :   int i;
    1002     2282128 :   pari_CATCH(CATCH_ALL) {
    1003         175 :     GEN E = pari_err_last();
    1004         175 :     switch(err_get_num(E))
    1005             :     {
    1006             :       case e_STACK: case e_MEM: case e_ALARM:
    1007           0 :         pari_err(0, E); /* rethrow */
    1008             :     }
    1009         175 :     return 0;
    1010             :   } pari_TRY {
    1011     2282128 :     i = gequal0(gadd(x, gneg_i(y)));
    1012     2281953 :   } pari_ENDCATCH;
    1013     2281953 :   return i;
    1014             : }
    1015             : 
    1016             : int
    1017   129312782 : gequal(GEN x, GEN y)
    1018             : {
    1019             :   pari_sp av;
    1020             :   long tx, ty;
    1021             :   long i;
    1022             : 
    1023   129312782 :   if (x == y) return 1;
    1024   115752005 :   tx = typ(x);
    1025   115752005 :   ty = typ(y);
    1026   115752005 :   if (tx == ty)
    1027   113469884 :     switch(tx)
    1028             :     {
    1029             :       case t_INT:
    1030    98507887 :         return equalii(x,y);
    1031             : 
    1032             :       case t_REAL:
    1033        1643 :         return equalrr(x,y);
    1034             : 
    1035             :       case t_FRAC: case t_INTMOD:
    1036     5813326 :         return equalii(gel(x,2), gel(y,2)) && equalii(gel(x,1), gel(y,1));
    1037             : 
    1038             :       case t_COMPLEX:
    1039         224 :         return gequal(gel(x,2),gel(y,2)) && gequal(gel(x,1),gel(y,1));
    1040             :       case t_PADIC:
    1041         756 :         if (!equalii(gel(x,2),gel(y,2))) return 0;
    1042         756 :         av = avma; i = gequal0(gsub(x,y)); avma = av;
    1043         756 :         return i;
    1044             :       case t_POLMOD:
    1045      231915 :         if (varn(gel(x,1)) != varn(gel(y,1))) break;
    1046      231908 :         return gequal(gel(x,2),gel(y,2)) && RgX_equal_var(gel(x,1),gel(y,1));
    1047             :       case t_POL:
    1048     3525440 :         return polequal(x,y);
    1049             :       case t_SER:
    1050         315 :         return serequal(x,y);
    1051             : 
    1052             :       case t_FFELT:
    1053       53977 :         return FF_equal(x,y);
    1054             : 
    1055             :       case t_QFR:
    1056             :       case t_QFI:
    1057     2100044 :         return equalii(gel(x,1),gel(y,1))
    1058      230157 :             && equalii(gel(x,2),gel(y,2))
    1059     1207162 :             && equalii(gel(x,3),gel(y,3));
    1060             : 
    1061             :       case t_QUAD:
    1062          14 :         return ZX_equal(gel(x,1),gel(y,1))
    1063           0 :             && gequal(gel(x,2),gel(y,2))
    1064           7 :             && gequal(gel(x,3),gel(y,3));
    1065             : 
    1066             :       case t_RFRAC:
    1067             :       {
    1068       73717 :         GEN a = gel(x,1), b = gel(x,2), c = gel(y,1), d = gel(y,2);
    1069       73717 :         if (gequal(b,d)) return gequal(a,c); /* simple case */
    1070           0 :         av = avma;
    1071           0 :         i = gequal(simplify_shallow(gmul(a,d)), simplify_shallow(gmul(b,c)));
    1072           0 :         avma = av; return i;
    1073             :       }
    1074             : 
    1075             :       case t_STR:
    1076       59330 :         return !strcmp(GSTR(x),GSTR(y));
    1077             :       case t_VEC: case t_COL: case t_MAT:
    1078     3614731 :         return vecequal(x,y);
    1079             :       case t_VECSMALL:
    1080      536384 :         return zv_equal(x,y);
    1081             :       case t_LIST:
    1082         175 :         return list_cmp(x, y, gequal);
    1083             :       case t_CLOSURE:
    1084           7 :         return closure_identical(x,y);
    1085             :       case t_INFINITY:
    1086          28 :         return gequal(gel(x,1),gel(y,1));
    1087             :     }
    1088             :   (void)&av; /* emulate volatile */
    1089     2282128 :   av = avma; i = gequal_try(x, y);
    1090     2282128 :   avma = av; return i;
    1091             : }
    1092             : 
    1093             : int
    1094       25501 : gequalsg(long s, GEN x)
    1095             : {
    1096       25501 :   pari_sp av = avma;
    1097       25501 :   int f = gequal(stoi(s), x);
    1098       25501 :   avma = av; return f;
    1099             : }
    1100             : 
    1101             : /* a and b are t_INT, t_FRAC, t_REAL or t_COMPLEX of those. Check whether
    1102             :  * a-b is invertible */
    1103             : int
    1104        9268 : cx_approx_equal(GEN a, GEN b)
    1105             : {
    1106        9268 :   pari_sp av = avma;
    1107             :   GEN d;
    1108             :   int r;
    1109        9268 :   if (a == b) return 1;
    1110        7770 :   d = gsub(a,b);
    1111        7770 :   r = (gequal0(d) || (typ(d) == t_COMPLEX && gequal0(cxnorm(d))));
    1112        7770 :   avma = av; return r;
    1113             : }
    1114             : /*******************************************************************/
    1115             : /*                                                                 */
    1116             : /*                          VALUATION                              */
    1117             : /*             p is either a t_INT or a t_POL.                     */
    1118             : /*  returns the largest exponent of p dividing x when this makes   */
    1119             : /*  sense : error for types real, integermod and polymod if p does */
    1120             : /*  not divide the modulus, q-adic if q!=p.                        */
    1121             : /*                                                                 */
    1122             : /*******************************************************************/
    1123             : 
    1124             : static long
    1125         231 : minval(GEN x, GEN p)
    1126             : {
    1127         231 :   long i,k, val = LONG_MAX, lx = lg(x);
    1128        5789 :   for (i=lontyp[typ(x)]; i<lx; i++)
    1129             :   {
    1130        5558 :     k = gvaluation(gel(x,i),p);
    1131        5558 :     if (k < val) val = k;
    1132             :   }
    1133         231 :   return val;
    1134             : }
    1135             : 
    1136             : static int
    1137          91 : intdvd(GEN x, GEN y, GEN *z) { GEN r; *z = dvmdii(x,y,&r); return (r==gen_0); }
    1138             : 
    1139             : /* x t_FRAC, p t_INT, return v_p(x) */
    1140             : static long
    1141       84903 : ratval(GEN x, GEN p) {
    1142       84903 :   long v = Z_pval(gel(x,2),p);
    1143       84903 :   if (v) return -v;
    1144        9051 :   return Z_pval(gel(x,1),p);
    1145             : }
    1146             : 
    1147             : long
    1148     1397316 : Q_pval(GEN x, GEN p) { return (typ(x) == t_INT)? Z_pval(x, p): ratval(x, p); }
    1149             : 
    1150             : long
    1151      443112 : Q_pvalrem(GEN x, GEN p, GEN *y)
    1152             : {
    1153             :   GEN a, b;
    1154             :   long v;
    1155      443112 :   if (typ(x) == t_INT) return Z_pvalrem(x, p, y);
    1156       78645 :   a = gel(x,1);
    1157       78645 :   b = gel(x,2);
    1158       78645 :   v = Z_pvalrem(b, p, &b);
    1159       78645 :   if (v) { *y = isint1(b)? a: mkfrac(a, b); return -v; }
    1160       48573 :   v = Z_pvalrem(a, p, &a);
    1161       48573 :   *y = mkfrac(a, b); return v;
    1162             : }
    1163             : 
    1164             : long
    1165      205830 : gvaluation(GEN x, GEN p)
    1166             : {
    1167      205830 :   long tx = typ(x), tp = typ(p);
    1168             :   pari_sp av;
    1169             : 
    1170      205830 :   switch(tp)
    1171             :   {
    1172             :     case t_INT:
    1173      197969 :       if (signe(p) && !is_pm1(p)) break;
    1174          28 :       pari_err_DOMAIN("gvaluation", "p", "=", p, p);
    1175             :     case t_POL:
    1176        7854 :       if (degpol(p) > 0) break;
    1177             :     default:
    1178           7 :       pari_err_DOMAIN("gvaluation", "p", "=", p, p);
    1179             :   }
    1180             : 
    1181      205795 :   switch(tx)
    1182             :   {
    1183             :     case t_INT:
    1184       11602 :       if (!signe(x)) return LONG_MAX;
    1185       11497 :       if (tp == t_POL) return 0;
    1186       11224 :       return Z_pval(x,p);
    1187             : 
    1188             :     case t_REAL:
    1189          49 :       if (tp == t_POL) return 0;
    1190          21 :       break;
    1191             : 
    1192             :     case t_FFELT:
    1193          28 :       if (tp == t_POL) return FF_equal0(x)? LONG_MAX: 0;
    1194          14 :       break;
    1195             : 
    1196             :     case t_INTMOD: {
    1197          77 :       GEN a = gel(x,1), b = gel(x,2);
    1198             :       long val;
    1199         140 :       if (tp == t_POL) return signe(b)? 0: LONG_MAX;
    1200          42 :       av = avma;
    1201          42 :       if (!intdvd(a, p, &a)) break;
    1202          28 :       if (!intdvd(b, p, &b)) { avma = av; return 0; }
    1203          14 :       val = 1; while (intdvd(a,p,&a) && intdvd(b,p,&b)) val++;
    1204          14 :       avma = av; return val;
    1205             :     }
    1206             : 
    1207             :     case t_FRAC:
    1208          42 :       if (tp == t_POL) return 0;
    1209          28 :       return ratval(x, p);
    1210             : 
    1211             :     case t_PADIC:
    1212      186367 :       if (tp == t_POL) return 0;
    1213      186353 :       if (!equalii(p,gel(x,2))) break;
    1214      186346 :       return valp(x);
    1215             : 
    1216             :     case t_POLMOD: {
    1217          35 :       GEN a = gel(x,1), b = gel(x,2);
    1218             :       long v, val;
    1219          35 :       if (tp == t_INT) return gvaluation(b,p);
    1220          21 :       v = varn(p);
    1221          21 :       if (varn(a) != v) return 0;
    1222          21 :       av = avma;
    1223          21 :       a = RgX_divrem(a, p, ONLY_DIVIDES);
    1224          21 :       if (!a) break;
    1225          14 :       if (typ(b) != t_POL || varn(b) != v ||
    1226           7 :           !(b = RgX_divrem(b, p, ONLY_DIVIDES)) ) { avma = av; return 0; }
    1227           7 :       val = 1;
    1228          21 :       while ((a = RgX_divrem(a, p, ONLY_DIVIDES)) &&
    1229           7 :              (b = RgX_divrem(b, p, ONLY_DIVIDES)) ) val++;
    1230           7 :       avma = av; return val;
    1231             :     }
    1232             :     case t_POL: {
    1233        7308 :       if (tp == t_POL) {
    1234        7175 :         long vp = varn(p), vx = varn(x);
    1235        7175 :         if (vp == vx)
    1236             :         {
    1237             :           long val;
    1238        7168 :           if (RgX_is_monomial(p)) return RgX_val(x) / degpol(p);
    1239           7 :           av = avma;
    1240           7 :           for (val=0; ; val++)
    1241             :           {
    1242           7 :             x = RgX_divrem(x,p,ONLY_DIVIDES);
    1243           7 :             if (!x) { avma = av; return val; }
    1244           0 :             if (gc_needed(av,1))
    1245             :             {
    1246           0 :               if(DEBUGMEM>1) pari_warn(warnmem,"gvaluation");
    1247           0 :               x = gerepilecopy(av, x);
    1248             :             }
    1249           0 :           }
    1250             :         }
    1251           7 :         if (varncmp(vx, vp) > 0) return 0;
    1252             :       }
    1253         133 :       return minval(x,p);
    1254             :     }
    1255             : 
    1256             :     case t_SER: {
    1257         175 :       if (tp == t_POL) {
    1258         161 :         long vp = varn(p), vx = varn(x);
    1259         161 :         if (vp == vx)
    1260             :         {
    1261         154 :           long val = RgX_val(p);
    1262         154 :           if (!val) pari_err_DOMAIN("gvaluation", "p", "=", p, p);
    1263         147 :           return (long)(valp(x) / val);
    1264             :         }
    1265           7 :         if (varncmp(vx, vp) > 0) return 0;
    1266             :       }
    1267          14 :       return minval(x,p);
    1268             :     }
    1269             : 
    1270             :     case t_RFRAC:
    1271          28 :       return gvaluation(gel(x,1),p) - gvaluation(gel(x,2),p);
    1272             : 
    1273             :     case t_COMPLEX: case t_QUAD: case t_VEC: case t_COL: case t_MAT:
    1274          84 :       return minval(x,p);
    1275             :   }
    1276          63 :   pari_err_OP("valuation", x,p);
    1277             :   return 0; /* LCOV_EXCL_LINE */
    1278             : }
    1279             : GEN
    1280        3661 : gpvaluation(GEN x, GEN p)
    1281             : {
    1282        3661 :   long v = gvaluation(x,p);
    1283        3563 :   return v == LONG_MAX? mkoo(): stoi(v);
    1284             : }
    1285             : 
    1286             : /* x is non-zero */
    1287             : long
    1288    12623603 : u_lvalrem(ulong x, ulong p, ulong *py)
    1289             : {
    1290             :   ulong vx;
    1291    12623603 :   if (p == 2) { vx = vals(x); *py = x >> vx; return vx; }
    1292    10438015 :   for(vx = 0;;)
    1293             :   {
    1294    21128288 :     if (x % p) { *py = x; return vx; }
    1295    10690273 :     x /= p; /* gcc is smart enough to make a single div */
    1296    10690273 :     vx++;
    1297    10690273 :   }
    1298             : }
    1299             : long
    1300    10078026 : u_lval(ulong x, ulong p)
    1301             : {
    1302             :   ulong vx;
    1303    10078026 :   if (p == 2) return vals(x);
    1304     9498037 :   for(vx = 0;;)
    1305             :   {
    1306    27643621 :     if (x % p) return vx;
    1307    18145584 :     x /= p; /* gcc is smart enough to make a single div */
    1308    18145584 :     vx++;
    1309    18145584 :   }
    1310             : }
    1311             : 
    1312             : long
    1313      350054 : z_lval(long s, ulong p) { return u_lval(labs(s), p); }
    1314             : long
    1315           0 : z_lvalrem(long s, ulong p, long *py)
    1316             : {
    1317             :   long v;
    1318           0 :   if (s < 0)
    1319             :   {
    1320           0 :     ulong u = (ulong)-s;
    1321           0 :     v = u_lvalrem(u, p, &u);
    1322           0 :     *py = -(long)u;
    1323             :   }
    1324             :   else
    1325             :   {
    1326           0 :     ulong u = (ulong)s;
    1327           0 :     v = u_lvalrem(u, p, &u);
    1328           0 :     *py = (long)u;
    1329             :   }
    1330           0 :   return v;
    1331             : }
    1332             : /* assume |p| > 1 */
    1333             : long
    1334       42217 : z_pval(long s, GEN p)
    1335             : {
    1336       42217 :   if (lgefint(p) > 3) return 0;
    1337       42217 :   return z_lval(s, uel(p,2));
    1338             : }
    1339             : /* assume |p| > 1 */
    1340             : long
    1341           0 : z_pvalrem(long s, GEN p, long *py)
    1342             : {
    1343           0 :   if (lgefint(p) > 3) { *py = s; return 0; }
    1344           0 :   return z_lvalrem(s, uel(p,2), py);
    1345             : }
    1346             : 
    1347             : /* return v_q(x) and set *py = x / q^v_q(x), using divide & conquer */
    1348             : static long
    1349     1374265 : Z_pvalrem_DC(GEN x, GEN q, GEN *py)
    1350             : {
    1351     1374265 :   GEN r, z = dvmdii(x, q, &r);
    1352             :   long v;
    1353     1374265 :   if (r != gen_0) { *py = x; return 0; }
    1354      965149 :   if (2 * lgefint(q) <= lgefint(z)+3) /* avoid squaring if pointless */
    1355      951596 :     v = Z_pvalrem_DC(z, sqri(q), py) << 1;
    1356             :   else
    1357       13553 :   { v = 0; *py = z; }
    1358      965149 :   z = dvmdii(*py, q, &r);
    1359      965149 :   if (r != gen_0) return v + 1;
    1360      410235 :   *py = z; return v + 2;
    1361             : }
    1362             : 
    1363             : static const long VAL_DC_THRESHOLD = 16;
    1364             : 
    1365             : long
    1366    10810757 : Z_lval(GEN x, ulong p)
    1367             : {
    1368             :   long vx;
    1369             :   pari_sp av;
    1370    10810757 :   if (p == 2) return vali(x);
    1371     7622109 :   if (lgefint(x) == 3) return u_lval(uel(x,2), p);
    1372      874894 :   av = avma;
    1373      874894 :   for(vx = 0;;)
    1374             :   {
    1375             :     ulong r;
    1376     6205197 :     GEN q = diviu_rem(x, p, &r);
    1377     7080091 :     if (r) break;
    1378     5445875 :     vx++; x = q;
    1379     5445875 :     if (vx == VAL_DC_THRESHOLD) {
    1380      115572 :       if (p == 1) pari_err_DOMAIN("Z_lval", "p", "=", gen_1, gen_1);
    1381      115572 :       vx += Z_pvalrem_DC(x, sqru(p), &x) << 1;
    1382      115572 :       q = diviu_rem(x, p, &r); if (!r) vx++;
    1383      115572 :       break;
    1384             :     }
    1385     5330303 :   }
    1386      874894 :   avma = av; return vx;
    1387             : }
    1388             : long
    1389     8332408 : Z_lvalrem(GEN x, ulong p, GEN *py)
    1390             : {
    1391             :   long vx, sx;
    1392             :   pari_sp av;
    1393     8332408 :   if (p == 2) { vx = vali(x); *py = shifti(x, -vx); return vx; }
    1394     6094016 :   if (lgefint(x) == 3) {
    1395             :     ulong u;
    1396     3921521 :     vx = u_lvalrem(uel(x,2), p, &u);
    1397     3921521 :     *py = signe(x) < 0? utoineg(u): utoipos(u);
    1398     3921520 :     return vx;
    1399             :   }
    1400     2172495 :   av = avma; (void)new_chunk(lgefint(x));
    1401     2172495 :   sx = signe(x);
    1402     2172495 :   for(vx = 0;;)
    1403             :   {
    1404             :     ulong r;
    1405     9932622 :     GEN q = diviu_rem(x, p, &r);
    1406    12105117 :     if (r) break;
    1407     8059380 :     vx++; x = q;
    1408     8059380 :     if (vx == VAL_DC_THRESHOLD) {
    1409      299253 :       if (p == 1) pari_err_DOMAIN("Z_lvalrem", "p", "=", gen_1, gen_1);
    1410      299253 :       vx += Z_pvalrem_DC(x, sqru(p), &x) << 1;
    1411      299253 :       q = diviu_rem(x, p, &r); if (!r) { vx++; x = q; }
    1412      299253 :       break;
    1413             :     }
    1414     7760127 :   }
    1415     2172495 :   avma = av; *py = icopy(x); setsigne(*py, sx); return vx;
    1416             : }
    1417             : 
    1418             : /* Is |q| <= p ? */
    1419             : static int
    1420   173693537 : isless_iu(GEN q, ulong p) {
    1421   173693537 :   long l = lgefint(q);
    1422   173693537 :   return l==2 || (l == 3 && uel(q,2) <= p);
    1423             : }
    1424             : 
    1425             : long
    1426   394128076 : u_lvalrem_stop(ulong *n, ulong p, int *stop)
    1427             : {
    1428   394128076 :   ulong N = *n, q = N / p, r = N % p; /* gcc makes a single div */
    1429   394128076 :   long v = 0;
    1430   394128076 :   if (!r)
    1431             :   {
    1432    32564855 :     do { v++; N = q; q = N / p; r = N % p; } while (!r);
    1433    21465170 :     *n = N;
    1434             :   }
    1435   394128076 :   *stop = q <= p; return v;
    1436             : }
    1437             : /* Assume n > 0. Return v_p(n), set *n := n/p^v_p(n). Set 'stop' if now
    1438             :  * n < p^2 [implies n prime if no prime < p divides n] */
    1439             : long
    1440   447884215 : Z_lvalrem_stop(GEN *n, ulong p, int *stop)
    1441             : {
    1442             :   pari_sp av;
    1443             :   long v;
    1444             :   ulong r;
    1445             :   GEN N, q;
    1446             : 
    1447   447884215 :   if (lgefint(*n) == 3)
    1448             :   {
    1449   274191954 :     r = (*n)[2];
    1450   274191954 :     v = u_lvalrem_stop(&r, p, stop);
    1451   274637764 :     if (v) *n = utoipos(r);
    1452   274637495 :     return v;
    1453             :   }
    1454   173692261 :   av = avma; v = 0; q = diviu_rem(*n, p, &r);
    1455   173692789 :   if (r) avma = av;
    1456             :   else
    1457             :   {
    1458             :     do {
    1459      678283 :       v++; N = q;
    1460      678283 :       if (v == VAL_DC_THRESHOLD)
    1461             :       {
    1462        7844 :         v += Z_pvalrem_DC(N,sqru(p),&N) << 1;
    1463        7844 :         q = diviu_rem(N, p, &r); if (!r) { v++; N = q; }
    1464        7844 :         break;
    1465             :       }
    1466      670439 :       q = diviu_rem(N, p, &r);
    1467      670439 :     } while (!r);
    1468      275617 :     *n = N;
    1469             :   }
    1470   173692789 :   *stop = isless_iu(q,p); return v;
    1471             : }
    1472             : 
    1473             : /* x is a non-zero integer, |p| > 1 */
    1474             : long
    1475     6028487 : Z_pvalrem(GEN x, GEN p, GEN *py)
    1476             : {
    1477             :   long vx;
    1478             :   pari_sp av;
    1479             : 
    1480     6028487 :   if (lgefint(p) == 3) return Z_lvalrem(x, uel(p,2), py);
    1481      132436 :   if (lgefint(x) == 3) { *py = icopy(x); return 0; }
    1482        3369 :   av = avma; vx = 0; (void)new_chunk(lgefint(x));
    1483             :   for(;;)
    1484             :   {
    1485       12507 :     GEN r, q = dvmdii(x,p,&r);
    1486       12507 :     if (r != gen_0) { avma = av; *py = icopy(x); return vx; }
    1487        9138 :     vx++; x = q;
    1488        9138 :   }
    1489             : }
    1490             : long
    1491      385511 : u_pvalrem(ulong x, GEN p, ulong *py)
    1492             : {
    1493      385511 :   if (lgefint(p) == 3) return u_lvalrem(x, uel(p,2), py);
    1494         459 :   *py = x; return 0;
    1495             : }
    1496             : long
    1497        2002 : u_pval(ulong x, GEN p)
    1498             : {
    1499        2002 :   if (lgefint(p) == 3) return u_lval(x, uel(p,2));
    1500           0 :   return 0;
    1501             : }
    1502             : long
    1503     6803891 : Z_pval(GEN x, GEN p) {
    1504             :   long vx;
    1505             :   pari_sp av;
    1506             : 
    1507     6803891 :   if (lgefint(p) == 3) return Z_lval(x, uel(p,2));
    1508       76153 :   if (lgefint(x) == 3) return 0;
    1509       70245 :   av = avma; vx = 0;
    1510             :   for(;;)
    1511             :   {
    1512       90689 :     GEN r, q = dvmdii(x,p,&r);
    1513       90689 :     if (r != gen_0) { avma = av; return vx; }
    1514       20444 :     vx++; x = q;
    1515       20444 :   }
    1516             : }
    1517             : 
    1518             : /* return v_p(n!) = [n/p] + [n/p^2] + ... */
    1519             : long
    1520       67421 : factorial_lval(ulong n, ulong p)
    1521             : {
    1522       67421 :   ulong q = p, v = 0;
    1523      110331 :   do { v += n/q; q *= p; } while (n >= q);
    1524       67421 :   return (long)v;
    1525             : }
    1526             : 
    1527             : /********** Same for "containers" ZX / ZV / ZC **********/
    1528             : 
    1529             : /* If the t_INT q divides the ZX/ZV x, return the quotient. Otherwise NULL.
    1530             :  * Stack clean; assumes lg(x) > 1 */
    1531             : static GEN
    1532        4361 : gen_Z_divides(GEN x, GEN q, long imin)
    1533             : {
    1534             :   long i, l;
    1535        4361 :   GEN y = cgetg_copy(x, &l);
    1536             : 
    1537        4361 :   y[1] = x[1]; /* Needed for ZX; no-op if ZV, overwritten in first iteration */
    1538       83510 :   for (i = imin; i < l; i++)
    1539             :   {
    1540       81767 :     GEN r, xi = gel(x,i);
    1541       81767 :     if (!signe(xi)) { gel(y,i) = xi; continue; }
    1542       50568 :     gel(y,i) = dvmdii(xi, q, &r);
    1543       50568 :     if (r != gen_0) { avma = (pari_sp)(y+l); return NULL; }
    1544             :   }
    1545        1743 :   return y;
    1546             : }
    1547             : /* If q divides the ZX/ZV x, return the quotient. Otherwise NULL.
    1548             :  * Stack clean; assumes lg(x) > 1 */
    1549             : static GEN
    1550        2681 : gen_z_divides(GEN x, ulong q, long imin)
    1551             : {
    1552             :   long i, l;
    1553        2681 :   GEN y = cgetg_copy(x, &l);
    1554             : 
    1555        2681 :   y[1] = x[1]; /* Needed for ZX; no-op if ZV, overwritten in first iteration */
    1556       36568 :   for (i = imin; i < l; i++)
    1557             :   {
    1558             :     ulong r;
    1559       36218 :     GEN xi = gel(x,i);
    1560       36218 :     if (!signe(xi)) { gel(y,i) = xi; continue; }
    1561       22680 :     gel(y,i) = diviu_rem(xi, q, &r);
    1562       22680 :     if (r) { avma = (pari_sp)(y+l); return NULL; }
    1563       20349 :     affectsign_safe(xi, &gel(y,i));
    1564             :   }
    1565         350 :   return y;
    1566             : }
    1567             : 
    1568             : /* return v_q(x) and set *py = x / q^v_q(x), using divide & conquer */
    1569             : static long
    1570        6998 : gen_pvalrem_DC(GEN x, GEN q, GEN *py, long imin)
    1571             : {
    1572             : 
    1573        6998 :   pari_sp av = avma;
    1574        6998 :   long v, i, l, lz = LONG_MAX;
    1575        6998 :   GEN y = cgetg_copy(x, &l);
    1576             : 
    1577        6998 :   y[1] = x[1];
    1578      121467 :   for (i = imin; i < l; i++)
    1579             :   {
    1580      117106 :     GEN r, xi = gel(x,i);
    1581      117106 :     if (!signe(xi)) { gel(y,i) = xi; continue; }
    1582       74485 :     gel(y,i) = dvmdii(xi, q, &r);
    1583       74485 :     if (r != gen_0) { avma = av; *py = x; return 0; }
    1584       71848 :     lz = minss(lz, lgefint(gel(y,i)));
    1585             :   }
    1586        4361 :   if (2 * lgefint(q) <= lz+3) /* avoid squaring if pointless */
    1587        4303 :     v = gen_pvalrem_DC(y, sqri(q), py, imin) << 1;
    1588             :   else
    1589          58 :   { v = 0; *py = y; }
    1590             : 
    1591        4361 :   y = gen_Z_divides(*py, q, imin);
    1592        4361 :   if (!y) return v+1;
    1593        1743 :   *py = y; return v+2;
    1594             : }
    1595             : 
    1596             : static long
    1597        3976 : gen_2val(GEN x, long imin)
    1598             : {
    1599        3976 :   long i, lx = lg(x), v = LONG_MAX;
    1600        7401 :   for (i = imin; i < lx; i++)
    1601             :   {
    1602        7345 :     GEN c = gel(x,i);
    1603             :     long w;
    1604        7345 :     if (!signe(c)) continue;
    1605        4423 :     w = vali(c);
    1606        4423 :     if (w < v) { v = w; if (!v) break; }
    1607             :   }
    1608        3976 :   return v;
    1609             : }
    1610             : static long
    1611       10748 : gen_lval(GEN x, ulong p, long imin)
    1612             : {
    1613             :   long i, lx, v;
    1614             :   pari_sp av;
    1615             :   GEN y;
    1616       10748 :   if (p == 2) return gen_2val(x, imin);
    1617        6772 :   av = avma;
    1618        6772 :   lx = lg(x); y = leafcopy(x);
    1619        6877 :   for(v = 0;; v++)
    1620        8599 :     for (i = imin; i < lx; i++)
    1621             :     {
    1622        8494 :       ulong r; gel(y,i) = diviu_rem(gel(y,i), p, &r);
    1623        8494 :       if (r) { avma = av; return v; }
    1624         105 :     }
    1625             : }
    1626             : long
    1627          42 : ZX_lval(GEN x, ulong p) { return gen_lval(x, p, 2); }
    1628             : long
    1629           0 : ZV_lval(GEN x, ulong p) { return gen_lval(x, p, 1); }
    1630             : 
    1631             : static long
    1632       12880 : gen_pval(GEN x, GEN p, long imin)
    1633             : {
    1634             :   long i, lx, v;
    1635             :   pari_sp av;
    1636             :   GEN y;
    1637       12880 :   if (lgefint(p) == 3) return gen_lval(x, p[2], imin);
    1638        2174 :   av = avma;
    1639        2174 :   lx = lg(x); y = leafcopy(x);
    1640        2174 :   for(v = 0;; v++)
    1641             :   {
    1642        2174 :     if (v == VAL_DC_THRESHOLD)
    1643             :     {
    1644           0 :       if (is_pm1(p)) pari_err_DOMAIN("gen_pval", "p", "=", p, p);
    1645           0 :       v += gen_pvalrem_DC(y, p, &y, imin);
    1646           0 :       avma = av; return v;
    1647             :     }
    1648             : 
    1649        2174 :     for (i = imin; i < lx; i++)
    1650             :     {
    1651        2174 :       GEN r; gel(y,i) = dvmdii(gel(y,i), p, &r);
    1652        2174 :       if (r != gen_0) { avma = av; return v; }
    1653             :     }
    1654           0 :   }
    1655             : }
    1656             : long
    1657        6363 : ZX_pval(GEN x, GEN p) { return gen_pval(x, p, 2); }
    1658             : long
    1659        6517 : ZV_pval(GEN x, GEN p) { return gen_pval(x, p, 1); }
    1660             : /* v = 0 (mod p) */
    1661             : int
    1662         245 : ZV_Z_dvd(GEN v, GEN p)
    1663             : {
    1664         245 :   pari_sp av = avma;
    1665         245 :   long i, l = lg(v);
    1666         889 :   for (i=1; i<l; i++)
    1667         672 :     if (!dvdii(gel(v,i), p)) { avma = av; return 0; }
    1668         217 :   avma = av; return 1;
    1669             : }
    1670             : 
    1671             : static long
    1672      300752 : gen_2valrem(GEN x, GEN *px, long imin)
    1673             : {
    1674      300752 :   long i, lx = lg(x), v = LONG_MAX;
    1675             :   GEN z;
    1676     3237868 :   for (i = imin; i < lx; i++)
    1677             :   {
    1678     3062609 :     GEN c = gel(x,i);
    1679             :     long w;
    1680     3062609 :     if (!signe(c)) continue;
    1681     2923554 :     w = vali(c);
    1682     2923554 :     if (w < v) {
    1683      596915 :       v = w;
    1684      596915 :       if (!v) { *px = x; return 0; } /* early abort */
    1685             :     }
    1686             :   }
    1687      175259 :   z = cgetg_copy(x, &lx); z[1] = x[1];
    1688      175259 :   for (i=imin; i<lx; i++) gel(z,i) = shifti(gel(x,i), -v);
    1689      175259 :   *px = z; return v;
    1690             : }
    1691             : static long
    1692      645655 : gen_lvalrem(GEN x, ulong p, GEN *px, long imin)
    1693             : {
    1694             :   long i, lx, v;
    1695             :   GEN y;
    1696      645655 :   if (p == 2) return gen_2valrem(x, px, imin);
    1697      344903 :   y = cgetg_copy(x, &lx);
    1698      344903 :   y[1] = x[1];
    1699      344903 :   x = leafcopy(x);
    1700      760768 :   for(v = 0;; v++)
    1701             :   {
    1702      760768 :     if (v == VAL_DC_THRESHOLD)
    1703             :     {
    1704        2681 :       if (p == 1) pari_err_DOMAIN("gen_lvalrem", "p", "=", gen_1, gen_1);
    1705        2681 :       v += gen_pvalrem_DC(x, sqru(p), px, imin) << 1;
    1706        2681 :       x = gen_z_divides(*px, p, imin);
    1707        2681 :       if (x) { *px = x; v++; }
    1708        2681 :       return v;
    1709             :     }
    1710             : 
    1711     6038664 :     for (i = imin; i < lx; i++)
    1712             :     {
    1713     5622799 :       ulong r; gel(y,i) = diviu_rem(gel(x,i), p, &r);
    1714     5622799 :       if (r) { *px = x; return v; }
    1715     5280577 :       affectsign_safe(gel(x,i), &gel(y,i));
    1716             :     }
    1717      415865 :     swap(x, y);
    1718      415865 :   }
    1719             : }
    1720             : long
    1721           0 : ZX_lvalrem(GEN x, ulong p, GEN *px) { return gen_lvalrem(x,p,px, 2); }
    1722             : long
    1723           0 : ZV_lvalrem(GEN x, ulong p, GEN *px) { return gen_lvalrem(x,p,px, 1); }
    1724             : 
    1725             : static long
    1726      645859 : gen_pvalrem(GEN x, GEN p, GEN *px, long imin)
    1727             : {
    1728             :   long i, lx, v;
    1729             :   GEN y;
    1730      645859 :   if (lgefint(p) == 3) return gen_lvalrem(x, p[2], px, imin);
    1731         204 :   y = cgetg_copy(x, &lx);
    1732         204 :   y[1] = x[1];
    1733         204 :   x = leafcopy(x);
    1734         930 :   for(v = 0;; v++)
    1735             :   {
    1736         930 :     if (v == VAL_DC_THRESHOLD)
    1737             :     {
    1738          14 :       if (is_pm1(p)) pari_err_DOMAIN("gen_pvalrem", "p", "=", p, p);
    1739          14 :       return v + gen_pvalrem_DC(x, p, px, imin);
    1740             :     }
    1741             : 
    1742        9153 :     for (i = imin; i < lx; i++)
    1743             :     {
    1744        8427 :       GEN r; gel(y,i) = dvmdii(gel(x,i), p, &r);
    1745        8427 :       if (r != gen_0) { *px = x; return v; }
    1746             :     }
    1747         726 :     swap(x, y);
    1748         726 :   }
    1749             : }
    1750             : long
    1751      538937 : ZX_pvalrem(GEN x, GEN p, GEN *px) { return gen_pvalrem(x,p,px, 2); }
    1752             : long
    1753      106922 : ZV_pvalrem(GEN x, GEN p, GEN *px) { return gen_pvalrem(x,p,px, 1); }
    1754             : 
    1755             : /*******************************************************************/
    1756             : /*                                                                 */
    1757             : /*                       NEGATION: Create -x                       */
    1758             : /*                                                                 */
    1759             : /*******************************************************************/
    1760             : 
    1761             : GEN
    1762   204985309 : gneg(GEN x)
    1763             : {
    1764             :   long lx, i;
    1765             :   GEN y;
    1766             : 
    1767   204985309 :   switch(typ(x))
    1768             :   {
    1769             :     case t_INT:
    1770    63076079 :       return signe(x)? negi(x): gen_0;
    1771             :     case t_REAL:
    1772    97984308 :       return mpneg(x);
    1773             : 
    1774      117509 :     case t_INTMOD: y=cgetg(3,t_INTMOD);
    1775      117509 :       gel(y,1) = icopy(gel(x,1));
    1776      117509 :       gel(y,2) = signe(gel(x,2))? subii(gel(y,1),gel(x,2)): gen_0;
    1777      117509 :       break;
    1778             : 
    1779             :     case t_FRAC:
    1780      495037 :       y = cgetg(3, t_FRAC);
    1781      495037 :       gel(y,1) = negi(gel(x,1));
    1782      495037 :       gel(y,2) = icopy(gel(x,2)); break;
    1783             : 
    1784             :     case t_COMPLEX:
    1785    41885742 :       y=cgetg(3, t_COMPLEX);
    1786    41885742 :       gel(y,1) = gneg(gel(x,1));
    1787    41885742 :       gel(y,2) = gneg(gel(x,2));
    1788    41885742 :       break;
    1789             : 
    1790      103740 :     case t_POLMOD: y=cgetg(3,t_POLMOD);
    1791      103740 :       gel(y,1) = RgX_copy(gel(x,1));
    1792      103740 :       gel(y,2) = gneg(gel(x,2)); break;
    1793             : 
    1794             :     case t_RFRAC:
    1795      153090 :       y = cgetg(3, t_RFRAC);
    1796      153090 :       gel(y,1) = gneg(gel(x,1));
    1797      153090 :       gel(y,2) = RgX_copy(gel(x,2)); break;
    1798             : 
    1799             :     case t_PADIC:
    1800        6860 :       if (!signe(gel(x,4))) return gcopy(x);
    1801        5859 :       y = cgetg(5, t_PADIC);
    1802        5859 :       y[1] = x[1];
    1803        5859 :       gel(y,2) = icopy(gel(x,2));
    1804        5859 :       gel(y,3) = icopy(gel(x,3));
    1805        5859 :       gel(y,4) = subii(gel(x,3),gel(x,4));
    1806        5859 :       break;
    1807             : 
    1808             :     case t_QUAD:
    1809          42 :       y=cgetg(4,t_QUAD);
    1810          42 :       gel(y,1) = ZX_copy(gel(x,1));
    1811          42 :       gel(y,2) = gneg(gel(x,2));
    1812          42 :       gel(y,3) = gneg(gel(x,3)); break;
    1813             : 
    1814       34119 :     case t_FFELT: return FF_neg(x);
    1815     1029052 :     case t_POL: return RgX_neg(x);
    1816             :     case t_SER:
    1817        1001 :       y = cgetg_copy(x, &lx); y[1] = x[1];
    1818        1001 :       for (i=2; i<lx; i++) gel(y,i) = gneg(gel(x,i));
    1819        1001 :       break;
    1820       22862 :     case t_VEC: return RgV_neg(x);
    1821       72641 :     case t_COL: return RgC_neg(x);
    1822        2471 :     case t_MAT: return RgM_neg(x);
    1823         756 :     case t_INFINITY: return inf_get_sign(x) == 1? mkmoo(): mkoo();
    1824             :     default:
    1825           0 :       pari_err_TYPE("gneg",x);
    1826             :       return NULL; /* LCOV_EXCL_LINE */
    1827             :   }
    1828    42762020 :   return y;
    1829             : }
    1830             : 
    1831             : GEN
    1832    41037513 : gneg_i(GEN x)
    1833             : {
    1834             :   long lx, i;
    1835             :   GEN y;
    1836             : 
    1837    41037513 :   switch(typ(x))
    1838             :   {
    1839             :     case t_INT:
    1840    21865203 :       return signe(x)? negi(x): gen_0;
    1841             :     case t_REAL:
    1842     4662687 :       return mpneg(x);
    1843             : 
    1844      544252 :     case t_INTMOD: y=cgetg(3,t_INTMOD);
    1845      544252 :       gel(y,1) = gel(x,1);
    1846      544252 :       gel(y,2) = signe(gel(x,2))? subii(gel(y,1),gel(x,2)): gen_0;
    1847      544252 :       break;
    1848             : 
    1849             :     case t_FRAC:
    1850     1075947 :       y = cgetg(3, t_FRAC);
    1851     1075947 :       gel(y,1) = negi(gel(x,1));
    1852     1075947 :       gel(y,2) = gel(x,2); break;
    1853             : 
    1854             :     case t_COMPLEX:
    1855     1271741 :       y = cgetg(3, t_COMPLEX);
    1856     1271741 :       gel(y,1) = gneg_i(gel(x,1));
    1857     1271741 :       gel(y,2) = gneg_i(gel(x,2)); break;
    1858             : 
    1859      126760 :     case t_PADIC: y = cgetg(5,t_PADIC);
    1860      126760 :       y[1] = x[1];
    1861      126760 :       gel(y,2) = gel(x,2);
    1862      126760 :       gel(y,3) = gel(x,3);
    1863      126760 :       gel(y,4) = signe(gel(x,4))? subii(gel(x,3),gel(x,4)): gen_0; break;
    1864             : 
    1865       62600 :     case t_POLMOD: y=cgetg(3,t_POLMOD);
    1866       62600 :       gel(y,1) = gel(x,1);
    1867       62600 :       gel(y,2) = gneg_i(gel(x,2)); break;
    1868             : 
    1869       85050 :     case t_FFELT: return FF_neg_i(x);
    1870             : 
    1871         630 :     case t_QUAD: y=cgetg(4,t_QUAD);
    1872         630 :       gel(y,1) = gel(x,1);
    1873         630 :       gel(y,2) = gneg_i(gel(x,2));
    1874         630 :       gel(y,3) = gneg_i(gel(x,3)); break;
    1875             : 
    1876             :     case t_VEC: case t_COL: case t_MAT:
    1877       17633 :       y = cgetg_copy(x, &lx);
    1878       17633 :       for (i=1; i<lx; i++) gel(y,i) = gneg_i(gel(x,i));
    1879       17633 :       break;
    1880             : 
    1881             :     case t_POL: case t_SER:
    1882     6326528 :       y = cgetg_copy(x, &lx); y[1]=x[1];
    1883     6326528 :       for (i=2; i<lx; i++) gel(y,i) = gneg_i(gel(x,i));
    1884     6326528 :       break;
    1885             : 
    1886             :     case t_RFRAC:
    1887     4998482 :       y = cgetg(3, t_RFRAC);
    1888     4998482 :       gel(y,1) = gneg_i(gel(x,1));
    1889     4998482 :       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    14424573 :   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     9902580 : gabs(GEN x, long prec)
    1919             : {
    1920             :   long lx, i;
    1921             :   pari_sp av, tetpil;
    1922             :   GEN y,p1;
    1923             : 
    1924     9902580 :   switch(typ(x))
    1925             :   {
    1926             :     case t_INT: case t_REAL:
    1927     7476237 :       return mpabs(x);
    1928             : 
    1929             :     case t_FRAC:
    1930        3801 :       return absfrac(x);
    1931             : 
    1932             :     case t_COMPLEX:
    1933     2414107 :       av=avma; p1=cxnorm(x);
    1934     2414107 :       switch(typ(p1))
    1935             :       {
    1936             :         case t_INT:
    1937         889 :           if (!Z_issquareall(p1, &y)) break;
    1938         693 :           return gerepileupto(av, y);
    1939             :         case t_FRAC: {
    1940             :           GEN a,b;
    1941         112 :           if (!Z_issquareall(gel(p1,1), &a)) break;
    1942          42 :           if (!Z_issquareall(gel(p1,2), &b)) break;
    1943           0 :           return gerepileupto(av, gdiv(a,b));
    1944             :         }
    1945             :       }
    1946     2413414 :       tetpil=avma;
    1947     2413414 :       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        8407 :       y = cgetg_copy(x, &lx);
    1964        8407 :       for (i=1; i<lx; i++) gel(y,i) = gabs(gel(x,i),prec);
    1965        8407 :       return y;
    1966             :   }
    1967           0 :   pari_err_TYPE("gabs",x);
    1968             :   return NULL; /* LCOV_EXCL_LINE */
    1969             : }
    1970             : 
    1971             : GEN
    1972     7832470 : gmax(GEN x, GEN y) { return gcopy(gcmp(x,y)<0? y: x); }
    1973             : GEN
    1974           0 : gmaxgs(GEN x, long s) { return (gcmpsg(s,x)>=0)? stoi(s): gcopy(x); }
    1975             : 
    1976             : GEN
    1977       93960 : gmin(GEN x, GEN y) { return gcopy(gcmp(x,y)<0? x: y); }
    1978             : GEN
    1979           0 : gmings(GEN x, long s) { return (gcmpsg(s,x)>0)? gcopy(x): stoi(s); }
    1980             : 
    1981             : long
    1982        6647 : vecindexmax(GEN x)
    1983             : {
    1984        6647 :   long lx = lg(x), i0, i;
    1985             :   GEN s;
    1986             : 
    1987        6647 :   if (lx==1) pari_err_DOMAIN("vecindexmax", "empty argument", "=", x,x);
    1988        6647 :   switch(typ(x))
    1989             :   {
    1990             :     case t_VEC: case t_COL:
    1991        6647 :       s = gel(x,i0=1);
    1992       21491 :       for (i=2; i<lx; i++)
    1993       14844 :         if (gcmp(gel(x,i),s) > 0) s = gel(x,i0=i);
    1994        6647 :       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        9097 : vecindexmin(GEN x)
    2004             : {
    2005        9097 :   long lx = lg(x), i0, i;
    2006             :   GEN s;
    2007             : 
    2008        9097 :   if (lx==1) pari_err_DOMAIN("vecindexmin", "empty argument", "=", x,x);
    2009        9097 :   switch(typ(x))
    2010             :   {
    2011             :     case t_VEC: case t_COL:
    2012        9097 :       s = gel(x,i0=1);
    2013       20735 :       for (i=2; i<lx; i++)
    2014       11638 :         if (gcmp(gel(x,i),s) < 0) s = gel(x,i0=i);
    2015        9097 :       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        2714 : vecmax0(GEN x, GEN *pi)
    2026             : {
    2027        2714 :   long i, lx = lg(x), tx = typ(x);
    2028        2714 :   if (!is_matvec_t(tx) && tx != t_VECSMALL) return gcopy(x);
    2029        2700 :   if (lx==1) pari_err_DOMAIN("vecmax", "empty argument", "=", x,x);
    2030        2679 :   switch(typ(x))
    2031             :   {
    2032             :     case t_VEC: case t_COL:
    2033        2240 :       i = vecindexmax(x); if (pi) *pi = utoipos(i);
    2034        2240 :       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        9153 : vecmin0(GEN x, GEN *pi)
    2057             : {
    2058        9153 :   long i, lx = lg(x), tx = typ(x);
    2059        9153 :   if (!is_matvec_t(tx) && tx != t_VECSMALL) return gcopy(x);
    2060        9139 :   if (lx==1) pari_err_DOMAIN("vecmin", "empty argument", "=", x,x);
    2061        9125 :   switch(typ(x))
    2062             :   {
    2063             :     case t_VEC: case t_COL:
    2064        9097 :       i = vecindexmin(x); if (pi) *pi = utoipos(i);
    2065        9097 :       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        2567 : vecmax(GEN x) { return vecmax0(x, NULL); }
    2089             : GEN
    2090        9076 : 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        1008 : gaffsg(long s, GEN x)
    2111             : {
    2112        1008 :   switch(typ(x))
    2113             :   {
    2114           0 :     case t_INT: affsi(s,x); break;
    2115        1008 :     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        1008 : }
    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        4207 : padic_to_Fp(GEN x, GEN Y) {
    2141        4207 :   pari_sp av = avma;
    2142        4207 :   GEN p = gel(x,2), z;
    2143        4207 :   long vy, vx = valp(x);
    2144        4207 :   if (!signe(Y)) pari_err_INV("padic_to_Fp",Y);
    2145        4207 :   vy = Z_pvalrem(Y,p, &z);
    2146        4207 :   if (vx < 0 || !gequal1(z)) pari_err_OP("",x, mkintmod(gen_1,Y));
    2147        4193 :   if (vx >= vy) { 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      245878 : gaffect(GEN x, GEN y)
    2180             : {
    2181      245878 :   long vx, i, lx, ly, tx = typ(x), ty = typ(y);
    2182             :   pari_sp av;
    2183             :   GEN p1, num, den;
    2184             : 
    2185      245878 :   if (tx == ty) switch(tx) {
    2186             :     case t_INT:
    2187      364685 :       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       51277 :     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        1673 :       gaffect(gel(x,1),gel(y,1));
    2204        1673 :       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       72077 :       lx = lg(x); if (lx != lg(y)) pari_err_DIM("gaffect");
    2215       72077 :       for (i=1; i<lx; i++) gaffect(gel(x,i),gel(y,i));
    2216       72077 :       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 :           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        1008 :       switch(ty)
    2250             :       {
    2251        1008 :         case t_COMPLEX: gaffect(x,gel(y,1)); gaffsg(0,gel(y,2)); break;
    2252           0 :         default: pari_err_TYPE2("=",x,y);
    2253             :       }
    2254        1008 :       break;
    2255             : 
    2256             :     case t_FRAC:
    2257          14 :       switch(ty)
    2258             :       {
    2259          14 :         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 :           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)); 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          14 :       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 :           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); 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); 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      284774 : cvtop2(GEN x, GEN y)
    2391             : {
    2392      284774 :   GEN z, p = gel(y,2);
    2393      284774 :   long v, d = signe(gel(y,4))? precp(y): 0;
    2394      284774 :   switch(typ(x))
    2395             :   {
    2396             :     case t_INT:
    2397      252490 :       if (!signe(x)) return zeropadic(p, d);
    2398      252490 :       if (d <= 0) return zeropadic(p, Z_pval(x,p));
    2399      247800 :       v = Z_pvalrem(x, p, &x);
    2400      247794 :       z = cgetg(5, t_PADIC);
    2401      247805 :       z[1] = evalprecp(d) | evalvalp(v);
    2402      247806 :       gel(z,2) = p;
    2403      247806 :       gel(z,3) = gel(y,3);
    2404      247806 :       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       32263 :       if (d <= 0) return zeropadic(p, Q_pval(x,p));
    2414       30982 :       num = gel(x,1); v = Z_pvalrem(num, p, &num);
    2415       30982 :       den = gel(x,2); if (!v) v = -Z_pvalrem(den, p, &den);
    2416       30982 :       z = cgetg(5, t_PADIC);
    2417       30982 :       z[1] = evalprecp(d) | evalvalp(v);
    2418       30982 :       gel(z,2) = p;
    2419       30982 :       gel(z,3) = gel(y,3);
    2420       30982 :       if (!is_pm1(den)) num = mulii(num, Fp_inv(den, gel(y,3)));
    2421       30982 :       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       46917 : cvtop(GEN x, GEN p, long d)
    2433             : {
    2434             :   GEN z;
    2435             :   long v;
    2436             : 
    2437       46917 :   if (typ(p) != t_INT) pari_err_TYPE("cvtop",p);
    2438       46917 :   switch(typ(x))
    2439             :   {
    2440             :     case t_INT:
    2441       31958 :       if (!signe(x)) return zeropadic(p, d);
    2442       30782 :       if (d <= 0) return zeropadic(p, Z_pval(x,p));
    2443       30782 :       v = Z_pvalrem(x, p, &x);
    2444       30782 :       z = cgetg(5, t_PADIC);
    2445       30782 :       z[1] = evalprecp(d) | evalvalp(v);
    2446       30782 :       gel(z,2) = icopy(p);
    2447       30782 :       gel(z,3) = powiu(p, d);
    2448       30782 :       gel(z,4) = modii(x, gel(z,3)); return z; /* not memory-clean */
    2449             : 
    2450             :     case t_INTMOD:
    2451           0 :       v = Z_pval(gel(x,1),p); if (v > d) v = d;
    2452           0 :       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          28 : gcvtop(GEN x, GEN p, long r)
    2485             : {
    2486             :   long i, lx;
    2487             :   GEN y;
    2488             : 
    2489          28 :   switch(typ(x))
    2490             :   {
    2491             :     case t_POL: case t_SER:
    2492           7 :       y = cgetg_copy(x, &lx); y[1] = x[1];
    2493           7 :       for (i=2; i<lx; i++) gel(y,i) = gcvtop(gel(x,i),p,r);
    2494           7 :       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          21 :   return cvtop(x,p,r);
    2501             : }
    2502             : 
    2503             : long
    2504   102899002 : gexpo_safe(GEN x)
    2505             : {
    2506   102899002 :   long tx = typ(x), lx, e, f, i;
    2507             : 
    2508   102899002 :   switch(tx)
    2509             :   {
    2510             :     case t_INT:
    2511    27040832 :       return expi(x);
    2512             : 
    2513             :     case t_FRAC:
    2514      318191 :       return expi(gel(x,1)) - expi(gel(x,2));
    2515             : 
    2516             :     case t_REAL:
    2517    49102445 :       return expo(x);
    2518             : 
    2519             :     case t_COMPLEX:
    2520    15460372 :       e = gexpo(gel(x,1));
    2521    15460372 :       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    10554957 :       lx = lg(x); f = -(long)HIGHEXPOBIT;
    2531    10554957 :       for (i=2; i<lx; i++) { e=gexpo(gel(x,i)); if (e>f) f=e; }
    2532    10554957 :       return f;
    2533             :     case t_VEC: case t_COL: case t_MAT:
    2534      422093 :       lx = lg(x); f = -(long)HIGHEXPOBIT;
    2535      422093 :       for (i=1; i<lx; i++) { e=gexpo(gel(x,i)); if (e>f) f=e; }
    2536      422093 :       return f;
    2537             :   }
    2538          77 :   return -1-(long)HIGHEXPOBIT;
    2539             : }
    2540             : long
    2541   102856834 : gexpo(GEN x)
    2542             : {
    2543   102856834 :   long e = gexpo_safe(x);
    2544   102856834 :   if (e < -(long)HIGHEXPOBIT) pari_err_TYPE("gexpo",x);
    2545   102856827 :   return e;
    2546             : }
    2547             : GEN
    2548          77 : gpexponent(GEN x)
    2549             : {
    2550          77 :   long e = gexpo(x);
    2551          77 :   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     6503510 : normalize(GEN x)
    2563             : {
    2564     6503510 :   long i, lx = lg(x), vx=varn(x), vp=valp(x);
    2565             :   GEN y, z;
    2566             : 
    2567     6503510 :   if (typ(x) != t_SER) pari_err_TYPE("normalize",x);
    2568     6503510 :   if (lx == 2) { setsigne(x,0); return x; }
    2569     6503167 :   if (lx == 3) {
    2570      175083 :     z = gel(x,2);
    2571      175083 :     if (!gequal0(z)) { setsigne(x,1); return x; }
    2572       28146 :     if (isrationalzero(z)) return zeroser(vx,vp+1);
    2573        6474 :     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        6467 :     setsigne(x,0); return x;
    2579             :   }
    2580     6599352 :   for (i=2; i<lx; i++)
    2581     6552683 :     if (! isrationalzero(gel(x,i))) break;
    2582     6328084 :   if (i == lx) return zeroser(vx,lx-2+vp);
    2583     6281415 :   z = gel(x,i);
    2584     6281415 :   while (i<lx && isexactzero(gel(x,i))) i++;
    2585     6281415 :   if (i == lx)
    2586             :   {
    2587         245 :     i -= 3; y = x + i;
    2588         245 :     stackdummy((pari_sp)y, (pari_sp)x);
    2589         245 :     gel(y,2) = z;
    2590         245 :     y[1] = evalsigne(0) | evalvalp(lx-2+vp) | evalvarn(vx);
    2591         245 :     y[0] = evaltyp(t_SER) | _evallg(3);
    2592         245 :     return y;
    2593             :   }
    2594             : 
    2595     6281170 :   i -= 2; y = x + i; lx -= i;
    2596     6281170 :   y[1] = evalsigne(1) | evalvalp(vp+i) | evalvarn(vx);
    2597     6281170 :   y[0] = evaltyp(t_SER) | evallg(lx);
    2598             : 
    2599     6281170 :   stackdummy((pari_sp)y, (pari_sp)x);
    2600     6297522 :   for (i = 2; i < lx; i++)
    2601     6296383 :     if (!gequal0(gel(y, i))) return y;
    2602        1139 :   setsigne(y, 0); return y;
    2603             : }
    2604             : 
    2605             : GEN
    2606       60942 : normalizepol_approx(GEN x, long lx)
    2607             : {
    2608             :   long i;
    2609       60942 :   for (i = lx-1; i>1; i--)
    2610       60942 :     if (! gequal0(gel(x,i))) break;
    2611       60942 :   stackdummy((pari_sp)(x + lg(x)), (pari_sp)(x + i+1));
    2612       60942 :   setlg(x, i+1); setsigne(x, i!=1); return x;
    2613             : }
    2614             : 
    2615             : GEN
    2616   183416889 : normalizepol_lg(GEN x, long lx)
    2617             : {
    2618   183416889 :   long i, LX = 0;
    2619   183416889 :   GEN KEEP = NULL;
    2620             : 
    2621   228538316 :   for (i = lx-1; i>1; i--)
    2622             :   {
    2623   209735278 :     GEN z = gel(x,i);
    2624   209735278 :     if (! gequal0(z) ) {
    2625   164617239 :       if (!LX) LX = i+1;
    2626   164617239 :       stackdummy((pari_sp)(x + lg(x)), (pari_sp)(x + LX));
    2627   164616083 :       x[0] = evaltyp(t_POL) | evallg(LX);
    2628   164614723 :       setsigne(x,1); return x;
    2629    45121428 :     } else if (!isexactzero(z)) {
    2630      261761 :       if (!LX) LX = i+1; /* to be kept as leading coeff */
    2631    44859666 :     } else if (!isrationalzero(z))
    2632      598807 :       KEEP = z; /* to be kept iff all other coeffs are exact 0s */
    2633             :   }
    2634    18803038 :   if (!LX) {
    2635    18748055 :     if (KEEP) { /* e.g. Pol(Mod(0,2)) */
    2636      326903 :       gel(x,2) = KEEP;
    2637      326903 :       LX = 3;
    2638             :     } else
    2639    18421152 :       LX = 2; /* Pol(0) */
    2640             :   }
    2641    18803038 :   stackdummy((pari_sp)(x + lg(x)), (pari_sp)(x + LX));
    2642    18803038 :   x[0] = evaltyp(t_POL) | evallg(LX);
    2643    18803038 :   setsigne(x,0); return x;
    2644             : }
    2645             : 
    2646             : /* normalize polynomial x in place */
    2647             : GEN
    2648      157756 : normalizepol(GEN x)
    2649             : {
    2650      157756 :   return normalizepol_lg(x, lg(x));
    2651             : }
    2652             : 
    2653             : int
    2654     3426319 : gsigne(GEN x)
    2655             : {
    2656     3426319 :   switch(typ(x))
    2657             :   {
    2658     3232545 :     case t_INT: case t_REAL: return signe(x);
    2659      190981 :     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) { avma = av; return sa; }
    2671          91 :       if (sa == 0) { avma = av; return sb; }
    2672          84 :       if (sb == 0) { avma = av; return sa; }
    2673             :       /* different signs, take conjugate expression */
    2674          84 :       sb = gsigne(gsub(gsqr(a), gmul(quad_disc(x), gsqr(b))));
    2675          84 :       avma = av; return sb * sa;
    2676             :     }
    2677        2667 :     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      786198 : ensure_nb(GEN L, long l)
    2692             : {
    2693      786198 :   long nmax = list_nmax(L), i, lw;
    2694             :   GEN v, w;
    2695     1572396 :   if (l <= nmax) return;
    2696         329 :   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          56 :     nmax = 32;
    2709          56 :     if (list_data(L))
    2710           0 :       pari_err(e_MISC, "store list in variable before appending elements");
    2711          56 :     v = newblock(nmax+1);
    2712          56 :     v[0] = evaltyp(t_VEC) | _evallg(1);
    2713             :   }
    2714         329 :   list_data(L) = v;
    2715         329 :   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         794 : mklist_typ(long t)
    2735             : {
    2736         794 :   GEN L = cgetg(3,t_LIST);
    2737         794 :   L[1] = evaltyp(t);
    2738         794 :   list_data(L) = NULL; return L;
    2739             : }
    2740             : 
    2741             : GEN
    2742         752 : mklist(void)
    2743             : {
    2744         752 :   return mklist_typ(t_LIST_RAW);
    2745             : }
    2746             : 
    2747             : GEN
    2748          35 : mkmap(void)
    2749             : {
    2750          35 :   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      751226 : listput(GEN L, GEN x, long index)
    2770             : {
    2771             :   long l;
    2772             :   GEN z;
    2773             : 
    2774      751226 :   if (index < 0) pari_err_COMPONENT("listput", "<", gen_0, stoi(index));
    2775      751219 :   z = list_data(L);
    2776      751219 :   l = z? lg(z): 1;
    2777             : 
    2778      751219 :   x = gclone(x);
    2779      751219 :   if (!index || index >= l)
    2780             :   {
    2781      751198 :     ensure_nb(L, l);
    2782      751198 :     z = list_data(L); /* it may change ! */
    2783      751198 :     index = l;
    2784      751198 :     l++;
    2785             :   } else
    2786          21 :     gunclone_deep( gel(z, index) );
    2787      751219 :   gel(z,index) = x;
    2788      751219 :   z[0] = evaltyp(t_VEC) | evallg(l); /*must be after gel(z,index) is set*/
    2789      751219 :   return gel(z,index);
    2790             : }
    2791             : 
    2792             : GEN
    2793      700224 : listput0(GEN L, GEN x, long index)
    2794             : {
    2795      700224 :   if (typ(L) != t_LIST || list_typ(L) != t_LIST_RAW)
    2796           0 :     pari_err_TYPE("listput",L);
    2797      700224 :   return listput(L, x, index);
    2798             : }
    2799             : 
    2800             : GEN
    2801       35014 : listinsert(GEN L, GEN x, long index)
    2802             : {
    2803             :   long l, i;
    2804             :   GEN z;
    2805             : 
    2806       35014 :   if (typ(L) != t_LIST || list_typ(L) != t_LIST_RAW)
    2807           0 :     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       43820 :   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          35 : listpop0(GEN L, long index)
    2842             : {
    2843          35 :   if (typ(L) != t_LIST || list_typ(L) != t_LIST_RAW)
    2844           0 :     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         425 : gtolist(GEN x)
    2852             : {
    2853             :   GEN y;
    2854             : 
    2855         425 :   if (!x) return mklist();
    2856         287 :   switch(typ(x))
    2857             :   {
    2858             :     case t_VEC: case t_COL:
    2859         238 :       y = mklist();
    2860         238 :       if (lg(x) == 1) return y;
    2861         224 :       list_data(y) = gcopy(x);
    2862         224 :       settyp(list_data(y), t_VEC);
    2863         224 :       return y;
    2864             :     case t_LIST:
    2865           0 :       y = mklist();
    2866           0 :       list_data(y) = list_data(x)? gcopy(list_data(x)): NULL;
    2867           0 :       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          42 :   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]; avma = av;
    2908             : }

Generated by: LCOV version 1.11