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-bordeaux1.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 17784-cfd2407) Lines: 1775 1937 91.6 %
Date: 2015-04-28 Functions: 88 88 100.0 %
Legend: Lines: hit not hit | Branches: + taken - not taken # not executed Branches: 1184 1442 82.1 %

           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                 :   40661523 : addRc(GEN x, GEN y) {
      63                 :   40661523 :   GEN z = cgetg(3,t_COMPLEX);
      64                 :   40661523 :   gel(z,1) = gadd(x,gel(y,1));
      65                 :   40661523 :   gel(z,2) = gcopy(gel(y,2)); return z;
      66                 :            : }
      67                 :            : static GEN
      68                 :   40997714 : mulRc(GEN x, GEN y) {
      69                 :   40997714 :   GEN z = cgetg(3,t_COMPLEX);
      70         [ +  + ]:   40997714 :   gel(z,1) = isintzero(gel(y,1))? gen_0: gmul(x,gel(y,1));
      71                 :   40997714 :   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                 :     340539 : divRc(GEN x, GEN y) {
      82                 :     340539 :   GEN t = gdiv(x, cxnorm(y)), mt = gneg(t); /* left on stack for efficiency */
      83                 :     340539 :   GEN z = cgetg(3,t_COMPLEX);
      84         [ +  + ]:     340539 :   gel(z,1) = isintzero(gel(y,1))? gen_0: gmul(t, gel(y,1));
      85                 :     340539 :   gel(z,2) = gmul(mt, gel(y,2));
      86                 :     340539 :   return z;
      87                 :            : }
      88                 :            : static GEN
      89                 :    2028508 : divcR(GEN x, GEN y) {
      90                 :    2028508 :   GEN z = cgetg(3,t_COMPLEX);
      91         [ +  + ]:    2028508 :   gel(z,1) = isintzero(gel(x,1))? gen_0: gdiv(gel(x,1), y);
      92                 :    2028508 :   gel(z,2) = gdiv(gel(x,2), y); return z;
      93                 :            : }
      94                 :            : static GEN
      95                 :        602 : addRq(GEN x, GEN y) {
      96                 :        602 :   GEN z = cgetg(4,t_QUAD);
      97                 :        602 :   gel(z,1) = ZX_copy(gel(y,1));
      98                 :        602 :   gel(z,2) = gadd(x, gel(y,2));
      99                 :        602 :   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                 :         14 : addqf(GEN x, GEN y, long prec) { pari_sp av = avma;
     110                 :         14 :   long i = gexpo(x) - gexpo(y);
     111         [ +  - ]:         14 :   if (i > 0) prec += nbits2extraprec( i );
     112                 :         14 :   return gerepileupto(av, gadd(y, quadtofp(x, prec)));
     113                 :            : }
     114                 :            : static GEN
     115                 :     935750 : mulrfrac(GEN x, GEN y)
     116                 :            : {
     117                 :     935750 :   pari_sp av = avma;
     118                 :     935750 :   GEN z, a = gel(y,1), b = gel(y,2);
     119         [ +  + ]:     935750 :   if (is_pm1(a)) /* frequent special case */
     120                 :            :   {
     121                 :     647442 :     z = divri(x, b);
     122         [ +  + ]:     647442 :     if (signe(a) < 0) togglesign(z);
     123                 :     647442 :     return z;
     124                 :            :   }
     125                 :     935750 :   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                 :      78576 : mulTp(GEN x, GEN y) { pari_sp av = avma;
     153                 :      78576 :   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                 :         63 : divTp(GEN x, GEN y) { pari_sp av = avma;
     158                 :         63 :   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                 :        910 : divpT(GEN x, GEN y) { pari_sp av = avma;
     164                 :        910 :   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                 :    1012511 : add_intmod_same(GEN z, GEN X, GEN x, GEN y) {
     171         [ +  + ]:    1012511 :   if (lgefint(X) == 3) {
     172                 :     977394 :     ulong u = Fl_add(itou(x),itou(y), X[2]);
     173                 :     977394 :     avma = (pari_sp)z; gel(z,2) = utoi(u);
     174                 :            :   }
     175                 :            :   else {
     176         [ +  + ]:      35117 :     GEN u = addii(x,y); if (cmpii(u, X) >= 0) u = subii(u, X);
     177                 :      35126 :     gel(z,2) = gerepileuptoint((pari_sp)z, u);
     178                 :            :   }
     179                 :    1012522 :   gel(z,1) = icopy(X); return z;
     180                 :            : }
     181                 :            : static GEN
     182                 :     122242 : sub_intmod_same(GEN z, GEN X, GEN x, GEN y) {
     183         [ +  + ]:     122242 :   if (lgefint(X) == 3) {
     184                 :     101797 :     ulong u = Fl_sub(itou(x),itou(y), X[2]);
     185                 :     101797 :     avma = (pari_sp)z; gel(z,2) = utoi(u);
     186                 :            :   }
     187                 :            :   else {
     188         [ +  + ]:      20445 :     GEN u = subii(x,y); if (signe(u) < 0) u = addii(u, X);
     189                 :      20438 :     gel(z,2) = gerepileuptoint((pari_sp)z, u);
     190                 :            :   }
     191                 :     122240 :   gel(z,1) = icopy(X); return z;
     192                 :            : }
     193                 :            : /* cf add_intmod_same */
     194                 :            : static GEN
     195                 :    2455957 : mul_intmod_same(GEN z, GEN X, GEN x, GEN y) {
     196         [ +  + ]:    2455957 :   if (lgefint(X) == 3) {
     197                 :    2341636 :     ulong u = Fl_mul(itou(x),itou(y), X[2]);
     198                 :    2341636 :     avma = (pari_sp)z; gel(z,2) = utoi(u);
     199                 :            :   }
     200                 :            :   else
     201                 :     114321 :     gel(z,2) = gerepileuptoint((pari_sp)z, remii(mulii(x,y), X) );
     202                 :    2455982 :   gel(z,1) = icopy(X); return z;
     203                 :            : }
     204                 :            : /* cf add_intmod_same */
     205                 :            : static GEN
     206                 :      28134 : div_intmod_same(GEN z, GEN X, GEN x, GEN y)
     207                 :            : {
     208         [ +  + ]:      28134 :   if (lgefint(X) == 3) {
     209                 :      20237 :     ulong m = uel(X,2), u = Fl_div(itou(x), itou(y), m);
     210                 :      20230 :     avma = (pari_sp)z; gel(z,2) = utoi(u);
     211                 :            :   }
     212                 :            :   else
     213                 :       7897 :     gel(z,2) = gerepileuptoint((pari_sp)z, remii(mulii(x, Fp_inv(y,X)), X) );
     214                 :      28127 :   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                 :    9405153 : rfrac_denom_mul_scal(GEN d, GEN y)
     227                 :            : {
     228                 :    9405153 :   GEN D = RgX_Rg_mul(d, y);
     229         [ -  + ]:    9405153 :   if (lg(D) != lg(d))
     230                 :            :   { /* try to generate a meaningful diagnostic */
     231                 :          0 :     D = gdiv(leading_term(d), y); /* should fail */
     232                 :          0 :     pari_err_INV("gred_rfrac", y); /* better than nothing */
     233                 :            :   }
     234                 :    9405153 :   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                 :   54135113 : gred_rfrac_simple(GEN n, GEN d)
     240                 :            : {
     241                 :            :   GEN c, cn, cd, z;
     242                 :   54135113 :   long dd = degpol(d);
     243                 :            : 
     244         [ +  + ]:   54135113 :   if (dd <= 0)
     245                 :            :   {
     246         [ -  + ]:       5922 :     if (dd < 0) pari_err_INV("gred_rfrac_simple", d);
     247                 :       5922 :     n = gdiv(n, gel(d,2));
     248 [ +  + ][ +  + ]:       5922 :     if (typ(n) != t_POL || varn(n) != varn(d)) n = scalarpol(n, varn(d));
     249                 :       5922 :     return n;
     250                 :            :   }
     251                 :            : 
     252                 :   54129191 :   cd = content(d);
     253 [ +  + ][ +  + ]:   55031904 :   while (typ(n) == t_POL && !degpol(n)) n = gel(n,2);
     254 [ +  + ][ +  + ]:   54129191 :   cn = (typ(n) == t_POL && varn(n) == varn(d))? content(n): n;
     255         [ +  + ]:   54129191 :   if (!gequal1(cd)) {
     256                 :    6547951 :     d = RgX_Rg_div(d,cd);
     257         [ +  + ]:    6547951 :     if (!gequal1(cn))
     258                 :            :     {
     259         [ -  + ]:    1302166 :       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         [ +  + ]:    1302166 :         n = (cn != n)? RgX_Rg_div(n,cn): gen_1;
     265                 :    1302166 :         c = gdiv(cn,cd);
     266                 :            :       }
     267                 :            :     }
     268                 :            :     else
     269                 :    5245785 :       c = ginv(cd);
     270                 :            :   } else {
     271         [ +  + ]:   47581240 :     if (!gequal1(cn))
     272                 :            :     {
     273         [ +  + ]:    2586626 :       if (gequal0(cn)) {
     274         [ +  + ]:         91 :         if (isexactzero(cn)) return scalarpol(cn, varn(d));
     275                 :         21 :         c = gen_1;
     276                 :            :       } else {
     277         [ +  + ]:    2586535 :         n = (cn != n)? RgX_Rg_div(n,cn): gen_1;
     278                 :    2586535 :         c = cn;
     279                 :            :       }
     280                 :            :     } else {
     281                 :   44994614 :       GEN y = cgetg(3,t_RFRAC);
     282                 :   44994614 :       gel(y,1) = gcopy(n);
     283                 :   44994614 :       gel(y,2) = RgX_copy(d); return y;
     284                 :            :     }
     285                 :            :   }
     286                 :            : 
     287         [ +  + ]:    9134507 :   if (typ(c) == t_POL)
     288                 :            :   {
     289                 :     905280 :     z = c;
     290         [ +  + ]:     944697 :     do { z = content(z); } while (typ(z) == t_POL);
     291                 :     905280 :     cd = denom(z);
     292                 :     905280 :     cn = gmul(c, cd);
     293                 :            :   }
     294                 :            :   else
     295                 :            :   {
     296                 :    8229227 :     cn = numer(c);
     297                 :    8229227 :     cd = denom(c);
     298                 :            :   }
     299                 :    9134507 :   z = cgetg(3,t_RFRAC);
     300                 :    9134507 :   gel(z,1) = gmul(n, cn);
     301                 :    9134507 :   gel(z,2) = rfrac_denom_mul_scal(d, cd);
     302                 :   54135113 :   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                 :     155484 : fix_rfrac(GEN x, long d)
     308                 :            : {
     309                 :            :   GEN z, N, D;
     310 [ +  + ][ -  + ]:     155484 :   if (!d || typ(x) == t_POL) return x;
     311                 :     153881 :   z = cgetg(3, t_RFRAC);
     312                 :     153881 :   N = gel(x,1);
     313                 :     153881 :   D = gel(x,2);
     314         [ +  + ]:     153881 :   if (d > 0) {
     315         [ +  + ]:        210 :     gel(z, 1) = (typ(N)==t_POL && varn(N)==varn(D))? RgX_shift(N,d)
     316         [ +  + ]:     154021 :                                                    : monomialcopy(N,d,varn(D));
     317                 :     153811 :     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                 :     155484 :   return z;
     323                 :            : }
     324                 :            : 
     325                 :            : /* assume d != 0 */
     326                 :            : static GEN
     327                 :   43368846 : gred_rfrac2_i(GEN n, GEN d)
     328                 :            : {
     329                 :            :   GEN y, z;
     330                 :            :   long v, vd, vn;
     331                 :            : 
     332                 :   43368846 :   n = simplify_shallow(n);
     333         [ +  + ]:   43368846 :   if (isrationalzero(n)) return gcopy(n);
     334                 :   36574637 :   d = simplify_shallow(d);
     335         [ +  + ]:   36574637 :   if (typ(d) != t_POL) return gdiv(n,d);
     336                 :   35395140 :   vd = varn(d);
     337         [ +  + ]:   35395140 :   if (typ(n) != t_POL)
     338                 :            :   {
     339         [ +  + ]:   19890102 :     if (varncmp(vd, gvar(n)) >= 0) return gdiv(n,d);
     340         [ +  - ]:   19888695 :     if (varncmp(vd, gvar2(n)) < 0) return gred_rfrac_simple(n,d);
     341                 :          0 :     pari_err_BUG("gred_rfrac2_i [incompatible variables]");
     342                 :            :   }
     343                 :   15505038 :   vn = varn(n);
     344         [ +  + ]:   15505038 :   if (varncmp(vd, vn) < 0) return gred_rfrac_simple(n,d);
     345         [ +  + ]:   15367455 :   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                 :   15207703 :   v = RgX_valrem(n, &n) - RgX_valrem(d, &d);
     349         [ +  + ]:   15207703 :   if (!degpol(d))
     350                 :            :   {
     351                 :   12229804 :     n = RgX_Rg_div(n,gel(d,2));
     352         [ +  + ]:   12229804 :     return v? RgX_mulXn(n,v): n;
     353                 :            :   }
     354                 :            : 
     355                 :            :   /* X does not divide gcd(n,d), deg(d) > 0 */
     356 [ +  + ][ +  - ]:    2977899 :   if (!isinexact(n) && !isinexact(d))
     357                 :            :   {
     358                 :    2977822 :     y = RgX_divrem(n, d, &z);
     359 [ +  + ][ +  + ]:    2977822 :     if (!signe(z)) { cgiv(z); return v? RgX_mulXn(y, v): y; }
     360                 :     155407 :     z = RgX_gcd(d, z);
     361         [ +  + ]:     155407 :     if (degpol(z)) { n = RgX_div(n,z); d = RgX_div(d,z); }
     362                 :            :   }
     363                 :   43368846 :   return fix_rfrac(gred_rfrac_simple(n,d), v);
     364                 :            : }
     365                 :            : 
     366                 :            : GEN
     367                 :   18173599 : gred_rfrac2(GEN x1, GEN x2)
     368                 :            : {
     369                 :   18173599 :   pari_sp av = avma;
     370                 :   18173599 :   return gerepileupto(av, gred_rfrac2_i(x1, x2));
     371                 :            : }
     372                 :            : 
     373                 :            : /* x1,x2 t_INT, return x1/x2 in reduced form */
     374                 :            : GEN
     375                 :   13827945 : gred_frac2(GEN x1, GEN x2)
     376                 :            : {
     377                 :   13827945 :   GEN r, y = dvmdii(x1,x2,&r);
     378                 :            :   pari_sp av;
     379                 :            : 
     380         [ +  + ]:   13827917 :   if (r == gen_0) return y; /* gen_0 intended */
     381                 :    5164418 :   av = avma; r = gcdii(x2,r);
     382         [ +  + ]:    5164418 :   if (lgefint(r) == 3)
     383                 :            :   {
     384                 :    4971048 :     ulong rr = r[2];
     385                 :    4971048 :     avma = av;
     386         [ +  + ]:    4971048 :     if (rr == 1) y = mkfraccopy(x1, x2);
     387                 :            :     else
     388                 :            :     {
     389                 :    2491626 :       y = cgetg(3,t_FRAC);
     390                 :    2491626 :       gel(y,1) = diviuexact(x1, rr);
     391                 :    2491626 :       gel(y,2) = diviuexact(x2, rr);
     392                 :            :     }
     393                 :            :   }
     394                 :            :   else
     395                 :            :   { /* rare: r left on stack for efficiency */
     396                 :     193370 :     y = cgetg(3,t_FRAC);
     397                 :     193370 :     gel(y,1) = diviiexact(x1,r);
     398                 :     193370 :     gel(y,2) = diviiexact(x2,r);
     399                 :            :   }
     400                 :   13827917 :   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                 :      13433 : quad_polmod_conj(GEN x, GEN y)
     411                 :            : {
     412                 :            :   GEN z, u, v, a, b;
     413                 :            :   pari_sp av;
     414         [ -  + ]:      13433 :   if (typ(x) != t_POL) return gcopy(x);
     415 [ +  - ][ -  + ]:      13433 :   if (varn(x) != varn(y) || degpol(x) <= 0) return RgX_copy(x);
     416                 :      13433 :   a = gel(y,4); u = gel(x,3); /*Mod(ux + v, ax^2 + bx + c)*/
     417                 :      13433 :   b = gel(y,3); v = gel(x,2);
     418                 :      13433 :   z = cgetg(4, t_POL); z[1] = x[1]; av = avma;
     419                 :      13433 :   gel(z,2) = gerepileupto(av, gsub(v, gdiv(gmul(u,b), a)));
     420                 :      13433 :   gel(z,3) = gneg(u); return z;
     421                 :            : }
     422                 :            : static GEN
     423                 :      13433 : quad_polmod_norm(GEN x, GEN y)
     424                 :            : {
     425                 :            :   GEN z, u, v, a, b, c;
     426                 :            :   pari_sp av;
     427 [ +  - ][ +  - ]:      13433 :   if (typ(x) != t_POL || varn(x) != varn(y) || degpol(x) <= 0)
                 [ -  + ]
     428                 :          0 :     return gsqr(x);
     429                 :      13433 :   a = gel(y,4); u = gel(x,3); /*Mod(ux + v, ax^2 + bx + c)*/
     430                 :      13433 :   b = gel(y,3); v = gel(x,2);
     431                 :      13433 :   c = gel(y,2); av = avma;
     432                 :      13433 :   z = gmul(u, gsub(gmul(c,u), gmul(b,v)));
     433         [ +  + ]:      13433 :   if (!gequal1(a)) z = gdiv(z, a);
     434                 :      13433 :   return gerepileupto(av, gadd(z, gsqr(v)));
     435                 :            : }
     436                 :            : 
     437                 :            : GEN
     438                 :     559586 : gconj(GEN x)
     439                 :            : {
     440                 :            :   long lx, i;
     441                 :            :   GEN y;
     442                 :            : 
     443   [ +  +  +  +  :     559586 :   switch(typ(x))
             +  +  -  - ]
     444                 :            :   {
     445                 :            :     case t_INT: case t_REAL:
     446                 :      64664 :       return mpcopy(x);
     447                 :            : 
     448                 :            :     case t_INTMOD: case t_FRAC: case t_PADIC:
     449                 :       1400 :       return gcopy(x);
     450                 :            : 
     451                 :            :     case t_COMPLEX:
     452                 :     489030 :       y = cgetg(3,t_COMPLEX);
     453                 :     489030 :       gel(y,1) = gcopy(gel(x,1));
     454                 :     489030 :       gel(y,2) = gneg(gel(x,2));
     455                 :     489030 :       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                 :         21 :       y = cgetg_copy(x, &lx); y[1] = x[1];
     467         [ +  + ]:         63 :       for (i=2; i<lx; i++) gel(y,i) = gconj(gel(x,i));
     468                 :         21 :       break;
     469                 :            : 
     470                 :            :     case t_RFRAC: case t_VEC: case t_COL: case t_MAT:
     471                 :       3876 :       y = cgetg_copy(x, &lx);
     472         [ +  + ]:      20350 :       for (i=1; i<lx; i++) gel(y,i) = gconj(gel(x,i));
     473                 :       3876 :       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                 :     559586 :   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                 :     939008 : addsub_pp(GEN x, GEN y, GEN (*op)(GEN,GEN))
     580                 :            : {
     581                 :     939008 :   pari_sp av = avma;
     582                 :            :   long d,e,r,rx,ry;
     583                 :     939008 :   GEN u, z, mod, p = gel(x,2);
     584                 :            :   int swap;
     585                 :            : 
     586                 :     939008 :   (void)new_chunk(5 + lgefint(gel(x,3)) + lgefint(gel(y,3)));
     587                 :     939008 :   e = valp(x);
     588                 :     939008 :   r = valp(y); d = r-e;
     589         [ +  + ]:     939008 :   if (d < 0) { swap = 1; swap(x,y); e = r; d = -d; } else swap = 0;
     590                 :     939008 :   rx = precp(x);
     591                 :     939008 :   ry = precp(y);
     592         [ +  + ]:     939008 :   if (d) /* v(x) < v(y) */
     593                 :            :   {
     594                 :     399714 :     r = d+ry; z = powiu(p,d);
     595         [ +  + ]:     399714 :     if (r < rx) mod = mulii(z,gel(y,3)); else { r = rx; mod = gel(x,3); }
     596                 :     399714 :     z = mulii(z,gel(y,4));
     597         [ +  + ]:     399714 :     u = swap? op(z, gel(x,4)): op(gel(x,4), z);
     598                 :            :   }
     599                 :            :   else
     600                 :            :   {
     601                 :            :     long c;
     602         [ +  + ]:     539294 :     if (ry < rx) { r=ry; mod = gel(y,3); } else { r=rx; mod = gel(x,3); }
     603         [ -  + ]:     539294 :     u = swap? op(gel(y,4), gel(x,4)): op(gel(x,4), gel(y,4));
     604 [ +  + ][ +  + ]:     539294 :     if (!signe(u) || (c = Z_pvalrem(u,p,&u)) >= r)
     605                 :            :     {
     606                 :      50764 :       avma = av; return zeropadic(p, e+r);
     607                 :            :     }
     608         [ +  + ]:     488530 :     if (c)
     609                 :            :     {
     610                 :      46319 :       mod = diviiexact(mod, powiu(p,c));
     611                 :      46319 :       r -= c;
     612                 :      46319 :       e += c;
     613                 :            :     }
     614                 :            :   }
     615                 :     888244 :   u = modii(u, mod);
     616                 :     888244 :   avma = av; z = cgetg(5,t_PADIC);
     617                 :     888244 :   z[1] = evalprecp(r) | evalvalp(e);
     618                 :     888244 :   gel(z,2) = icopy(p);
     619                 :     888244 :   gel(z,3) = icopy(mod);
     620                 :     939008 :   gel(z,4) = icopy(u); return z;
     621                 :            : }
     622                 :            : 
     623                 :            : /* return x + y, where y t_PADIC and x is a non-zero t_INT or t_FRAC */
     624                 :            : static GEN
     625                 :      94380 : addQp(GEN x, GEN y)
     626                 :            : {
     627                 :      94380 :   pari_sp av = avma;
     628                 :      94380 :   long tx,d,r,e, vy = valp(y), py = precp(y);
     629                 :      94380 :   GEN z,q,p1,p2,mod,u, p = gel(y,2);
     630                 :            : 
     631                 :      94380 :   tx = typ(x);
     632                 :      94367 :   e = (tx == t_INT)? Z_pvalrem(x,p,&p1)
     633         [ +  + ]:      95906 :                    : Z_pvalrem(gel(x,1),p,&p1) -
     634                 :       1526 :                      Z_pvalrem(gel(x,2),p,&p2);
     635                 :      94367 :   d = vy - e; r = d + py;
     636         [ +  + ]:      94367 :   if (r <= 0) { avma = av; return gcopy(y); }
     637                 :      94150 :   mod = gel(y,3);
     638                 :      94150 :   u   = gel(y,4);
     639                 :      94150 :   (void)new_chunk(5 + ((lgefint(mod) + lgefint(p)*labs(d)) << 1));
     640                 :            : 
     641         [ +  + ]:      94173 :   if (d > 0)
     642                 :            :   {
     643                 :      84753 :     q = powiu(p,d);
     644                 :      84737 :     mod = mulii(mod, q);
     645                 :      84738 :     u   = mulii(u, q);
     646 [ +  + ][ +  + ]:      84737 :     if (tx != t_INT && !is_pm1(p2)) p1 = mulii(p1, Fp_inv(p2,mod));
     647                 :      84737 :     u = addii(u, p1);
     648                 :            :   }
     649         [ +  + ]:       9420 :   else if (d < 0)
     650                 :            :   {
     651                 :       1837 :     q = powiu(p,-d);
     652 [ +  + ][ +  + ]:       1837 :     if (tx != t_INT && !is_pm1(p2)) p1 = mulii(p1, Fp_inv(p2,mod));
     653                 :       1837 :     p1 = mulii(p1, q);
     654                 :       1835 :     u = addii(u, p1);
     655                 :       1835 :     r = py; e = vy;
     656                 :            :   }
     657                 :            :   else
     658                 :            :   {
     659                 :            :     long c;
     660 [ +  + ][ +  + ]:       7583 :     if (tx != t_INT && !is_pm1(p2)) p1 = mulii(p1, Fp_inv(p2,mod));
     661                 :       7583 :     u = addii(u, p1);
     662 [ +  + ][ +  + ]:       7583 :     if (!signe(u) || (c = Z_pvalrem(u,p,&u)) >= r)
     663                 :            :     {
     664                 :        399 :       avma = av; return zeropadic(p,e+r);
     665                 :            :     }
     666         [ +  + ]:       7184 :     if (c)
     667                 :            :     {
     668                 :       4672 :       mod = diviiexact(mod, powiu(p,c));
     669                 :       4672 :       r -= c;
     670                 :       4672 :       e += c;
     671                 :            :     }
     672                 :            :   }
     673                 :      93756 :   u = modii(u, mod);
     674                 :      93760 :   avma = av; z = cgetg(5,t_PADIC);
     675                 :      93780 :   z[1] = evalprecp(r) | evalvalp(e);
     676                 :      93779 :   gel(z,2) = icopy(p);
     677                 :      93784 :   gel(z,3) = icopy(mod);
     678                 :      94392 :   gel(z,4) = icopy(u); return z;
     679                 :            : }
     680                 :            : 
     681                 :            : /* Mod(x,X) + Mod(y,X) */
     682                 :            : #define addsub_polmod_same addsub_polmod_scal
     683                 :            : /* Mod(x,X) +/- Mod(y,Y) */
     684                 :            : static GEN
     685                 :        973 : addsub_polmod(GEN X, GEN Y, GEN x, GEN y, GEN(*op)(GEN,GEN))
     686                 :            : {
     687                 :        973 :   long T[3] = { evaltyp(t_POLMOD) | _evallg(3),0,0 };
     688                 :        973 :   GEN z = cgetg(3,t_POLMOD);
     689                 :        973 :   long vx = varn(X), vy = varn(Y);
     690         [ +  + ]:        973 :   if (vx==vy) {
     691                 :            :     pari_sp av;
     692                 :         14 :     gel(z,1) = RgX_gcd(X,Y); av = avma;
     693                 :         14 :     warn_coercion(X,Y,gel(z,1));
     694                 :         14 :     gel(z,2) = gerepileupto(av, gmod(op(x, y), gel(z,1))); return z;
     695                 :            :   }
     696         [ +  - ]:        959 :   if (varncmp(vx, vy) < 0)
     697                 :        959 :   { gel(z,1) = RgX_copy(X); gel(T,1) = Y; gel(T,2) = y; y = T; }
     698                 :            :   else
     699                 :          0 :   { gel(z,1) = RgX_copy(Y); gel(T,1) = X; gel(T,2) = x; x = T; }
     700                 :        973 :   gel(z,2) = op(x, y); return z;
     701                 :            : }
     702                 :            : /* Mod(y, Y) +/- x,  x scalar or polynomial in same var and reduced degree */
     703                 :            : static GEN
     704                 :    2720692 : addsub_polmod_scal(GEN Y, GEN y, GEN x, GEN(*op)(GEN,GEN))
     705                 :            : {
     706                 :    2720692 :   GEN z = cgetg(3,t_POLMOD);
     707                 :    2720692 :   gel(z,1) = RgX_copy(Y);
     708                 :    2720692 :   gel(z,2) = op(y, x); return z;
     709                 :            : }
     710                 :            : 
     711                 :            : /* typ(y) == t_SER, x "scalar" [e.g object in lower variable] */
     712                 :            : static GEN
     713                 :       5992 : add_ser_scal(GEN y, GEN x)
     714                 :            : {
     715                 :            :   long i, l, ly, vy;
     716                 :            :   GEN z;
     717                 :            : 
     718         [ +  + ]:       5992 :   if (isrationalzero(x)) return gcopy(y);
     719                 :       5474 :   ly = lg(y);
     720                 :       5474 :   l = valp(y);
     721         [ +  + ]:       5474 :   if (l < 3-ly) return gcopy(y);
     722                 :            :   /* l + ly >= 3 */
     723         [ +  + ]:       5453 :   if (l < 0)
     724                 :            :   {
     725                 :        301 :     z = cgetg(ly,t_SER); z[1] = y[1];
     726         [ +  + ]:       1148 :     for (i = 2; i <= 1-l; i++) gel(z,i) = gcopy(gel(y,i));
     727                 :        301 :     gel(z,i) = gadd(x,gel(y,i)); i++;
     728         [ +  + ]:       1400 :     for (     ; i < ly; i++)   gel(z,i) = gcopy(gel(y,i));
     729                 :        301 :     return z;
     730                 :            :   }
     731                 :       5152 :   vy = varn(y);
     732         [ +  + ]:       5152 :   if (l > 0)
     733                 :            :   {
     734         [ +  + ]:       3612 :     if (ser_isexactzero(y))
     735         [ +  + ]:       1120 :       return scalarser(ly == 2? x: gadd(x,gel(y,2)), vy, l);
     736                 :       2492 :     y -= l; ly += l;
     737                 :       2492 :     z = cgetg(ly,t_SER);
     738                 :       2492 :     x = gcopy(x);
     739         [ +  + ]:       4207 :     for (i=3; i<=l+1; i++) gel(z,i) = gen_0;
     740                 :            :   }
     741                 :            :   else
     742                 :            :   { /* l = 0, ly >= 3. Also OK if ser_isexactzero(y) */
     743                 :       1540 :     z = cgetg(ly,t_SER);
     744                 :       1540 :     x = gadd(x, gel(y,2));
     745                 :       1540 :     i = 3;
     746                 :            :   }
     747         [ +  + ]:      50988 :   for (; i<ly; i++) gel(z,i) = gcopy(gel(y,i));
     748                 :       4032 :   gel(z,2) = x;
     749                 :       4032 :   z[1] = evalsigne(1) | _evalvalp(0) | evalvarn(vy);
     750         [ +  + ]:       5992 :   return gequal0(x)? normalize(z): z;
     751                 :            : }
     752                 :            : static long
     753         [ +  + ]:     501604 : serprec(GEN x) { return ser_isexactzero(x)? 2: lg(x); }
     754                 :            : /* x,y t_SER in the same variable: x+y */
     755                 :            : static GEN
     756                 :     251173 : ser_add(GEN x, GEN y)
     757                 :            : {
     758                 :     251173 :   long i, lx,ly, n = valp(y) - valp(x);
     759                 :            :   GEN z;
     760         [ +  + ]:     251173 :   if (n < 0) { n = -n; swap(x,y); }
     761                 :            :   /* valp(x) <= valp(y) */
     762                 :     251173 :   lx = serprec(x);
     763         [ +  + ]:     251173 :   if (lx == 2) /* don't lose type information */
     764                 :        742 :     return scalarser(gadd(RgX_get_0(x), RgX_get_0(y)), varn(x), valp(x));
     765         [ +  + ]:     250431 :   ly = serprec(y) + n; if (lx < ly) ly = lx;
     766         [ +  + ]:     250431 :   if (n)
     767                 :            :   {
     768         [ +  + ]:       8225 :     if (n+2 > lx) return gcopy(x);
     769                 :       7525 :     z = cgetg(ly,t_SER);
     770         [ +  + ]:      47334 :     for (i=2; i<=n+1; i++) gel(z,i) = gcopy(gel(x,i));
     771         [ +  + ]:      38773 :     for (   ; i < ly; i++) gel(z,i) = gadd(gel(x,i),gel(y,i-n));
     772                 :            :   } else {
     773                 :     242206 :     z = cgetg(ly,t_SER);
     774         [ +  + ]:    1072023 :     for (i=2; i < ly; i++) gel(z,i) = gadd(gel(x,i),gel(y,i));
     775                 :            :   }
     776                 :     251173 :   z[1] = x[1]; return normalize(z);
     777                 :            : }
     778                 :            : /* typ(y) == RFRAC, x polynomial in same variable or "scalar" */
     779                 :            : static GEN
     780                 :    8350047 : add_rfrac_scal(GEN y, GEN x)
     781                 :            : {
     782                 :            :   pari_sp av;
     783                 :            :   GEN n;
     784                 :            : 
     785         [ +  + ]:    8350047 :   if (isintzero(x)) return gcopy(y); /* frequent special case */
     786                 :    4625035 :   av = avma; n = gadd(gmul(x, gel(y,2)), gel(y,1));
     787                 :    8350047 :   return gerepileupto(av, gred_rfrac_simple(n, gel(y,2)));
     788                 :            : }
     789                 :            : 
     790                 :            : /* x "scalar", ty != t_MAT and non-scalar */
     791                 :            : static GEN
     792                 :   13652669 : add_scal(GEN y, GEN x, long ty)
     793                 :            : {
     794   [ +  +  +  -  :   13652669 :   switch(ty)
                   +  - ]
     795                 :            :   {
     796                 :    9195583 :     case t_POL: return RgX_Rg_add(y, x);
     797                 :       5992 :     case t_SER: return add_ser_scal(y, x);
     798                 :    4241052 :     case t_RFRAC: return add_rfrac_scal(y, x);
     799                 :          0 :     case t_COL: return RgC_Rg_add(y, x);
     800                 :            :     case t_VEC:
     801         [ +  - ]:     210042 :       if (isintzero(x)) return gcopy(y);
     802                 :          0 :       break;
     803                 :            :   }
     804                 :          0 :   pari_err_TYPE2("+",x,y);
     805                 :   13652669 :   return NULL; /* not reached */
     806                 :            : }
     807                 :            : 
     808                 :            : static GEN
     809                 :   19657431 : addsub_frac(GEN x, GEN y, GEN (*op)(GEN,GEN))
     810                 :            : {
     811                 :   19657431 :   pari_sp av = avma;
     812                 :   19657431 :   GEN x1 = gel(x,1), x2 = gel(x,2), z = cgetg(3,t_FRAC);
     813                 :   19657431 :   GEN y1 = gel(y,1), y2 = gel(y,2), q, r, n, d, delta;
     814                 :   19657431 :   int s = cmpii(x2, y2);
     815                 :            : 
     816         [ +  + ]:   19657431 :   if (!s)
     817                 :            :   { /* common denominator: (x1 op y1) / x2 */
     818                 :    8702208 :     n = op(x1, y1);
     819         [ +  + ]:    8702208 :     if (!signe(n)) { avma = av; return gen_0; }
     820                 :    8296706 :     d = x2;
     821                 :    8296706 :     q = dvmdii(n, d, &r);
     822         [ +  + ]:    8296706 :     if (r == gen_0) { avma = av; return icopy(q); }
     823                 :    7876895 :     r = gcdii(d, r);
     824         [ +  + ]:    7876895 :     if (!is_pm1(r)) { n = diviiexact(n, r); d = diviiexact(d, r); }
     825                 :    7876895 :     gel(z,1) = icopy_avma(n, (pari_sp)z);
     826                 :    7876895 :     gel(z,2) = icopy_avma(d, (pari_sp)gel(z,1));
     827                 :    7876895 :     avma = (pari_sp)gel(z,2); return z;
     828                 :            :   }
     829         [ +  + ]:   10955223 :   if (s < 0)
     830                 :            :   {
     831                 :    4906430 :     GEN Q = dvmdii(y2, x2, &r);
     832         [ +  + ]:    4906430 :     if (r == gen_0)
     833                 :            :     { /* y2 = Q x2: 1/x2 . (Q x1 op y1)/Q, where latter is in coprime form */
     834                 :    3873644 :       pari_sp av = avma;
     835                 :    3873644 :       n = op(mulii(Q,x1), y1);
     836                 :    3873644 :       q = dvmdii(n, x2, &r);
     837         [ +  + ]:    3873644 :       if (r == gen_0)
     838                 :            :       {
     839                 :     621419 :         gel(z,1) = gerepileuptoint(av, q);
     840                 :     621419 :         gel(z,2) = Q; return z;
     841                 :            :       }
     842                 :    3252225 :       r = gcdii(x2, r);
     843         [ +  + ]:    3252225 :       if (!is_pm1(r)) { n = diviiexact(n, r); x2 = diviiexact(x2, r); }
     844                 :    3252225 :       d = mulii(x2,Q);
     845                 :    3252225 :       gel(z,1) = icopy_avma(n, (pari_sp)z);
     846                 :    3252225 :       gel(z,2) = icopy_avma(d, (pari_sp)gel(z,1));
     847                 :    3252225 :       avma = (pari_sp)gel(z,2); return z;
     848                 :            :     }
     849                 :    1032786 :     delta = gcdii(x2,r);
     850                 :            :   }
     851                 :            :   else
     852                 :            :   {
     853                 :    6048793 :     GEN Q = dvmdii(x2, y2, &r);
     854         [ +  + ]:    6048793 :     if (r == gen_0)
     855                 :            :     { /* x2 = Q y2: 1/y2 . (x1 op Q y1)/Q, where latter is in coprime form */
     856                 :    4767045 :       pari_sp av = avma;
     857                 :    4767045 :       n = op(x1, mulii(Q,y1));
     858                 :    4767045 :       q = dvmdii(n, y2, &r);
     859         [ +  + ]:    4767045 :       if (r == gen_0)
     860                 :            :       {
     861                 :      72136 :         gel(z,1) = gerepileuptoint(av, q);
     862                 :      72136 :         gel(z,2) = Q; return z;
     863                 :            :       }
     864                 :    4694909 :       r = gcdii(y2, r);
     865         [ +  + ]:    4694909 :       if (!is_pm1(r)) { n = diviiexact(n, r); y2 = diviiexact(y2, r); }
     866                 :    4694909 :       d = mulii(y2,Q);
     867                 :    4694909 :       gel(z,1) = icopy_avma(n, (pari_sp)z);
     868                 :    4694909 :       gel(z,2) = icopy_avma(d, (pari_sp)gel(z,1));
     869                 :    4694909 :       avma = (pari_sp)gel(z,2); return z;
     870                 :            :     }
     871                 :    1281748 :     delta = gcdii(y2,r);
     872                 :            :   }
     873                 :            :   /* delta = gcd(x2,y2) */
     874         [ +  + ]:    2314534 :   if (is_pm1(delta))
     875                 :            :   { /* numerator is non-zero */
     876                 :     129545 :     gel(z,1) = gerepileuptoint((pari_sp)z, op(mulii(x1,y2), mulii(y1,x2)));
     877                 :     129545 :     gel(z,2) = mulii(x2,y2); return z;
     878                 :            :   }
     879                 :    2184989 :   x2 = diviiexact(x2,delta);
     880                 :    2184989 :   y2 = diviiexact(y2,delta);
     881                 :    2184989 :   n = op(mulii(x1,y2), mulii(y1,x2));
     882         [ -  + ]:    2184989 :   if (!signe(n)) { avma = av; return gen_0; }
     883                 :    2184989 :   d = mulii(x2, y2);
     884                 :    2184989 :   q = dvmdii(n, delta, &r);
     885         [ +  + ]:    2184989 :   if (r == gen_0)
     886                 :            :   {
     887         [ -  + ]:     109801 :     if (is_pm1(d)) { avma = av; return icopy(q); }
     888                 :     109801 :     avma = (pari_sp)z;
     889                 :     109801 :     gel(z,2) = icopy(d);
     890                 :     109801 :     gel(z,1) = icopy(q); return z;
     891                 :            :   }
     892                 :    2075188 :   r = gcdii(delta, r);
     893         [ +  + ]:    2075188 :   if (!is_pm1(r))
     894                 :            :   {
     895                 :     735119 :     n     = diviiexact(n, r);
     896                 :     735119 :     delta = diviiexact(delta, r);
     897                 :            :   }
     898                 :    2075188 :   d = mulii(d,delta); avma = (pari_sp)z;
     899                 :    2075188 :   gel(z,1) = icopy(n);
     900                 :   19657431 :   gel(z,2) = icopy(d); return z;
     901                 :            : }
     902                 :            : 
     903                 :            : /* assume x2, y2 are t_POLs in the same variable */
     904                 :            : static GEN
     905                 :    2781641 : add_rfrac(GEN x, GEN y)
     906                 :            : {
     907                 :    2781641 :   pari_sp av = avma;
     908                 :    2781641 :   GEN x1 = gel(x,1), x2 = gel(x,2);
     909                 :    2781641 :   GEN y1 = gel(y,1), y2 = gel(y,2), q, r, n, d, delta;
     910                 :            : 
     911                 :    2781641 :   delta = RgX_gcd(x2,y2);
     912         [ +  + ]:    2781641 :   if (!degpol(delta))
     913                 :            :   {
     914                 :        602 :     n = simplify_shallow( gadd(gmul(x1,y2), gmul(y1,x2)) );
     915                 :        602 :     d = RgX_mul(x2, y2);
     916                 :        602 :     return gerepileupto(av, gred_rfrac_simple(n, d));
     917                 :            :   }
     918                 :    2781039 :   x2 = RgX_div(x2,delta);
     919                 :    2781039 :   y2 = RgX_div(y2,delta);
     920                 :    2781039 :   n = gadd(gmul(x1,y2), gmul(y1,x2));
     921         [ +  + ]:    2781039 :   if (!signe(n))
     922                 :            :   {
     923                 :     680797 :     n = simplify_shallow(n);
     924         [ +  + ]:     680797 :     if (isrationalzero(n)) return gerepileupto(av, n);
     925                 :          7 :     return gerepilecopy(av, mkrfrac(n, RgX_mul(gel(x,2),y2)));
     926                 :            :   }
     927         [ +  + ]:    2100242 :   if (degpol(n) == 0)
     928                 :    1138189 :     return gerepileupto(av, gred_rfrac_simple(gel(n,2), RgX_mul(gel(x,2),y2)));
     929                 :     962053 :   q = RgX_divrem(n, delta, &r); /* we want gcd(n,delta) */
     930         [ +  + ]:     962053 :   if (isexactzero(r))
     931                 :            :   {
     932                 :            :     GEN z;
     933                 :     208991 :     d = RgX_mul(x2, y2);
     934                 :            :     /* "constant" denominator ? */
     935         [ +  + ]:     208991 :     z = lg(d) == 3? RgX_Rg_div(q, gel(d,2)): gred_rfrac_simple(q, d);
     936                 :     208991 :     return gerepileupto(av, z);
     937                 :            :   }
     938                 :     753062 :   r = RgX_gcd(delta, r);
     939         [ +  + ]:     753062 :   if (degpol(r))
     940                 :            :   {
     941                 :     148378 :     n = RgX_div(n, r);
     942                 :     148378 :     d = RgX_mul(RgX_mul(x2,y2), RgX_div(delta, r));
     943                 :            :   }
     944                 :            :   else
     945                 :     604684 :     d = RgX_mul(gel(x,2), y2);
     946                 :    2781641 :   return gerepileupto(av, gred_rfrac_simple(n, d));
     947                 :            : }
     948                 :            : 
     949                 :            : GEN
     950                 :  825075686 : gadd(GEN x, GEN y)
     951                 :            : {
     952                 :  825075686 :   long tx = typ(x), ty = typ(y), vx, vy, lx, i, l;
     953                 :            :   pari_sp av, tetpil;
     954                 :            :   GEN z, p1;
     955                 :            : 
     956 [ +  + ][ +  +  :  825075686 :   if (tx == ty) switch(tx) /* shortcut to generic case */
          +  +  +  +  +  
          +  +  +  +  +  
             +  +  +  - ]
     957                 :            :   {
     958                 :  425538273 :     case t_INT: return addii(x,y);
     959                 :  205232096 :     case t_REAL: return addrr(x,y);
     960                 :     584889 :     case t_INTMOD:  { GEN X = gel(x,1), Y = gel(y,1);
     961                 :     584889 :       z = cgetg(3,t_INTMOD);
     962 [ +  + ][ +  + ]:     584881 :       if (X==Y || equalii(X,Y))
     963                 :     584879 :         return add_intmod_same(z, X, gel(x,2), gel(y,2));
     964                 :         14 :       gel(z,1) = gcdii(X,Y);
     965                 :         14 :       warn_coercion(X,Y,gel(z,1));
     966                 :         14 :       av = avma; p1 = addii(gel(x,2),gel(y,2));
     967                 :         14 :       gel(z,2) = gerepileuptoint(av, remii(p1, gel(z,1))); return z;
     968                 :            :     }
     969                 :   13073592 :     case t_FRAC: return addsub_frac(x,y,addii);
     970                 :   25040527 :     case t_COMPLEX: z = cgetg(3,t_COMPLEX);
     971                 :   25040527 :       gel(z,2) = gadd(gel(x,2),gel(y,2));
     972         [ +  + ]:   25040527 :       if (isintzero(gel(z,2)))
     973                 :            :       {
     974                 :        273 :         avma = (pari_sp)(z+3);
     975                 :        273 :         return gadd(gel(x,1),gel(y,1));
     976                 :            :       }
     977                 :   25040254 :       gel(z,1) = gadd(gel(x,1),gel(y,1));
     978                 :   25040254 :       return z;
     979                 :            :     case t_PADIC:
     980         [ -  + ]:     927514 :       if (!equalii(gel(x,2),gel(y,2))) pari_err_OP("+",x,y);
     981                 :     927514 :       return addsub_pp(x,y, addii);
     982                 :        301 :     case t_QUAD: z = cgetg(4,t_QUAD);
     983         [ -  + ]:        301 :       if (!ZX_equal(gel(x,1),gel(y,1))) pari_err_OP("+",x,y);
     984                 :        301 :       gel(z,1) = ZX_copy(gel(x,1));
     985                 :        301 :       gel(z,2) = gadd(gel(x,2),gel(y,2));
     986                 :        301 :       gel(z,3) = gadd(gel(x,3),gel(y,3)); return z;
     987                 :            :     case t_POLMOD:
     988         [ +  + ]:    1229845 :       if (RgX_equal_var(gel(x,1), gel(y,1)))
     989                 :    1228907 :         return addsub_polmod_same(gel(x,1), gel(x,2), gel(y,2), &gadd);
     990                 :        938 :       return addsub_polmod(gel(x,1), gel(y,1), gel(x,2), gel(y,2), &gadd);
     991                 :     629444 :     case t_FFELT: return FF_add(x,y);
     992                 :            :     case t_POL:
     993                 :   14936938 :       vx = varn(x);
     994                 :   14936938 :       vy = varn(y);
     995         [ +  + ]:   14936938 :       if (vx != vy) {
     996         [ +  + ]:     790981 :         if (varncmp(vx, vy) < 0) return RgX_Rg_add(x, y);
     997                 :      19168 :         else                     return RgX_Rg_add(y, x);
     998                 :            :       }
     999                 :   14145957 :       return RgX_add(x, y);
    1000                 :            :     case t_SER:
    1001                 :     248485 :       vx = varn(x);
    1002                 :     248485 :       vy = varn(y);
    1003         [ -  + ]:     248485 :       if (vx != vy) {
    1004         [ #  # ]:          0 :         if (varncmp(vx, vy) < 0) return add_ser_scal(x, y);
    1005                 :          0 :         else                     return add_ser_scal(y, x);
    1006                 :            :       }
    1007                 :     248485 :       return ser_add(x, y);
    1008                 :            :     case t_RFRAC:
    1009                 :    4073544 :       vx = varn(gel(x,2));
    1010                 :    4073544 :       vy = varn(gel(y,2));
    1011         [ +  + ]:    4073544 :       if (vx != vy) {
    1012         [ +  + ]:    1291903 :         if (varncmp(vx, vy) < 0) return add_rfrac_scal(x, y);
    1013                 :     536802 :         else                     return add_rfrac_scal(y, x);
    1014                 :            :       }
    1015                 :    2781641 :       return add_rfrac(x,y);
    1016                 :            :     case t_VEC:
    1017         [ -  + ]:     454494 :       if (lg(y) != lg(x)) pari_err_OP("+",x,y);
    1018                 :     454494 :       return RgV_add(x,y);
    1019                 :            :     case t_COL:
    1020         [ -  + ]:    4345540 :       if (lg(y) != lg(x)) pari_err_OP("+",x,y);
    1021                 :    4345540 :       return RgC_add(x,y);
    1022                 :            :     case t_MAT:
    1023                 :       1078 :       lx = lg(x);
    1024         [ -  + ]:       1078 :       if (lg(y) != lx) pari_err_OP("+",x,y);
    1025         [ -  + ]:       1078 :       if (lx == 1) return cgetg(1, t_MAT);
    1026         [ +  + ]:       1078 :       if (lgcols(y) != lgcols(x)) pari_err_OP("+",x,y);
    1027                 :       1071 :       return RgM_add(x,y);
    1028                 :            : 
    1029                 :          0 :     default: pari_err_TYPE2("+",x,y);
    1030                 :            :   }
    1031                 :            :   /* tx != ty */
    1032         [ +  + ]:  128760632 :   if (tx > ty) { swap(x,y); lswap(tx,ty); }
    1033                 :            : 
    1034 [ +  + ][ +  +  :  128760632 :   if (is_const_t(ty)) switch(tx) /* tx < ty, is_const_t(tx) && is_const_t(ty) */
          +  +  -  +  -  
                      + ]
    1035                 :            :   {
    1036                 :            :     case t_INT:
    1037   [ +  +  +  +  :   98412907 :       switch(ty)
             +  +  +  + ]
    1038                 :            :       {
    1039                 :   61198954 :         case t_REAL: return addir(x,y);
    1040                 :            :         case t_INTMOD:
    1041                 :     424069 :           z = cgetg(3, t_INTMOD);
    1042                 :     424069 :           return add_intmod_same(z, gel(y,1), gel(y,2), modii(x, gel(y,1)));
    1043                 :    8036746 :         case t_FRAC: z = cgetg(3,t_FRAC);
    1044                 :    8036746 :           gel(z,1) = gerepileuptoint((pari_sp)z, addii(gel(y,1), mulii(gel(y,2),x)));
    1045                 :    8036746 :           gel(z,2) = icopy(gel(y,2)); return z;
    1046                 :   28416685 :         case t_COMPLEX: return addRc(x, y);
    1047                 :            :         case t_PADIC:
    1048         [ +  + ]:     101693 :           if (!signe(x)) return gcopy(y);
    1049                 :      92859 :           return addQp(x,y);
    1050                 :        588 :         case t_QUAD: return addRq(x, y);
    1051                 :     234169 :         case t_FFELT: return FF_Z_add(y,x);
    1052                 :            :       }
    1053                 :            : 
    1054                 :            :     case t_REAL:
    1055   [ +  +  +  - ]:   12998580 :       switch(ty)
    1056                 :            :       {
    1057                 :            :         case t_FRAC:
    1058         [ -  + ]:     972492 :           if (!signe(gel(y,1))) return rcopy(x);
    1059         [ +  + ]:     972492 :           if (!signe(x))
    1060                 :            :           {
    1061                 :      12348 :             lx = expi(gel(y,1)) - expi(gel(y,2)) - expo(x);
    1062         [ -  + ]:      12348 :             return lx <= 0? rcopy(x): fractor(y, nbits2prec(lx));
    1063                 :            :           }
    1064                 :     960144 :           av=avma; z=addir(gel(y,1),mulir(gel(y,2),x)); tetpil=avma;
    1065                 :     960144 :           return gerepile(av,tetpil,divri(z,gel(y,2)));
    1066                 :   12026081 :         case t_COMPLEX: return addRc(x, y);
    1067         [ -  + ]:          7 :         case t_QUAD: return gequal0(y)? rcopy(x): addqf(y, x, lg(x));
    1068                 :            : 
    1069                 :          0 :         default: pari_err_TYPE2("+",x,y);
    1070                 :            :       }
    1071                 :            : 
    1072                 :            :     case t_INTMOD:
    1073   [ +  +  +  -  :       3964 :       switch(ty)
                   +  - ]
    1074                 :            :       {
    1075                 :       3500 :         case t_FRAC: { GEN X = gel(x,1);
    1076                 :       3500 :           z = cgetg(3, t_INTMOD);
    1077                 :       3500 :           p1 = Fp_div(gel(y,1), gel(y,2), X);
    1078                 :       3500 :           return add_intmod_same(z, X, p1, gel(x,2));
    1079                 :            :         }
    1080                 :            :         case t_FFELT:
    1081         [ -  + ]:        394 :           if (!equalii(gel(x,1),FF_p_i(y)))
    1082                 :          0 :             pari_err_OP("+",x,y);
    1083                 :        394 :           return FF_Z_add(y,gel(x,2));
    1084                 :         56 :         case t_COMPLEX: return addRc(x, y);
    1085                 :          0 :         case t_PADIC: { GEN X = gel(x,1);
    1086                 :          0 :           z = cgetg(3, t_INTMOD);
    1087                 :          0 :           return add_intmod_same(z, X, gel(x,2), padic_to_Fp(y, X));
    1088                 :            :         }
    1089                 :         14 :         case t_QUAD: return addRq(x, y);
    1090                 :            :       }
    1091                 :            : 
    1092                 :            :     case t_FRAC:
    1093   [ +  +  -  +  :     221655 :       switch (ty)
                      - ]
    1094                 :            :       {
    1095                 :     218687 :         case t_COMPLEX: return addRc(x, y);
    1096                 :            :         case t_PADIC:
    1097         [ -  + ]:       1526 :           if (!signe(gel(x,1))) return gcopy(y);
    1098                 :       1526 :           return addQp(x,y);
    1099                 :          0 :         case t_QUAD: return addRq(x, y);
    1100                 :       1442 :         case t_FFELT: return FF_Q_add(y, x);
    1101                 :            :       }
    1102                 :            : 
    1103                 :            :     case t_FFELT:
    1104                 :          0 :       pari_err_TYPE2("+",x,y);
    1105                 :            : 
    1106                 :            :     case t_COMPLEX:
    1107      [ +  +  - ]:         28 :       switch(ty)
    1108                 :            :       {
    1109                 :            :         case t_PADIC:
    1110         [ +  + ]:         21 :           return Zp_nosquare_m1(gel(y,2))? addRc(y, x): addTp(x, y);
    1111                 :            :         case t_QUAD:
    1112         [ -  + ]:          7 :           lx = precision(x); if (!lx) pari_err_OP("+",x,y);
    1113         [ -  + ]:          7 :           return gequal0(y)? gcopy(x): addqf(y, x, lx);
    1114                 :            :       }
    1115                 :            : 
    1116                 :            :     case t_PADIC: /* ty == t_QUAD */
    1117         [ #  # ]:          0 :       return (kro_quad(y,gel(x,2)) == -1)? addRq(x, y): addTp(y, x);
    1118                 :            :   }
    1119                 :            :   /* tx < ty, !is_const_t(y) */
    1120   [ +  +  +  + ]:   17123508 :   switch(ty)
    1121                 :            :   {
    1122                 :            :     case t_MAT:
    1123         [ -  + ]:      12915 :       if (is_matvec_t(tx)) pari_err_TYPE2("+",x,y);
    1124         [ +  + ]:      12915 :       if (isrationalzero(x)) return gcopy(y);
    1125                 :      12803 :       return RgM_Rg_add(y, x);
    1126                 :            :     case t_COL:
    1127         [ -  + ]:      33546 :       if (tx == t_VEC) pari_err_TYPE2("+",x,y);
    1128                 :      33546 :       return RgC_Rg_add(y, x);
    1129                 :            :     case t_POLMOD: /* is_const_t(tx) in this case */
    1130                 :     600356 :       return addsub_polmod_scal(gel(y,1), gel(y,2), x, &gadd);
    1131                 :            :   }
    1132         [ +  + ]:   16476691 :   if (is_scalar_t(tx))  {
    1133         [ +  + ]:   13653470 :     if (tx == t_POLMOD)
    1134                 :            :     {
    1135                 :      21882 :       vx = varn(gel(x,1));
    1136                 :      21882 :       vy = gvar(y);
    1137         [ +  + ]:      21882 :       if (vx == vy) y = gmod(y, gel(x,1)); /* error if ty == t_SER */
    1138                 :            :       else
    1139         [ +  + ]:      18074 :         if (varncmp(vx,vy) > 0) return add_scal(y, x, ty);
    1140                 :       3871 :       return addsub_polmod_scal(gel(x,1), gel(x,2), y, &gadd);
    1141                 :            :     }
    1142                 :   13631588 :     return add_scal(y, x, ty);
    1143                 :            :   }
    1144                 :            :   /* x and y are not scalars, ty != t_MAT */
    1145                 :    2823221 :   vx = gvar(x);
    1146                 :    2823221 :   vy = gvar(y);
    1147         [ +  + ]:    2823221 :   if (vx != vy) { /* x or y is treated as a scalar */
    1148 [ +  - ][ +  + ]:       3077 :     if (is_vec_t(tx) || is_vec_t(ty)) pari_err_TYPE2("+",x,y);
    1149                 :       6140 :     return (varncmp(vx, vy) < 0)? add_scal(x, y, tx)
    1150         [ +  + ]:       3070 :                                 : add_scal(y, x, ty);
    1151                 :            :   }
    1152                 :            :   /* vx = vy */
    1153      [ +  +  - ]:    2820144 :   switch(tx)
    1154                 :            :   {
    1155                 :            :     case t_POL:
    1156      [ +  +  - ]:    2819794 :       switch (ty)
    1157                 :            :       {
    1158                 :            :         case t_SER:
    1159         [ +  + ]:       2702 :           if (lg(x) == 2) return gcopy(y);
    1160                 :       2688 :           i = lg(y) + valp(y) - RgX_val(x);
    1161         [ -  + ]:       2688 :           if (i < 3) return gcopy(y);
    1162                 :            : 
    1163                 :       2688 :           p1 = RgX_to_ser(x,i); y = ser_add(p1,y);
    1164                 :       2688 :           settyp(p1, t_VECSMALL); /* p1 left on stack */
    1165                 :       2688 :           return y;
    1166                 :            : 
    1167                 :    2817092 :         case t_RFRAC: return add_rfrac_scal(y, x);
    1168                 :            :       }
    1169                 :          0 :       break;
    1170                 :            : 
    1171                 :            :     case t_SER:
    1172         [ +  - ]:        350 :       if (ty == t_RFRAC)
    1173                 :            :       {
    1174                 :            :         GEN n, d;
    1175                 :            :         long vn, vd;
    1176                 :        350 :         av = avma;
    1177                 :        350 :         n = gel(y,1); vn = gval(n, vy);
    1178                 :        350 :         d = gel(y,2); vd = RgX_valrem(d, &d);
    1179                 :            : 
    1180                 :        350 :         l = lg(x) + valp(x) - (vn - vd);
    1181         [ -  + ]:        350 :         if (l < 3) { avma = av; return gcopy(x); }
    1182                 :            : 
    1183                 :            :         /* take advantage of y = t^n ! */
    1184         [ +  + ]:        350 :         if (degpol(d))
    1185                 :         63 :           y = gdiv(n, RgX_to_ser_inexact(d,l));
    1186                 :            :         else {
    1187                 :        287 :           y = gdiv(n, gel(d,2));
    1188         [ +  + ]:        287 :           if (gvar(y) == vy) y = RgX_to_ser(y,l); else y = scalarser(y, vy, l);
    1189                 :            :         }
    1190                 :        350 :         setvalp(y, valp(y) - vd);
    1191                 :        350 :         return gerepileupto(av, gadd(y, x));
    1192                 :            :       }
    1193                 :          0 :       break;
    1194                 :            :   }
    1195                 :          0 :   pari_err_TYPE2("+",x,y);
    1196                 :  825064188 :   return NULL; /* not reached */
    1197                 :            : }
    1198                 :            : 
    1199                 :            : GEN
    1200                 :   14318976 : gaddsg(long x, GEN y)
    1201                 :            : {
    1202                 :   14318976 :   long ty = typ(y);
    1203                 :            :   GEN z;
    1204                 :            : 
    1205   [ +  +  +  +  :   14318976 :   switch(ty)
                   +  + ]
    1206                 :            :   {
    1207                 :     272582 :     case t_INT:  return addsi(x,y);
    1208                 :    7257499 :     case t_REAL: return addsr(x,y);
    1209                 :            :     case t_INTMOD:
    1210                 :         14 :       z = cgetg(3, t_INTMOD);
    1211                 :         14 :       return add_intmod_same(z, gel(y,1), gel(y,2), modsi(x, gel(y,1)));
    1212                 :      37415 :     case t_FRAC: z = cgetg(3,t_FRAC);
    1213                 :      37415 :       gel(z,1) = gerepileuptoint((pari_sp)z, addii(gel(y,1), mulis(gel(y,2),x)));
    1214                 :      37415 :       gel(z,2) = icopy(gel(y,2)); return z;
    1215                 :            :     case t_COMPLEX:
    1216                 :    6395880 :       z = cgetg(3, t_COMPLEX);
    1217                 :    6395880 :       gel(z,1) = gaddsg(x, gel(y,1));
    1218                 :    6395880 :       gel(z,2) = gcopy(gel(y,2)); return z;
    1219                 :            : 
    1220                 :   14318976 :     default: return gadd(stoi(x), y);
    1221                 :            :   }
    1222                 :            : }
    1223                 :            : 
    1224                 :            : GEN
    1225                 :     296054 : gsubsg(long x, GEN y)
    1226                 :            : {
    1227                 :            :   GEN z, a, b;
    1228                 :            :   pari_sp av;
    1229                 :            : 
    1230   [ +  +  +  +  :     296054 :   switch(typ(y))
                   +  + ]
    1231                 :            :   {
    1232                 :     174582 :     case t_INT:  return subsi(x,y);
    1233                 :      53910 :     case t_REAL: return subsr(x,y);
    1234                 :            :     case t_INTMOD:
    1235                 :         49 :       z = cgetg(3, t_INTMOD); a = gel(y,1); b = gel(y,2);
    1236                 :         49 :       return add_intmod_same(z, a, Fp_neg(b,a), modsi(x, a));
    1237                 :       8190 :     case t_FRAC: z = cgetg(3,t_FRAC); a = gel(y,1); b = gel(y,2);
    1238                 :       8190 :       gel(z,1) = gerepileuptoint((pari_sp)z, subii(mulis(b,x), a));
    1239                 :       8190 :       gel(z,2) = icopy(gel(y,2)); return z;
    1240                 :            :     case t_COMPLEX:
    1241                 :      35824 :       z = cgetg(3, t_COMPLEX);
    1242                 :      35824 :       gel(z,1) = gsubsg(x, gel(y,1));
    1243                 :      35824 :       gel(z,2) = gneg(gel(y,2)); return z;
    1244                 :            :   }
    1245                 :      23499 :   av = avma;
    1246                 :     296054 :   return gerepileupto(av, gadd(stoi(x), gneg_i(y)));
    1247                 :            : }
    1248                 :            : 
    1249                 :            : /********************************************************************/
    1250                 :            : /**                                                                **/
    1251                 :            : /**                          SUBTRACTION                           **/
    1252                 :            : /**                                                                **/
    1253                 :            : /********************************************************************/
    1254                 :            : 
    1255                 :            : GEN
    1256                 : 1409613048 : gsub(GEN x, GEN y)
    1257                 :            : {
    1258                 : 1409613048 :   long tx = typ(x), ty = typ(y);
    1259                 :            :   pari_sp av;
    1260                 :            :   GEN z;
    1261 [ +  + ][ +  +  : 1409613048 :   if (tx == ty) switch(tx) /* shortcut to generic case */
          +  +  +  +  +  
          +  +  +  +  +  
                +  +  - ]
    1262                 :            :   {
    1263                 : 1242833731 :     case t_INT: return subii(x,y);
    1264                 :  124845266 :     case t_REAL: return subrr(x,y);
    1265                 :     122256 :     case t_INTMOD:  { GEN p1, X = gel(x,1), Y = gel(y,1);
    1266                 :     122256 :       z = cgetg(3,t_INTMOD);
    1267 [ +  + ][ +  + ]:     122256 :       if (X==Y || equalii(X,Y))
    1268                 :     122243 :         return sub_intmod_same(z, X, gel(x,2), gel(y,2));
    1269                 :         14 :       gel(z,1) = gcdii(X,Y);
    1270                 :         14 :       warn_coercion(X,Y,gel(z,1));
    1271                 :         14 :       av = avma; p1 = subii(gel(x,2),gel(y,2));
    1272                 :         14 :       gel(z,2) = gerepileuptoint(av, modii(p1, gel(z,1))); return z;
    1273                 :            :     }
    1274                 :    6583839 :     case t_FRAC: return addsub_frac(x,y, subii);
    1275                 :   13189404 :     case t_COMPLEX: z = cgetg(3,t_COMPLEX);
    1276                 :   13189404 :       gel(z,2) = gsub(gel(x,2),gel(y,2));
    1277         [ +  + ]:   13189404 :       if (isintzero(gel(z,2)))
    1278                 :            :       {
    1279                 :       5498 :         avma = (pari_sp)(z+3);
    1280                 :       5498 :         return gsub(gel(x,1),gel(y,1));
    1281                 :            :       }
    1282                 :   13183906 :       gel(z,1) = gsub(gel(x,1),gel(y,1));
    1283                 :   13183906 :       return z;
    1284                 :            :     case t_PADIC:
    1285         [ -  + ]:      11487 :       if (!equalii(gel(x,2),gel(y,2))) pari_err_OP("+",x,y);
    1286                 :      11487 :       return addsub_pp(x,y, subii);
    1287                 :        567 :     case t_QUAD: z = cgetg(4,t_QUAD);
    1288         [ -  + ]:        567 :       if (!ZX_equal(gel(x,1),gel(y,1))) pari_err_OP("+",x,y);
    1289                 :        567 :       gel(z,1) = ZX_copy(gel(x,1));
    1290                 :        567 :       gel(z,2) = gsub(gel(x,2),gel(y,2));
    1291                 :        567 :       gel(z,3) = gsub(gel(x,3),gel(y,3)); return z;
    1292                 :            :     case t_POLMOD:
    1293         [ +  + ]:     887593 :       if (RgX_equal_var(gel(x,1), gel(y,1)))
    1294                 :     887558 :         return addsub_polmod_same(gel(x,1), gel(x,2), gel(y,2), &gsub);
    1295                 :         35 :       return addsub_polmod(gel(x,1), gel(y,1), gel(x,2), gel(y,2), &gsub);
    1296                 :     183849 :     case t_FFELT: return FF_sub(x,y);
    1297                 :            :     case t_POL: {
    1298                 :    5007288 :       long vx = varn(x);
    1299                 :    5007288 :       long vy = varn(y);
    1300         [ +  + ]:    5007288 :       if (vx != vy) {
    1301         [ +  + ]:      11411 :         if (varncmp(vx, vy) < 0) return RgX_Rg_sub(x, y);
    1302                 :       1834 :         else                     return Rg_RgX_sub(x, y);
    1303                 :            :       }
    1304                 :    4995877 :       return RgX_sub(x, y);
    1305                 :            :     }
    1306                 :            :     case t_VEC:
    1307         [ -  + ]:      50855 :       if (lg(y) != lg(x)) pari_err_OP("+",x,y);
    1308                 :      50855 :       return RgV_sub(x,y);
    1309                 :            :     case t_COL:
    1310         [ -  + ]:    1156102 :       if (lg(y) != lg(x)) pari_err_OP("+",x,y);
    1311                 :    1156102 :       return RgC_sub(x,y);
    1312                 :            :     case t_MAT: {
    1313                 :       5320 :       long lx = lg(x);
    1314         [ -  + ]:       5320 :       if (lg(y) != lx) pari_err_OP("+",x,y);
    1315         [ -  + ]:       5320 :       if (lx == 1) return cgetg(1, t_MAT);
    1316         [ -  + ]:       5320 :       if (lgcols(y) != lgcols(x)) pari_err_OP("+",x,y);
    1317                 :       5320 :       return RgM_sub(x,y);
    1318                 :            :     }
    1319                 :    1706460 :     case t_RFRAC: case t_SER: break;
    1320                 :            : 
    1321                 :          0 :     default: pari_err_TYPE2("+",x,y);
    1322                 :            :   }
    1323                 :   14735491 :   av = avma;
    1324                 : 1410110821 :   return gerepileupto(av, gadd(x,gneg_i(y)));
    1325                 :            : }
    1326                 :            : 
    1327                 :            : /********************************************************************/
    1328                 :            : /**                                                                **/
    1329                 :            : /**                        MULTIPLICATION                          **/
    1330                 :            : /**                                                                **/
    1331                 :            : /********************************************************************/
    1332                 :            : static GEN
    1333                 :     189631 : mul_ser_scal(GEN y, GEN x) {
    1334                 :            :   long ly, i;
    1335                 :            :   GEN z;
    1336         [ +  + ]:     189631 :   if (isexactzero(x)) return gmul(RgX_get_0(y), x);
    1337         [ +  + ]:     188343 :   if (ser_isexactzero(y))
    1338                 :            :   {
    1339         [ +  - ]:        595 :     if (lg(y) == 2) return gcopy(y);
    1340                 :          0 :     return scalarser(gmul(x,gel(y,2)), varn(y), valp(y));
    1341                 :            :   }
    1342                 :     187748 :   z = cgetg_copy(y, &ly); z[1] = y[1];
    1343         [ +  + ]:     967451 :   for (i = 2; i < ly; i++) gel(z,i) = gmul(x,gel(y,i));
    1344                 :     189631 :   return normalize(z);
    1345                 :            : }
    1346                 :            : /* (n/d) * x, x "scalar" or polynomial in the same variable as d
    1347                 :            :  * [n/d a valid RFRAC]  */
    1348                 :            : static GEN
    1349                 :    9454207 : mul_rfrac_scal(GEN n, GEN d, GEN x)
    1350                 :            : {
    1351                 :    9454207 :   pari_sp av = avma;
    1352                 :            :   GEN z;
    1353                 :            : 
    1354      [ -  +  + ]:    9454207 :   switch(typ(x))
    1355                 :            :   {
    1356                 :            :     case t_PADIC:
    1357                 :          0 :       n = gmul(n, x);
    1358         [ #  # ]:          0 :       d = gcvtop(d, gel(x,2), signe(gel(x,4))? precp(x): 1);
    1359                 :          0 :       return gerepileupto(av, gdiv(n,d));
    1360                 :            : 
    1361                 :            :     case t_INTMOD: case t_POLMOD:
    1362                 :         14 :       n = gmul(n, x);
    1363                 :         14 :       d = gmul(d, gmodulo(gen_1, gel(x,1)));
    1364                 :         14 :       return gerepileupto(av, gdiv(n,d));
    1365                 :            :   }
    1366                 :    9454193 :   z = gred_rfrac2_i(x, d);
    1367                 :    9454193 :   n = simplify_shallow(n);
    1368         [ +  + ]:    9454193 :   if (typ(z) == t_RFRAC)
    1369                 :            :   {
    1370                 :    7119529 :     n = gmul(gel(z,1), n);
    1371                 :    7119529 :     d = gel(z,2);
    1372 [ +  + ][ -  + ]:    7119529 :     if (typ(n) == t_POL && varncmp(varn(n), varn(d)) < 0)
    1373                 :          0 :       z = RgX_Rg_div(n, d);
    1374                 :            :     else
    1375                 :    7119529 :       z = gred_rfrac_simple(n, d);
    1376                 :            :   }
    1377                 :            :   else
    1378                 :    2334664 :     z = gmul(z, n);
    1379                 :    9454207 :   return gerepileupto(av, z);
    1380                 :            : }
    1381                 :            : static GEN
    1382                 :   55103398 : mul_scal(GEN y, GEN x, long ty)
    1383                 :            : {
    1384   [ +  +  +  -  :   55103398 :   switch(ty)
                      - ]
    1385                 :            :   {
    1386                 :            :     case t_POL:
    1387         [ +  + ]:   46873999 :       if (lg(y) == 2) return scalarpol(gmul(gen_0,x), varn(y));
    1388                 :   45935745 :       return RgX_Rg_mul(y, x);
    1389                 :     117867 :     case t_SER: return mul_ser_scal(y, x);
    1390                 :    8111532 :     case t_RFRAC: return mul_rfrac_scal(gel(y,1),gel(y,2), x);
    1391                 :            :     case t_QFI: case t_QFR:
    1392 [ #  # ][ #  # ]:          0 :       if (typ(x) == t_INT && gequal1(x)) return gcopy(y); /* fall through */
    1393                 :            :   }
    1394                 :          0 :   pari_err_TYPE2("*",x,y);
    1395                 :   55103391 :   return NULL; /* not reached */
    1396                 :            : }
    1397                 :            : 
    1398                 :            : static GEN
    1399                 :     160830 : mul_gen_rfrac(GEN X, GEN Y)
    1400                 :            : {
    1401                 :     160830 :   GEN y1 = gel(Y,1), y2 = gel(Y,2);
    1402                 :     160830 :   long vx = gvar(X), vy = varn(y2);
    1403         [ +  + ]:     166570 :   return (varncmp(vx, vy) <= 0)? mul_scal(Y, X, typ(Y)):
    1404                 :       5740 :                                  gred_rfrac_simple(gmul(y1,X), y2);
    1405                 :            : }
    1406                 :            : /* (x1/x2) * (y1/y2) */
    1407                 :            : static GEN
    1408                 :    7743960 : mul_rfrac(GEN x1, GEN x2, GEN y1, GEN y2)
    1409                 :            : {
    1410                 :            :   GEN z, X, Y;
    1411                 :    7743960 :   pari_sp av = avma;
    1412                 :            : 
    1413                 :    7743960 :   X = gred_rfrac2_i(x1, y2);
    1414                 :    7743960 :   Y = gred_rfrac2_i(y1, x2);
    1415         [ +  + ]:    7743960 :   if (typ(X) == t_RFRAC)
    1416                 :            :   {
    1417         [ +  + ]:    6479540 :     if (typ(Y) == t_RFRAC) {
    1418                 :    6399615 :       x1 = gel(X,1);
    1419                 :    6399615 :       x2 = gel(X,2);
    1420                 :    6399615 :       y1 = gel(Y,1);
    1421                 :    6399615 :       y2 = gel(Y,2);
    1422                 :    6399615 :       z = gred_rfrac_simple(gmul(x1,y1), gmul(x2,y2));
    1423                 :            :     } else
    1424                 :      79925 :       z = mul_gen_rfrac(Y, X);
    1425                 :            :   }
    1426         [ +  + ]:    1264420 :   else if (typ(Y) == t_RFRAC)
    1427                 :      80905 :     z = mul_gen_rfrac(X, Y);
    1428                 :            :   else
    1429                 :    1183515 :     z = gmul(X, Y);
    1430                 :    7743960 :   return gerepileupto(av, z);
    1431                 :            : }
    1432                 :            : /* (x1/x2) /y2, x2 and y2 are t_POL in the same variable */
    1433                 :            : static GEN
    1434                 :     253134 : div_rfrac_pol(GEN x1, GEN x2, GEN y2)
    1435                 :            : {
    1436                 :     253134 :   pari_sp av = avma;
    1437                 :     253134 :   GEN X = gred_rfrac2_i(x1, y2);
    1438 [ +  + ][ +  + ]:     253134 :   if (typ(X) == t_RFRAC && varn(gel(X,2)) == varn(x2))
    1439                 :            :   {
    1440                 :     246582 :     x2 = RgX_mul(gel(X,2), x2);
    1441                 :     246582 :     x1 = gel(X,1);
    1442                 :            :   }
    1443                 :            :   else
    1444                 :       6552 :     x1 = X;
    1445                 :     253134 :   return gerepileupto(av, gred_rfrac_simple(x1, x2));
    1446                 :            : }
    1447                 :            : 
    1448                 :            : /* Mod(y, Y) * x,  assuming x scalar */
    1449                 :            : static GEN
    1450                 :    1162504 : mul_polmod_scal(GEN Y, GEN y, GEN x)
    1451                 :            : {
    1452                 :    1162504 :   GEN z = cgetg(3,t_POLMOD);
    1453                 :    1162504 :   gel(z,1) = RgX_copy(Y);
    1454                 :    1162504 :   gel(z,2) = gmul(x,y); return z;
    1455                 :            : }
    1456                 :            : 
    1457                 :            : /* cf mulqq */
    1458                 :            : static GEN
    1459                 :    1013119 : quad_polmod_mul(GEN P, GEN x, GEN y)
    1460                 :            : {
    1461                 :    1013119 :   GEN T = cgetg(4, t_POL), b = gel(P,3), c = gel(P,2), p1, p2, p3, p4;
    1462                 :    1013119 :   pari_sp tetpil, av = avma;
    1463                 :    1013119 :   T[1] = x[1];
    1464                 :    1013119 :   p2 = gmul(gel(x,2), gel(y,2));
    1465                 :    1013119 :   p3 = gmul(gel(x,3), gel(y,3));
    1466                 :    1013119 :   p1 = gmul(gneg_i(c),p3);
    1467                 :            :   /* operands are usually small: gadd ~ gmul and Karatsuba is a waste */
    1468         [ +  - ]:    1013119 :   if (typ(b) == t_INT)
    1469                 :            :   {
    1470         [ +  + ]:    1013119 :     if (signe(b))
    1471                 :            :     {
    1472                 :     728902 :       p4 = gadd(gmul(gel(x,2), gel(y,3)), gmul(gel(x,3), gel(y,2)));
    1473         [ +  + ]:     728902 :       if (is_pm1(b))
    1474                 :            :       {
    1475         [ +  + ]:     728797 :         if (signe(b) > 0) p3 = gneg(p3);
    1476                 :            :       }
    1477                 :            :       else
    1478                 :        105 :         p3 = gmul(negi(b), p3);
    1479                 :            :     }
    1480                 :            :     else
    1481                 :            :     {
    1482                 :     284217 :       p3 = gmul(gel(x,2),gel(y,3));
    1483                 :     284217 :       p4 = gmul(gel(x,3),gel(y,2));
    1484                 :            :     }
    1485                 :            :   }
    1486                 :            :   else
    1487                 :            :   {
    1488                 :          0 :     p4 = gadd(gmul(gel(x,2), gel(y,3)), gmul(gel(x,3), gel(y,2)));
    1489                 :          0 :     p3 = gmul(gneg_i(b), p3);
    1490                 :            :   }
    1491                 :    1013119 :   tetpil = avma;
    1492                 :    1013119 :   gel(T,2) = gadd(p2, p1);
    1493                 :    1013119 :   gel(T,3) = gadd(p4, p3);
    1494                 :    1013119 :   gerepilecoeffssp(av,tetpil,T+2,2);
    1495                 :    1013119 :   return normalizepol_lg(T,4);
    1496                 :            : }
    1497                 :            : /* Mod(x,T) * Mod(y,T) */
    1498                 :            : static GEN
    1499                 :    1636137 : mul_polmod_same(GEN T, GEN x, GEN y)
    1500                 :            : {
    1501                 :    1636137 :   GEN z = cgetg(3,t_POLMOD), a;
    1502                 :    1636137 :   long v = varn(T), lx = lg(x), ly = lg(y);
    1503                 :    1636137 :   gel(z,1) = RgX_copy(T);
    1504                 :            :   /* x * y mod T optimised */
    1505 [ +  + ][ +  + ]:    1636137 :   if (typ(x) != t_POL || varn(x) != v || lx <= 3
                 [ +  + ]
    1506 [ +  + ][ +  - ]:    1284158 :    || typ(y) != t_POL || varn(y) != v || ly <= 3)
                 [ +  + ]
    1507                 :     452275 :     a = gmul(x, y);
    1508                 :            :   else
    1509                 :            :   {
    1510 [ +  + ][ +  + ]:    1183862 :     if (lg(T) == 5 && isint1(gel(T,4))) /* quadratic fields */
    1511                 :    1011103 :       a = quad_polmod_mul(T, x, y);
    1512                 :            :     else
    1513                 :            :     {
    1514                 :     172759 :       pari_sp av = avma;
    1515                 :     172759 :       GEN p = NULL;
    1516 [ +  + ][ +  + ]:     172759 :       if (RgX_is_FpX(T, &p) && RgX_is_FpX(x, &p) && RgX_is_FpX(y, &p) && p)
         [ +  + ][ +  + ]
    1517                 :            :       {
    1518                 :      37121 :         T = RgX_to_FpX(T, p); x = RgX_to_FpX(x, p); y = RgX_to_FpX(y, p);
    1519         [ +  + ]:      37121 :         if (lgefint(p) == 3)
    1520                 :            :         {
    1521                 :      32284 :           ulong pp = p[2];
    1522                 :      32284 :           a = Flxq_mul(ZX_to_Flx(x, pp), ZX_to_Flx(y, pp), ZX_to_Flx(T, pp), pp);
    1523                 :      32284 :           a = Flx_to_ZX(a);
    1524                 :            :         }
    1525                 :            :         else
    1526                 :       4837 :           a = FpXQ_mul(x, y, T, p);
    1527                 :      37121 :         a = FpX_to_mod(a, p);
    1528                 :            :       }
    1529                 :            :       else
    1530                 :     135638 :         a = RgXQ_mul(x, y, gel(z,1));
    1531                 :     172759 :       a = gerepileupto(av, a);
    1532                 :            :     }
    1533                 :            :   }
    1534                 :    1636137 :   gel(z,2) = a; return z;
    1535                 :            : }
    1536                 :            : static GEN
    1537                 :      22347 : sqr_polmod(GEN T, GEN x)
    1538                 :            : {
    1539                 :      22347 :   GEN a, z = cgetg(3,t_POLMOD);
    1540                 :      22347 :   gel(z,1) = RgX_copy(T);
    1541 [ +  + ][ +  - ]:      22347 :   if (typ(x) != t_POL || varn(x) != varn(T) || lg(x) <= 3)
                 [ +  + ]
    1542                 :       2795 :     a = gsqr(x);
    1543                 :            :   else
    1544                 :            :   {
    1545                 :      19552 :     pari_sp av = avma;
    1546                 :      19552 :     GEN p = NULL;
    1547 [ +  - ][ +  + ]:      19552 :     if (RgX_is_FpX(T, &p) && RgX_is_FpX(x, &p) && p)
                 [ +  + ]
    1548                 :            :     {
    1549                 :         14 :       T = RgX_to_FpX(T, p); x = RgX_to_FpX(x, p);
    1550         [ +  + ]:         14 :       if (lgefint(p) == 3)
    1551                 :            :       {
    1552                 :          7 :         ulong pp = p[2];
    1553                 :          7 :         a = Flxq_sqr(ZX_to_Flx(x, pp), ZX_to_Flx(T, pp), pp);
    1554                 :          7 :         a = Flx_to_ZX(a);
    1555                 :            :       }
    1556                 :            :       else
    1557                 :          7 :         a = FpXQ_sqr(x, T, p);
    1558                 :         14 :       a = FpX_to_mod(a, p);
    1559                 :            :     }
    1560                 :            :     else
    1561                 :      19538 :       a = RgXQ_sqr(x, gel(z,1));
    1562                 :      19552 :     a = gerepileupto(av, a);
    1563                 :            :   }
    1564                 :      22347 :   gel(z,2) = a; return z;
    1565                 :            : }
    1566                 :            : /* Mod(x,X) * Mod(y,Y) */
    1567                 :            : static GEN
    1568                 :       1386 : mul_polmod(GEN X, GEN Y, GEN x, GEN y)
    1569                 :            : {
    1570                 :       1386 :   long T[3] = { evaltyp(t_POLMOD) | _evallg(3),0,0 };
    1571                 :       1386 :   long vx = varn(X), vy = varn(Y);
    1572                 :       1386 :   GEN z = cgetg(3,t_POLMOD);
    1573                 :            : 
    1574         [ +  + ]:       1386 :   if (vx==vy) {
    1575                 :            :     pari_sp av;
    1576                 :         14 :     gel(z,1) = RgX_gcd(X,Y); av = avma;
    1577                 :         14 :     warn_coercion(X,Y,gel(z,1));
    1578                 :         14 :     gel(z,2) = gerepileupto(av, gmod(gmul(x, y), gel(z,1)));
    1579                 :         14 :     return z;
    1580                 :            :   }
    1581         [ +  + ]:       1372 :   if (varncmp(vx, vy) < 0)
    1582                 :         21 :   { gel(z,1) = RgX_copy(X); gel(T,1) = Y; gel(T,2) = y; y = T; }
    1583                 :            :   else
    1584                 :       1351 :   { gel(z,1) = RgX_copy(Y); gel(T,1) = X; gel(T,2) = x; x = T; }
    1585                 :       1386 :   gel(z,2) = gmul(x, y); return z;
    1586                 :            : }
    1587                 :            : 
    1588                 :            : #if 0 /* used by 3M only */
    1589                 :            : /* set z = x+y and return 1 if x,y have the same sign
    1590                 :            :  * set z = x-y and return 0 otherwise */
    1591                 :            : static int
    1592                 :            : did_add(GEN x, GEN y, GEN *z)
    1593                 :            : {
    1594                 :            :   long tx = typ(x), ty = typ(y);
    1595                 :            :   if (tx == ty) switch(tx)
    1596                 :            :   {
    1597                 :            :     case t_INT: *z = addii(x,y); return 1;
    1598                 :            :     case t_FRAC: *z = addsub_frac(x,y,addii); return 1;
    1599                 :            :     case t_REAL:
    1600                 :            :       if (signe(x) == -signe(y))
    1601                 :            :       { *z = subrr(x,y); return 0; }
    1602                 :            :       else
    1603                 :            :       { *z = addrr(x,y); return 1; }
    1604                 :            :   }
    1605                 :            :   if (tx == t_REAL) switch(ty)
    1606                 :            :   {
    1607                 :            :     case t_INT:
    1608                 :            :       if (signe(x) == -signe(y))
    1609                 :            :       { *z = subri(x,y); return 0; }
    1610                 :            :       else
    1611                 :            :       { *z = addri(x,y); return 1; }
    1612                 :            :     case t_FRAC:
    1613                 :            :       if (signe(x) == -signe(gel(y,1)))
    1614                 :            :       { *z = gsub(x,y); return 0; }
    1615                 :            :       else
    1616                 :            :       { *z = gadd(x,y); return 1; }
    1617                 :            :   }
    1618                 :            :   else if (ty == t_REAL) switch(tx)
    1619                 :            :   {
    1620                 :            :     case t_INT:
    1621                 :            :       if (signe(x) == -signe(y))
    1622                 :            :       { *z = subir(x,y); return 0; }
    1623                 :            :       else
    1624                 :            :       { *z = addir(x,y); return 1; }
    1625                 :            :     case t_FRAC:
    1626                 :            :       if (signe(gel(x,1)) == -signe(y))
    1627                 :            :       { *z = gsub(x,y); return 0; }
    1628                 :            :       else
    1629                 :            :       { *z = gadd(x,y); return 1; }
    1630                 :            :   }
    1631                 :            :   *z = gadd(x,y); return 1;
    1632                 :            : }
    1633                 :            : #endif
    1634                 :            : /* x * I * y, x t_COMPLEX with non-intzero real part, y non-intzero "scalar" */
    1635                 :            : static GEN
    1636                 :     733434 : mulcIR(GEN x, GEN y)
    1637                 :            : {
    1638                 :     733434 :   GEN z = cgetg(3,t_COMPLEX);
    1639                 :     733434 :   pari_sp av = avma;
    1640                 :     733434 :   gel(z,1) = gerepileupto(av, gneg(gmul(y,gel(x,2))));
    1641                 :     733434 :   gel(z,2) = gmul(y, gel(x,1));
    1642                 :     733434 :   return z;
    1643                 :            : 
    1644                 :            : }
    1645                 :            : /* x,y COMPLEX */
    1646                 :            : static GEN
    1647                 :   63715192 : mulcc(GEN x, GEN y)
    1648                 :            : {
    1649                 :   63715192 :   GEN xr = gel(x,1), xi = gel(x,2);
    1650                 :   63715192 :   GEN yr = gel(y,1), yi = gel(y,2);
    1651                 :            :   GEN p1, p2, p3, p4, z;
    1652                 :            :   pari_sp tetpil, av;
    1653                 :            : 
    1654         [ +  + ]:   63715192 :   if (isintzero(xr))
    1655                 :            :   {
    1656         [ +  + ]:     736054 :     if (isintzero(yr)) {
    1657                 :     116569 :       av = avma;
    1658                 :     116569 :       return gerepileupto(av, gneg(gmul(xi,yi)));
    1659                 :            :     }
    1660                 :     619485 :     return mulcIR(y, xi);
    1661                 :            :   }
    1662         [ +  + ]:   62979138 :   if (isintzero(yr)) return mulcIR(x, yi);
    1663                 :            : 
    1664                 :   62865189 :   z = cgetg(3,t_COMPLEX); av = avma;
    1665                 :            : #if 0
    1666                 :            :   /* 3M method avoiding catastrophic cancellation, BUT loses accuracy due to
    1667                 :            :    * e.g. xr + xi if exponents differ */
    1668                 :            :   if (did_add(xr, xi, &p3))
    1669                 :            :   {
    1670                 :            :     if (did_add(yr, yi, &p4)) {
    1671                 :            :     /* R = xr*yr - xi*yi
    1672                 :            :      * I = (xr+xi)(yr+yi) - xr*yr - xi*yi */
    1673                 :            :       p1 = gmul(xr,yr);
    1674                 :            :       p2 = gmul(xi,yi); p2 = gneg(p2);
    1675                 :            :       p3 = gmul(p3, p4);
    1676                 :            :       p4 = gsub(p2, p1);
    1677                 :            :     } else {
    1678                 :            :     /* R = (xr + xi) * (yr - yi) + (xr * yi - xi * yr)
    1679                 :            :      * I = xr*yi + xi*yr */
    1680                 :            :       p1 = gmul(p3,p4);
    1681                 :            :       p3 = gmul(xr,yi);
    1682                 :            :       p4 = gmul(xi,yr);
    1683                 :            :       p2 = gsub(p3, p4);
    1684                 :            :     }
    1685                 :            :   } else {
    1686                 :            :     if (did_add(yr, yi, &p4)) {
    1687                 :            :      /* R = (xr - xi) * (yr + yi) + (xi * yr - xr * yi)
    1688                 :            :       * I = xr*yi +xi*yr */
    1689                 :            :       p1 = gmul(p3,p4);
    1690                 :            :       p3 = gmul(xr,yi);
    1691                 :            :       p4 = gmul(xi,yr);
    1692                 :            :       p2 = gsub(p4, p3);
    1693                 :            :     } else {
    1694                 :            :     /* R = xr*yr - xi*yi
    1695                 :            :      * I = -(xr-xi)(yr-yi) + xr*yr + xi*yi */
    1696                 :            :       p3 = gneg( gmul(p3, p4) );
    1697                 :            :       p1 = gmul(xr,yr);
    1698                 :            :       p2 = gmul(xi,yi);
    1699                 :            :       p4 = gadd(p1, p2);
    1700                 :            : 
    1701                 :            :       p2 = gneg(p2);
    1702                 :            :     }
    1703                 :            :   }
    1704                 :            :   tetpil = avma;
    1705                 :            :   gel(z,1) = gadd(p1,p2);
    1706                 :            :   gel(z,2) = gadd(p3,p4);
    1707                 :            : #else
    1708 [ +  + ][ +  + ]:   62865189 :   if (typ(xr)==t_INT && typ(yr)==t_INT && typ(xi)==t_INT && typ(yi)==t_INT)
         [ +  - ][ +  + ]
    1709                 :            :   { /* 3M formula */
    1710                 :        168 :     p3 = addii(xr,xi);
    1711                 :        168 :     p4 = addii(yr,yi);
    1712                 :        168 :     p1 = mulii(xr,yr);
    1713                 :        168 :     p2 = mulii(xi,yi);
    1714                 :        168 :     p3 = mulii(p3,p4);
    1715                 :        168 :     p4 = addii(p2,p1);
    1716                 :        168 :     tetpil = avma;
    1717                 :        168 :     gel(z,1) = subii(p1,p2);
    1718                 :        168 :     gel(z,2) = subii(p3,p4);
    1719         [ +  + ]:        168 :     if (!signe(gel(z,2)))
    1720                 :         49 :       return gerepileuptoint((pari_sp)(z+3), gel(z,1));
    1721                 :            :   }
    1722                 :            :   else
    1723                 :            :   { /* naive 4M formula: avoid all loss of accuracy */
    1724                 :   62865021 :     p1 = gmul(xr,yr);
    1725                 :   62865021 :     p2 = gmul(xi,yi);
    1726                 :   62865021 :     p3 = gmul(xr,yi);
    1727                 :   62865021 :     p4 = gmul(xi,yr);
    1728                 :   62865021 :     tetpil = avma;
    1729                 :   62865021 :     gel(z,1) = gsub(p1,p2);
    1730                 :   62865021 :     gel(z,2) = gadd(p3,p4);
    1731         [ +  + ]:   62865021 :     if (isintzero(gel(z,2)))
    1732                 :            :     {
    1733                 :       8985 :       cgiv(gel(z,2));
    1734                 :       8985 :       return gerepileupto((pari_sp)(z+3), gel(z,1));
    1735                 :            :     }
    1736                 :            :   }
    1737                 :            : #endif
    1738                 :            : 
    1739                 :   63715192 :   gerepilecoeffssp(av,tetpil, z+1,2); return z;
    1740                 :            : }
    1741                 :            : /* x,y PADIC */
    1742                 :            : static GEN
    1743                 :    1155311 : mulpp(GEN x, GEN y) {
    1744                 :    1155311 :   long l = valp(x) + valp(y);
    1745                 :            :   pari_sp av;
    1746                 :            :   GEN z, t;
    1747         [ -  + ]:    1155311 :   if (!equalii(gel(x,2),gel(y,2))) pari_err_OP("*",x,y);
    1748         [ +  + ]:    1155311 :   if (!signe(gel(x,4))) return zeropadic(gel(x,2), l);
    1749         [ +  + ]:     998406 :   if (!signe(gel(y,4))) return zeropadic(gel(x,2), l);
    1750                 :            : 
    1751         [ +  + ]:     940369 :   t = (precp(x) > precp(y))? y: x;
    1752                 :     940369 :   z = cgetp(t); setvalp(z,l); av = avma;
    1753                 :     940369 :   affii(remii(mulii(gel(x,4),gel(y,4)), gel(t,3)), gel(z,4));
    1754                 :    1155323 :   avma = av; return z;
    1755                 :            : }
    1756                 :            : /* x,y QUAD */
    1757                 :            : static GEN
    1758                 :       1344 : mulqq(GEN x, GEN y) {
    1759                 :       1344 :   GEN z = cgetg(4,t_QUAD);
    1760                 :       1344 :   GEN p1, p2, p3, p4, P = gel(x,1), b = gel(P,3), c = gel(P,2);
    1761                 :            :   pari_sp av, tetpil;
    1762         [ -  + ]:       1344 :   if (!ZX_equal(P, gel(y,1))) pari_err_OP("*",x,y);
    1763                 :            : 
    1764                 :       1344 :   gel(z,1) = ZX_copy(P); av = avma;
    1765                 :       1344 :   p2 = gmul(gel(x,2),gel(y,2));
    1766                 :       1344 :   p3 = gmul(gel(x,3),gel(y,3));
    1767                 :       1344 :   p1 = gmul(gneg_i(c),p3);
    1768                 :            : 
    1769         [ +  + ]:       1344 :   if (signe(b))
    1770                 :       1239 :     p4 = gadd(gmul(gel(x,2),gel(y,3)), gmul(gel(x,3),gel(y,2)));
    1771                 :            :   else
    1772                 :            :   {
    1773                 :        105 :     p3 = gmul(gel(x,2),gel(y,3));
    1774                 :        105 :     p4 = gmul(gel(x,3),gel(y,2));
    1775                 :            :   }
    1776                 :       1344 :   tetpil = avma;
    1777                 :       1344 :   gel(z,2) = gadd(p2,p1);
    1778                 :       1344 :   gel(z,3) = gadd(p4,p3);
    1779                 :       1344 :   gerepilecoeffssp(av,tetpil,z+2,2); return z;
    1780                 :            : }
    1781                 :            : 
    1782                 :            : GEN
    1783                 :    1559593 : mulcxI(GEN x)
    1784                 :            : {
    1785                 :            :   GEN z;
    1786      [ +  +  + ]:    1559593 :   switch(typ(x))
    1787                 :            :   {
    1788                 :            :     case t_INT: case t_REAL: case t_FRAC:
    1789                 :     184159 :       return mkcomplex(gen_0, x);
    1790                 :            :     case t_COMPLEX:
    1791         [ +  + ]:    1375378 :       if (isintzero(gel(x,1))) return gneg(gel(x,2));
    1792                 :    1373250 :       z = cgetg(3,t_COMPLEX);
    1793                 :    1373250 :       gel(z,1) = gneg(gel(x,2));
    1794                 :    1373250 :       gel(z,2) = gel(x,1); return z;
    1795                 :            :     default:
    1796                 :    1559593 :       return gmul(gen_I(), x);
    1797                 :            :   }
    1798                 :            : }
    1799                 :            : GEN
    1800                 :      47838 : mulcxmI(GEN x)
    1801                 :            : {
    1802                 :            :   GEN z;
    1803      [ +  +  + ]:      47838 :   switch(typ(x))
    1804                 :            :   {
    1805                 :            :     case t_INT: case t_REAL: case t_FRAC:
    1806                 :       2051 :       return mkcomplex(gen_0, gneg(x));
    1807                 :            :     case t_COMPLEX:
    1808         [ +  + ]:      45731 :       if (isintzero(gel(x,1))) return gel(x,2);
    1809                 :      44744 :       z = cgetg(3,t_COMPLEX);
    1810                 :      44744 :       gel(z,1) = gel(x,2);
    1811                 :      44744 :       gel(z,2) = gneg(gel(x,1)); return z;
    1812                 :            :     default:
    1813                 :      47838 :       return gmul(mkcomplex(gen_0, gen_m1), x);
    1814                 :            :   }
    1815                 :            : }
    1816                 :            : 
    1817                 :            : /* fill in coefficients of t_SER z from coeffs of t_POL y */
    1818                 :            : static GEN
    1819                 :     374416 : fill_ser(GEN z, GEN y)
    1820                 :            : {
    1821                 :     374416 :   long i, lx = lg(z), ly = lg(y);
    1822         [ +  + ]:     374416 :   if (ly >= lx) {
    1823         [ +  + ]:    1598126 :     for (i = 2; i < lx; i++) gel(z,i) = gel(y,i);
    1824                 :            :   } else {
    1825         [ +  + ]:      15939 :     for (i = 2; i < ly; i++) gel(z,i) = gel(y,i);
    1826         [ +  + ]:      28336 :     for (     ; i < lx; i++) gel(z,i) = gen_0;
    1827                 :            :   }
    1828                 :     374416 :   return normalize(z);
    1829                 :            : }
    1830                 :            : 
    1831                 :            : GEN
    1832                 : 2443425445 : gmul(GEN x, GEN y)
    1833                 :            : {
    1834                 :            :   long tx, ty, lx, ly, vx, vy, i, l;
    1835                 :            :   pari_sp av, tetpil;
    1836                 :            :   GEN z, p1, p2;
    1837                 :            : 
    1838         [ +  + ]: 2443425445 :   if (x == y) return gsqr(x);
    1839                 : 1604634349 :   tx = typ(x); ty = typ(y);
    1840 [ +  + ][ +  +  : 1604634349 :   if (tx == ty) switch(tx)
          +  +  +  +  +  
          +  +  +  +  +  
             +  +  +  -  
                      - ]
    1841                 :            :   {
    1842                 :  807257376 :     case t_INT: return mulii(x,y);
    1843                 :  409873813 :     case t_REAL: return mulrr(x,y);
    1844                 :     894593 :     case t_INTMOD: { GEN X = gel(x,1), Y = gel(y,1);
    1845                 :     894593 :       z = cgetg(3,t_INTMOD);
    1846 [ +  - ][ +  + ]:     894578 :       if (X==Y || equalii(X,Y))
    1847                 :     894577 :         return mul_intmod_same(z, X, gel(x,2), gel(y,2));
    1848                 :          7 :       gel(z,1) = gcdii(X,Y);
    1849                 :          7 :       warn_coercion(X,Y,gel(z,1));
    1850                 :          7 :       av = avma; p1 = mulii(gel(x,2),gel(y,2));
    1851                 :          7 :       gel(z,2) = gerepileuptoint(av, remii(p1, gel(z,1))); return z;
    1852                 :            :     }
    1853                 :            :     case t_FRAC:
    1854                 :            :     {
    1855                 :    9664876 :       GEN x1 = gel(x,1), x2 = gel(x,2);
    1856                 :    9664876 :       GEN y1 = gel(y,1), y2 = gel(y,2);
    1857                 :    9664876 :       z=cgetg(3,t_FRAC);
    1858                 :    9664876 :       p1 = gcdii(x1, y2);
    1859         [ +  + ]:    9664876 :       if (!is_pm1(p1)) { x1 = diviiexact(x1,p1); y2 = diviiexact(y2,p1); }
    1860                 :    9664876 :       p1 = gcdii(x2, y1);
    1861         [ +  + ]:    9664876 :       if (!is_pm1(p1)) { x2 = diviiexact(x2,p1); y1 = diviiexact(y1,p1); }
    1862                 :    9664876 :       tetpil = avma;
    1863                 :    9664876 :       gel(z,2) = mulii(x2,y2);
    1864                 :    9664876 :       gel(z,1) = mulii(x1,y1);
    1865         [ +  + ]:    9664876 :       fix_frac_if_int_GC(z,tetpil); return z;
    1866                 :            :     }
    1867                 :   63316881 :     case t_COMPLEX: return mulcc(x, y);
    1868                 :    1076026 :     case t_PADIC: return mulpp(x, y);
    1869                 :       1022 :     case t_QUAD: return mulqq(x, y);
    1870                 :    1638487 :     case t_FFELT: return FF_mul(x, y);
    1871                 :            :     case t_POLMOD:
    1872         [ +  + ]:    1494534 :       if (RgX_equal_var(gel(x,1), gel(y,1)))
    1873                 :    1493148 :         return mul_polmod_same(gel(x,1), gel(x,2), gel(y,2));
    1874                 :       1386 :       return mul_polmod(gel(x,1), gel(y,1), gel(x,2), gel(y,2));
    1875                 :            :     case t_POL:
    1876                 :   33895426 :       vx = varn(x);
    1877                 :   33895426 :       vy = varn(y);
    1878         [ +  + ]:   33895426 :       if (vx != vy) {
    1879         [ +  + ]:    4672746 :         if (varncmp(vx, vy) < 0) return RgX_Rg_mul(x, y);
    1880                 :    1993134 :         else                     return RgX_Rg_mul(y, x);
    1881                 :            :       }
    1882 [ +  + ][ +  + ]:   29222680 :       if (RgX_is_ZX(x) && RgX_is_ZX(y)) return ZX_mul(x,y);
    1883                 :    5369243 :       return RgX_mul(x, y);
    1884                 :            : 
    1885                 :            :     case t_SER: {
    1886                 :     374479 :       GEN p = NULL;
    1887                 :     374479 :       vx = varn(x);
    1888                 :     374479 :       vy = varn(y);
    1889         [ -  + ]:     374479 :       if (vx != vy) {
    1890         [ #  # ]:          0 :         if (varncmp(vx, vy) < 0) return mul_ser_scal(x, y);
    1891                 :          0 :         else                     return mul_ser_scal(y, x);
    1892                 :            :       }
    1893                 :     374479 :       lx = lg(x);
    1894         [ +  + ]:     374479 :       ly = lg(y); if (lx > ly) { lx = ly; swap(x, y); }
    1895         [ +  + ]:     374479 :       if (lx == 2) return zeroser(vx, valp(x)+valp(y));
    1896                 :     374304 :       z = cgetg(lx,t_SER);
    1897                 :     374304 :       z[1] = evalvalp(valp(x)+valp(y)) | evalvarn(vx) | evalsigne(1);
    1898                 :     374304 :       x = ser2pol_i(x, lx);
    1899                 :     374304 :       y = ser2pol_i(y, lx);
    1900 [ +  + ][ +  + ]:     374304 :       if (RgX_is_FpX(x,&p) && RgX_is_FpX(y,&p))
    1901                 :            :       {
    1902         [ +  + ]:       8394 :         if (!p) y = ZX_mul(x,y);
    1903                 :            :         else
    1904                 :            :         {
    1905                 :         21 :           x = RgX_to_FpX(x, p);
    1906                 :         21 :           y = RgX_to_FpX(y, p);
    1907                 :         21 :           y = FpX_to_mod(ZX_mul(x,y), p);
    1908                 :            :         }
    1909                 :            :       }
    1910                 :            :       else
    1911                 :     365931 :         y = RgXn_mul(x, y, lx-2);
    1912                 :     374304 :       z = fill_ser(z, y);
    1913                 :     374479 :       return gerepilecopy((pari_sp)(z + lx), z);
    1914                 :            :     }
    1915                 :      47201 :     case t_QFI: return qficomp(x,y);
    1916                 :          7 :     case t_QFR: return qfrcomp(x,y);
    1917                 :    6557631 :     case t_RFRAC: return mul_rfrac(gel(x,1),gel(x,2), gel(y,1),gel(y,2));
    1918                 :      22510 :     case t_MAT: return RgM_mul(x, y);
    1919                 :            : 
    1920                 :            :     case t_VECSMALL: /* multiply as permutation. cf perm_mul */
    1921                 :          0 :       z = cgetg_copy(x, &l);
    1922         [ #  # ]:          0 :       if (l != lg(y)) break;
    1923         [ #  # ]:          0 :       for (i=1; i<l; i++)
    1924                 :            :       {
    1925                 :          0 :         long yi = y[i];
    1926 [ #  # ][ #  # ]:          0 :         if (yi < 1 || yi >= l) pari_err_TYPE2("*",x,y);
    1927                 :          0 :         z[i] = x[yi];
    1928                 :            :       }
    1929                 :          0 :       return z;
    1930                 :            : 
    1931                 :            : 
    1932                 :            :     default:
    1933                 :          0 :       pari_err_TYPE2("*",x,y);
    1934                 :            :   }
    1935                 :            :   /* tx != ty */
    1936 [ +  + ][ +  + ]:  268519487 :   if (is_const_t(ty) && is_const_t(tx))  {
    1937         [ +  + ]:  203389023 :     if (tx > ty) { swap(x,y); lswap(tx,ty); }
    1938   [ +  +  +  +  :  203389023 :     switch(tx) {
             -  +  +  - ]
    1939                 :            :     case t_INT:
    1940   [ +  +  +  +  :  181452383 :       switch(ty)
             +  +  +  + ]
    1941                 :            :       {
    1942         [ +  + ]:  107388124 :         case t_REAL: return signe(x)? mulir(x,y): gen_0;
    1943                 :            :         case t_INTMOD:
    1944                 :    1561419 :           z = cgetg(3, t_INTMOD);
    1945                 :    1561403 :           return mul_intmod_same(z, gel(y,1), gel(y,2), modii(x, gel(y,1)));
    1946                 :            :         case t_FRAC:
    1947         [ +  + ]:   30995827 :           if (!signe(x)) return gen_0;
    1948                 :   18258519 :           z=cgetg(3,t_FRAC);
    1949                 :   18258519 :           p1 = gcdii(x,gel(y,2));
    1950         [ +  + ]:   18258519 :           if (is_pm1(p1))
    1951                 :            :           {
    1952                 :   11392401 :             avma = (pari_sp)z;
    1953                 :   11392401 :             gel(z,2) = icopy(gel(y,2));
    1954                 :   11392401 :             gel(z,1) = mulii(gel(y,1), x);
    1955                 :            :           }
    1956                 :            :           else
    1957                 :            :           {
    1958                 :    6866118 :             x = diviiexact(x,p1); tetpil = avma;
    1959                 :    6866118 :             gel(z,2) = diviiexact(gel(y,2), p1);
    1960                 :    6866118 :             gel(z,1) = mulii(gel(y,1), x);
    1961         [ +  + ]:    6866118 :             fix_frac_if_int_GC(z,tetpil);
    1962                 :            :           }
    1963                 :   18258519 :           return z;
    1964         [ +  + ]:   41222978 :         case t_COMPLEX: return signe(x)? mulRc(x, y): gen_0;
    1965         [ +  + ]:      79304 :         case t_PADIC: return signe(x)? mulTp(x, y): gen_0;
    1966                 :       1281 :         case t_QUAD: return mulRq(x,y);
    1967                 :     203449 :         case t_FFELT: return FF_Z_mul(y,x);
    1968                 :            :       }
    1969                 :            : 
    1970                 :            :     case t_REAL:
    1971   [ +  +  +  + ]:   21878933 :       switch(ty)
    1972                 :            :       {
    1973                 :     935750 :         case t_FRAC: return mulrfrac(x, y);
    1974                 :   20943169 :         case t_COMPLEX: return mulRc(x, y);
    1975                 :          7 :         case t_QUAD: return mulqf(y, x, lg(x));
    1976                 :          7 :         default: pari_err_TYPE2("*",x,y);
    1977                 :            :       }
    1978                 :            : 
    1979                 :            :     case t_INTMOD:
    1980   [ +  +  -  +  :       5086 :       switch(ty)
                   +  - ]
    1981                 :            :       {
    1982                 :        504 :         case t_FRAC: { GEN X = gel(x,1);
    1983                 :        504 :           z = cgetg(3, t_INTMOD); p1 = Fp_mul(gel(y,1), gel(x,2), X);
    1984                 :        504 :           return div_intmod_same(z, X, p1, remii(gel(y,2), X));
    1985                 :            :         }
    1986                 :         35 :         case t_COMPLEX: return mulRc_direct(x,y);
    1987                 :          0 :         case t_PADIC: { GEN X = gel(x,1);
    1988                 :          0 :           z = cgetg(3, t_INTMOD);
    1989                 :          0 :           return mul_intmod_same(z, X, gel(x,2), padic_to_Fp(y, X));
    1990                 :            :         }
    1991                 :         42 :         case t_QUAD: return mulRq(x, y);
    1992                 :            :         case t_FFELT:
    1993         [ -  + ]:       4505 :           if (!equalii(gel(x,1),FF_p_i(y)))
    1994                 :          0 :             pari_err_OP("*",x,y);
    1995                 :       4505 :           return FF_Z_mul(y,gel(x,2));
    1996                 :            :       }
    1997                 :            : 
    1998                 :            :     case t_FRAC:
    1999   [ +  +  +  +  :      52592 :       switch(ty)
                      - ]
    2000                 :            :       {
    2001                 :      48161 :         case t_COMPLEX: return mulRc(x, y);
    2002         [ +  - ]:       2198 :         case t_PADIC: return signe(gel(x,1))? mulTp(x, y): gen_0;
    2003                 :        455 :         case t_QUAD:  return mulRq(x, y);
    2004                 :       1778 :         case t_FFELT: return FF_Z_Z_muldiv(y, gel(x,1),gel(x,2));
    2005                 :            :       }
    2006                 :            : 
    2007                 :            :     case t_FFELT:
    2008                 :          0 :       pari_err_TYPE2("*",x,y);
    2009                 :            : 
    2010                 :            :     case t_COMPLEX:
    2011      [ +  +  - ]:         14 :       switch(ty)
    2012                 :            :       {
    2013                 :            :         case t_PADIC:
    2014         [ -  + ]:          7 :           return Zp_nosquare_m1(gel(y,2))? mulRc(y, x): mulTp(x, y);
    2015                 :            :         case t_QUAD:
    2016         [ -  + ]:          7 :           lx = precision(x); if (!lx) pari_err_OP("*",x,y);
    2017                 :          7 :           return mulqf(y, x, lx);
    2018                 :            :       }
    2019                 :            : 
    2020                 :            :     case t_PADIC: /* ty == t_QUAD */
    2021         [ +  + ]:         21 :       return (kro_quad(y,gel(x,2))== -1)? mulRq(x, y): mulTp(y, x);
    2022                 :            :     }
    2023                 :            :   }
    2024                 :            : 
    2025         [ +  + ]:   65186568 :   if (is_matvec_t(ty))
    2026                 :            :   {
    2027         [ +  + ]:    7301451 :     if (!is_matvec_t(tx))
    2028                 :            :     {
    2029         [ -  + ]:    7002180 :       if (is_noncalc_t(tx)) pari_err_TYPE2( "*",x,y); /* necessary if ly = 1 */
    2030                 :    7002180 :       z = cgetg_copy(y, &ly);
    2031         [ +  + ]:  132326801 :       for (i=1; i<ly; i++) gel(z,i) = gmul(x,gel(y,i));
    2032                 :    7002180 :       return z;
    2033                 :            :     }
    2034   [ +  +  +  - ]:     299271 :     switch(tx)
    2035                 :            :     {
    2036                 :            :       case t_VEC:
    2037      [ +  +  - ]:     210361 :         switch(ty) {
    2038                 :     193702 :           case t_COL: return RgV_RgC_mul(x,y);
    2039                 :      16659 :           case t_MAT: return RgV_RgM_mul(x,y);
    2040                 :            :         }
    2041                 :          0 :         break;
    2042                 :            :       case t_COL:
    2043      [ +  -  - ]:          7 :         switch(ty) {
    2044                 :          7 :           case t_VEC: return RgC_RgV_mul(x,y);
    2045                 :          0 :           case t_MAT: return RgC_RgM_mul(x,y);
    2046                 :            :         }
    2047                 :          0 :         break;
    2048                 :            :       case t_MAT:
    2049      [ -  +  - ]:      88903 :         switch(ty) {
    2050                 :          0 :           case t_VEC: return RgM_RgV_mul(x,y);
    2051                 :      88903 :           case t_COL: return RgM_RgC_mul(x,y);
    2052                 :            :         }
    2053                 :            :     }
    2054                 :            :   }
    2055         [ +  + ]:   57885125 :   if (is_matvec_t(tx))
    2056                 :            :   {
    2057         [ -  + ]:     214435 :     if (is_noncalc_t(ty)) pari_err_TYPE2( "*",x,y); /* necessary if lx = 1 */
    2058                 :     214435 :     z = cgetg_copy(x, &lx);
    2059         [ +  + ]:    1175731 :     for (i=1; i<lx; i++) gel(z,i) = gmul(y,gel(x,i));
    2060                 :     214435 :     return z;
    2061                 :            :   }
    2062         [ +  + ]:   57670690 :   if (tx > ty) { swap(x,y); lswap(tx,ty); }
    2063                 :            :   /* tx < ty, !ismatvec(x and y) */
    2064                 :            : 
    2065         [ +  + ]:   57670690 :   if (ty == t_POLMOD) /* is_const_t(tx) in this case */
    2066                 :    1161825 :     return mul_polmod_scal(gel(y,1), gel(y,2), x);
    2067         [ +  + ]:   56508865 :   if (is_scalar_t(tx)) {
    2068         [ +  + ]:   53677839 :     if (tx == t_POLMOD) {
    2069                 :     175701 :       vx = varn(gel(x,1));
    2070                 :     175701 :       vy = gvar(y);
    2071         [ +  + ]:     175701 :       if (vx != vy) {
    2072         [ +  + ]:      32845 :         if (varncmp(vx,vy) > 0) return mul_scal(y, x, ty);
    2073                 :        679 :         return mul_polmod_scal(gel(x,1), gel(x,2), y);
    2074                 :            :       }
    2075                 :            :       /* error if ty == t_SER */
    2076                 :     142856 :       av = avma; y = gmod(y, gel(x,1));
    2077                 :     142849 :       return gerepileupto(av, mul_polmod_same(gel(x,1), gel(x,2), y));
    2078                 :            :     }
    2079                 :   53502138 :     return mul_scal(y, x, ty);
    2080                 :            :   }
    2081                 :            : 
    2082                 :            :   /* x and y are not scalars, nor matvec */
    2083                 :    2831026 :   vx = gvar(x);
    2084                 :    2831026 :   vy = gvar(y);
    2085         [ +  + ]:    2831026 :   if (vx != vy) /* x or y is treated as a scalar */
    2086                 :    2828008 :     return (varncmp(vx, vy) < 0)? mul_scal(x, y, tx)
    2087         [ +  + ]:    1414004 :                                 : mul_scal(y, x, ty);
    2088                 :            :   /* vx = vy */
    2089      [ +  -  - ]:    1417022 :   switch(tx)
    2090                 :            :   {
    2091                 :            :     case t_POL:
    2092      [ +  +  - ]:    1417022 :       switch (ty)
    2093                 :            :       {
    2094                 :            :         case t_SER:
    2095                 :            :         {
    2096                 :            :           long vn;
    2097         [ -  + ]:      74375 :           if (lg(x) == 2) return zeropol(vx);
    2098         [ +  + ]:      74375 :           if (lg(y) == 2) return zeroser(vx, valp(y)+RgX_val(x));
    2099                 :      74165 :           av = avma;
    2100                 :      74165 :           vn = RgX_valrem(x, &x);
    2101                 :            :           /* take advantage of x = t^n ! */
    2102         [ +  + ]:      74165 :           if (degpol(x)) {
    2103                 :       2401 :             p1 = RgX_to_ser(x,lg(y));
    2104         [ -  + ]:       2401 :             if (vn) settyp(x, t_VECSMALL); /* *new* x left on stack */
    2105                 :       2401 :             p2 = gmul(p1,y);
    2106                 :       2401 :             settyp(p1, t_VECSMALL); /* p1 left on stack */
    2107                 :            :           } else {
    2108                 :      71764 :             avma = av;
    2109                 :      71764 :             p2 = mul_ser_scal(y, gel(x,2));
    2110                 :            :           }
    2111                 :      74165 :           setvalp(p2, valp(p2) + vn);
    2112                 :      74165 :           return p2;
    2113                 :            :         }
    2114                 :            : 
    2115                 :    1342647 :         case t_RFRAC: return mul_rfrac_scal(gel(y,1),gel(y,2), x);
    2116                 :            :       }
    2117                 :          0 :       break;
    2118                 :            : 
    2119                 :            :     case t_SER:
    2120         [ #  # ]:          0 :       switch (ty)
    2121                 :            :       {
    2122                 :            :         case t_RFRAC:
    2123                 :          0 :           av = avma;
    2124                 :          0 :           return gerepileupto(av, gdiv(gmul(gel(y,1),x), gel(y,2)));
    2125                 :            :       }
    2126                 :          0 :       break;
    2127                 :            :   }
    2128                 :          0 :   pari_err_TYPE2("*",x,y);
    2129                 : 2442880195 :   return NULL; /* not reached */
    2130                 :            : }
    2131                 :            : 
    2132                 :            : int
    2133                 :      28378 : ff_poltype(GEN *x, GEN *p, GEN *pol)
    2134                 :            : {
    2135                 :      28378 :   GEN Q, P = *x;
    2136         [ +  + ]:      28378 :   if (!signe(P)) return 0;
    2137 [ +  + ][ +  + ]:      28294 :   if (!RgX_is_FpXQX(P,pol,p) || !*p || !*pol || typ(*pol)!=t_POL)
         [ +  + ][ +  - ]
    2138                 :      28294 :     return 0;
    2139                 :          0 :   Q = RgX_to_FpX(*pol, *p);
    2140                 :          0 :   P = RgX_to_FpXQX(P, Q, *p);
    2141                 :          0 :   *x = ZXX_to_Kronecker(P, degpol(Q));
    2142                 :          0 :   *pol = Q;
    2143                 :      28378 :   return 1;
    2144                 :            : }
    2145                 :            : 
    2146                 :            : /* return a non-normalized result */
    2147                 :            : GEN
    2148                 :       5313 : sqr_ser_part(GEN x, long l1, long l2)
    2149                 :            : {
    2150                 :            :   long i, j, l;
    2151                 :            :   pari_sp av;
    2152                 :            :   GEN Z, z, p1, p2;
    2153                 :            :   long mi;
    2154         [ +  + ]:       5313 :   if (l2 < l1) return zeroser(varn(x), 2*valp(x));
    2155                 :       5306 :   p2 = cgetg(l2+2, t_VECSMALL)+1; /* left on stack on exit */
    2156                 :       5306 :   Z = cgetg(l2-l1+3, t_SER);
    2157                 :       5306 :   Z[1] = evalvalp(2*valp(x)) | evalvarn(varn(x));
    2158                 :       5306 :   z = Z + 2-l1;
    2159                 :       5306 :   x += 2; mi = 0;
    2160         [ +  + ]:      28378 :   for (i=0; i<l1; i++)
    2161                 :            :   {
    2162         [ +  + ]:      23072 :     p2[i] = !isrationalzero(gel(x,i)); if (p2[i]) mi = i;
    2163                 :            :   }
    2164                 :            : 
    2165         [ +  + ]:      39319 :   for (i=l1; i<=l2; i++)
    2166                 :            :   {
    2167         [ +  + ]:      34013 :     p2[i] = !isrationalzero(gel(x,i)); if (p2[i]) mi = i;
    2168                 :      34013 :     p1=gen_0; av=avma; l=((i+1)>>1) - 1;
    2169         [ +  + ]:     381521 :     for (j=i-mi; j<=minss(l,mi); j++)
    2170 [ +  + ][ +  + ]:     347508 :       if (p2[j] && p2[i-j]) p1 = gadd(p1, gmul(gel(x,j),gel(x,i-j)));
    2171                 :      34013 :     p1 = gshift(p1,1);
    2172 [ +  + ][ +  + ]:      34013 :     if ((i&1) == 0 && p2[i>>1])
    2173                 :       9520 :       p1 = gadd(p1, gsqr(gel(x,i>>1)));
    2174                 :      34013 :     gel(z,i) = gerepileupto(av,p1);
    2175                 :            :   }
    2176                 :       5313 :   return Z;
    2177                 :            : }
    2178                 :            : 
    2179                 :            : GEN
    2180                 :  872339289 : gsqr(GEN x)
    2181                 :            : {
    2182                 :            :   long i, lx;
    2183                 :            :   pari_sp av, tetpil;
    2184                 :            :   GEN z, p1, p2, p3, p4;
    2185                 :            : 
    2186   [ +  +  +  +  :  872339289 :   switch(typ(x))
          +  +  +  +  +  
          +  +  +  +  +  
                +  -  - ]
    2187                 :            :   {
    2188                 :  849786945 :     case t_INT: return sqri(x);
    2189                 :   15468825 :     case t_REAL: return sqrr(x);
    2190                 :     141675 :     case t_INTMOD: { GEN X = gel(x,1);
    2191                 :     141675 :       z = cgetg(3,t_INTMOD);
    2192                 :     141678 :       gel(z,2) = gerepileuptoint((pari_sp)z, remii(sqri(gel(x,2)), X));
    2193                 :     141681 :       gel(z,1) = icopy(X); return z;
    2194                 :            :     }
    2195                 :      91218 :     case t_FRAC: return sqrfrac(x);
    2196                 :            : 
    2197                 :            :     case t_COMPLEX:
    2198         [ +  + ]:    2830324 :       if (isintzero(gel(x,1))) {
    2199                 :      16998 :         av = avma;
    2200                 :      16998 :         return gerepileupto(av, gneg(gsqr(gel(x,2))));
    2201                 :            :       }
    2202                 :    2813326 :       z = cgetg(3,t_COMPLEX); av = avma;
    2203                 :    2813326 :       p1 = gadd(gel(x,1),gel(x,2));
    2204                 :    2813326 :       p2 = gsub(gel(x,1), gel(x,2));
    2205                 :    2813326 :       p3 = gmul(gel(x,1),gel(x,2));
    2206                 :    2813326 :       tetpil = avma;
    2207                 :    2813326 :       gel(z,1) = gmul(p1,p2);
    2208                 :    2813326 :       gel(z,2) = gshift(p3,1); gerepilecoeffssp(av,tetpil,z+1,2); return z;
    2209                 :            : 
    2210                 :            :     case t_PADIC:
    2211                 :       1848 :       z = cgetg(5,t_PADIC);
    2212 [ +  + ][ +  - ]:       1848 :       i = (equaliu(gel(x,2), 2) && signe(gel(x,4)))? 1: 0;
    2213 [ +  + ][ +  + ]:       1848 :       if (i && precp(x) == 1) i = 2; /* (1 + O(2))^2 = 1 + O(2^3) */
    2214                 :       1848 :       z[1] = evalprecp(precp(x)+i) | evalvalp(valp(x) << 1);
    2215                 :       1848 :       gel(z,2) = icopy(gel(x,2));
    2216                 :       1848 :       gel(z,3) = shifti(gel(x,3), i); av = avma;
    2217                 :       1848 :       gel(z,4) = gerepileuptoint(av, remii(sqri(gel(x,4)), gel(z,3)));
    2218                 :       1848 :       return z;
    2219                 :            : 
    2220                 :         28 :     case t_QUAD: z = cgetg(4,t_QUAD);
    2221                 :         28 :       p1 = gel(x,1);
    2222                 :         28 :       gel(z,1) = ZX_copy(p1); av = avma;
    2223                 :         28 :       p2 = gsqr(gel(x,2));
    2224                 :         28 :       p3 = gsqr(gel(x,3));
    2225                 :         28 :       p4 = gmul(gneg_i(gel(p1,2)),p3);
    2226                 :            : 
    2227         [ +  + ]:         28 :       if (gequal0(gel(p1,3)))
    2228                 :            :       {
    2229                 :          7 :         tetpil = avma;
    2230                 :          7 :         gel(z,2) = gerepile(av,tetpil,gadd(p4,p2));
    2231                 :          7 :         av = avma;
    2232                 :          7 :         p2 = gmul(gel(x,2),gel(x,3)); tetpil = avma;
    2233                 :          7 :         gel(z,3) = gerepile(av,tetpil,gmul2n(p2,1)); return z;
    2234                 :            :       }
    2235                 :            : 
    2236                 :         21 :       p1 = gmul2n(gmul(gel(x,2),gel(x,3)), 1);
    2237                 :         21 :       tetpil = avma;
    2238                 :         21 :       gel(z,2) = gadd(p2,p4);
    2239                 :         21 :       gel(z,3) = gadd(p1,p3);
    2240                 :         21 :       gerepilecoeffssp(av,tetpil,z+2,2); return z;
    2241                 :            : 
    2242                 :            :     case t_POLMOD:
    2243                 :      22347 :       return sqr_polmod(gel(x,1), gel(x,2));
    2244                 :            : 
    2245                 :    2200777 :     case t_FFELT: return FF_sqr(x);
    2246                 :            : 
    2247                 :            :     case t_POL:
    2248                 :            :     {
    2249                 :    1697386 :       GEN a = x, p = NULL, pol = NULL;
    2250                 :    1697386 :       av = avma;
    2251         [ +  + ]:    1697386 :       if (RgX_is_ZX(x)) return ZX_sqr(x);
    2252         [ -  + ]:      28378 :       if (ff_poltype(&x,&p,&pol))
    2253                 :            :       {
    2254                 :          0 :         z = ZX_sqr(x);
    2255         [ #  # ]:          0 :         if (p) z = FpX_to_mod(z,p);
    2256         [ #  # ]:          0 :         if (pol) z = Kronecker_to_mod(z,pol);
    2257                 :          0 :         z = gerepileupto(av, z);
    2258                 :            :       }
    2259                 :      28378 :       else { avma = av; z = RgX_sqr(a); }
    2260                 :    1697162 :       return z;
    2261                 :            :     }
    2262                 :            : 
    2263                 :            :     case t_SER:
    2264                 :       2177 :       lx = lg(x);
    2265         [ +  + ]:       2177 :       if (ser_isexactzero(x)) {
    2266                 :          7 :         GEN z = gcopy(x);
    2267                 :          7 :         setvalp(z, 2*valp(x));
    2268                 :          7 :         return z;
    2269                 :            :       }
    2270         [ +  + ]:       2170 :       if (lx < 40)
    2271                 :       2058 :         return normalize( sqr_ser_part(x, 0, lx-3) );
    2272                 :            :       else
    2273                 :            :       {
    2274                 :        112 :         pari_sp av = avma;
    2275                 :        112 :         GEN z = cgetg(lx,t_SER), p = NULL;
    2276                 :        112 :         z[1] = evalvalp(2*valp(x)) | evalvarn(varn(x)) | evalsigne(1);
    2277                 :        112 :         x = ser2pol_i(x,lx);
    2278         [ +  + ]:        112 :         if (RgX_is_FpX(x,&p))
    2279                 :            :         {
    2280         [ +  - ]:          7 :           if (!p) x = ZX_sqr(x);
    2281                 :            :           else
    2282                 :            :           {
    2283                 :          0 :             x = RgX_to_FpX(x, p);
    2284                 :          0 :             x = FpX_to_mod(ZX_sqr(x), p);
    2285                 :            :           }
    2286                 :            :         }
    2287                 :            :         else
    2288                 :        105 :           x = RgXn_sqr(x, lx-2);
    2289                 :        112 :         z = fill_ser(z, x);
    2290                 :        112 :         return gerepilecopy(av, z);
    2291                 :            :       }
    2292                 :            : 
    2293                 :          7 :     case t_RFRAC: z = cgetg(3,t_RFRAC);
    2294                 :          7 :       gel(z,1) = gsqr(gel(x,1));
    2295                 :          7 :       gel(z,2) = gsqr(gel(x,2)); return z;
    2296                 :            : 
    2297                 :        273 :     case t_MAT: return RgM_sqr(x);
    2298                 :         14 :     case t_QFR: return qfrsqr(x);
    2299                 :      95445 :     case t_QFI: return qfisqr(x);
    2300                 :            :     case t_VECSMALL:
    2301                 :          0 :       z = cgetg_copy(x, &lx);
    2302         [ #  # ]:          0 :       for (i=1; i<lx; i++)
    2303                 :            :       {
    2304                 :          0 :         long xi = x[i];
    2305 [ #  # ][ #  # ]:          0 :         if (xi < 1 || xi >= lx) pari_err_TYPE2("*",x,x);
    2306                 :          0 :         z[i] = x[xi];
    2307                 :            :       }
    2308                 :          0 :       return z;
    2309                 :            :   }
    2310                 :          0 :   pari_err_TYPE2("*",x,x);
    2311                 :  872337372 :   return NULL; /* not reached */
    2312                 :            : }
    2313                 :            : 
    2314                 :            : /********************************************************************/
    2315                 :            : /**                                                                **/
    2316                 :            : /**                           DIVISION                             **/
    2317                 :            : /**                                                                **/
    2318                 :            : /********************************************************************/
    2319                 :            : static GEN
    2320                 :     270646 : div_rfrac_scal(GEN x, GEN y)
    2321                 :            : {
    2322                 :     270646 :   pari_sp av = avma;
    2323                 :     270646 :   GEN d = rfrac_denom_mul_scal(gel(x,2), y);
    2324                 :     270646 :   return gerepileupto(av, gred_rfrac_simple(gel(x,1), d));
    2325                 :            : }
    2326                 :            : static GEN
    2327                 :    1004057 : div_scal_rfrac(GEN x, GEN y)
    2328                 :            : {
    2329                 :    1004057 :   GEN y1 = gel(y,1), y2 = gel(y,2);
    2330                 :    1004057 :   pari_sp av = avma;
    2331 [ +  + ][ -  + ]:    1004057 :   if (typ(y1) == t_POL && varn(y2) == varn(y1))
    2332                 :            :   {
    2333         [ #  # ]:          0 :     if (degpol(y1)) return gerepileupto(av, gred_rfrac_simple(gmul(x, y2), y1));
    2334                 :          0 :     y1 = gel(y1,2);
    2335                 :            :   }
    2336                 :    1004057 :   return RgX_Rg_mul(y2, gdiv(x,y1));
    2337                 :            : }
    2338                 :            : static GEN
    2339                 :    1186329 : div_rfrac(GEN x, GEN y)
    2340                 :    1186329 : { return mul_rfrac(gel(x,1),gel(x,2), gel(y,2),gel(y,1)); }
    2341                 :            : 
    2342                 :            : static GEN
    2343                 :      90834 : div_ser_scal(GEN x, GEN y) {
    2344                 :            :   long i, lx;
    2345                 :            :   GEN z;
    2346         [ +  + ]:      90834 :   if (ser_isexactzero(x))
    2347                 :            :   {
    2348         [ +  - ]:          7 :     if (lg(x) == 2) return gcopy(x);
    2349                 :          0 :     return scalarser(gdiv(gel(x,2), y), varn(x), valp(x));
    2350                 :            :   }
    2351                 :      90827 :   z = cgetg_copy(x, &lx); z[1] = x[1];
    2352         [ +  + ]:     420050 :   for (i=2; i<lx; i++) gel(z,i) = gdiv(gel(x,i),y);
    2353                 :      90834 :   return normalize(z);
    2354                 :            : }
    2355                 :            : GEN
    2356                 :         56 : ser_normalize(GEN x)
    2357                 :            : {
    2358                 :         56 :   long i, lx = lg(x);
    2359                 :            :   GEN c, z;
    2360         [ -  + ]:         56 :   if (lx == 2) return x;
    2361         [ +  + ]:         56 :   c = gel(x,2); if (gequal1(c)) return x;
    2362                 :         28 :   z = cgetg(lx, t_SER); z[1] = x[1]; gel(z,2) = gen_1;
    2363         [ +  + ]:        147 :   for (i=3; i<lx; i++) gel(z,i) = gdiv(gel(x,i),c);
    2364                 :         56 :   return z;
    2365                 :            : }
    2366                 :            : 
    2367                 :            : static GEN
    2368                 :     877876 : div_T_scal(GEN x, GEN y, long tx) {
    2369   [ +  +  +  - ]:     877876 :   switch(tx)
    2370                 :            :   {
    2371                 :     520120 :     case t_POL: return RgX_Rg_div(x, y);
    2372                 :      90834 :     case t_SER: return div_ser_scal(x, y);
    2373                 :     266922 :     case t_RFRAC: return div_rfrac_scal(x,y);
    2374                 :            :   }
    2375                 :          0 :   pari_err_TYPE2("/",x,y);
    2376                 :     877876 :   return NULL; /* not reached */
    2377                 :            : }
    2378                 :            : 
    2379                 :            : static GEN
    2380                 :    8187541 : div_scal_pol(GEN x, GEN y) {
    2381                 :    8187541 :   long ly = lg(y);
    2382                 :            :   pari_sp av;
    2383         [ +  + ]:    8187541 :   if (ly == 3) return scalarpol(gdiv(x,gel(y,2)), varn(y));
    2384         [ +  + ]:    8151069 :   if (isrationalzero(x)) return zeropol(varn(y));
    2385                 :    6099118 :   av = avma;
    2386                 :    8187541 :   return gerepileupto(av, gred_rfrac_simple(x,y));
    2387                 :            : }
    2388                 :            : static GEN
    2389                 :       1512 : div_scal_ser(GEN x, GEN y) { /* TODO: improve */
    2390                 :            :   GEN z;
    2391                 :            :   long ly, i;
    2392         [ -  + ]:       1512 :   if (gequal0(x)) { pari_sp av=avma; return gerepileupto(av, gmul(x, ginv(y))); }
    2393                 :       1512 :   ly = lg(y); z = (GEN)pari_malloc(ly*sizeof(long));
    2394                 :       1512 :   z[0] = evaltyp(t_SER) | evallg(ly);
    2395                 :       1512 :   z[1] = evalsigne(1) | _evalvalp(0) | evalvarn(varn(y));
    2396         [ +  + ]:      40866 :   gel(z,2) = x; for (i=3; i<ly; i++) gel(z,i) = gen_0;
    2397                 :       1512 :   y = gdiv(z,y); pari_free(z); return y;
    2398                 :            : }
    2399                 :            : static GEN
    2400                 :    9143298 : div_scal_T(GEN x, GEN y, long ty) {
    2401   [ +  +  +  - ]:    9143298 :   switch(ty)
    2402                 :            :   {
    2403                 :    8138485 :     case t_POL: return div_scal_pol(x, y);
    2404                 :       1512 :     case t_SER: return div_scal_ser(x, y);
    2405                 :    1003301 :     case t_RFRAC: return div_scal_rfrac(x, y);
    2406                 :            :   }
    2407                 :          0 :   pari_err_TYPE2("/",x,y);
    2408                 :    9143298 :   return NULL; /* not reached */
    2409                 :            : }
    2410                 :            : 
    2411                 :            : /* assume tx = ty = t_SER, same variable vx */
    2412                 :            : static GEN
    2413                 :     330136 : div_ser(GEN x, GEN y, long vx)
    2414                 :            : {
    2415                 :     330136 :   long i, j, l = valp(x) - valp(y), lx = lg(x), ly = lg(y);
    2416                 :            :   GEN y_lead, p1, p2, z;
    2417                 :            : 
    2418         [ +  + ]:     330136 :   if (!signe(y)) pari_err_INV("div_ser", y);
    2419         [ +  + ]:     330129 :   if (ser_isexactzero(x))
    2420                 :            :   {
    2421         [ +  + ]:        658 :     if (lx == 2) return zeroser(vx, l);
    2422                 :          7 :     return scalarser(gmul(gel(x,2),RgX_get_0(y)), varn(x), l);
    2423                 :            :   }
    2424                 :     329471 :   y_lead = gel(y,2);
    2425         [ +  + ]:     329471 :   if (gequal0(y_lead)) /* normalize denominator if leading term is 0 */
    2426                 :            :   {
    2427                 :         14 :     pari_warn(warner,"normalizing a series with 0 leading term");
    2428         [ +  - ]:         14 :     for (l--, ly--,y++; ly > 2; l--, ly--, y++)
    2429                 :            :     {
    2430                 :         14 :       y_lead = gel(y,2);
    2431         [ +  - ]:         14 :       if (!gequal0(y_lead)) break;
    2432                 :            :     }
    2433         [ -  + ]:         14 :     if (ly <= 2) pari_err_INV("div_ser", y);
    2434                 :            :   }
    2435         [ +  + ]:     329471 :   if (ly < lx) lx = ly;
    2436                 :     329471 :   p2 = cgetg(lx, t_VECSMALL); /* left on stack for efficiency */
    2437         [ +  + ]:    1086367 :   for (i=3; i<lx; i++)
    2438                 :            :   {
    2439                 :     756896 :     p1 = gel(y,i);
    2440         [ +  + ]:     756896 :     if (isrationalzero(p1)) p1 = NULL;
    2441                 :     756896 :     gel(p2,i) = p1;
    2442                 :            :   }
    2443                 :     329471 :   z = cgetg(lx,t_SER);
    2444                 :     329471 :   z[1] = evalvalp(l) | evalvarn(vx) | evalsigne(1);
    2445                 :     329471 :   gel(z,2) = gdiv(gel(x,2), y_lead);
    2446         [ +  + ]:    1086367 :   for (i=3; i<lx; i++)
    2447                 :            :   {
    2448                 :     756896 :     pari_sp av = avma;
    2449                 :     756896 :     p1 = gel(x,i);
    2450         [ +  + ]:    8747503 :     for (j=2, l=i; j<i; j++, l--)
    2451         [ +  + ]:    7990607 :       if (p2[l]) p1 = gsub(p1, gmul(gel(z,j), gel(p2,l)));
    2452                 :     756896 :     gel(z,i) = gerepileupto(av, gdiv(p1, y_lead));
    2453                 :            :   }
    2454                 :     330129 :   return normalize(z);
    2455                 :            : }
    2456                 :            : /* x,y compatible PADIC */
    2457                 :            : static GEN
    2458                 :      50081 : divpp(GEN x, GEN y) {
    2459                 :            :   pari_sp av;
    2460                 :            :   long a, b;
    2461                 :            :   GEN z, M;
    2462                 :            : 
    2463         [ +  + ]:      50081 :   if (!signe(gel(y,4))) pari_err_INV("divpp",y);
    2464         [ +  + ]:      50079 :   if (!signe(gel(x,4))) return zeropadic(gel(x,2), valp(x)-valp(y));
    2465                 :      50072 :   a = precp(x);
    2466         [ +  + ]:      50072 :   b = precp(y); if (a > b) { M = gel(y,3); } else { M = gel(x,3); b = a; }
    2467                 :      50072 :   z = cgetg(5, t_PADIC);
    2468                 :      50096 :   z[1] = _evalprecp(b) | evalvalp(valp(x) - valp(y));
    2469                 :      50099 :   gel(z,2) = icopy(gel(x,2));
    2470                 :      50104 :   gel(z,3) = icopy(M); av = avma;
    2471                 :      50105 :   gel(z,4) = gerepileuptoint(av, remii(mulii(gel(x,4), Fp_inv(gel(y,4), M)), M) );
    2472                 :      50111 :   return z;
    2473                 :            : }
    2474                 :            : static GEN
    2475                 :      31955 : div_polmod_same(GEN T, GEN x, GEN y)
    2476                 :            : {
    2477                 :      31955 :   long v = varn(T);
    2478                 :      31955 :   GEN a, z = cgetg(3, t_POLMOD);
    2479                 :      31955 :   gel(z,1) = RgX_copy(T);
    2480 [ +  + ][ +  - ]:      31955 :   if (typ(y) != t_POL || varn(y) != v || lg(y) <= 3)
                 [ +  + ]
    2481                 :      25116 :     a = gdiv(x, y);
    2482 [ +  + ][ +  - ]:       6839 :   else if (typ(x) != t_POL || varn(x) != v || lg(x) <= 3)
                 [ +  + ]
    2483                 :       4382 :   {
    2484                 :       4382 :     pari_sp av = avma;
    2485                 :       4382 :     a = gerepileupto(av, gmul(x, RgXQ_inv(y, T)));
    2486                 :            :   }
    2487 [ +  + ][ +  + ]:       2457 :   else if (degpol(T) == 2 && isint1(gel(T,4))) /* quadratic fields */
    2488                 :       2016 :   {
    2489                 :       2016 :     pari_sp av = avma;
    2490                 :       2016 :     a = quad_polmod_mul(T, x, quad_polmod_conj(y, T));
    2491                 :       2016 :     a = RgX_Rg_div(a, quad_polmod_norm(y, T));
    2492                 :       2016 :     a = gerepileupto(av, a);
    2493                 :            :   }
    2494                 :            :   else
    2495                 :            :   {
    2496                 :        441 :     pari_sp av = avma;
    2497                 :        441 :     GEN p = NULL;
    2498 [ +  - ][ +  + ]:        441 :     if (RgX_is_FpX(T, &p) && RgX_is_FpX(x, &p) && RgX_is_FpX(y, &p) && p)
         [ +  + ][ +  + ]
    2499                 :            :     {
    2500                 :         14 :       T = RgX_to_FpX(T, p); x = RgX_to_FpX(x, p); y = RgX_to_FpX(y, p);
    2501         [ +  + ]:         14 :       if (lgefint(p) == 3)
    2502                 :            :       {
    2503                 :          7 :         ulong pp = p[2];
    2504                 :          7 :         x = ZX_to_Flx(x, pp);
    2505                 :          7 :         y = ZX_to_Flx(y, pp);
    2506                 :          7 :         T = ZX_to_Flx(T, pp);
    2507                 :          7 :         a = Flxq_mul(x, Flxq_inv(y,T,pp),T,pp);
    2508                 :          7 :         a = Flx_to_ZX(a);
    2509                 :            :       }
    2510                 :            :       else
    2511                 :          7 :         a = FpXQ_div(x, y, T, p);
    2512                 :         14 :       a = FpX_to_mod(a, p);
    2513                 :            :     } else
    2514                 :        427 :       a = RgXQ_mul(x, ginvmod(y, gel(z,1)), gel(z,1));
    2515                 :        441 :     a = gerepileupto(av, a);
    2516                 :            :   }
    2517                 :      31955 :   gel(z,2) = a; return z;
    2518                 :            : }
    2519                 :            : GEN
    2520                 :   94587364 : gdiv(GEN x, GEN y)
    2521                 :            : {
    2522                 :   94587364 :   long tx = typ(x), ty = typ(y), lx, ly, vx, vy, i;
    2523                 :            :   pari_sp av, tetpil;
    2524                 :            :   GEN z, p1, p2;
    2525                 :            : 
    2526 [ +  + ][ +  +  :   94587364 :   if (tx == ty) switch(tx)
          +  +  +  +  +  
          +  +  +  +  +  
             -  -  -  - ]
    2527                 :            :   {
    2528                 :            :     case t_INT:
    2529 [ +  + ][ +  + ]:   48270702 :       if (is_pm1(y)) return (signe(y) < 0)? negi(x): icopy(x);
    2530         [ +  + ]:   17874294 :       if (is_pm1(x)) {
    2531                 :    4739587 :         long s = signe(y);
    2532         [ +  + ]:    4739587 :         if (!s) pari_err_INV("gdiv",y);
    2533         [ +  + ]:    4739510 :         if (signe(x) < 0) s = -s;
    2534                 :    4739510 :         z = cgetg(3, t_FRAC);
    2535         [ +  + ]:    4739510 :         gel(z,1) = s<0? gen_m1: gen_1;
    2536                 :    4739510 :         gel(z,2) = absi(y); return z;
    2537                 :            :       }
    2538                 :   13134707 :       return gred_frac2(x,y);
    2539                 :            : 
    2540                 :    7597161 :     case t_REAL: return divrr(x,y);
    2541                 :      19761 :     case t_INTMOD: { GEN X = gel(x,1), Y = gel(y,1);
    2542                 :      19761 :       z = cgetg(3,t_INTMOD);
    2543 [ +  + ][ +  + ]:      19760 :       if (X==Y || equalii(X,Y))
    2544                 :      19754 :         return div_intmod_same(z, X, gel(x,2), gel(y,2));
    2545                 :          7 :       gel(z,1) = gcdii(X,Y);
    2546                 :          7 :       warn_coercion(X,Y,gel(z,1));
    2547                 :          7 :       av = avma; p1 = mulii(gel(x,2), Fp_inv(gel(y,2), gel(z,1)));
    2548                 :          7 :       gel(z,2) = gerepileuptoint(av, remii(p1, gel(z,1))); return z;
    2549                 :            :     }
    2550                 :            :     case t_FRAC: {
    2551                 :     473699 :       GEN x1 = gel(x,1), x2 = gel(x,2);
    2552                 :     473699 :       GEN y1 = gel(y,1), y2 = gel(y,2);
    2553                 :     473699 :       z = cgetg(3, t_FRAC);
    2554                 :     473699 :       p1 = gcdii(x1, y1);
    2555         [ +  + ]:     473699 :       if (!is_pm1(p1)) { x1 = diviiexact(x1,p1); y1 = diviiexact(y1,p1); }
    2556                 :     473699 :       p1 = gcdii(x2, y2);
    2557         [ +  + ]:     473699 :       if (!is_pm1(p1)) { x2 = diviiexact(x2,p1); y2 = diviiexact(y2,p1); }
    2558                 :     473699 :       tetpil = avma;
    2559                 :     473699 :       gel(z,2) = mulii(x2,y1);
    2560                 :     473699 :       gel(z,1) = mulii(x1,y2);
    2561                 :     473699 :       normalize_frac(z);
    2562         [ +  + ]:     473699 :       fix_frac_if_int_GC(z,tetpil);
    2563                 :     473699 :       return z;
    2564                 :            :     }
    2565                 :            :     case t_COMPLEX:
    2566         [ +  + ]:     406417 :       if (isintzero(gel(y,1)))
    2567                 :            :       {
    2568                 :       8106 :         y = gel(y,2);
    2569         [ +  + ]:       8106 :         if (isintzero(gel(x,1))) return gdiv(gel(x,2), y);
    2570                 :       8050 :         z = cgetg(3,t_COMPLEX);
    2571                 :       8050 :         gel(z,1) = gdiv(gel(x,2), y);
    2572                 :       8050 :         av = avma;
    2573                 :       8050 :         gel(z,2) = gerepileupto(av, gneg(gdiv(gel(x,1), y)));
    2574                 :       8050 :         return z;
    2575                 :            :       }
    2576                 :     398311 :       av = avma; p1 = cxnorm(y); p2 = mulcc(x, gconj(y)); tetpil = avma;
    2577                 :     398311 :       return gerepile(av, tetpil, gdiv(p2,p1));
    2578                 :            : 
    2579                 :            :     case t_PADIC:
    2580         [ -  + ]:       2457 :       if (!equalii(gel(x,2),gel(y,2))) pari_err_OP("/",x,y);
    2581                 :       2457 :       return divpp(x, y);
    2582                 :            : 
    2583                 :            :     case t_QUAD:
    2584         [ -  + ]:        322 :       if (!ZX_equal(gel(x,1),gel(y,1))) pari_err_OP("/",x,y);
    2585                 :        322 :       av = avma; p1 = quadnorm(y); p2 = mulqq(x, gconj(y)); tetpil = avma;
    2586                 :        322 :       return gerepile(av, tetpil, gdiv(p2,p1));
    2587                 :            : 
    2588                 :      56119 :     case t_FFELT: return FF_div(x,y);
    2589                 :            : 
    2590                 :            :     case t_POLMOD:
    2591         [ +  + ]:      31962 :       if (RgX_equal_var(gel(x,1), gel(y,1)))
    2592                 :      31955 :         z = div_polmod_same(gel(x,1), gel(x,2), gel(y,2));
    2593                 :            :       else {
    2594                 :          7 :         av = avma;
    2595                 :          7 :         z = gerepileupto(av, gmul(x, ginv(y)));
    2596                 :            :       }
    2597                 :      31962 :       return z;
    2598                 :            : 
    2599                 :            :     case t_POL:
    2600                 :   18381329 :       vx = varn(x);
    2601                 :   18381329 :       vy = varn(y);
    2602         [ +  + ]:   18381329 :       if (vx != vy) {
    2603         [ +  + ]:      98343 :         if (varncmp(vx, vy) < 0) return RgX_Rg_div(x, y);
    2604                 :      49056 :                             else return div_scal_pol(x, y);
    2605                 :            :       }
    2606         [ -  + ]:   18282986 :       if (!signe(y)) pari_err_INV("gdiv",y);
    2607         [ +  + ]:   18282986 :       if (lg(y) == 3) return RgX_Rg_div(x,gel(y,2));
    2608                 :   18173599 :       return gred_rfrac2(x,y);
    2609                 :            : 
    2610                 :            :     case t_SER:
    2611                 :      51836 :       vx = varn(x);
    2612                 :      51836 :       vy = varn(y);
    2613         [ -  + ]:      51836 :       if (vx != vy) {
    2614         [ #  # ]:          0 :         if (varncmp(vx, vy) < 0) return div_ser_scal(x, y);
    2615                 :          0 :                             else return div_scal_ser(x, y);
    2616                 :            :       }
    2617                 :      51836 :       return div_ser(x, y, vx);
    2618                 :            :     case t_RFRAC:
    2619                 :    1190809 :       vx = varn(gel(x,2));
    2620                 :    1190809 :       vy = varn(gel(y,2));
    2621         [ +  + ]:    1190809 :       if (vx != vy) {
    2622         [ +  + ]:       4480 :         if (varncmp(vx, vy) < 0) return div_rfrac_scal(x, y);
    2623                 :        756 :                             else return div_scal_rfrac(x, y);
    2624                 :            :       }
    2625                 :    1186329 :       return div_rfrac(x,y);
    2626                 :            : 
    2627                 :          0 :     case t_QFI: av = avma; return gerepileupto(av, qficomp(x, ginv(y)));
    2628                 :          0 :     case t_QFR: av = avma; return gerepileupto(av, qfrcomp(x, ginv(y)));
    2629                 :            : 
    2630                 :            :     case t_MAT:
    2631                 :          0 :       av = avma; p1 = RgM_inv(y);
    2632         [ #  # ]:          0 :       if (!p1) pari_err_INV("gdiv",y);
    2633                 :          0 :       return gerepileupto(av, RgM_mul(x, p1));
    2634                 :            : 
    2635                 :          0 :     default: pari_err_TYPE2("/",x,y);
    2636                 :            :   }
    2637                 :            : 
    2638 [ +  + ][ +  + ]:   18104790 :   if (tx==t_INT && is_const_t(ty)) /* optimized for speed */
    2639                 :            :   {
    2640                 :     534293 :     long s = signe(x);
    2641         [ +  + ]:     534293 :     if (!s) {
    2642         [ -  + ]:      45085 :       if (gequal0(y)) pari_err_INV("gdiv",y);
    2643      [ +  +  + ]:      45085 :       switch (ty)
    2644                 :            :       {
    2645                 :      41942 :       default: return gen_0;
    2646                 :            :       case t_INTMOD:
    2647                 :         14 :         z = cgetg(3,t_INTMOD);
    2648                 :         14 :         gel(z,1) = icopy(gel(y,1));
    2649                 :         14 :         gel(z,2) = gen_0; return z;
    2650                 :       3129 :       case t_FFELT: return FF_zero(y);
    2651                 :            :       }
    2652                 :            :     }
    2653         [ +  + ]:     489208 :     if (is_pm1(x)) {
    2654         [ +  + ]:     324050 :       if (s > 0) return ginv(y);
    2655                 :      23375 :       av = avma; return gerepileupto(av, ginv(gneg(y)));
    2656                 :            :     }
    2657   [ +  +  +  +  :     165158 :     switch(ty)
             +  +  +  - ]
    2658                 :            :     {
    2659                 :      70169 :       case t_REAL: return divir(x,y);
    2660                 :            :       case t_INTMOD:
    2661                 :         42 :         z = cgetg(3, t_INTMOD);
    2662                 :         42 :         return div_intmod_same(z, gel(y,1), modii(x, gel(y,1)), gel(y,2));
    2663                 :            :       case t_FRAC:
    2664                 :      42290 :         z = cgetg(3,t_FRAC); p1 = gcdii(x,gel(y,1));
    2665         [ +  + ]:      42290 :         if (is_pm1(p1))
    2666                 :            :         {
    2667                 :      34822 :           avma = (pari_sp)z;
    2668                 :      34822 :           gel(z,2) = icopy(gel(y,1));
    2669                 :      34822 :           gel(z,1) = mulii(gel(y,2), x);
    2670                 :      34822 :           normalize_frac(z);
    2671         [ +  + ]:      34822 :           fix_frac_if_int(z);
    2672                 :            :         }
    2673                 :            :         else
    2674                 :            :         {
    2675                 :       7468 :           x = diviiexact(x,p1); tetpil = avma;
    2676                 :       7468 :           gel(z,2) = diviiexact(gel(y,1), p1);
    2677                 :       7468 :           gel(z,1) = mulii(gel(y,2), x);
    2678                 :       7468 :           normalize_frac(z);
    2679         [ +  + ]:       7468 :           fix_frac_if_int_GC(z,tetpil);
    2680                 :            :         }
    2681                 :      42290 :         return z;
    2682                 :            : 
    2683                 :        217 :       case t_FFELT: return Z_FF_div(x,y);
    2684                 :      52356 :       case t_COMPLEX: return divRc(x,y);
    2685                 :         42 :       case t_PADIC: return divTp(x, y);
    2686                 :            :       case t_QUAD:
    2687                 :         42 :         av = avma; p1 = quadnorm(y); p2 = mulRq(x, gconj(y)); tetpil = avma;
    2688                 :         42 :         return gerepile(av, tetpil, gdiv(p2,p1));
    2689                 :            :     }
    2690                 :            :   }
    2691         [ +  + ]:   17570497 :   if (gequal0(y))
    2692                 :            :   {
    2693 [ +  + ][ +  + ]:         35 :     if (is_matvec_t(tx) && lg(x) == 1) return gcopy(x);
    2694         [ +  + ]:         14 :     if (ty != t_MAT) pari_err_INV("gdiv",y);
    2695                 :            :   }
    2696                 :            : 
    2697 [ +  + ][ +  + ]:   17570469 :   if (is_const_t(tx) && is_const_t(ty)) switch(tx)
           [ +  +  +  +  
             +  +  +  - ]
    2698                 :            :   {
    2699                 :            :     case t_REAL:
    2700   [ +  +  +  +  :    5054695 :       switch(ty)
                      + ]
    2701                 :            :       {
    2702                 :    4632918 :         case t_INT: return divri(x,y);
    2703                 :            :         case t_FRAC:
    2704                 :     134364 :           av = avma; z = divri(mulri(x,gel(y,2)), gel(y,1));
    2705                 :     134364 :           return gerepileuptoleaf(av, z);
    2706                 :     287385 :         case t_COMPLEX: return divRc(x, y);
    2707                 :          7 :         case t_QUAD: return divfq(x, y, lg(x));
    2708                 :         21 :         default: pari_err_TYPE2("/",x,y);
    2709                 :            :       }
    2710                 :            : 
    2711                 :            :     case t_INTMOD:
    2712   [ +  +  +  -  :        560 :       switch(ty)
             +  +  +  - ]
    2713                 :            :       {
    2714                 :            :         case t_INT:
    2715                 :        427 :           z = cgetg(3, t_INTMOD);
    2716                 :        427 :           return div_intmod_same(z, gel(x,1), gel(x,2), modii(y, gel(x,1)));
    2717                 :         28 :         case t_FRAC: { GEN X = gel(x,1);
    2718                 :         28 :           z = cgetg(3,t_INTMOD); p1 = remii(mulii(gel(y,2), gel(x,2)), X);
    2719                 :         28 :           return div_intmod_same(z, X, p1, modii(gel(y,1), X));
    2720                 :            :         }
    2721                 :            :         case t_FFELT:
    2722         [ -  + ]:         63 :           if (!equalii(gel(x,1),FF_p_i(y)))
    2723                 :          0 :             pari_err_OP("/",x,y);
    2724                 :         63 :           return Z_FF_div(gel(x,2),y);
    2725                 :            : 
    2726                 :            :         case t_COMPLEX:
    2727                 :          0 :           av = avma;
    2728                 :          0 :           return gerepileupto(av, mulRc_direct(gdiv(x,cxnorm(y)), gconj(y)));
    2729                 :            : 
    2730                 :            :         case t_QUAD:
    2731                 :          7 :           av = avma; p1 = quadnorm(y); p2 = gmul(x,gconj(y)); tetpil = avma;
    2732                 :          7 :           return gerepile(av,tetpil, gdiv(p2,p1));
    2733                 :            : 
    2734                 :          7 :         case t_PADIC: { GEN X = gel(x,1);
    2735                 :          7 :           z = cgetg(3, t_INTMOD);
    2736                 :          7 :           return div_intmod_same(z, X, gel(x,2), padic_to_Fp(y, X));
    2737                 :            :         }
    2738                 :         28 :         case t_REAL: pari_err_TYPE2("/",x,y);
    2739                 :            :       }
    2740                 :            : 
    2741                 :            :     case t_FRAC:
    2742   [ +  +  +  +  :     392473 :       switch(ty)
             +  +  +  - ]
    2743                 :            :       {
    2744                 :     377234 :         case t_INT: z = cgetg(3, t_FRAC);
    2745                 :     377234 :         p1 = gcdii(y,gel(x,1));
    2746         [ +  + ]:     377234 :         if (is_pm1(p1))
    2747                 :            :         {
    2748                 :     218146 :           avma = (pari_sp)z; tetpil = 0;
    2749                 :     218146 :           gel(z,1) = icopy(gel(x,1));
    2750                 :            :         }
    2751                 :            :         else
    2752                 :            :         {
    2753                 :     159088 :           y = diviiexact(y,p1); tetpil = avma;
    2754                 :     159088 :           gel(z,1) = diviiexact(gel(x,1), p1);
    2755                 :            :         }
    2756                 :     377234 :         gel(z,2) = mulii(gel(x,2),y);
    2757                 :     377234 :         normalize_frac(z);
    2758 [ +  + ][ -  + ]:     377234 :         if (tetpil) fix_frac_if_int_GC(z,tetpil);
    2759                 :     377234 :         return z;
    2760                 :            : 
    2761                 :            :         case t_REAL:
    2762                 :      14385 :           av=avma; p1=mulri(y,gel(x,2)); tetpil=avma;
    2763                 :      14385 :           return gerepile(av, tetpil, divir(gel(x,1), p1));
    2764                 :            : 
    2765                 :          7 :         case t_INTMOD: { GEN Y = gel(y,1);
    2766                 :          7 :           z = cgetg(3,t_INTMOD); p1 = remii(mulii(gel(y,2),gel(x,2)), Y);
    2767                 :          7 :           return div_intmod_same(z, Y, modii(gel(x,1), Y), p1);
    2768                 :            :         }
    2769                 :            : 
    2770                 :         28 :         case t_FFELT: av=avma;
    2771                 :         28 :           return gerepileupto(av,Z_FF_div(gel(x,1),FF_Z_mul(y,gel(x,2))));
    2772                 :            : 
    2773                 :        798 :         case t_COMPLEX: return divRc(x, y);
    2774                 :            : 
    2775                 :            :         case t_PADIC:
    2776         [ -  + ]:         14 :           if (!signe(gel(x,1))) return gen_0;
    2777                 :         14 :           return divTp(x, y);
    2778                 :            : 
    2779                 :            :         case t_QUAD:
    2780                 :          7 :           av=avma; p1=quadnorm(y); p2=gmul(x,gconj(y)); tetpil=avma;
    2781                 :          7 :           return gerepile(av,tetpil,gdiv(p2,p1));
    2782                 :            :       }
    2783                 :            : 
    2784                 :            :     case t_FFELT:
    2785   [ +  +  +  + ]:       4459 :       switch (ty)
    2786                 :            :       {
    2787                 :       4340 :         case t_INT: return FF_Z_Z_muldiv(x,gen_1,y);
    2788                 :         28 :         case t_FRAC: return FF_Z_Z_muldiv(x,gel(y,2),gel(y,1));
    2789                 :            :         case t_INTMOD:
    2790         [ -  + ]:         49 :           if (!equalii(gel(y,1),FF_p_i(x)))
    2791                 :          0 :             pari_err_OP("/",x,y);
    2792                 :         49 :           return FF_Z_Z_muldiv(x,gen_1,gel(y,2));
    2793                 :            :         default:
    2794                 :         42 :         pari_err_TYPE2("/",x,y);
    2795                 :            :       }
    2796                 :          0 :       break;
    2797                 :            : 
    2798                 :            :     case t_COMPLEX:
    2799   [ +  -  -  -  :    1162198 :       switch(ty)
                      - ]
    2800                 :            :       {
    2801                 :    1162198 :         case t_INT: case t_REAL: case t_FRAC: return divcR(x,y);
    2802                 :          0 :         case t_INTMOD: return mulRc_direct(ginv(y), x);
    2803                 :            :         case t_PADIC:
    2804         [ #  # ]:          0 :           return Zp_nosquare_m1(gel(y,2))? divcR(x,y): divTp(x, y);
    2805                 :            :         case t_QUAD:
    2806         [ #  # ]:          0 :           lx = precision(x); if (!lx) pari_err_OP("/",x,y);
    2807                 :          0 :           return divfq(x, y, lx);
    2808                 :            :       }
    2809                 :            : 
    2810                 :            :     case t_PADIC:
    2811   [ +  +  +  +  :        994 :       switch(ty)
                      + ]
    2812                 :            :       {
    2813                 :        945 :         case t_INT: case t_FRAC: { GEN p = gel(x,2);
    2814                 :        945 :           return signe(gel(x,4))? divpT(x, y)
    2815         [ +  + ]:        945 :                             : zeropadic(p, valp(x) - Q_pval(y,p));
    2816                 :            :         }
    2817                 :          7 :         case t_INTMOD: { GEN Y = gel(y,1);
    2818                 :          7 :           z = cgetg(3, t_INTMOD);
    2819                 :          7 :           return div_intmod_same(z, Y, padic_to_Fp(x, Y), gel(y,2));
    2820                 :            :         }
    2821                 :            :         case t_COMPLEX: case t_QUAD:
    2822                 :          7 :           av=avma; p1=gmul(x,gconj(y)); p2=gnorm(y); tetpil=avma;
    2823                 :          7 :           return gerepile(av,tetpil,gdiv(p1,p2));
    2824                 :            : 
    2825                 :         28 :         case t_REAL: pari_err_TYPE2("/",x,y);
    2826                 :            :       }
    2827                 :            : 
    2828                 :            :     case t_QUAD:
    2829   [ +  +  +  -  :        889 :       switch (ty)
                      + ]
    2830                 :            :       {
    2831                 :            :         case t_INT: case t_INTMOD: case t_FRAC:
    2832                 :        840 :           z = cgetg(4,t_QUAD);
    2833                 :        840 :           gel(z,1) = ZX_copy(gel(x,1));
    2834                 :        840 :           gel(z,2) = gdiv(gel(x,2), y);
    2835                 :        840 :           gel(z,3) = gdiv(gel(x,3), y); return z;
    2836                 :         28 :         case t_REAL: return divqf(x, y, lg(y));
    2837                 :          7 :         case t_PADIC: return divTp(x, y);
    2838                 :            :         case t_COMPLEX:
    2839         [ #  # ]:          0 :           ly = precision(y); if (!ly) pari_err_OP("/",x,y);
    2840                 :          0 :           return divqf(x, y, ly);
    2841                 :            :       }
    2842                 :            :   }
    2843   [ +  +  -  + ]:   10954222 :   switch(ty) {
    2844                 :            :     case t_REAL: case t_INTMOD: case t_PADIC: case t_POLMOD:
    2845                 :      23157 :       return gmul(x, ginv(y)); /* missing gerepile, for speed */
    2846                 :            :     case t_MAT:
    2847                 :         28 :       av = avma; p1 = RgM_inv(y);
    2848         [ +  + ]:         28 :       if (!p1) pari_err_INV("gdiv",y);
    2849                 :         21 :       return gerepileupto(av, gmul(x, p1));
    2850                 :            :     case t_VEC: case t_COL:
    2851                 :            :     case t_LIST: case t_STR: case t_VECSMALL: case t_CLOSURE:
    2852                 :          0 :       pari_err_TYPE2("/",x,y);
    2853                 :            :   }
    2854      [ +  -  + ]:   10931037 :   switch(tx) {
    2855                 :            :     case t_VEC: case t_COL: case t_MAT:
    2856                 :     290454 :       z = cgetg_copy(x, &lx);
    2857         [ +  + ]:    1118194 :       for (i=1; i<lx; i++) gel(z,i) = gdiv(gel(x,i),y);
    2858                 :     290454 :       return z;
    2859                 :            :     case t_LIST: case t_STR: case t_VECSMALL: case t_CLOSURE:
    2860                 :          0 :       pari_err_TYPE2("/",x,y);
    2861                 :            :   }
    2862                 :            : 
    2863                 :   10640583 :   vy = gvar(y);
    2864         [ +  + ]:   10640583 :   if (tx == t_POLMOD) { GEN X = gel(x,1);
    2865                 :       8561 :     vx = varn(X);
    2866         [ +  + ]:       8561 :     if (vx != vy) {
    2867         [ +  + ]:       8414 :       if (varncmp(vx, vy) > 0) return div_scal_T(x, y, ty);
    2868                 :       8183 :       z = cgetg(3,t_POLMOD);
    2869                 :       8183 :       gel(z,1) = RgX_copy(X);
    2870                 :       8183 :       gel(z,2) = gdiv(gel(x,2), y); return z;
    2871                 :            :     }
    2872                 :            :     /* y is POL, SER or RFRAC */
    2873                 :        147 :     av = avma;
    2874         [ -  + ]:        147 :     switch(ty)
    2875                 :            :     {
    2876                 :          0 :       case t_RFRAC: y = gmod(ginv(y), X); break;
    2877                 :        147 :       default: y = ginvmod(gmod(y,X), X);
    2878                 :            :     }
    2879                 :        140 :     return gerepileupto(av, mul_polmod_same(X, gel(x,2), y));
    2880                 :            :   }
    2881                 :            :   /* x and y are not both is_scalar_t. If one of them is scalar, it's not a
    2882                 :            :    * POLMOD (done already), hence its variable is NO_VARIABLE. If the other has
    2883                 :            :    * variable NO_VARIABLE, then the operation is incorrect */
    2884                 :   10632022 :   vx = gvar(x);
    2885         [ +  + ]:   10632022 :   if (vx != vy) { /* includes cases where one is scalar */
    2886         [ +  + ]:   10020943 :     if (varncmp(vx, vy) < 0) return div_T_scal(x, y, tx);
    2887                 :    9143067 :                         else return div_scal_T(x, y, ty);
    2888                 :            :   }
    2889   [ +  +  +  + ]:     611079 :   switch(tx)
    2890                 :            :   {
    2891                 :            :     case t_POL:
    2892      [ +  +  - ]:      79554 :       switch(ty)
    2893                 :            :       {
    2894                 :            :         case t_SER:
    2895         [ -  + ]:         28 :           if (lg(y) == 2)
    2896                 :          0 :             return zeroser(vx, RgX_val(x) - valp(y));
    2897                 :         28 :           p1 = RgX_to_ser(x,lg(y));
    2898                 :         28 :           p2 = div_ser(p1, y, vx);
    2899                 :         28 :           settyp(p1, t_VECSMALL); /* p1 left on stack */
    2900                 :         28 :           return p2;
    2901                 :            : 
    2902                 :            :         case t_RFRAC:
    2903                 :            :         {
    2904                 :      79526 :           GEN y1 = gel(y,1), y2 = gel(y,2);
    2905 [ +  + ][ -  + ]:      79526 :           if (typ(y1) == t_POL && varn(y1) == vx)
    2906                 :          0 :             return mul_rfrac_scal(y2, y1, x);
    2907                 :      79526 :           av = avma;
    2908                 :      79526 :           return gerepileupto(av, RgX_Rg_div(RgX_mul(y2, x), y1));
    2909                 :            :         }
    2910                 :            :       }
    2911                 :          0 :       break;
    2912                 :            : 
    2913                 :            :     case t_SER:
    2914      [ +  -  - ]:     278377 :       switch(ty)
    2915                 :            :       {
    2916                 :            :         case t_POL:
    2917         [ +  + ]:     278377 :           if (lg(x) == 2)
    2918                 :        105 :             return zeroser(vx, valp(x) - RgX_val(y));
    2919                 :     278272 :           p1 = RgX_to_ser_inexact(y,lg(x));
    2920                 :     278272 :           p2 = div_ser(x, p1, vx);
    2921                 :     278272 :           settyp(p1, t_VECSMALL); /* p1 left on stack */
    2922                 :     278272 :           return p2;
    2923                 :            :         case t_RFRAC:
    2924                 :          0 :           av = avma;
    2925                 :          0 :           return gerepileupto(av, gdiv(gmul(x,gel(y,2)), gel(y,1)));
    2926                 :            :       }
    2927                 :          0 :       break;
    2928                 :            : 
    2929                 :            :     case t_RFRAC:
    2930      [ +  -  - ]:     253134 :       switch(ty)
    2931                 :            :       {
    2932                 :     253134 :         case t_POL: return div_rfrac_pol(gel(x,1),gel(x,2), y);
    2933                 :            :         case t_SER:
    2934                 :          0 :           av = avma; z = RgX_to_ser_inexact(gel(x,2), lg(y));
    2935                 :          0 :           return gerepileupto(av, gdiv(gel(x,1), gmul(z,y)));
    2936                 :            :       }
    2937                 :          0 :       break;
    2938                 :            :   }
    2939                 :         14 :   pari_err_TYPE2("/",x,y);
    2940                 :   94587065 :   return NULL; /* not reached */
    2941                 :            : }
    2942                 :            : 
    2943                 :            : /********************************************************************/
    2944                 :            : /**                                                                **/
    2945                 :            : /**                     SIMPLE MULTIPLICATION                      **/
    2946                 :            : /**                                                                **/
    2947                 :            : /********************************************************************/
    2948                 :            : GEN
    2949                 :   18322157 : gmulsg(long s, GEN y)
    2950                 :            : {
    2951                 :            :   long ly, i;
    2952                 :            :   pari_sp av;
    2953                 :            :   GEN z;
    2954                 :            : 
    2955   [ +  +  +  +  :   18322157 :   switch(typ(y))
          +  +  +  +  +  
             +  +  +  +  
                      - ]
    2956                 :            :   {
    2957                 :    9620141 :     case t_INT:  return mulsi(s,y);
    2958                 :    5956346 :     case t_REAL: return mulsr(s,y);
    2959                 :     168075 :     case t_INTMOD: { GEN p = gel(y,1);
    2960                 :     168075 :       z = cgetg(3,t_INTMOD);
    2961                 :     168059 :       gel(z,2) = gerepileuptoint((pari_sp)z, modii(mulsi(s,gel(y,2)), p));
    2962                 :     168067 :       gel(z,1) = icopy(p); return z;
    2963                 :            :     }
    2964                 :     260011 :     case t_FFELT: return FF_Z_mul(y,stoi(s));
    2965                 :            :     case t_FRAC:
    2966         [ +  + ]:     685342 :       if (!s) return gen_0;
    2967                 :     685104 :       z = cgetg(3,t_FRAC);
    2968                 :     685104 :       i = cgcd(s, smodis(gel(y,2), s));
    2969         [ +  + ]:     685104 :       if (i == 1)
    2970                 :            :       {
    2971                 :     318766 :         gel(z,2) = icopy(gel(y,2));
    2972                 :     318766 :         gel(z,1) = mulis(gel(y,1), s);
    2973                 :            :       }
    2974                 :            :       else
    2975                 :            :       {
    2976                 :     366338 :         gel(z,2) = divis(gel(y,2), i);
    2977                 :     366338 :         gel(z,1) = mulis(gel(y,1), s/i);
    2978         [ +  + ]:     366338 :         fix_frac_if_int(z);
    2979                 :            :       }
    2980                 :     685104 :       return z;
    2981                 :            : 
    2982                 :     969583 :     case t_COMPLEX: z = cgetg(3, t_COMPLEX);
    2983                 :     969583 :       gel(z,1) = gmulsg(s,gel(y,1));
    2984                 :     969583 :       gel(z,2) = gmulsg(s,gel(y,2)); return z;
    2985                 :            : 
    2986                 :            :     case t_PADIC:
    2987         [ -  + ]:        714 :       if (!s) return gen_0;
    2988                 :        714 :       av = avma; return gerepileupto(av, mulpp(cvtop2(stoi(s),y), y));
    2989                 :            : 
    2990                 :          7 :     case t_QUAD: z = cgetg(4, t_QUAD);
    2991                 :          7 :       gel(z,1) = ZX_copy(gel(y,1));
    2992                 :          7 :       gel(z,2) = gmulsg(s,gel(y,2));
    2993                 :          7 :       gel(z,3) = gmulsg(s,gel(y,3)); return z;
    2994                 :            : 
    2995                 :       4844 :     case t_POLMOD: z = cgetg(3, t_POLMOD);
    2996                 :       4844 :       gel(z,1) = RgX_copy(gel(y,1));
    2997                 :       4844 :       gel(z,2) = gmulsg(s,gel(y,2)); return z;
    2998                 :            : 
    2999                 :            :     case t_POL:
    3000         [ +  + ]:     468919 :       if (!signe(y)) return RgX_copy(y);
    3001         [ +  + ]:     463718 :       if (!s) return scalarpol(RgX_get_0(y), varn(y));
    3002                 :     459532 :       z = cgetg_copy(y, &ly); z[1]=y[1];
    3003         [ +  + ]:    1629596 :       for (i=2; i<ly; i++) gel(z,i) = gmulsg(s,gel(y,i));
    3004                 :     459532 :       return normalizepol_lg(z, ly);
    3005                 :            : 
    3006                 :            :     case t_SER:
    3007         [ -  + ]:      17935 :       if (ser_isexactzero(y)) return gcopy(y);
    3008         [ -  + ]:      17935 :       if (!s) return scalarser(RgX_get_0(y), varn(y), valp(y));
    3009                 :      17935 :       z = cgetg_copy(y, &ly); z[1]=y[1];
    3010         [ +  + ]:      55225 :       for (i=2; i<ly; i++) gel(z,i) = gmulsg(s,gel(y,i));
    3011                 :      17935 :       return normalize(z);
    3012                 :            : 
    3013                 :            :     case t_RFRAC:
    3014         [ -  + ]:         14 :       if (!s) return zeropol(varn(gel(y,2)));
    3015         [ -  + ]:         14 :       if (s == 1) return gcopy(y);
    3016         [ -  + ]:         14 :       if (s == -1) return gneg(y);
    3017                 :         14 :       return mul_rfrac_scal(gel(y,1), gel(y,2), stoi(s));
    3018                 :            : 
    3019                 :            :     case t_VEC: case t_COL: case t_MAT:
    3020                 :     170226 :       z = cgetg_copy(y, &ly);
    3021         [ +  + ]:     678789 :       for (i=1; i<ly; i++) gel(z,i) = gmulsg(s,gel(y,i));
    3022                 :     170226 :       return z;
    3023                 :            :   }
    3024                 :          0 :   pari_err_TYPE("gmulsg",y);
    3025                 :   18322150 :   return NULL; /* not reached */
    3026                 :            : }
    3027                 :            : 
    3028                 :            : /********************************************************************/
    3029                 :            : /**                                                                **/
    3030                 :            : /**                       SIMPLE DIVISION                          **/
    3031                 :            : /**                                                                **/
    3032                 :            : /********************************************************************/
    3033                 :            : 
    3034                 :            : GEN
    3035                 :    2577274 : gdivgs(GEN x, long s)
    3036                 :            : {
    3037                 :    2577274 :   long tx = typ(x), lx, i;
    3038                 :            :   pari_sp av;
    3039                 :            :   GEN z, y, p1;
    3040                 :            : 
    3041         [ -  + ]:    2577274 :   if (!s)
    3042                 :            :   {
    3043 [ #  # ][ #  # ]:          0 :     if (is_matvec_t(tx) && lg(x) == 1) return gcopy(x);
    3044                 :          0 :     pari_err_INV("gdivgs",gen_0);
    3045                 :            :   }
    3046   [ +  +  +  +  :    2577273 :   switch(tx)
          +  +  +  -  +  
             +  +  +  - ]
    3047                 :            :   {
    3048                 :            :     case t_INT:
    3049                 :     195000 :       av = avma; z = divis_rem(x,s,&i);
    3050         [ +  + ]:     195000 :       if (!i) return z;
    3051                 :            : 
    3052                 :     108178 :       i = cgcd(s, i);
    3053                 :     108178 :       avma=av; z = cgetg(3,t_FRAC);
    3054         [ +  + ]:     108178 :       if (i == 1) y = icopy(x); else { s /= i; y = diviuexact(x, i); }
    3055                 :     108178 :       gel(z,1) = y;
    3056                 :     108178 :       gel(z,2) = stoi(s); normalize_frac(z); return z;
    3057                 :            : 
    3058                 :            :     case t_REAL:
    3059                 :    1672938 :       return divrs(x,s);
    3060                 :            : 
    3061                 :            :     case t_INTMOD:
    3062                 :       7350 :       z = cgetg(3, t_INTMOD);
    3063                 :       7350 :       return div_intmod_same(z, gel(x,1), gel(x,2), modsi(s, gel(x,1)));
    3064                 :            : 
    3065                 :        399 :     case t_FFELT: return FF_Z_Z_muldiv(x,gen_1,stoi(s));
    3066                 :            : 
    3067                 :      91468 :     case t_FRAC: z = cgetg(3, t_FRAC);
    3068                 :      91468 :       i = cgcd(s, smodis(gel(x,1), s));
    3069         [ +  + ]:      91468 :       if (i == 1)
    3070                 :            :       {
    3071                 :      42745 :         gel(z,2) = mulsi(s, gel(x,2));
    3072                 :      42745 :         gel(z,1) = icopy(gel(x,1));
    3073                 :            :       }
    3074                 :            :       else
    3075                 :            :       {
    3076                 :      48723 :         gel(z,2) = mulsi(s/i, gel(x,2));
    3077                 :      48723 :         gel(z,1) = divis(gel(x,1), i);
    3078                 :            :       }
    3079                 :      91468 :       normalize_frac(z);
    3080         [ +  + ]:      91468 :       fix_frac_if_int(z); return z;
    3081                 :            : 
    3082                 :     557592 :     case t_COMPLEX: z = cgetg(3, t_COMPLEX);
    3083                 :     557592 :       gel(z,1) = gdivgs(gel(x,1),s);
    3084                 :     557592 :       gel(z,2) = gdivgs(gel(x,2),s); return z;
    3085                 :            : 
    3086                 :            :     case t_PADIC: /* divpT */
    3087                 :            :     {
    3088                 :      47052 :       GEN p = gel(x,2);
    3089         [ +  + ]:      47052 :       if (!signe(gel(x,4))) return zeropadic(p, valp(x) - u_pval(s,p));
    3090                 :      46674 :       av = avma;
    3091                 :      46674 :       return gerepileupto(av, divpp(x, cvtop2(stoi(s),x)));
    3092                 :            :     }
    3093                 :            : 
    3094                 :          0 :     case t_QUAD: z = cgetg(4, t_QUAD);
    3095                 :          0 :       gel(z,1) = ZX_copy(gel(x,1));
    3096                 :          0 :       gel(z,2) = gdivgs(gel(x,2),s);
    3097                 :          0 :       gel(z,3) = gdivgs(gel(x,3),s); return z;
    3098                 :            : 
    3099                 :       1505 :     case t_POLMOD: z = cgetg(3, t_POLMOD);
    3100                 :       1505 :       gel(z,1) = RgX_copy(gel(x,1));
    3101                 :       1505 :       gel(z,2) = gdivgs(gel(x,2),s); return z;
    3102                 :            : 
    3103                 :            :     case t_RFRAC:
    3104                 :         91 :       av = avma;
    3105                 :         91 :       p1 = ggcd(stoi(s),gel(x,1));
    3106         [ +  + ]:         91 :       if (typ(p1) == t_INT)
    3107                 :            :       {
    3108                 :         42 :         avma = av;
    3109                 :         42 :         z = cgetg(3, t_RFRAC);
    3110                 :         42 :         i = p1[2];
    3111         [ +  - ]:         42 :         if (i == 1)
    3112                 :            :         {
    3113                 :         42 :           gel(z,1) = gcopy(gel(x,1));
    3114                 :         42 :           gel(z,2) = gmulsg(s,gel(x,2));
    3115                 :            :         }
    3116                 :            :         else
    3117                 :            :         {
    3118                 :          0 :           gel(z,1) = gdivgs(gel(x,1), i);
    3119                 :          0 :           gel(z,2) = gmulgs(gel(x,2), s/i);
    3120                 :            :         }
    3121                 :            :       }
    3122                 :            :       else /* t_FRAC */
    3123                 :            :       {
    3124                 :         49 :         z = cgetg(3, t_RFRAC);
    3125                 :         49 :         gel(z,1) = gdiv(gel(x,1), p1);
    3126                 :         49 :         gel(z,2) = RgX_Rg_mul(gel(x,2), gdivsg(s,p1));
    3127                 :         49 :         z = gerepilecopy(av, z);
    3128                 :            :       }
    3129                 :         91 :       return z;
    3130                 :            : 
    3131                 :            :     case t_POL: case t_SER:
    3132                 :       3836 :       z = cgetg_copy(x, &lx); z[1] = x[1];
    3133         [ +  + ]:      13132 :       for (i=2; i<lx; i++) gel(z,i) = gdivgs(gel(x,i),s);
    3134                 :       3836 :       return z;
    3135                 :            :     case t_VEC: case t_COL: case t_MAT:
    3136                 :         42 :       z = cgetg_copy(x, &lx);
    3137         [ +  + ]:        126 :       for (i=1; i<lx; i++) gel(z,i) = gdivgs(gel(x,i),s);
    3138                 :         42 :       return z;
    3139                 :            : 
    3140                 :            :   }
    3141                 :          0 :   pari_err_TYPE2("/",x, stoi(s));
    3142                 :    2577279 :   return NULL; /* not reached */
    3143                 :            : }
    3144                 :            : 
    3145                 :            : /* True shift (exact multiplication by 2^n) */
    3146                 :            : GEN
    3147                 :   28888804 : gmul2n(GEN x, long n)
    3148                 :            : {
    3149                 :            :   long lx, i, k, l;
    3150                 :            :   GEN z, a, b;
    3151                 :            : 
    3152   [ +  +  +  +  :   28888804 :   switch(typ(x))
          +  +  +  +  +  
             +  +  +  +  
                      - ]
    3153                 :            :   {
    3154                 :            :     case t_INT:
    3155         [ +  + ]:   21820764 :       if (n>=0) return shifti(x,n);
    3156         [ +  + ]:     115710 :       if (!signe(x)) return gen_0;
    3157                 :      57372 :       l = vali(x); n = -n;
    3158         [ +  + ]:      57372 :       if (n<=l) return shifti(x,-n);
    3159                 :      35987 :       z = cgetg(3,t_FRAC);
    3160                 :      35987 :       gel(z,1) = shifti(x,-l);
    3161                 :      35987 :       gel(z,2) = int2n(n-l); return z;
    3162                 :            : 
    3163                 :            :     case t_REAL:
    3164                 :    3407870 :       return shiftr(x,n);
    3165                 :            : 
    3166                 :      74184 :     case t_INTMOD: b = gel(x,1); a = gel(x,2);
    3167                 :      74184 :       z = cgetg(3,t_INTMOD);
    3168         [ +  + ]:      74184 :       if (n <= 0) return div_intmod_same(z, b, a, modii(int2n(-n), b));
    3169                 :      74177 :       gel(z,2) = gerepileuptoint((pari_sp)z, modii(shifti(a,n), b));
    3170                 :      74178 :       gel(z,1) = icopy(b); return z;
    3171                 :            : 
    3172                 :      92977 :     case t_FFELT: return FF_mul2n(x,n);
    3173                 :            : 
    3174                 :     101664 :     case t_FRAC: a = gel(x,1); b = gel(x,2);
    3175                 :     101664 :       l = vali(a);
    3176                 :     101664 :       k = vali(b);
    3177         [ +  + ]:     101664 :       if (n+l >= k)
    3178                 :            :       {
    3179         [ +  + ]:      56078 :         if (expi(b) == k) return shifti(a,n-k); /* b power of 2 */
    3180                 :      48651 :         l = n-k; k = -k;
    3181                 :            :       }
    3182                 :            :       else
    3183                 :            :       {
    3184                 :      45586 :         k = -(l+n); l = -l;
    3185                 :            :       }
    3186                 :      94237 :       z = cgetg(3,t_FRAC);
    3187                 :      94237 :       gel(z,1) = shifti(a,l);
    3188                 :      94237 :       gel(z,2) = shifti(b,k); return z;
    3189                 :            : 
    3190                 :    2374333 :     case t_COMPLEX: z = cgetg(3,t_COMPLEX);
    3191                 :    2374333 :       gel(z,1) = gmul2n(gel(x,1),n);
    3192                 :    2374333 :       gel(z,2) = gmul2n(gel(x,2),n); return z;
    3193                 :            : 
    3194                 :         14 :     case t_QUAD: z = cgetg(4,t_QUAD);
    3195                 :         14 :       gel(z,1) = ZX_copy(gel(x,1));
    3196                 :         14 :       gel(z,2) = gmul2n(gel(x,2),n);
    3197                 :         14 :       gel(z,3) = gmul2n(gel(x,3),n); return z;
    3198                 :            : 
    3199                 :      13329 :     case t_POLMOD: z = cgetg(3,t_POLMOD);
    3200                 :      13329 :       gel(z,1) = RgX_copy(gel(x,1));
    3201                 :      13329 :       gel(z,2) = gmul2n(gel(x,2),n); return z;
    3202                 :            : 
    3203                 :            :     case t_POL:
    3204                 :     259389 :       z = cgetg_copy(x, &lx); z[1] = x[1];
    3205         [ +  + ]:    2159408 :       for (i=2; i<lx; i++) gel(z,i) = gmul2n(gel(x,i),n);
    3206                 :     259389 :       return normalizepol_lg(z, lx); /* needed if char = 2 */
    3207                 :            :     case t_SER:
    3208         [ +  + ]:      52521 :       if (ser_isexactzero(x)) return gcopy(x);
    3209                 :      52507 :       z = cgetg_copy(x, &lx); z[1] = x[1];
    3210         [ +  + ]:     848386 :       for (i=2; i<lx; i++) gel(z,i) = gmul2n(gel(x,i),n);
    3211                 :      52507 :       return normalize(z); /* needed if char = 2 */
    3212                 :            :     case t_VEC: case t_COL: case t_MAT:
    3213                 :     689351 :       z = cgetg_copy(x, &lx);
    3214         [ +  + ]:    2835678 :       for (i=1; i<lx; i++) gel(z,i) = gmul2n(gel(x,i),n);
    3215                 :     689351 :       return z;
    3216                 :            : 
    3217                 :            :     case t_RFRAC: /* int2n wrong if n < 0 */
    3218                 :         14 :       return mul_rfrac_scal(gel(x,1),gel(x,2), gmul2n(gen_1,n));
    3219                 :            : 
    3220                 :            :     case t_PADIC: /* int2n wrong if n < 0 */
    3221                 :       2394 :       return gmul(gmul2n(gen_1,n),x);
    3222                 :            :   }
    3223                 :          0 :   pari_err_TYPE("gmul2n",x);
    3224                 :   28888803 :   return NULL; /* not reached */
    3225                 :            : }
    3226                 :            : 
    3227                 :            : /*******************************************************************/
    3228                 :            : /*                                                                 */
    3229                 :            : /*                              INVERSE                            */
    3230                 :            : /*                                                                 */
    3231                 :            : /*******************************************************************/
    3232                 :            : static GEN
    3233                 :      23740 : inv_polmod(GEN T, GEN x)
    3234                 :            : {
    3235                 :      23740 :   GEN z = cgetg(3,t_POLMOD), a;
    3236                 :      23740 :   gel(z,1) = RgX_copy(T);
    3237 [ +  + ][ +  + ]:      23740 :   if (typ(x) != t_POL || varn(x) != varn(T) || lg(x) <= 3)
                 [ +  + ]
    3238                 :       8918 :     a = ginv(x);
    3239                 :            :   else
    3240                 :            :   {
    3241                 :      14822 :     pari_sp av = avma;
    3242         [ +  + ]:      14822 :     if (lg(T) == 5) /* quadratic fields */
    3243                 :      11417 :       a = RgX_Rg_div(quad_polmod_conj(x,T), quad_polmod_norm(x,T));
    3244                 :            :     else
    3245                 :            :     {
    3246                 :       3405 :       GEN p = NULL;
    3247 [ +  + ][ +  + ]:       3405 :       if (RgX_is_FpX(T, &p) && RgX_is_FpX(x, &p) && p)
                 [ +  + ]
    3248                 :            :       {
    3249                 :         14 :         T = RgX_to_FpX(T, p); x = RgX_to_FpX(x, p);
    3250         [ +  + ]:         14 :         if (lgefint(p) == 3)
    3251                 :            :         {
    3252                 :          7 :           ulong pp = p[2];
    3253                 :          7 :           a = Flxq_inv(ZX_to_Flx(x, pp), ZX_to_Flx(T, pp), pp);
    3254                 :          7 :           a = Flx_to_ZX(a);
    3255                 :            :         }
    3256                 :            :         else
    3257                 :          7 :           a = FpXQ_inv(x, T, p);
    3258                 :         14 :         a = FpX_to_mod(a, p);
    3259                 :         14 :         a = gerepileupto(av, a);
    3260                 :            :       }
    3261                 :            :       else {
    3262                 :       3391 :         avma = av;
    3263                 :       3405 :         a = RgXQ_inv(x, gel(z,1));
    3264                 :            :       }
    3265                 :            :     }
    3266                 :            :   }
    3267                 :      23740 :   gel(z,2) = a; return z;
    3268                 :            : }
    3269                 :            : GEN
    3270                 :    7255909 : ginv(GEN x)
    3271                 :            : {
    3272                 :            :   long s;
    3273                 :            :   pari_sp av, tetpil;
    3274                 :            :   GEN z, y, p1, p2;
    3275                 :            : 
    3276   [ +  +  +  +  :    7255909 :   switch(typ(x))
          +  +  +  +  +  
          +  +  +  +  +  
                +  -  - ]
    3277                 :            :   {
    3278                 :            :     case t_INT:
    3279         [ +  + ]:      73794 :       if (is_pm1(x)) return icopy(x);
    3280         [ -  + ]:      41076 :       s = signe(x); if (!s) pari_err_INV("ginv",gen_0);
    3281                 :      41076 :       z = cgetg(3,t_FRAC);
    3282         [ +  + ]:      41076 :       gel(z,1) = s<0? gen_m1: gen_1;
    3283                 :      41076 :       gel(z,2) = absi(x); return z;
    3284                 :            : 
    3285                 :     876731 :     case t_REAL: return invr(x);
    3286                 :            : 
    3287                 :        770 :     case t_INTMOD: z=cgetg(3,t_INTMOD);
    3288                 :        770 :       gel(z,1) = icopy(gel(x,1));
    3289                 :        770 :       gel(z,2) = Fp_inv(gel(x,2),gel(x,1)); return z;
    3290                 :            : 
    3291                 :            :     case t_FRAC: {
    3292                 :     103839 :       GEN a = gel(x,1), b = gel(x,2);
    3293                 :     103839 :       s = signe(a);
    3294 [ +  + ][ +  + ]:     103839 :       if (is_pm1(a)) return s > 0? icopy(b): negi(b);
    3295                 :      39025 :       z = cgetg(3,t_FRAC);
    3296                 :      39025 :       gel(z,1) = icopy(b);
    3297                 :      39025 :       gel(z,2) = icopy(a);
    3298                 :      39025 :       normalize_frac(z); return z;
    3299                 :            :     }
    3300                 :            :     case t_COMPLEX:
    3301                 :     866310 :       av=avma;
    3302                 :     866310 :       p1=cxnorm(x);
    3303                 :     866310 :       p2=mkcomplex(gel(x,1), gneg(gel(x,2)));
    3304                 :     866310 :       tetpil=avma;
    3305                 :     866310 :       return gerepile(av,tetpil,divcR(p2,p1));
    3306                 :            : 
    3307                 :            :     case t_QUAD:
    3308                 :        203 :       av=avma; p1=gnorm(x); p2=gconj(x); tetpil=avma;
    3309                 :        203 :       return gerepile(av,tetpil,gdiv(p2,p1));
    3310                 :            : 
    3311                 :        581 :     case t_PADIC: z = cgetg(5,t_PADIC);
    3312         [ +  + ]:        581 :       if (!signe(gel(x,4))) pari_err_INV("ginv",x);
    3313                 :        574 :       z[1] = _evalprecp(precp(x)) | evalvalp(-valp(x));
    3314                 :        574 :       gel(z,2) = icopy(gel(x,2));
    3315                 :        574 :       gel(z,3) = icopy(gel(x,3));
    3316                 :        574 :       gel(z,4) = Fp_inv(gel(x,4),gel(z,3)); return z;
    3317                 :            : 
    3318                 :      23740 :     case t_POLMOD: return inv_polmod(gel(x,1), gel(x,2));
    3319                 :       4656 :     case t_FFELT: return FF_inv(x);
    3320                 :    5290025 :     case t_POL: return gred_rfrac_simple(gen_1,x);
    3321                 :       1281 :     case t_SER: return gdiv(gen_1,x);
    3322                 :            : 
    3323                 :            :     case t_RFRAC:
    3324                 :            :     {
    3325                 :       2905 :       GEN n = gel(x,1), d = gel(x,2);
    3326                 :       2905 :       pari_sp av = avma, ltop;
    3327         [ -  + ]:       2905 :       if (gequal0(n)) pari_err_INV("ginv",x);
    3328                 :            : 
    3329                 :       2905 :       n = simplify_shallow(n);
    3330 [ +  + ][ +  - ]:       2905 :       if (typ(n) != t_POL || varn(n) != varn(d))
    3331                 :            :       {
    3332         [ +  + ]:       2905 :         if (gequal1(n)) { avma = av; return RgX_copy(d); }
    3333                 :        679 :         ltop = avma;
    3334                 :        679 :         z = RgX_Rg_div(d,n);
    3335                 :            :       } else {
    3336                 :          0 :         ltop = avma;
    3337                 :          0 :         z = cgetg(3,t_RFRAC);
    3338                 :          0 :         gel(z,1) = RgX_copy(d);
    3339                 :          0 :         gel(z,2) = RgX_copy(n);
    3340                 :            :       }
    3341                 :        679 :       stackdummy(av, ltop);
    3342                 :        679 :       return z;
    3343                 :            :     }
    3344                 :            : 
    3345                 :            :     case t_QFR:
    3346                 :          7 :       av = avma; z = cgetg(5, t_QFR);
    3347                 :          7 :       gel(z,1) = gel(x,1);
    3348                 :          7 :       gel(z,2) = negi( gel(x,2) );
    3349                 :          7 :       gel(z,3) = gel(x,3);
    3350                 :          7 :       gel(z,4) = negr( gel(x,4) );
    3351                 :          7 :       return gerepileupto(av, redreal(z));
    3352                 :            : 
    3353                 :            :     case t_QFI:
    3354                 :       9751 :       y = gcopy(x);
    3355 [ +  + ][ +  + ]:       9751 :       if (!equalii(gel(x,1),gel(x,2)) && !equalii(gel(x,1),gel(x,3)))
    3356                 :       9492 :         togglesign(gel(y,2));
    3357                 :       9751 :       return y;
    3358                 :            :     case t_MAT:
    3359                 :            :     {
    3360                 :       1316 :       GEN ff = NULL;
    3361         [ +  + ]:       1316 :       if (RgM_is_FFM(x,&ff))
    3362                 :         42 :         y = FFM_inv(x, ff);
    3363                 :            :       else
    3364                 :       1274 :         y = RgM_inv(x);
    3365         [ -  + ]:       1316 :       if (!y) pari_err_INV("ginv",x);
    3366                 :       1316 :       return y;
    3367                 :            :     }
    3368                 :            :     case t_VECSMALL:
    3369                 :            :     {
    3370                 :          0 :       long i, lx = lg(x)-1;
    3371                 :          0 :       y = zero_zv(lx);
    3372         [ #  # ]:          0 :       for (i=1; i<=lx; i++)
    3373                 :            :       {
    3374                 :          0 :         long xi = x[i];
    3375 [ #  # ][ #  # ]:          0 :         if (xi<1 || xi>lx || y[xi])
                 [ #  # ]
    3376                 :          0 :           pari_err_TYPE("ginv [not a permutation]", x);
    3377                 :          0 :         y[xi] = i;
    3378                 :            :       }
    3379                 :          0 :       return y;
    3380                 :            :     }
    3381                 :            :   }
    3382                 :          0 :   pari_err_TYPE("inverse",x);
    3383                 :    7255895 :   return NULL; /* not reached */
    3384                 :            : }

Generated by: LCOV version 1.9