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.8.0 lcov report (development 19374-ac31b96) Lines: 1324 1531 86.5 %
Date: 2016-08-30 06:11:37 Functions: 134 145 92.4 %
Legend: Lines: hit not hit

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

Generated by: LCOV version 1.11