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 - gen1.c (source / functions) Hit Total Coverage
Test: PARI/GP v2.8.0 lcov report (development 18946-c0ba5ba) Lines: 1794 1934 92.8 %
Date: 2016-05-25 Functions: 89 89 100.0 %
Legend: Lines: hit not hit | Branches: + taken - not taken # not executed Branches: 1191 1436 82.9 %

           Branch data     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                 :            : /**                         (first part)                           **/
      18                 :            : /**                                                                **/
      19                 :            : /********************************************************************/
      20                 :            : #include "pari.h"
      21                 :            : #include "paripriv.h"
      22                 :            : 
      23                 :            : /* assume z[1] was created last */
      24                 :            : #define fix_frac_if_int(z) if (is_pm1(gel(z,2)))\
      25                 :            :   z = gerepileupto((pari_sp)(z+3), gel(z,1));
      26                 :            : 
      27                 :            : /* assume z[1] was created last */
      28                 :            : #define fix_frac_if_int_GC(z,tetpil) { if (is_pm1(gel(z,2)))\
      29                 :            :   z = gerepileupto((pari_sp)(z+3), gel(z,1));\
      30                 :            : else\
      31                 :            :   gerepilecoeffssp((pari_sp)z, tetpil, z+1, 2); }
      32                 :            : 
      33                 :            : static void
      34                 :         70 : warn_coercion(GEN x, GEN y, GEN z)
      35                 :            : {
      36         [ +  + ]:         70 :   if (DEBUGLEVEL)
      37                 :         56 :    pari_warn(warner,"coercing quotient rings; moduli %Ps and %Ps -> %Ps",x,y,z);
      38                 :         70 : }
      39                 :            : 
      40                 :            : static long
      41                 :         21 : kro_quad(GEN x, GEN y)
      42                 :            : {
      43                 :         21 :   pari_sp av=avma;
      44                 :         21 :   long k = kronecker(quad_disc(x), y);
      45                 :         21 :   avma = av; return k;
      46                 :            : }
      47                 :            : 
      48                 :            : /* is -1 not a square in Zp, assume p prime */
      49                 :            : INLINE int
      50                 :         28 : Zp_nosquare_m1(GEN p) { return (mod4(p) & 2); /* 2 or 3 mod 4 */ }
      51                 :            : 
      52                 :            : static GEN addsub_pp(GEN x, GEN y, GEN(*op)(GEN,GEN));
      53                 :            : static GEN addsub_frac(GEN x, GEN y, GEN (*op)(GEN,GEN));
      54                 :            : static GEN mulpp(GEN x, GEN y);
      55                 :            : static GEN divpp(GEN x, GEN y);
      56                 :            : /* Argument codes for inline routines
      57                 :            :  * c: complex, p: padic, q: quad, f: floating point (REAL, some complex)
      58                 :            :  * R: without imaginary part (INT, REAL, INTMOD, FRAC, PADIC if -1 not square)
      59                 :            :  * T: some type (to be converted to PADIC)
      60                 :            :  */
      61                 :            : static GEN
      62                 :   43482000 : addRc(GEN x, GEN y) {
      63                 :   43482000 :   GEN z = cgetg(3,t_COMPLEX);
      64                 :   43482000 :   gel(z,1) = gadd(x,gel(y,1));
      65                 :   43482000 :   gel(z,2) = gcopy(gel(y,2)); return z;
      66                 :            : }
      67                 :            : static GEN
      68                 :   44958098 : mulRc(GEN x, GEN y) {
      69                 :   44958098 :   GEN z = cgetg(3,t_COMPLEX);
      70         [ +  + ]:   44958098 :   gel(z,1) = isintzero(gel(y,1))? gen_0: gmul(x,gel(y,1));
      71                 :   44958098 :   gel(z,2) = gmul(x,gel(y,2)); return z;
      72                 :            : }
      73                 :            : /* for INTMODs: can't simplify when Re(x) = gen_0 */
      74                 :            : static GEN
      75                 :         35 : mulRc_direct(GEN x, GEN y) {
      76                 :         35 :   GEN z = cgetg(3,t_COMPLEX);
      77                 :         35 :   gel(z,1) = gmul(x,gel(y,1));
      78                 :         35 :   gel(z,2) = gmul(x,gel(y,2)); return z;
      79                 :            : }
      80                 :            : static GEN
      81                 :     345779 : divRc(GEN x, GEN y) {
      82                 :     345779 :   GEN t = gdiv(x, cxnorm(y)), mt = gneg(t); /* left on stack for efficiency */
      83                 :     345779 :   GEN z = cgetg(3,t_COMPLEX);
      84         [ +  + ]:     345779 :   gel(z,1) = isintzero(gel(y,1))? gen_0: gmul(t, gel(y,1));
      85                 :     345779 :   gel(z,2) = gmul(mt, gel(y,2));
      86                 :     345779 :   return z;
      87                 :            : }
      88                 :            : static GEN
      89                 :    3694602 : divcR(GEN x, GEN y) {
      90                 :    3694602 :   GEN z = cgetg(3,t_COMPLEX);
      91         [ +  + ]:    3694602 :   gel(z,1) = isintzero(gel(x,1))? gen_0: gdiv(gel(x,1), y);
      92                 :    3694602 :   gel(z,2) = gdiv(gel(x,2), y); return z;
      93                 :            : }
      94                 :            : static GEN
      95                 :        679 : addRq(GEN x, GEN y) {
      96                 :        679 :   GEN z = cgetg(4,t_QUAD);
      97                 :        679 :   gel(z,1) = ZX_copy(gel(y,1));
      98                 :        679 :   gel(z,2) = gadd(x, gel(y,2));
      99                 :        679 :   gel(z,3) = gcopy(gel(y,3)); return z;
     100                 :            : }
     101                 :            : static GEN
     102                 :       1834 : mulRq(GEN x, GEN y) {
     103                 :       1834 :   GEN z = cgetg(4,t_QUAD);
     104                 :       1834 :   gel(z,1) = ZX_copy(gel(y,1));
     105                 :       1834 :   gel(z,2) = gmul(x,gel(y,2));
     106                 :       1834 :   gel(z,3) = gmul(x,gel(y,3)); return z;
     107                 :            : }
     108                 :            : static GEN
     109                 :         21 : addqf(GEN x, GEN y, long prec) { pari_sp av = avma;
     110                 :         21 :   long i = gexpo(x) - gexpo(y);
     111         [ +  - ]:         21 :   if (i > 0) prec += nbits2extraprec( i );
     112                 :         21 :   return gerepileupto(av, gadd(y, quadtofp(x, prec)));
     113                 :            : }
     114                 :            : static GEN
     115                 :    1480153 : mulrfrac(GEN x, GEN y)
     116                 :            : {
     117                 :    1480153 :   pari_sp av = avma;
     118                 :    1480153 :   GEN z, a = gel(y,1), b = gel(y,2);
     119         [ +  + ]:    1480153 :   if (is_pm1(a)) /* frequent special case */
     120                 :            :   {
     121                 :     800235 :     z = divri(x, b);
     122         [ +  + ]:     800235 :     if (signe(a) < 0) togglesign(z);
     123                 :     800235 :     return z;
     124                 :            :   }
     125                 :    1480153 :   return gerepileuptoleaf(av, divri(mulri(x,gel(y,1)), gel(y,2)));
     126                 :            : }
     127                 :            : static GEN
     128                 :         14 : mulqf(GEN x, GEN y, long prec) { pari_sp av = avma;
     129                 :         14 :   return gerepileupto(av, gmul(y, quadtofp(x, prec)));
     130                 :            : }
     131                 :            : static GEN
     132                 :         28 : divqf(GEN x, GEN y, long prec) { pari_sp av = avma;
     133                 :         28 :   return gerepileupto(av, gdiv(quadtofp(x,prec), y));
     134                 :            : }
     135                 :            : static GEN
     136                 :          7 : divfq(GEN x, GEN y, long prec) { pari_sp av = avma;
     137                 :          7 :   return gerepileupto(av, gdiv(x, quadtofp(y,prec)));
     138                 :            : }
     139                 :            : /* y PADIC, x + y by converting x to padic */
     140                 :            : static GEN
     141                 :          7 : addTp(GEN x, GEN y) { pari_sp av = avma; GEN z;
     142                 :            : 
     143         [ -  + ]:          7 :   if (!valp(y)) z = cvtop2(x,y);
     144                 :            :   else {
     145         [ -  + ]:          7 :     long l = signe(gel(y,4))? valp(y) + precp(y): valp(y);
     146                 :          7 :     z  = cvtop(x, gel(y,2), l);
     147                 :            :   }
     148                 :          7 :   return gerepileupto(av, addsub_pp(z, y, addii));
     149                 :            : }
     150                 :            : /* y PADIC, x * y by converting x to padic */
     151                 :            : static GEN
     152                 :     103526 : mulTp(GEN x, GEN y) { pari_sp av = avma;
     153                 :     103526 :   return gerepileupto(av, mulpp(cvtop2(x,y), y));
     154                 :            : }
     155                 :            : /* y PADIC, non zero x / y by converting x to padic */
     156                 :            : static GEN
     157                 :         70 : divTp(GEN x, GEN y) { pari_sp av = avma;
     158                 :         70 :   return gerepileupto(av, divpp(cvtop2(x,y), y));
     159                 :            : }
     160                 :            : /* x PADIC, x / y by converting y to padic. Assume x != 0; otherwise y
     161                 :            :  * converted to O(p^e) and division by 0 */
     162                 :            : static GEN
     163                 :       1141 : divpT(GEN x, GEN y) { pari_sp av = avma;
     164                 :       1141 :   return gerepileupto(av, divpp(x, cvtop2(y,x)));
     165                 :            : }
     166                 :            : 
     167                 :            : /* z := Mod(x,X) + Mod(y,X) [ t_INTMOD preallocated ], x,y,X INT, 0 <= x,y < X
     168                 :            :  * clean memory from z on */
     169                 :            : static GEN
     170                 :    1812810 : add_intmod_same(GEN z, GEN X, GEN x, GEN y) {
     171         [ +  + ]:    1812810 :   if (lgefint(X) == 3) {
     172                 :    1777493 :     ulong u = Fl_add(itou(x),itou(y), X[2]);
     173                 :    1777493 :     avma = (pari_sp)z; gel(z,2) = utoi(u);
     174                 :            :   }
     175                 :            :   else {
     176         [ +  + ]:      35317 :     GEN u = addii(x,y); if (cmpii(u, X) >= 0) u = subii(u, X);
     177                 :      35320 :     gel(z,2) = gerepileuptoint((pari_sp)z, u);
     178                 :            :   }
     179                 :    1812827 :   gel(z,1) = icopy(X); return z;
     180                 :            : }
     181                 :            : static GEN
     182                 :     257586 : sub_intmod_same(GEN z, GEN X, GEN x, GEN y) {
     183         [ +  + ]:     257586 :   if (lgefint(X) == 3) {
     184                 :     237081 :     ulong u = Fl_sub(itou(x),itou(y), X[2]);
     185                 :     237081 :     avma = (pari_sp)z; gel(z,2) = utoi(u);
     186                 :            :   }
     187                 :            :   else {
     188         [ +  + ]:      20505 :     GEN u = subii(x,y); if (signe(u) < 0) u = addii(u, X);
     189                 :      20503 :     gel(z,2) = gerepileuptoint((pari_sp)z, u);
     190                 :            :   }
     191                 :     257589 :   gel(z,1) = icopy(X); return z;
     192                 :            : }
     193                 :            : /* cf add_intmod_same */
     194                 :            : static GEN
     195                 :    3001909 : mul_intmod_same(GEN z, GEN X, GEN x, GEN y) {
     196         [ +  + ]:    3001909 :   if (lgefint(X) == 3) {
     197                 :    2887162 :     ulong u = Fl_mul(itou(x),itou(y), X[2]);
     198                 :    2887162 :     avma = (pari_sp)z; gel(z,2) = utoi(u);
     199                 :            :   }
     200                 :            :   else
     201                 :     114747 :     gel(z,2) = gerepileuptoint((pari_sp)z, remii(mulii(x,y), X) );
     202                 :    3001923 :   gel(z,1) = icopy(X); return z;
     203                 :            : }
     204                 :            : /* cf add_intmod_same */
     205                 :            : static GEN
     206                 :      29657 : div_intmod_same(GEN z, GEN X, GEN x, GEN y)
     207                 :            : {
     208         [ +  + ]:      29657 :   if (lgefint(X) == 3) {
     209                 :      21742 :     ulong m = uel(X,2), u = Fl_div(itou(x), itou(y), m);
     210                 :      21735 :     avma = (pari_sp)z; gel(z,2) = utoi(u);
     211                 :            :   }
     212                 :            :   else
     213                 :       7915 :     gel(z,2) = gerepileuptoint((pari_sp)z, remii(mulii(x, Fp_inv(y,X)), X) );
     214                 :      29652 :   gel(z,1) = icopy(X); return z;
     215                 :            : }
     216                 :            : 
     217                 :            : /*******************************************************************/
     218                 :            : /*                                                                 */
     219                 :            : /*        REDUCTION to IRREDUCIBLE TERMS (t_FRAC/t_RFRAC)          */
     220                 :            : /*                                                                 */
     221                 :            : /* (static routines are not memory clean, but OK for gerepileupto) */
     222                 :            : /*******************************************************************/
     223                 :            : /* Compute the denominator of (1/y) * (n/d) = n/yd, y a "scalar".
     224                 :            :  * Sanity check : avoid (1/2) / (Mod(1,2)*x + 1) "=" 1 / (0 * x + 1) */
     225                 :            : static GEN
     226                 :    9409332 : rfrac_denom_mul_scal(GEN d, GEN y)
     227                 :            : {
     228                 :    9409332 :   GEN D = RgX_Rg_mul(d, y);
     229         [ -  + ]:    9409332 :   if (lg(D) != lg(d))
     230                 :            :   { /* try to generate a meaningful diagnostic */
     231                 :          0 :     D = gdiv(leading_coeff(d), y); /* should fail */
     232                 :          0 :     pari_err_INV("gred_rfrac", y); /* better than nothing */
     233                 :            :   }
     234                 :    9409332 :   return D;
     235                 :            : }
     236                 :            : 
     237                 :            : /* d a t_POL, n a coprime t_POL of same var or "scalar". Not memory clean */
     238                 :            : GEN
     239                 :   54252909 : gred_rfrac_simple(GEN n, GEN d)
     240                 :            : {
     241                 :            :   GEN c, cn, cd, z;
     242                 :   54252909 :   long dd = degpol(d);
     243                 :            : 
     244         [ +  + ]:   54252909 :   if (dd <= 0)
     245                 :            :   {
     246         [ -  + ]:       6090 :     if (dd < 0) pari_err_INV("gred_rfrac_simple", d);
     247                 :       6090 :     n = gdiv(n, gel(d,2));
     248 [ +  + ][ +  + ]:       6090 :     if (typ(n) != t_POL || varn(n) != varn(d)) n = scalarpol(n, varn(d));
     249                 :       6090 :     return n;
     250                 :            :   }
     251                 :            : 
     252                 :   54246819 :   cd = content(d);
     253 [ +  + ][ +  + ]:   55149469 :   while (typ(n) == t_POL && !degpol(n)) n = gel(n,2);
     254 [ +  + ][ +  + ]:   54246819 :   cn = (typ(n) == t_POL && varn(n) == varn(d))? content(n): n;
     255         [ +  + ]:   54246819 :   if (!gequal1(cd)) {
     256                 :    6548420 :     d = RgX_Rg_div(d,cd);
     257         [ +  + ]:    6548420 :     if (!gequal1(cn))
     258                 :            :     {
     259         [ -  + ]:    1302229 :       if (gequal0(cn)) {
     260         [ #  # ]:          0 :         if (isexactzero(cn)) return scalarpol(cn, varn(d));
     261         [ #  # ]:          0 :         n = (cn != n)? RgX_Rg_div(n,cd): gdiv(n, cd);
     262                 :          0 :         c = gen_1;
     263                 :            :       } else {
     264         [ +  + ]:    1302229 :         n = (cn != n)? RgX_Rg_div(n,cn): gen_1;
     265                 :    1302229 :         c = gdiv(cn,cd);
     266                 :            :       }
     267                 :            :     }
     268                 :            :     else
     269                 :    5246191 :       c = ginv(cd);
     270                 :            :   } else {
     271         [ +  + ]:   47698399 :     if (!gequal1(cn))
     272                 :            :     {
     273         [ +  + ]:    2590336 :       if (gequal0(cn)) {
     274         [ +  + ]:         91 :         if (isexactzero(cn)) return scalarpol(cn, varn(d));
     275                 :         21 :         c = gen_1;
     276                 :            :       } else {
     277         [ +  + ]:    2590245 :         n = (cn != n)? RgX_Rg_div(n,cn): gen_1;
     278                 :    2590245 :         c = cn;
     279                 :            :       }
     280                 :            :     } else {
     281                 :   45108063 :       GEN y = cgetg(3,t_RFRAC);
     282                 :   45108063 :       gel(y,1) = gcopy(n);
     283                 :   45108063 :       gel(y,2) = RgX_copy(d); return y;
     284                 :            :     }
     285                 :            :   }
     286                 :            : 
     287         [ +  + ]:    9138686 :   if (typ(c) == t_POL)
     288                 :            :   {
     289                 :     905329 :     z = c;
     290         [ +  + ]:     944746 :     do { z = content(z); } while (typ(z) == t_POL);
     291                 :     905329 :     cd = denom(z);
     292                 :     905329 :     cn = gmul(c, cd);
     293                 :            :   }
     294                 :            :   else
     295                 :            :   {
     296                 :    8233357 :     cn = numer(c);
     297                 :    8233357 :     cd = denom(c);
     298                 :            :   }
     299                 :    9138686 :   z = cgetg(3,t_RFRAC);
     300                 :    9138686 :   gel(z,1) = gmul(n, cn);
     301                 :    9138686 :   gel(z,2) = rfrac_denom_mul_scal(d, cd);
     302                 :   54252909 :   return z;
     303                 :            : }
     304                 :            : 
     305                 :            : /* in rare cases x may be a t_POL, after 0/x for instance -> pol_0() */
     306                 :            : static GEN
     307                 :     155400 : fix_rfrac(GEN x, long d)
     308                 :            : {
     309                 :            :   GEN z, N, D;
     310 [ +  + ][ -  + ]:     155400 :   if (!d || typ(x) == t_POL) return x;
     311                 :     153769 :   z = cgetg(3, t_RFRAC);
     312                 :     153769 :   N = gel(x,1);
     313                 :     153769 :   D = gel(x,2);
     314         [ +  + ]:     153769 :   if (d > 0) {
     315         [ +  + ]:        203 :     gel(z, 1) = (typ(N)==t_POL && varn(N)==varn(D))? RgX_shift(N,d)
     316         [ +  + ]:     153902 :                                                    : monomialcopy(N,d,varn(D));
     317                 :     153699 :     gel(z, 2) = RgX_copy(D);
     318                 :            :   } else {
     319                 :         70 :     gel(z, 1) = gcopy(N);
     320                 :         70 :     gel(z, 2) = RgX_shift(D, -d);
     321                 :            :   }
     322                 :     155400 :   return z;
     323                 :            : }
     324                 :            : 
     325                 :            : /* assume d != 0 */
     326                 :            : static GEN
     327                 :   43370106 : gred_rfrac2_i(GEN n, GEN d)
     328                 :            : {
     329                 :            :   GEN y, z;
     330                 :            :   long v, vd, vn;
     331                 :            : 
     332                 :   43370106 :   n = simplify_shallow(n);
     333         [ +  + ]:   43370106 :   if (isrationalzero(n)) return gcopy(n);
     334                 :   36575897 :   d = simplify_shallow(d);
     335         [ +  + ]:   36575897 :   if (typ(d) != t_POL) return gdiv(n,d);
     336                 :   35396400 :   vd = varn(d);
     337         [ +  + ]:   35396400 :   if (typ(n) != t_POL)
     338                 :            :   {
     339         [ +  + ]:   19890697 :     if (varncmp(vd, gvar(n)) >= 0) return gdiv(n,d);
     340         [ +  - ]:   19889290 :     if (varncmp(vd, gvar2(n)) < 0) return gred_rfrac_simple(n,d);
     341                 :          0 :     pari_err_BUG("gred_rfrac2_i [incompatible variables]");
     342                 :            :   }
     343                 :   15505703 :   vn = varn(n);
     344         [ +  + ]:   15505703 :   if (varncmp(vd, vn) < 0) return gred_rfrac_simple(n,d);
     345         [ +  + ]:   15368127 :   if (varncmp(vd, vn) > 0) return RgX_Rg_div(n,d);
     346                 :            : 
     347                 :            :   /* now n and d are t_POLs in the same variable */
     348                 :   15208375 :   v = RgX_valrem(n, &n) - RgX_valrem(d, &d);
     349         [ +  + ]:   15208375 :   if (!degpol(d))
     350                 :            :   {
     351                 :   12229916 :     n = RgX_Rg_div(n,gel(d,2));
     352         [ +  + ]:   12229916 :     return v? RgX_mulXn(n,v): n;
     353                 :            :   }
     354                 :            : 
     355                 :            :   /* X does not divide gcd(n,d), deg(d) > 0 */
     356 [ +  + ][ +  - ]:    2978459 :   if (!isinexact(n) && !isinexact(d))
     357                 :            :   {
     358                 :    2978333 :     y = RgX_divrem(n, d, &z);
     359 [ +  + ][ +  + ]:    2978333 :     if (!signe(z)) { cgiv(z); return v? RgX_mulXn(y, v): y; }
     360                 :     155274 :     z = RgX_gcd(d, z);
     361         [ +  + ]:     155274 :     if (degpol(z)) { n = RgX_div(n,z); d = RgX_div(d,z); }
     362                 :            :   }
     363                 :   43370106 :   return fix_rfrac(gred_rfrac_simple(n,d), v);
     364                 :            : }
     365                 :            : 
     366                 :            : GEN
     367                 :   18174411 : gred_rfrac2(GEN x1, GEN x2)
     368                 :            : {
     369                 :   18174411 :   pari_sp av = avma;
     370                 :   18174411 :   return gerepileupto(av, gred_rfrac2_i(x1, x2));
     371                 :            : }
     372                 :            : 
     373                 :            : /* x1,x2 t_INT, return x1/x2 in reduced form */
     374                 :            : GEN
     375                 :   18301782 : gred_frac2(GEN x1, GEN x2)
     376                 :            : {
     377                 :   18301782 :   GEN r, y = dvmdii(x1,x2,&r);
     378                 :            :   pari_sp av;
     379                 :            : 
     380         [ +  + ]:   18301754 :   if (r == gen_0) return y; /* gen_0 intended */
     381                 :    6674232 :   av = avma; r = gcdii(x2,r);
     382         [ +  + ]:    6674232 :   if (lgefint(r) == 3)
     383                 :            :   {
     384                 :    6472089 :     ulong rr = r[2];
     385                 :    6472089 :     avma = av;
     386         [ +  + ]:    6472089 :     if (rr == 1) y = mkfraccopy(x1, x2);
     387                 :            :     else
     388                 :            :     {
     389                 :    3405851 :       y = cgetg(3,t_FRAC);
     390                 :    3405851 :       gel(y,1) = diviuexact(x1, rr);
     391                 :    3405851 :       gel(y,2) = diviuexact(x2, rr);
     392                 :            :     }
     393                 :            :   }
     394                 :            :   else
     395                 :            :   { /* rare: r left on stack for efficiency */
     396                 :     202143 :     y = cgetg(3,t_FRAC);
     397                 :     202143 :     gel(y,1) = diviiexact(x1,r);
     398                 :     202143 :     gel(y,2) = diviiexact(x2,r);
     399                 :            :   }
     400                 :   18301754 :   normalize_frac(y); return y;
     401                 :            : }
     402                 :            : 
     403                 :            : /*******************************************************************/
     404                 :            : /*                                                                 */
     405                 :            : /*                          CONJUGATION                            */
     406                 :            : /*                                                                 */
     407                 :            : /*******************************************************************/
     408                 :            : /* lift( conj(Mod(x, y)) ), assuming degpol(y) = 2, degpol(x) < 2 */
     409                 :            : static GEN
     410                 :      13594 : quad_polmod_conj(GEN x, GEN y)
     411                 :            : {
     412                 :            :   GEN z, u, v, a, b;
     413                 :            :   pari_sp av;
     414         [ -  + ]:      13594 :   if (typ(x) != t_POL) return gcopy(x);
     415 [ +  - ][ -  + ]:      13594 :   if (varn(x) != varn(y) || degpol(x) <= 0) return RgX_copy(x);
     416                 :      13594 :   a = gel(y,4); u = gel(x,3); /*Mod(ux + v, ax^2 + bx + c)*/
     417                 :      13594 :   b = gel(y,3); v = gel(x,2);
     418                 :      13594 :   z = cgetg(4, t_POL); z[1] = x[1]; av = avma;
     419                 :      13594 :   gel(z,2) = gerepileupto(av, gsub(v, gdiv(gmul(u,b), a)));
     420                 :      13594 :   gel(z,3) = gneg(u); return z;
     421                 :            : }
     422                 :            : static GEN
     423                 :      13594 : quad_polmod_norm(GEN x, GEN y)
     424                 :            : {
     425                 :            :   GEN z, u, v, a, b, c;
     426                 :            :   pari_sp av;
     427 [ +  - ][ +  - ]:      13594 :   if (typ(x) != t_POL || varn(x) != varn(y) || degpol(x) <= 0)
                 [ -  + ]
     428                 :          0 :     return gsqr(x);
     429                 :      13594 :   a = gel(y,4); u = gel(x,3); /*Mod(ux + v, ax^2 + bx + c)*/
     430                 :      13594 :   b = gel(y,3); v = gel(x,2);
     431                 :      13594 :   c = gel(y,2); av = avma;
     432                 :      13594 :   z = gmul(u, gsub(gmul(c,u), gmul(b,v)));
     433         [ +  + ]:      13594 :   if (!gequal1(a)) z = gdiv(z, a);
     434                 :      13594 :   return gerepileupto(av, gadd(z, gsqr(v)));
     435                 :            : }
     436                 :            : 
     437                 :            : GEN
     438                 :    1731078 : gconj(GEN x)
     439                 :            : {
     440                 :            :   long lx, i;
     441                 :            :   GEN y;
     442                 :            : 
     443   [ +  +  +  +  :    1731078 :   switch(typ(x))
             +  +  -  - ]
     444                 :            :   {
     445                 :            :     case t_INT: case t_REAL:
     446                 :      90588 :       return mpcopy(x);
     447                 :            : 
     448                 :            :     case t_INTMOD: case t_FRAC: case t_PADIC:
     449                 :       1414 :       return gcopy(x);
     450                 :            : 
     451                 :            :     case t_COMPLEX:
     452                 :    1629796 :       y = cgetg(3,t_COMPLEX);
     453                 :    1629796 :       gel(y,1) = gcopy(gel(x,1));
     454                 :    1629796 :       gel(y,2) = gneg(gel(x,2));
     455                 :    1629796 :       break;
     456                 :            : 
     457                 :            :     case t_QUAD:
     458                 :        595 :       y = cgetg(4,t_QUAD);
     459                 :        595 :       gel(y,1) = ZX_copy(gel(x,1));
     460                 :        595 :       gel(y,2) = gequal0(gmael(x,1,3))? gcopy(gel(x,2))
     461         [ +  + ]:        595 :                                     : gadd(gel(x,2), gel(x,3));
     462                 :        595 :       gel(y,3) = gneg(gel(x,3));
     463                 :        595 :       break;
     464                 :            : 
     465                 :            :     case t_POL: case t_SER:
     466                 :       4683 :       y = cgetg_copy(x, &lx); y[1] = x[1];
     467         [ +  + ]:      16086 :       for (i=2; i<lx; i++) gel(y,i) = gconj(gel(x,i));
     468                 :       4683 :       break;
     469                 :            : 
     470                 :            :     case t_RFRAC: case t_VEC: case t_COL: case t_MAT:
     471                 :       4002 :       y = cgetg_copy(x, &lx);
     472         [ +  + ]:      20420 :       for (i=1; i<lx; i++) gel(y,i) = gconj(gel(x,i));
     473                 :       4002 :       break;
     474                 :            : 
     475                 :            :     case t_POLMOD:
     476                 :            :     {
     477                 :          0 :       GEN y, X = gel(x,1);
     478                 :          0 :       long d = degpol(X);
     479         [ #  # ]:          0 :       if (d < 2) return RgX_copy(x);
     480         [ #  # ]:          0 :       if (d == 2) {
     481                 :          0 :         y = cgetg(3, t_POLMOD);
     482                 :          0 :         gel(y,1) = RgX_copy(X);
     483                 :          0 :         gel(y,2) = quad_polmod_conj(gel(x,2), X); return y;
     484                 :            :       }
     485                 :            :     }
     486                 :            :     default:
     487                 :          0 :       pari_err_TYPE("gconj",x);
     488                 :          0 :       return NULL; /* not reached */
     489                 :            :   }
     490                 :    1731078 :   return y;
     491                 :            : }
     492                 :            : 
     493                 :            : GEN
     494                 :         42 : conjvec(GEN x,long prec)
     495                 :            : {
     496                 :            :   long lx, s, i;
     497                 :            :   GEN z;
     498                 :            : 
     499   [ -  -  +  -  :         42 :   switch(typ(x))
                   +  - ]
     500                 :            :   {
     501                 :            :     case t_INT: case t_INTMOD: case t_FRAC:
     502                 :          0 :       return mkcolcopy(x);
     503                 :            : 
     504                 :            :     case t_COMPLEX: case t_QUAD:
     505                 :          0 :       z=cgetg(3,t_COL); gel(z,1) = gcopy(x); gel(z,2) = gconj(x); break;
     506                 :            : 
     507                 :            :     case t_FFELT:
     508                 :         28 :       return FF_conjvec(x);
     509                 :            : 
     510                 :            :     case t_VEC: case t_COL:
     511                 :          0 :       lx = lg(x); z = cgetg(lx,t_MAT);
     512         [ #  # ]:          0 :       if (lx == 1) return z;
     513                 :          0 :       gel(z,1) = conjvec(gel(x,1),prec);
     514                 :          0 :       s = lgcols(z);
     515         [ #  # ]:          0 :       for (i=2; i<lx; i++)
     516                 :            :       {
     517                 :          0 :         gel(z,i) = conjvec(gel(x,i),prec);
     518         [ #  # ]:          0 :         if (lg(gel(z,i)) != s) pari_err_OP("conjvec", gel(z,1), gel(z,i));
     519                 :            :       }
     520                 :          0 :       break;
     521                 :            : 
     522                 :            :     case t_POLMOD: {
     523                 :         14 :       GEN T = gel(x,1), r;
     524                 :            :       pari_sp av;
     525                 :            : 
     526                 :         14 :       lx = lg(T);
     527         [ -  + ]:         14 :       if (lx <= 3) return cgetg(1,t_COL);
     528                 :         14 :       x = gel(x,2);
     529         [ +  + ]:         42 :       for (i=2; i<lx; i++)
     530                 :            :       {
     531                 :         35 :         GEN c = gel(T,i);
     532      [ +  +  - ]:         35 :         switch(typ(c)) {
     533                 :            :           case t_INTMOD: {
     534                 :          7 :             GEN p = gel(c,1);
     535                 :            :             pari_sp av;
     536 [ -  + ][ #  # ]:          7 :             if (typ(x) != t_POL) retconst_col(lx-3, Rg_to_Fp(x, p));
     537                 :          7 :             av = avma;
     538                 :          7 :             T = RgX_to_FpX(T,p);
     539                 :          7 :             x = RgX_to_FpX(x, p);
     540         [ -  + ]:          7 :             if (varn(x) != varn(T)) pari_err_VAR("conjvec",x,T);
     541                 :          7 :             z = FpXQC_to_mod(FpXQ_conjvec(x, T , p), T, p);
     542                 :          7 :             return gerepileupto(av, z);
     543                 :            :           }
     544                 :            :           case t_INT:
     545                 :         28 :           case t_FRAC: break;
     546                 :          0 :           default: pari_err_TYPE("conjvec [not a rational t_POL]",T);
     547                 :            :         }
     548                 :            :       }
     549         [ -  + ]:          7 :       if (typ(x) != t_POL)
     550                 :            :       {
     551         [ #  # ]:          0 :         if (!is_rational_t(typ(x)))
     552                 :          0 :           pari_err_TYPE("conjvec [not a rational t_POL]",x);
     553         [ #  # ]:          0 :         retconst_col(lx-3, gcopy(x));
     554                 :            :       }
     555         [ -  + ]:          7 :       if (!RgX_is_QX(x)) pari_err_TYPE("conjvec", x);
     556                 :          7 :       av = avma;
     557         [ -  + ]:          7 :       if (varn(x) != varn(T)) pari_err_VAR("conjvec",x,T);
     558                 :          7 :       r = cleanroots(T,prec);
     559                 :          7 :       z = cgetg(lx-2,t_COL);
     560         [ +  + ]:         28 :       for (i=1; i<=lx-3; i++) gel(z,i) = poleval(x, gel(r,i));
     561                 :          7 :       return gerepileupto(av, z);
     562                 :            :     }
     563                 :            : 
     564                 :            :     default:
     565                 :          0 :       pari_err_TYPE("conjvec",x);
     566                 :          0 :       return NULL; /* not reached */
     567                 :            :   }
     568                 :         42 :   return z;
     569                 :            : }
     570                 :            : 
     571                 :            : 
     572                 :            : /********************************************************************/
     573                 :            : /**                                                                **/
     574                 :            : /**                           ADDITION                             **/
     575                 :            : /**                                                                **/
     576                 :            : /********************************************************************/
     577                 :            : /* x, y compatible PADIC, op = add or sub */
     578                 :            : static GEN
     579                 :     941815 : addsub_pp(GEN x, GEN y, GEN (*op)(GEN,GEN))
     580                 :            : {
     581                 :     941815 :   pari_sp av = avma;
     582                 :            :   long d,e,r,rx,ry;
     583                 :     941815 :   GEN u, z, mod, p = gel(x,2);
     584                 :            :   int swap;
     585                 :            : 
     586                 :     941815 :   (void)new_chunk(5 + lgefint(gel(x,3)) + lgefint(gel(y,3)));
     587                 :     941815 :   e = valp(x);
     588                 :     941815 :   r = valp(y); d = r-e;
     589         [ +  + ]:     941815 :   if (d < 0) { swap = 1; swap(x,y); e = r; d = -d; } else swap = 0;
     590                 :     941815 :   rx = precp(x);
     591                 :     941815 :   ry = precp(y);
     592         [ +  + ]:     941815 :   if (d) /* v(x) < v(y) */
     593                 :            :   {
     594                 :     401289 :     r = d+ry; z = powiu(p,d);
     595         [ +  + ]:     401289 :     if (r < rx) mod = mulii(z,gel(y,3)); else { r = rx; mod = gel(x,3); }
     596                 :     401289 :     z = mulii(z,gel(y,4));
     597         [ +  + ]:     401289 :     u = swap? op(z, gel(x,4)): op(gel(x,4), z);
     598                 :            :   }
     599                 :            :   else
     600                 :            :   {
     601                 :            :     long c;
     602         [ +  + ]:     540526 :     if (ry < rx) { r=ry; mod = gel(y,3); } else { r=rx; mod = gel(x,3); }
     603         [ -  + ]:     540526 :     u = swap? op(gel(y,4), gel(x,4)): op(gel(x,4), gel(y,4));
     604 [ +  + ][ +  + ]:     540526 :     if (!signe(u) || (c = Z_pvalrem(u,p,&u)) >= r)
     605                 :            :     {
     606                 :      51065 :       avma = av; return zeropadic(p, e+r);
     607                 :            :     }
     608         [ +  + ]:     489461 :     if (c)
     609                 :            :     {
     610                 :      46760 :       mod = diviiexact(mod, powiu(p,c));
     611                 :      46760 :       r -= c;
     612                 :      46760 :       e += c;
     613                 :            :     }
     614                 :            :   }
     615                 :     890750 :   u = modii(u, mod);
     616                 :     890750 :   avma = av; z = cgetg(5,t_PADIC);
     617                 :     890750 :   z[1] = evalprecp(r) | evalvalp(e);
     618                 :     890750 :   gel(z,2) = icopy(p);
     619                 :     890750 :   gel(z,3) = icopy(mod);
     620                 :     941815 :   gel(z,4) = icopy(u); return z;
     621                 :            : }
     622                 :            : /* Rg_to_Fp(t_FRAC) without GC */
     623                 :            : static GEN
     624                 :       1302 : Q_to_Fp(GEN x, GEN p)
     625                 :       1302 : { return mulii(gel(x,1), Fp_inv(gel(x,2),p)); }
     626                 :            : /* return x + y, where y t_PADIC and x is a non-zero t_INT or t_FRAC */
     627                 :            : static GEN
     628                 :     151178 : addQp(GEN x, GEN y)
     629                 :            : {
     630                 :     151178 :   pari_sp av = avma;
     631                 :     151178 :   long d, r, e, vy = valp(y), py = precp(y);
     632                 :     151178 :   GEN z, q, mod, u, p = gel(y,2);
     633                 :            : 
     634                 :     151178 :   e = Q_pvalrem(x, p, &x);
     635                 :     151172 :   d = vy - e; r = d + py;
     636         [ +  + ]:     151172 :   if (r <= 0) { avma = av; return gcopy(y); }
     637                 :     150682 :   mod = gel(y,3);
     638                 :     150682 :   u   = gel(y,4);
     639                 :     150682 :   (void)new_chunk(5 + ((lgefint(mod) + lgefint(p)*labs(d)) << 1));
     640                 :            : 
     641         [ +  + ]:     150687 :   if (d > 0)
     642                 :            :   {
     643                 :     123705 :     q = powiu(p,d);
     644                 :     123706 :     mod = mulii(mod, q);
     645         [ +  + ]:     123704 :     if (typ(x) != t_INT) x = Q_to_Fp(x, mod);
     646                 :     123704 :     u = addii(x,  mulii(u, q));
     647                 :            :   }
     648         [ +  + ]:      26982 :   else if (d < 0)
     649                 :            :   {
     650                 :       1951 :     q = powiu(p,-d);
     651         [ +  + ]:       1951 :     if (typ(x) != t_INT) x = Q_to_Fp(x, mod);
     652                 :       1951 :     u = addii(u, mulii(x, q));
     653                 :       1951 :     r = py; e = vy;
     654                 :            :   }
     655                 :            :   else
     656                 :            :   {
     657                 :            :     long c;
     658         [ +  + ]:      25031 :     if (typ(x) != t_INT) x = Q_to_Fp(x, mod);
     659                 :      25031 :     u = addii(u, x);
     660 [ +  + ][ +  + ]:      25031 :     if (!signe(u) || (c = Z_pvalrem(u,p,&u)) >= r)
     661                 :            :     {
     662                 :        742 :       avma = av; return zeropadic(p,e+r);
     663                 :            :     }
     664         [ +  + ]:      24289 :     if (c)
     665                 :            :     {
     666                 :      13754 :       mod = diviiexact(mod, powiu(p,c));
     667                 :      13754 :       r -= c;
     668                 :      13754 :       e += c;
     669                 :            :     }
     670                 :            :   }
     671                 :     149942 :   u = modii(u, mod); avma = av;
     672                 :     149945 :   z = cgetg(5,t_PADIC);
     673                 :     149945 :   z[1] = evalprecp(r) | evalvalp(e);
     674                 :     149946 :   gel(z,2) = icopy(p);
     675                 :     149946 :   gel(z,3) = icopy(mod);
     676                 :     151178 :   gel(z,4) = icopy(u); return z;
     677                 :            : }
     678                 :            : 
     679                 :            : /* Mod(x,X) + Mod(y,X) */
     680                 :            : #define addsub_polmod_same addsub_polmod_scal
     681                 :            : /* Mod(x,X) +/- Mod(y,Y) */
     682                 :            : static GEN
     683                 :        980 : addsub_polmod(GEN X, GEN Y, GEN x, GEN y, GEN(*op)(GEN,GEN))
     684                 :            : {
     685                 :        980 :   long T[3] = { evaltyp(t_POLMOD) | _evallg(3),0,0 };
     686                 :        980 :   GEN z = cgetg(3,t_POLMOD);
     687                 :        980 :   long vx = varn(X), vy = varn(Y);
     688         [ +  + ]:        980 :   if (vx==vy) {
     689                 :            :     pari_sp av;
     690                 :         14 :     gel(z,1) = RgX_gcd(X,Y); av = avma;
     691                 :         14 :     warn_coercion(X,Y,gel(z,1));
     692                 :         14 :     gel(z,2) = gerepileupto(av, gmod(op(x, y), gel(z,1))); return z;
     693                 :            :   }
     694         [ +  - ]:        966 :   if (varncmp(vx, vy) < 0)
     695                 :        966 :   { gel(z,1) = RgX_copy(X); gel(T,1) = Y; gel(T,2) = y; y = T; }
     696                 :            :   else
     697                 :          0 :   { gel(z,1) = RgX_copy(Y); gel(T,1) = X; gel(T,2) = x; x = T; }
     698                 :        980 :   gel(z,2) = op(x, y); return z;
     699                 :            : }
     700                 :            : /* Mod(y, Y) +/- x,  x scalar or polynomial in same var and reduced degree */
     701                 :            : static GEN
     702                 :    2722706 : addsub_polmod_scal(GEN Y, GEN y, GEN x, GEN(*op)(GEN,GEN))
     703                 :            : {
     704                 :    2722706 :   GEN z = cgetg(3,t_POLMOD);
     705                 :    2722706 :   gel(z,1) = RgX_copy(Y);
     706                 :    2722706 :   gel(z,2) = op(y, x); return z;
     707                 :            : }
     708                 :            : 
     709                 :            : /* typ(y) == t_SER, x "scalar" [e.g object in lower variable] */
     710                 :            : static GEN
     711                 :     192826 : add_ser_scal(GEN y, GEN x)
     712                 :            : {
     713                 :            :   long i, l, ly, vy;
     714                 :            :   GEN z;
     715                 :            : 
     716         [ +  + ]:     192826 :   if (isrationalzero(x)) return gcopy(y);
     717                 :     188395 :   ly = lg(y);
     718                 :     188395 :   l = valp(y);
     719         [ +  + ]:     188395 :   if (l < 3-ly) return gcopy(y);
     720                 :            :   /* l + ly >= 3 */
     721         [ +  + ]:     188276 :   if (l < 0)
     722                 :            :   {
     723                 :        609 :     z = cgetg(ly,t_SER); z[1] = y[1];
     724         [ +  + ]:       1932 :     for (i = 2; i <= 1-l; i++) gel(z,i) = gcopy(gel(y,i));
     725                 :        609 :     gel(z,i) = gadd(x,gel(y,i)); i++;
     726         [ +  + ]:       2121 :     for (     ; i < ly; i++)   gel(z,i) = gcopy(gel(y,i));
     727                 :        609 :     return z;
     728                 :            :   }
     729                 :     187667 :   vy = varn(y);
     730         [ +  + ]:     187667 :   if (l > 0)
     731                 :            :   {
     732         [ +  + ]:       7840 :     if (ser_isexactzero(y))
     733         [ +  + ]:       5404 :       return scalarser(ly == 2? x: gadd(x,gel(y,2)), vy, l);
     734                 :       2436 :     y -= l; ly += l;
     735                 :       2436 :     z = cgetg(ly,t_SER);
     736                 :       2436 :     x = gcopy(x);
     737         [ +  + ]:       4200 :     for (i=3; i<=l+1; i++) gel(z,i) = gen_0;
     738                 :            :   }
     739                 :            :   else
     740                 :            :   { /* l = 0, ly >= 3. Also OK if ser_isexactzero(y) */
     741                 :     179827 :     z = cgetg(ly,t_SER);
     742                 :     179827 :     x = gadd(x, gel(y,2));
     743                 :     179827 :     i = 3;
     744                 :            :   }
     745         [ +  + ]:     584327 :   for (; i<ly; i++) gel(z,i) = gcopy(gel(y,i));
     746                 :     182263 :   gel(z,2) = x;
     747                 :     182263 :   z[1] = evalsigne(1) | _evalvalp(0) | evalvarn(vy);
     748         [ +  + ]:     192826 :   return gequal0(x)? normalize(z): z;
     749                 :            : }
     750                 :            : static long
     751         [ +  + ]:    2325858 : serprec(GEN x) { return ser_isexactzero(x)? 2: lg(x); }
     752                 :            : /* x,y t_SER in the same variable: x+y */
     753                 :            : static GEN
     754                 :    1163300 : ser_add(GEN x, GEN y)
     755                 :            : {
     756                 :    1163300 :   long i, lx,ly, n = valp(y) - valp(x);
     757                 :            :   GEN z;
     758         [ +  + ]:    1163300 :   if (n < 0) { n = -n; swap(x,y); }
     759                 :            :   /* valp(x) <= valp(y) */
     760                 :    1163300 :   lx = serprec(x);
     761         [ +  + ]:    1163300 :   if (lx == 2) /* don't lose type information */
     762                 :        742 :     return scalarser(gadd(RgX_get_0(x), RgX_get_0(y)), varn(x), valp(x));
     763         [ +  + ]:    1162558 :   ly = serprec(y) + n; if (lx < ly) ly = lx;
     764         [ +  + ]:    1162558 :   if (n)
     765                 :            :   {
     766         [ +  + ]:       8855 :     if (n+2 > lx) return gcopy(x);
     767                 :       8155 :     z = cgetg(ly,t_SER);
     768         [ +  + ]:      60977 :     for (i=2; i<=n+1; i++) gel(z,i) = gcopy(gel(x,i));
     769         [ +  + ]:      38983 :     for (   ; i < ly; i++) gel(z,i) = gadd(gel(x,i),gel(y,i-n));
     770                 :            :   } else {
     771                 :    1153703 :     z = cgetg(ly,t_SER);
     772         [ +  + ]:    5216529 :     for (i=2; i < ly; i++) gel(z,i) = gadd(gel(x,i),gel(y,i));
     773                 :            :   }
     774                 :    1163300 :   z[1] = x[1]; return normalize(z);
     775                 :            : }
     776                 :            : /* typ(y) == RFRAC, x polynomial in same variable or "scalar" */
     777                 :            : static GEN
     778                 :    8350089 : add_rfrac_scal(GEN y, GEN x)
     779                 :            : {
     780                 :            :   pari_sp av;
     781                 :            :   GEN n;
     782                 :            : 
     783         [ +  + ]:    8350089 :   if (isintzero(x)) return gcopy(y); /* frequent special case */
     784                 :    4625077 :   av = avma; n = gadd(gmul(x, gel(y,2)), gel(y,1));
     785                 :    8350089 :   return gerepileupto(av, gred_rfrac_simple(n, gel(y,2)));
     786                 :            : }
     787                 :            : 
     788                 :            : /* x "scalar", ty != t_MAT and non-scalar */
     789                 :            : static GEN
     790                 :   14474654 : add_scal(GEN y, GEN x, long ty)
     791                 :            : {
     792   [ +  +  +  -  :   14474654 :   switch(ty)
                   +  - ]
     793                 :            :   {
     794                 :    9830615 :     case t_POL: return RgX_Rg_add(y, x);
     795                 :     192826 :     case t_SER: return add_ser_scal(y, x);
     796                 :    4241003 :     case t_RFRAC: return add_rfrac_scal(y, x);
     797                 :          0 :     case t_COL: return RgC_Rg_add(y, x);
     798                 :            :     case t_VEC:
     799         [ +  + ]:     210210 :       if (isintzero(x)) return gcopy(y);
     800                 :        168 :       break;
     801                 :            :   }
     802                 :        168 :   pari_err_TYPE2("+",x,y);
     803                 :   14474486 :   return NULL; /* not reached */
     804                 :            : }
     805                 :            : 
     806                 :            : static GEN
     807                 :   23584708 : addsub_frac(GEN x, GEN y, GEN (*op)(GEN,GEN))
     808                 :            : {
     809                 :   23584708 :   pari_sp av = avma;
     810                 :   23584708 :   GEN x1 = gel(x,1), x2 = gel(x,2), z = cgetg(3,t_FRAC);
     811                 :   23584708 :   GEN y1 = gel(y,1), y2 = gel(y,2), q, r, n, d, delta;
     812                 :   23584708 :   int s = cmpii(x2, y2);
     813                 :            : 
     814         [ +  + ]:   23584708 :   if (!s)
     815                 :            :   { /* common denominator: (x1 op y1) / x2 */
     816                 :   11407209 :     n = op(x1, y1);
     817         [ +  + ]:   11407209 :     if (!signe(n)) { avma = av; return gen_0; }
     818                 :   10901391 :     d = x2;
     819                 :   10901391 :     q = dvmdii(n, d, &r);
     820         [ +  + ]:   10901391 :     if (r == gen_0) { avma = av; return icopy(q); }
     821                 :   10121043 :     r = gcdii(d, r);
     822         [ +  + ]:   10121043 :     if (!is_pm1(r)) { n = diviiexact(n, r); d = diviiexact(d, r); }
     823                 :   10121043 :     gel(z,1) = icopy_avma(n, (pari_sp)z);
     824                 :   10121043 :     gel(z,2) = icopy_avma(d, (pari_sp)gel(z,1));
     825                 :   10121043 :     avma = (pari_sp)gel(z,2); return z;
     826                 :            :   }
     827         [ +  + ]:   12177499 :   if (s < 0)
     828                 :            :   {
     829                 :    5268584 :     GEN Q = dvmdii(y2, x2, &r);
     830         [ +  + ]:    5268584 :     if (r == gen_0)
     831                 :            :     { /* y2 = Q x2: 1/x2 . (Q x1 op y1)/Q, where latter is in coprime form */
     832                 :    4257961 :       pari_sp av = avma;
     833                 :    4257961 :       n = op(mulii(Q,x1), y1);
     834                 :    4257961 :       q = dvmdii(n, x2, &r);
     835         [ +  + ]:    4257961 :       if (r == gen_0)
     836                 :            :       {
     837                 :     729673 :         gel(z,1) = gerepileuptoint(av, q);
     838                 :     729673 :         gel(z,2) = Q; return z;
     839                 :            :       }
     840                 :    3528288 :       r = gcdii(x2, r);
     841         [ +  + ]:    3528288 :       if (!is_pm1(r)) { n = diviiexact(n, r); x2 = diviiexact(x2, r); }
     842                 :    3528288 :       d = mulii(x2,Q);
     843                 :    3528288 :       gel(z,1) = icopy_avma(n, (pari_sp)z);
     844                 :    3528288 :       gel(z,2) = icopy_avma(d, (pari_sp)gel(z,1));
     845                 :    3528288 :       avma = (pari_sp)gel(z,2); return z;
     846                 :            :     }
     847                 :    1010623 :     delta = gcdii(x2,r);
     848                 :            :   }
     849                 :            :   else
     850                 :            :   {
     851                 :    6908915 :     GEN Q = dvmdii(x2, y2, &r);
     852         [ +  + ]:    6908915 :     if (r == gen_0)
     853                 :            :     { /* x2 = Q y2: 1/y2 . (x1 op Q y1)/Q, where latter is in coprime form */
     854                 :    5554459 :       pari_sp av = avma;
     855                 :    5554459 :       n = op(x1, mulii(Q,y1));
     856                 :    5554459 :       q = dvmdii(n, y2, &r);
     857         [ +  + ]:    5554459 :       if (r == gen_0)
     858                 :            :       {
     859                 :     104214 :         gel(z,1) = gerepileuptoint(av, q);
     860                 :     104214 :         gel(z,2) = Q; return z;
     861                 :            :       }
     862                 :    5450245 :       r = gcdii(y2, r);
     863         [ +  + ]:    5450245 :       if (!is_pm1(r)) { n = diviiexact(n, r); y2 = diviiexact(y2, r); }
     864                 :    5450245 :       d = mulii(y2,Q);
     865                 :    5450245 :       gel(z,1) = icopy_avma(n, (pari_sp)z);
     866                 :    5450245 :       gel(z,2) = icopy_avma(d, (pari_sp)gel(z,1));
     867                 :    5450245 :       avma = (pari_sp)gel(z,2); return z;
     868                 :            :     }
     869                 :    1354456 :     delta = gcdii(y2,r);
     870                 :            :   }
     871                 :            :   /* delta = gcd(x2,y2) */
     872         [ +  + ]:    2365079 :   if (is_pm1(delta))
     873                 :            :   { /* numerator is non-zero */
     874                 :     174815 :     gel(z,1) = gerepileuptoint((pari_sp)z, op(mulii(x1,y2), mulii(y1,x2)));
     875                 :     174815 :     gel(z,2) = mulii(x2,y2); return z;
     876                 :            :   }
     877                 :    2190264 :   x2 = diviiexact(x2,delta);
     878                 :    2190264 :   y2 = diviiexact(y2,delta);
     879                 :    2190264 :   n = op(mulii(x1,y2), mulii(y1,x2));
     880         [ -  + ]:    2190264 :   if (!signe(n)) { avma = av; return gen_0; }
     881                 :    2190264 :   d = mulii(x2, y2);
     882                 :    2190264 :   q = dvmdii(n, delta, &r);
     883         [ +  + ]:    2190264 :   if (r == gen_0)
     884                 :            :   {
     885         [ -  + ]:      99125 :     if (is_pm1(d)) { avma = av; return icopy(q); }
     886                 :      99125 :     avma = (pari_sp)z;
     887                 :      99125 :     gel(z,2) = icopy(d);
     888                 :      99125 :     gel(z,1) = icopy(q); return z;
     889                 :            :   }
     890                 :    2091139 :   r = gcdii(delta, r);
     891         [ +  + ]:    2091139 :   if (!is_pm1(r))
     892                 :            :   {
     893                 :     739711 :     n     = diviiexact(n, r);
     894                 :     739711 :     delta = diviiexact(delta, r);
     895                 :            :   }
     896                 :    2091139 :   d = mulii(d,delta); avma = (pari_sp)z;
     897                 :    2091139 :   gel(z,1) = icopy(n);
     898                 :   23584708 :   gel(z,2) = icopy(d); return z;
     899                 :            : }
     900                 :            : 
     901                 :            : /* assume x2, y2 are t_POLs in the same variable */
     902                 :            : static GEN
     903                 :    2781571 : add_rfrac(GEN x, GEN y)
     904                 :            : {
     905                 :    2781571 :   pari_sp av = avma;
     906                 :    2781571 :   GEN x1 = gel(x,1), x2 = gel(x,2);
     907                 :    2781571 :   GEN y1 = gel(y,1), y2 = gel(y,2), q, r, n, d, delta;
     908                 :            : 
     909                 :    2781571 :   delta = RgX_gcd(x2,y2);
     910         [ +  + ]:    2781571 :   if (!degpol(delta))
     911                 :            :   {
     912                 :        616 :     n = simplify_shallow( gadd(gmul(x1,y2), gmul(y1,x2)) );
     913                 :        616 :     d = RgX_mul(x2, y2);
     914                 :        616 :     return gerepileupto(av, gred_rfrac_simple(n, d));
     915                 :            :   }
     916                 :    2780955 :   x2 = RgX_div(x2,delta);
     917                 :    2780955 :   y2 = RgX_div(y2,delta);
     918                 :    2780955 :   n = gadd(gmul(x1,y2), gmul(y1,x2));
     919         [ +  + ]:    2780955 :   if (!signe(n))
     920                 :            :   {
     921                 :     680797 :     n = simplify_shallow(n);
     922         [ +  + ]:     680797 :     if (isrationalzero(n)) return gerepileupto(av, n);
     923                 :          7 :     return gerepilecopy(av, mkrfrac(n, RgX_mul(gel(x,2),y2)));
     924                 :            :   }
     925         [ +  + ]:    2100158 :   if (degpol(n) == 0)
     926                 :    1138189 :     return gerepileupto(av, gred_rfrac_simple(gel(n,2), RgX_mul(gel(x,2),y2)));
     927                 :     961969 :   q = RgX_divrem(n, delta, &r); /* we want gcd(n,delta) */
     928         [ +  + ]:     961969 :   if (isexactzero(r))
     929                 :            :   {
     930                 :            :     GEN z;
     931                 :     208991 :     d = RgX_mul(x2, y2);
     932                 :            :     /* "constant" denominator ? */
     933         [ +  + ]:     208991 :     z = lg(d) == 3? RgX_Rg_div(q, gel(d,2)): gred_rfrac_simple(q, d);
     934                 :     208991 :     return gerepileupto(av, z);
     935                 :            :   }
     936                 :     752978 :   r = RgX_gcd(delta, r);
     937         [ +  + ]:     752978 :   if (degpol(r))
     938                 :            :   {
     939                 :     148378 :     n = RgX_div(n, r);
     940                 :     148378 :     d = RgX_mul(RgX_mul(x2,y2), RgX_div(delta, r));
     941                 :            :   }
     942                 :            :   else
     943                 :     604600 :     d = RgX_mul(gel(x,2), y2);
     944                 :    2781571 :   return gerepileupto(av, gred_rfrac_simple(n, d));
     945                 :            : }
     946                 :            : 
     947                 :            : GEN
     948                 : 1304419513 : gadd(GEN x, GEN y)
     949                 :            : {
     950                 : 1304419513 :   long tx = typ(x), ty = typ(y), vx, vy, lx, i, l;
     951                 :            :   pari_sp av, tetpil;
     952                 :            :   GEN z, p1;
     953                 :            : 
     954 [ +  + ][ +  +  : 1304419513 :   if (tx == ty) switch(tx) /* shortcut to generic case */
          +  +  +  +  +  
          +  +  +  +  +  
             +  +  +  - ]
     955                 :            :   {
     956                 :  731918646 :     case t_INT: return addii(x,y);
     957                 :  321821398 :     case t_REAL: return addrr(x,y);
     958                 :    1346595 :     case t_INTMOD:  { GEN X = gel(x,1), Y = gel(y,1);
     959                 :    1346595 :       z = cgetg(3,t_INTMOD);
     960 [ +  + ][ +  + ]:    1346584 :       if (X==Y || equalii(X,Y))
     961                 :    1346580 :         return add_intmod_same(z, X, gel(x,2), gel(y,2));
     962                 :         14 :       gel(z,1) = gcdii(X,Y);
     963                 :         14 :       warn_coercion(X,Y,gel(z,1));
     964                 :         14 :       av = avma; p1 = addii(gel(x,2),gel(y,2));
     965                 :         14 :       gel(z,2) = gerepileuptoint(av, remii(p1, gel(z,1))); return z;
     966                 :            :     }
     967                 :   16915792 :     case t_FRAC: return addsub_frac(x,y,addii);
     968                 :   32288958 :     case t_COMPLEX: z = cgetg(3,t_COMPLEX);
     969                 :   32288958 :       gel(z,2) = gadd(gel(x,2),gel(y,2));
     970         [ +  + ]:   32288958 :       if (isintzero(gel(z,2)))
     971                 :            :       {
     972                 :        315 :         avma = (pari_sp)(z+3);
     973                 :        315 :         return gadd(gel(x,1),gel(y,1));
     974                 :            :       }
     975                 :   32288643 :       gel(z,1) = gadd(gel(x,1),gel(y,1));
     976                 :   32288643 :       return z;
     977                 :            :     case t_PADIC:
     978         [ -  + ]:     929922 :       if (!equalii(gel(x,2),gel(y,2))) pari_err_OP("+",x,y);
     979                 :     929922 :       return addsub_pp(x,y, addii);
     980                 :        301 :     case t_QUAD: z = cgetg(4,t_QUAD);
     981         [ -  + ]:        301 :       if (!ZX_equal(gel(x,1),gel(y,1))) pari_err_OP("+",x,y);
     982                 :        301 :       gel(z,1) = ZX_copy(gel(x,1));
     983                 :        301 :       gel(z,2) = gadd(gel(x,2),gel(y,2));
     984                 :        301 :       gel(z,3) = gadd(gel(x,3),gel(y,3)); return z;
     985                 :            :     case t_POLMOD:
     986         [ +  + ]:    1226546 :       if (RgX_equal_var(gel(x,1), gel(y,1)))
     987                 :    1225601 :         return addsub_polmod_same(gel(x,1), gel(x,2), gel(y,2), &gadd);
     988                 :        945 :       return addsub_polmod(gel(x,1), gel(y,1), gel(x,2), gel(y,2), &gadd);
     989                 :   10099045 :     case t_FFELT: return FF_add(x,y);
     990                 :            :     case t_POL:
     991                 :   16782198 :       vx = varn(x);
     992                 :   16782198 :       vy = varn(y);
     993         [ +  + ]:   16782198 :       if (vx != vy) {
     994         [ +  + ]:     806195 :         if (varncmp(vx, vy) < 0) return RgX_Rg_add(x, y);
     995                 :      19807 :         else                     return RgX_Rg_add(y, x);
     996                 :            :       }
     997                 :   15976003 :       return RgX_add(x, y);
     998                 :            :     case t_SER:
     999                 :    1160388 :       vx = varn(x);
    1000                 :    1160388 :       vy = varn(y);
    1001         [ -  + ]:    1160388 :       if (vx != vy) {
    1002         [ #  # ]:          0 :         if (varncmp(vx, vy) < 0) return add_ser_scal(x, y);
    1003                 :          0 :         else                     return add_ser_scal(y, x);
    1004                 :            :       }
    1005                 :    1160388 :       return ser_add(x, y);
    1006                 :            :     case t_RFRAC:
    1007                 :    4073474 :       vx = varn(gel(x,2));
    1008                 :    4073474 :       vy = varn(gel(y,2));
    1009         [ +  + ]:    4073474 :       if (vx != vy) {
    1010         [ +  + ]:    1291903 :         if (varncmp(vx, vy) < 0) return add_rfrac_scal(x, y);
    1011                 :     536802 :         else                     return add_rfrac_scal(y, x);
    1012                 :            :       }
    1013                 :    2781571 :       return add_rfrac(x,y);
    1014                 :            :     case t_VEC:
    1015         [ -  + ]:     472055 :       if (lg(y) != lg(x)) pari_err_OP("+",x,y);
    1016                 :     472055 :       return RgV_add(x,y);
    1017                 :            :     case t_COL:
    1018         [ -  + ]:    4671946 :       if (lg(y) != lg(x)) pari_err_OP("+",x,y);
    1019                 :    4671946 :       return RgC_add(x,y);
    1020                 :            :     case t_MAT:
    1021                 :     410312 :       lx = lg(x);
    1022         [ -  + ]:     410312 :       if (lg(y) != lx) pari_err_OP("+",x,y);
    1023         [ -  + ]:     410312 :       if (lx == 1) return cgetg(1, t_MAT);
    1024         [ +  + ]:     410312 :       if (lgcols(y) != lgcols(x)) pari_err_OP("+",x,y);
    1025                 :     410305 :       return RgM_add(x,y);
    1026                 :            : 
    1027                 :          0 :     default: pari_err_TYPE2("+",x,y);
    1028                 :            :   }
    1029                 :            :   /* tx != ty */
    1030         [ +  + ]:  160303092 :   if (tx > ty) { swap(x,y); lswap(tx,ty); }
    1031                 :            : 
    1032 [ +  + ][ +  +  :  160303092 :   if (is_const_t(ty)) switch(tx) /* tx < ty, is_const_t(tx) && is_const_t(ty) */
          +  +  -  +  -  
                      - ]
    1033                 :            :   {
    1034                 :            :     case t_INT:
    1035   [ +  +  +  +  :  125130888 :       switch(ty)
             +  +  +  - ]
    1036                 :            :       {
    1037                 :   75428666 :         case t_REAL: return addir(x,y);
    1038                 :            :         case t_INTMOD:
    1039                 :     462669 :           z = cgetg(3, t_INTMOD);
    1040                 :     462669 :           return add_intmod_same(z, gel(y,1), gel(y,2), modii(x, gel(y,1)));
    1041                 :   20323283 :         case t_FRAC: z = cgetg(3,t_FRAC);
    1042                 :   20323283 :           gel(z,1) = gerepileuptoint((pari_sp)z, addii(gel(y,1), mulii(gel(y,2),x)));
    1043                 :   20323283 :           gel(z,2) = icopy(gel(y,2)); return z;
    1044                 :   27265199 :         case t_COMPLEX: return addRc(x, y);
    1045                 :            :         case t_PADIC:
    1046         [ +  + ]:     159789 :           if (!signe(x)) return gcopy(y);
    1047                 :     149268 :           return addQp(x,y);
    1048                 :        658 :         case t_QUAD: return addRq(x, y);
    1049                 :    1490624 :         case t_FFELT: return FF_Z_add(y,x);
    1050                 :            :       }
    1051                 :            : 
    1052                 :            :     case t_REAL:
    1053   [ +  +  +  - ]:   16981707 :       switch(ty)
    1054                 :            :       {
    1055                 :            :         case t_FRAC:
    1056         [ -  + ]:     996158 :           if (!signe(gel(y,1))) return rcopy(x);
    1057         [ +  + ]:     996158 :           if (!signe(x))
    1058                 :            :           {
    1059                 :      11963 :             lx = expi(gel(y,1)) - expi(gel(y,2)) - expo(x);
    1060         [ -  + ]:      11963 :             return lx <= 0? rcopy(x): fractor(y, nbits2prec(lx));
    1061                 :            :           }
    1062                 :     984195 :           av=avma; z=addir(gel(y,1),mulir(gel(y,2),x)); tetpil=avma;
    1063                 :     984195 :           return gerepile(av,tetpil,divri(z,gel(y,2)));
    1064                 :   15985535 :         case t_COMPLEX: return addRc(x, y);
    1065         [ -  + ]:         14 :         case t_QUAD: return gequal0(y)? rcopy(x): addqf(y, x, lg(x));
    1066                 :            : 
    1067                 :          0 :         default: pari_err_TYPE2("+",x,y);
    1068                 :            :       }
    1069                 :            : 
    1070                 :            :     case t_INTMOD:
    1071   [ +  +  +  -  :       4006 :       switch(ty)
                   +  - ]
    1072                 :            :       {
    1073                 :       3500 :         case t_FRAC: { GEN X = gel(x,1);
    1074                 :       3500 :           z = cgetg(3, t_INTMOD);
    1075                 :       3500 :           p1 = Fp_div(gel(y,1), gel(y,2), X);
    1076                 :       3500 :           return add_intmod_same(z, X, p1, gel(x,2));
    1077                 :            :         }
    1078                 :            :         case t_FFELT:
    1079         [ -  + ]:        436 :           if (!equalii(gel(x,1),FF_p_i(y)))
    1080                 :          0 :             pari_err_OP("+",x,y);
    1081                 :        436 :           return FF_Z_add(y,gel(x,2));
    1082                 :         56 :         case t_COMPLEX: return addRc(x, y);
    1083                 :          0 :         case t_PADIC: { GEN X = gel(x,1);
    1084                 :          0 :           z = cgetg(3, t_INTMOD);
    1085                 :          0 :           return add_intmod_same(z, X, gel(x,2), padic_to_Fp(y, X));
    1086                 :            :         }
    1087                 :         14 :         case t_QUAD: return addRq(x, y);
    1088                 :            :       }
    1089                 :            : 
    1090                 :            :     case t_FRAC:
    1091   [ +  +  +  +  :     234556 :       switch (ty)
                      - ]
    1092                 :            :       {
    1093                 :     231196 :         case t_COMPLEX: return addRc(x, y);
    1094                 :            :         case t_PADIC:
    1095         [ -  + ]:       1911 :           if (!signe(gel(x,1))) return gcopy(y);
    1096                 :       1911 :           return addQp(x,y);
    1097                 :          7 :         case t_QUAD: return addRq(x, y);
    1098                 :       1442 :         case t_FFELT: return FF_Q_add(y, x);
    1099                 :            :       }
    1100                 :            : 
    1101                 :            :     case t_FFELT:
    1102                 :          0 :       pari_err_TYPE2("+",x,y);
    1103                 :            : 
    1104                 :            :     case t_COMPLEX:
    1105      [ +  +  - ]:         28 :       switch(ty)
    1106                 :            :       {
    1107                 :            :         case t_PADIC:
    1108         [ +  + ]:         21 :           return Zp_nosquare_m1(gel(y,2))? addRc(y, x): addTp(x, y);
    1109                 :            :         case t_QUAD:
    1110         [ -  + ]:          7 :           lx = precision(x); if (!lx) pari_err_OP("+",x,y);
    1111         [ -  + ]:          7 :           return gequal0(y)? gcopy(x): addqf(y, x, lx);
    1112                 :            :       }
    1113                 :            : 
    1114                 :            :     case t_PADIC: /* ty == t_QUAD */
    1115         [ #  # ]:          0 :       return (kro_quad(y,gel(x,2)) == -1)? addRq(x, y): addTp(y, x);
    1116                 :            :   }
    1117                 :            :   /* tx < ty, !is_const_t(y) */
    1118   [ +  +  +  + ]:   17951908 :   switch(ty)
    1119                 :            :   {
    1120                 :            :     case t_MAT:
    1121         [ -  + ]:      15197 :       if (is_matvec_t(tx)) pari_err_TYPE2("+",x,y);
    1122         [ +  + ]:      15197 :       if (isrationalzero(x)) return gcopy(y);
    1123                 :      15071 :       return RgM_Rg_add(y, x);
    1124                 :            :     case t_COL:
    1125         [ -  + ]:      34610 :       if (tx == t_VEC) pari_err_TYPE2("+",x,y);
    1126                 :      34610 :       return RgC_Rg_add(y, x);
    1127                 :            :     case t_POLMOD: /* is_const_t(tx) in this case */
    1128                 :     602921 :       return addsub_polmod_scal(gel(y,1), gel(y,2), x, &gadd);
    1129                 :            :   }
    1130         [ +  + ]:   17299180 :   if (is_scalar_t(tx))  {
    1131         [ +  + ]:   14475434 :     if (tx == t_POLMOD)
    1132                 :            :     {
    1133                 :      21987 :       vx = varn(gel(x,1));
    1134                 :      21987 :       vy = gvar(y);
    1135         [ +  + ]:      21987 :       if (vx == vy) y = gmod(y, gel(x,1)); /* error if ty == t_SER */
    1136                 :            :       else
    1137         [ +  + ]:      18186 :         if (varncmp(vx,vy) > 0) return add_scal(y, x, ty);
    1138                 :       3864 :       return addsub_polmod_scal(gel(x,1), gel(x,2), y, &gadd);
    1139                 :            :     }
    1140                 :   14453447 :     return add_scal(y, x, ty);
    1141                 :            :   }
    1142                 :            :   /* x and y are not scalars, ty != t_MAT */
    1143                 :    2823746 :   vx = gvar(x);
    1144                 :    2823746 :   vy = gvar(y);
    1145         [ +  + ]:    2823746 :   if (vx != vy) { /* x or y is treated as a scalar */
    1146 [ +  - ][ +  + ]:       3091 :     if (is_vec_t(tx) || is_vec_t(ty)) pari_err_TYPE2("+",x,y);
    1147                 :       6168 :     return (varncmp(vx, vy) < 0)? add_scal(x, y, tx)
    1148         [ +  + ]:       3084 :                                 : add_scal(y, x, ty);
    1149                 :            :   }
    1150                 :            :   /* vx = vy */
    1151      [ +  +  - ]:    2820655 :   switch(tx)
    1152                 :            :   {
    1153                 :            :     case t_POL:
    1154      [ +  +  - ]:    2820116 :       switch (ty)
    1155                 :            :       {
    1156                 :            :         case t_SER:
    1157         [ +  + ]:       2933 :           if (lg(x) == 2) return gcopy(y);
    1158                 :       2919 :           i = lg(y) + valp(y) - RgX_val(x);
    1159         [ +  + ]:       2919 :           if (i < 3) return gcopy(y);
    1160                 :            : 
    1161                 :       2912 :           p1 = RgX_to_ser(x,i); y = ser_add(p1,y);
    1162                 :       2912 :           settyp(p1, t_VECSMALL); /* p1 left on stack */
    1163                 :       2912 :           return y;
    1164                 :            : 
    1165                 :    2817183 :         case t_RFRAC: return add_rfrac_scal(y, x);
    1166                 :            :       }
    1167                 :          0 :       break;
    1168                 :            : 
    1169                 :            :     case t_SER:
    1170         [ +  - ]:        539 :       if (ty == t_RFRAC)
    1171                 :            :       {
    1172                 :            :         GEN n, d;
    1173                 :            :         long vn, vd;
    1174                 :        539 :         av = avma;
    1175                 :        539 :         n = gel(y,1); vn = gval(n, vy);
    1176                 :        539 :         d = gel(y,2); vd = RgX_valrem(d, &d);
    1177                 :            : 
    1178                 :        539 :         l = lg(x) + valp(x) - (vn - vd);
    1179         [ -  + ]:        539 :         if (l < 3) { avma = av; return gcopy(x); }
    1180                 :            : 
    1181                 :            :         /* take advantage of y = t^n ! */
    1182         [ +  + ]:        539 :         if (degpol(d))
    1183                 :         63 :           y = gdiv(n, RgX_to_ser_inexact(d,l));
    1184                 :            :         else {
    1185                 :        476 :           y = gdiv(n, gel(d,2));
    1186         [ +  + ]:        476 :           if (gvar(y) == vy) y = RgX_to_ser(y,l); else y = scalarser(y, vy, l);
    1187                 :            :         }
    1188                 :        539 :         setvalp(y, valp(y) - vd);
    1189                 :        539 :         return gerepileupto(av, gadd(y, x));
    1190                 :            :       }
    1191                 :          0 :       break;
    1192                 :            :   }
    1193                 :          0 :   pari_err_TYPE2("+",x,y);
    1194                 : 1304412778 :   return NULL; /* not reached */
    1195                 :            : }
    1196                 :            : 
    1197                 :            : GEN
    1198                 :   15421748 : gaddsg(long x, GEN y)
    1199                 :            : {
    1200                 :   15421748 :   long ty = typ(y);
    1201                 :            :   GEN z;
    1202                 :            : 
    1203   [ +  +  +  +  :   15421748 :   switch(ty)
                   +  + ]
    1204                 :            :   {
    1205                 :     778027 :     case t_INT:  return addsi(x,y);
    1206                 :    7014300 :     case t_REAL: return addsr(x,y);
    1207                 :            :     case t_INTMOD:
    1208                 :         14 :       z = cgetg(3, t_INTMOD);
    1209                 :         14 :       return add_intmod_same(z, gel(y,1), gel(y,2), modsi(x, gel(y,1)));
    1210                 :     383005 :     case t_FRAC: z = cgetg(3,t_FRAC);
    1211                 :     383005 :       gel(z,1) = gerepileuptoint((pari_sp)z, addii(gel(y,1), mulis(gel(y,2),x)));
    1212                 :     383005 :       gel(z,2) = icopy(gel(y,2)); return z;
    1213                 :            :     case t_COMPLEX:
    1214                 :    6825254 :       z = cgetg(3, t_COMPLEX);
    1215                 :    6825254 :       gel(z,1) = gaddsg(x, gel(y,1));
    1216                 :    6825254 :       gel(z,2) = gcopy(gel(y,2)); return z;
    1217                 :            : 
    1218                 :   15421748 :     default: return gadd(stoi(x), y);
    1219                 :            :   }
    1220                 :            : }
    1221                 :            : 
    1222                 :            : GEN
    1223                 :     597667 : gsubsg(long x, GEN y)
    1224                 :            : {
    1225                 :            :   GEN z, a, b;
    1226                 :            :   pari_sp av;
    1227                 :            : 
    1228   [ +  +  +  +  :     597667 :   switch(typ(y))
                   +  + ]
    1229                 :            :   {
    1230                 :     224955 :     case t_INT:  return subsi(x,y);
    1231                 :     292403 :     case t_REAL: return subsr(x,y);
    1232                 :            :     case t_INTMOD:
    1233                 :         49 :       z = cgetg(3, t_INTMOD); a = gel(y,1); b = gel(y,2);
    1234                 :         49 :       return add_intmod_same(z, a, Fp_neg(b,a), modsi(x, a));
    1235                 :       7742 :     case t_FRAC: z = cgetg(3,t_FRAC); a = gel(y,1); b = gel(y,2);
    1236                 :       7742 :       gel(z,1) = gerepileuptoint((pari_sp)z, subii(mulis(b,x), a));
    1237                 :       7742 :       gel(z,2) = icopy(gel(y,2)); return z;
    1238                 :            :     case t_COMPLEX:
    1239                 :      46415 :       z = cgetg(3, t_COMPLEX);
    1240                 :      46415 :       gel(z,1) = gsubsg(x, gel(y,1));
    1241                 :      46415 :       gel(z,2) = gneg(gel(y,2)); return z;
    1242                 :            :   }
    1243                 :      26103 :   av = avma;
    1244                 :     597667 :   return gerepileupto(av, gadd(stoi(x), gneg_i(y)));
    1245                 :            : }
    1246                 :            : 
    1247                 :            : /********************************************************************/
    1248                 :            : /**                                                                **/
    1249                 :            : /**                          SUBTRACTION                           **/
    1250                 :            : /**                                                                **/
    1251                 :            : /********************************************************************/
    1252                 :            : 
    1253                 :            : GEN
    1254                 : 1478563930 : gsub(GEN x, GEN y)
    1255                 :            : {
    1256                 : 1478563930 :   long tx = typ(x), ty = typ(y);
    1257                 :            :   pari_sp av;
    1258                 :            :   GEN z;
    1259 [ +  + ][ +  +  : 1478563930 :   if (tx == ty) switch(tx) /* shortcut to generic case */
          +  +  +  +  +  
          +  +  +  +  +  
                +  +  - ]
    1260                 :            :   {
    1261                 : 1283885805 :     case t_INT: return subii(x,y);
    1262                 :  146609353 :     case t_REAL: return subrr(x,y);
    1263                 :     257601 :     case t_INTMOD:  { GEN p1, X = gel(x,1), Y = gel(y,1);
    1264                 :     257601 :       z = cgetg(3,t_INTMOD);
    1265 [ +  + ][ +  + ]:     257599 :       if (X==Y || equalii(X,Y))
    1266                 :     257586 :         return sub_intmod_same(z, X, gel(x,2), gel(y,2));
    1267                 :         14 :       gel(z,1) = gcdii(X,Y);
    1268                 :         14 :       warn_coercion(X,Y,gel(z,1));
    1269                 :         14 :       av = avma; p1 = subii(gel(x,2),gel(y,2));
    1270                 :         14 :       gel(z,2) = gerepileuptoint(av, modii(p1, gel(z,1))); return z;
    1271                 :            :     }
    1272                 :    6668916 :     case t_FRAC: return addsub_frac(x,y, subii);
    1273                 :   16205949 :     case t_COMPLEX: z = cgetg(3,t_COMPLEX);
    1274                 :   16205949 :       gel(z,2) = gsub(gel(x,2),gel(y,2));
    1275         [ +  + ]:   16205949 :       if (isintzero(gel(z,2)))
    1276                 :            :       {
    1277                 :       6732 :         avma = (pari_sp)(z+3);
    1278                 :       6732 :         return gsub(gel(x,1),gel(y,1));
    1279                 :            :       }
    1280                 :   16199217 :       gel(z,1) = gsub(gel(x,1),gel(y,1));
    1281                 :   16199217 :       return z;
    1282                 :            :     case t_PADIC:
    1283         [ -  + ]:      11886 :       if (!equalii(gel(x,2),gel(y,2))) pari_err_OP("+",x,y);
    1284                 :      11886 :       return addsub_pp(x,y, subii);
    1285                 :        581 :     case t_QUAD: z = cgetg(4,t_QUAD);
    1286         [ -  + ]:        581 :       if (!ZX_equal(gel(x,1),gel(y,1))) pari_err_OP("+",x,y);
    1287                 :        581 :       gel(z,1) = ZX_copy(gel(x,1));
    1288                 :        581 :       gel(z,2) = gsub(gel(x,2),gel(y,2));
    1289                 :        581 :       gel(z,3) = gsub(gel(x,3),gel(y,3)); return z;
    1290                 :            :     case t_POLMOD:
    1291         [ +  + ]:     890355 :       if (RgX_equal_var(gel(x,1), gel(y,1)))
    1292                 :     890320 :         return addsub_polmod_same(gel(x,1), gel(x,2), gel(y,2), &gsub);
    1293                 :         35 :       return addsub_polmod(gel(x,1), gel(y,1), gel(x,2), gel(y,2), &gsub);
    1294                 :     416467 :     case t_FFELT: return FF_sub(x,y);
    1295                 :            :     case t_POL: {
    1296                 :    6580857 :       long vx = varn(x);
    1297                 :    6580857 :       long vy = varn(y);
    1298         [ +  + ]:    6580857 :       if (vx != vy) {
    1299         [ +  + ]:      13924 :         if (varncmp(vx, vy) < 0) return RgX_Rg_sub(x, y);
    1300                 :       2793 :         else                     return Rg_RgX_sub(x, y);
    1301                 :            :       }
    1302                 :    6566933 :       return RgX_sub(x, y);
    1303                 :            :     }
    1304                 :            :     case t_VEC:
    1305         [ -  + ]:      59951 :       if (lg(y) != lg(x)) pari_err_OP("+",x,y);
    1306                 :      59951 :       return RgV_sub(x,y);
    1307                 :            :     case t_COL:
    1308         [ -  + ]:    1177902 :       if (lg(y) != lg(x)) pari_err_OP("+",x,y);
    1309                 :    1177902 :       return RgC_sub(x,y);
    1310                 :            :     case t_MAT: {
    1311                 :       7118 :       long lx = lg(x);
    1312         [ -  + ]:       7118 :       if (lg(y) != lx) pari_err_OP("+",x,y);
    1313         [ -  + ]:       7118 :       if (lx == 1) return cgetg(1, t_MAT);
    1314         [ -  + ]:       7118 :       if (lgcols(y) != lgcols(x)) pari_err_OP("+",x,y);
    1315                 :       7118 :       return RgM_sub(x,y);
    1316                 :            :     }
    1317                 :    1887799 :     case t_RFRAC: case t_SER: break;
    1318                 :            : 
    1319                 :          0 :     default: pari_err_TYPE2("+",x,y);
    1320                 :            :   }
    1321                 :   15791189 :   av = avma;
    1322                 : 1478792760 :   return gerepileupto(av, gadd(x,gneg_i(y)));
    1323                 :            : }
    1324                 :            : 
    1325                 :            : /********************************************************************/
    1326                 :            : /**                                                                **/
    1327                 :            : /**                        MULTIPLICATION                          **/
    1328                 :            : /**                                                                **/
    1329                 :            : /********************************************************************/
    1330                 :            : static GEN
    1331                 :     228418 : mul_ser_scal(GEN y, GEN x) {
    1332                 :            :   long ly, i;
    1333                 :            :   GEN z;
    1334         [ +  + ]:     228418 :   if (isexactzero(x)) return gmul(RgX_get_0(y), x);
    1335         [ +  + ]:     227130 :   if (ser_isexactzero(y))
    1336                 :            :   {
    1337         [ +  - ]:       1414 :     if (lg(y) == 2) return gcopy(y);
    1338                 :          0 :     return scalarser(gmul(x,gel(y,2)), varn(y), valp(y));
    1339                 :            :   }
    1340                 :     225716 :   z = cgetg_copy(y, &ly); z[1] = y[1];
    1341         [ +  + ]:    1103412 :   for (i = 2; i < ly; i++) gel(z,i) = gmul(x,gel(y,i));
    1342                 :     228418 :   return normalize(z);
    1343                 :            : }
    1344                 :            : /* (n/d) * x, x "scalar" or polynomial in the same variable as d
    1345                 :            :  * [n/d a valid RFRAC]  */
    1346                 :            : static GEN
    1347                 :    9454571 : mul_rfrac_scal(GEN n, GEN d, GEN x)
    1348                 :            : {
    1349                 :    9454571 :   pari_sp av = avma;
    1350                 :            :   GEN z;
    1351                 :            : 
    1352      [ +  +  + ]:    9454571 :   switch(typ(x))
    1353                 :            :   {
    1354                 :            :     case t_PADIC:
    1355                 :          7 :       n = gmul(n, x);
    1356         [ +  - ]:          7 :       d = gcvtop(d, gel(x,2), signe(gel(x,4))? precp(x): 1);
    1357                 :          7 :       return gerepileupto(av, gdiv(n,d));
    1358                 :            : 
    1359                 :            :     case t_INTMOD: case t_POLMOD:
    1360                 :         14 :       n = gmul(n, x);
    1361                 :         14 :       d = gmul(d, gmodulo(gen_1, gel(x,1)));
    1362                 :         14 :       return gerepileupto(av, gdiv(n,d));
    1363                 :            :   }
    1364                 :    9454550 :   z = gred_rfrac2_i(x, d);
    1365                 :    9454550 :   n = simplify_shallow(n);
    1366         [ +  + ]:    9454550 :   if (typ(z) == t_RFRAC)
    1367                 :            :   {
    1368                 :    7119858 :     n = gmul(gel(z,1), n);
    1369                 :    7119858 :     d = gel(z,2);
    1370 [ +  + ][ -  + ]:    7119858 :     if (typ(n) == t_POL && varncmp(varn(n), varn(d)) < 0)
    1371                 :          0 :       z = RgX_Rg_div(n, d);
    1372                 :            :     else
    1373                 :    7119858 :       z = gred_rfrac_simple(n, d);
    1374                 :            :   }
    1375                 :            :   else
    1376                 :    2334692 :     z = gmul(z, n);
    1377                 :    9454571 :   return gerepileupto(av, z);
    1378                 :            : }
    1379                 :            : static GEN
    1380                 :   58961173 : mul_scal(GEN y, GEN x, long ty)
    1381                 :            : {
    1382   [ +  +  +  -  :   58961173 :   switch(ty)
                      - ]
    1383                 :            :   {
    1384                 :            :     case t_POL:
    1385         [ +  + ]:   50697152 :       if (lg(y) == 2) return scalarpol(gmul(gen_0,x), varn(y));
    1386                 :   49744545 :       return RgX_Rg_mul(y, x);
    1387                 :     152356 :     case t_SER: return mul_ser_scal(y, x);
    1388                 :    8111665 :     case t_RFRAC: return mul_rfrac_scal(gel(y,1),gel(y,2), x);
    1389                 :            :     case t_QFI: case t_QFR:
    1390 [ #  # ][ #  # ]:          0 :       if (typ(x) == t_INT && gequal1(x)) return gcopy(y); /* fall through */
    1391                 :            :   }
    1392                 :          0 :   pari_err_TYPE2("*",x,y);
    1393                 :   58961166 :   return NULL; /* not reached */
    1394                 :            : }
    1395                 :            : 
    1396                 :            : static GEN
    1397                 :     160830 : mul_gen_rfrac(GEN X, GEN Y)
    1398                 :            : {
    1399                 :     160830 :   GEN y1 = gel(Y,1), y2 = gel(Y,2);
    1400                 :     160830 :   long vx = gvar(X), vy = varn(y2);
    1401         [ +  + ]:     166570 :   return (varncmp(vx, vy) <= 0)? mul_scal(Y, X, typ(Y)):
    1402                 :       5740 :                                  gred_rfrac_simple(gmul(y1,X), y2);
    1403                 :            : }
    1404                 :            : /* (x1/x2) * (y1/y2) */
    1405                 :            : static GEN
    1406                 :    7744009 : mul_rfrac(GEN x1, GEN x2, GEN y1, GEN y2)
    1407                 :            : {
    1408                 :            :   GEN z, X, Y;
    1409                 :    7744009 :   pari_sp av = avma;
    1410                 :            : 
    1411                 :    7744009 :   X = gred_rfrac2_i(x1, y2);
    1412                 :    7744009 :   Y = gred_rfrac2_i(y1, x2);
    1413         [ +  + ]:    7744009 :   if (typ(X) == t_RFRAC)
    1414                 :            :   {
    1415         [ +  + ]:    6479589 :     if (typ(Y) == t_RFRAC) {
    1416                 :    6399664 :       x1 = gel(X,1);
    1417                 :    6399664 :       x2 = gel(X,2);
    1418                 :    6399664 :       y1 = gel(Y,1);
    1419                 :    6399664 :       y2 = gel(Y,2);
    1420                 :    6399664 :       z = gred_rfrac_simple(gmul(x1,y1), gmul(x2,y2));
    1421                 :            :     } else
    1422                 :      79925 :       z = mul_gen_rfrac(Y, X);
    1423                 :            :   }
    1424         [ +  + ]:    1264420 :   else if (typ(Y) == t_RFRAC)
    1425                 :      80905 :     z = mul_gen_rfrac(X, Y);
    1426                 :            :   else
    1427                 :    1183515 :     z = gmul(X, Y);
    1428                 :    7744009 :   return gerepileupto(av, z);
    1429                 :            : }
    1430                 :            : /* (x1/x2) /y2, x2 and y2 are t_POL in the same variable */
    1431                 :            : static GEN
    1432                 :     253127 : div_rfrac_pol(GEN x1, GEN x2, GEN y2)
    1433                 :            : {
    1434                 :     253127 :   pari_sp av = avma;
    1435                 :     253127 :   GEN X = gred_rfrac2_i(x1, y2);
    1436 [ +  + ][ +  + ]:     253127 :   if (typ(X) == t_RFRAC && varn(gel(X,2)) == varn(x2))
    1437                 :            :   {
    1438                 :     246575 :     x2 = RgX_mul(gel(X,2), x2);
    1439                 :     246575 :     x1 = gel(X,1);
    1440                 :            :   }
    1441                 :            :   else
    1442                 :       6552 :     x1 = X;
    1443                 :     253127 :   return gerepileupto(av, gred_rfrac_simple(x1, x2));
    1444                 :            : }
    1445                 :            : 
    1446                 :            : /* Mod(y, Y) * x,  assuming x scalar */
    1447                 :            : static GEN
    1448                 :    1173123 : mul_polmod_scal(GEN Y, GEN y, GEN x)
    1449                 :            : {
    1450                 :    1173123 :   GEN z = cgetg(3,t_POLMOD);
    1451                 :    1173123 :   gel(z,1) = RgX_copy(Y);
    1452                 :    1173123 :   gel(z,2) = gmul(x,y); return z;
    1453                 :            : }
    1454                 :            : 
    1455                 :            : /* cf mulqq */
    1456                 :            : static GEN
    1457                 :    1013161 : quad_polmod_mul(GEN P, GEN x, GEN y)
    1458                 :            : {
    1459                 :    1013161 :   GEN T = cgetg(4, t_POL), b = gel(P,3), c = gel(P,2), p1, p2, p3, p4;
    1460                 :    1013161 :   pari_sp tetpil, av = avma;
    1461                 :    1013161 :   T[1] = x[1];
    1462                 :    1013161 :   p2 = gmul(gel(x,2), gel(y,2));
    1463                 :    1013161 :   p3 = gmul(gel(x,3), gel(y,3));
    1464                 :    1013161 :   p1 = gmul(gneg_i(c),p3);
    1465                 :            :   /* operands are usually small: gadd ~ gmul and Karatsuba is a waste */
    1466         [ +  - ]:    1013161 :   if (typ(b) == t_INT)
    1467                 :            :   {
    1468         [ +  + ]:    1013161 :     if (signe(b))
    1469                 :            :     {
    1470                 :     728650 :       p4 = gadd(gmul(gel(x,2), gel(y,3)), gmul(gel(x,3), gel(y,2)));
    1471         [ +  + ]:     728650 :       if (is_pm1(b))
    1472                 :            :       {
    1473         [ +  + ]:     727887 :         if (signe(b) > 0) p3 = gneg(p3);
    1474                 :            :       }
    1475                 :            :       else
    1476                 :        763 :         p3 = gmul(negi(b), p3);
    1477                 :            :     }
    1478                 :            :     else
    1479                 :            :     {
    1480                 :     284511 :       p3 = gmul(gel(x,2),gel(y,3));
    1481                 :     284511 :       p4 = gmul(gel(x,3),gel(y,2));
    1482                 :            :     }
    1483                 :            :   }
    1484                 :            :   else
    1485                 :            :   {
    1486                 :          0 :     p4 = gadd(gmul(gel(x,2), gel(y,3)), gmul(gel(x,3), gel(y,2)));
    1487                 :          0 :     p3 = gmul(gneg_i(b), p3);
    1488                 :            :   }
    1489                 :    1013161 :   tetpil = avma;
    1490                 :    1013161 :   gel(T,2) = gadd(p2, p1);
    1491                 :    1013161 :   gel(T,3) = gadd(p4, p3);
    1492                 :    1013161 :   gerepilecoeffssp(av,tetpil,T+2,2);
    1493                 :    1013161 :   return normalizepol_lg(T,4);
    1494                 :            : }
    1495                 :            : /* Mod(x,T) * Mod(y,T) */
    1496                 :            : static GEN
    1497                 :    1706195 : mul_polmod_same(GEN T, GEN x, GEN y)
    1498                 :            : {
    1499                 :    1706195 :   GEN z = cgetg(3,t_POLMOD), a;
    1500                 :    1706195 :   long v = varn(T), lx = lg(x), ly = lg(y);
    1501                 :    1706195 :   gel(z,1) = RgX_copy(T);
    1502                 :            :   /* x * y mod T optimised */
    1503 [ +  + ][ +  + ]:    1706195 :   if (typ(x) != t_POL || varn(x) != v || lx <= 3
                 [ +  + ]
    1504 [ +  + ][ +  - ]:    1341698 :    || typ(y) != t_POL || varn(y) != v || ly <= 3)
                 [ +  + ]
    1505                 :     476049 :     a = gmul(x, y);
    1506                 :            :   else
    1507                 :            :   {
    1508 [ +  + ][ +  + ]:    1230146 :     if (lg(T) == 5 && isint1(gel(T,4))) /* quadratic fields */
    1509                 :    1011110 :       a = quad_polmod_mul(T, x, y);
    1510                 :            :     else
    1511                 :            :     {
    1512                 :     219036 :       pari_sp av = avma;
    1513                 :     219036 :       GEN p = NULL;
    1514 [ +  + ][ +  + ]:     219036 :       if (RgX_is_FpX(T, &p) && RgX_is_FpX(x, &p) && RgX_is_FpX(y, &p) && p)
         [ +  + ][ +  + ]
    1515                 :            :       {
    1516                 :      37121 :         T = RgX_to_FpX(T, p); x = RgX_to_FpX(x, p); y = RgX_to_FpX(y, p);
    1517         [ +  + ]:      37121 :         if (lgefint(p) == 3)
    1518                 :            :         {
    1519                 :      32284 :           ulong pp = p[2];
    1520                 :      32284 :           a = Flxq_mul(ZX_to_Flx(x, pp), ZX_to_Flx(y, pp), ZX_to_Flx(T, pp), pp);
    1521                 :      32284 :           a = Flx_to_ZX(a);
    1522                 :            :         }
    1523                 :            :         else
    1524                 :       4837 :           a = FpXQ_mul(x, y, T, p);
    1525                 :      37121 :         a = FpX_to_mod(a, p);
    1526                 :            :       }
    1527                 :            :       else
    1528                 :     181915 :         a = RgXQ_mul(x, y, gel(z,1));
    1529                 :     219036 :       a = gerepileupto(av, a);
    1530                 :            :     }
    1531                 :            :   }
    1532                 :    1706195 :   gel(z,2) = a; return z;
    1533                 :            : }
    1534                 :            : static GEN
    1535                 :      23677 : sqr_polmod(GEN T, GEN x)
    1536                 :            : {
    1537                 :      23677 :   GEN a, z = cgetg(3,t_POLMOD);
    1538                 :      23677 :   gel(z,1) = RgX_copy(T);
    1539 [ +  + ][ +  - ]:      23677 :   if (typ(x) != t_POL || varn(x) != varn(T) || lg(x) <= 3)
                 [ +  + ]
    1540                 :       3166 :     a = gsqr(x);
    1541                 :            :   else
    1542                 :            :   {
    1543                 :      20511 :     pari_sp av = avma;
    1544                 :      20511 :     GEN p = NULL;
    1545 [ +  + ][ +  + ]:      20511 :     if (RgX_is_FpX(T, &p) && RgX_is_FpX(x, &p) && p)
                 [ +  + ]
    1546                 :            :     {
    1547                 :         14 :       T = RgX_to_FpX(T, p); x = RgX_to_FpX(x, p);
    1548         [ +  + ]:         14 :       if (lgefint(p) == 3)
    1549                 :            :       {
    1550                 :          7 :         ulong pp = p[2];
    1551                 :          7 :         a = Flxq_sqr(ZX_to_Flx(x, pp), ZX_to_Flx(T, pp), pp);
    1552                 :          7 :         a = Flx_to_ZX(a);
    1553                 :            :       }
    1554                 :            :       else
    1555                 :          7 :         a = FpXQ_sqr(x, T, p);
    1556                 :         14 :       a = FpX_to_mod(a, p);
    1557                 :            :     }
    1558                 :            :     else
    1559                 :      20497 :       a = RgXQ_sqr(x, gel(z,1));
    1560                 :      20511 :     a = gerepileupto(av, a);
    1561                 :            :   }
    1562                 :      23677 :   gel(z,2) = a; return z;
    1563                 :            : }
    1564                 :            : /* Mod(x,X) * Mod(y,Y) */
    1565                 :            : static GEN
    1566                 :       1386 : mul_polmod(GEN X, GEN Y, GEN x, GEN y)
    1567                 :            : {
    1568                 :       1386 :   long T[3] = { evaltyp(t_POLMOD) | _evallg(3),0,0 };
    1569                 :       1386 :   long vx = varn(X), vy = varn(Y);
    1570                 :       1386 :   GEN z = cgetg(3,t_POLMOD);
    1571                 :            : 
    1572         [ +  + ]:       1386 :   if (vx==vy) {
    1573                 :            :     pari_sp av;
    1574                 :         14 :     gel(z,1) = RgX_gcd(X,Y); av = avma;
    1575                 :         14 :     warn_coercion(X,Y,gel(z,1));
    1576                 :         14 :     gel(z,2) = gerepileupto(av, gmod(gmul(x, y), gel(z,1)));
    1577                 :         14 :     return z;
    1578                 :            :   }
    1579         [ +  + ]:       1372 :   if (varncmp(vx, vy) < 0)
    1580                 :         21 :   { gel(z,1) = RgX_copy(X); gel(T,1) = Y; gel(T,2) = y; y = T; }
    1581                 :            :   else
    1582                 :       1351 :   { gel(z,1) = RgX_copy(Y); gel(T,1) = X; gel(T,2) = x; x = T; }
    1583                 :       1386 :   gel(z,2) = gmul(x, y); return z;
    1584                 :            : }
    1585                 :            : 
    1586                 :            : #if 0 /* used by 3M only */
    1587                 :            : /* set z = x+y and return 1 if x,y have the same sign
    1588                 :            :  * set z = x-y and return 0 otherwise */
    1589                 :            : static int
    1590                 :            : did_add(GEN x, GEN y, GEN *z)
    1591                 :            : {
    1592                 :            :   long tx = typ(x), ty = typ(y);
    1593                 :            :   if (tx == ty) switch(tx)
    1594                 :            :   {
    1595                 :            :     case t_INT: *z = addii(x,y); return 1;
    1596                 :            :     case t_FRAC: *z = addsub_frac(x,y,addii); return 1;
    1597                 :            :     case t_REAL:
    1598                 :            :       if (signe(x) == -signe(y))
    1599                 :            :       { *z = subrr(x,y); return 0; }
    1600                 :            :       else
    1601                 :            :       { *z = addrr(x,y); return 1; }
    1602                 :            :   }
    1603                 :            :   if (tx == t_REAL) switch(ty)
    1604                 :            :   {
    1605                 :            :     case t_INT:
    1606                 :            :       if (signe(x) == -signe(y))
    1607                 :            :       { *z = subri(x,y); return 0; }
    1608                 :            :       else
    1609                 :            :       { *z = addri(x,y); return 1; }
    1610                 :            :     case t_FRAC:
    1611                 :            :       if (signe(x) == -signe(gel(y,1)))
    1612                 :            :       { *z = gsub(x,y); return 0; }
    1613                 :            :       else
    1614                 :            :       { *z = gadd(x,y); return 1; }
    1615                 :            :   }
    1616                 :            :   else if (ty == t_REAL) switch(tx)
    1617                 :            :   {
    1618                 :            :     case t_INT:
    1619                 :            :       if (signe(x) == -signe(y))
    1620                 :            :       { *z = subir(x,y); return 0; }
    1621                 :            :       else
    1622                 :            :       { *z = addir(x,y); return 1; }
    1623                 :            :     case t_FRAC:
    1624                 :            :       if (signe(gel(x,1)) == -signe(y))
    1625                 :            :       { *z = gsub(x,y); return 0; }
    1626                 :            :       else
    1627                 :            :       { *z = gadd(x,y); return 1; }
    1628                 :            :   }
    1629                 :            :   *z = gadd(x,y); return 1;
    1630                 :            : }
    1631                 :            : #endif
    1632                 :            : /* x * I * y, x t_COMPLEX with non-intzero real part, y non-intzero "scalar" */
    1633                 :            : static GEN
    1634                 :     902436 : mulcIR(GEN x, GEN y)
    1635                 :            : {
    1636                 :     902436 :   GEN z = cgetg(3,t_COMPLEX);
    1637                 :     902436 :   pari_sp av = avma;
    1638                 :     902436 :   gel(z,1) = gerepileupto(av, gneg(gmul(y,gel(x,2))));
    1639                 :     902436 :   gel(z,2) = gmul(y, gel(x,1));
    1640                 :     902436 :   return z;
    1641                 :            : 
    1642                 :            : }
    1643                 :            : /* x,y COMPLEX */
    1644                 :            : static GEN
    1645                 :   69648365 : mulcc(GEN x, GEN y)
    1646                 :            : {
    1647                 :   69648365 :   GEN xr = gel(x,1), xi = gel(x,2);
    1648                 :   69648365 :   GEN yr = gel(y,1), yi = gel(y,2);
    1649                 :            :   GEN p1, p2, p3, p4, z;
    1650                 :            :   pari_sp tetpil, av;
    1651                 :            : 
    1652         [ +  + ]:   69648365 :   if (isintzero(xr))
    1653                 :            :   {
    1654         [ +  + ]:     906441 :     if (isintzero(yr)) {
    1655                 :     131762 :       av = avma;
    1656                 :     131762 :       return gerepileupto(av, gneg(gmul(xi,yi)));
    1657                 :            :     }
    1658                 :     774679 :     return mulcIR(y, xi);
    1659                 :            :   }
    1660         [ +  + ]:   68741924 :   if (isintzero(yr)) return mulcIR(x, yi);
    1661                 :            : 
    1662                 :   68614167 :   z = cgetg(3,t_COMPLEX); av = avma;
    1663                 :            : #if 0
    1664                 :            :   /* 3M method avoiding catastrophic cancellation, BUT loses accuracy due to
    1665                 :            :    * e.g. xr + xi if exponents differ */
    1666                 :            :   if (did_add(xr, xi, &p3))
    1667                 :            :   {
    1668                 :            :     if (did_add(yr, yi, &p4)) {
    1669                 :            :     /* R = xr*yr - xi*yi
    1670                 :            :      * I = (xr+xi)(yr+yi) - xr*yr - xi*yi */
    1671                 :            :       p1 = gmul(xr,yr);
    1672                 :            :       p2 = gmul(xi,yi); p2 = gneg(p2);
    1673                 :            :       p3 = gmul(p3, p4);
    1674                 :            :       p4 = gsub(p2, p1);
    1675                 :            :     } else {
    1676                 :            :     /* R = (xr + xi) * (yr - yi) + (xr * yi - xi * yr)
    1677                 :            :      * I = xr*yi + xi*yr */
    1678                 :            :       p1 = gmul(p3,p4);
    1679                 :            :       p3 = gmul(xr,yi);
    1680                 :            :       p4 = gmul(xi,yr);
    1681                 :            :       p2 = gsub(p3, p4);
    1682                 :            :     }
    1683                 :            :   } else {
    1684                 :            :     if (did_add(yr, yi, &p4)) {
    1685                 :            :      /* R = (xr - xi) * (yr + yi) + (xi * yr - xr * yi)
    1686                 :            :       * I = xr*yi +xi*yr */
    1687                 :            :       p1 = gmul(p3,p4);
    1688                 :            :       p3 = gmul(xr,yi);
    1689                 :            :       p4 = gmul(xi,yr);
    1690                 :            :       p2 = gsub(p4, p3);
    1691                 :            :     } else {
    1692                 :            :     /* R = xr*yr - xi*yi
    1693                 :            :      * I = -(xr-xi)(yr-yi) + xr*yr + xi*yi */
    1694                 :            :       p3 = gneg( gmul(p3, p4) );
    1695                 :            :       p1 = gmul(xr,yr);
    1696                 :            :       p2 = gmul(xi,yi);
    1697                 :            :       p4 = gadd(p1, p2);
    1698                 :            : 
    1699                 :            :       p2 = gneg(p2);
    1700                 :            :     }
    1701                 :            :   }
    1702                 :            :   tetpil = avma;
    1703                 :            :   gel(z,1) = gadd(p1,p2);
    1704                 :            :   gel(z,2) = gadd(p3,p4);
    1705                 :            : #else
    1706 [ +  + ][ +  + ]:   68614167 :   if (typ(xr)==t_INT && typ(yr)==t_INT && typ(xi)==t_INT && typ(yi)==t_INT)
         [ +  - ][ +  + ]
    1707                 :            :   { /* 3M formula */
    1708                 :        168 :     p3 = addii(xr,xi);
    1709                 :        168 :     p4 = addii(yr,yi);
    1710                 :        168 :     p1 = mulii(xr,yr);
    1711                 :        168 :     p2 = mulii(xi,yi);
    1712                 :        168 :     p3 = mulii(p3,p4);
    1713                 :        168 :     p4 = addii(p2,p1);
    1714                 :        168 :     tetpil = avma;
    1715                 :        168 :     gel(z,1) = subii(p1,p2);
    1716                 :        168 :     gel(z,2) = subii(p3,p4);
    1717         [ +  + ]:        168 :     if (!signe(gel(z,2)))
    1718                 :         49 :       return gerepileuptoint((pari_sp)(z+3), gel(z,1));
    1719                 :            :   }
    1720                 :            :   else
    1721                 :            :   { /* naive 4M formula: avoid all loss of accuracy */
    1722                 :   68613999 :     p1 = gmul(xr,yr);
    1723                 :   68613999 :     p2 = gmul(xi,yi);
    1724                 :   68613999 :     p3 = gmul(xr,yi);
    1725                 :   68613999 :     p4 = gmul(xi,yr);
    1726                 :   68613999 :     tetpil = avma;
    1727                 :   68613999 :     gel(z,1) = gsub(p1,p2);
    1728                 :   68613999 :     gel(z,2) = gadd(p3,p4);
    1729         [ +  + ]:   68613999 :     if (isintzero(gel(z,2)))
    1730                 :            :     {
    1731                 :       9219 :       cgiv(gel(z,2));
    1732                 :       9219 :       return gerepileupto((pari_sp)(z+3), gel(z,1));
    1733                 :            :     }
    1734                 :            :   }
    1735                 :            : #endif
    1736                 :            : 
    1737                 :   69648365 :   gerepilecoeffssp(av,tetpil, z+1,2); return z;
    1738                 :            : }
    1739                 :            : /* x,y PADIC */
    1740                 :            : static GEN
    1741                 :    1222458 : mulpp(GEN x, GEN y) {
    1742                 :    1222458 :   long l = valp(x) + valp(y);
    1743                 :            :   pari_sp av;
    1744                 :            :   GEN z, t;
    1745         [ -  + ]:    1222458 :   if (!equalii(gel(x,2),gel(y,2))) pari_err_OP("*",x,y);
    1746         [ +  + ]:    1222458 :   if (!signe(gel(x,4))) return zeropadic(gel(x,2), l);
    1747         [ +  + ]:    1064685 :   if (!signe(gel(y,4))) return zeropadic(gel(x,2), l);
    1748                 :            : 
    1749         [ +  + ]:    1005710 :   t = (precp(x) > precp(y))? y: x;
    1750                 :    1005710 :   z = cgetp(t); setvalp(z,l); av = avma;
    1751                 :    1005709 :   affii(remii(mulii(gel(x,4),gel(y,4)), gel(t,3)), gel(z,4));
    1752                 :    1222458 :   avma = av; return z;
    1753                 :            : }
    1754                 :            : /* x,y QUAD */
    1755                 :            : static GEN
    1756                 :       1344 : mulqq(GEN x, GEN y) {
    1757                 :       1344 :   GEN z = cgetg(4,t_QUAD);
    1758                 :       1344 :   GEN p1, p2, p3, p4, P = gel(x,1), b = gel(P,3), c = gel(P,2);
    1759                 :            :   pari_sp av, tetpil;
    1760         [ -  + ]:       1344 :   if (!ZX_equal(P, gel(y,1))) pari_err_OP("*",x,y);
    1761                 :            : 
    1762                 :       1344 :   gel(z,1) = ZX_copy(P); av = avma;
    1763                 :       1344 :   p2 = gmul(gel(x,2),gel(y,2));
    1764                 :       1344 :   p3 = gmul(gel(x,3),gel(y,3));
    1765                 :       1344 :   p1 = gmul(gneg_i(c),p3);
    1766                 :            : 
    1767         [ +  + ]:       1344 :   if (signe(b))
    1768                 :       1239 :     p4 = gadd(gmul(gel(x,2),gel(y,3)), gmul(gel(x,3),gel(y,2)));
    1769                 :            :   else
    1770                 :            :   {
    1771                 :        105 :     p3 = gmul(gel(x,2),gel(y,3));
    1772                 :        105 :     p4 = gmul(gel(x,3),gel(y,2));
    1773                 :            :   }
    1774                 :       1344 :   tetpil = avma;
    1775                 :       1344 :   gel(z,2) = gadd(p2,p1);
    1776                 :       1344 :   gel(z,3) = gadd(p4,p3);
    1777                 :       1344 :   gerepilecoeffssp(av,tetpil,z+2,2); return z;
    1778                 :            : }
    1779                 :            : 
    1780                 :            : GEN
    1781                 :    2118392 : mulcxI(GEN x)
    1782                 :            : {
    1783                 :            :   GEN z;
    1784      [ +  +  + ]:    2118392 :   switch(typ(x))
    1785                 :            :   {
    1786                 :            :     case t_INT: case t_REAL: case t_FRAC:
    1787                 :     212949 :       return mkcomplex(gen_0, x);
    1788                 :            :     case t_COMPLEX:
    1789         [ +  + ]:    1905387 :       if (isintzero(gel(x,1))) return gneg(gel(x,2));
    1790                 :    1903273 :       z = cgetg(3,t_COMPLEX);
    1791                 :    1903273 :       gel(z,1) = gneg(gel(x,2));
    1792                 :    1903273 :       gel(z,2) = gel(x,1); return z;
    1793                 :            :     default:
    1794                 :    2118392 :       return gmul(gen_I(), x);
    1795                 :            :   }
    1796                 :            : }
    1797                 :            : GEN
    1798                 :      47838 : mulcxmI(GEN x)
    1799                 :            : {
    1800                 :            :   GEN z;
    1801      [ +  +  + ]:      47838 :   switch(typ(x))
    1802                 :            :   {
    1803                 :            :     case t_INT: case t_REAL: case t_FRAC:
    1804                 :       2051 :       return mkcomplex(gen_0, gneg(x));
    1805                 :            :     case t_COMPLEX:
    1806         [ +  + ]:      45731 :       if (isintzero(gel(x,1))) return gel(x,2);
    1807                 :      44744 :       z = cgetg(3,t_COMPLEX);
    1808                 :      44744 :       gel(z,1) = gel(x,2);
    1809                 :      44744 :       gel(z,2) = gneg(gel(x,1)); return z;
    1810                 :            :     default:
    1811                 :      47838 :       return gmul(mkcomplex(gen_0, gen_m1), x);
    1812                 :            :   }
    1813                 :            : }
    1814                 :            : 
    1815                 :            : /* fill in coefficients of t_SER z from coeffs of t_POL y */
    1816                 :            : static GEN
    1817                 :    1645560 : fill_ser(GEN z, GEN y)
    1818                 :            : {
    1819                 :    1645560 :   long i, lx = lg(z), ly = lg(y);
    1820         [ +  + ]:    1645560 :   if (ly >= lx) {
    1821         [ +  + ]:    7321480 :     for (i = 2; i < lx; i++) gel(z,i) = gel(y,i);
    1822                 :            :   } else {
    1823         [ +  + ]:      17955 :     for (i = 2; i < ly; i++) gel(z,i) = gel(y,i);
    1824         [ +  + ]:      29694 :     for (     ; i < lx; i++) gel(z,i) = gen_0;
    1825                 :            :   }
    1826                 :    1645560 :   return normalize(z);
    1827                 :            : }
    1828                 :            : 
    1829                 :            : GEN
    1830                 : 2921326313 : gmul(GEN x, GEN y)
    1831                 :            : {
    1832                 :            :   long tx, ty, lx, ly, vx, vy, i, l;
    1833                 :            :   pari_sp av, tetpil;
    1834                 :            :   GEN z, p1, p2;
    1835                 :            : 
    1836         [ +  + ]: 2921326313 :   if (x == y) return gsqr(x);
    1837                 : 2079535845 :   tx = typ(x); ty = typ(y);
    1838 [ +  + ][ +  +  : 2079535845 :   if (tx == ty) switch(tx)
          +  +  +  +  +  
          +  +  +  +  +  
             +  +  +  +  
                      - ]
    1839                 :            :   {
    1840                 : 1079867725 :     case t_INT: return mulii(x,y);
    1841                 :  510995243 :     case t_REAL: return mulrr(x,y);
    1842                 :    1418293 :     case t_INTMOD: { GEN X = gel(x,1), Y = gel(y,1);
    1843                 :    1418293 :       z = cgetg(3,t_INTMOD);
    1844 [ +  - ][ +  + ]:    1418285 :       if (X==Y || equalii(X,Y))
    1845                 :    1418274 :         return mul_intmod_same(z, X, gel(x,2), gel(y,2));
    1846                 :          7 :       gel(z,1) = gcdii(X,Y);
    1847                 :          7 :       warn_coercion(X,Y,gel(z,1));
    1848                 :          7 :       av = avma; p1 = mulii(gel(x,2),gel(y,2));
    1849                 :          7 :       gel(z,2) = gerepileuptoint(av, remii(p1, gel(z,1))); return z;
    1850                 :            :     }
    1851                 :            :     case t_FRAC:
    1852                 :            :     {
    1853                 :   10995714 :       GEN x1 = gel(x,1), x2 = gel(x,2);
    1854                 :   10995714 :       GEN y1 = gel(y,1), y2 = gel(y,2);
    1855                 :   10995714 :       z=cgetg(3,t_FRAC);
    1856                 :   10995714 :       p1 = gcdii(x1, y2);
    1857         [ +  + ]:   10995714 :       if (!is_pm1(p1)) { x1 = diviiexact(x1,p1); y2 = diviiexact(y2,p1); }
    1858                 :   10995714 :       p1 = gcdii(x2, y1);
    1859         [ +  + ]:   10995714 :       if (!is_pm1(p1)) { x2 = diviiexact(x2,p1); y1 = diviiexact(y1,p1); }
    1860                 :   10995714 :       tetpil = avma;
    1861                 :   10995714 :       gel(z,2) = mulii(x2,y2);
    1862                 :   10995714 :       gel(z,1) = mulii(x1,y1);
    1863         [ +  + ]:   10995714 :       fix_frac_if_int_GC(z,tetpil); return z;
    1864                 :            :     }
    1865                 :   68132363 :     case t_COMPLEX: return mulcc(x, y);
    1866                 :    1118183 :     case t_PADIC: return mulpp(x, y);
    1867                 :       1022 :     case t_QUAD: return mulqq(x, y);
    1868                 :   10547622 :     case t_FFELT: return FF_mul(x, y);
    1869                 :            :     case t_POLMOD:
    1870         [ +  + ]:    1512183 :       if (RgX_equal_var(gel(x,1), gel(y,1)))
    1871                 :    1510797 :         return mul_polmod_same(gel(x,1), gel(x,2), gel(y,2));
    1872                 :       1386 :       return mul_polmod(gel(x,1), gel(y,1), gel(x,2), gel(y,2));
    1873                 :            :     case t_POL:
    1874                 :   34658699 :       vx = varn(x);
    1875                 :   34658699 :       vy = varn(y);
    1876         [ +  + ]:   34658699 :       if (vx != vy) {
    1877         [ +  + ]:    4688382 :         if (varncmp(vx, vy) < 0) return RgX_Rg_mul(x, y);
    1878                 :    1998675 :         else                     return RgX_Rg_mul(y, x);
    1879                 :            :       }
    1880 [ +  + ][ +  + ]:   29970317 :       if (RgX_is_ZX(x) && RgX_is_ZX(y)) return ZX_mul(x,y);
    1881                 :    5511619 :       return RgX_mul(x, y);
    1882                 :            : 
    1883                 :            :     case t_SER: {
    1884                 :    1645413 :       GEN p = NULL;
    1885                 :    1645413 :       vx = varn(x);
    1886                 :    1645413 :       vy = varn(y);
    1887         [ -  + ]:    1645413 :       if (vx != vy) {
    1888         [ #  # ]:          0 :         if (varncmp(vx, vy) < 0) return mul_ser_scal(x, y);
    1889                 :          0 :         else                     return mul_ser_scal(y, x);
    1890                 :            :       }
    1891                 :    1645413 :       lx = lg(x);
    1892         [ +  + ]:    1645413 :       ly = lg(y); if (lx > ly) { lx = ly; swap(x, y); }
    1893         [ +  + ]:    1645413 :       if (lx == 2) return zeroser(vx, valp(x)+valp(y));
    1894                 :    1645399 :       z = cgetg(lx,t_SER);
    1895                 :    1645399 :       z[1] = evalvalp(valp(x)+valp(y)) | evalvarn(vx) | evalsigne(1);
    1896                 :    1645399 :       x = ser2pol_i(x, lx);
    1897                 :    1645399 :       y = ser2pol_i(y, lx);
    1898 [ +  + ][ +  + ]:    1645399 :       if (RgX_is_FpX(x,&p) && RgX_is_FpX(y,&p))
    1899                 :            :       {
    1900         [ +  + ]:      14694 :         if (!p) y = ZX_mul(x,y);
    1901                 :            :         else
    1902                 :            :         {
    1903                 :         21 :           x = RgX_to_FpX(x, p);
    1904                 :         21 :           y = RgX_to_FpX(y, p);
    1905                 :         21 :           y = FpX_to_mod(ZX_mul(x,y), p);
    1906                 :            :         }
    1907                 :            :       }
    1908                 :            :       else
    1909                 :    1630726 :         y = RgXn_mul(x, y, lx-2);
    1910                 :    1645399 :       z = fill_ser(z, y);
    1911                 :    1645413 :       return gerepilecopy((pari_sp)(z + lx), z);
    1912                 :            :     }
    1913                 :    2505298 :     case t_QFI: return qficomp(x,y);
    1914                 :          7 :     case t_QFR: return qfrcomp(x,y);
    1915                 :    6557680 :     case t_RFRAC: return mul_rfrac(gel(x,1),gel(x,2), gel(y,1),gel(y,2));
    1916                 :    1066721 :     case t_MAT: return RgM_mul(x, y);
    1917                 :            : 
    1918                 :            :     case t_VECSMALL: /* multiply as permutation. cf perm_mul */
    1919                 :     131621 :       z = cgetg_copy(x, &l);
    1920         [ -  + ]:     131621 :       if (l != lg(y)) break;
    1921         [ +  + ]:    2310854 :       for (i=1; i<l; i++)
    1922                 :            :       {
    1923                 :    2179233 :         long yi = y[i];
    1924 [ +  - ][ -  + ]:    2179233 :         if (yi < 1 || yi >= l) pari_err_TYPE2("*",x,y);
    1925                 :    2179233 :         z[i] = x[yi];
    1926                 :            :       }
    1927                 :     131621 :       return z;
    1928                 :            : 
    1929                 :            : 
    1930                 :            :     default:
    1931                 :          0 :       pari_err_TYPE2("*",x,y);
    1932                 :            :   }
    1933                 :            :   /* tx != ty */
    1934 [ +  + ][ +  + ]:  348382058 :   if (is_const_t(ty) && is_const_t(tx))  {
    1935         [ +  + ]:  278556283 :     if (tx > ty) { swap(x,y); lswap(tx,ty); }
    1936   [ +  +  +  +  :  278556283 :     switch(tx) {
             -  +  +  - ]
    1937                 :            :     case t_INT:
    1938   [ +  +  +  +  :  252315336 :       switch(ty)
             +  +  +  - ]
    1939                 :            :       {
    1940         [ +  + ]:  155509642 :         case t_REAL: return signe(x)? mulir(x,y): gen_0;
    1941                 :            :         case t_INTMOD:
    1942                 :    1583663 :           z = cgetg(3, t_INTMOD);
    1943                 :    1583650 :           return mul_intmod_same(z, gel(y,1), gel(y,2), modii(x, gel(y,1)));
    1944                 :            :         case t_FRAC:
    1945         [ +  + ]:   54592920 :           if (!signe(x)) return gen_0;
    1946                 :   24155757 :           z=cgetg(3,t_FRAC);
    1947                 :   24155757 :           p1 = gcdii(x,gel(y,2));
    1948         [ +  + ]:   24155757 :           if (is_pm1(p1))
    1949                 :            :           {
    1950                 :   14941331 :             avma = (pari_sp)z;
    1951                 :   14941331 :             gel(z,2) = icopy(gel(y,2));
    1952                 :   14941331 :             gel(z,1) = mulii(gel(y,1), x);
    1953                 :            :           }
    1954                 :            :           else
    1955                 :            :           {
    1956                 :    9214426 :             x = diviiexact(x,p1); tetpil = avma;
    1957                 :    9214426 :             gel(z,2) = diviiexact(gel(y,2), p1);
    1958                 :    9214426 :             gel(z,1) = mulii(gel(y,1), x);
    1959         [ +  + ]:    9214426 :             fix_frac_if_int_GC(z,tetpil);
    1960                 :            :           }
    1961                 :   24155757 :           return z;
    1962         [ +  + ]:   39203835 :         case t_COMPLEX: return signe(x)? mulRc(x, y): gen_0;
    1963         [ +  + ]:      98542 :         case t_PADIC: return signe(x)? mulTp(x, y): gen_0;
    1964                 :       1281 :         case t_QUAD: return mulRq(x,y);
    1965                 :    1325454 :         case t_FFELT: return FF_Z_mul(y,x);
    1966                 :            :       }
    1967                 :            : 
    1968                 :            :     case t_REAL:
    1969   [ +  +  +  + ]:   26153434 :       switch(ty)
    1970                 :            :       {
    1971                 :    1480153 :         case t_FRAC: return mulrfrac(x, y);
    1972                 :   24673267 :         case t_COMPLEX: return mulRc(x, y);
    1973                 :          7 :         case t_QUAD: return mulqf(y, x, lg(x));
    1974                 :          7 :         default: pari_err_TYPE2("*",x,y);
    1975                 :            :       }
    1976                 :            : 
    1977                 :            :     case t_INTMOD:
    1978   [ +  +  -  +  :       5338 :       switch(ty)
                   +  - ]
    1979                 :            :       {
    1980                 :        504 :         case t_FRAC: { GEN X = gel(x,1);
    1981                 :        504 :           z = cgetg(3, t_INTMOD); p1 = Fp_mul(gel(y,1), gel(x,2), X);
    1982                 :        504 :           return div_intmod_same(z, X, p1, remii(gel(y,2), X));
    1983                 :            :         }
    1984                 :         35 :         case t_COMPLEX: return mulRc_direct(x,y);
    1985                 :          0 :         case t_PADIC: { GEN X = gel(x,1);
    1986                 :          0 :           z = cgetg(3, t_INTMOD);
    1987                 :          0 :           return mul_intmod_same(z, X, gel(x,2), padic_to_Fp(y, X));
    1988                 :            :         }
    1989                 :         42 :         case t_QUAD: return mulRq(x, y);
    1990                 :            :         case t_FFELT:
    1991         [ -  + ]:       4757 :           if (!equalii(gel(x,1),FF_p_i(y)))
    1992                 :          0 :             pari_err_OP("*",x,y);
    1993                 :       4757 :           return FF_Z_mul(y,gel(x,2));
    1994                 :            :       }
    1995                 :            : 
    1996                 :            :     case t_FRAC:
    1997   [ +  +  +  +  :      82144 :       switch(ty)
                      - ]
    1998                 :            :       {
    1999                 :      69831 :         case t_COMPLEX: return mulRc(x, y);
    2000         [ +  - ]:      10038 :         case t_PADIC: return signe(gel(x,1))? mulTp(x, y): gen_0;
    2001                 :        455 :         case t_QUAD:  return mulRq(x, y);
    2002                 :       1820 :         case t_FFELT: return FF_Z_Z_muldiv(y, gel(x,1),gel(x,2));
    2003                 :            :       }
    2004                 :            : 
    2005                 :            :     case t_FFELT:
    2006                 :          0 :       pari_err_TYPE2("*",x,y);
    2007                 :            : 
    2008                 :            :     case t_COMPLEX:
    2009      [ +  +  - ]:         14 :       switch(ty)
    2010                 :            :       {
    2011                 :            :         case t_PADIC:
    2012         [ -  + ]:          7 :           return Zp_nosquare_m1(gel(y,2))? mulRc(y, x): mulTp(x, y);
    2013                 :            :         case t_QUAD:
    2014         [ -  + ]:          7 :           lx = precision(x); if (!lx) pari_err_OP("*",x,y);
    2015                 :          7 :           return mulqf(y, x, lx);
    2016                 :            :       }
    2017                 :            : 
    2018                 :            :     case t_PADIC: /* ty == t_QUAD */
    2019         [ +  + ]:         21 :       return (kro_quad(y,gel(x,2))== -1)? mulRq(x, y): mulTp(y, x);
    2020                 :            :     }
    2021                 :            :   }
    2022                 :            : 
    2023         [ +  + ]:   69882377 :   if (is_matvec_t(ty))
    2024                 :            :   {
    2025         [ +  + ]:    8044655 :     if (!is_matvec_t(tx))
    2026                 :            :     {
    2027         [ -  + ]:    7657354 :       if (is_noncalc_t(tx)) pari_err_TYPE2( "*",x,y); /* necessary if ly = 1 */
    2028                 :    7657354 :       z = cgetg_copy(y, &ly);
    2029         [ +  + ]:  134804922 :       for (i=1; i<ly; i++) gel(z,i) = gmul(x,gel(y,i));
    2030                 :    7657354 :       return z;
    2031                 :            :     }
    2032   [ +  +  +  - ]:     387301 :     switch(tx)
    2033                 :            :     {
    2034                 :            :       case t_VEC:
    2035      [ +  +  - ]:     297936 :         switch(ty) {
    2036                 :     243169 :           case t_COL: return RgV_RgC_mul(x,y);
    2037                 :      54767 :           case t_MAT: return RgV_RgM_mul(x,y);
    2038                 :            :         }
    2039                 :          0 :         break;
    2040                 :            :       case t_COL:
    2041      [ +  -  - ]:          7 :         switch(ty) {
    2042                 :          7 :           case t_VEC: return RgC_RgV_mul(x,y);
    2043                 :          0 :           case t_MAT: return RgC_RgM_mul(x,y);
    2044                 :            :         }
    2045                 :          0 :         break;
    2046                 :            :       case t_MAT:
    2047      [ -  +  - ]:      89358 :         switch(ty) {
    2048                 :          0 :           case t_VEC: return RgM_RgV_mul(x,y);
    2049                 :      89358 :           case t_COL: return RgM_RgC_mul(x,y);
    2050                 :            :         }
    2051                 :            :     }
    2052                 :            :   }
    2053         [ +  + ]:   61837729 :   if (is_matvec_t(tx))
    2054                 :            :   {
    2055         [ -  + ]:     241707 :     if (is_noncalc_t(ty)) pari_err_TYPE2( "*",x,y); /* necessary if lx = 1 */
    2056                 :     241709 :     z = cgetg_copy(x, &lx);
    2057         [ +  + ]:    1300094 :     for (i=1; i<lx; i++) gel(z,i) = gmul(y,gel(x,i));
    2058                 :     241709 :     return z;
    2059                 :            :   }
    2060         [ +  + ]:   61596022 :   if (tx > ty) { swap(x,y); lswap(tx,ty); }
    2061                 :            :   /* tx < ty, !ismatvec(x and y) */
    2062                 :            : 
    2063         [ +  + ]:   61596022 :   if (ty == t_POLMOD) /* is_const_t(tx) in this case */
    2064                 :    1172227 :     return mul_polmod_scal(gel(y,1), gel(y,2), x);
    2065         [ +  + ]:   60423795 :   if (is_scalar_t(tx)) {
    2066         [ +  + ]:   57588219 :     if (tx == t_POLMOD) {
    2067                 :     228915 :       vx = varn(gel(x,1));
    2068                 :     228915 :       vy = gvar(y);
    2069         [ +  + ]:     228915 :       if (vx != vy) {
    2070         [ +  + ]:      33650 :         if (varncmp(vx,vy) > 0) return mul_scal(y, x, ty);
    2071                 :        896 :         return mul_polmod_scal(gel(x,1), gel(x,2), y);
    2072                 :            :       }
    2073                 :            :       /* error if ty == t_SER */
    2074                 :     195265 :       av = avma; y = gmod(y, gel(x,1));
    2075                 :     195258 :       return gerepileupto(av, mul_polmod_same(gel(x,1), gel(x,2), y));
    2076                 :            :     }
    2077                 :   57359304 :     return mul_scal(y, x, ty);
    2078                 :            :   }
    2079                 :            : 
    2080                 :            :   /* x and y are not scalars, nor matvec */
    2081                 :    2835576 :   vx = gvar(x);
    2082                 :    2835576 :   vy = gvar(y);
    2083         [ +  + ]:    2835576 :   if (vx != vy) /* x or y is treated as a scalar */
    2084                 :    2828050 :     return (varncmp(vx, vy) < 0)? mul_scal(x, y, tx)
    2085         [ +  + ]:    1414025 :                                 : mul_scal(y, x, ty);
    2086                 :            :   /* vx = vy */
    2087      [ +  -  - ]:    1421551 :   switch(tx)
    2088                 :            :   {
    2089                 :            :     case t_POL:
    2090      [ +  +  - ]:    1421551 :       switch (ty)
    2091                 :            :       {
    2092                 :            :         case t_SER:
    2093                 :            :         {
    2094                 :            :           long vn;
    2095         [ -  + ]:      78673 :           if (lg(x) == 2) return zeropol(vx);
    2096         [ +  + ]:      78673 :           if (lg(y) == 2) return zeroser(vx, valp(y)+RgX_val(x));
    2097                 :      78463 :           av = avma;
    2098                 :      78463 :           vn = RgX_valrem(x, &x);
    2099                 :            :           /* take advantage of x = t^n ! */
    2100         [ +  + ]:      78463 :           if (degpol(x)) {
    2101                 :       2401 :             p1 = RgX_to_ser(x,lg(y));
    2102         [ -  + ]:       2401 :             if (vn) settyp(x, t_VECSMALL); /* *new* x left on stack */
    2103                 :       2401 :             p2 = gmul(p1,y);
    2104                 :       2401 :             settyp(p1, t_VECSMALL); /* p1 left on stack */
    2105                 :            :           } else {
    2106                 :      76062 :             avma = av;
    2107                 :      76062 :             p2 = mul_ser_scal(y, gel(x,2));
    2108                 :            :           }
    2109                 :      78463 :           setvalp(p2, valp(p2) + vn);
    2110                 :      78463 :           return p2;
    2111                 :            :         }
    2112                 :            : 
    2113                 :    1342878 :         case t_RFRAC: return mul_rfrac_scal(gel(y,1),gel(y,2), x);
    2114                 :            :       }
    2115                 :          0 :       break;
    2116                 :            : 
    2117                 :            :     case t_SER:
    2118         [ #  # ]:          0 :       switch (ty)
    2119                 :            :       {
    2120                 :            :         case t_RFRAC:
    2121                 :          0 :           av = avma;
    2122                 :          0 :           return gerepileupto(av, gdiv(gmul(gel(y,1),x), gel(y,2)));
    2123                 :            :       }
    2124                 :          0 :       break;
    2125                 :            :   }
    2126                 :          0 :   pari_err_TYPE2("*",x,y);
    2127                 : 2920996846 :   return NULL; /* not reached */
    2128                 :            : }
    2129                 :            : 
    2130                 :            : int
    2131                 :      33495 : ff_poltype(GEN *x, GEN *p, GEN *pol)
    2132                 :            : {
    2133                 :      33495 :   GEN Q, P = *x;
    2134         [ +  + ]:      33495 :   if (!signe(P)) return 0;
    2135 [ +  + ][ +  + ]:      33348 :   if (!RgX_is_FpXQX(P,pol,p) || !*p || !*pol || typ(*pol)!=t_POL)
         [ +  + ][ +  + ]
    2136                 :      33159 :     return 0;
    2137                 :        189 :   Q = RgX_to_FpX(*pol, *p);
    2138                 :        189 :   P = RgX_to_FpXQX(P, Q, *p);
    2139                 :        189 :   *x = ZXX_to_Kronecker(P, degpol(Q));
    2140                 :        189 :   *pol = Q;
    2141                 :      33495 :   return 1;
    2142                 :            : }
    2143                 :            : 
    2144                 :            : /* return a non-normalized result */
    2145                 :            : GEN
    2146                 :       9373 : sqr_ser_part(GEN x, long l1, long l2)
    2147                 :            : {
    2148                 :            :   long i, j, l;
    2149                 :            :   pari_sp av;
    2150                 :            :   GEN Z, z, p1, p2;
    2151                 :            :   long mi;
    2152         [ +  + ]:       9373 :   if (l2 < l1) return zeroser(varn(x), 2*valp(x));
    2153                 :       9366 :   p2 = cgetg(l2+2, t_VECSMALL)+1; /* left on stack on exit */
    2154                 :       9366 :   Z = cgetg(l2-l1+3, t_SER);
    2155                 :       9366 :   Z[1] = evalvalp(2*valp(x)) | evalvarn(varn(x));
    2156                 :       9366 :   z = Z + 2-l1;
    2157                 :       9366 :   x += 2; mi = 0;
    2158         [ +  + ]:      31269 :   for (i=0; i<l1; i++)
    2159                 :            :   {
    2160         [ +  + ]:      21903 :     p2[i] = !isrationalzero(gel(x,i)); if (p2[i]) mi = i;
    2161                 :            :   }
    2162                 :            : 
    2163         [ +  + ]:      56686 :   for (i=l1; i<=l2; i++)
    2164                 :            :   {
    2165         [ +  + ]:      47320 :     p2[i] = !isrationalzero(gel(x,i)); if (p2[i]) mi = i;
    2166                 :      47320 :     p1=gen_0; av=avma; l=((i+1)>>1) - 1;
    2167         [ +  + ]:     404579 :     for (j=i-mi; j<=minss(l,mi); j++)
    2168 [ +  + ][ +  + ]:     357259 :       if (p2[j] && p2[i-j]) p1 = gadd(p1, gmul(gel(x,j),gel(x,i-j)));
    2169                 :      47320 :     p1 = gshift(p1,1);
    2170 [ +  + ][ +  + ]:      47320 :     if ((i&1) == 0 && p2[i>>1])
    2171                 :      16093 :       p1 = gadd(p1, gsqr(gel(x,i>>1)));
    2172                 :      47320 :     gel(z,i) = gerepileupto(av,p1);
    2173                 :            :   }
    2174                 :       9373 :   return Z;
    2175                 :            : }
    2176                 :            : 
    2177                 :            : GEN
    2178                 :  884728569 : gsqr(GEN x)
    2179                 :            : {
    2180                 :            :   long i, lx;
    2181                 :            :   pari_sp av, tetpil;
    2182                 :            :   GEN z, p1, p2, p3, p4;
    2183                 :            : 
    2184   [ +  +  +  +  :  884728569 :   switch(typ(x))
          +  +  +  +  +  
          +  +  +  +  +  
                +  +  - ]
    2185                 :            :   {
    2186                 :  853943068 :     case t_INT: return sqri(x);
    2187                 :   17217517 :     case t_REAL: return sqrr(x);
    2188                 :     144153 :     case t_INTMOD: { GEN X = gel(x,1);
    2189                 :     144153 :       z = cgetg(3,t_INTMOD);
    2190                 :     144151 :       gel(z,2) = gerepileuptoint((pari_sp)z, remii(sqri(gel(x,2)), X));
    2191                 :     144163 :       gel(z,1) = icopy(X); return z;
    2192                 :            :     }
    2193                 :     161926 :     case t_FRAC: return sqrfrac(x);
    2194                 :            : 
    2195                 :            :     case t_COMPLEX:
    2196         [ +  + ]:    2976426 :       if (isintzero(gel(x,1))) {
    2197                 :      18664 :         av = avma;
    2198                 :      18664 :         return gerepileupto(av, gneg(gsqr(gel(x,2))));
    2199                 :            :       }
    2200                 :    2957762 :       z = cgetg(3,t_COMPLEX); av = avma;
    2201                 :    2957762 :       p1 = gadd(gel(x,1),gel(x,2));
    2202                 :    2957762 :       p2 = gsub(gel(x,1), gel(x,2));
    2203                 :    2957762 :       p3 = gmul(gel(x,1),gel(x,2));
    2204                 :    2957762 :       tetpil = avma;
    2205                 :    2957762 :       gel(z,1) = gmul(p1,p2);
    2206                 :    2957762 :       gel(z,2) = gshift(p3,1); gerepilecoeffssp(av,tetpil,z+1,2); return z;
    2207                 :            : 
    2208                 :            :     case t_PADIC:
    2209                 :       7833 :       z = cgetg(5,t_PADIC);
    2210 [ +  + ][ +  - ]:       7833 :       i = (equaliu(gel(x,2), 2) && signe(gel(x,4)))? 1: 0;
    2211 [ +  + ][ +  + ]:       7833 :       if (i && precp(x) == 1) i = 2; /* (1 + O(2))^2 = 1 + O(2^3) */
    2212                 :       7833 :       z[1] = evalprecp(precp(x)+i) | evalvalp(valp(x)*2);
    2213                 :       7833 :       gel(z,2) = icopy(gel(x,2));
    2214                 :       7833 :       gel(z,3) = shifti(gel(x,3), i); av = avma;
    2215                 :       7833 :       gel(z,4) = gerepileuptoint(av, remii(sqri(gel(x,4)), gel(z,3)));
    2216                 :       7833 :       return z;
    2217                 :            : 
    2218                 :         28 :     case t_QUAD: z = cgetg(4,t_QUAD);
    2219                 :         28 :       p1 = gel(x,1);
    2220                 :         28 :       gel(z,1) = ZX_copy(p1); av = avma;
    2221                 :         28 :       p2 = gsqr(gel(x,2));
    2222                 :         28 :       p3 = gsqr(gel(x,3));
    2223                 :         28 :       p4 = gmul(gneg_i(gel(p1,2)),p3);
    2224                 :            : 
    2225         [ +  + ]:         28 :       if (gequal0(gel(p1,3)))
    2226                 :            :       {
    2227                 :          7 :         tetpil = avma;
    2228                 :          7 :         gel(z,2) = gerepile(av,tetpil,gadd(p4,p2));
    2229                 :          7 :         av = avma;
    2230                 :          7 :         p2 = gmul(gel(x,2),gel(x,3)); tetpil = avma;
    2231                 :          7 :         gel(z,3) = gerepile(av,tetpil,gmul2n(p2,1)); return z;
    2232                 :            :       }
    2233                 :            : 
    2234                 :         21 :       p1 = gmul2n(gmul(gel(x,2),gel(x,3)), 1);
    2235                 :         21 :       tetpil = avma;
    2236                 :         21 :       gel(z,2) = gadd(p2,p4);
    2237                 :         21 :       gel(z,3) = gadd(p1,p3);
    2238                 :         21 :       gerepilecoeffssp(av,tetpil,z+2,2); return z;
    2239                 :            : 
    2240                 :            :     case t_POLMOD:
    2241                 :      23677 :       return sqr_polmod(gel(x,1), gel(x,2));
    2242                 :            : 
    2243                 :    2621515 :     case t_FFELT: return FF_sqr(x);
    2244                 :            : 
    2245                 :            :     case t_POL:
    2246                 :            :     {
    2247                 :    1802362 :       GEN a = x, p = NULL, pol = NULL;
    2248                 :    1802362 :       av = avma;
    2249         [ +  + ]:    1802362 :       if (RgX_is_ZX(x)) return ZX_sqr(x);
    2250         [ +  + ]:      33495 :       if (ff_poltype(&x,&p,&pol))
    2251                 :            :       {
    2252                 :        189 :         z = ZX_sqr(x);
    2253         [ +  - ]:        189 :         if (p) z = FpX_to_mod(z,p);
    2254         [ +  - ]:        189 :         if (pol) z = Kronecker_to_mod(z,pol);
    2255                 :        189 :         z = gerepileupto(av, z);
    2256                 :            :       }
    2257                 :      33306 :       else { avma = av; z = RgX_sqr(a); }
    2258                 :    1802169 :       return z;
    2259                 :            :     }
    2260                 :            : 
    2261                 :            :     case t_SER:
    2262                 :       6342 :       lx = lg(x);
    2263         [ +  + ]:       6342 :       if (ser_isexactzero(x)) {
    2264                 :          7 :         GEN z = gcopy(x);
    2265                 :          7 :         setvalp(z, 2*valp(x));
    2266                 :          7 :         return z;
    2267                 :            :       }
    2268         [ +  + ]:       6335 :       if (lx < 40)
    2269                 :       6174 :         return normalize( sqr_ser_part(x, 0, lx-3) );
    2270                 :            :       else
    2271                 :            :       {
    2272                 :        161 :         pari_sp av = avma;
    2273                 :        161 :         GEN z = cgetg(lx,t_SER), p = NULL;
    2274                 :        161 :         z[1] = evalvalp(2*valp(x)) | evalvarn(varn(x)) | evalsigne(1);
    2275                 :        161 :         x = ser2pol_i(x,lx);
    2276         [ +  + ]:        161 :         if (RgX_is_FpX(x,&p))
    2277                 :            :         {
    2278         [ +  - ]:         63 :           if (!p) x = ZX_sqr(x);
    2279                 :            :           else
    2280                 :            :           {
    2281                 :          0 :             x = RgX_to_FpX(x, p);
    2282                 :          0 :             x = FpX_to_mod(ZX_sqr(x), p);
    2283                 :            :           }
    2284                 :            :         }
    2285                 :            :         else
    2286                 :         98 :           x = RgXn_sqr(x, lx-2);
    2287                 :        161 :         z = fill_ser(z, x);
    2288                 :        161 :         return gerepilecopy(av, z);
    2289                 :            :       }
    2290                 :            : 
    2291                 :          7 :     case t_RFRAC: z = cgetg(3,t_RFRAC);
    2292                 :          7 :       gel(z,1) = gsqr(gel(x,1));
    2293                 :          7 :       gel(z,2) = gsqr(gel(x,2)); return z;
    2294                 :            : 
    2295                 :        511 :     case t_MAT: return RgM_sqr(x);
    2296                 :         14 :     case t_QFR: return qfrsqr(x);
    2297                 :    5819732 :     case t_QFI: return qfisqr(x);
    2298                 :            :     case t_VECSMALL:
    2299                 :       3458 :       z = cgetg_copy(x, &lx);
    2300         [ +  + ]:      56392 :       for (i=1; i<lx; i++)
    2301                 :            :       {
    2302                 :      52934 :         long xi = x[i];
    2303 [ +  - ][ -  + ]:      52934 :         if (xi < 1 || xi >= lx) pari_err_TYPE2("*",x,x);
    2304                 :      52934 :         z[i] = x[xi];
    2305                 :            :       }
    2306                 :       3458 :       return z;
    2307                 :            :   }
    2308                 :          0 :   pari_err_TYPE2("*",x,x);
    2309                 :  884726670 :   return NULL; /* not reached */
    2310                 :            : }
    2311                 :            : 
    2312                 :            : /********************************************************************/
    2313                 :            : /**                                                                **/
    2314                 :            : /**                           DIVISION                             **/
    2315                 :            : /**                                                                **/
    2316                 :            : /********************************************************************/
    2317                 :            : static GEN
    2318                 :     270646 : div_rfrac_scal(GEN x, GEN y)
    2319                 :            : {
    2320                 :     270646 :   pari_sp av = avma;
    2321                 :     270646 :   GEN d = rfrac_denom_mul_scal(gel(x,2), y);
    2322                 :     270646 :   return gerepileupto(av, gred_rfrac_simple(gel(x,1), d));
    2323                 :            : }
    2324                 :            : static GEN
    2325                 :    1004057 : div_scal_rfrac(GEN x, GEN y)
    2326                 :            : {
    2327                 :    1004057 :   GEN y1 = gel(y,1), y2 = gel(y,2);
    2328                 :    1004057 :   pari_sp av = avma;
    2329 [ +  + ][ -  + ]:    1004057 :   if (typ(y1) == t_POL && varn(y2) == varn(y1))
    2330                 :            :   {
    2331         [ #  # ]:          0 :     if (degpol(y1)) return gerepileupto(av, gred_rfrac_simple(gmul(x, y2), y1));
    2332                 :          0 :     y1 = gel(y1,2);
    2333                 :            :   }
    2334                 :    1004057 :   return RgX_Rg_mul(y2, gdiv(x,y1));
    2335                 :            : }
    2336                 :            : static GEN
    2337                 :    1186329 : div_rfrac(GEN x, GEN y)
    2338                 :    1186329 : { return mul_rfrac(gel(x,1),gel(x,2), gel(y,2),gel(y,1)); }
    2339                 :            : 
    2340                 :            : static GEN
    2341                 :     453960 : div_ser_scal(GEN x, GEN y) {
    2342                 :            :   long i, lx;
    2343                 :            :   GEN z;
    2344         [ +  + ]:     453960 :   if (ser_isexactzero(x))
    2345                 :            :   {
    2346         [ +  - ]:          7 :     if (lg(x) == 2) return gcopy(x);
    2347                 :          0 :     return scalarser(gdiv(gel(x,2), y), varn(x), valp(x));
    2348                 :            :   }
    2349                 :     453953 :   z = cgetg_copy(x, &lx); z[1] = x[1];
    2350         [ +  + ]:    2076094 :   for (i=2; i<lx; i++) gel(z,i) = gdiv(gel(x,i),y);
    2351                 :     453960 :   return normalize(z);
    2352                 :            : }
    2353                 :            : GEN
    2354                 :        133 : ser_normalize(GEN x)
    2355                 :            : {
    2356                 :        133 :   long i, lx = lg(x);
    2357                 :            :   GEN c, z;
    2358         [ -  + ]:        133 :   if (lx == 2) return x;
    2359         [ +  + ]:        133 :   c = gel(x,2); if (gequal1(c)) return x;
    2360                 :        105 :   z = cgetg(lx, t_SER); z[1] = x[1]; gel(z,2) = gen_1;
    2361         [ +  + ]:       1190 :   for (i=3; i<lx; i++) gel(z,i) = gdiv(gel(x,i),c);
    2362                 :        133 :   return z;
    2363                 :            : }
    2364                 :            : 
    2365                 :            : static GEN
    2366                 :    1292020 : div_T_scal(GEN x, GEN y, long tx) {
    2367   [ +  +  +  - ]:    1292020 :   switch(tx)
    2368                 :            :   {
    2369                 :     571138 :     case t_POL: return RgX_Rg_div(x, y);
    2370                 :     453960 :     case t_SER: return div_ser_scal(x, y);
    2371                 :     266922 :     case t_RFRAC: return div_rfrac_scal(x,y);
    2372                 :            :   }
    2373                 :          0 :   pari_err_TYPE2("/",x,y);
    2374                 :    1292020 :   return NULL; /* not reached */
    2375                 :            : }
    2376                 :            : 
    2377                 :            : static GEN
    2378                 :    8184454 : div_scal_pol(GEN x, GEN y) {
    2379                 :    8184454 :   long ly = lg(y);
    2380                 :            :   pari_sp av;
    2381         [ +  + ]:    8184454 :   if (ly == 3) return scalarpol(gdiv(x,gel(y,2)), varn(y));
    2382         [ +  + ]:    8151622 :   if (isrationalzero(x)) return zeropol(varn(y));
    2383                 :    6099671 :   av = avma;
    2384                 :    8184454 :   return gerepileupto(av, gred_rfrac_simple(x,y));
    2385                 :            : }
    2386                 :            : static GEN
    2387                 :       9331 : div_scal_ser(GEN x, GEN y) { /* TODO: improve */
    2388                 :            :   GEN z;
    2389                 :            :   long ly, i;
    2390         [ -  + ]:       9331 :   if (gequal0(x)) { pari_sp av=avma; return gerepileupto(av, gmul(x, ginv(y))); }
    2391                 :       9331 :   ly = lg(y); z = (GEN)pari_malloc(ly*sizeof(long));
    2392                 :       9331 :   z[0] = evaltyp(t_SER) | evallg(ly);
    2393                 :       9331 :   z[1] = evalsigne(1) | _evalvalp(0) | evalvarn(varn(y));
    2394         [ +  + ]:      61922 :   gel(z,2) = x; for (i=3; i<ly; i++) gel(z,i) = gen_0;
    2395                 :       9331 :   y = gdiv(z,y); pari_free(z); return y;
    2396                 :            : }
    2397                 :            : static GEN
    2398                 :    9147995 : div_scal_T(GEN x, GEN y, long ty) {
    2399   [ +  +  +  - ]:    9147995 :   switch(ty)
    2400                 :            :   {
    2401                 :    8135363 :     case t_POL: return div_scal_pol(x, y);
    2402                 :       9331 :     case t_SER: return div_scal_ser(x, y);
    2403                 :    1003301 :     case t_RFRAC: return div_scal_rfrac(x, y);
    2404                 :            :   }
    2405                 :          0 :   pari_err_TYPE2("/",x,y);
    2406                 :    9147995 :   return NULL; /* not reached */
    2407                 :            : }
    2408                 :            : 
    2409                 :            : /* assume tx = ty = t_SER, same variable vx */
    2410                 :            : static GEN
    2411                 :     691648 : div_ser(GEN x, GEN y, long vx)
    2412                 :            : {
    2413                 :     691648 :   long i, j, l = valp(x) - valp(y), lx = lg(x), ly = lg(y);
    2414                 :            :   GEN y_lead, p1, p2, z;
    2415                 :            : 
    2416         [ +  + ]:     691648 :   if (!signe(y)) pari_err_INV("div_ser", y);
    2417         [ +  + ]:     691641 :   if (ser_isexactzero(x))
    2418                 :            :   {
    2419         [ +  + ]:        644 :     if (lx == 2) return zeroser(vx, l);
    2420                 :          7 :     return scalarser(gmul(gel(x,2),RgX_get_0(y)), varn(x), l);
    2421                 :            :   }
    2422                 :     690997 :   y_lead = gel(y,2);
    2423         [ -  + ]:     690997 :   if (gequal0(y_lead)) /* normalize denominator if leading term is 0 */
    2424                 :            :   {
    2425                 :          0 :     pari_warn(warner,"normalizing a series with 0 leading term");
    2426         [ #  # ]:          0 :     for (l--, ly--,y++; ly > 2; l--, ly--, y++)
    2427                 :            :     {
    2428                 :          0 :       y_lead = gel(y,2);
    2429         [ #  # ]:          0 :       if (!gequal0(y_lead)) break;
    2430                 :            :     }
    2431         [ #  # ]:          0 :     if (ly <= 2) pari_err_INV("div_ser", y);
    2432                 :            :   }
    2433         [ +  + ]:     690997 :   if (ly < lx) lx = ly;
    2434                 :     690997 :   p2 = cgetg(lx, t_VECSMALL); /* left on stack for efficiency */
    2435         [ +  + ]:    2167827 :   for (i=3; i<lx; i++)
    2436                 :            :   {
    2437                 :    1476830 :     p1 = gel(y,i);
    2438         [ +  + ]:    1476830 :     if (isrationalzero(p1)) p1 = NULL;
    2439                 :    1476830 :     gel(p2,i) = p1;
    2440                 :            :   }
    2441                 :     690997 :   z = cgetg(lx,t_SER);
    2442                 :     690997 :   z[1] = evalvalp(l) | evalvarn(vx) | evalsigne(1);
    2443                 :     690997 :   gel(z,2) = gdiv(gel(x,2), y_lead);
    2444         [ +  + ]:    2167827 :   for (i=3; i<lx; i++)
    2445                 :            :   {
    2446                 :    1476830 :     pari_sp av = avma;
    2447                 :    1476830 :     p1 = gel(x,i);
    2448         [ +  + ]:   10567414 :     for (j=2, l=i; j<i; j++, l--)
    2449         [ +  + ]:    9090584 :       if (p2[l]) p1 = gsub(p1, gmul(gel(z,j), gel(p2,l)));
    2450                 :    1476830 :     gel(z,i) = gerepileupto(av, gdiv(p1, y_lead));
    2451                 :            :   }
    2452                 :     691641 :   return normalize(z);
    2453                 :            : }
    2454                 :            : /* x,y compatible PADIC */
    2455                 :            : static GEN
    2456                 :      92297 : divpp(GEN x, GEN y) {
    2457                 :            :   pari_sp av;
    2458                 :            :   long a, b;
    2459                 :            :   GEN z, M;
    2460                 :            : 
    2461         [ +  + ]:      92297 :   if (!signe(gel(y,4))) pari_err_INV("divpp",y);
    2462         [ +  + ]:      92294 :   if (!signe(gel(x,4))) return zeropadic(gel(x,2), valp(x)-valp(y));
    2463                 :      92287 :   a = precp(x);
    2464         [ +  + ]:      92287 :   b = precp(y); if (a > b) { M = gel(y,3); } else { M = gel(x,3); b = a; }
    2465                 :      92287 :   z = cgetg(5, t_PADIC);
    2466                 :      92291 :   z[1] = _evalprecp(b) | evalvalp(valp(x) - valp(y));
    2467                 :      92292 :   gel(z,2) = icopy(gel(x,2));
    2468                 :      92292 :   gel(z,3) = icopy(M); av = avma;
    2469                 :      92292 :   gel(z,4) = gerepileuptoint(av, remii(mulii(gel(x,4), Fp_inv(gel(y,4), M)), M) );
    2470                 :      92298 :   return z;
    2471                 :            : }
    2472                 :            : static GEN
    2473                 :      34146 : div_polmod_same(GEN T, GEN x, GEN y)
    2474                 :            : {
    2475                 :      34146 :   long v = varn(T);
    2476                 :      34146 :   GEN a, z = cgetg(3, t_POLMOD);
    2477                 :      34146 :   gel(z,1) = RgX_copy(T);
    2478 [ +  + ][ +  - ]:      34146 :   if (typ(y) != t_POL || varn(y) != v || lg(y) <= 3)
                 [ +  + ]
    2479                 :      27104 :     a = gdiv(x, y);
    2480 [ +  + ][ +  - ]:       7042 :   else if (typ(x) != t_POL || varn(x) != v || lg(x) <= 3)
                 [ +  + ]
    2481                 :       4543 :   {
    2482                 :       4543 :     pari_sp av = avma;
    2483                 :       4543 :     a = gerepileupto(av, gmul(x, RgXQ_inv(y, T)));
    2484                 :            :   }
    2485 [ +  + ][ +  + ]:       2499 :   else if (degpol(T) == 2 && isint1(gel(T,4))) /* quadratic fields */
    2486                 :       2051 :   {
    2487                 :       2051 :     pari_sp av = avma;
    2488                 :       2051 :     a = quad_polmod_mul(T, x, quad_polmod_conj(y, T));
    2489                 :       2051 :     a = RgX_Rg_div(a, quad_polmod_norm(y, T));
    2490                 :       2051 :     a = gerepileupto(av, a);
    2491                 :            :   }
    2492                 :            :   else
    2493                 :            :   {
    2494                 :        448 :     pari_sp av = avma;
    2495                 :        448 :     GEN p = NULL;
    2496 [ +  - ][ +  + ]:        448 :     if (RgX_is_FpX(T, &p) && RgX_is_FpX(x, &p) && RgX_is_FpX(y, &p) && p)
         [ +  + ][ +  + ]
    2497                 :            :     {
    2498                 :         14 :       T = RgX_to_FpX(T, p); x = RgX_to_FpX(x, p); y = RgX_to_FpX(y, p);
    2499         [ +  + ]:         14 :       if (lgefint(p) == 3)
    2500                 :            :       {
    2501                 :          7 :         ulong pp = p[2];
    2502                 :          7 :         x = ZX_to_Flx(x, pp);
    2503                 :          7 :         y = ZX_to_Flx(y, pp);
    2504                 :          7 :         T = ZX_to_Flx(T, pp);
    2505                 :          7 :         a = Flxq_mul(x, Flxq_inv(y,T,pp),T,pp);
    2506                 :          7 :         a = Flx_to_ZX(a);
    2507                 :            :       }
    2508                 :            :       else
    2509                 :          7 :         a = FpXQ_div(x, y, T, p);
    2510                 :         14 :       a = FpX_to_mod(a, p);
    2511                 :            :     } else
    2512                 :        434 :       a = RgXQ_mul(x, ginvmod(y, gel(z,1)), gel(z,1));
    2513                 :        448 :     a = gerepileupto(av, a);
    2514                 :            :   }
    2515                 :      34146 :   gel(z,2) = a; return z;
    2516                 :            : }
    2517                 :            : GEN
    2518                 :  132423243 : gdiv(GEN x, GEN y)
    2519                 :            : {
    2520                 :  132423243 :   long tx = typ(x), ty = typ(y), lx, ly, vx, vy, i;
    2521                 :            :   pari_sp av, tetpil;
    2522                 :            :   GEN z, p1, p2;
    2523                 :            : 
    2524 [ +  + ][ +  +  :  132423243 :   if (tx == ty) switch(tx)
          +  +  +  +  +  
          +  +  +  +  +  
             -  -  +  - ]
    2525                 :            :   {
    2526                 :            :     case t_INT:
    2527 [ +  + ][ +  + ]:   58581108 :       if (is_pm1(y)) return (signe(y) < 0)? negi(x): icopy(x);
    2528         [ +  + ]:   22397203 :       if (is_pm1(x)) {
    2529                 :    4788386 :         long s = signe(y);
    2530         [ +  + ]:    4788386 :         if (!s) pari_err_INV("gdiv",y);
    2531         [ +  + ]:    4788309 :         if (signe(x) < 0) s = -s;
    2532                 :    4788309 :         z = cgetg(3, t_FRAC);
    2533         [ +  + ]:    4788309 :         gel(z,1) = s<0? gen_m1: gen_1;
    2534                 :    4788309 :         gel(z,2) = absi(y); return z;
    2535                 :            :       }
    2536                 :   17608817 :       return gred_frac2(x,y);
    2537                 :            : 
    2538                 :   27903785 :     case t_REAL: return divrr(x,y);
    2539                 :      21280 :     case t_INTMOD: { GEN X = gel(x,1), Y = gel(y,1);
    2540                 :      21280 :       z = cgetg(3,t_INTMOD);
    2541 [ +  + ][ +  + ]:      21278 :       if (X==Y || equalii(X,Y))
    2542                 :      21271 :         return div_intmod_same(z, X, gel(x,2), gel(y,2));
    2543                 :          7 :       gel(z,1) = gcdii(X,Y);
    2544                 :          7 :       warn_coercion(X,Y,gel(z,1));
    2545                 :          7 :       av = avma; p1 = mulii(gel(x,2), Fp_inv(gel(y,2), gel(z,1)));
    2546                 :          7 :       gel(z,2) = gerepileuptoint(av, remii(p1, gel(z,1))); return z;
    2547                 :            :     }
    2548                 :            :     case t_FRAC: {
    2549                 :     503757 :       GEN x1 = gel(x,1), x2 = gel(x,2);
    2550                 :     503757 :       GEN y1 = gel(y,1), y2 = gel(y,2);
    2551                 :     503757 :       z = cgetg(3, t_FRAC);
    2552                 :     503757 :       p1 = gcdii(x1, y1);
    2553         [ +  + ]:     503757 :       if (!is_pm1(p1)) { x1 = diviiexact(x1,p1); y1 = diviiexact(y1,p1); }
    2554                 :     503757 :       p1 = gcdii(x2, y2);
    2555         [ +  + ]:     503757 :       if (!is_pm1(p1)) { x2 = diviiexact(x2,p1); y2 = diviiexact(y2,p1); }
    2556                 :     503757 :       tetpil = avma;
    2557                 :     503757 :       gel(z,2) = mulii(x2,y1);
    2558                 :     503757 :       gel(z,1) = mulii(x1,y2);
    2559                 :     503757 :       normalize_frac(z);
    2560         [ +  + ]:     503757 :       fix_frac_if_int_GC(z,tetpil);
    2561                 :     503757 :       return z;
    2562                 :            :     }
    2563                 :            :     case t_COMPLEX:
    2564         [ +  + ]:    1524199 :       if (isintzero(gel(y,1)))
    2565                 :            :       {
    2566                 :       8197 :         y = gel(y,2);
    2567         [ +  + ]:       8197 :         if (isintzero(gel(x,1))) return gdiv(gel(x,2), y);
    2568                 :       8141 :         z = cgetg(3,t_COMPLEX);
    2569                 :       8141 :         gel(z,1) = gdiv(gel(x,2), y);
    2570                 :       8141 :         av = avma;
    2571                 :       8141 :         gel(z,2) = gerepileupto(av, gneg(gdiv(gel(x,1), y)));
    2572                 :       8141 :         return z;
    2573                 :            :       }
    2574                 :    1516002 :       av = avma; p1 = cxnorm(y); p2 = mulcc(x, gconj(y)); tetpil = avma;
    2575                 :    1516002 :       return gerepile(av, tetpil, gdiv(p2,p1));
    2576                 :            : 
    2577                 :            :     case t_PADIC:
    2578         [ -  + ]:       9198 :       if (!equalii(gel(x,2),gel(y,2))) pari_err_OP("/",x,y);
    2579                 :       9198 :       return divpp(x, y);
    2580                 :            : 
    2581                 :            :     case t_QUAD:
    2582         [ -  + ]:        322 :       if (!ZX_equal(gel(x,1),gel(y,1))) pari_err_OP("/",x,y);
    2583                 :        322 :       av = avma; p1 = quadnorm(y); p2 = mulqq(x, gconj(y)); tetpil = avma;
    2584                 :        322 :       return gerepile(av, tetpil, gdiv(p2,p1));
    2585                 :            : 
    2586                 :      74844 :     case t_FFELT: return FF_div(x,y);
    2587                 :            : 
    2588                 :            :     case t_POLMOD:
    2589         [ +  + ]:      34153 :       if (RgX_equal_var(gel(x,1), gel(y,1)))
    2590                 :      34146 :         z = div_polmod_same(gel(x,1), gel(x,2), gel(y,2));
    2591                 :            :       else {
    2592                 :          7 :         av = avma;
    2593                 :          7 :         z = gerepileupto(av, gmul(x, ginv(y)));
    2594                 :            :       }
    2595                 :      34153 :       return z;
    2596                 :            : 
    2597                 :            :     case t_POL:
    2598                 :   18386096 :       vx = varn(x);
    2599                 :   18386096 :       vy = varn(y);
    2600         [ +  + ]:   18386096 :       if (vx != vy) {
    2601         [ +  + ]:      98154 :         if (varncmp(vx, vy) < 0) return RgX_Rg_div(x, y);
    2602                 :      49091 :                             else return div_scal_pol(x, y);
    2603                 :            :       }
    2604         [ -  + ]:   18287942 :       if (!signe(y)) pari_err_INV("gdiv",y);
    2605         [ +  + ]:   18287942 :       if (lg(y) == 3) return RgX_Rg_div(x,gel(y,2));
    2606                 :   18174411 :       return gred_rfrac2(x,y);
    2607                 :            : 
    2608                 :            :     case t_SER:
    2609                 :     352364 :       vx = varn(x);
    2610                 :     352364 :       vy = varn(y);
    2611         [ -  + ]:     352364 :       if (vx != vy) {
    2612         [ #  # ]:          0 :         if (varncmp(vx, vy) < 0) return div_ser_scal(x, y);
    2613                 :          0 :                             else return div_scal_ser(x, y);
    2614                 :            :       }
    2615                 :     352364 :       return div_ser(x, y, vx);
    2616                 :            :     case t_RFRAC:
    2617                 :    1190809 :       vx = varn(gel(x,2));
    2618                 :    1190809 :       vy = varn(gel(y,2));
    2619         [ +  + ]:    1190809 :       if (vx != vy) {
    2620         [ +  + ]:       4480 :         if (varncmp(vx, vy) < 0) return div_rfrac_scal(x, y);
    2621                 :        756 :                             else return div_scal_rfrac(x, y);
    2622                 :            :       }
    2623                 :    1186329 :       return div_rfrac(x,y);
    2624                 :            : 
    2625                 :          0 :     case t_QFI: av = avma; return gerepileupto(av, qficomp(x, ginv(y)));
    2626                 :          0 :     case t_QFR: av = avma; return gerepileupto(av, qfrcomp(x, ginv(y)));
    2627                 :            : 
    2628                 :            :     case t_MAT:
    2629                 :         14 :       av = avma; p1 = RgM_inv(y);
    2630         [ -  + ]:         14 :       if (!p1) pari_err_INV("gdiv",y);
    2631                 :         14 :       return gerepileupto(av, RgM_mul(x, p1));
    2632                 :            : 
    2633                 :          0 :     default: pari_err_TYPE2("/",x,y);
    2634                 :            :   }
    2635                 :            : 
    2636 [ +  + ][ +  + ]:   23841315 :   if (tx==t_INT && is_const_t(ty)) /* optimized for speed */
    2637                 :            :   {
    2638                 :     435762 :     long s = signe(x);
    2639         [ +  + ]:     435762 :     if (!s) {
    2640         [ -  + ]:      44210 :       if (gequal0(y)) pari_err_INV("gdiv",y);
    2641      [ +  +  + ]:      44210 :       switch (ty)
    2642                 :            :       {
    2643                 :      41067 :       default: return gen_0;
    2644                 :            :       case t_INTMOD:
    2645                 :         14 :         z = cgetg(3,t_INTMOD);
    2646                 :         14 :         gel(z,1) = icopy(gel(y,1));
    2647                 :         14 :         gel(z,2) = gen_0; return z;
    2648                 :       3129 :       case t_FFELT: return FF_zero(y);
    2649                 :            :       }
    2650                 :            :     }
    2651         [ +  + ]:     391552 :     if (is_pm1(x)) {
    2652         [ +  + ]:     291735 :       if (s > 0) return ginv(y);
    2653                 :      27187 :       av = avma; return gerepileupto(av, ginv(gneg(y)));
    2654                 :            :     }
    2655   [ +  +  +  +  :      99817 :     switch(ty)
             +  +  +  - ]
    2656                 :            :     {
    2657                 :      32317 :       case t_REAL: return divir(x,y);
    2658                 :            :       case t_INTMOD:
    2659                 :         42 :         z = cgetg(3, t_INTMOD);
    2660                 :         42 :         return div_intmod_same(z, gel(y,1), modii(x, gel(y,1)), gel(y,2));
    2661                 :            :       case t_FRAC:
    2662                 :      45441 :         z = cgetg(3,t_FRAC); p1 = gcdii(x,gel(y,1));
    2663         [ +  + ]:      45441 :         if (is_pm1(p1))
    2664                 :            :         {
    2665                 :      37847 :           avma = (pari_sp)z;
    2666                 :      37847 :           gel(z,2) = icopy(gel(y,1));
    2667                 :      37847 :           gel(z,1) = mulii(gel(y,2), x);
    2668                 :      37847 :           normalize_frac(z);
    2669         [ +  + ]:      37847 :           fix_frac_if_int(z);
    2670                 :            :         }
    2671                 :            :         else
    2672                 :            :         {
    2673                 :       7594 :           x = diviiexact(x,p1); tetpil = avma;
    2674                 :       7594 :           gel(z,2) = diviiexact(gel(y,1), p1);
    2675                 :       7594 :           gel(z,1) = mulii(gel(y,2), x);
    2676                 :       7594 :           normalize_frac(z);
    2677         [ +  + ]:       7594 :           fix_frac_if_int_GC(z,tetpil);
    2678                 :            :         }
    2679                 :      45441 :         return z;
    2680                 :            : 
    2681                 :        231 :       case t_FFELT: return Z_FF_div(x,y);
    2682                 :      21695 :       case t_COMPLEX: return divRc(x,y);
    2683                 :         49 :       case t_PADIC: return divTp(x, y);
    2684                 :            :       case t_QUAD:
    2685                 :         42 :         av = avma; p1 = quadnorm(y); p2 = mulRq(x, gconj(y)); tetpil = avma;
    2686                 :         42 :         return gerepile(av, tetpil, gdiv(p2,p1));
    2687                 :            :     }
    2688                 :            :   }
    2689         [ +  + ]:   23405553 :   if (gequal0(y))
    2690                 :            :   {
    2691 [ +  + ][ +  + ]:         35 :     if (is_matvec_t(tx) && lg(x) == 1) return gcopy(x);
    2692         [ +  + ]:         14 :     if (ty != t_MAT) pari_err_INV("gdiv",y);
    2693                 :            :   }
    2694                 :            : 
    2695 [ +  + ][ +  + ]:   23405525 :   if (is_const_t(tx) && is_const_t(ty)) switch(tx)
           [ +  +  +  +  
             +  +  +  - ]
    2696                 :            :   {
    2697                 :            :     case t_REAL:
    2698   [ +  +  +  +  :    8972805 :       switch(ty)
                      + ]
    2699                 :            :       {
    2700                 :    7975805 :         case t_INT: return divri(x,y);
    2701                 :            :         case t_FRAC:
    2702                 :     673119 :           av = avma; z = divri(mulri(x,gel(y,2)), gel(y,1));
    2703                 :     673119 :           return gerepileuptoleaf(av, z);
    2704                 :     323853 :         case t_COMPLEX: return divRc(x, y);
    2705                 :          7 :         case t_QUAD: return divfq(x, y, lg(x));
    2706                 :         21 :         default: pari_err_TYPE2("/",x,y);
    2707                 :            :       }
    2708                 :            : 
    2709                 :            :     case t_INTMOD:
    2710   [ +  +  +  -  :        567 :       switch(ty)
             +  +  +  - ]
    2711                 :            :       {
    2712                 :            :         case t_INT:
    2713                 :        434 :           z = cgetg(3, t_INTMOD);
    2714                 :        434 :           return div_intmod_same(z, gel(x,1), gel(x,2), modii(y, gel(x,1)));
    2715                 :         28 :         case t_FRAC: { GEN X = gel(x,1);
    2716                 :         28 :           z = cgetg(3,t_INTMOD); p1 = remii(mulii(gel(y,2), gel(x,2)), X);
    2717                 :         28 :           return div_intmod_same(z, X, p1, modii(gel(y,1), X));
    2718                 :            :         }
    2719                 :            :         case t_FFELT:
    2720         [ -  + ]:         63 :           if (!equalii(gel(x,1),FF_p_i(y)))
    2721                 :          0 :             pari_err_OP("/",x,y);
    2722                 :         63 :           return Z_FF_div(gel(x,2),y);
    2723                 :            : 
    2724                 :            :         case t_COMPLEX:
    2725                 :          0 :           av = avma;
    2726                 :          0 :           return gerepileupto(av, mulRc_direct(gdiv(x,cxnorm(y)), gconj(y)));
    2727                 :            : 
    2728                 :            :         case t_QUAD:
    2729                 :          7 :           av = avma; p1 = quadnorm(y); p2 = gmul(x,gconj(y)); tetpil = avma;
    2730                 :          7 :           return gerepile(av,tetpil, gdiv(p2,p1));
    2731                 :            : 
    2732                 :          7 :         case t_PADIC: { GEN X = gel(x,1);
    2733                 :          7 :           z = cgetg(3, t_INTMOD);
    2734                 :          7 :           return div_intmod_same(z, X, gel(x,2), padic_to_Fp(y, X));
    2735                 :            :         }
    2736                 :         28 :         case t_REAL: pari_err_TYPE2("/",x,y);
    2737                 :            :       }
    2738                 :            : 
    2739                 :            :     case t_FRAC:
    2740   [ +  +  +  +  :     470519 :       switch(ty)
             +  +  +  - ]
    2741                 :            :       {
    2742                 :     437795 :         case t_INT: z = cgetg(3, t_FRAC);
    2743                 :     437795 :         p1 = gcdii(y,gel(x,1));
    2744         [ +  + ]:     437795 :         if (is_pm1(p1))
    2745                 :            :         {
    2746                 :     248521 :           avma = (pari_sp)z; tetpil = 0;
    2747                 :     248521 :           gel(z,1) = icopy(gel(x,1));
    2748                 :            :         }
    2749                 :            :         else
    2750                 :            :         {
    2751                 :     189274 :           y = diviiexact(y,p1); tetpil = avma;
    2752                 :     189274 :           gel(z,1) = diviiexact(gel(x,1), p1);
    2753                 :            :         }
    2754                 :     437795 :         gel(z,2) = mulii(gel(x,2),y);
    2755                 :     437795 :         normalize_frac(z);
    2756 [ +  + ][ -  + ]:     437795 :         if (tetpil) fix_frac_if_int_GC(z,tetpil);
    2757                 :     437795 :         return z;
    2758                 :            : 
    2759                 :            :         case t_REAL:
    2760                 :      32437 :           av=avma; p1=mulri(y,gel(x,2)); tetpil=avma;
    2761                 :      32437 :           return gerepile(av, tetpil, divir(gel(x,1), p1));
    2762                 :            : 
    2763                 :          7 :         case t_INTMOD: { GEN Y = gel(y,1);
    2764                 :          7 :           z = cgetg(3,t_INTMOD); p1 = remii(mulii(gel(y,2),gel(x,2)), Y);
    2765                 :          7 :           return div_intmod_same(z, Y, modii(gel(x,1), Y), p1);
    2766                 :            :         }
    2767                 :            : 
    2768                 :         28 :         case t_FFELT: av=avma;
    2769                 :         28 :           return gerepileupto(av,Z_FF_div(gel(x,1),FF_Z_mul(y,gel(x,2))));
    2770                 :            : 
    2771                 :        231 :         case t_COMPLEX: return divRc(x, y);
    2772                 :            : 
    2773                 :            :         case t_PADIC:
    2774         [ -  + ]:         14 :           if (!signe(gel(x,1))) return gen_0;
    2775                 :         14 :           return divTp(x, y);
    2776                 :            : 
    2777                 :            :         case t_QUAD:
    2778                 :          7 :           av=avma; p1=quadnorm(y); p2=gmul(x,gconj(y)); tetpil=avma;
    2779                 :          7 :           return gerepile(av,tetpil,gdiv(p2,p1));
    2780                 :            :       }
    2781                 :            : 
    2782                 :            :     case t_FFELT:
    2783   [ +  +  +  + ]:       2527 :       switch (ty)
    2784                 :            :       {
    2785                 :       2408 :         case t_INT: return FF_Z_Z_muldiv(x,gen_1,y);
    2786                 :         28 :         case t_FRAC: return FF_Z_Z_muldiv(x,gel(y,2),gel(y,1));
    2787                 :            :         case t_INTMOD:
    2788         [ -  + ]:         49 :           if (!equalii(gel(y,1),FF_p_i(x)))
    2789                 :          0 :             pari_err_OP("/",x,y);
    2790                 :         49 :           return FF_Z_Z_muldiv(x,gen_1,gel(y,2));
    2791                 :            :         default:
    2792                 :         42 :         pari_err_TYPE2("/",x,y);
    2793                 :            :       }
    2794                 :          0 :       break;
    2795                 :            : 
    2796                 :            :     case t_COMPLEX:
    2797   [ +  -  -  -  :    2511626 :       switch(ty)
                      - ]
    2798                 :            :       {
    2799                 :    2511626 :         case t_INT: case t_REAL: case t_FRAC: return divcR(x,y);
    2800                 :          0 :         case t_INTMOD: return mulRc_direct(ginv(y), x);
    2801                 :            :         case t_PADIC:
    2802         [ #  # ]:          0 :           return Zp_nosquare_m1(gel(y,2))? divcR(x,y): divTp(x, y);
    2803                 :            :         case t_QUAD:
    2804         [ #  # ]:          0 :           lx = precision(x); if (!lx) pari_err_OP("/",x,y);
    2805                 :          0 :           return divfq(x, y, lx);
    2806                 :            :       }
    2807                 :            : 
    2808                 :            :     case t_PADIC:
    2809   [ +  +  +  +  :       1281 :       switch(ty)
                      + ]
    2810                 :            :       {
    2811                 :       1232 :         case t_INT: case t_FRAC: { GEN p = gel(x,2);
    2812                 :       1232 :           return signe(gel(x,4))? divpT(x, y)
    2813         [ +  + ]:       1232 :                             : zeropadic(p, valp(x) - Q_pval(y,p));
    2814                 :            :         }
    2815                 :          7 :         case t_INTMOD: { GEN Y = gel(y,1);
    2816                 :          7 :           z = cgetg(3, t_INTMOD);
    2817                 :          7 :           return div_intmod_same(z, Y, padic_to_Fp(x, Y), gel(y,2));
    2818                 :            :         }
    2819                 :            :         case t_COMPLEX: case t_QUAD:
    2820                 :          7 :           av=avma; p1=gmul(x,gconj(y)); p2=gnorm(y); tetpil=avma;
    2821                 :          7 :           return gerepile(av,tetpil,gdiv(p1,p2));
    2822                 :            : 
    2823                 :         28 :         case t_REAL: pari_err_TYPE2("/",x,y);
    2824                 :            :       }
    2825                 :            : 
    2826                 :            :     case t_QUAD:
    2827   [ +  +  +  -  :        889 :       switch (ty)
                      + ]
    2828                 :            :       {
    2829                 :            :         case t_INT: case t_INTMOD: case t_FRAC:
    2830                 :        840 :           z = cgetg(4,t_QUAD);
    2831                 :        840 :           gel(z,1) = ZX_copy(gel(x,1));
    2832                 :        840 :           gel(z,2) = gdiv(gel(x,2), y);
    2833                 :        840 :           gel(z,3) = gdiv(gel(x,3), y); return z;
    2834                 :         28 :         case t_REAL: return divqf(x, y, lg(y));
    2835                 :          7 :         case t_PADIC: return divTp(x, y);
    2836                 :            :         case t_COMPLEX:
    2837         [ #  # ]:          0 :           ly = precision(y); if (!ly) pari_err_OP("/",x,y);
    2838                 :          0 :           return divqf(x, y, ly);
    2839                 :            :       }
    2840                 :            :   }
    2841   [ +  +  -  + ]:   11445332 :   switch(ty) {
    2842                 :            :     case t_REAL: case t_INTMOD: case t_PADIC: case t_POLMOD:
    2843                 :      25432 :       return gmul(x, ginv(y)); /* missing gerepile, for speed */
    2844                 :            :     case t_MAT:
    2845                 :         28 :       av = avma; p1 = RgM_inv(y);
    2846         [ +  + ]:         28 :       if (!p1) pari_err_INV("gdiv",y);
    2847                 :         21 :       return gerepileupto(av, gmul(x, p1));
    2848                 :            :     case t_VEC: case t_COL:
    2849                 :            :     case t_LIST: case t_STR: case t_VECSMALL: case t_CLOSURE:
    2850                 :          0 :       pari_err_TYPE2("/",x,y);
    2851                 :            :   }
    2852      [ +  -  + ]:   11419872 :   switch(tx) {
    2853                 :            :     case t_VEC: case t_COL: case t_MAT:
    2854                 :     296762 :       z = cgetg_copy(x, &lx);
    2855         [ +  + ]:    1188283 :       for (i=1; i<lx; i++) gel(z,i) = gdiv(gel(x,i),y);
    2856                 :     296762 :       return z;
    2857                 :            :     case t_LIST: case t_STR: case t_VECSMALL: case t_CLOSURE:
    2858                 :          0 :       pari_err_TYPE2("/",x,y);
    2859                 :            :   }
    2860                 :            : 
    2861                 :   11123110 :   vy = gvar(y);
    2862         [ +  + ]:   11123110 :   if (tx == t_POLMOD) { GEN X = gel(x,1);
    2863                 :      11270 :     vx = varn(X);
    2864         [ +  + ]:      11270 :     if (vx != vy) {
    2865         [ +  + ]:      11123 :       if (varncmp(vx, vy) > 0) return div_scal_T(x, y, ty);
    2866                 :      10892 :       z = cgetg(3,t_POLMOD);
    2867                 :      10892 :       gel(z,1) = RgX_copy(X);
    2868                 :      10892 :       gel(z,2) = gdiv(gel(x,2), y); return z;
    2869                 :            :     }
    2870                 :            :     /* y is POL, SER or RFRAC */
    2871                 :        147 :     av = avma;
    2872         [ -  + ]:        147 :     switch(ty)
    2873                 :            :     {
    2874                 :          0 :       case t_RFRAC: y = gmod(ginv(y), X); break;
    2875                 :        147 :       default: y = ginvmod(gmod(y,X), X);
    2876                 :            :     }
    2877                 :        140 :     return gerepileupto(av, mul_polmod_same(X, gel(x,2), y));
    2878                 :            :   }
    2879                 :            :   /* x and y are not both is_scalar_t. If one of them is scalar, it's not a
    2880                 :            :    * POLMOD (done already), hence its variable is NO_VARIABLE. If the other has
    2881                 :            :    * variable NO_VARIABLE, then the operation is incorrect */
    2882                 :   11111840 :   vx = gvar(x);
    2883         [ +  + ]:   11111840 :   if (vx != vy) { /* includes cases where one is scalar */
    2884         [ +  + ]:   10439784 :     if (varncmp(vx, vy) < 0) return div_T_scal(x, y, tx);
    2885                 :    9147764 :                         else return div_scal_T(x, y, ty);
    2886                 :            :   }
    2887   [ +  +  +  + ]:     672056 :   switch(tx)
    2888                 :            :   {
    2889                 :            :     case t_POL:
    2890      [ +  +  - ]:      79554 :       switch(ty)
    2891                 :            :       {
    2892                 :            :         case t_SER:
    2893         [ -  + ]:         28 :           if (lg(y) == 2)
    2894                 :          0 :             return zeroser(vx, RgX_val(x) - valp(y));
    2895                 :         28 :           p1 = RgX_to_ser(x,lg(y));
    2896                 :         28 :           p2 = div_ser(p1, y, vx);
    2897                 :         28 :           settyp(p1, t_VECSMALL); /* p1 left on stack */
    2898                 :         28 :           return p2;
    2899                 :            : 
    2900                 :            :         case t_RFRAC:
    2901                 :            :         {
    2902                 :      79526 :           GEN y1 = gel(y,1), y2 = gel(y,2);
    2903 [ +  + ][ -  + ]:      79526 :           if (typ(y1) == t_POL && varn(y1) == vx)
    2904                 :          0 :             return mul_rfrac_scal(y2, y1, x);
    2905                 :      79526 :           av = avma;
    2906                 :      79526 :           return gerepileupto(av, RgX_Rg_div(RgX_mul(y2, x), y1));
    2907                 :            :         }
    2908                 :            :       }
    2909                 :          0 :       break;
    2910                 :            : 
    2911                 :            :     case t_SER:
    2912      [ +  -  - ]:     339361 :       switch(ty)
    2913                 :            :       {
    2914                 :            :         case t_POL:
    2915         [ +  + ]:     339361 :           if (lg(x) == 2)
    2916                 :        105 :             return zeroser(vx, valp(x) - RgX_val(y));
    2917                 :     339256 :           p1 = RgX_to_ser_inexact(y,lg(x));
    2918                 :     339256 :           p2 = div_ser(x, p1, vx);
    2919                 :     339256 :           settyp(p1, t_VECSMALL); /* p1 left on stack */
    2920                 :     339256 :           return p2;
    2921                 :            :         case t_RFRAC:
    2922                 :          0 :           av = avma;
    2923                 :          0 :           return gerepileupto(av, gdiv(gmul(x,gel(y,2)), gel(y,1)));
    2924                 :            :       }
    2925                 :          0 :       break;
    2926                 :            : 
    2927                 :            :     case t_RFRAC:
    2928      [ +  -  - ]:     253127 :       switch(ty)
    2929                 :            :       {
    2930                 :     253127 :         case t_POL: return div_rfrac_pol(gel(x,1),gel(x,2), y);
    2931                 :            :         case t_SER:
    2932                 :          0 :           av = avma; z = RgX_to_ser_inexact(gel(x,2), lg(y));
    2933                 :          0 :           return gerepileupto(av, gdiv(gel(x,1), gmul(z,y)));
    2934                 :            :       }
    2935                 :          0 :       break;
    2936                 :            :   }
    2937                 :         14 :   pari_err_TYPE2("/",x,y);
    2938                 :  132422942 :   return NULL; /* not reached */
    2939                 :            : }
    2940                 :            : 
    2941                 :            : /********************************************************************/
    2942                 :            : /**                                                                **/
    2943                 :            : /**                     SIMPLE MULTIPLICATION                      **/
    2944                 :            : /**                                                                **/
    2945                 :            : /********************************************************************/
    2946                 :            : GEN
    2947                 :   22711582 : gmulsg(long s, GEN y)
    2948                 :            : {
    2949                 :            :   long ly, i;
    2950                 :            :   pari_sp av;
    2951                 :            :   GEN z;
    2952                 :            : 
    2953   [ +  +  +  +  :   22711582 :   switch(typ(y))
          +  +  +  +  +  
             +  +  +  +  
                      - ]
    2954                 :            :   {
    2955                 :   11177036 :     case t_INT:  return mulsi(s,y);
    2956                 :    8475088 :     case t_REAL: return mulsr(s,y);
    2957                 :     168367 :     case t_INTMOD: { GEN p = gel(y,1);
    2958                 :     168367 :       z = cgetg(3,t_INTMOD);
    2959                 :     168371 :       gel(z,2) = gerepileuptoint((pari_sp)z, modii(mulsi(s,gel(y,2)), p));
    2960                 :     168374 :       gel(z,1) = icopy(p); return z;
    2961                 :            :     }
    2962                 :     390034 :     case t_FFELT: return FF_Z_mul(y,stoi(s));
    2963                 :            :     case t_FRAC:
    2964         [ +  + ]:     692419 :       if (!s) return gen_0;
    2965                 :     691747 :       z = cgetg(3,t_FRAC);
    2966                 :     691747 :       i = cgcd(s, smodis(gel(y,2), s));
    2967         [ +  + ]:     691747 :       if (i == 1)
    2968                 :            :       {
    2969                 :     328482 :         gel(z,2) = icopy(gel(y,2));
    2970                 :     328482 :         gel(z,1) = mulis(gel(y,1), s);
    2971                 :            :       }
    2972                 :            :       else
    2973                 :            :       {
    2974                 :     363265 :         gel(z,2) = divis(gel(y,2), i);
    2975                 :     363265 :         gel(z,1) = mulis(gel(y,1), s/i);
    2976         [ +  + ]:     363265 :         fix_frac_if_int(z);
    2977                 :            :       }
    2978                 :     691747 :       return z;
    2979                 :            : 
    2980                 :    1081972 :     case t_COMPLEX: z = cgetg(3, t_COMPLEX);
    2981                 :    1081972 :       gel(z,1) = gmulsg(s,gel(y,1));
    2982                 :    1081972 :       gel(z,2) = gmulsg(s,gel(y,2)); return z;
    2983                 :            : 
    2984                 :            :     case t_PADIC:
    2985         [ -  + ]:        756 :       if (!s) return gen_0;
    2986                 :        756 :       av = avma; return gerepileupto(av, mulpp(cvtop2(stoi(s),y), y));
    2987                 :            : 
    2988                 :          7 :     case t_QUAD: z = cgetg(4, t_QUAD);
    2989                 :          7 :       gel(z,1) = ZX_copy(gel(y,1));
    2990                 :          7 :       gel(z,2) = gmulsg(s,gel(y,2));
    2991                 :          7 :       gel(z,3) = gmulsg(s,gel(y,3)); return z;
    2992                 :            : 
    2993                 :       5229 :     case t_POLMOD: z = cgetg(3, t_POLMOD);
    2994                 :       5229 :       gel(z,1) = RgX_copy(gel(y,1));
    2995                 :       5229 :       gel(z,2) = gmulsg(s,gel(y,2)); return z;
    2996                 :            : 
    2997                 :            :     case t_POL:
    2998         [ +  + ]:     554648 :       if (!signe(y)) return RgX_copy(y);
    2999         [ +  + ]:     549657 :       if (!s) return scalarpol(RgX_get_0(y), varn(y));
    3000                 :     545961 :       z = cgetg_copy(y, &ly); z[1]=y[1];
    3001         [ +  + ]:    1954746 :       for (i=2; i<ly; i++) gel(z,i) = gmulsg(s,gel(y,i));
    3002                 :     545961 :       return normalizepol_lg(z, ly);
    3003                 :            : 
    3004                 :            :     case t_SER:
    3005         [ -  + ]:        784 :       if (ser_isexactzero(y)) return gcopy(y);
    3006         [ -  + ]:        784 :       if (!s) return scalarser(RgX_get_0(y), varn(y), valp(y));
    3007                 :        784 :       z = cgetg_copy(y, &ly); z[1]=y[1];
    3008         [ +  + ]:       5341 :       for (i=2; i<ly; i++) gel(z,i) = gmulsg(s,gel(y,i));
    3009                 :        784 :       return normalize(z);
    3010                 :            : 
    3011                 :            :     case t_RFRAC:
    3012         [ -  + ]:         14 :       if (!s) return zeropol(varn(gel(y,2)));
    3013         [ -  + ]:         14 :       if (s == 1) return gcopy(y);
    3014         [ -  + ]:         14 :       if (s == -1) return gneg(y);
    3015                 :         14 :       return mul_rfrac_scal(gel(y,1), gel(y,2), stoi(s));
    3016                 :            : 
    3017                 :            :     case t_VEC: case t_COL: case t_MAT:
    3018                 :     165228 :       z = cgetg_copy(y, &ly);
    3019         [ +  + ]:     652360 :       for (i=1; i<ly; i++) gel(z,i) = gmulsg(s,gel(y,i));
    3020                 :     165228 :       return z;
    3021                 :            :   }
    3022                 :          0 :   pari_err_TYPE("gmulsg",y);
    3023                 :   22711594 :   return NULL; /* not reached */
    3024                 :            : }
    3025                 :            : 
    3026                 :            : /********************************************************************/
    3027                 :            : /**                                                                **/
    3028                 :            : /**                       SIMPLE DIVISION                          **/
    3029                 :            : /**                                                                **/
    3030                 :            : /********************************************************************/
    3031                 :            : 
    3032                 :            : GEN
    3033                 :    6241674 : gdivgs(GEN x, long s)
    3034                 :            : {
    3035                 :    6241674 :   long tx = typ(x), lx, i;
    3036                 :            :   pari_sp av;
    3037                 :            :   GEN z, y, p1;
    3038                 :            : 
    3039         [ -  + ]:    6241674 :   if (!s)
    3040                 :            :   {
    3041 [ #  # ][ #  # ]:          0 :     if (is_matvec_t(tx) && lg(x) == 1) return gcopy(x);
    3042                 :          0 :     pari_err_INV("gdivgs",gen_0);
    3043                 :            :   }
    3044   [ +  +  +  +  :    6241674 :   switch(tx)
          +  +  +  -  +  
             +  +  -  - ]
    3045                 :            :   {
    3046                 :            :     case t_INT:
    3047                 :    2525414 :       av = avma; z = divis_rem(x,s,&i);
    3048         [ +  + ]:    2525414 :       if (!i) return z;
    3049                 :            : 
    3050                 :    1501470 :       i = cgcd(s, i);
    3051                 :    1501470 :       avma=av; z = cgetg(3,t_FRAC);
    3052         [ +  + ]:    1501470 :       if (i == 1) y = icopy(x); else { s /= i; y = diviuexact(x, i); }
    3053                 :    1501470 :       gel(z,1) = y;
    3054                 :    1501470 :       gel(z,2) = stoi(s); normalize_frac(z); return z;
    3055                 :            : 
    3056                 :            :     case t_REAL:
    3057                 :    2493639 :       return divrs(x,s);
    3058                 :            : 
    3059                 :            :     case t_INTMOD:
    3060                 :       7350 :       z = cgetg(3, t_INTMOD);
    3061                 :       7350 :       return div_intmod_same(z, gel(x,1), gel(x,2), modsi(s, gel(x,1)));
    3062                 :            : 
    3063                 :        399 :     case t_FFELT: return FF_Z_Z_muldiv(x,gen_1,stoi(s));
    3064                 :            : 
    3065                 :     219837 :     case t_FRAC: z = cgetg(3, t_FRAC);
    3066                 :     219837 :       i = cgcd(s, smodis(gel(x,1), s));
    3067         [ +  + ]:     219837 :       if (i == 1)
    3068                 :            :       {
    3069                 :      40721 :         gel(z,2) = mulsi(s, gel(x,2));
    3070                 :      40721 :         gel(z,1) = icopy(gel(x,1));
    3071                 :            :       }
    3072                 :            :       else
    3073                 :            :       {
    3074                 :     179116 :         gel(z,2) = mulsi(s/i, gel(x,2));
    3075                 :     179116 :         gel(z,1) = divis(gel(x,1), i);
    3076                 :            :       }
    3077                 :     219837 :       normalize_frac(z);
    3078         [ +  + ]:     219837 :       fix_frac_if_int(z); return z;
    3079                 :            : 
    3080                 :     893592 :     case t_COMPLEX: z = cgetg(3, t_COMPLEX);
    3081                 :     893592 :       gel(z,1) = gdivgs(gel(x,1),s);
    3082                 :     893592 :       gel(z,2) = gdivgs(gel(x,2),s); return z;
    3083                 :            : 
    3084                 :            :     case t_PADIC: /* divpT */
    3085                 :            :     {
    3086                 :      82627 :       GEN p = gel(x,2);
    3087         [ +  + ]:      82627 :       if (!signe(gel(x,4))) return zeropadic(p, valp(x) - u_pval(s,p));
    3088                 :      81906 :       av = avma;
    3089                 :      81906 :       return gerepileupto(av, divpp(x, cvtop2(stoi(s),x)));
    3090                 :            :     }
    3091                 :            : 
    3092                 :          0 :     case t_QUAD: z = cgetg(4, t_QUAD);
    3093                 :          0 :       gel(z,1) = ZX_copy(gel(x,1));
    3094                 :          0 :       gel(z,2) = gdivgs(gel(x,2),s);
    3095                 :          0 :       gel(z,3) = gdivgs(gel(x,3),s); return z;
    3096                 :            : 
    3097                 :       1505 :     case t_POLMOD: z = cgetg(3, t_POLMOD);
    3098                 :       1505 :       gel(z,1) = RgX_copy(gel(x,1));
    3099                 :       1505 :       gel(z,2) = gdivgs(gel(x,2),s); return z;
    3100                 :            : 
    3101                 :            :     case t_RFRAC:
    3102                 :         91 :       av = avma;
    3103                 :         91 :       p1 = ggcd(stoi(s),gel(x,1));
    3104         [ +  + ]:         91 :       if (typ(p1) == t_INT)
    3105                 :            :       {
    3106                 :         42 :         avma = av;
    3107                 :         42 :         z = cgetg(3, t_RFRAC);
    3108                 :         42 :         i = p1[2];
    3109         [ +  - ]:         42 :         if (i == 1)
    3110                 :            :         {
    3111                 :         42 :           gel(z,1) = gcopy(gel(x,1));
    3112                 :         42 :           gel(z,2) = gmulsg(s,gel(x,2));
    3113                 :            :         }
    3114                 :            :         else
    3115                 :            :         {
    3116                 :          0 :           gel(z,1) = gdivgs(gel(x,1), i);
    3117                 :          0 :           gel(z,2) = gmulgs(gel(x,2), s/i);
    3118                 :            :         }
    3119                 :            :       }
    3120                 :            :       else /* t_FRAC */
    3121                 :            :       {
    3122                 :         49 :         z = cgetg(3, t_RFRAC);
    3123                 :         49 :         gel(z,1) = gdiv(gel(x,1), p1);
    3124                 :         49 :         gel(z,2) = RgX_Rg_mul(gel(x,2), gdivsg(s,p1));
    3125                 :         49 :         z = gerepilecopy(av, z);
    3126                 :            :       }
    3127                 :         91 :       return z;
    3128                 :            : 
    3129                 :            :     case t_POL: case t_SER:
    3130                 :      17220 :       z = cgetg_copy(x, &lx); z[1] = x[1];
    3131         [ +  + ]:      59451 :       for (i=2; i<lx; i++) gel(z,i) = gdivgs(gel(x,i),s);
    3132                 :      17220 :       return z;
    3133                 :            :     case t_VEC: case t_COL: case t_MAT:
    3134                 :          0 :       z = cgetg_copy(x, &lx);
    3135         [ #  # ]:          0 :       for (i=1; i<lx; i++) gel(z,i) = gdivgs(gel(x,i),s);
    3136                 :          0 :       return z;
    3137                 :            : 
    3138                 :            :   }
    3139                 :          0 :   pari_err_TYPE2("/",x, stoi(s));
    3140                 :    6241675 :   return NULL; /* not reached */
    3141                 :            : }
    3142                 :            : 
    3143                 :            : /* True shift (exact multiplication by 2^n) */
    3144                 :            : GEN
    3145                 :   33850344 : gmul2n(GEN x, long n)
    3146                 :            : {
    3147                 :            :   long lx, i, k, l;
    3148                 :            :   GEN z, a, b;
    3149                 :            : 
    3150   [ +  +  +  +  :   33850344 :   switch(typ(x))
          +  +  +  +  +  
             +  +  +  +  
                      - ]
    3151                 :            :   {
    3152                 :            :     case t_INT:
    3153         [ +  + ]:   25543074 :       if (n>=0) return shifti(x,n);
    3154         [ +  + ]:     161077 :       if (!signe(x)) return gen_0;
    3155                 :      64211 :       l = vali(x); n = -n;
    3156         [ +  + ]:      64211 :       if (n<=l) return shifti(x,-n);
    3157                 :      38472 :       z = cgetg(3,t_FRAC);
    3158                 :      38472 :       gel(z,1) = shifti(x,-l);
    3159                 :      38472 :       gel(z,2) = int2n(n-l); return z;
    3160                 :            : 
    3161                 :            :     case t_REAL:
    3162                 :    4010998 :       return shiftr(x,n);
    3163                 :            : 
    3164                 :      78803 :     case t_INTMOD: b = gel(x,1); a = gel(x,2);
    3165                 :      78803 :       z = cgetg(3,t_INTMOD);
    3166         [ +  + ]:      78796 :       if (n <= 0) return div_intmod_same(z, b, a, modii(int2n(-n), b));
    3167                 :      78789 :       gel(z,2) = gerepileuptoint((pari_sp)z, modii(shifti(a,n), b));
    3168                 :      78797 :       gel(z,1) = icopy(b); return z;
    3169                 :            : 
    3170                 :     153071 :     case t_FFELT: return FF_mul2n(x,n);
    3171                 :            : 
    3172                 :     125083 :     case t_FRAC: a = gel(x,1); b = gel(x,2);
    3173                 :     125083 :       l = vali(a);
    3174                 :     125083 :       k = vali(b);
    3175         [ +  + ]:     125083 :       if (n+l >= k)
    3176                 :            :       {
    3177         [ +  + ]:      67254 :         if (expi(b) == k) return shifti(a,n-k); /* b power of 2 */
    3178                 :      59344 :         l = n-k; k = -k;
    3179                 :            :       }
    3180                 :            :       else
    3181                 :            :       {
    3182                 :      57829 :         k = -(l+n); l = -l;
    3183                 :            :       }
    3184                 :     117173 :       z = cgetg(3,t_FRAC);
    3185                 :     117173 :       gel(z,1) = shifti(a,l);
    3186                 :     117173 :       gel(z,2) = shifti(b,k); return z;
    3187                 :            : 
    3188                 :    2769987 :     case t_COMPLEX: z = cgetg(3,t_COMPLEX);
    3189                 :    2769987 :       gel(z,1) = gmul2n(gel(x,1),n);
    3190                 :    2769987 :       gel(z,2) = gmul2n(gel(x,2),n); return z;
    3191                 :            : 
    3192                 :         14 :     case t_QUAD: z = cgetg(4,t_QUAD);
    3193                 :         14 :       gel(z,1) = ZX_copy(gel(x,1));
    3194                 :         14 :       gel(z,2) = gmul2n(gel(x,2),n);
    3195                 :         14 :       gel(z,3) = gmul2n(gel(x,3),n); return z;
    3196                 :            : 
    3197                 :      13385 :     case t_POLMOD: z = cgetg(3,t_POLMOD);
    3198                 :      13385 :       gel(z,1) = RgX_copy(gel(x,1));
    3199                 :      13385 :       gel(z,2) = gmul2n(gel(x,2),n); return z;
    3200                 :            : 
    3201                 :            :     case t_POL:
    3202                 :     284398 :       z = cgetg_copy(x, &lx); z[1] = x[1];
    3203         [ +  + ]:    2321584 :       for (i=2; i<lx; i++) gel(z,i) = gmul2n(gel(x,i),n);
    3204                 :     284398 :       return normalizepol_lg(z, lx); /* needed if char = 2 */
    3205                 :            :     case t_SER:
    3206         [ +  + ]:      57106 :       if (ser_isexactzero(x)) return gcopy(x);
    3207                 :      57092 :       z = cgetg_copy(x, &lx); z[1] = x[1];
    3208         [ +  + ]:     866866 :       for (i=2; i<lx; i++) gel(z,i) = gmul2n(gel(x,i),n);
    3209                 :      57092 :       return normalize(z); /* needed if char = 2 */
    3210                 :            :     case t_VEC: case t_COL: case t_MAT:
    3211                 :     805087 :       z = cgetg_copy(x, &lx);
    3212         [ +  + ]:    3215670 :       for (i=1; i<lx; i++) gel(z,i) = gmul2n(gel(x,i),n);
    3213                 :     805087 :       return z;
    3214                 :            : 
    3215                 :            :     case t_RFRAC: /* int2n wrong if n < 0 */
    3216                 :         14 :       return mul_rfrac_scal(gel(x,1),gel(x,2), gmul2n(gen_1,n));
    3217                 :            : 
    3218                 :            :     case t_PADIC: /* int2n wrong if n < 0 */
    3219                 :       9324 :       return gmul(gmul2n(gen_1,n),x);
    3220                 :            :   }
    3221                 :          0 :   pari_err_TYPE("gmul2n",x);
    3222                 :   33850345 :   return NULL; /* not reached */
    3223                 :            : }
    3224                 :            : 
    3225                 :            : /*******************************************************************/
    3226                 :            : /*                                                                 */
    3227                 :            : /*                              INVERSE                            */
    3228                 :            : /*                                                                 */
    3229                 :            : /*******************************************************************/
    3230                 :            : static GEN
    3231                 :      24279 : inv_polmod(GEN T, GEN x)
    3232                 :            : {
    3233                 :      24279 :   GEN z = cgetg(3,t_POLMOD), a;
    3234                 :      24279 :   gel(z,1) = RgX_copy(T);
    3235 [ +  + ][ +  + ]:      24279 :   if (typ(x) != t_POL || varn(x) != varn(T) || lg(x) <= 3)
                 [ +  + ]
    3236                 :       9268 :     a = ginv(x);
    3237                 :            :   else
    3238                 :            :   {
    3239                 :      15011 :     pari_sp av = avma;
    3240         [ +  + ]:      15011 :     if (lg(T) == 5) /* quadratic fields */
    3241                 :      11543 :       a = RgX_Rg_div(quad_polmod_conj(x,T), quad_polmod_norm(x,T));
    3242                 :            :     else
    3243                 :            :     {
    3244                 :       3468 :       GEN p = NULL;
    3245 [ +  + ][ +  + ]:       3468 :       if (RgX_is_FpX(T, &p) && RgX_is_FpX(x, &p) && p)
                 [ +  + ]
    3246                 :            :       {
    3247                 :         14 :         T = RgX_to_FpX(T, p); x = RgX_to_FpX(x, p);
    3248         [ +  + ]:         14 :         if (lgefint(p) == 3)
    3249                 :            :         {
    3250                 :          7 :           ulong pp = p[2];
    3251                 :          7 :           a = Flxq_inv(ZX_to_Flx(x, pp), ZX_to_Flx(T, pp), pp);
    3252                 :          7 :           a = Flx_to_ZX(a);
    3253                 :            :         }
    3254                 :            :         else
    3255                 :          7 :           a = FpXQ_inv(x, T, p);
    3256                 :         14 :         a = FpX_to_mod(a, p);
    3257                 :         14 :         a = gerepileupto(av, a);
    3258                 :            :       }
    3259 [ +  + ][ +  + ]:       3454 :       else if (RgX_is_ZX(T) && RgX_is_QX(x))
    3260                 :            :       {
    3261                 :       2747 :         avma = av;
    3262                 :       2747 :         a = QXQ_inv(x, T);
    3263                 :            :       }
    3264                 :            :       else {
    3265                 :        707 :         avma = av;
    3266                 :       3468 :         a = RgXQ_inv(x, T);
    3267                 :            :       }
    3268                 :            :     }
    3269                 :            :   }
    3270                 :      24279 :   gel(z,2) = a; return z;
    3271                 :            : }
    3272                 :            : 
    3273                 :            : GEN
    3274                 :    9286076 : ginv(GEN x)
    3275                 :            : {
    3276                 :            :   long s;
    3277                 :            :   pari_sp av, tetpil;
    3278                 :            :   GEN z, y, p1, p2;
    3279                 :            : 
    3280   [ +  +  +  +  :    9286076 :   switch(typ(x))
          +  +  +  +  +  
          +  +  +  +  +  
                +  -  - ]
    3281                 :            :   {
    3282                 :            :     case t_INT:
    3283         [ +  + ]:      83489 :       if (is_pm1(x)) return icopy(x);
    3284         [ -  + ]:      50743 :       s = signe(x); if (!s) pari_err_INV("ginv",gen_0);
    3285                 :      50743 :       z = cgetg(3,t_FRAC);
    3286         [ +  + ]:      50743 :       gel(z,1) = s<0? gen_m1: gen_1;
    3287                 :      50743 :       gel(z,2) = absi(x); return z;
    3288                 :            : 
    3289                 :    1496437 :     case t_REAL: return invr(x);
    3290                 :            : 
    3291                 :        777 :     case t_INTMOD: z=cgetg(3,t_INTMOD);
    3292                 :        777 :       gel(z,1) = icopy(gel(x,1));
    3293                 :        777 :       gel(z,2) = Fp_inv(gel(x,2),gel(x,1)); return z;
    3294                 :            : 
    3295                 :            :     case t_FRAC: {
    3296                 :     115315 :       GEN a = gel(x,1), b = gel(x,2);
    3297                 :     115315 :       s = signe(a);
    3298 [ +  + ][ +  + ]:     115315 :       if (is_pm1(a)) return s > 0? icopy(b): negi(b);
    3299                 :      48765 :       z = cgetg(3,t_FRAC);
    3300                 :      48765 :       gel(z,1) = icopy(b);
    3301                 :      48765 :       gel(z,2) = icopy(a);
    3302                 :      48765 :       normalize_frac(z); return z;
    3303                 :            :     }
    3304                 :            :     case t_COMPLEX:
    3305                 :    1182976 :       av=avma;
    3306                 :    1182976 :       p1=cxnorm(x);
    3307                 :    1182976 :       p2=mkcomplex(gel(x,1), gneg(gel(x,2)));
    3308                 :    1182976 :       tetpil=avma;
    3309                 :    1182976 :       return gerepile(av,tetpil,divcR(p2,p1));
    3310                 :            : 
    3311                 :            :     case t_QUAD:
    3312                 :        203 :       av=avma; p1=gnorm(x); p2=gconj(x); tetpil=avma;
    3313                 :        203 :       return gerepile(av,tetpil,gdiv(p2,p1));
    3314                 :            : 
    3315                 :        868 :     case t_PADIC: z = cgetg(5,t_PADIC);
    3316         [ +  + ]:        868 :       if (!signe(gel(x,4))) pari_err_INV("ginv",x);
    3317                 :        861 :       z[1] = _evalprecp(precp(x)) | evalvalp(-valp(x));
    3318                 :        861 :       gel(z,2) = icopy(gel(x,2));
    3319                 :        861 :       gel(z,3) = icopy(gel(x,3));
    3320                 :        861 :       gel(z,4) = Fp_inv(gel(x,4),gel(z,3)); return z;
    3321                 :            : 
    3322                 :      24279 :     case t_POLMOD: return inv_polmod(gel(x,1), gel(x,2));
    3323                 :       4629 :     case t_FFELT: return FF_inv(x);
    3324                 :    5391182 :     case t_POL: return gred_rfrac_simple(gen_1,x);
    3325                 :       7609 :     case t_SER: return gdiv(gen_1,x);
    3326                 :            : 
    3327                 :            :     case t_RFRAC:
    3328                 :            :     {
    3329                 :       2905 :       GEN n = gel(x,1), d = gel(x,2);
    3330                 :       2905 :       pari_sp av = avma, ltop;
    3331         [ -  + ]:       2905 :       if (gequal0(n)) pari_err_INV("ginv",x);
    3332                 :            : 
    3333                 :       2905 :       n = simplify_shallow(n);
    3334 [ +  + ][ +  - ]:       2905 :       if (typ(n) != t_POL || varn(n) != varn(d))
    3335                 :            :       {
    3336         [ +  + ]:       2905 :         if (gequal1(n)) { avma = av; return RgX_copy(d); }
    3337                 :        679 :         ltop = avma;
    3338                 :        679 :         z = RgX_Rg_div(d,n);
    3339                 :            :       } else {
    3340                 :          0 :         ltop = avma;
    3341                 :          0 :         z = cgetg(3,t_RFRAC);
    3342                 :          0 :         gel(z,1) = RgX_copy(d);
    3343                 :          0 :         gel(z,2) = RgX_copy(n);
    3344                 :            :       }
    3345                 :        679 :       stackdummy(av, ltop);
    3346                 :        679 :       return z;
    3347                 :            :     }
    3348                 :            : 
    3349                 :            :     case t_QFR:
    3350                 :          7 :       av = avma; z = cgetg(5, t_QFR);
    3351                 :          7 :       gel(z,1) = gel(x,1);
    3352                 :          7 :       gel(z,2) = negi( gel(x,2) );
    3353                 :          7 :       gel(z,3) = gel(x,3);
    3354                 :          7 :       gel(z,4) = negr( gel(x,4) );
    3355                 :          7 :       return gerepileupto(av, redreal(z));
    3356                 :            : 
    3357                 :            :     case t_QFI:
    3358                 :     973846 :       y = gcopy(x);
    3359 [ +  + ][ +  + ]:     973846 :       if (!equalii(gel(x,1),gel(x,2)) && !equalii(gel(x,1),gel(x,3)))
    3360                 :     948932 :         togglesign(gel(y,2));
    3361                 :     973846 :       return y;
    3362                 :            :     case t_MAT:
    3363                 :       1554 :       y = RgM_inv(x);
    3364         [ -  + ]:       1554 :       if (!y) pari_err_INV("ginv",x);
    3365                 :       1554 :       return y;
    3366                 :            :     case t_VECSMALL:
    3367                 :            :     {
    3368                 :          0 :       long i, lx = lg(x)-1;
    3369                 :          0 :       y = zero_zv(lx);
    3370         [ #  # ]:          0 :       for (i=1; i<=lx; i++)
    3371                 :            :       {
    3372                 :          0 :         long xi = x[i];
    3373 [ #  # ][ #  # ]:          0 :         if (xi<1 || xi>lx || y[xi])
                 [ #  # ]
    3374                 :          0 :           pari_err_TYPE("ginv [not a permutation]", x);
    3375                 :          0 :         y[xi] = i;
    3376                 :            :       }
    3377                 :          0 :       return y;
    3378                 :            :     }
    3379                 :            :   }
    3380                 :          0 :   pari_err_TYPE("inverse",x);
    3381                 :    9286056 :   return NULL; /* not reached */
    3382                 :            : }

Generated by: LCOV version 1.9