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.12.0 lcov report (development 22933-0de3639e3) Lines: 1323 1496 88.4 %
Date: 2018-08-19 05:36:10 Functions: 137 146 93.8 %
Legend: Lines: hit not hit

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

Generated by: LCOV version 1.13