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 16746-c2cb716) Lines: 1736 1918 90.5 %
Date: 2014-08-31 Functions: 86 87 98.9 %
Legend: Lines: hit not hit | Branches: + taken - not taken # not executed Branches: 1148 1424 80.6 %

           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 long
      34                 :         15 : kro_quad(GEN x, GEN y)
      35                 :            : {
      36                 :         15 :   pari_sp av=avma;
      37                 :         15 :   long k = kronecker(quad_disc(x), y);
      38                 :         15 :   avma = av; return k;
      39                 :            : }
      40                 :            : 
      41                 :            : /* is -1 not a square in Zp, assume p prime */
      42                 :            : INLINE int
      43                 :         20 : Zp_nosquare_m1(GEN p) { return (mod4(p) & 2); /* 2 or 3 mod 4 */ }
      44                 :            : 
      45                 :            : static GEN addsub_pp(GEN x, GEN y, GEN(*op)(GEN,GEN));
      46                 :            : static GEN addsub_frac(GEN x, GEN y, GEN (*op)(GEN,GEN));
      47                 :            : static GEN mulpp(GEN x, GEN y);
      48                 :            : static GEN divpp(GEN x, GEN y);
      49                 :            : /* Argument codes for inline routines
      50                 :            :  * c: complex, p: padic, q: quad, f: floating point (REAL, some complex)
      51                 :            :  * R: without imaginary part (INT, REAL, INTMOD, FRAC, PADIC if -1 not square)
      52                 :            :  * T: some type (to be converted to PADIC)
      53                 :            :  */
      54                 :            : static GEN
      55                 :   18645050 : addRc(GEN x, GEN y) {
      56                 :   18645050 :   GEN z = cgetg(3,t_COMPLEX);
      57                 :   18645050 :   gel(z,1) = gadd(x,gel(y,1));
      58                 :   18645050 :   gel(z,2) = gcopy(gel(y,2)); return z;
      59                 :            : }
      60                 :            : static GEN
      61                 :   26863729 : mulRc(GEN x, GEN y) {
      62                 :   26863729 :   GEN z = cgetg(3,t_COMPLEX);
      63         [ +  + ]:   26863729 :   gel(z,1) = isintzero(gel(y,1))? gen_0: gmul(x,gel(y,1));
      64                 :   26863729 :   gel(z,2) = gmul(x,gel(y,2)); return z;
      65                 :            : }
      66                 :            : /* for INTMODs: can't simplify when Re(x) = gen_0 */
      67                 :            : static GEN
      68                 :         25 : mulRc_direct(GEN x, GEN y) {
      69                 :         25 :   GEN z = cgetg(3,t_COMPLEX);
      70                 :         25 :   gel(z,1) = gmul(x,gel(y,1));
      71                 :         25 :   gel(z,2) = gmul(x,gel(y,2)); return z;
      72                 :            : }
      73                 :            : static GEN
      74                 :     158430 : divRc(GEN x, GEN y) {
      75                 :     158430 :   GEN t = gdiv(x, cxnorm(y)), mt = gneg(t); /* left on stack for efficiency */
      76                 :     158430 :   GEN z = cgetg(3,t_COMPLEX);
      77         [ +  + ]:     158430 :   gel(z,1) = isintzero(gel(y,1))? gen_0: gmul(t, gel(y,1));
      78                 :     158430 :   gel(z,2) = gmul(mt, gel(y,2));
      79                 :     158430 :   return z;
      80                 :            : }
      81                 :            : static GEN
      82                 :    1156716 : divcR(GEN x, GEN y) {
      83                 :    1156716 :   GEN z = cgetg(3,t_COMPLEX);
      84         [ +  + ]:    1156716 :   gel(z,1) = isintzero(gel(x,1))? gen_0: gdiv(gel(x,1), y);
      85                 :    1156716 :   gel(z,2) = gdiv(gel(x,2), y); return z;
      86                 :            : }
      87                 :            : static GEN
      88                 :        690 : addRq(GEN x, GEN y) {
      89                 :        690 :   GEN z = cgetg(4,t_QUAD);
      90                 :        690 :   gel(z,1) = ZX_copy(gel(y,1));
      91                 :        690 :   gel(z,2) = gadd(x, gel(y,2));
      92                 :        690 :   gel(z,3) = gcopy(gel(y,3)); return z;
      93                 :            : }
      94                 :            : static GEN
      95                 :       2165 : mulRq(GEN x, GEN y) {
      96                 :       2165 :   GEN z = cgetg(4,t_QUAD);
      97                 :       2165 :   gel(z,1) = ZX_copy(gel(y,1));
      98                 :       2165 :   gel(z,2) = gmul(x,gel(y,2));
      99                 :       2165 :   gel(z,3) = gmul(x,gel(y,3)); return z;
     100                 :            : }
     101                 :            : static GEN
     102                 :         10 : addqf(GEN x, GEN y, long prec) { pari_sp av = avma;
     103                 :         10 :   long i = gexpo(x) - gexpo(y);
     104         [ +  - ]:         10 :   if (i > 0) prec += nbits2extraprec( i );
     105                 :         10 :   return gerepileupto(av, gadd(y, quadtofp(x, prec)));
     106                 :            : }
     107                 :            : static GEN
     108                 :     704485 : mulrfrac(GEN x, GEN y)
     109                 :            : {
     110                 :     704485 :   pari_sp av = avma;
     111                 :     704485 :   GEN z, a = gel(y,1), b = gel(y,2);
     112         [ +  + ]:     704485 :   if (is_pm1(a)) /* frequent special case */
     113                 :            :   {
     114                 :     185158 :     z = divri(x, b);
     115         [ +  + ]:     185158 :     if (signe(a) < 0) togglesign(z);
     116                 :     185158 :     return z;
     117                 :            :   }
     118                 :     704485 :   return gerepileuptoleaf(av, divri(mulri(x,gel(y,1)), gel(y,2)));
     119                 :            : }
     120                 :            : static GEN
     121                 :         10 : mulqf(GEN x, GEN y, long prec) { pari_sp av = avma;
     122                 :         10 :   return gerepileupto(av, gmul(y, quadtofp(x, prec)));
     123                 :            : }
     124                 :            : static GEN
     125                 :         20 : divqf(GEN x, GEN y, long prec) { pari_sp av = avma;
     126                 :         20 :   return gerepileupto(av, gdiv(quadtofp(x,prec), y));
     127                 :            : }
     128                 :            : static GEN
     129                 :          5 : divfq(GEN x, GEN y, long prec) { pari_sp av = avma;
     130                 :          5 :   return gerepileupto(av, gdiv(x, quadtofp(y,prec)));
     131                 :            : }
     132                 :            : /* y PADIC, x + y by converting x to padic */
     133                 :            : static GEN
     134                 :          5 : addTp(GEN x, GEN y) { pari_sp av = avma; GEN z;
     135                 :            : 
     136         [ -  + ]:          5 :   if (!valp(y)) z = cvtop2(x,y);
     137                 :            :   else {
     138         [ -  + ]:          5 :     long l = signe(gel(y,4))? valp(y) + precp(y): valp(y);
     139                 :          5 :     z  = cvtop(x, gel(y,2), l);
     140                 :            :   }
     141                 :          5 :   return gerepileupto(av, addsub_pp(z, y, addii));
     142                 :            : }
     143                 :            : /* y PADIC, x * y by converting x to padic */
     144                 :            : static GEN
     145                 :      23990 : mulTp(GEN x, GEN y) { pari_sp av = avma;
     146                 :      23990 :   return gerepileupto(av, mulpp(cvtop2(x,y), y));
     147                 :            : }
     148                 :            : /* y PADIC, non zero x / y by converting x to padic */
     149                 :            : static GEN
     150                 :         45 : divTp(GEN x, GEN y) { pari_sp av = avma;
     151                 :         45 :   return gerepileupto(av, divpp(cvtop2(x,y), y));
     152                 :            : }
     153                 :            : /* x PADIC, x / y by converting y to padic. Assume x != 0; otherwise y
     154                 :            :  * converted to O(p^e) and division by 0 */
     155                 :            : static GEN
     156                 :        660 : divpT(GEN x, GEN y) { pari_sp av = avma;
     157                 :        660 :   return gerepileupto(av, divpp(x, cvtop2(y,x)));
     158                 :            : }
     159                 :            : 
     160                 :            : /* z := Mod(x,X) + Mod(y,X) [ t_INTMOD preallocated ], x,y,X INT, 0 <= x,y < X
     161                 :            :  * clean memory from z on */
     162                 :            : static GEN
     163                 :    1007427 : add_intmod_same(GEN z, GEN X, GEN x, GEN y) {
     164         [ +  + ]:    1007427 :   if (lgefint(X) == 3) {
     165                 :     777230 :     ulong u = Fl_add(itou(x),itou(y), X[2]);
     166                 :     777230 :     avma = (pari_sp)z; gel(z,2) = utoi(u);
     167                 :            :   }
     168                 :            :   else {
     169         [ +  + ]:     230197 :     GEN u = addii(x,y); if (cmpii(u, X) >= 0) u = subii(u, X);
     170                 :     230197 :     gel(z,2) = gerepileuptoint((pari_sp)z, u);
     171                 :            :   }
     172                 :    1007427 :   gel(z,1) = icopy(X); return z;
     173                 :            : }
     174                 :            : static GEN
     175                 :     288531 : sub_intmod_same(GEN z, GEN X, GEN x, GEN y) {
     176         [ +  + ]:     288531 :   if (lgefint(X) == 3) {
     177                 :     131756 :     ulong u = Fl_sub(itou(x),itou(y), X[2]);
     178                 :     131756 :     avma = (pari_sp)z; gel(z,2) = utoi(u);
     179                 :            :   }
     180                 :            :   else {
     181         [ +  + ]:     156775 :     GEN u = subii(x,y); if (signe(u) < 0) u = addii(u, X);
     182                 :     156775 :     gel(z,2) = gerepileuptoint((pari_sp)z, u);
     183                 :            :   }
     184                 :     288531 :   gel(z,1) = icopy(X); return z;
     185                 :            : }
     186                 :            : /* cf add_intmod_same */
     187                 :            : static GEN
     188                 :    2325304 : mul_intmod_same(GEN z, GEN X, GEN x, GEN y) {
     189         [ +  + ]:    2325304 :   if (lgefint(X) == 3) {
     190                 :    1824603 :     ulong u = Fl_mul(itou(x),itou(y), X[2]);
     191                 :    1824603 :     avma = (pari_sp)z; gel(z,2) = utoi(u);
     192                 :            :   }
     193                 :            :   else
     194                 :     500701 :     gel(z,2) = gerepileuptoint((pari_sp)z, remii(mulii(x,y), X) );
     195                 :    2325304 :   gel(z,1) = icopy(X); return z;
     196                 :            : }
     197                 :            : /* cf add_intmod_same */
     198                 :            : static GEN
     199                 :      20435 : div_intmod_same(GEN z, GEN X, GEN x, GEN y)
     200                 :            : {
     201         [ +  + ]:      20435 :   if (lgefint(X) == 3) {
     202                 :      15055 :     ulong m = uel(X,2), u = Fl_div(itou(x), itou(y), m);
     203                 :      15050 :     avma = (pari_sp)z; gel(z,2) = utoi(u);
     204                 :            :   }
     205                 :            :   else
     206                 :       5380 :     gel(z,2) = gerepileuptoint((pari_sp)z, remii(mulii(x, Fp_inv(y,X)), X) );
     207                 :      20430 :   gel(z,1) = icopy(X); return z;
     208                 :            : }
     209                 :            : 
     210                 :            : /*******************************************************************/
     211                 :            : /*                                                                 */
     212                 :            : /*        REDUCTION to IRREDUCIBLE TERMS (t_FRAC/t_RFRAC)          */
     213                 :            : /*                                                                 */
     214                 :            : /* (static routines are not memory clean, but OK for gerepileupto) */
     215                 :            : /*******************************************************************/
     216                 :            : /* Compute the denominator of (1/y) * (n/d) = n/yd, y a "scalar".
     217                 :            :  * Sanity check : avoid (1/2) / (Mod(1,2)*x + 1) "=" 1 / (0 * x + 1) */
     218                 :            : static GEN
     219                 :    6833534 : rfrac_denom_mul_scal(GEN d, GEN y)
     220                 :            : {
     221                 :    6833534 :   GEN D = RgX_Rg_mul(d, y);
     222         [ -  + ]:    6833534 :   if (lg(D) != lg(d))
     223                 :            :   { /* try to generate a meaningful diagnostic */
     224                 :          0 :     D = gdiv(leading_term(d), y); /* should fail */
     225                 :          0 :     pari_err_INV("gred_rfrac", y); /* better than nothing */
     226                 :            :   }
     227                 :    6833534 :   return D;
     228                 :            : }
     229                 :            : 
     230                 :            : /* d a t_POL, n a coprime t_POL of same var or "scalar". Not memory clean */
     231                 :            : GEN
     232                 :   39032670 : gred_rfrac_simple(GEN n, GEN d)
     233                 :            : {
     234                 :            :   GEN c, cn, cd, z;
     235                 :   39032670 :   long dd = degpol(d);
     236                 :            : 
     237         [ +  + ]:   39032670 :   if (dd <= 0)
     238                 :            :   {
     239         [ -  + ]:       2655 :     if (dd < 0) pari_err_INV("gred_rfrac_simple", d);
     240                 :       2655 :     n = gdiv(n, gel(d,2));
     241 [ +  + ][ +  + ]:       2655 :     if (typ(n) != t_POL || varn(n) != varn(d)) n = scalarpol(n, varn(d));
     242                 :       2655 :     return n;
     243                 :            :   }
     244                 :            : 
     245                 :   39030015 :   cd = content(d);
     246 [ +  + ][ +  + ]:   39030015 :   cn = (typ(n) == t_POL && varn(n) == varn(d))? content(n): n;
     247         [ +  + ]:   39030015 :   if (!gequal1(cd)) {
     248                 :    4754702 :     d = RgX_Rg_div(d,cd);
     249         [ +  + ]:    4754702 :     if (!gequal1(cn))
     250                 :            :     {
     251         [ -  + ]:     956345 :       if (gequal0(cn)) {
     252         [ #  # ]:          0 :         if (isexactzero(cn)) return scalarpol(cn, varn(d));
     253         [ #  # ]:          0 :         n = (cn != n)? RgX_Rg_div(n,cd): gdiv(n, cd);
     254                 :          0 :         c = gen_1;
     255                 :            :       } else {
     256         [ +  + ]:     956345 :         n = (cn != n)? RgX_Rg_div(n,cn): gen_1;
     257                 :     956345 :         c = gdiv(cn,cd);
     258                 :            :       }
     259                 :            :     }
     260                 :            :     else
     261                 :    3798357 :       c = ginv(cd);
     262                 :            :   } else {
     263         [ +  + ]:   34275313 :     if (!gequal1(cn))
     264                 :            :     {
     265         [ +  + ]:    1873006 :       if (gequal0(cn)) {
     266         [ +  + ]:         55 :         if (isexactzero(cn)) return scalarpol(cn, varn(d));
     267                 :          5 :         c = gen_1;
     268                 :            :       } else {
     269         [ +  + ]:    1872951 :         n = (cn != n)? RgX_Rg_div(n,cn): gen_1;
     270                 :    1872951 :         c = cn;
     271                 :            :       }
     272                 :            :     } else {
     273                 :   32402307 :       GEN y = cgetg(3,t_RFRAC);
     274                 :   32402307 :       gel(y,1) = gcopy(n);
     275                 :   32402307 :       gel(y,2) = RgX_copy(d); return y;
     276                 :            :     }
     277                 :            :   }
     278                 :            : 
     279         [ +  + ]:    6627658 :   if (typ(c) == t_POL)
     280                 :            :   {
     281                 :     658923 :     z = c;
     282         [ +  + ]:     689498 :     do { z = content(z); } while (typ(z) == t_POL);
     283                 :     658923 :     cd = denom(z);
     284                 :     658923 :     cn = gmul(c, cd);
     285                 :            :   }
     286                 :            :   else
     287                 :            :   {
     288                 :    5968735 :     cn = numer(c);
     289                 :    5968735 :     cd = denom(c);
     290                 :            :   }
     291                 :    6627658 :   z = cgetg(3,t_RFRAC);
     292                 :    6627658 :   gel(z,1) = gmul(n, cn);
     293                 :    6627658 :   gel(z,2) = rfrac_denom_mul_scal(d, cd);
     294                 :   39032670 :   return z;
     295                 :            : }
     296                 :            : 
     297                 :            : /* in rare cases x may be a t_POL, after 0/x for instance -> pol_0() */
     298                 :            : static GEN
     299                 :     116915 : fix_rfrac(GEN x, long d)
     300                 :            : {
     301                 :            :   GEN z, N, D;
     302 [ +  + ][ -  + ]:     116915 :   if (!d || typ(x) == t_POL) return x;
     303                 :     109895 :   z = cgetg(3, t_RFRAC);
     304                 :     109895 :   N = gel(x,1);
     305                 :     109895 :   D = gel(x,2);
     306         [ +  + ]:     109895 :   if (d > 0) {
     307         [ +  - ]:     109865 :     gel(z, 1) = (typ(N)==t_POL && varn(N)==varn(D))? RgX_shift(N,d)
     308         [ +  - ]:     219730 :                                                    : monomialcopy(N,d,varn(D));
     309                 :     109865 :     gel(z, 2) = RgX_copy(D);
     310                 :            :   } else {
     311                 :         30 :     gel(z, 1) = gcopy(N);
     312                 :         30 :     gel(z, 2) = RgX_shift(D, -d);
     313                 :            :   }
     314                 :     116915 :   return z;
     315                 :            : }
     316                 :            : 
     317                 :            : /* assume d != 0 */
     318                 :            : static GEN
     319                 :   31533799 : gred_rfrac2_i(GEN n, GEN d)
     320                 :            : {
     321                 :            :   GEN y, z;
     322                 :            :   long v, vd, vn;
     323                 :            : 
     324                 :   31533799 :   n = simplify_shallow(n);
     325         [ +  + ]:   31533799 :   if (isrationalzero(n)) return gcopy(n);
     326                 :   26603033 :   d = simplify_shallow(d);
     327         [ +  + ]:   26603033 :   if (typ(d) != t_POL) return gdiv(n,d);
     328                 :   25694499 :   vd = varn(d);
     329         [ +  + ]:   25694499 :   if (typ(n) != t_POL)
     330                 :            :   {
     331         [ +  + ]:   14286399 :     if (varncmp(vd, gvar(n)) >= 0) return gdiv(n,d);
     332         [ +  - ]:   14285394 :     if (varncmp(vd, gvar2(n)) < 0) return gred_rfrac_simple(n,d);
     333                 :          0 :     pari_err_BUG("gred_rfrac2_i [incompatible variables]");
     334                 :            :   }
     335                 :   11408100 :   vn = varn(n);
     336         [ +  + ]:   11408100 :   if (varncmp(vd, vn) < 0) return gred_rfrac_simple(n,d);
     337         [ +  + ]:   11303005 :   if (varncmp(vd, vn) > 0) return RgX_Rg_div(n,d);
     338                 :            : 
     339                 :            :   /* now n and d are t_POLs in the same variable */
     340                 :   11180793 :   v = RgX_valrem(n, &n) - RgX_valrem(d, &d);
     341         [ +  + ]:   11180793 :   if (!degpol(d))
     342                 :            :   {
     343                 :    9036572 :     n = RgX_Rg_div(n,gel(d,2));
     344         [ +  + ]:    9036572 :     return v? RgX_mulXn(n,v): n;
     345                 :            :   }
     346                 :            : 
     347                 :            :   /* X does not divide gcd(n,d), deg(d) > 0 */
     348 [ +  + ][ +  - ]:    2144221 :   if (!isinexact(n) && !isinexact(d))
     349                 :            :   {
     350                 :    2144216 :     y = RgX_divrem(n, d, &z);
     351 [ +  + ][ +  + ]:    2144216 :     if (!signe(z)) { cgiv(z); return v? RgX_mulXn(y, v): y; }
     352                 :     116910 :     z = RgX_gcd(d, z);
     353         [ +  + ]:     116910 :     if (degpol(z)) { n = RgX_div(n,z); d = RgX_div(d,z); }
     354                 :            :   }
     355                 :   31533799 :   return fix_rfrac(gred_rfrac_simple(n,d), v);
     356                 :            : }
     357                 :            : 
     358                 :            : GEN
     359                 :   13291019 : gred_rfrac2(GEN x1, GEN x2)
     360                 :            : {
     361                 :   13291019 :   pari_sp av = avma;
     362                 :   13291019 :   return gerepileupto(av, gred_rfrac2_i(x1, x2));
     363                 :            : }
     364                 :            : 
     365                 :            : /* x1,x2 t_INT, return x1/x2 in reduced form */
     366                 :            : GEN
     367                 :    8131076 : gred_frac2(GEN x1, GEN x2)
     368                 :            : {
     369                 :    8131076 :   GEN r, y = dvmdii(x1,x2,&r);
     370                 :            :   pari_sp av;
     371                 :            : 
     372         [ +  + ]:    8131056 :   if (r == gen_0) return y; /* gen_0 intended */
     373                 :    2195430 :   av = avma; r = gcdii(x2,r);
     374         [ +  + ]:    2195430 :   if (lgefint(r) == 3)
     375                 :            :   {
     376                 :    2069616 :     ulong rr = r[2];
     377                 :    2069616 :     avma = av;
     378         [ +  + ]:    2069616 :     if (rr == 1) y = mkfraccopy(x1, x2);
     379                 :            :     else
     380                 :            :     {
     381                 :    1033865 :       y = cgetg(3,t_FRAC);
     382                 :    1033865 :       gel(y,1) = diviuexact(x1, rr);
     383                 :    1033865 :       gel(y,2) = diviuexact(x2, rr);
     384                 :            :     }
     385                 :            :   }
     386                 :            :   else
     387                 :            :   { /* rare: r left on stack for efficiency */
     388                 :     125814 :     y = cgetg(3,t_FRAC);
     389                 :     125814 :     gel(y,1) = diviiexact(x1,r);
     390                 :     125814 :     gel(y,2) = diviiexact(x2,r);
     391                 :            :   }
     392                 :    8131056 :   normalize_frac(y); return y;
     393                 :            : }
     394                 :            : 
     395                 :            : /*******************************************************************/
     396                 :            : /*                                                                 */
     397                 :            : /*                          CONJUGATION                            */
     398                 :            : /*                                                                 */
     399                 :            : /*******************************************************************/
     400                 :            : /* lift( conj(Mod(x, y)) ), assuming degpol(y) = 2, degpol(x) < 2 */
     401                 :            : static GEN
     402                 :       2195 : quad_polmod_conj(GEN x, GEN y)
     403                 :            : {
     404                 :            :   GEN z, u, v, a, b;
     405                 :            :   pari_sp av;
     406         [ -  + ]:       2195 :   if (typ(x) != t_POL) return gcopy(x);
     407 [ +  - ][ -  + ]:       2195 :   if (varn(x) != varn(y) || degpol(x) <= 0) return RgX_copy(x);
     408                 :       2195 :   a = gel(y,4); u = gel(x,3); /*Mod(ux + v, ax^2 + bx + c)*/
     409                 :       2195 :   b = gel(y,3); v = gel(x,2);
     410                 :       2195 :   z = cgetg(4, t_POL); z[1] = x[1]; av = avma;
     411                 :       2195 :   gel(z,2) = gerepileupto(av, gsub(v, gdiv(gmul(u,b), a)));
     412                 :       2195 :   gel(z,3) = gneg(u); return z;
     413                 :            : }
     414                 :            : static GEN
     415                 :       2195 : quad_polmod_norm(GEN x, GEN y)
     416                 :            : {
     417                 :            :   GEN z, u, v, a, b, c;
     418                 :            :   pari_sp av;
     419 [ +  - ][ +  - ]:       2195 :   if (typ(x) != t_POL || varn(x) != varn(y) || degpol(x) <= 0)
                 [ -  + ]
     420                 :          0 :     return gsqr(x);
     421                 :       2195 :   a = gel(y,4); u = gel(x,3); /*Mod(ux + v, ax^2 + bx + c)*/
     422                 :       2195 :   b = gel(y,3); v = gel(x,2);
     423                 :       2195 :   c = gel(y,2); av = avma;
     424                 :       2195 :   z = gmul(u, gsub(gmul(c,u), gmul(b,v)));
     425         [ +  + ]:       2195 :   if (!gequal1(a)) z = gdiv(z, a);
     426                 :       2195 :   return gerepileupto(av, gadd(z, gsqr(v)));
     427                 :            : }
     428                 :            : 
     429                 :            : GEN
     430                 :     359704 : gconj(GEN x)
     431                 :            : {
     432                 :            :   long lx, i;
     433                 :            :   GEN y;
     434                 :            : 
     435   [ +  +  +  +  :     359704 :   switch(typ(x))
             +  +  -  - ]
     436                 :            :   {
     437                 :            :     case t_INT: case t_REAL:
     438                 :      42616 :       return mpcopy(x);
     439                 :            : 
     440                 :            :     case t_INTMOD: case t_FRAC: case t_PADIC:
     441                 :        965 :       return gcopy(x);
     442                 :            : 
     443                 :            :     case t_COMPLEX:
     444                 :     312808 :       y = cgetg(3,t_COMPLEX);
     445                 :     312808 :       gel(y,1) = gcopy(gel(x,1));
     446                 :     312808 :       gel(y,2) = gneg(gel(x,2));
     447                 :     312808 :       break;
     448                 :            : 
     449                 :            :     case t_QUAD:
     450                 :        740 :       y = cgetg(4,t_QUAD);
     451                 :        740 :       gel(y,1) = ZX_copy(gel(x,1));
     452                 :        740 :       gel(y,2) = gequal0(gmael(x,1,3))? gcopy(gel(x,2))
     453         [ +  + ]:        740 :                                     : gadd(gel(x,2), gel(x,3));
     454                 :        740 :       gel(y,3) = gneg(gel(x,3));
     455                 :        740 :       break;
     456                 :            : 
     457                 :            :     case t_POL: case t_SER:
     458                 :         15 :       y = cgetg_copy(x, &lx); y[1] = x[1];
     459         [ +  + ]:         45 :       for (i=2; i<lx; i++) gel(y,i) = gconj(gel(x,i));
     460                 :         15 :       break;
     461                 :            : 
     462                 :            :     case t_RFRAC: case t_VEC: case t_COL: case t_MAT:
     463                 :       2560 :       y = cgetg_copy(x, &lx);
     464         [ +  + ]:      17145 :       for (i=1; i<lx; i++) gel(y,i) = gconj(gel(x,i));
     465                 :       2560 :       break;
     466                 :            : 
     467                 :            :     case t_POLMOD:
     468                 :            :     {
     469                 :          0 :       GEN y, X = gel(x,1);
     470                 :          0 :       long d = degpol(X);
     471         [ #  # ]:          0 :       if (d < 2) return RgX_copy(x);
     472         [ #  # ]:          0 :       if (d == 2) {
     473                 :          0 :         y = cgetg(3, t_POLMOD);
     474                 :          0 :         gel(y,1) = RgX_copy(X);
     475                 :          0 :         gel(y,2) = quad_polmod_conj(gel(x,2), X); return y;
     476                 :            :       }
     477                 :            :     }
     478                 :            :     default:
     479                 :          0 :       pari_err_TYPE("gconj",x);
     480                 :          0 :       return NULL; /* not reached */
     481                 :            :   }
     482                 :     359704 :   return y;
     483                 :            : }
     484                 :            : 
     485                 :            : GEN
     486                 :         35 : conjvec(GEN x,long prec)
     487                 :            : {
     488                 :            :   long lx, s, i;
     489                 :            :   GEN z;
     490                 :            : 
     491   [ -  -  +  -  :         35 :   switch(typ(x))
                   +  - ]
     492                 :            :   {
     493                 :            :     case t_INT: case t_INTMOD: case t_FRAC:
     494                 :          0 :       return mkcolcopy(x);
     495                 :            : 
     496                 :            :     case t_COMPLEX: case t_QUAD:
     497                 :          0 :       z=cgetg(3,t_COL); gel(z,1) = gcopy(x); gel(z,2) = gconj(x); break;
     498                 :            : 
     499                 :            :     case t_FFELT:
     500                 :         20 :       return FF_conjvec(x);
     501                 :            : 
     502                 :            :     case t_VEC: case t_COL:
     503                 :          0 :       lx = lg(x); z = cgetg(lx,t_MAT);
     504         [ #  # ]:          0 :       if (lx == 1) return z;
     505                 :          0 :       gel(z,1) = conjvec(gel(x,1),prec);
     506                 :          0 :       s = lgcols(z);
     507         [ #  # ]:          0 :       for (i=2; i<lx; i++)
     508                 :            :       {
     509                 :          0 :         gel(z,i) = conjvec(gel(x,i),prec);
     510         [ #  # ]:          0 :         if (lg(gel(z,i)) != s) pari_err_OP("conjvec", gel(z,1), gel(z,i));
     511                 :            :       }
     512                 :          0 :       break;
     513                 :            : 
     514                 :            :     case t_POLMOD: {
     515                 :         15 :       GEN T = gel(x,1), r;
     516                 :            :       pari_sp av;
     517                 :            : 
     518                 :         15 :       lx = lg(T);
     519         [ -  + ]:         15 :       if (lx <= 3) return cgetg(1,t_COL);
     520                 :         15 :       x = gel(x,2);
     521         [ +  + ]:         55 :       for (i=2; i<lx; i++)
     522                 :            :       {
     523                 :         45 :         GEN c = gel(T,i);
     524      [ +  +  - ]:         45 :         switch(typ(c)) {
     525                 :            :           case t_INTMOD: {
     526                 :          5 :             GEN p = gel(c,1);
     527                 :            :             pari_sp av;
     528 [ -  + ][ #  # ]:          5 :             if (typ(x) != t_POL) retconst_col(lx-3, Rg_to_Fp(x, p));
     529                 :          5 :             av = avma;
     530                 :          5 :             T = RgX_to_FpX(T,p);
     531                 :          5 :             x = RgX_to_FpX(x, p);
     532         [ -  + ]:          5 :             if (varn(x) != varn(T)) pari_err_VAR("conjvec",x,T);
     533                 :          5 :             z = FpXQC_to_mod(FpXQ_conjvec(x, T , p), T, p);
     534                 :          5 :             return gerepileupto(av, z);
     535                 :            :           }
     536                 :            :           case t_INT:
     537                 :         40 :           case t_FRAC: break;
     538                 :          0 :           default: pari_err_TYPE("conjvec [not a rational t_POL]",T);
     539                 :            :         }
     540                 :            :       }
     541         [ -  + ]:         10 :       if (typ(x) != t_POL)
     542                 :            :       {
     543         [ #  # ]:          0 :         if (!is_rational_t(typ(x)))
     544                 :          0 :           pari_err_TYPE("conjvec [not a rational t_POL]",x);
     545         [ #  # ]:          0 :         retconst_col(lx-3, gcopy(x));
     546                 :            :       }
     547         [ -  + ]:         10 :       if (!RgX_is_QX(x)) pari_err_TYPE("conjvec", x);
     548                 :         10 :       av = avma;
     549         [ -  + ]:         10 :       if (varn(x) != varn(T)) pari_err_VAR("conjvec",x,T);
     550                 :         10 :       r = cleanroots(T,prec);
     551                 :         10 :       z = cgetg(lx-2,t_COL);
     552         [ +  + ]:         40 :       for (i=1; i<=lx-3; i++) gel(z,i) = poleval(x, gel(r,i));
     553                 :         10 :       return gerepileupto(av, z);
     554                 :            :     }
     555                 :            : 
     556                 :            :     default:
     557                 :          0 :       pari_err_TYPE("conjvec",x);
     558                 :          0 :       return NULL; /* not reached */
     559                 :            :   }
     560                 :         35 :   return z;
     561                 :            : }
     562                 :            : 
     563                 :            : 
     564                 :            : /********************************************************************/
     565                 :            : /**                                                                **/
     566                 :            : /**                           ADDITION                             **/
     567                 :            : /**                                                                **/
     568                 :            : /********************************************************************/
     569                 :            : /* x, y compatible PADIC, op = add or sub */
     570                 :            : static GEN
     571                 :     148555 : addsub_pp(GEN x, GEN y, GEN (*op)(GEN,GEN))
     572                 :            : {
     573                 :     148555 :   pari_sp av = avma;
     574                 :            :   long d,e,r,rx,ry;
     575                 :     148555 :   GEN u, z, mod, p = gel(x,2);
     576                 :            :   int swap;
     577                 :            : 
     578                 :     148555 :   (void)new_chunk(5 + lgefint(gel(x,3)) + lgefint(gel(y,3)));
     579                 :     148555 :   e = valp(x);
     580                 :     148555 :   r = valp(y); d = r-e;
     581         [ +  + ]:     148555 :   if (d < 0) { swap = 1; swap(x,y); e = r; d = -d; } else swap = 0;
     582                 :     148555 :   rx = precp(x);
     583                 :     148555 :   ry = precp(y);
     584         [ +  + ]:     148555 :   if (d) /* v(x) < v(y) */
     585                 :            :   {
     586                 :      50435 :     r = d+ry; z = powiu(p,d);
     587         [ +  + ]:      50435 :     if (r < rx) mod = mulii(z,gel(y,3)); else { r = rx; mod = gel(x,3); }
     588                 :      50435 :     z = mulii(z,gel(y,4));
     589         [ +  + ]:      50435 :     u = swap? op(z, gel(x,4)): op(gel(x,4), z);
     590                 :            :   }
     591                 :            :   else
     592                 :            :   {
     593                 :            :     long c;
     594         [ +  + ]:      98120 :     if (ry < rx) { r=ry; mod = gel(y,3); } else { r=rx; mod = gel(x,3); }
     595         [ -  + ]:      98120 :     u = swap? op(gel(y,4), gel(x,4)): op(gel(x,4), gel(y,4));
     596 [ +  + ][ +  + ]:      98120 :     if (!signe(u) || (c = Z_pvalrem(u,p,&u)) >= r)
     597                 :            :     {
     598                 :       2035 :       avma = av; return zeropadic(p, e+r);
     599                 :            :     }
     600         [ +  + ]:      96085 :     if (c)
     601                 :            :     {
     602                 :      11055 :       mod = diviiexact(mod, powiu(p,c));
     603                 :      11055 :       r -= c;
     604                 :      11055 :       e += c;
     605                 :            :     }
     606                 :            :   }
     607                 :     146520 :   u = modii(u, mod);
     608                 :     146520 :   avma = av; z = cgetg(5,t_PADIC);
     609                 :     146520 :   z[1] = evalprecp(r) | evalvalp(e);
     610                 :     146520 :   gel(z,2) = icopy(p);
     611                 :     146520 :   gel(z,3) = icopy(mod);
     612                 :     148555 :   gel(z,4) = icopy(u); return z;
     613                 :            : }
     614                 :            : 
     615                 :            : /* return x + y, where y t_PADIC and x is a non-zero t_INT or t_FRAC */
     616                 :            : static GEN
     617                 :      49190 : addQp(GEN x, GEN y)
     618                 :            : {
     619                 :      49190 :   pari_sp av = avma;
     620                 :      49190 :   long tx,d,r,e, vy = valp(y), py = precp(y);
     621                 :      49190 :   GEN z,q,p1,p2,mod,u, p = gel(y,2);
     622                 :            : 
     623                 :      49190 :   tx = typ(x);
     624                 :      49190 :   e = (tx == t_INT)? Z_pvalrem(x,p,&p1)
     625         [ +  + ]:      50285 :                    : Z_pvalrem(gel(x,1),p,&p1) -
     626                 :       1095 :                      Z_pvalrem(gel(x,2),p,&p2);
     627                 :      49190 :   d = vy - e; r = d + py;
     628         [ +  + ]:      49190 :   if (r <= 0) { avma = av; return gcopy(y); }
     629                 :      49060 :   mod = gel(y,3);
     630                 :      49060 :   u   = gel(y,4);
     631                 :      49060 :   (void)new_chunk(5 + ((lgefint(mod) + lgefint(p)*labs(d)) << 1));
     632                 :            : 
     633         [ +  + ]:      49060 :   if (d > 0)
     634                 :            :   {
     635                 :      44230 :     q = powiu(p,d);
     636                 :      44230 :     mod = mulii(mod, q);
     637                 :      44230 :     u   = mulii(u, q);
     638 [ +  + ][ +  + ]:      44230 :     if (tx != t_INT && !is_pm1(p2)) p1 = mulii(p1, Fp_inv(p2,mod));
     639                 :      44230 :     u = addii(u, p1);
     640                 :            :   }
     641         [ +  + ]:       4830 :   else if (d < 0)
     642                 :            :   {
     643                 :        375 :     q = powiu(p,-d);
     644 [ +  + ][ +  + ]:        375 :     if (tx != t_INT && !is_pm1(p2)) p1 = mulii(p1, Fp_inv(p2,mod));
     645                 :        375 :     p1 = mulii(p1, q);
     646                 :        375 :     u = addii(u, p1);
     647                 :        375 :     r = py; e = vy;
     648                 :            :   }
     649                 :            :   else
     650                 :            :   {
     651                 :            :     long c;
     652 [ +  + ][ +  + ]:       4455 :     if (tx != t_INT && !is_pm1(p2)) p1 = mulii(p1, Fp_inv(p2,mod));
     653                 :       4455 :     u = addii(u, p1);
     654 [ +  + ][ +  + ]:       4455 :     if (!signe(u) || (c = Z_pvalrem(u,p,&u)) >= r)
     655                 :            :     {
     656                 :        285 :       avma = av; return zeropadic(p,e+r);
     657                 :            :     }
     658         [ +  + ]:       4170 :     if (c)
     659                 :            :     {
     660                 :       2380 :       mod = diviiexact(mod, powiu(p,c));
     661                 :       2380 :       r -= c;
     662                 :       2380 :       e += c;
     663                 :            :     }
     664                 :            :   }
     665                 :      48775 :   u = modii(u, mod);
     666                 :      48775 :   avma = av; z = cgetg(5,t_PADIC);
     667                 :      48775 :   z[1] = evalprecp(r) | evalvalp(e);
     668                 :      48775 :   gel(z,2) = icopy(p);
     669                 :      48775 :   gel(z,3) = icopy(mod);
     670                 :      49190 :   gel(z,4) = icopy(u); return z;
     671                 :            : }
     672                 :            : 
     673                 :            : /* Mod(x,X) + Mod(y,X) */
     674                 :            : #define addsub_polmod_same addsub_polmod_scal
     675                 :            : /* Mod(x,X) +/- Mod(y,Y) */
     676                 :            : static GEN
     677                 :          0 : addsub_polmod(GEN X, GEN Y, GEN x, GEN y, GEN(*op)(GEN,GEN))
     678                 :            : {
     679                 :          0 :   long T[3] = { evaltyp(t_POLMOD) | _evallg(3),0,0 };
     680                 :          0 :   GEN z = cgetg(3,t_POLMOD);
     681                 :          0 :   long vx = varn(X), vy = varn(Y);
     682         [ #  # ]:          0 :   if (vx==vy) {
     683                 :            :     pari_sp av;
     684                 :          0 :     gel(z,1) = RgX_gcd(X,Y); av = avma;
     685                 :          0 :     gel(z,2) = gerepileupto(av, gmod(op(x, y), gel(z,1))); return z;
     686                 :            :   }
     687         [ #  # ]:          0 :   if (varncmp(vx, vy) < 0)
     688                 :          0 :   { gel(z,1) = RgX_copy(X); gel(T,1) = Y; gel(T,2) = y; y = T; }
     689                 :            :   else
     690                 :          0 :   { gel(z,1) = RgX_copy(Y); gel(T,1) = X; gel(T,2) = x; x = T; }
     691                 :          0 :   gel(z,2) = op(x, y); return z;
     692                 :            : }
     693                 :            : /* Mod(y, Y) +/- x,  x scalar or polynomial in same var and reduced degree */
     694                 :            : static GEN
     695                 :     310243 : addsub_polmod_scal(GEN Y, GEN y, GEN x, GEN(*op)(GEN,GEN))
     696                 :            : {
     697                 :     310243 :   GEN z = cgetg(3,t_POLMOD);
     698                 :     310243 :   gel(z,1) = RgX_copy(Y);
     699                 :     310243 :   gel(z,2) = op(y, x); return z;
     700                 :            : }
     701                 :            : 
     702                 :            : /* typ(y) == t_SER, x "scalar" [e.g object in lower variable] */
     703                 :            : static GEN
     704                 :       5010 : add_ser_scal(GEN y, GEN x)
     705                 :            : {
     706                 :            :   long i, l, ly, vy;
     707                 :            :   GEN z;
     708                 :            : 
     709         [ +  + ]:       5010 :   if (isrationalzero(x)) return gcopy(y);
     710                 :       3925 :   ly = lg(y);
     711                 :       3925 :   l = valp(y);
     712         [ +  + ]:       3925 :   if (l < 3-ly) return gcopy(y);
     713                 :            :   /* l + ly >= 3 */
     714         [ +  + ]:       3920 :   if (l < 0)
     715                 :            :   {
     716                 :       1250 :     z = cgetg(ly,t_SER); z[1] = y[1];
     717         [ +  + ]:       5215 :     for (i = 2; i <= 1-l; i++) gel(z,i) = gcopy(gel(y,i));
     718                 :       1250 :     gel(z,i) = gadd(x,gel(y,i)); i++;
     719         [ +  + ]:      14295 :     for (     ; i < ly; i++)   gel(z,i) = gcopy(gel(y,i));
     720                 :       1250 :     return z;
     721                 :            :   }
     722                 :       2670 :   vy = varn(y);
     723         [ +  + ]:       2670 :   if (l > 0)
     724                 :            :   {
     725         [ +  + ]:       2375 :     if (ser_isexactzero(y))
     726         [ +  + ]:       1020 :       return scalarser(ly == 2? x: gadd(x,gel(y,2)), vy, l);
     727                 :       1355 :     y -= l; ly += l;
     728                 :       1355 :     z = cgetg(ly,t_SER);
     729                 :       1355 :     x = gcopy(x);
     730         [ +  + ]:       2490 :     for (i=3; i<=l+1; i++) gel(z,i) = gen_0;
     731                 :            :   }
     732                 :            :   else
     733                 :            :   { /* l = 0, ly >= 3. Also OK if ser_isexactzero(y) */
     734                 :        295 :     z = cgetg(ly,t_SER);
     735                 :        295 :     x = gadd(x, gel(y,2));
     736                 :        295 :     i = 3;
     737                 :            :   }
     738         [ +  + ]:      10060 :   for (; i<ly; i++) gel(z,i) = gcopy(gel(y,i));
     739                 :       1650 :   gel(z,2) = x;
     740                 :       1650 :   z[1] = evalsigne(1) | _evalvalp(0) | evalvarn(vy);
     741         [ +  + ]:       5010 :   return gequal0(x)? normalize(z): z;
     742                 :            : }
     743                 :            : static long
     744         [ +  + ]:      68264 : serprec(GEN x) { return ser_isexactzero(x)? 2: lg(x); }
     745                 :            : /* x,y t_SER in the same variable: x+y */
     746                 :            : static GEN
     747                 :      35427 : ser_add(GEN x, GEN y)
     748                 :            : {
     749                 :      35427 :   long i, lx,ly, n = valp(y) - valp(x);
     750                 :            :   GEN z;
     751         [ +  + ]:      35427 :   if (n < 0) { n = -n; swap(x,y); }
     752                 :            :   /* valp(x) <= valp(y) */
     753                 :      35427 :   lx = serprec(x);
     754         [ +  + ]:      35427 :   if (lx == 2) /* don't lose type information */
     755                 :       2590 :     return scalarser(gadd(RgX_get_0(x), RgX_get_0(y)), varn(x), valp(x));
     756         [ +  + ]:      32837 :   ly = serprec(y) + n; if (lx < ly) ly = lx;
     757         [ +  + ]:      32837 :   if (n)
     758                 :            :   {
     759         [ +  + ]:       9970 :     if (n+2 > lx) return gcopy(x);
     760                 :       9380 :     z = cgetg(ly,t_SER);
     761         [ +  + ]:     483350 :     for (i=2; i<=n+1; i++) gel(z,i) = gcopy(gel(x,i));
     762         [ +  + ]:     350625 :     for (   ; i < ly; i++) gel(z,i) = gadd(gel(x,i),gel(y,i-n));
     763                 :            :   } else {
     764                 :      22867 :     z = cgetg(ly,t_SER);
     765         [ +  + ]:     130904 :     for (i=2; i < ly; i++) gel(z,i) = gadd(gel(x,i),gel(y,i));
     766                 :            :   }
     767                 :      35427 :   z[1] = x[1]; return normalize(z);
     768                 :            : }
     769                 :            : /* typ(y) == RFRAC, x polynomial in same variable or "scalar" */
     770                 :            : static GEN
     771                 :    6132999 : add_rfrac_scal(GEN y, GEN x)
     772                 :            : {
     773                 :            :   pari_sp av;
     774                 :            :   GEN n;
     775                 :            : 
     776         [ +  + ]:    6132999 :   if (isintzero(x)) return gcopy(y); /* frequent special case */
     777                 :    3348365 :   av = avma; n = gadd(gmul(x, gel(y,2)), gel(y,1));
     778                 :    6132999 :   return gerepileupto(av, gred_rfrac_simple(n, gel(y,2)));
     779                 :            : }
     780                 :            : 
     781                 :            : /* x "scalar", ty != t_MAT and non-scalar */
     782                 :            : static GEN
     783                 :    9596708 : add_scal(GEN y, GEN x, long ty)
     784                 :            : {
     785   [ +  +  +  -  :    9596708 :   switch(ty)
                   +  - ]
     786                 :            :   {
     787                 :    6263912 :     case t_POL: return RgX_Rg_add(y, x);
     788                 :       5010 :     case t_SER: return add_ser_scal(y, x);
     789                 :    3177781 :     case t_RFRAC: return add_rfrac_scal(y, x);
     790                 :          0 :     case t_COL: return RgC_Rg_add(y, x);
     791                 :            :     case t_VEC:
     792         [ +  - ]:     150005 :       if (isintzero(x)) return gcopy(y);
     793                 :          0 :       break;
     794                 :            :   }
     795                 :          0 :   pari_err_TYPE2("+",x,y);
     796                 :    9596708 :   return NULL; /* not reached */
     797                 :            : }
     798                 :            : 
     799                 :            : static GEN
     800                 :    5017174 : addsub_frac(GEN x, GEN y, GEN (*op)(GEN,GEN))
     801                 :            : {
     802                 :    5017174 :   pari_sp av = avma;
     803                 :    5017174 :   GEN x1 = gel(x,1), x2 = gel(x,2), z = cgetg(3,t_FRAC);
     804                 :    5017174 :   GEN y1 = gel(y,1), y2 = gel(y,2), q, r, n, d, delta;
     805                 :    5017174 :   int s = cmpii(x2, y2);
     806                 :            : 
     807         [ +  + ]:    5017174 :   if (!s)
     808                 :            :   { /* common denominator: (x1 op y1) / x2 */
     809                 :    1714134 :     n = op(x1, y1);
     810         [ +  + ]:    1714134 :     if (!signe(n)) { avma = av; return gen_0; }
     811                 :    1586415 :     d = x2;
     812                 :    1586415 :     q = dvmdii(n, d, &r);
     813         [ +  + ]:    1586415 :     if (r == gen_0) { avma = av; return icopy(q); }
     814                 :    1411536 :     r = gcdii(d, r);
     815         [ +  + ]:    1411536 :     if (!is_pm1(r)) { n = diviiexact(n, r); d = diviiexact(d, r); }
     816                 :    1411536 :     gel(z,1) = icopy_avma(n, (pari_sp)z);
     817                 :    1411536 :     gel(z,2) = icopy_avma(d, (pari_sp)gel(z,1));
     818                 :    1411536 :     avma = (pari_sp)gel(z,2); return z;
     819                 :            :   }
     820         [ +  + ]:    3303040 :   if (s < 0)
     821                 :            :   {
     822                 :    1579581 :     GEN Q = dvmdii(y2, x2, &r);
     823         [ +  + ]:    1579581 :     if (r == gen_0)
     824                 :            :     { /* y2 = Q x2: 1/x2 . (Q x1 op y1)/Q, where latter is in coprime form */
     825                 :    1182848 :       pari_sp av = avma;
     826                 :    1182848 :       n = op(mulii(Q,x1), y1);
     827                 :    1182848 :       q = dvmdii(n, x2, &r);
     828         [ +  + ]:    1182848 :       if (r == gen_0)
     829                 :            :       {
     830                 :     285568 :         gel(z,1) = gerepileuptoint(av, q);
     831                 :     285568 :         gel(z,2) = Q; return z;
     832                 :            :       }
     833                 :     897280 :       r = gcdii(x2, r);
     834         [ +  + ]:     897280 :       if (!is_pm1(r)) { n = diviiexact(n, r); x2 = diviiexact(x2, r); }
     835                 :     897280 :       d = mulii(x2,Q);
     836                 :     897280 :       gel(z,1) = icopy_avma(n, (pari_sp)z);
     837                 :     897280 :       gel(z,2) = icopy_avma(d, (pari_sp)gel(z,1));
     838                 :     897280 :       avma = (pari_sp)gel(z,2); return z;
     839                 :            :     }
     840                 :     396733 :     delta = gcdii(x2,r);
     841                 :            :   }
     842                 :            :   else
     843                 :            :   {
     844                 :    1723459 :     GEN Q = dvmdii(x2, y2, &r);
     845         [ +  + ]:    1723459 :     if (r == gen_0)
     846                 :            :     { /* x2 = Q y2: 1/y2 . (x1 op Q y1)/Q, where latter is in coprime form */
     847                 :    1399214 :       pari_sp av = avma;
     848                 :    1399214 :       n = op(x1, mulii(Q,y1));
     849                 :    1399214 :       q = dvmdii(n, y2, &r);
     850         [ +  + ]:    1399214 :       if (r == gen_0)
     851                 :            :       {
     852                 :      40018 :         gel(z,1) = gerepileuptoint(av, q);
     853                 :      40018 :         gel(z,2) = Q; return z;
     854                 :            :       }
     855                 :    1359196 :       r = gcdii(y2, r);
     856         [ +  + ]:    1359196 :       if (!is_pm1(r)) { n = diviiexact(n, r); y2 = diviiexact(y2, r); }
     857                 :    1359196 :       d = mulii(y2,Q);
     858                 :    1359196 :       gel(z,1) = icopy_avma(n, (pari_sp)z);
     859                 :    1359196 :       gel(z,2) = icopy_avma(d, (pari_sp)gel(z,1));
     860                 :    1359196 :       avma = (pari_sp)gel(z,2); return z;
     861                 :            :     }
     862                 :     324245 :     delta = gcdii(y2,r);
     863                 :            :   }
     864                 :            :   /* delta = gcd(x2,y2) */
     865         [ +  + ]:     720978 :   if (is_pm1(delta))
     866                 :            :   { /* numerator is non-zero */
     867                 :      57488 :     gel(z,1) = gerepileuptoint((pari_sp)z, op(mulii(x1,y2), mulii(y1,x2)));
     868                 :      57488 :     gel(z,2) = mulii(x2,y2); return z;
     869                 :            :   }
     870                 :     663490 :   x2 = diviiexact(x2,delta);
     871                 :     663490 :   y2 = diviiexact(y2,delta);
     872                 :     663490 :   n = op(mulii(x1,y2), mulii(y1,x2));
     873         [ -  + ]:     663490 :   if (!signe(n)) { avma = av; return gen_0; }
     874                 :     663490 :   d = mulii(x2, y2);
     875                 :     663490 :   q = dvmdii(n, delta, &r);
     876         [ +  + ]:     663490 :   if (r == gen_0)
     877                 :            :   {
     878         [ -  + ]:      49160 :     if (is_pm1(d)) { avma = av; return icopy(q); }
     879                 :      49160 :     avma = (pari_sp)z;
     880                 :      49160 :     gel(z,2) = icopy(d);
     881                 :      49160 :     gel(z,1) = icopy(q); return z;
     882                 :            :   }
     883                 :     614330 :   r = gcdii(delta, r);
     884         [ +  + ]:     614330 :   if (!is_pm1(r))
     885                 :            :   {
     886                 :     186382 :     n     = diviiexact(n, r);
     887                 :     186382 :     delta = diviiexact(delta, r);
     888                 :            :   }
     889                 :     614330 :   d = mulii(d,delta); avma = (pari_sp)z;
     890                 :     614330 :   gel(z,1) = icopy(n);
     891                 :    5017174 :   gel(z,2) = icopy(d); return z;
     892                 :            : }
     893                 :            : 
     894                 :            : /* assume x2, y2 are t_POLs in the same variable */
     895                 :            : static GEN
     896                 :    2063248 : add_rfrac(GEN x, GEN y)
     897                 :            : {
     898                 :    2063248 :   pari_sp av = avma;
     899                 :    2063248 :   GEN x1 = gel(x,1), x2 = gel(x,2);
     900                 :    2063248 :   GEN y1 = gel(y,1), y2 = gel(y,2), q, r, n, d, delta;
     901                 :            : 
     902                 :    2063248 :   delta = RgX_gcd(x2,y2);
     903         [ +  + ]:    2063248 :   if (!degpol(delta))
     904                 :            :   {
     905                 :        445 :     n = simplify_shallow( gadd(gmul(x1,y2), gmul(y1,x2)) );
     906                 :        445 :     d = RgX_mul(x2, y2);
     907                 :        445 :     return gerepileupto(av, gred_rfrac_simple(n, d));
     908                 :            :   }
     909                 :    2062803 :   x2 = RgX_div(x2,delta);
     910                 :    2062803 :   y2 = RgX_div(y2,delta);
     911                 :    2062803 :   n = gadd(gmul(x1,y2), gmul(y1,x2));
     912         [ +  + ]:    2062803 :   if (!signe(n))
     913                 :            :   {
     914                 :     508843 :     n = simplify_shallow(n);
     915         [ +  + ]:     508843 :     if (isrationalzero(n)) return gerepileupto(av, n);
     916                 :          5 :     return gerepilecopy(av, mkrfrac(n, RgX_mul(gel(x,2),y2)));
     917                 :            :   }
     918         [ +  + ]:    1553960 :   if (degpol(n) == 0)
     919                 :     835609 :     return gerepileupto(av, gred_rfrac_simple(gel(n,2), RgX_mul(gel(x,2),y2)));
     920                 :     718351 :   q = RgX_divrem(n, delta, &r); /* we want gcd(n,delta) */
     921         [ +  + ]:     718351 :   if (isexactzero(r))
     922                 :            :   {
     923                 :            :     GEN z;
     924                 :     158686 :     d = RgX_mul(x2, y2);
     925                 :            :     /* "constant" denominator ? */
     926         [ +  + ]:     158686 :     z = lg(d) == 3? RgX_Rg_div(q, gel(d,2)): gred_rfrac_simple(q, d);
     927                 :     158686 :     return gerepileupto(av, z);
     928                 :            :   }
     929                 :     559665 :   r = RgX_gcd(delta, r);
     930         [ +  + ]:     559665 :   if (degpol(r))
     931                 :            :   {
     932                 :     113828 :     n = RgX_div(n, r);
     933                 :     113828 :     d = RgX_mul(RgX_mul(x2,y2), RgX_div(delta, r));
     934                 :            :   }
     935                 :            :   else
     936                 :     445837 :     d = RgX_mul(gel(x,2), y2);
     937                 :    2063248 :   return gerepileupto(av, gred_rfrac_simple(n, d));
     938                 :            : }
     939                 :            : 
     940                 :            : GEN
     941                 :  482287927 : gadd(GEN x, GEN y)
     942                 :            : {
     943                 :  482287927 :   long tx = typ(x), ty = typ(y), vx, vy, lx, i, l;
     944                 :            :   pari_sp av, tetpil;
     945                 :            :   GEN z, p1;
     946                 :            : 
     947 [ +  + ][ +  +  :  482287927 :   if (tx == ty) switch(tx) /* shortcut to generic case */
          +  +  +  +  +  
          +  +  +  +  +  
             +  +  +  - ]
     948                 :            :   {
     949                 :  240216075 :     case t_INT: return addii(x,y);
     950                 :  137650759 :     case t_REAL: return addrr(x,y);
     951                 :     626183 :     case t_INTMOD:  { GEN X = gel(x,1), Y = gel(y,1);
     952                 :     626183 :       z = cgetg(3,t_INTMOD);
     953 [ +  + ][ +  + ]:     626183 :       if (X==Y || equalii(X,Y))
     954                 :     626178 :         return add_intmod_same(z, X, gel(x,2), gel(y,2));
     955                 :          5 :       gel(z,1) = gcdii(X,Y);
     956                 :          5 :       av = avma; p1 = addii(gel(x,2),gel(y,2));
     957                 :          5 :       gel(z,2) = gerepileuptoint(av, remii(p1, gel(z,1))); return z;
     958                 :            :     }
     959                 :    3574076 :     case t_FRAC: return addsub_frac(x,y,addii);
     960                 :   15986621 :     case t_COMPLEX: z = cgetg(3,t_COMPLEX);
     961                 :   15986621 :       gel(z,2) = gadd(gel(x,2),gel(y,2));
     962         [ +  + ]:   15986621 :       if (isintzero(gel(z,2)))
     963                 :            :       {
     964                 :        155 :         avma = (pari_sp)(z+3);
     965                 :        155 :         return gadd(gel(x,1),gel(y,1));
     966                 :            :       }
     967                 :   15986466 :       gel(z,1) = gadd(gel(x,1),gel(y,1));
     968                 :   15986466 :       return z;
     969                 :            :     case t_PADIC:
     970         [ -  + ]:      88230 :       if (!equalii(gel(x,2),gel(y,2))) pari_err_OP("+",x,y);
     971                 :      88230 :       return addsub_pp(x,y, addii);
     972                 :        410 :     case t_QUAD: z = cgetg(4,t_QUAD);
     973         [ -  + ]:        410 :       if (!ZX_equal(gel(x,1),gel(y,1))) pari_err_OP("+",x,y);
     974                 :        410 :       gel(z,1) = ZX_copy(gel(x,1));
     975                 :        410 :       gel(z,2) = gadd(gel(x,2),gel(y,2));
     976                 :        410 :       gel(z,3) = gadd(gel(x,3),gel(y,3)); return z;
     977                 :            :     case t_POLMOD:
     978         [ +  - ]:     160766 :       if (RgX_equal_var(gel(x,1), gel(y,1)))
     979                 :     160766 :         return addsub_polmod_same(gel(x,1), gel(x,2), gel(y,2), &gadd);
     980                 :          0 :       return addsub_polmod(gel(x,1), gel(y,1), gel(x,2), gel(y,2), &gadd);
     981                 :     410629 :     case t_FFELT: return FF_add(x,y);
     982                 :            :     case t_POL:
     983                 :    9376708 :       vx = varn(x);
     984                 :    9376708 :       vy = varn(y);
     985         [ +  + ]:    9376708 :       if (vx != vy) {
     986         [ +  + ]:     564518 :         if (varncmp(vx, vy) < 0) return RgX_Rg_add(x, y);
     987                 :      13982 :         else                     return RgX_Rg_add(y, x);
     988                 :            :       }
     989                 :    8812190 :       return RgX_add(x, y);
     990                 :            :     case t_SER:
     991                 :      33522 :       vx = varn(x);
     992                 :      33522 :       vy = varn(y);
     993         [ -  + ]:      33522 :       if (vx != vy) {
     994         [ #  # ]:          0 :         if (varncmp(vx, vy) < 0) return add_ser_scal(x, y);
     995                 :          0 :         else                     return add_ser_scal(y, x);
     996                 :            :       }
     997                 :      33522 :       return ser_add(x, y);
     998                 :            :     case t_RFRAC:
     999                 :    3004929 :       vx = varn(gel(x,2));
    1000                 :    3004929 :       vy = varn(gel(y,2));
    1001         [ +  + ]:    3004929 :       if (vx != vy) {
    1002         [ +  + ]:     941681 :         if (varncmp(vx, vy) < 0) return add_rfrac_scal(x, y);
    1003                 :     389890 :         else                     return add_rfrac_scal(y, x);
    1004                 :            :       }
    1005                 :    2063248 :       return add_rfrac(x,y);
    1006                 :            :     case t_VEC:
    1007         [ -  + ]:     418893 :       if (lg(y) != lg(x)) pari_err_OP("+",x,y);
    1008                 :     418893 :       return RgV_add(x,y);
    1009                 :            :     case t_COL:
    1010         [ -  + ]:    2935719 :       if (lg(y) != lg(x)) pari_err_OP("+",x,y);
    1011                 :    2935719 :       return RgC_add(x,y);
    1012                 :            :     case t_MAT:
    1013                 :         35 :       lx = lg(x);
    1014         [ -  + ]:         35 :       if (lg(y) != lx) pari_err_OP("+",x,y);
    1015         [ -  + ]:         35 :       if (lx == 1) return cgetg(1, t_MAT);
    1016         [ +  + ]:         35 :       if (lgcols(y) != lgcols(x)) pari_err_OP("+",x,y);
    1017                 :         30 :       return RgM_add(x,y);
    1018                 :            : 
    1019                 :          0 :     default: pari_err_TYPE2("+",x,y);
    1020                 :            :   }
    1021                 :            :   /* tx != ty */
    1022         [ +  + ]:   67804372 :   if (tx > ty) { swap(x,y); lswap(tx,ty); }
    1023                 :            : 
    1024 [ +  + ][ +  +  :   67804372 :   if (is_const_t(ty)) switch(tx) /* tx < ty, is_const_t(tx) && is_const_t(ty) */
          +  +  -  +  -  
                      - ]
    1025                 :            :   {
    1026                 :            :     case t_INT:
    1027   [ +  +  +  +  :   50222530 :       switch(ty)
             +  +  +  - ]
    1028                 :            :       {
    1029                 :   33416740 :         case t_REAL: return addir(x,y);
    1030                 :            :         case t_INTMOD:
    1031                 :     378734 :           z = cgetg(3, t_INTMOD);
    1032                 :     378734 :           return add_intmod_same(z, gel(y,1), gel(y,2), modii(x, gel(y,1)));
    1033                 :    2983772 :         case t_FRAC: z = cgetg(3,t_FRAC);
    1034                 :    2983772 :           gel(z,1) = gerepileuptoint((pari_sp)z, addii(gel(y,1), mulii(gel(y,2),x)));
    1035                 :    2983772 :           gel(z,2) = icopy(gel(y,2)); return z;
    1036                 :   13308998 :         case t_COMPLEX: return addRc(x, y);
    1037                 :            :         case t_PADIC:
    1038         [ +  + ]:      51300 :           if (!signe(x)) return gcopy(y);
    1039                 :      48095 :           return addQp(x,y);
    1040                 :        680 :         case t_QUAD: return addRq(x, y);
    1041                 :      82306 :         case t_FFELT: return FF_Z_add(y,x);
    1042                 :            :       }
    1043                 :            : 
    1044                 :            :     case t_REAL:
    1045   [ +  +  +  - ]:    5827964 :       switch(ty)
    1046                 :            :       {
    1047                 :            :         case t_FRAC:
    1048         [ -  + ]:     525367 :           if (!signe(gel(y,1))) return rcopy(x);
    1049         [ +  + ]:     525367 :           if (!signe(x))
    1050                 :            :           {
    1051                 :       3285 :             lx = expi(gel(y,1)) - expi(gel(y,2)) - expo(x);
    1052         [ -  + ]:       3285 :             return lx <= 0? rcopy(x): fractor(y, nbits2prec(lx));
    1053                 :            :           }
    1054                 :     522082 :           av=avma; z=addir(gel(y,1),mulir(gel(y,2),x)); tetpil=avma;
    1055                 :     522082 :           return gerepile(av,tetpil,divri(z,gel(y,2)));
    1056                 :    5302592 :         case t_COMPLEX: return addRc(x, y);
    1057         [ -  + ]:          5 :         case t_QUAD: return gequal0(y)? rcopy(x): addqf(y, x, lg(x));
    1058                 :            : 
    1059                 :          0 :         default: pari_err_TYPE2("+",x,y);
    1060                 :            :       }
    1061                 :            : 
    1062                 :            :     case t_INTMOD:
    1063   [ +  +  +  -  :       2838 :       switch(ty)
                   +  - ]
    1064                 :            :       {
    1065                 :       2500 :         case t_FRAC: { GEN X = gel(x,1);
    1066                 :       2500 :           z = cgetg(3, t_INTMOD);
    1067                 :       2500 :           p1 = Fp_div(gel(y,1), gel(y,2), X);
    1068                 :       2500 :           return add_intmod_same(z, X, p1, gel(x,2));
    1069                 :            :         }
    1070                 :            :         case t_FFELT:
    1071         [ -  + ]:        288 :           if (!equalii(gel(x,1),FF_p_i(y)))
    1072                 :          0 :             pari_err_OP("+",x,y);
    1073                 :        288 :           return FF_Z_add(y,gel(x,2));
    1074                 :         40 :         case t_COMPLEX: return addRc(x, y);
    1075                 :          0 :         case t_PADIC: { GEN X = gel(x,1);
    1076                 :          0 :           z = cgetg(3, t_INTMOD);
    1077                 :          0 :           return add_intmod_same(z, X, gel(x,2), padic_to_Fp(y, X));
    1078                 :            :         }
    1079                 :         10 :         case t_QUAD: return addRq(x, y);
    1080                 :            :       }
    1081                 :            : 
    1082                 :            :     case t_FRAC:
    1083   [ +  +  -  +  :      35535 :       switch (ty)
                      - ]
    1084                 :            :       {
    1085                 :      33410 :         case t_COMPLEX: return addRc(x, y);
    1086                 :            :         case t_PADIC:
    1087         [ -  + ]:       1095 :           if (!signe(gel(x,1))) return gcopy(y);
    1088                 :       1095 :           return addQp(x,y);
    1089                 :          0 :         case t_QUAD: return addRq(x, y);
    1090                 :       1030 :         case t_FFELT: return FF_Q_add(y, x);
    1091                 :            :       }
    1092                 :            : 
    1093                 :            :     case t_FFELT:
    1094                 :          0 :       pari_err_TYPE2("+",x,y);
    1095                 :            : 
    1096                 :            :     case t_COMPLEX:
    1097      [ +  +  - ]:         20 :       switch(ty)
    1098                 :            :       {
    1099                 :            :         case t_PADIC:
    1100         [ +  + ]:         15 :           return Zp_nosquare_m1(gel(y,2))? addRc(y, x): addTp(x, y);
    1101                 :            :         case t_QUAD:
    1102         [ -  + ]:          5 :           lx = precision(x); if (!lx) pari_err_OP("+",x,y);
    1103         [ -  + ]:          5 :           return gequal0(y)? gcopy(x): addqf(y, x, lx);
    1104                 :            :       }
    1105                 :            : 
    1106                 :            :     case t_PADIC: /* ty == t_QUAD */
    1107         [ #  # ]:          0 :       return (kro_quad(y,gel(x,2)) == -1)? addRq(x, y): addTp(y, x);
    1108                 :            :   }
    1109                 :            :   /* tx < ty, !is_const_t(y) */
    1110   [ +  +  +  + ]:   11715485 :   switch(ty)
    1111                 :            :   {
    1112                 :            :     case t_MAT:
    1113         [ -  + ]:       6895 :       if (is_matvec_t(tx)) pari_err_TYPE2("+",x,y);
    1114         [ +  + ]:       6895 :       if (isrationalzero(x)) return gcopy(y);
    1115                 :       6875 :       return RgM_Rg_add(y, x);
    1116                 :            :     case t_COL:
    1117         [ -  + ]:      22020 :       if (tx == t_VEC) pari_err_TYPE2("+",x,y);
    1118                 :      22020 :       return RgC_Rg_add(y, x);
    1119                 :            :     case t_POLMOD: /* is_const_t(tx) in this case */
    1120                 :      71230 :       return addsub_polmod_scal(gel(y,1), gel(y,2), x, &gadd);
    1121                 :            :   }
    1122         [ +  + ]:   11615340 :   if (is_scalar_t(tx))  {
    1123         [ +  + ]:    9596008 :     if (tx == t_POLMOD)
    1124                 :            :     {
    1125                 :       3375 :       vx = varn(gel(x,1));
    1126                 :       3375 :       vy = gvar(y);
    1127         [ +  + ]:       3375 :       if (vx == vy) y = gmod(y, gel(x,1)); /* error if ty == t_SER */
    1128                 :            :       else
    1129         [ +  + ]:       1830 :         if (varncmp(vx,vy) > 0) return add_scal(y, x, ty);
    1130                 :       1600 :       return addsub_polmod_scal(gel(x,1), gel(x,2), y, &gadd);
    1131                 :            :     }
    1132                 :    9592633 :     return add_scal(y, x, ty);
    1133                 :            :   }
    1134                 :            :   /* x and y are not scalars, ty != t_MAT */
    1135                 :    2019332 :   vx = gvar(x);
    1136                 :    2019332 :   vy = gvar(y);
    1137         [ +  + ]:    2019332 :   if (vx != vy) { /* x or y is treated as a scalar */
    1138 [ +  - ][ -  + ]:       2300 :     if (is_vec_t(tx) || is_vec_t(ty)) pari_err_TYPE2("+",x,y);
    1139                 :       2300 :     return (varncmp(vx, vy) < 0)? add_scal(x, y, tx)
    1140         [ +  + ]:       2300 :                                 : add_scal(y, x, ty);
    1141                 :            :   }
    1142                 :            :   /* vx = vy */
    1143      [ +  +  - ]:    2017032 :   switch(tx)
    1144                 :            :   {
    1145                 :            :     case t_POL:
    1146      [ +  +  - ]:    2015452 :       switch (ty)
    1147                 :            :       {
    1148                 :            :         case t_SER:
    1149         [ +  + ]:       1915 :           if (lg(x) == 2) return gcopy(y);
    1150                 :       1905 :           i = lg(y) + valp(y) - RgX_val(x);
    1151         [ -  + ]:       1905 :           if (i < 3) return gcopy(y);
    1152                 :            : 
    1153                 :       1905 :           p1 = RgX_to_ser(x,i); y = ser_add(p1,y);
    1154                 :       1905 :           settyp(p1, t_VECSMALL); /* p1 left on stack */
    1155                 :       1905 :           return y;
    1156                 :            : 
    1157                 :    2013537 :         case t_RFRAC: return add_rfrac_scal(y, x);
    1158                 :            :       }
    1159                 :          0 :       break;
    1160                 :            : 
    1161                 :            :     case t_SER:
    1162         [ +  - ]:       1580 :       if (ty == t_RFRAC)
    1163                 :            :       {
    1164                 :            :         GEN n, d;
    1165                 :            :         long vn, vd;
    1166                 :       1580 :         av = avma;
    1167                 :       1580 :         n = gel(y,1); vn = gval(n, vy);
    1168                 :       1580 :         d = gel(y,2); vd = RgX_valrem(d, &d);
    1169                 :            : 
    1170                 :       1580 :         l = lg(x) + valp(x) - (vn - vd);
    1171         [ -  + ]:       1580 :         if (l < 3) { avma = av; return gcopy(x); }
    1172                 :            : 
    1173                 :            :         /* take advantage of y = t^n ! */
    1174         [ +  + ]:       1580 :         if (degpol(d))
    1175                 :         55 :           y = gdiv(n, RgX_to_ser_inexact(d,l));
    1176                 :            :         else {
    1177                 :       1525 :           y = gdiv(n, gel(d,2));
    1178         [ +  + ]:       1525 :           if (gvar(y) == vy) y = RgX_to_ser(y,l); else y = scalarser(y, vy, l);
    1179                 :            :         }
    1180                 :       1580 :         setvalp(y, valp(y) - vd);
    1181                 :       1580 :         return gerepileupto(av, gadd(y, x));
    1182                 :            :       }
    1183                 :          0 :       break;
    1184                 :            :   }
    1185                 :          0 :   pari_err_TYPE2("+",x,y);
    1186                 :  482287922 :   return NULL; /* not reached */
    1187                 :            : }
    1188                 :            : 
    1189                 :            : GEN
    1190                 :    1947524 : gaddsg(long x, GEN y)
    1191                 :            : {
    1192                 :    1947524 :   long ty = typ(y);
    1193                 :            :   GEN z;
    1194                 :            : 
    1195   [ +  +  +  +  :    1947524 :   switch(ty)
                   +  + ]
    1196                 :            :   {
    1197                 :     113148 :     case t_INT:  return addsi(x,y);
    1198                 :     855542 :     case t_REAL: return addsr(x,y);
    1199                 :            :     case t_INTMOD:
    1200                 :         10 :       z = cgetg(3, t_INTMOD);
    1201                 :         10 :       return add_intmod_same(z, gel(y,1), gel(y,2), modsi(x, gel(y,1)));
    1202                 :      15645 :     case t_FRAC: z = cgetg(3,t_FRAC);
    1203                 :      15645 :       gel(z,1) = gerepileuptoint((pari_sp)z, addii(gel(y,1), mulis(gel(y,2),x)));
    1204                 :      15645 :       gel(z,2) = icopy(gel(y,2)); return z;
    1205                 :            :     case t_COMPLEX:
    1206                 :     729659 :       z = cgetg(3, t_COMPLEX);
    1207                 :     729659 :       gel(z,1) = gaddsg(x, gel(y,1));
    1208                 :     729659 :       gel(z,2) = gcopy(gel(y,2)); return z;
    1209                 :            : 
    1210                 :    1947524 :     default: return gadd(stoi(x), y);
    1211                 :            :   }
    1212                 :            : }
    1213                 :            : 
    1214                 :            : GEN
    1215                 :     248129 : gsubsg(long x, GEN y)
    1216                 :            : {
    1217                 :            :   GEN z, a, b;
    1218                 :            :   pari_sp av;
    1219                 :            : 
    1220   [ +  +  +  +  :     248129 :   switch(typ(y))
                   +  + ]
    1221                 :            :   {
    1222                 :     158090 :     case t_INT:  return subsi(x,y);
    1223                 :      56505 :     case t_REAL: return subsr(x,y);
    1224                 :            :     case t_INTMOD:
    1225                 :          5 :       z = cgetg(3, t_INTMOD); a = gel(y,1); b = gel(y,2);
    1226                 :          5 :       return add_intmod_same(z, a, Fp_neg(b,a), modsi(x, a));
    1227                 :         25 :     case t_FRAC: z = cgetg(3,t_FRAC); a = gel(y,1); b = gel(y,2);
    1228                 :         25 :       gel(z,1) = gerepileuptoint((pari_sp)z, subii(mulis(b,x), a));
    1229                 :         25 :       gel(z,2) = icopy(gel(y,2)); return z;
    1230                 :            :     case t_COMPLEX:
    1231                 :      29164 :       z = cgetg(3, t_COMPLEX);
    1232                 :      29164 :       gel(z,1) = gsubsg(x, gel(y,1));
    1233                 :      29164 :       gel(z,2) = gneg(gel(y,2)); return z;
    1234                 :            :   }
    1235                 :       4340 :   av = avma;
    1236                 :     248129 :   return gerepileupto(av, gadd(stoi(x), gneg_i(y)));
    1237                 :            : }
    1238                 :            : 
    1239                 :            : /********************************************************************/
    1240                 :            : /**                                                                **/
    1241                 :            : /**                          SUBTRACTION                           **/
    1242                 :            : /**                                                                **/
    1243                 :            : /********************************************************************/
    1244                 :            : 
    1245                 :            : GEN
    1246                 :  936358402 : gsub(GEN x, GEN y)
    1247                 :            : {
    1248                 :  936358402 :   long tx = typ(x), ty = typ(y);
    1249                 :            :   pari_sp av;
    1250                 :            :   GEN z;
    1251 [ +  + ][ +  +  :  936358402 :   if (tx == ty) switch(tx) /* shortcut to generic case */
          +  +  +  +  +  
          +  +  +  +  +  
                +  +  - ]
    1252                 :            :   {
    1253                 :  833149462 :     case t_INT: return subii(x,y);
    1254                 :   79547180 :     case t_REAL: return subrr(x,y);
    1255                 :     288536 :     case t_INTMOD:  { GEN p1, X = gel(x,1), Y = gel(y,1);
    1256                 :     288536 :       z = cgetg(3,t_INTMOD);
    1257 [ +  - ][ +  + ]:     288536 :       if (X==Y || equalii(X,Y))
    1258                 :     288531 :         return sub_intmod_same(z, X, gel(x,2), gel(y,2));
    1259                 :          5 :       gel(z,1) = gcdii(X,Y);
    1260                 :          5 :       av = avma; p1 = subii(gel(x,2),gel(y,2));
    1261                 :          5 :       gel(z,2) = gerepileuptoint(av, modii(p1, gel(z,1))); return z;
    1262                 :            :     }
    1263                 :    1443098 :     case t_FRAC: return addsub_frac(x,y, subii);
    1264                 :    8962317 :     case t_COMPLEX: z = cgetg(3,t_COMPLEX);
    1265                 :    8962317 :       gel(z,2) = gsub(gel(x,2),gel(y,2));
    1266         [ +  + ]:    8962317 :       if (isintzero(gel(z,2)))
    1267                 :            :       {
    1268                 :       2788 :         avma = (pari_sp)(z+3);
    1269                 :       2788 :         return gsub(gel(x,1),gel(y,1));
    1270                 :            :       }
    1271                 :    8959529 :       gel(z,1) = gsub(gel(x,1),gel(y,1));
    1272                 :    8959529 :       return z;
    1273                 :            :     case t_PADIC:
    1274         [ -  + ]:      60320 :       if (!equalii(gel(x,2),gel(y,2))) pari_err_OP("+",x,y);
    1275                 :      60320 :       return addsub_pp(x,y, subii);
    1276                 :        800 :     case t_QUAD: z = cgetg(4,t_QUAD);
    1277         [ -  + ]:        800 :       if (!ZX_equal(gel(x,1),gel(y,1))) pari_err_OP("+",x,y);
    1278                 :        800 :       gel(z,1) = ZX_copy(gel(x,1));
    1279                 :        800 :       gel(z,2) = gsub(gel(x,2),gel(y,2));
    1280                 :        800 :       gel(z,3) = gsub(gel(x,3),gel(y,3)); return z;
    1281                 :            :     case t_POLMOD:
    1282         [ +  - ]:      76647 :       if (RgX_equal_var(gel(x,1), gel(y,1)))
    1283                 :      76647 :         return addsub_polmod_same(gel(x,1), gel(x,2), gel(y,2), &gsub);
    1284                 :          0 :       return addsub_polmod(gel(x,1), gel(y,1), gel(x,2), gel(y,2), &gsub);
    1285                 :     130450 :     case t_FFELT: return FF_sub(x,y);
    1286                 :            :     case t_POL: {
    1287                 :    2898123 :       long vx = varn(x);
    1288                 :    2898123 :       long vy = varn(y);
    1289         [ +  + ]:    2898123 :       if (vx != vy) {
    1290         [ +  + ]:       7501 :         if (varncmp(vx, vy) < 0) return RgX_Rg_sub(x, y);
    1291                 :        975 :         else                     return Rg_RgX_sub(x, y);
    1292                 :            :       }
    1293                 :    2890622 :       return RgX_sub(x, y);
    1294                 :            :     }
    1295                 :            :     case t_VEC:
    1296         [ -  + ]:      36100 :       if (lg(y) != lg(x)) pari_err_OP("+",x,y);
    1297                 :      36100 :       return RgV_sub(x,y);
    1298                 :            :     case t_COL:
    1299         [ -  + ]:     761982 :       if (lg(y) != lg(x)) pari_err_OP("+",x,y);
    1300                 :     761982 :       return RgC_sub(x,y);
    1301                 :            :     case t_MAT: {
    1302                 :       3518 :       long lx = lg(x);
    1303         [ -  + ]:       3518 :       if (lg(y) != lx) pari_err_OP("+",x,y);
    1304         [ -  + ]:       3518 :       if (lx == 1) return cgetg(1, t_MAT);
    1305         [ -  + ]:       3518 :       if (lgcols(y) != lgcols(x)) pari_err_OP("+",x,y);
    1306                 :       3518 :       return RgM_sub(x,y);
    1307                 :            :     }
    1308                 :    1262631 :     case t_RFRAC: case t_SER: break;
    1309                 :            : 
    1310                 :          0 :     default: pari_err_TYPE2("+",x,y);
    1311                 :            :   }
    1312                 :    8999869 :   av = avma;
    1313                 :  936358402 :   return gerepileupto(av, gadd(x,gneg_i(y)));
    1314                 :            : }
    1315                 :            : 
    1316                 :            : /********************************************************************/
    1317                 :            : /**                                                                **/
    1318                 :            : /**                        MULTIPLICATION                          **/
    1319                 :            : /**                                                                **/
    1320                 :            : /********************************************************************/
    1321                 :            : static GEN
    1322                 :     125932 : mul_ser_scal(GEN y, GEN x) {
    1323                 :            :   long ly, i;
    1324                 :            :   GEN z;
    1325         [ +  + ]:     125932 :   if (ser_isexactzero(y))
    1326                 :            :   {
    1327         [ +  - ]:       4795 :     if (lg(y) == 2) return gcopy(y);
    1328                 :          0 :     return scalarser(gmul(x,gel(y,2)), varn(y), valp(y));
    1329                 :            :   }
    1330                 :     121137 :   z = cgetg_copy(y, &ly); z[1] = y[1];
    1331         [ +  + ]:     599149 :   for (i = 2; i < ly; i++) gel(z,i) = gmul(x,gel(y,i));
    1332                 :     125932 :   return normalize(z);
    1333                 :            : }
    1334                 :            : /* (n/d) * x, x "scalar" or polynomial in the same variable as d
    1335                 :            :  * [n/d a valid RFRAC]  */
    1336                 :            : static GEN
    1337                 :    6858467 : mul_rfrac_scal(GEN n, GEN d, GEN x)
    1338                 :            : {
    1339                 :    6858467 :   pari_sp av = avma;
    1340                 :            :   GEN z;
    1341                 :            : 
    1342      [ -  +  + ]:    6858467 :   switch(typ(x))
    1343                 :            :   {
    1344                 :            :     case t_PADIC:
    1345                 :          0 :       n = gmul(n, x);
    1346         [ #  # ]:          0 :       d = gcvtop(d, gel(x,2), signe(gel(x,4))? precp(x): 1);
    1347                 :          0 :       return gerepileupto(av, gdiv(n,d));
    1348                 :            : 
    1349                 :            :     case t_INTMOD: case t_POLMOD:
    1350                 :        170 :       n = gmul(n, x);
    1351                 :        170 :       d = gmul(d, gmodulo(gen_1, gel(x,1)));
    1352                 :        170 :       return gerepileupto(av, gdiv(n,d));
    1353                 :            :   }
    1354                 :    6858297 :   z = gred_rfrac2_i(x, d);
    1355                 :    6858297 :   n = simplify_shallow(n);
    1356         [ +  + ]:    6858297 :   if (typ(z) == t_RFRAC)
    1357                 :            :   {
    1358                 :    5103665 :     n = gmul(gel(z,1), n);
    1359                 :    5103665 :     d = gel(z,2);
    1360 [ +  + ][ +  + ]:    5103665 :     if (typ(n) == t_POL && varncmp(varn(n), varn(d)) < 0)
    1361                 :        120 :       z = RgX_Rg_div(n, d);
    1362                 :            :     else
    1363                 :    5103665 :       z = gred_rfrac_simple(n, d);
    1364                 :            :   }
    1365                 :            :   else
    1366                 :    1754632 :     z = gmul(z, n);
    1367                 :    6858467 :   return gerepileupto(av, z);
    1368                 :            : }
    1369                 :            : static GEN
    1370                 :   38542135 : mul_scal(GEN y, GEN x, long ty)
    1371                 :            : {
    1372   [ +  +  +  -  :   38542135 :   switch(ty)
                      - ]
    1373                 :            :   {
    1374                 :            :     case t_POL:
    1375         [ +  + ]:   32619491 :       if (lg(y) == 2) return scalarpol(gmul(gen_0,x), varn(y));
    1376                 :   32050389 :       return RgX_Rg_mul(y, x);
    1377                 :      92687 :     case t_SER: return mul_ser_scal(y, x);
    1378                 :    5829957 :     case t_RFRAC: return mul_rfrac_scal(gel(y,1),gel(y,2), x);
    1379                 :            :     case t_QFI: case t_QFR:
    1380 [ #  # ][ #  # ]:          0 :       if (typ(x) == t_INT && gequal1(x)) return gcopy(y); /* fall through */
    1381                 :            :   }
    1382                 :          0 :   pari_err_TYPE2("*",x,y);
    1383                 :   38542130 :   return NULL; /* not reached */
    1384                 :            : }
    1385                 :            : 
    1386                 :            : static GEN
    1387                 :     122462 : mul_gen_rfrac(GEN X, GEN Y)
    1388                 :            : {
    1389                 :     122462 :   GEN y1 = gel(Y,1), y2 = gel(Y,2);
    1390                 :     122462 :   long vx = gvar(X), vy = varn(y2);
    1391         [ +  + ]:     126562 :   return (varncmp(vx, vy) <= 0)? mul_scal(Y, X, typ(Y)):
    1392                 :       4100 :                                  gred_rfrac_simple(gmul(y1,X), y2);
    1393                 :            : }
    1394                 :            : /* (x1/x2) * (y1/y2) */
    1395                 :            : static GEN
    1396                 :    5598195 : mul_rfrac(GEN x1, GEN x2, GEN y1, GEN y2)
    1397                 :            : {
    1398                 :            :   GEN z, X, Y;
    1399                 :    5598195 :   pari_sp av = avma;
    1400                 :            : 
    1401                 :    5598195 :   X = gred_rfrac2_i(x1, y2);
    1402                 :    5598195 :   Y = gred_rfrac2_i(y1, x2);
    1403         [ +  + ]:    5598195 :   if (typ(X) == t_RFRAC)
    1404                 :            :   {
    1405         [ +  + ]:    4663553 :     if (typ(Y) == t_RFRAC) {
    1406                 :    4603382 :       x1 = gel(X,1);
    1407                 :    4603382 :       x2 = gel(X,2);
    1408                 :    4603382 :       y1 = gel(Y,1);
    1409                 :    4603382 :       y2 = gel(Y,2);
    1410                 :    4603382 :       z = gred_rfrac_simple(gmul(x1,y1), gmul(x2,y2));
    1411                 :            :     } else
    1412                 :      60171 :       z = mul_gen_rfrac(Y, X);
    1413                 :            :   }
    1414         [ +  + ]:     934642 :   else if (typ(Y) == t_RFRAC)
    1415                 :      62291 :     z = mul_gen_rfrac(X, Y);
    1416                 :            :   else
    1417                 :     872351 :     z = gmul(X, Y);
    1418                 :    5598195 :   return gerepileupto(av, z);
    1419                 :            : }
    1420                 :            : /* (x1/x2) /y2, x2 and y2 are t_POL in the same variable */
    1421                 :            : static GEN
    1422                 :     188093 : div_rfrac_pol(GEN x1, GEN x2, GEN y2)
    1423                 :            : {
    1424                 :     188093 :   pari_sp av = avma;
    1425                 :     188093 :   GEN X = gred_rfrac2_i(x1, y2);
    1426 [ +  + ][ +  + ]:     188093 :   if (typ(X) == t_RFRAC && varn(gel(X,2)) == varn(x2))
    1427                 :            :   {
    1428                 :     183413 :     x2 = RgX_mul(gel(X,2), x2);
    1429                 :     183413 :     x1 = gel(X,1);
    1430                 :            :   }
    1431                 :            :   else
    1432                 :       4680 :     x1 = X;
    1433                 :     188093 :   return gerepileupto(av, gred_rfrac_simple(x1, x2));
    1434                 :            : }
    1435                 :            : 
    1436                 :            : /* Mod(y, Y) * x,  assuming x scalar */
    1437                 :            : static GEN
    1438                 :      34936 : mul_polmod_scal(GEN Y, GEN y, GEN x)
    1439                 :            : {
    1440                 :      34936 :   GEN z = cgetg(3,t_POLMOD);
    1441                 :      34936 :   gel(z,1) = RgX_copy(Y);
    1442                 :      34936 :   gel(z,2) = gmul(x,y); return z;
    1443                 :            : }
    1444                 :            : 
    1445                 :            : /* cf mulqq */
    1446                 :            : static GEN
    1447                 :      12954 : quad_polmod_mul(GEN P, GEN x, GEN y)
    1448                 :            : {
    1449                 :      12954 :   GEN T = cgetg(4, t_POL), b = gel(P,3), c = gel(P,2), p1, p2, p3, p4;
    1450                 :      12954 :   pari_sp tetpil, av = avma;
    1451                 :      12954 :   T[1] = x[1];
    1452                 :      12954 :   p2 = gmul(gel(x,2), gel(y,2));
    1453                 :      12954 :   p3 = gmul(gel(x,3), gel(y,3));
    1454                 :      12954 :   p1 = gmul(gneg_i(c),p3);
    1455                 :            :   /* operands are usually small: gadd ~ gmul and Karatsuba is a waste */
    1456         [ +  - ]:      12954 :   if (typ(b) == t_INT)
    1457                 :            :   {
    1458         [ +  + ]:      12954 :     if (signe(b))
    1459                 :            :     {
    1460                 :      10417 :       p4 = gadd(gmul(gel(x,2), gel(y,3)), gmul(gel(x,3), gel(y,2)));
    1461         [ +  + ]:      10417 :       if (is_pm1(b))
    1462                 :            :       {
    1463         [ +  + ]:      10357 :         if (signe(b) > 0) p3 = gneg(p3);
    1464                 :            :       }
    1465                 :            :       else
    1466                 :         60 :         p3 = gmul(negi(b), p3);
    1467                 :            :     }
    1468                 :            :     else
    1469                 :            :     {
    1470                 :       2537 :       p3 = gmul(gel(x,2),gel(y,3));
    1471                 :       2537 :       p4 = gmul(gel(x,3),gel(y,2));
    1472                 :            :     }
    1473                 :            :   }
    1474                 :            :   else
    1475                 :            :   {
    1476                 :          0 :     p4 = gadd(gmul(gel(x,2), gel(y,3)), gmul(gel(x,3), gel(y,2)));
    1477                 :          0 :     p3 = gmul(gneg_i(b), p3);
    1478                 :            :   }
    1479                 :      12954 :   tetpil = avma;
    1480                 :      12954 :   gel(T,2) = gadd(p2, p1);
    1481                 :      12954 :   gel(T,3) = gadd(p4, p3);
    1482                 :      12954 :   gerepilecoeffssp(av,tetpil,T+2,2);
    1483                 :      12954 :   return normalizepol_lg(T,4);
    1484                 :            : }
    1485                 :            : /* Mod(x,T) * Mod(y,T) */
    1486                 :            : static GEN
    1487                 :     275365 : mul_polmod_same(GEN T, GEN x, GEN y)
    1488                 :            : {
    1489                 :     275365 :   GEN z = cgetg(3,t_POLMOD), a;
    1490                 :     275365 :   long v = varn(T), lx = lg(x), ly = lg(y);
    1491                 :     275365 :   gel(z,1) = RgX_copy(T);
    1492                 :            :   /* x * y mod T optimised */
    1493 [ +  + ][ +  - ]:     275365 :   if (typ(x) != t_POL || varn(x) != v || lx <= 3
                 [ +  + ]
    1494 [ +  + ][ +  - ]:     150035 :    || typ(y) != t_POL || varn(y) != v || ly <= 3)
                 [ +  + ]
    1495                 :     170805 :     a = gmul(x, y);
    1496                 :            :   else
    1497                 :            :   {
    1498 [ +  + ][ +  + ]:     104560 :     if (lg(T) == 5 && isint1(gel(T,4))) /* quadratic fields */
    1499                 :      12324 :       a = quad_polmod_mul(T, x, y);
    1500                 :            :     else
    1501                 :            :     {
    1502                 :      92236 :       pari_sp av = avma;
    1503                 :      92236 :       GEN p = NULL;
    1504 [ +  + ][ +  + ]:      92236 :       if (RgX_is_FpX(T, &p) && RgX_is_FpX(x, &p) && RgX_is_FpX(y, &p) && p)
         [ +  + ][ +  + ]
    1505                 :            :       {
    1506                 :      27695 :         T = RgX_to_FpX(T, p); x = RgX_to_FpX(x, p); y = RgX_to_FpX(y, p);
    1507         [ +  + ]:      27695 :         if (lgefint(p) == 3)
    1508                 :            :         {
    1509                 :      24240 :           ulong pp = p[2];
    1510                 :      24240 :           a = Flxq_mul(ZX_to_Flx(x, pp), ZX_to_Flx(y, pp), ZX_to_Flx(T, pp), pp);
    1511                 :      24240 :           a = Flx_to_ZX(a);
    1512                 :            :         }
    1513                 :            :         else
    1514                 :       3455 :           a = FpXQ_mul(x, y, T, p);
    1515                 :      27695 :         a = FpX_to_mod(a, p);
    1516                 :            :       }
    1517                 :            :       else
    1518                 :      64541 :         a = RgXQ_mul(x, y, gel(z,1));
    1519                 :      92236 :       a = gerepileupto(av, a);
    1520                 :            :     }
    1521                 :            :   }
    1522                 :     275365 :   gel(z,2) = a; return z;
    1523                 :            : }
    1524                 :            : static GEN
    1525                 :      10686 : sqr_polmod(GEN T, GEN x)
    1526                 :            : {
    1527                 :      10686 :   GEN a, z = cgetg(3,t_POLMOD);
    1528                 :      10686 :   gel(z,1) = RgX_copy(T);
    1529 [ +  + ][ +  - ]:      10686 :   if (typ(x) != t_POL || varn(x) != varn(T) || lg(x) <= 3)
                 [ +  + ]
    1530                 :       1701 :     a = gsqr(x);
    1531                 :            :   else
    1532                 :            :   {
    1533                 :       8985 :     pari_sp av = avma;
    1534                 :       8985 :     GEN p = NULL;
    1535 [ +  - ][ +  + ]:       8985 :     if (RgX_is_FpX(T, &p) && RgX_is_FpX(x, &p) && p)
                 [ +  + ]
    1536                 :            :     {
    1537                 :         60 :       T = RgX_to_FpX(T, p); x = RgX_to_FpX(x, p);
    1538         [ +  + ]:         60 :       if (lgefint(p) == 3)
    1539                 :            :       {
    1540                 :         55 :         ulong pp = p[2];
    1541                 :         55 :         a = Flxq_sqr(ZX_to_Flx(x, pp), ZX_to_Flx(T, pp), pp);
    1542                 :         55 :         a = Flx_to_ZX(a);
    1543                 :            :       }
    1544                 :            :       else
    1545                 :          5 :         a = FpXQ_sqr(x, T, p);
    1546                 :         60 :       a = FpX_to_mod(a, p);
    1547                 :            :     }
    1548                 :            :     else
    1549                 :       8925 :       a = RgXQ_sqr(x, gel(z,1));
    1550                 :       8985 :     a = gerepileupto(av, a);
    1551                 :            :   }
    1552                 :      10686 :   gel(z,2) = a; return z;
    1553                 :            : }
    1554                 :            : /* Mod(x,X) * Mod(y,Y) */
    1555                 :            : static GEN
    1556                 :          5 : mul_polmod(GEN X, GEN Y, GEN x, GEN y)
    1557                 :            : {
    1558                 :          5 :   long T[3] = { evaltyp(t_POLMOD) | _evallg(3),0,0 };
    1559                 :          5 :   long vx = varn(X), vy = varn(Y);
    1560                 :          5 :   GEN z = cgetg(3,t_POLMOD);
    1561                 :            : 
    1562         [ -  + ]:          5 :   if (vx==vy) {
    1563                 :            :     pari_sp av;
    1564                 :          0 :     gel(z,1) = RgX_gcd(X,Y); av = avma;
    1565                 :          0 :     gel(z,2) = gerepileupto(av, gmod(gmul(x, y), gel(z,1)));
    1566                 :          0 :     return z;
    1567                 :            :   }
    1568         [ +  - ]:          5 :   if (varncmp(vx, vy) < 0)
    1569                 :          5 :   { gel(z,1) = RgX_copy(X); gel(T,1) = Y; gel(T,2) = y; y = T; }
    1570                 :            :   else
    1571                 :          0 :   { gel(z,1) = RgX_copy(Y); gel(T,1) = X; gel(T,2) = x; x = T; }
    1572                 :          5 :   gel(z,2) = gmul(x, y); return z;
    1573                 :            : }
    1574                 :            : 
    1575                 :            : #if 0 /* used by 3M only */
    1576                 :            : /* set z = x+y and return 1 if x,y have the same sign
    1577                 :            :  * set z = x-y and return 0 otherwise */
    1578                 :            : static int
    1579                 :            : did_add(GEN x, GEN y, GEN *z)
    1580                 :            : {
    1581                 :            :   long tx = typ(x), ty = typ(y);
    1582                 :            :   if (tx == ty) switch(tx)
    1583                 :            :   {
    1584                 :            :     case t_INT: *z = addii(x,y); return 1;
    1585                 :            :     case t_FRAC: *z = addsub_frac(x,y,addii); return 1;
    1586                 :            :     case t_REAL:
    1587                 :            :       if (signe(x) == -signe(y))
    1588                 :            :       { *z = subrr(x,y); return 0; }
    1589                 :            :       else
    1590                 :            :       { *z = addrr(x,y); return 1; }
    1591                 :            :   }
    1592                 :            :   if (tx == t_REAL) switch(ty)
    1593                 :            :   {
    1594                 :            :     case t_INT:
    1595                 :            :       if (signe(x) == -signe(y))
    1596                 :            :       { *z = subri(x,y); return 0; }
    1597                 :            :       else
    1598                 :            :       { *z = addri(x,y); return 1; }
    1599                 :            :     case t_FRAC:
    1600                 :            :       if (signe(x) == -signe(gel(y,1)))
    1601                 :            :       { *z = gsub(x,y); return 0; }
    1602                 :            :       else
    1603                 :            :       { *z = gadd(x,y); return 1; }
    1604                 :            :   }
    1605                 :            :   else if (ty == t_REAL) switch(tx)
    1606                 :            :   {
    1607                 :            :     case t_INT:
    1608                 :            :       if (signe(x) == -signe(y))
    1609                 :            :       { *z = subir(x,y); return 0; }
    1610                 :            :       else
    1611                 :            :       { *z = addir(x,y); return 1; }
    1612                 :            :     case t_FRAC:
    1613                 :            :       if (signe(gel(x,1)) == -signe(y))
    1614                 :            :       { *z = gsub(x,y); return 0; }
    1615                 :            :       else
    1616                 :            :       { *z = gadd(x,y); return 1; }
    1617                 :            :   }
    1618                 :            :   *z = gadd(x,y); return 1;
    1619                 :            : }
    1620                 :            : #endif
    1621                 :            : /* x * I * y, x t_COMPLEX with non-intzero real part, y non-intzero "scalar" */
    1622                 :            : static GEN
    1623                 :     462184 : mulcIR(GEN x, GEN y)
    1624                 :            : {
    1625                 :     462184 :   GEN z = cgetg(3,t_COMPLEX);
    1626                 :     462184 :   pari_sp av = avma;
    1627                 :     462184 :   gel(z,1) = gerepileupto(av, gneg(gmul(y,gel(x,2))));
    1628                 :     462184 :   gel(z,2) = gmul(y, gel(x,1));
    1629                 :     462184 :   return z;
    1630                 :            : 
    1631                 :            : }
    1632                 :            : /* x,y COMPLEX */
    1633                 :            : static GEN
    1634                 :   35931245 : mulcc(GEN x, GEN y)
    1635                 :            : {
    1636                 :   35931245 :   GEN xr = gel(x,1), xi = gel(x,2);
    1637                 :   35931245 :   GEN yr = gel(y,1), yi = gel(y,2);
    1638                 :            :   GEN p1, p2, p3, p4, z;
    1639                 :            :   pari_sp tetpil, av;
    1640                 :            : 
    1641         [ +  + ]:   35931245 :   if (isintzero(xr))
    1642                 :            :   {
    1643         [ +  + ]:     465294 :     if (isintzero(yr)) {
    1644                 :      73486 :       av = avma;
    1645                 :      73486 :       return gerepileupto(av, gneg(gmul(xi,yi)));
    1646                 :            :     }
    1647                 :     391808 :     return mulcIR(y, xi);
    1648                 :            :   }
    1649         [ +  + ]:   35465951 :   if (isintzero(yr)) return mulcIR(x, yi);
    1650                 :            : 
    1651                 :   35395575 :   z = cgetg(3,t_COMPLEX); av = avma;
    1652                 :            : #if 0
    1653                 :            :   /* 3M method avoiding catastrophic cancellation, BUT loses accuracy due to
    1654                 :            :    * e.g. xr + xi if exponents differ */
    1655                 :            :   if (did_add(xr, xi, &p3))
    1656                 :            :   {
    1657                 :            :     if (did_add(yr, yi, &p4)) {
    1658                 :            :     /* R = xr*yr - xi*yi
    1659                 :            :      * I = (xr+xi)(yr+yi) - xr*yr - xi*yi */
    1660                 :            :       p1 = gmul(xr,yr);
    1661                 :            :       p2 = gmul(xi,yi); p2 = gneg(p2);
    1662                 :            :       p3 = gmul(p3, p4);
    1663                 :            :       p4 = gsub(p2, p1);
    1664                 :            :     } else {
    1665                 :            :     /* R = (xr + xi) * (yr - yi) + (xr * yi - xi * yr)
    1666                 :            :      * I = xr*yi + xi*yr */
    1667                 :            :       p1 = gmul(p3,p4);
    1668                 :            :       p3 = gmul(xr,yi);
    1669                 :            :       p4 = gmul(xi,yr);
    1670                 :            :       p2 = gsub(p3, p4);
    1671                 :            :     }
    1672                 :            :   } else {
    1673                 :            :     if (did_add(yr, yi, &p4)) {
    1674                 :            :      /* R = (xr - xi) * (yr + yi) + (xi * yr - xr * yi)
    1675                 :            :       * I = xr*yi +xi*yr */
    1676                 :            :       p1 = gmul(p3,p4);
    1677                 :            :       p3 = gmul(xr,yi);
    1678                 :            :       p4 = gmul(xi,yr);
    1679                 :            :       p2 = gsub(p4, p3);
    1680                 :            :     } else {
    1681                 :            :     /* R = xr*yr - xi*yi
    1682                 :            :      * I = -(xr-xi)(yr-yi) + xr*yr + xi*yi */
    1683                 :            :       p3 = gneg( gmul(p3, p4) );
    1684                 :            :       p1 = gmul(xr,yr);
    1685                 :            :       p2 = gmul(xi,yi);
    1686                 :            :       p4 = gadd(p1, p2);
    1687                 :            : 
    1688                 :            :       p2 = gneg(p2);
    1689                 :            :     }
    1690                 :            :   }
    1691                 :            :   tetpil = avma;
    1692                 :            :   gel(z,1) = gadd(p1,p2);
    1693                 :            :   gel(z,2) = gadd(p3,p4);
    1694                 :            : #else
    1695 [ +  + ][ +  + ]:   35395575 :   if (typ(xr)==t_INT && typ(yr)==t_INT && typ(xi)==t_INT && typ(yr)==t_INT)
         [ +  - ][ +  - ]
    1696                 :            :   { /* 3M formula */
    1697                 :         60 :     p3 = addii(xr,xi);
    1698                 :         60 :     p4 = addii(yr,yi);
    1699                 :         60 :     p1 = mulii(xr,yr);
    1700                 :         60 :     p2 = mulii(xi,yi);
    1701                 :         60 :     p3 = mulii(p3,p4);
    1702                 :         60 :     p4 = addii(p2,p1);
    1703                 :         60 :     tetpil = avma;
    1704                 :         60 :     gel(z,1) = subii(p1,p2);
    1705                 :         60 :     gel(z,2) = subii(p3,p4);
    1706         [ +  + ]:         60 :     if (!signe(gel(z,2)))
    1707                 :         35 :       return gerepileuptoint((pari_sp)(z+3), gel(z,1));
    1708                 :            :   }
    1709                 :            :   else
    1710                 :            :   { /* naive 4M formula: avoid all loss of accuracy */
    1711                 :   35395515 :     p1 = gmul(xr,yr);
    1712                 :   35395515 :     p2 = gmul(xi,yi);
    1713                 :   35395515 :     p3 = gmul(xr,yi);
    1714                 :   35395515 :     p4 = gmul(xi,yr);
    1715                 :   35395515 :     tetpil = avma;
    1716                 :   35395515 :     gel(z,1) = gsub(p1,p2);
    1717                 :   35395515 :     gel(z,2) = gadd(p3,p4);
    1718         [ +  + ]:   35395515 :     if (isintzero(gel(z,2)))
    1719                 :            :     {
    1720                 :       4744 :       cgiv(gel(z,2));
    1721                 :       4744 :       return gerepileupto((pari_sp)(z+3), gel(z,1));
    1722                 :            :     }
    1723                 :            :   }
    1724                 :            : #endif
    1725                 :            : 
    1726                 :   35931245 :   gerepilecoeffssp(av,tetpil, z+1,2); return z;
    1727                 :            : }
    1728                 :            : /* x,y PADIC */
    1729                 :            : static GEN
    1730                 :     204325 : mulpp(GEN x, GEN y) {
    1731                 :     204325 :   long l = valp(x) + valp(y);
    1732                 :            :   pari_sp av;
    1733                 :            :   GEN z, t;
    1734         [ -  + ]:     204325 :   if (!equalii(gel(x,2),gel(y,2))) pari_err_OP("*",x,y);
    1735         [ +  + ]:     204325 :   if (!signe(gel(x,4))) return zeropadic(gel(x,2), l);
    1736         [ +  + ]:     203565 :   if (!signe(gel(y,4))) return zeropadic(gel(x,2), l);
    1737                 :            : 
    1738         [ +  + ]:     203035 :   t = (precp(x) > precp(y))? y: x;
    1739                 :     203035 :   z = cgetp(t); setvalp(z,l); av = avma;
    1740                 :     203035 :   affii(remii(mulii(gel(x,4),gel(y,4)), gel(t,3)), gel(z,4));
    1741                 :     204325 :   avma = av; return z;
    1742                 :            : }
    1743                 :            : /* x,y QUAD */
    1744                 :            : static GEN
    1745                 :       1835 : mulqq(GEN x, GEN y) {
    1746                 :       1835 :   GEN z = cgetg(4,t_QUAD);
    1747                 :       1835 :   GEN p1, p2, p3, p4, P = gel(x,1), b = gel(P,3), c = gel(P,2);
    1748                 :            :   pari_sp av, tetpil;
    1749         [ -  + ]:       1835 :   if (!ZX_equal(P, gel(y,1))) pari_err_OP("*",x,y);
    1750                 :            : 
    1751                 :       1835 :   gel(z,1) = ZX_copy(P); av = avma;
    1752                 :       1835 :   p2 = gmul(gel(x,2),gel(y,2));
    1753                 :       1835 :   p3 = gmul(gel(x,3),gel(y,3));
    1754                 :       1835 :   p1 = gmul(gneg_i(c),p3);
    1755                 :            : 
    1756         [ +  + ]:       1835 :   if (signe(b))
    1757                 :       1760 :     p4 = gadd(gmul(gel(x,2),gel(y,3)), gmul(gel(x,3),gel(y,2)));
    1758                 :            :   else
    1759                 :            :   {
    1760                 :         75 :     p3 = gmul(gel(x,2),gel(y,3));
    1761                 :         75 :     p4 = gmul(gel(x,3),gel(y,2));
    1762                 :            :   }
    1763                 :       1835 :   tetpil = avma;
    1764                 :       1835 :   gel(z,2) = gadd(p2,p1);
    1765                 :       1835 :   gel(z,3) = gadd(p4,p3);
    1766                 :       1835 :   gerepilecoeffssp(av,tetpil,z+2,2); return z;
    1767                 :            : }
    1768                 :            : 
    1769                 :            : GEN
    1770                 :    1155641 : mulcxI(GEN x)
    1771                 :            : {
    1772                 :            :   GEN z;
    1773      [ +  +  + ]:    1155641 :   switch(typ(x))
    1774                 :            :   {
    1775                 :            :     case t_INT: case t_REAL: case t_FRAC:
    1776                 :     286672 :       return mkcomplex(gen_0, x);
    1777                 :            :     case t_COMPLEX:
    1778         [ +  + ]:     868929 :       if (isintzero(gel(x,1))) return gneg(gel(x,2));
    1779                 :     867404 :       z = cgetg(3,t_COMPLEX);
    1780                 :     867404 :       gel(z,1) = gneg(gel(x,2));
    1781                 :     867404 :       gel(z,2) = gel(x,1); return z;
    1782                 :            :     default:
    1783                 :    1155641 :       return gmul(gen_I(), x);
    1784                 :            :   }
    1785                 :            : }
    1786                 :            : GEN
    1787                 :      33475 : mulcxmI(GEN x)
    1788                 :            : {
    1789                 :            :   GEN z;
    1790      [ +  +  + ]:      33475 :   switch(typ(x))
    1791                 :            :   {
    1792                 :            :     case t_INT: case t_REAL: case t_FRAC:
    1793                 :       1415 :       return mkcomplex(gen_0, gneg(x));
    1794                 :            :     case t_COMPLEX:
    1795         [ +  + ]:      32020 :       if (isintzero(gel(x,1))) return gel(x,2);
    1796                 :      31335 :       z = cgetg(3,t_COMPLEX);
    1797                 :      31335 :       gel(z,1) = gel(x,2);
    1798                 :      31335 :       gel(z,2) = gneg(gel(x,1)); return z;
    1799                 :            :     default:
    1800                 :      33475 :       return gmul(mkcomplex(gen_0, gen_m1), x);
    1801                 :            :   }
    1802                 :            : }
    1803                 :            : 
    1804                 :            : /* fill in coefficients of t_SER z from coeffs of t_POL y */
    1805                 :            : static GEN
    1806                 :      98562 : fill_ser(GEN z, GEN y)
    1807                 :            : {
    1808                 :      98562 :   long i, lx = lg(z), ly = lg(y);
    1809         [ +  + ]:      98562 :   if (ly >= lx) {
    1810         [ +  + ]:     448879 :     for (i = 2; i < lx; i++) gel(z,i) = gel(y,i);
    1811                 :            :   } else {
    1812         [ +  + ]:      11305 :     for (i = 2; i < ly; i++) gel(z,i) = gel(y,i);
    1813         [ +  + ]:       8840 :     for (     ; i < lx; i++) gel(z,i) = gen_0;
    1814                 :            :   }
    1815                 :      98562 :   return normalize(z);
    1816                 :            : }
    1817                 :            : 
    1818                 :            : GEN
    1819                 : 1543632064 : gmul(GEN x, GEN y)
    1820                 :            : {
    1821                 :            :   long tx, ty, lx, ly, vx, vy, i, l;
    1822                 :            :   pari_sp av, tetpil;
    1823                 :            :   GEN z, p1, p2;
    1824                 :            : 
    1825         [ +  + ]: 1543632064 :   if (x == y) return gsqr(x);
    1826                 :  950349942 :   tx = typ(x); ty = typ(y);
    1827 [ +  + ][ +  +  :  950349942 :   if (tx == ty) switch(tx)
          +  +  +  +  +  
          +  +  +  +  +  
             +  +  +  -  
                      - ]
    1828                 :            :   {
    1829                 :  468367941 :     case t_INT: return mulii(x,y);
    1830                 :  258214388 :     case t_REAL: return mulrr(x,y);
    1831                 :    1083414 :     case t_INTMOD: { GEN X = gel(x,1), Y = gel(y,1);
    1832                 :    1083414 :       z = cgetg(3,t_INTMOD);
    1833 [ +  - ][ +  - ]:    1083414 :       if (X==Y || equalii(X,Y))
    1834                 :    1083414 :         return mul_intmod_same(z, X, gel(x,2), gel(y,2));
    1835                 :          0 :       gel(z,1) = gcdii(X,Y); av = avma; p1 = mulii(gel(x,2),gel(y,2));
    1836                 :          0 :       gel(z,2) = gerepileuptoint(av, remii(p1, gel(z,1))); return z;
    1837                 :            :     }
    1838                 :            :     case t_FRAC:
    1839                 :            :     {
    1840                 :    1547700 :       GEN x1 = gel(x,1), x2 = gel(x,2);
    1841                 :    1547700 :       GEN y1 = gel(y,1), y2 = gel(y,2);
    1842                 :    1547700 :       z=cgetg(3,t_FRAC);
    1843                 :    1547700 :       p1 = gcdii(x1, y2);
    1844         [ +  + ]:    1547700 :       if (!is_pm1(p1)) { x1 = diviiexact(x1,p1); y2 = diviiexact(y2,p1); }
    1845                 :    1547700 :       p1 = gcdii(x2, y1);
    1846         [ +  + ]:    1547700 :       if (!is_pm1(p1)) { x2 = diviiexact(x2,p1); y1 = diviiexact(y1,p1); }
    1847                 :    1547700 :       tetpil = avma;
    1848                 :    1547700 :       gel(z,2) = mulii(x2,y2);
    1849                 :    1547700 :       gel(z,1) = mulii(x1,y1);
    1850         [ +  + ]:    1547700 :       fix_frac_if_int_GC(z,tetpil); return z;
    1851                 :            :     }
    1852                 :   35680596 :     case t_COMPLEX: return mulcc(x, y);
    1853                 :     179830 :     case t_PADIC: return mulpp(x, y);
    1854                 :       1390 :     case t_QUAD: return mulqq(x, y);
    1855                 :     545370 :     case t_FFELT: return FF_mul(x, y);
    1856                 :            :     case t_POLMOD:
    1857         [ +  + ]:     267765 :       if (RgX_equal_var(gel(x,1), gel(y,1)))
    1858                 :     267760 :         return mul_polmod_same(gel(x,1), gel(x,2), gel(y,2));
    1859                 :          5 :       return mul_polmod(gel(x,1), gel(y,1), gel(x,2), gel(y,2));
    1860                 :            :     case t_POL:
    1861                 :   23943929 :       vx = varn(x);
    1862                 :   23943929 :       vy = varn(y);
    1863         [ +  + ]:   23943929 :       if (vx != vy) {
    1864         [ +  + ]:    3481361 :         if (varncmp(vx, vy) < 0) return RgX_Rg_mul(x, y);
    1865                 :    1432406 :         else                     return RgX_Rg_mul(y, x);
    1866                 :            :       }
    1867 [ +  + ][ +  + ]:   20462568 :       if (RgX_is_ZX(x) && RgX_is_ZX(y)) return ZX_mul(x,y);
    1868                 :    3622219 :       return RgX_mul(x, y);
    1869                 :            : 
    1870                 :            :     case t_SER: {
    1871                 :      98677 :       GEN p = NULL;
    1872                 :      98677 :       vx = varn(x);
    1873                 :      98677 :       vy = varn(y);
    1874         [ -  + ]:      98677 :       if (vx != vy) {
    1875         [ #  # ]:          0 :         if (varncmp(vx, vy) < 0) return mul_ser_scal(x, y);
    1876                 :          0 :         else                     return mul_ser_scal(y, x);
    1877                 :            :       }
    1878                 :      98677 :       lx = lg(x);
    1879         [ +  + ]:      98677 :       ly = lg(y); if (lx > ly) { lx = ly; swap(x, y); }
    1880         [ +  + ]:      98677 :       if (lx == 2) return zeroser(vx, valp(x)+valp(y));
    1881                 :      98557 :       z = cgetg(lx,t_SER);
    1882                 :      98557 :       z[1] = evalvalp(valp(x)+valp(y)) | evalvarn(vx) | evalsigne(1);
    1883                 :      98557 :       x = ser2pol_i(x, lx);
    1884                 :      98557 :       y = ser2pol_i(y, lx);
    1885 [ +  + ][ +  + ]:      98557 :       if (RgX_is_FpX(x,&p) && RgX_is_FpX(y,&p))
    1886                 :            :       {
    1887         [ +  + ]:      12217 :         if (!p) y = ZX_mul(x,y);
    1888                 :            :         else
    1889                 :            :         {
    1890                 :       2955 :           x = RgX_to_FpX(x, p);
    1891                 :       2955 :           y = RgX_to_FpX(y, p);
    1892                 :       2955 :           y = FpX_to_mod(ZX_mul(x,y), p);
    1893                 :            :         }
    1894                 :            :       }
    1895                 :            :       else
    1896                 :      89295 :         y = RgXn_mul(x, y, lx-2);
    1897                 :      98557 :       z = fill_ser(z, y);
    1898                 :      98677 :       return gerepilecopy((pari_sp)(z + lx), z);
    1899                 :            :     }
    1900                 :      26790 :     case t_QFI: return qficomp(x,y);
    1901                 :          5 :     case t_QFR: return qfrcomp(x,y);
    1902                 :    4723674 :     case t_RFRAC: return mul_rfrac(gel(x,1),gel(x,2), gel(y,1),gel(y,2));
    1903                 :      13947 :     case t_MAT: return RgM_mul(x, y);
    1904                 :            : 
    1905                 :            :     case t_VECSMALL: /* multiply as permutation. cf perm_mul */
    1906                 :          0 :       z = cgetg_copy(x, &l);
    1907         [ #  # ]:          0 :       if (l != lg(y)) break;
    1908         [ #  # ]:          0 :       for (i=1; i<l; i++)
    1909                 :            :       {
    1910                 :          0 :         long yi = y[i];
    1911 [ #  # ][ #  # ]:          0 :         if (yi < 1 || yi >= l) pari_err_TYPE2("*",x,y);
    1912                 :          0 :         z[i] = x[yi];
    1913                 :            :       }
    1914                 :          0 :       return z;
    1915                 :            : 
    1916                 :            : 
    1917                 :            :     default:
    1918                 :          0 :       pari_err_TYPE2("*",x,y);
    1919                 :            :   }
    1920                 :            :   /* tx != ty */
    1921 [ +  + ][ +  + ]:  155654526 :   if (is_const_t(ty) && is_const_t(tx))  {
    1922         [ +  + ]:  110974617 :     if (tx > ty) { swap(x,y); lswap(tx,ty); }
    1923   [ +  +  +  +  :  110974617 :     switch(tx) {
             -  +  +  - ]
    1924                 :            :     case t_INT:
    1925   [ +  +  +  +  :   94490666 :       switch(ty)
             +  +  +  - ]
    1926                 :            :       {
    1927         [ +  + ]:   59922440 :         case t_REAL: return signe(x)? mulir(x,y): gen_0;
    1928                 :            :         case t_INTMOD:
    1929                 :    1241890 :           z = cgetg(3, t_INTMOD);
    1930                 :    1241890 :           return mul_intmod_same(z, gel(y,1), gel(y,2), modii(x, gel(y,1)));
    1931                 :            :         case t_FRAC:
    1932         [ +  + ]:   10855469 :           if (!signe(x)) return gen_0;
    1933                 :    6829695 :           z=cgetg(3,t_FRAC);
    1934                 :    6829695 :           p1 = gcdii(x,gel(y,2));
    1935         [ +  + ]:    6829695 :           if (is_pm1(p1))
    1936                 :            :           {
    1937                 :    4047629 :             avma = (pari_sp)z;
    1938                 :    4047629 :             gel(z,2) = icopy(gel(y,2));
    1939                 :    4047629 :             gel(z,1) = mulii(gel(y,1), x);
    1940                 :            :           }
    1941                 :            :           else
    1942                 :            :           {
    1943                 :    2782066 :             x = diviiexact(x,p1); tetpil = avma;
    1944                 :    2782066 :             gel(z,2) = diviiexact(gel(y,2), p1);
    1945                 :    2782066 :             gel(z,1) = mulii(gel(y,1), x);
    1946         [ +  + ]:    2782066 :             fix_frac_if_int_GC(z,tetpil);
    1947                 :            :           }
    1948                 :    6829695 :           return z;
    1949         [ +  + ]:   22373978 :         case t_COMPLEX: return signe(x)? mulRc(x, y): gen_0;
    1950         [ +  + ]:      24505 :         case t_PADIC: return signe(x)? mulTp(x, y): gen_0;
    1951                 :       1525 :         case t_QUAD: return mulRq(x,y);
    1952                 :      70859 :         case t_FFELT: return FF_Z_mul(y,x);
    1953                 :            :       }
    1954                 :            : 
    1955                 :            :     case t_REAL:
    1956   [ +  +  +  + ]:   16428500 :       switch(ty)
    1957                 :            :       {
    1958                 :     704485 :         case t_FRAC: return mulrfrac(x, y);
    1959                 :   15724005 :         case t_COMPLEX: return mulRc(x, y);
    1960                 :          5 :         case t_QUAD: return mulqf(y, x, lg(x));
    1961                 :          5 :         default: pari_err_TYPE2("*",x,y);
    1962                 :            :       }
    1963                 :            : 
    1964                 :            :     case t_INTMOD:
    1965   [ +  +  -  +  :       3591 :       switch(ty)
                   +  - ]
    1966                 :            :       {
    1967                 :        335 :         case t_FRAC: { GEN X = gel(x,1);
    1968                 :        335 :           z = cgetg(3, t_INTMOD); p1 = Fp_mul(gel(y,1), gel(x,2), X);
    1969                 :        335 :           return div_intmod_same(z, X, p1, remii(gel(y,2), X));
    1970                 :            :         }
    1971                 :         25 :         case t_COMPLEX: return mulRc_direct(x,y);
    1972                 :          0 :         case t_PADIC: { GEN X = gel(x,1);
    1973                 :          0 :           z = cgetg(3, t_INTMOD);
    1974                 :          0 :           return mul_intmod_same(z, X, gel(x,2), padic_to_Fp(y, X));
    1975                 :            :         }
    1976                 :         30 :         case t_QUAD: return mulRq(x, y);
    1977                 :            :         case t_FFELT:
    1978         [ -  + ]:       3201 :           if (!equalii(gel(x,1),FF_p_i(y)))
    1979                 :          0 :             pari_err_OP("*",x,y);
    1980                 :       3201 :           return FF_Z_mul(y,gel(x,2));
    1981                 :            :       }
    1982                 :            : 
    1983                 :            :     case t_FRAC:
    1984   [ +  +  +  +  :      51835 :       switch(ty)
                      - ]
    1985                 :            :       {
    1986                 :      48415 :         case t_COMPLEX: return mulRc(x, y);
    1987         [ +  - ]:       1580 :         case t_PADIC: return signe(gel(x,1))? mulTp(x, y): gen_0;
    1988                 :        570 :         case t_QUAD:  return mulRq(x, y);
    1989                 :       1270 :         case t_FFELT: return FF_Z_Z_muldiv(y, gel(x,1),gel(x,2));
    1990                 :            :       }
    1991                 :            : 
    1992                 :            :     case t_FFELT:
    1993                 :          0 :       pari_err_TYPE2("*",x,y);
    1994                 :            : 
    1995                 :            :     case t_COMPLEX:
    1996      [ +  +  - ]:         10 :       switch(ty)
    1997                 :            :       {
    1998                 :            :         case t_PADIC:
    1999         [ -  + ]:          5 :           return Zp_nosquare_m1(gel(y,2))? mulRc(y, x): mulTp(x, y);
    2000                 :            :         case t_QUAD:
    2001         [ -  + ]:          5 :           lx = precision(x); if (!lx) pari_err_OP("*",x,y);
    2002                 :          5 :           return mulqf(y, x, lx);
    2003                 :            :       }
    2004                 :            : 
    2005                 :            :     case t_PADIC: /* ty == t_QUAD */
    2006         [ +  + ]:         15 :       return (kro_quad(y,gel(x,2))== -1)? mulRq(x, y): mulTp(y, x);
    2007                 :            :     }
    2008                 :            :   }
    2009                 :            : 
    2010         [ +  + ]:   44679909 :   if (is_matvec_t(ty))
    2011                 :            :   {
    2012         [ +  + ]:    5050013 :     if (!is_matvec_t(tx))
    2013                 :            :     {
    2014         [ -  + ]:    4878285 :       if (is_noncalc_t(tx)) pari_err_TYPE2( "*",x,y); /* necessary if ly = 1 */
    2015                 :    4878285 :       z = cgetg_copy(y, &ly);
    2016         [ +  + ]:   87735283 :       for (i=1; i<ly; i++) gel(z,i) = gmul(x,gel(y,i));
    2017                 :    4878285 :       return z;
    2018                 :            :     }
    2019   [ +  +  +  - ]:     171728 :     switch(tx)
    2020                 :            :     {
    2021                 :            :       case t_VEC:
    2022      [ +  +  - ]:     117106 :         switch(ty) {
    2023                 :     105781 :           case t_COL: return RgV_RgC_mul(x,y);
    2024                 :      11325 :           case t_MAT: return RgV_RgM_mul(x,y);
    2025                 :            :         }
    2026                 :          0 :         break;
    2027                 :            :       case t_COL:
    2028      [ +  -  - ]:         10 :         switch(ty) {
    2029                 :         10 :           case t_VEC: return RgC_RgV_mul(x,y);
    2030                 :          0 :           case t_MAT: return RgC_RgM_mul(x,y);
    2031                 :            :         }
    2032                 :          0 :         break;
    2033                 :            :       case t_MAT:
    2034      [ -  +  - ]:      54612 :         switch(ty) {
    2035                 :          0 :           case t_VEC: return RgM_RgV_mul(x,y);
    2036                 :      54612 :           case t_COL: return RgM_RgC_mul(x,y);
    2037                 :            :         }
    2038                 :            :     }
    2039                 :            :   }
    2040         [ +  + ]:   39629896 :   if (is_matvec_t(tx))
    2041                 :            :   {
    2042         [ -  + ]:     141998 :     if (is_noncalc_t(ty)) pari_err_TYPE2( "*",x,y); /* necessary if lx = 1 */
    2043                 :     141998 :     z = cgetg_copy(x, &lx);
    2044         [ +  + ]:     721814 :     for (i=1; i<lx; i++) gel(z,i) = gmul(y,gel(x,i));
    2045                 :     141998 :     return z;
    2046                 :            :   }
    2047         [ +  + ]:   39487898 :   if (tx > ty) { swap(x,y); lswap(tx,ty); }
    2048                 :            :   /* tx < ty, !ismatvec(x and y) */
    2049                 :            : 
    2050         [ +  + ]:   39487898 :   if (ty == t_POLMOD) /* is_const_t(tx) in this case */
    2051                 :      34921 :     return mul_polmod_scal(gel(y,1), gel(y,2), x);
    2052         [ +  + ]:   39452977 :   if (is_scalar_t(tx)) {
    2053         [ +  + ]:   37402557 :     if (tx == t_POLMOD) {
    2054                 :      16067 :       vx = varn(gel(x,1));
    2055                 :      16067 :       vy = gvar(y);
    2056         [ +  + ]:      16067 :       if (vx != vy) {
    2057         [ +  + ]:       8567 :         if (varncmp(vx,vy) > 0) return mul_scal(y, x, ty);
    2058                 :         15 :         return mul_polmod_scal(gel(x,1), gel(x,2), y);
    2059                 :            :       }
    2060                 :            :       /* error if ty == t_SER */
    2061                 :       7500 :       av = avma; y = gmod(y, gel(x,1));
    2062                 :       7495 :       return gerepileupto(av, mul_polmod_same(gel(x,1), gel(x,2), y));
    2063                 :            :     }
    2064                 :   37386490 :     return mul_scal(y, x, ty);
    2065                 :            :   }
    2066                 :            : 
    2067                 :            :   /* x and y are not scalars, nor matvec */
    2068                 :    2050420 :   vx = gvar(x);
    2069                 :    2050420 :   vy = gvar(y);
    2070         [ +  + ]:    2050420 :   if (vx != vy) /* x or y is treated as a scalar */
    2071                 :    1028731 :     return (varncmp(vx, vy) < 0)? mul_scal(x, y, tx)
    2072         [ +  + ]:    1028731 :                                 : mul_scal(y, x, ty);
    2073                 :            :   /* vx = vy */
    2074      [ +  -  - ]:    1021689 :   switch(tx)
    2075                 :            :   {
    2076                 :            :     case t_POL:
    2077      [ +  +  - ]:    1021689 :       switch (ty)
    2078                 :            :       {
    2079                 :            :         case t_SER:
    2080                 :            :         {
    2081                 :            :           long vn;
    2082         [ -  + ]:      36825 :           if (lg(x) == 2) return zeropol(vx);
    2083         [ +  + ]:      36825 :           if (lg(y) == 2) return zeroser(vx, valp(y)+RgX_val(x));
    2084                 :      34965 :           av = avma;
    2085                 :      34965 :           vn = RgX_valrem(x, &x);
    2086                 :            :           /* take advantage of x = t^n ! */
    2087         [ +  + ]:      34965 :           if (degpol(x)) {
    2088                 :       1720 :             p1 = RgX_to_ser(x,lg(y));
    2089         [ -  + ]:       1720 :             if (vn) settyp(x, t_VECSMALL); /* *new* x left on stack */
    2090                 :       1720 :             p2 = gmul(p1,y);
    2091                 :       1720 :             settyp(p1, t_VECSMALL); /* p1 left on stack */
    2092                 :            :           } else {
    2093                 :      33245 :             avma = av;
    2094                 :      33245 :             p2 = mul_ser_scal(y, gel(x,2));
    2095                 :            :           }
    2096                 :      34965 :           setvalp(p2, valp(p2) + vn);
    2097                 :      34965 :           return p2;
    2098                 :            :         }
    2099                 :            : 
    2100                 :     984864 :         case t_RFRAC: return mul_rfrac_scal(gel(y,1),gel(y,2), x);
    2101                 :            :       }
    2102                 :          0 :       break;
    2103                 :            : 
    2104                 :            :     case t_SER:
    2105         [ #  # ]:          0 :       switch (ty)
    2106                 :            :       {
    2107                 :            :         case t_RFRAC:
    2108                 :          0 :           av = avma;
    2109                 :          0 :           return gerepileupto(av, gdiv(gmul(gel(y,1),x), gel(y,2)));
    2110                 :            :       }
    2111                 :          0 :       break;
    2112                 :            :   }
    2113                 :          0 :   pari_err_TYPE2("*",x,y);
    2114                 : 1543632044 :   return NULL; /* not reached */
    2115                 :            : }
    2116                 :            : 
    2117                 :            : int
    2118                 :      14110 : ff_poltype(GEN *x, GEN *p, GEN *pol)
    2119                 :            : {
    2120                 :      14110 :   GEN Q, P = *x;
    2121         [ +  + ]:      14110 :   if (!signe(P)) return 0;
    2122 [ +  + ][ +  + ]:      14040 :   if (!RgX_is_FpXQX(P,pol,p) || !*p || !*pol)
                 [ +  - ]
    2123                 :      14040 :     return 0;
    2124                 :          0 :   Q = RgX_to_FpX(*pol, *p);
    2125                 :          0 :   P = RgX_to_FpXQX(P, Q, *p);
    2126                 :          0 :   *x = ZXX_to_Kronecker(P, degpol(Q));
    2127                 :          0 :   *pol = Q;
    2128                 :      14110 :   return 1;
    2129                 :            : }
    2130                 :            : 
    2131                 :            : /* return a non-normalized result */
    2132                 :            : GEN
    2133                 :       4745 : sqr_ser_part(GEN x, long l1, long l2)
    2134                 :            : {
    2135                 :            :   long i, j, l;
    2136                 :            :   pari_sp av;
    2137                 :            :   GEN Z, z, p1, p2;
    2138                 :            :   long mi;
    2139         [ +  + ]:       4745 :   if (l2 < l1) return zeroser(varn(x), 2*valp(x));
    2140                 :       4740 :   p2 = cgetg(l2+2, t_VECSMALL)+1; /* left on stack on exit */
    2141                 :       4740 :   Z = cgetg(l2-l1+3, t_SER);
    2142                 :       4740 :   Z[1] = evalvalp(2*valp(x)) | evalvarn(varn(x));
    2143                 :       4740 :   z = Z + 2-l1;
    2144                 :       4740 :   x += 2; mi = 0;
    2145         [ +  + ]:     386220 :   for (i=0; i<l1; i++)
    2146                 :            :   {
    2147         [ +  + ]:     381480 :     p2[i] = !isrationalzero(gel(x,i)); if (p2[i]) mi = i;
    2148                 :            :   }
    2149                 :            : 
    2150         [ +  + ]:     410845 :   for (i=l1; i<=l2; i++)
    2151                 :            :   {
    2152         [ +  + ]:     406105 :     p2[i] = !isrationalzero(gel(x,i)); if (p2[i]) mi = i;
    2153                 :     406105 :     p1=gen_0; av=avma; l=((i+1)>>1) - 1;
    2154         [ +  + ]:  166539205 :     for (j=i-mi; j<=minss(l,mi); j++)
    2155 [ +  + ][ +  + ]:  166133100 :       if (p2[j] && p2[i-j]) p1 = gadd(p1, gmul(gel(x,j),gel(x,i-j)));
    2156                 :     406105 :     p1 = gshift(p1,1);
    2157 [ +  + ][ +  + ]:     406105 :     if ((i&1) == 0 && p2[i>>1])
    2158                 :      12435 :       p1 = gadd(p1, gsqr(gel(x,i>>1)));
    2159                 :     406105 :     gel(z,i) = gerepileupto(av,p1);
    2160                 :            :   }
    2161                 :       4745 :   return Z;
    2162                 :            : }
    2163                 :            : 
    2164                 :            : GEN
    2165                 :  611251701 : gsqr(GEN x)
    2166                 :            : {
    2167                 :            :   long i, lx;
    2168                 :            :   pari_sp av, tetpil;
    2169                 :            :   GEN z, p1, p2, p3, p4;
    2170                 :            : 
    2171   [ +  +  +  +  :  611251701 :   switch(typ(x))
          +  +  +  +  +  
          +  +  +  +  +  
                +  -  - ]
    2172                 :            :   {
    2173                 :  599866753 :     case t_INT: return sqri(x);
    2174                 :    8403852 :     case t_REAL: return sqrr(x);
    2175                 :     109400 :     case t_INTMOD: { GEN X = gel(x,1);
    2176                 :     109400 :       z = cgetg(3,t_INTMOD);
    2177                 :     109400 :       gel(z,2) = gerepileuptoint((pari_sp)z, remii(sqri(gel(x,2)), X));
    2178                 :     109400 :       gel(z,1) = icopy(X); return z;
    2179                 :            :     }
    2180                 :      75242 :     case t_FRAC: return sqrfrac(x);
    2181                 :            : 
    2182                 :            :     case t_COMPLEX:
    2183         [ +  + ]:    1793390 :       if (isintzero(gel(x,1))) {
    2184                 :      10379 :         av = avma;
    2185                 :      10379 :         return gerepileupto(av, gneg(gsqr(gel(x,2))));
    2186                 :            :       }
    2187                 :    1783011 :       z = cgetg(3,t_COMPLEX); av = avma;
    2188                 :    1783011 :       p1 = gadd(gel(x,1),gel(x,2));
    2189                 :    1783011 :       p2 = gsub(gel(x,1), gel(x,2));
    2190                 :    1783011 :       p3 = gmul(gel(x,1),gel(x,2));
    2191                 :    1783011 :       tetpil = avma;
    2192                 :    1783011 :       gel(z,1) = gmul(p1,p2);
    2193                 :    1783011 :       gel(z,2) = gshift(p3,1); gerepilecoeffssp(av,tetpil,z+1,2); return z;
    2194                 :            : 
    2195                 :            :     case t_PADIC:
    2196                 :       1320 :       z = cgetg(5,t_PADIC);
    2197 [ +  + ][ +  - ]:       1320 :       i = (equaliu(gel(x,2), 2) && signe(gel(x,4)))? 1: 0;
    2198 [ +  + ][ +  + ]:       1320 :       if (i && precp(x) == 1) i = 2; /* (1 + O(2))^2 = 1 + O(2^3) */
    2199                 :       1320 :       z[1] = evalprecp(precp(x)+i) | evalvalp(valp(x) << 1);
    2200                 :       1320 :       gel(z,2) = icopy(gel(x,2));
    2201                 :       1320 :       gel(z,3) = shifti(gel(x,3), i); av = avma;
    2202                 :       1320 :       gel(z,4) = gerepileuptoint(av, remii(sqri(gel(x,4)), gel(z,3)));
    2203                 :       1320 :       return z;
    2204                 :            : 
    2205                 :         35 :     case t_QUAD: z = cgetg(4,t_QUAD);
    2206                 :         35 :       p1 = gel(x,1);
    2207                 :         35 :       gel(z,1) = ZX_copy(p1); av = avma;
    2208                 :         35 :       p2 = gsqr(gel(x,2));
    2209                 :         35 :       p3 = gsqr(gel(x,3));
    2210                 :         35 :       p4 = gmul(gneg_i(gel(p1,2)),p3);
    2211                 :            : 
    2212         [ +  + ]:         35 :       if (gequal0(gel(p1,3)))
    2213                 :            :       {
    2214                 :          5 :         tetpil = avma;
    2215                 :          5 :         gel(z,2) = gerepile(av,tetpil,gadd(p4,p2));
    2216                 :          5 :         av = avma;
    2217                 :          5 :         p2 = gmul(gel(x,2),gel(x,3)); tetpil = avma;
    2218                 :          5 :         gel(z,3) = gerepile(av,tetpil,gmul2n(p2,1)); return z;
    2219                 :            :       }
    2220                 :            : 
    2221                 :         30 :       p1 = gmul2n(gmul(gel(x,2),gel(x,3)), 1);
    2222                 :         30 :       tetpil = avma;
    2223                 :         30 :       gel(z,2) = gadd(p2,p4);
    2224                 :         30 :       gel(z,3) = gadd(p1,p3);
    2225                 :         30 :       gerepilecoeffssp(av,tetpil,z+2,2); return z;
    2226                 :            : 
    2227                 :            :     case t_POLMOD:
    2228                 :      10686 :       return sqr_polmod(gel(x,1), gel(x,2));
    2229                 :            : 
    2230                 :     204595 :     case t_FFELT: return FF_sqr(x);
    2231                 :            : 
    2232                 :            :     case t_POL:
    2233                 :            :     {
    2234                 :     715878 :       GEN a = x, p = NULL, pol = NULL;
    2235                 :     715878 :       av = avma;
    2236         [ +  + ]:     715878 :       if (RgX_is_ZX(x)) return ZX_sqr(x);
    2237         [ -  + ]:      14110 :       if (ff_poltype(&x,&p,&pol))
    2238                 :            :       {
    2239                 :          0 :         z = ZX_sqr(x);
    2240         [ #  # ]:          0 :         if (p) z = FpX_to_mod(z,p);
    2241         [ #  # ]:          0 :         if (pol) z = Kronecker_to_mod(z,pol);
    2242                 :          0 :         z = gerepileupto(av, z);
    2243                 :            :       }
    2244                 :      14110 :       else { avma = av; z = RgX_sqr(a); }
    2245                 :     715878 :       return z;
    2246                 :            :     }
    2247                 :            : 
    2248                 :            :     case t_SER:
    2249                 :       2535 :       lx = lg(x);
    2250         [ +  + ]:       2535 :       if (ser_isexactzero(x)) {
    2251                 :          5 :         GEN z = gcopy(x);
    2252                 :          5 :         setvalp(z, 2*valp(x));
    2253                 :          5 :         return z;
    2254                 :            :       }
    2255         [ +  + ]:       2530 :       if (lx < 40)
    2256                 :       2525 :         return normalize( sqr_ser_part(x, 0, lx-3) );
    2257                 :            :       else
    2258                 :            :       {
    2259                 :          5 :         pari_sp av = avma;
    2260                 :          5 :         GEN z = cgetg(lx,t_SER), p = NULL;
    2261                 :          5 :         z[1] = evalvalp(2*valp(x)) | evalvarn(varn(x)) | evalsigne(1);
    2262                 :          5 :         x = ser2pol_i(x,lx);
    2263         [ +  - ]:          5 :         if (RgX_is_FpX(x,&p))
    2264                 :            :         {
    2265         [ +  - ]:          5 :           if (!p) x = ZX_sqr(x);
    2266                 :            :           else
    2267                 :            :           {
    2268                 :          0 :             x = RgX_to_FpX(x, p);
    2269                 :          0 :             x = FpX_to_mod(ZX_sqr(x), p);
    2270                 :            :           }
    2271                 :            :         }
    2272                 :            :         else
    2273                 :          0 :           x = RgXn_sqr(x, lx-2);
    2274                 :          5 :         z = fill_ser(z, x);
    2275                 :          5 :         return gerepilecopy(av, z);
    2276                 :            :       }
    2277                 :            : 
    2278                 :        165 :     case t_RFRAC: z = cgetg(3,t_RFRAC);
    2279                 :        165 :       gel(z,1) = gsqr(gel(x,1));
    2280                 :        165 :       gel(z,2) = gsqr(gel(x,2)); return z;
    2281                 :            : 
    2282                 :        175 :     case t_MAT: return RgM_sqr(x);
    2283                 :         10 :     case t_QFR: return qfrsqr(x);
    2284                 :      67665 :     case t_QFI: return qfisqr(x);
    2285                 :            :     case t_VECSMALL:
    2286                 :          0 :       z = cgetg_copy(x, &lx);
    2287         [ #  # ]:          0 :       for (i=1; i<lx; i++)
    2288                 :            :       {
    2289                 :          0 :         long xi = x[i];
    2290 [ #  # ][ #  # ]:          0 :         if (xi < 1 || xi >= lx) pari_err_TYPE2("*",x,x);
    2291                 :          0 :         z[i] = x[xi];
    2292                 :            :       }
    2293                 :          0 :       return z;
    2294                 :            :   }
    2295                 :          0 :   pari_err_TYPE2("*",x,x);
    2296                 :  611251701 :   return NULL; /* not reached */
    2297                 :            : }
    2298                 :            : 
    2299                 :            : /********************************************************************/
    2300                 :            : /**                                                                **/
    2301                 :            : /**                           DIVISION                             **/
    2302                 :            : /**                                                                **/
    2303                 :            : /********************************************************************/
    2304                 :            : static GEN
    2305                 :     205876 : div_rfrac_scal(GEN x, GEN y)
    2306                 :            : {
    2307                 :     205876 :   pari_sp av = avma;
    2308                 :     205876 :   GEN d = rfrac_denom_mul_scal(gel(x,2), y);
    2309                 :     205876 :   return gerepileupto(av, gred_rfrac_simple(gel(x,1), d));
    2310                 :            : }
    2311                 :            : static GEN
    2312                 :     725548 : div_scal_rfrac(GEN x, GEN y)
    2313                 :            : {
    2314                 :     725548 :   GEN y1 = gel(y,1), y2 = gel(y,2);
    2315                 :     725548 :   pari_sp av = avma;
    2316 [ +  + ][ +  + ]:     725548 :   if (typ(y1) == t_POL && varn(y2) == varn(y1) && degpol(y1) > 0)
                 [ -  + ]
    2317                 :          0 :     return gerepileupto(av, gred_rfrac_simple(gmul(x, y2), y1));
    2318                 :     725548 :   return RgX_Rg_mul(y2, gdiv(x,y1));
    2319                 :            : }
    2320                 :            : static GEN
    2321                 :     874521 : div_rfrac(GEN x, GEN y)
    2322                 :     874521 : { return mul_rfrac(gel(x,1),gel(x,2), gel(y,2),gel(y,1)); }
    2323                 :            : 
    2324                 :            : static GEN
    2325                 :       3480 : div_ser_scal(GEN x, GEN y) {
    2326                 :            :   long i, lx;
    2327                 :            :   GEN z;
    2328         [ -  + ]:       3480 :   if (ser_isexactzero(x))
    2329                 :            :   {
    2330         [ #  # ]:          0 :     if (lg(y) == 2) return gcopy(y);
    2331                 :          0 :     return scalarser(gdiv(gel(x,2), y), varn(x), valp(x));
    2332                 :            :   }
    2333                 :       3480 :   z = cgetg_copy(x, &lx); z[1] = x[1];
    2334         [ +  + ]:      25440 :   for (i=2; i<lx; i++) gel(z,i) = gdiv(gel(x,i),y);
    2335                 :       3480 :   return normalize(z);
    2336                 :            : }
    2337                 :            : GEN
    2338                 :         45 : ser_normalize(GEN x)
    2339                 :            : {
    2340                 :         45 :   long i, lx = lg(x);
    2341                 :            :   GEN c, z;
    2342         [ -  + ]:         45 :   if (lx == 2) return x;
    2343         [ +  + ]:         45 :   c = gel(x,2); if (gequal1(c)) return x;
    2344                 :         20 :   z = cgetg(lx, t_SER); z[1] = x[1]; gel(z,2) = gen_1;
    2345         [ +  + ]:        105 :   for (i=3; i<lx; i++) gel(z,i) = gdiv(gel(x,i),c);
    2346                 :         45 :   return z;
    2347                 :            : }
    2348                 :            : 
    2349                 :            : static GEN
    2350                 :     561384 : div_T_scal(GEN x, GEN y, long tx) {
    2351   [ +  +  +  - ]:     561384 :   switch(tx)
    2352                 :            :   {
    2353                 :     354688 :     case t_POL: return RgX_Rg_div(x, y);
    2354                 :       3480 :     case t_SER: return div_ser_scal(x, y);
    2355                 :     203216 :     case t_RFRAC: return div_rfrac_scal(x,y);
    2356                 :            :   }
    2357                 :          0 :   pari_err_TYPE2("/",x,y);
    2358                 :     561384 :   return NULL; /* not reached */
    2359                 :            : }
    2360                 :            : 
    2361                 :            : static GEN
    2362                 :    5918765 : div_scal_pol(GEN x, GEN y) {
    2363                 :    5918765 :   long ly = lg(y);
    2364                 :            :   pari_sp av;
    2365         [ +  + ]:    5918765 :   if (ly == 3) return scalarpol(gdiv(x,gel(y,2)), varn(y));
    2366         [ +  + ]:    5887387 :   if (isrationalzero(x)) return zeropol(varn(y));
    2367                 :    4375332 :   av = avma;
    2368                 :    5918765 :   return gerepileupto(av, gred_rfrac_simple(x,y));
    2369                 :            : }
    2370                 :            : static GEN
    2371                 :        410 : div_scal_ser(GEN x, GEN y) { /* TODO: improve */
    2372                 :            :   GEN z;
    2373                 :            :   long ly, i;
    2374         [ -  + ]:        410 :   if (gequal0(x)) { pari_sp av=avma; return gerepileupto(av, gmul(x, ginv(y))); }
    2375                 :        410 :   ly = lg(y); z = (GEN)pari_malloc(ly*sizeof(long));
    2376                 :        410 :   z[0] = evaltyp(t_SER) | evallg(ly);
    2377                 :        410 :   z[1] = evalsigne(1) | _evalvalp(0) | evalvarn(varn(y));
    2378         [ +  + ]:       4895 :   gel(z,2) = x; for (i=3; i<ly; i++) gel(z,i) = gen_0;
    2379                 :        410 :   y = gdiv(z,y); pari_free(z); return y;
    2380                 :            : }
    2381                 :            : static GEN
    2382                 :    6612188 : div_scal_T(GEN x, GEN y, long ty) {
    2383   [ +  +  +  - ]:    6612188 :   switch(ty)
    2384                 :            :   {
    2385                 :    5886770 :     case t_POL: return div_scal_pol(x, y);
    2386                 :        410 :     case t_SER: return div_scal_ser(x, y);
    2387                 :     725008 :     case t_RFRAC: return div_scal_rfrac(x, y);
    2388                 :            :   }
    2389                 :          0 :   pari_err_TYPE2("/",x,y);
    2390                 :    6612188 :   return NULL; /* not reached */
    2391                 :            : }
    2392                 :            : 
    2393                 :            : /* assume tx = ty = t_SER, same variable vx */
    2394                 :            : static GEN
    2395                 :     192950 : div_ser(GEN x, GEN y, long vx)
    2396                 :            : {
    2397                 :     192950 :   long i, j, l = valp(x) - valp(y), lx = lg(x), ly = lg(y);
    2398                 :            :   GEN y_lead, p1, p2, z;
    2399                 :            : 
    2400         [ -  + ]:     192950 :   if (!signe(y)) pari_err_INV("div_ser", y);
    2401         [ +  + ]:     192950 :   if (ser_isexactzero(x))
    2402                 :            :   {
    2403         [ +  + ]:        895 :     if (lx == 2) return zeroser(vx, l);
    2404                 :          5 :     return scalarser(gmul(gel(x,2),RgX_get_0(y)), varn(x), l);
    2405                 :            :   }
    2406                 :     192055 :   y_lead = gel(y,2);
    2407         [ +  + ]:     192055 :   if (gequal0(y_lead)) /* normalize denominator if leading term is 0 */
    2408                 :            :   {
    2409                 :         10 :     pari_warn(warner,"normalizing a series with 0 leading term");
    2410         [ +  - ]:         10 :     for (l--, ly--,y++; ly > 2; l--, ly--, y++)
    2411                 :            :     {
    2412                 :         10 :       y_lead = gel(y,2);
    2413         [ +  - ]:         10 :       if (!gequal0(y_lead)) break;
    2414                 :            :     }
    2415         [ -  + ]:         10 :     if (ly <= 2) pari_err_INV("div_ser", y);
    2416                 :            :   }
    2417         [ +  + ]:     192055 :   if (ly < lx) lx = ly;
    2418                 :     192055 :   p2 = cgetg(lx, t_VECSMALL); /* left on stack for efficiency */
    2419         [ +  + ]:     921315 :   for (i=3; i<lx; i++)
    2420                 :            :   {
    2421                 :     729260 :     p1 = gel(y,i);
    2422         [ +  + ]:     729260 :     if (isrationalzero(p1)) p1 = NULL;
    2423                 :     729260 :     gel(p2,i) = p1;
    2424                 :            :   }
    2425                 :     192055 :   z = cgetg(lx,t_SER);
    2426                 :     192055 :   z[1] = evalvalp(l) | evalvarn(vx) | evalsigne(1);
    2427                 :     192055 :   gel(z,2) = gdiv(gel(x,2), y_lead);
    2428         [ +  + ]:     921315 :   for (i=3; i<lx; i++)
    2429                 :            :   {
    2430                 :     729260 :     pari_sp av = avma;
    2431                 :     729260 :     p1 = gel(x,i);
    2432         [ +  + ]: 1744423735 :     for (j=2, l=i; j<i; j++, l--)
    2433         [ +  + ]: 1743694475 :       if (p2[l]) p1 = gsub(p1, gmul(gel(z,j), gel(p2,l)));
    2434                 :     729260 :     gel(z,i) = gerepileupto(av, gdiv(p1, y_lead));
    2435                 :            :   }
    2436                 :     192950 :   return normalize(z);
    2437                 :            : }
    2438                 :            : /* x,y compatible PADIC */
    2439                 :            : static GEN
    2440                 :      28395 : divpp(GEN x, GEN y) {
    2441                 :            :   pari_sp av;
    2442                 :            :   long a, b;
    2443                 :            :   GEN z, M;
    2444                 :            : 
    2445         [ +  + ]:      28395 :   if (!signe(gel(y,4))) pari_err_INV("divpp",y);
    2446         [ +  + ]:      28390 :   if (!signe(gel(x,4))) return zeropadic(gel(x,2), valp(x)-valp(y));
    2447                 :      28385 :   a = precp(x);
    2448         [ +  + ]:      28385 :   b = precp(y); if (a > b) { M = gel(y,3); } else { M = gel(x,3); b = a; }
    2449                 :      28385 :   z = cgetg(5, t_PADIC);
    2450                 :      28385 :   z[1] = _evalprecp(b) | evalvalp(valp(x) - valp(y));
    2451                 :      28385 :   gel(z,2) = icopy(gel(x,2));
    2452                 :      28385 :   gel(z,3) = icopy(M); av = avma;
    2453                 :      28385 :   gel(z,4) = gerepileuptoint(av, remii(mulii(gel(x,4), Fp_inv(gel(y,4), M)), M) );
    2454                 :      28390 :   return z;
    2455                 :            : }
    2456                 :            : static GEN
    2457                 :      13520 : div_polmod_same(GEN T, GEN x, GEN y)
    2458                 :            : {
    2459                 :      13520 :   long v = varn(T);
    2460                 :      13520 :   GEN a, z = cgetg(3, t_POLMOD);
    2461                 :      13520 :   gel(z,1) = RgX_copy(T);
    2462 [ +  + ][ +  - ]:      13520 :   if (typ(y) != t_POL || varn(y) != v || lg(y) <= 3)
                 [ +  + ]
    2463                 :       9900 :     a = gdiv(x, y);
    2464 [ +  + ][ +  - ]:       3620 :   else if (typ(x) != t_POL || varn(x) != v || lg(x) <= 3)
                 [ +  + ]
    2465                 :       2745 :   {
    2466                 :       2745 :     pari_sp av = avma;
    2467                 :       2745 :     a = gerepileupto(av, gmul(x, RgXQ_inv(y, T)));
    2468                 :            :   }
    2469 [ +  + ][ +  + ]:        875 :   else if (degpol(T) == 2 && isint1(gel(T,4))) /* quadratic fields */
    2470                 :        630 :   {
    2471                 :        630 :     pari_sp av = avma;
    2472                 :        630 :     a = quad_polmod_mul(T, x, quad_polmod_conj(y, T));
    2473                 :        630 :     a = RgX_Rg_div(a, quad_polmod_norm(y, T));
    2474                 :        630 :     a = gerepileupto(av, a);
    2475                 :            :   }
    2476                 :            :   else
    2477                 :            :   {
    2478                 :        245 :     pari_sp av = avma;
    2479                 :        245 :     GEN p = NULL;
    2480 [ +  - ][ +  + ]:        245 :     if (RgX_is_FpX(T, &p) && RgX_is_FpX(x, &p) && RgX_is_FpX(y, &p) && p)
         [ +  - ][ +  + ]
    2481                 :            :     {
    2482                 :         70 :       T = RgX_to_FpX(T, p); x = RgX_to_FpX(x, p); y = RgX_to_FpX(y, p);
    2483         [ +  + ]:         70 :       if (lgefint(p) == 3)
    2484                 :            :       {
    2485                 :         65 :         ulong pp = p[2];
    2486                 :         65 :         x = ZX_to_Flx(x, pp);
    2487                 :         65 :         y = ZX_to_Flx(y, pp);
    2488                 :         65 :         T = ZX_to_Flx(T, pp);
    2489                 :         65 :         a = Flxq_mul(x, Flxq_inv(y,T,pp),T,pp);
    2490                 :         65 :         a = Flx_to_ZX(a);
    2491                 :            :       }
    2492                 :            :       else
    2493                 :          5 :         a = FpXQ_div(x, y, T, p);
    2494                 :         70 :       a = FpX_to_mod(a, p);
    2495                 :            :     } else
    2496                 :        175 :       a = RgXQ_mul(x, ginvmod(y, gel(z,1)), gel(z,1));
    2497                 :        245 :     a = gerepileupto(av, a);
    2498                 :            :   }
    2499                 :      13520 :   gel(z,2) = a; return z;
    2500                 :            : }
    2501                 :            : GEN
    2502                 :   62527182 : gdiv(GEN x, GEN y)
    2503                 :            : {
    2504                 :   62527182 :   long tx = typ(x), ty = typ(y), lx, ly, vx, vy, i;
    2505                 :            :   pari_sp av, tetpil;
    2506                 :            :   GEN z, p1, p2;
    2507                 :            : 
    2508 [ +  + ][ +  +  :   62527182 :   if (tx == ty) switch(tx)
          +  +  +  +  +  
          +  +  +  +  +  
             -  -  -  - ]
    2509                 :            :   {
    2510                 :            :     case t_INT:
    2511 [ +  + ][ +  + ]:   32447513 :       if (is_pm1(y)) return (signe(y) < 0)? negi(x): icopy(x);
    2512         [ +  + ]:   10555156 :       if (is_pm1(x)) {
    2513                 :    2425390 :         long s = signe(y);
    2514         [ +  + ]:    2425390 :         if (!s) pari_err_INV("gdiv",y);
    2515         [ +  + ]:    2425345 :         if (signe(x) < 0) s = -s;
    2516                 :    2425345 :         z = cgetg(3, t_FRAC);
    2517         [ +  + ]:    2425345 :         gel(z,1) = s<0? gen_m1: gen_1;
    2518                 :    2425345 :         gel(z,2) = absi(y); return z;
    2519                 :            :       }
    2520                 :    8129766 :       return gred_frac2(x,y);
    2521                 :            : 
    2522                 :    4072645 :     case t_REAL: return divrr(x,y);
    2523                 :      13845 :     case t_INTMOD: { GEN X = gel(x,1), Y = gel(y,1);
    2524                 :      13845 :       z = cgetg(3,t_INTMOD);
    2525 [ +  + ][ +  - ]:      13845 :       if (X==Y || equalii(X,Y))
    2526                 :      13845 :         return div_intmod_same(z, X, gel(x,2), gel(y,2));
    2527                 :          0 :       gel(z,1) = gcdii(X,Y); av = avma;
    2528                 :          0 :       p1 = mulii(gel(x,2), Fp_inv(gel(y,2), gel(z,1)));
    2529                 :          0 :       gel(z,2) = gerepileuptoint(av, remii(p1, gel(z,1))); return z;
    2530                 :            :     }
    2531                 :            :     case t_FRAC: {
    2532                 :     303542 :       GEN x1 = gel(x,1), x2 = gel(x,2);
    2533                 :     303542 :       GEN y1 = gel(y,1), y2 = gel(y,2);
    2534                 :     303542 :       z = cgetg(3, t_FRAC);
    2535                 :     303542 :       p1 = gcdii(x1, y1);
    2536         [ +  + ]:     303542 :       if (!is_pm1(p1)) { x1 = diviiexact(x1,p1); y1 = diviiexact(y1,p1); }
    2537                 :     303542 :       p1 = gcdii(x2, y2);
    2538         [ +  + ]:     303542 :       if (!is_pm1(p1)) { x2 = diviiexact(x2,p1); y2 = diviiexact(y2,p1); }
    2539                 :     303542 :       tetpil = avma;
    2540                 :     303542 :       gel(z,2) = mulii(x2,y1);
    2541                 :     303542 :       gel(z,1) = mulii(x1,y2);
    2542                 :     303542 :       normalize_frac(z);
    2543         [ +  + ]:     303542 :       fix_frac_if_int_GC(z,tetpil);
    2544                 :     303542 :       return z;
    2545                 :            :     }
    2546                 :            :     case t_COMPLEX:
    2547         [ +  + ]:     256434 :       if (isintzero(gel(y,1)))
    2548                 :            :       {
    2549                 :       5785 :         y = gel(y,2);
    2550         [ +  + ]:       5785 :         if (isintzero(gel(x,1))) return gdiv(gel(x,2), y);
    2551                 :       5745 :         z = cgetg(3,t_COMPLEX);
    2552                 :       5745 :         gel(z,1) = gdiv(gel(x,2), y);
    2553                 :       5745 :         av = avma;
    2554                 :       5745 :         gel(z,2) = gerepileupto(av, gneg(gdiv(gel(x,1), y)));
    2555                 :       5745 :         return z;
    2556                 :            :       }
    2557                 :     250649 :       av = avma; p1 = cxnorm(y); p2 = mulcc(x, gconj(y)); tetpil = avma;
    2558                 :     250649 :       return gerepile(av, tetpil, gdiv(p2,p1));
    2559                 :            : 
    2560                 :            :     case t_PADIC:
    2561         [ -  + ]:       1755 :       if (!equalii(gel(x,2),gel(y,2))) pari_err_OP("/",x,y);
    2562                 :       1755 :       return divpp(x, y);
    2563                 :            : 
    2564                 :            :     case t_QUAD:
    2565         [ -  + ]:        445 :       if (!ZX_equal(gel(x,1),gel(y,1))) pari_err_OP("/",x,y);
    2566                 :        445 :       av = avma; p1 = quadnorm(y); p2 = mulqq(x, gconj(y)); tetpil = avma;
    2567                 :        445 :       return gerepile(av, tetpil, gdiv(p2,p1));
    2568                 :            : 
    2569                 :      35705 :     case t_FFELT: return FF_div(x,y);
    2570                 :            : 
    2571                 :            :     case t_POLMOD:
    2572         [ +  - ]:      13520 :       if (RgX_equal_var(gel(x,1), gel(y,1)))
    2573                 :      13520 :         z = div_polmod_same(gel(x,1), gel(x,2), gel(y,2));
    2574                 :            :       else {
    2575                 :          0 :         av = avma;
    2576                 :          0 :         z = gerepileupto(av, gmul(x, ginv(y)));
    2577                 :            :       }
    2578                 :      13520 :       return z;
    2579                 :            : 
    2580                 :            :     case t_POL:
    2581                 :   13429335 :       vx = varn(x);
    2582                 :   13429335 :       vy = varn(y);
    2583         [ +  + ]:   13429335 :       if (vx != vy) {
    2584         [ +  + ]:      67900 :         if (varncmp(vx, vy) < 0) return RgX_Rg_div(x, y);
    2585                 :      31995 :                             else return div_scal_pol(x, y);
    2586                 :            :       }
    2587         [ -  + ]:   13361435 :       if (!signe(y)) pari_err_INV("gdiv",y);
    2588         [ +  + ]:   13361435 :       if (lg(y) == 3) return RgX_Rg_div(x,gel(y,2));
    2589                 :   13291019 :       return gred_rfrac2(x,y);
    2590                 :            : 
    2591                 :            :     case t_SER:
    2592                 :       5145 :       vx = varn(x);
    2593                 :       5145 :       vy = varn(y);
    2594         [ -  + ]:       5145 :       if (vx != vy) {
    2595         [ #  # ]:          0 :         if (varncmp(vx, vy) < 0) return div_ser_scal(x, y);
    2596                 :          0 :                             else return div_scal_ser(x, y);
    2597                 :            :       }
    2598                 :       5145 :       return div_ser(x, y, vx);
    2599                 :            :     case t_RFRAC:
    2600                 :     877721 :       vx = varn(gel(x,2));
    2601                 :     877721 :       vy = varn(gel(y,2));
    2602         [ +  + ]:     877721 :       if (vx != vy) {
    2603         [ +  + ]:       3200 :         if (varncmp(vx, vy) < 0) return div_rfrac_scal(x, y);
    2604                 :        540 :                             else return div_scal_rfrac(x, y);
    2605                 :            :       }
    2606                 :     874521 :       return div_rfrac(x,y);
    2607                 :            : 
    2608                 :          0 :     case t_QFI: av = avma; return gerepileupto(av, qficomp(x, ginv(y)));
    2609                 :          0 :     case t_QFR: av = avma; return gerepileupto(av, qfrcomp(x, ginv(y)));
    2610                 :            : 
    2611                 :            :     case t_MAT:
    2612                 :          0 :       av = avma; p1 = RgM_inv(y);
    2613         [ #  # ]:          0 :       if (!p1) pari_err_INV("gdiv",y);
    2614                 :          0 :       return gerepileupto(av, RgM_mul(x, p1));
    2615                 :            : 
    2616                 :          0 :     default: pari_err_TYPE2("/",x,y);
    2617                 :            :   }
    2618                 :            : 
    2619 [ +  + ][ +  + ]:   11069577 :   if (tx==t_INT && is_const_t(ty)) /* optimized for speed */
    2620                 :            :   {
    2621                 :     724211 :     long s = signe(x);
    2622         [ +  + ]:     724211 :     if (!s) {
    2623         [ -  + ]:      23078 :       if (gequal0(y)) pari_err_INV("gdiv",y);
    2624      [ +  +  + ]:      23078 :       switch (ty)
    2625                 :            :       {
    2626                 :      20833 :       default: return gen_0;
    2627                 :            :       case t_INTMOD:
    2628                 :         10 :         z = cgetg(3,t_INTMOD);
    2629                 :         10 :         gel(z,1) = icopy(gel(y,1));
    2630                 :         10 :         gel(z,2) = gen_0; return z;
    2631                 :       2235 :       case t_FFELT: return FF_zero(y);
    2632                 :            :       }
    2633                 :            :     }
    2634         [ +  + ]:     701133 :     if (is_pm1(x)) {
    2635         [ +  + ]:     383561 :       if (s > 0) return ginv(y);
    2636                 :      11861 :       av = avma; return gerepileupto(av, ginv(gneg(y)));
    2637                 :            :     }
    2638   [ +  +  +  +  :     317572 :     switch(ty)
             +  +  +  - ]
    2639                 :            :     {
    2640                 :     237450 :       case t_REAL: return divir(x,y);
    2641                 :            :       case t_INTMOD:
    2642                 :         30 :         z = cgetg(3, t_INTMOD);
    2643                 :         30 :         return div_intmod_same(z, gel(y,1), modii(x, gel(y,1)), gel(y,2));
    2644                 :            :       case t_FRAC:
    2645                 :      28777 :         z = cgetg(3,t_FRAC); p1 = gcdii(x,gel(y,1));
    2646         [ +  + ]:      28777 :         if (is_pm1(p1))
    2647                 :            :         {
    2648                 :      23494 :           avma = (pari_sp)z;
    2649                 :      23494 :           gel(z,2) = icopy(gel(y,1));
    2650                 :      23494 :           gel(z,1) = mulii(gel(y,2), x);
    2651                 :      23494 :           normalize_frac(z);
    2652         [ +  + ]:      23494 :           fix_frac_if_int(z);
    2653                 :            :         }
    2654                 :            :         else
    2655                 :            :         {
    2656                 :       5283 :           x = diviiexact(x,p1); tetpil = avma;
    2657                 :       5283 :           gel(z,2) = diviiexact(gel(y,1), p1);
    2658                 :       5283 :           gel(z,1) = mulii(gel(y,2), x);
    2659                 :       5283 :           normalize_frac(z);
    2660         [ +  + ]:       5283 :           fix_frac_if_int_GC(z,tetpil);
    2661                 :            :         }
    2662                 :      28777 :         return z;
    2663                 :            : 
    2664                 :        140 :       case t_FFELT: return Z_FF_div(x,y);
    2665                 :      51115 :       case t_COMPLEX: return divRc(x,y);
    2666                 :         30 :       case t_PADIC: return divTp(x, y);
    2667                 :            :       case t_QUAD:
    2668                 :         30 :         av = avma; p1 = quadnorm(y); p2 = mulRq(x, gconj(y)); tetpil = avma;
    2669                 :         30 :         return gerepile(av, tetpil, gdiv(p2,p1));
    2670                 :            :     }
    2671                 :            :   }
    2672 [ +  + ][ -  + ]:   10345366 :   if (gequal0(y) && ty != t_MAT) pari_err_INV("gdiv",y);
    2673                 :            : 
    2674 [ +  + ][ +  + ]:   10345366 :   if (is_const_t(tx) && is_const_t(ty)) switch(tx)
           [ +  +  +  +  
             +  +  +  - ]
    2675                 :            :   {
    2676                 :            :     case t_REAL:
    2677   [ +  +  +  +  :    1837711 :       switch(ty)
                      + ]
    2678                 :            :       {
    2679                 :    1647181 :         case t_INT: return divri(x,y);
    2680                 :            :         case t_FRAC:
    2681                 :      83735 :           av = avma; z = divri(mulri(x,gel(y,2)), gel(y,1));
    2682                 :      83735 :           return gerepileuptoleaf(av, z);
    2683                 :     106775 :         case t_COMPLEX: return divRc(x, y);
    2684                 :          5 :         case t_QUAD: return divfq(x, y, lg(x));
    2685                 :         15 :         default: pari_err_TYPE2("/",x,y);
    2686                 :            :       }
    2687                 :            : 
    2688                 :            :     case t_INTMOD:
    2689   [ +  +  +  -  :       1030 :       switch(ty)
             +  +  +  - ]
    2690                 :            :       {
    2691                 :            :         case t_INT:
    2692                 :        935 :           z = cgetg(3, t_INTMOD);
    2693                 :        935 :           return div_intmod_same(z, gel(x,1), gel(x,2), modii(y, gel(x,1)));
    2694                 :         20 :         case t_FRAC: { GEN X = gel(x,1);
    2695                 :         20 :           z = cgetg(3,t_INTMOD); p1 = remii(mulii(gel(y,2), gel(x,2)), X);
    2696                 :         20 :           return div_intmod_same(z, X, p1, modii(gel(y,1), X));
    2697                 :            :         }
    2698                 :            :         case t_FFELT:
    2699         [ -  + ]:         45 :           if (!equalii(gel(x,1),FF_p_i(y)))
    2700                 :          0 :             pari_err_OP("/",x,y);
    2701                 :         45 :           return Z_FF_div(gel(x,2),y);
    2702                 :            : 
    2703                 :            :         case t_COMPLEX:
    2704                 :          0 :           av = avma;
    2705                 :          0 :           return gerepileupto(av, mulRc_direct(gdiv(x,cxnorm(y)), gconj(y)));
    2706                 :            : 
    2707                 :            :         case t_QUAD:
    2708                 :          5 :           av = avma; p1 = quadnorm(y); p2 = gmul(x,gconj(y)); tetpil = avma;
    2709                 :          5 :           return gerepile(av,tetpil, gdiv(p2,p1));
    2710                 :            : 
    2711                 :          5 :         case t_PADIC: { GEN X = gel(x,1);
    2712                 :          5 :           z = cgetg(3, t_INTMOD);
    2713                 :          5 :           return div_intmod_same(z, X, gel(x,2), padic_to_Fp(y, X));
    2714                 :            :         }
    2715                 :         20 :         case t_REAL: pari_err_TYPE2("/",x,y);
    2716                 :            :       }
    2717                 :            : 
    2718                 :            :     case t_FRAC:
    2719   [ +  +  +  +  :     201892 :       switch(ty)
             +  +  +  - ]
    2720                 :            :       {
    2721                 :     192582 :         case t_INT: z = cgetg(3, t_FRAC);
    2722                 :     192582 :         p1 = gcdii(y,gel(x,1));
    2723         [ +  + ]:     192582 :         if (is_pm1(p1))
    2724                 :            :         {
    2725                 :      90066 :           avma = (pari_sp)z; tetpil = 0;
    2726                 :      90066 :           gel(z,1) = icopy(gel(x,1));
    2727                 :            :         }
    2728                 :            :         else
    2729                 :            :         {
    2730                 :     102516 :           y = diviiexact(y,p1); tetpil = avma;
    2731                 :     102516 :           gel(z,1) = diviiexact(gel(x,1), p1);
    2732                 :            :         }
    2733                 :     192582 :         gel(z,2) = mulii(gel(x,2),y);
    2734                 :     192582 :         normalize_frac(z);
    2735 [ +  + ][ -  + ]:     192582 :         if (tetpil) fix_frac_if_int_GC(z,tetpil);
    2736                 :     192582 :         return z;
    2737                 :            : 
    2738                 :            :         case t_REAL:
    2739                 :       8730 :           av=avma; p1=mulri(y,gel(x,2)); tetpil=avma;
    2740                 :       8730 :           return gerepile(av, tetpil, divir(gel(x,1), p1));
    2741                 :            : 
    2742                 :          5 :         case t_INTMOD: { GEN Y = gel(y,1);
    2743                 :          5 :           z = cgetg(3,t_INTMOD); p1 = remii(mulii(gel(y,2),gel(x,2)), Y);
    2744                 :          5 :           return div_intmod_same(z, Y, modii(gel(x,1), Y), p1);
    2745                 :            :         }
    2746                 :            : 
    2747                 :         20 :         case t_FFELT: av=avma;
    2748                 :         20 :           return gerepileupto(av,Z_FF_div(gel(x,1),FF_Z_mul(y,gel(x,2))));
    2749                 :            : 
    2750                 :        540 :         case t_COMPLEX: return divRc(x, y);
    2751                 :            : 
    2752                 :            :         case t_PADIC:
    2753         [ -  + ]:         10 :           if (!signe(gel(x,1))) return gen_0;
    2754                 :         10 :           return divTp(x, y);
    2755                 :            : 
    2756                 :            :         case t_QUAD:
    2757                 :          5 :           av=avma; p1=quadnorm(y); p2=gmul(x,gconj(y)); tetpil=avma;
    2758                 :          5 :           return gerepile(av,tetpil,gdiv(p2,p1));
    2759                 :            :       }
    2760                 :            : 
    2761                 :            :     case t_FFELT:
    2762   [ +  +  +  + ]:       3185 :       switch (ty)
    2763                 :            :       {
    2764                 :       3100 :         case t_INT: return FF_Z_Z_muldiv(x,gen_1,y);
    2765                 :         20 :         case t_FRAC: return FF_Z_Z_muldiv(x,gel(y,2),gel(y,1));
    2766                 :            :         case t_INTMOD:
    2767         [ -  + ]:         35 :           if (!equalii(gel(y,1),FF_p_i(x)))
    2768                 :          0 :             pari_err_OP("/",x,y);
    2769                 :         35 :           return FF_Z_Z_muldiv(x,gen_1,gel(y,2));
    2770                 :            :         default:
    2771                 :         30 :         pari_err_TYPE2("/",x,y);
    2772                 :            :       }
    2773                 :          0 :       break;
    2774                 :            : 
    2775                 :            :     case t_COMPLEX:
    2776   [ +  -  -  -  :     407315 :       switch(ty)
                      - ]
    2777                 :            :       {
    2778                 :     407315 :         case t_INT: case t_REAL: case t_FRAC: return divcR(x,y);
    2779                 :          0 :         case t_INTMOD: return mulRc_direct(ginv(y), x);
    2780                 :            :         case t_PADIC:
    2781         [ #  # ]:          0 :           return Zp_nosquare_m1(gel(y,2))? divcR(x,y): divTp(x, y);
    2782                 :            :         case t_QUAD:
    2783         [ #  # ]:          0 :           lx = precision(x); if (!lx) pari_err_OP("/",x,y);
    2784                 :          0 :           return divfq(x, y, lx);
    2785                 :            :       }
    2786                 :            : 
    2787                 :            :     case t_PADIC:
    2788   [ +  +  +  +  :        710 :       switch(ty)
                      + ]
    2789                 :            :       {
    2790                 :        675 :         case t_INT: case t_FRAC: { GEN p = gel(x,2);
    2791                 :        675 :           return signe(gel(x,4))? divpT(x, y)
    2792         [ +  + ]:        675 :                             : zeropadic(p, valp(x) - Q_pval(y,p));
    2793                 :            :         }
    2794                 :          5 :         case t_INTMOD: { GEN Y = gel(y,1);
    2795                 :          5 :           z = cgetg(3, t_INTMOD);
    2796                 :          5 :           return div_intmod_same(z, Y, padic_to_Fp(x, Y), gel(y,2));
    2797                 :            :         }
    2798                 :            :         case t_COMPLEX: case t_QUAD:
    2799                 :          5 :           av=avma; p1=gmul(x,gconj(y)); p2=gnorm(y); tetpil=avma;
    2800                 :          5 :           return gerepile(av,tetpil,gdiv(p1,p2));
    2801                 :            : 
    2802                 :         20 :         case t_REAL: pari_err_TYPE2("/",x,y);
    2803                 :            :       }
    2804                 :            : 
    2805                 :            :     case t_QUAD:
    2806   [ +  +  +  -  :       1075 :       switch (ty)
                      + ]
    2807                 :            :       {
    2808                 :            :         case t_INT: case t_INTMOD: case t_FRAC:
    2809                 :       1040 :           z = cgetg(4,t_QUAD);
    2810                 :       1040 :           gel(z,1) = ZX_copy(gel(x,1));
    2811                 :       1040 :           gel(z,2) = gdiv(gel(x,2), y);
    2812                 :       1040 :           gel(z,3) = gdiv(gel(x,3), y); return z;
    2813                 :         20 :         case t_REAL: return divqf(x, y, lg(y));
    2814                 :          5 :         case t_PADIC: return divTp(x, y);
    2815                 :            :         case t_COMPLEX:
    2816         [ #  # ]:          0 :           ly = precision(y); if (!ly) pari_err_OP("/",x,y);
    2817                 :          0 :           return divqf(x, y, ly);
    2818                 :            :       }
    2819                 :            :   }
    2820   [ +  +  -  + ]:    7892463 :   switch(ty) {
    2821                 :            :     case t_REAL: case t_INTMOD: case t_PADIC: case t_POLMOD:
    2822                 :      12422 :       return gmul(x, ginv(y)); /* missing gerepile, for speed */
    2823                 :            :     case t_MAT:
    2824                 :         35 :       av = avma; p1 = RgM_inv(y);
    2825         [ +  + ]:         35 :       if (!p1) pari_err_INV("gdiv",y);
    2826                 :         30 :       return gerepileupto(av, gmul(x, p1));
    2827                 :            :     case t_VEC: case t_COL:
    2828                 :            :     case t_LIST: case t_STR: case t_VECSMALL: case t_CLOSURE:
    2829                 :          0 :       pari_err_TYPE2("/",x,y);
    2830                 :            :   }
    2831      [ +  -  + ]:    7880006 :   switch(tx) {
    2832                 :            :     case t_VEC: case t_COL: case t_MAT:
    2833                 :     268635 :       z = cgetg_copy(x, &lx);
    2834         [ +  + ]:    1046934 :       for (i=1; i<lx; i++) gel(z,i) = gdiv(gel(x,i),y);
    2835                 :     268635 :       return z;
    2836                 :            :     case t_LIST: case t_STR: case t_VECSMALL: case t_CLOSURE:
    2837                 :          0 :       pari_err_TYPE2("/",x,y);
    2838                 :            :   }
    2839                 :            : 
    2840                 :    7611371 :   vy = gvar(y);
    2841         [ +  + ]:    7611371 :   if (tx == t_POLMOD) { GEN X = gel(x,1);
    2842                 :       1360 :     vx = varn(X);
    2843         [ +  + ]:       1360 :     if (vx != vy) {
    2844         [ +  + ]:       1245 :       if (varncmp(vx, vy) > 0) return div_scal_T(x, y, ty);
    2845                 :       1240 :       z = cgetg(3,t_POLMOD);
    2846                 :       1240 :       gel(z,1) = RgX_copy(X);
    2847                 :       1240 :       gel(z,2) = gdiv(gel(x,2), y); return z;
    2848                 :            :     }
    2849                 :            :     /* y is POL, SER or RFRAC */
    2850                 :        115 :     av = avma;
    2851         [ -  + ]:        115 :     switch(ty)
    2852                 :            :     {
    2853                 :          0 :       case t_RFRAC: y = gmod(ginv(y), X); break;
    2854                 :        115 :       default: y = ginvmod(gmod(y,X), X);
    2855                 :            :     }
    2856                 :        110 :     return gerepileupto(av, mul_polmod_same(X, gel(x,2), y));
    2857                 :            :   }
    2858                 :            :   /* x and y are not both is_scalar_t. If one of them is scalar, it's not a
    2859                 :            :    * POLMOD (done already), hence its variable is NO_VARIABLE. If the other has
    2860                 :            :    * variable NO_VARIABLE, then the operation is incorrect */
    2861                 :    7610011 :   vx = gvar(x);
    2862         [ +  + ]:    7610011 :   if (vx != vy) { /* includes cases where one is scalar */
    2863         [ +  + ]:    7173567 :     if (varncmp(vx, vy) < 0) return div_T_scal(x, y, tx);
    2864                 :    6612183 :                         else return div_scal_T(x, y, ty);
    2865                 :            :   }
    2866   [ +  +  +  + ]:     436444 :   switch(tx)
    2867                 :            :   {
    2868                 :            :     case t_POL:
    2869      [ +  +  - ]:      59636 :       switch(ty)
    2870                 :            :       {
    2871                 :            :         case t_SER:
    2872         [ -  + ]:         30 :           if (lg(y) == 2)
    2873                 :          0 :             return zeroser(vx, RgX_val(x) - valp(y));
    2874                 :         30 :           p1 = RgX_to_ser(x,lg(y));
    2875                 :         30 :           p2 = div_ser(p1, y, vx);
    2876                 :         30 :           settyp(p1, t_VECSMALL); /* p1 left on stack */
    2877                 :         30 :           return p2;
    2878                 :            : 
    2879                 :            :         case t_RFRAC:
    2880                 :            :         {
    2881                 :      59606 :           GEN y1 = gel(y,1), y2 = gel(y,2);
    2882 [ +  + ][ +  + ]:      59606 :           if (typ(y1) == t_POL && varn(y1) == vx)
    2883                 :      43621 :             return mul_rfrac_scal(y2, y1, x);
    2884                 :      15985 :           av = avma;
    2885                 :      15985 :           return gerepileupto(av, RgX_Rg_div(RgX_mul(y2, x), y1));
    2886                 :            :         }
    2887                 :            :       }
    2888                 :          0 :       break;
    2889                 :            : 
    2890                 :            :     case t_SER:
    2891      [ +  -  - ]:     188705 :       switch(ty)
    2892                 :            :       {
    2893                 :            :         case t_POL:
    2894         [ +  + ]:     188705 :           if (lg(x) == 2)
    2895                 :        930 :             return zeroser(vx, valp(x) - RgX_val(y));
    2896                 :     187775 :           p1 = RgX_to_ser_inexact(y,lg(x));
    2897                 :     187775 :           p2 = div_ser(x, p1, vx);
    2898                 :     187775 :           settyp(p1, t_VECSMALL); /* p1 left on stack */
    2899                 :     187775 :           return p2;
    2900                 :            :         case t_RFRAC:
    2901                 :          0 :           av = avma;
    2902                 :          0 :           return gerepileupto(av, gdiv(gmul(x,gel(y,2)), gel(y,1)));
    2903                 :            :       }
    2904                 :          0 :       break;
    2905                 :            : 
    2906                 :            :     case t_RFRAC:
    2907      [ +  -  - ]:     188093 :       switch(ty)
    2908                 :            :       {
    2909                 :     188093 :         case t_POL: return div_rfrac_pol(gel(x,1),gel(x,2), y);
    2910                 :            :         case t_SER:
    2911                 :          0 :           av = avma; z = RgX_to_ser_inexact(gel(x,2), lg(y));
    2912                 :          0 :           return gerepileupto(av, gdiv(gel(x,1), gmul(z,y)));
    2913                 :            :       }
    2914                 :          0 :       break;
    2915                 :            :   }
    2916                 :         10 :   pari_err_TYPE2("/",x,y);
    2917                 :   62526987 :   return NULL; /* not reached */
    2918                 :            : }
    2919                 :            : 
    2920                 :            : /********************************************************************/
    2921                 :            : /**                                                                **/
    2922                 :            : /**                     SIMPLE MULTIPLICATION                      **/
    2923                 :            : /**                                                                **/
    2924                 :            : /********************************************************************/
    2925                 :            : GEN
    2926                 :   10673503 : gmulsg(long s, GEN y)
    2927                 :            : {
    2928                 :            :   long ly, i;
    2929                 :            :   pari_sp av;
    2930                 :            :   GEN z;
    2931                 :            : 
    2932   [ +  +  +  +  :   10673503 :   switch(typ(y))
          +  +  +  +  +  
             +  +  +  +  
                      - ]
    2933                 :            :   {
    2934                 :    4807291 :     case t_INT:  return mulsi(s,y);
    2935                 :    4371787 :     case t_REAL: return mulsr(s,y);
    2936                 :     118435 :     case t_INTMOD: { GEN p = gel(y,1);
    2937                 :     118435 :       z = cgetg(3,t_INTMOD);
    2938                 :     118435 :       gel(z,2) = gerepileuptoint((pari_sp)z, modii(mulsi(s,gel(y,2)), p));
    2939                 :     118435 :       gel(z,1) = icopy(p); return z;
    2940                 :            :     }
    2941                 :     134775 :     case t_FFELT: return FF_Z_mul(y,stoi(s));
    2942                 :            :     case t_FRAC:
    2943         [ +  + ]:      16855 :       if (!s) return gen_0;
    2944                 :      16595 :       z = cgetg(3,t_FRAC);
    2945                 :      16595 :       i = cgcd(s, smodis(gel(y,2), s));
    2946         [ +  + ]:      16595 :       if (i == 1)
    2947                 :            :       {
    2948                 :      10945 :         gel(z,2) = icopy(gel(y,2));
    2949                 :      10945 :         gel(z,1) = mulis(gel(y,1), s);
    2950                 :            :       }
    2951                 :            :       else
    2952                 :            :       {
    2953                 :       5650 :         gel(z,2) = divis(gel(y,2), i);
    2954                 :       5650 :         gel(z,1) = mulis(gel(y,1), s/i);
    2955         [ +  + ]:       5650 :         fix_frac_if_int(z);
    2956                 :            :       }
    2957                 :      16595 :       return z;
    2958                 :            : 
    2959                 :     873074 :     case t_COMPLEX: z = cgetg(3, t_COMPLEX);
    2960                 :     873074 :       gel(z,1) = gmulsg(s,gel(y,1));
    2961                 :     873074 :       gel(z,2) = gmulsg(s,gel(y,2)); return z;
    2962                 :            : 
    2963                 :            :     case t_PADIC:
    2964         [ -  + ]:        510 :       if (!s) return gen_0;
    2965                 :        510 :       av = avma; return gerepileupto(av, mulpp(cvtop2(stoi(s),y), y));
    2966                 :            : 
    2967                 :         10 :     case t_QUAD: z = cgetg(4, t_QUAD);
    2968                 :         10 :       gel(z,1) = ZX_copy(gel(y,1));
    2969                 :         10 :       gel(z,2) = gmulsg(s,gel(y,2));
    2970                 :         10 :       gel(z,3) = gmulsg(s,gel(y,3)); return z;
    2971                 :            : 
    2972                 :        925 :     case t_POLMOD: z = cgetg(3, t_POLMOD);
    2973                 :        925 :       gel(z,1) = RgX_copy(gel(y,1));
    2974                 :        925 :       gel(z,2) = gmulsg(s,gel(y,2)); return z;
    2975                 :            : 
    2976                 :            :     case t_POL:
    2977         [ +  + ]:      65485 :       if (!signe(y)) return RgX_copy(y);
    2978         [ +  + ]:      64840 :       if (!s) return scalarpol(RgX_get_0(y), varn(y));
    2979                 :      64175 :       z = cgetg_copy(y, &ly); z[1]=y[1];
    2980         [ +  + ]:     254575 :       for (i=2; i<ly; i++) gel(z,i) = gmulsg(s,gel(y,i));
    2981                 :      64175 :       return normalizepol_lg(z, ly);
    2982                 :            : 
    2983                 :            :     case t_SER:
    2984         [ -  + ]:      13122 :       if (ser_isexactzero(y)) return gcopy(y);
    2985         [ -  + ]:      13122 :       if (!s) return scalarser(RgX_get_0(y), varn(y), valp(y));
    2986                 :      13122 :       z = cgetg_copy(y, &ly); z[1]=y[1];
    2987         [ +  + ]:      40069 :       for (i=2; i<ly; i++) gel(z,i) = gmulsg(s,gel(y,i));
    2988                 :      13122 :       return normalize(z);
    2989                 :            : 
    2990                 :            :     case t_RFRAC:
    2991         [ -  + ]:         10 :       if (!s) return zeropol(varn(gel(y,2)));
    2992         [ -  + ]:         10 :       if (s == 1) return gcopy(y);
    2993         [ -  + ]:         10 :       if (s == -1) return gneg(y);
    2994                 :         10 :       return mul_rfrac_scal(gel(y,1), gel(y,2), stoi(s));
    2995                 :            : 
    2996                 :            :     case t_VEC: case t_COL: case t_MAT:
    2997                 :     271224 :       z = cgetg_copy(y, &ly);
    2998         [ +  + ]:    1047834 :       for (i=1; i<ly; i++) gel(z,i) = gmulsg(s,gel(y,i));
    2999                 :     271224 :       return z;
    3000                 :            :   }
    3001                 :          0 :   pari_err_TYPE("gmulsg",y);
    3002                 :   10673503 :   return NULL; /* not reached */
    3003                 :            : }
    3004                 :            : 
    3005                 :            : /********************************************************************/
    3006                 :            : /**                                                                **/
    3007                 :            : /**                       SIMPLE DIVISION                          **/
    3008                 :            : /**                                                                **/
    3009                 :            : /********************************************************************/
    3010                 :            : 
    3011                 :            : GEN
    3012                 :    3044898 : gdivgs(GEN x, long s)
    3013                 :            : {
    3014                 :            :   long lx, i;
    3015                 :            :   pari_sp av;
    3016                 :            :   GEN z, y, p1;
    3017                 :            : 
    3018         [ -  + ]:    3044898 :   if (!s) pari_err_INV("gdivgs",gen_0);
    3019   [ +  +  +  +  :    3044898 :   switch(typ(x))
          +  +  +  -  +  
             +  +  +  - ]
    3020                 :            :   {
    3021                 :            :     case t_INT:
    3022                 :     154430 :       av = avma; z = divis_rem(x,s,&i);
    3023         [ +  + ]:     154430 :       if (!i) return z;
    3024                 :            : 
    3025                 :     113550 :       i = cgcd(s, i);
    3026                 :     113550 :       avma=av; z = cgetg(3,t_FRAC);
    3027         [ +  + ]:     113550 :       if (i == 1) y = icopy(x); else { s /= i; y = diviuexact(x, i); }
    3028                 :     113550 :       gel(z,1) = y;
    3029                 :     113550 :       gel(z,2) = stoi(s); normalize_frac(z); return z;
    3030                 :            : 
    3031                 :            :     case t_REAL:
    3032                 :    2002238 :       return divrs(x,s);
    3033                 :            : 
    3034                 :            :     case t_INTMOD:
    3035                 :       5250 :       z = cgetg(3, t_INTMOD);
    3036                 :       5250 :       return div_intmod_same(z, gel(x,1), gel(x,2), modsi(s, gel(x,1)));
    3037                 :            : 
    3038                 :        285 :     case t_FFELT: return FF_Z_Z_muldiv(x,gen_1,stoi(s));
    3039                 :            : 
    3040                 :      28255 :     case t_FRAC: z = cgetg(3, t_FRAC);
    3041                 :      28255 :       i = cgcd(s, smodis(gel(x,1), s));
    3042         [ +  + ]:      28255 :       if (i == 1)
    3043                 :            :       {
    3044                 :      25540 :         gel(z,2) = mulsi(s, gel(x,2));
    3045                 :      25540 :         gel(z,1) = icopy(gel(x,1));
    3046                 :            :       }
    3047                 :            :       else
    3048                 :            :       {
    3049                 :       2715 :         gel(z,2) = mulsi(s/i, gel(x,2));
    3050                 :       2715 :         gel(z,1) = divis(gel(x,1), i);
    3051                 :            :       }
    3052                 :      28255 :       normalize_frac(z);
    3053         [ +  + ]:      28255 :       fix_frac_if_int(z); return z;
    3054                 :            : 
    3055                 :     825505 :     case t_COMPLEX: z = cgetg(3, t_COMPLEX);
    3056                 :     825505 :       gel(z,1) = gdivgs(gel(x,1),s);
    3057                 :     825505 :       gel(z,2) = gdivgs(gel(x,2),s); return z;
    3058                 :            : 
    3059                 :            :     case t_PADIC: /* divpT */
    3060                 :            :     {
    3061                 :      26210 :       GEN p = gel(x,2);
    3062         [ +  + ]:      26210 :       if (!signe(gel(x,4))) return zeropadic(p, valp(x) - u_pval(s,p));
    3063                 :      25940 :       av = avma;
    3064                 :      25940 :       return gerepileupto(av, divpp(x, cvtop2(stoi(s),x)));
    3065                 :            :     }
    3066                 :            : 
    3067                 :          0 :     case t_QUAD: z = cgetg(4, t_QUAD);
    3068                 :          0 :       gel(z,1) = ZX_copy(gel(x,1));
    3069                 :          0 :       gel(z,2) = gdivgs(gel(x,2),s);
    3070                 :          0 :       gel(z,3) = gdivgs(gel(x,3),s); return z;
    3071                 :            : 
    3072                 :        975 :     case t_POLMOD: z = cgetg(3, t_POLMOD);
    3073                 :        975 :       gel(z,1) = RgX_copy(gel(x,1));
    3074                 :        975 :       gel(z,2) = gdivgs(gel(x,2),s); return z;
    3075                 :            : 
    3076                 :            :     case t_RFRAC:
    3077                 :        105 :       av = avma;
    3078                 :        105 :       p1 = ggcd(stoi(s),gel(x,1));
    3079         [ +  + ]:        105 :       if (typ(p1) == t_INT)
    3080                 :            :       {
    3081                 :         25 :         avma = av;
    3082                 :         25 :         z = cgetg(3, t_RFRAC);
    3083                 :         25 :         i = p1[2];
    3084         [ +  - ]:         25 :         if (i == 1)
    3085                 :            :         {
    3086                 :         25 :           gel(z,1) = gcopy(gel(x,1));
    3087                 :         25 :           gel(z,2) = gmulsg(s,gel(x,2));
    3088                 :            :         }
    3089                 :            :         else
    3090                 :            :         {
    3091                 :          0 :           gel(z,1) = gdivgs(gel(x,1), i);
    3092                 :          0 :           gel(z,2) = gmulgs(gel(x,2), s/i);
    3093                 :            :         }
    3094                 :            :       }
    3095                 :            :       else /* t_FRAC */
    3096                 :            :       {
    3097                 :         80 :         z = cgetg(3, t_RFRAC);
    3098                 :         80 :         gel(z,1) = gdiv(gel(x,1), p1);
    3099                 :         80 :         gel(z,2) = RgX_Rg_mul(gel(x,2), gdivsg(s,p1));
    3100                 :         80 :         z = gerepilecopy(av, z);
    3101                 :            :       }
    3102                 :        105 :       return z;
    3103                 :            : 
    3104                 :            :     case t_POL: case t_SER:
    3105                 :       1615 :       z = cgetg_copy(x, &lx); z[1] = x[1];
    3106         [ +  + ]:       5115 :       for (i=2; i<lx; i++) gel(z,i) = gdivgs(gel(x,i),s);
    3107                 :       1615 :       return z;
    3108                 :            :     case t_VEC: case t_COL: case t_MAT:
    3109                 :         30 :       z = cgetg_copy(x, &lx);
    3110         [ +  + ]:         90 :       for (i=1; i<lx; i++) gel(z,i) = gdivgs(gel(x,i),s);
    3111                 :         30 :       return z;
    3112                 :            : 
    3113                 :            :   }
    3114                 :          0 :   pari_err_TYPE2("/",x, stoi(s));
    3115                 :    3044898 :   return NULL; /* not reached */
    3116                 :            : }
    3117                 :            : 
    3118                 :            : /* True shift (exact multiplication by 2^n) */
    3119                 :            : GEN
    3120                 :   20697995 : gmul2n(GEN x, long n)
    3121                 :            : {
    3122                 :            :   long lx, i, k, l;
    3123                 :            :   GEN z, a, b;
    3124                 :            : 
    3125   [ +  +  +  +  :   20697995 :   switch(typ(x))
          +  +  +  +  +  
             +  +  +  +  
                      - ]
    3126                 :            :   {
    3127                 :            :     case t_INT:
    3128         [ +  + ]:   14511666 :       if (n>=0) return shifti(x,n);
    3129         [ +  + ]:      71695 :       if (!signe(x)) return gen_0;
    3130                 :      39110 :       l = vali(x); n = -n;
    3131         [ +  + ]:      39110 :       if (n<=l) return shifti(x,-n);
    3132                 :      24820 :       z = cgetg(3,t_FRAC);
    3133                 :      24820 :       gel(z,1) = shifti(x,-l);
    3134                 :      24820 :       gel(z,2) = int2n(n-l); return z;
    3135                 :            : 
    3136                 :            :     case t_REAL:
    3137                 :    3454642 :       return shiftr(x,n);
    3138                 :            : 
    3139                 :      69945 :     case t_INTMOD: b = gel(x,1); a = gel(x,2);
    3140                 :      69945 :       z = cgetg(3,t_INTMOD);
    3141         [ +  + ]:      69945 :       if (n <= 0) return div_intmod_same(z, b, a, modii(int2n(-n), b));
    3142                 :      69940 :       gel(z,2) = gerepileuptoint((pari_sp)z, modii(shifti(a,n), b));
    3143                 :      69940 :       gel(z,1) = icopy(b); return z;
    3144                 :            : 
    3145                 :      65026 :     case t_FFELT: return FF_mul2n(x,n);
    3146                 :            : 
    3147                 :      35985 :     case t_FRAC: a = gel(x,1); b = gel(x,2);
    3148                 :      35985 :       l = vali(a);
    3149                 :      35985 :       k = vali(b);
    3150         [ +  + ]:      35985 :       if (n+l >= k)
    3151                 :            :       {
    3152         [ +  + ]:      20540 :         if (expi(b) == k) return shifti(a,n-k); /* b power of 2 */
    3153                 :      17130 :         l = n-k; k = -k;
    3154                 :            :       }
    3155                 :            :       else
    3156                 :            :       {
    3157                 :      15445 :         k = -(l+n); l = -l;
    3158                 :            :       }
    3159                 :      32575 :       z = cgetg(3,t_FRAC);
    3160                 :      32575 :       gel(z,1) = shifti(a,l);
    3161                 :      32575 :       gel(z,2) = shifti(b,k); return z;
    3162                 :            : 
    3163                 :    1719178 :     case t_COMPLEX: z = cgetg(3,t_COMPLEX);
    3164                 :    1719178 :       gel(z,1) = gmul2n(gel(x,1),n);
    3165                 :    1719178 :       gel(z,2) = gmul2n(gel(x,2),n); return z;
    3166                 :            : 
    3167                 :         15 :     case t_QUAD: z = cgetg(4,t_QUAD);
    3168                 :         15 :       gel(z,1) = ZX_copy(gel(x,1));
    3169                 :         15 :       gel(z,2) = gmul2n(gel(x,2),n);
    3170                 :         15 :       gel(z,3) = gmul2n(gel(x,3),n); return z;
    3171                 :            : 
    3172                 :       1800 :     case t_POLMOD: z = cgetg(3,t_POLMOD);
    3173                 :       1800 :       gel(z,1) = RgX_copy(gel(x,1));
    3174                 :       1800 :       gel(z,2) = gmul2n(gel(x,2),n); return z;
    3175                 :            : 
    3176                 :            :     case t_POL:
    3177                 :     166368 :       z = cgetg_copy(x, &lx); z[1] = x[1];
    3178         [ +  + ]:    1474119 :       for (i=2; i<lx; i++) gel(z,i) = gmul2n(gel(x,i),n);
    3179                 :     166368 :       return normalizepol_lg(z, lx); /* needed if char = 2 */
    3180                 :            :     case t_SER:
    3181         [ +  + ]:      39820 :       if (ser_isexactzero(x)) return gcopy(x);
    3182                 :      39810 :       z = cgetg_copy(x, &lx); z[1] = x[1];
    3183         [ +  + ]:    1018415 :       for (i=2; i<lx; i++) gel(z,i) = gmul2n(gel(x,i),n);
    3184                 :      39810 :       return normalize(z); /* needed if char = 2 */
    3185                 :            :     case t_VEC: case t_COL: case t_MAT:
    3186                 :     631815 :       z = cgetg_copy(x, &lx);
    3187         [ +  + ]:    2567754 :       for (i=1; i<lx; i++) gel(z,i) = gmul2n(gel(x,i),n);
    3188                 :     631815 :       return z;
    3189                 :            : 
    3190                 :            :     case t_RFRAC: /* int2n wrong if n < 0 */
    3191                 :         15 :       return mul_rfrac_scal(gel(x,1),gel(x,2), gmul2n(gen_1,n));
    3192                 :            : 
    3193                 :            :     case t_PADIC: /* int2n wrong if n < 0 */
    3194                 :       1720 :       return gmul(gmul2n(gen_1,n),x);
    3195                 :            :   }
    3196                 :          0 :   pari_err_TYPE("gmul2n",x);
    3197                 :   20697995 :   return NULL; /* not reached */
    3198                 :            : }
    3199                 :            : 
    3200                 :            : /*******************************************************************/
    3201                 :            : /*                                                                 */
    3202                 :            : /*                              INVERSE                            */
    3203                 :            : /*                                                                 */
    3204                 :            : /*******************************************************************/
    3205                 :            : static GEN
    3206                 :       5273 : inv_polmod(GEN T, GEN x)
    3207                 :            : {
    3208                 :       5273 :   GEN z = cgetg(3,t_POLMOD), a;
    3209                 :       5273 :   gel(z,1) = RgX_copy(T);
    3210 [ +  + ][ +  - ]:       5273 :   if (typ(x) != t_POL || varn(x) != varn(T) || lg(x) <= 3)
                 [ +  + ]
    3211                 :       2480 :     a = ginv(x);
    3212                 :            :   else
    3213                 :            :   {
    3214                 :       2793 :     pari_sp av = avma;
    3215         [ +  + ]:       2793 :     if (lg(T) == 5) /* quadratic fields */
    3216                 :       1565 :       a = RgX_Rg_div(quad_polmod_conj(x,T), quad_polmod_norm(x,T));
    3217                 :            :     else
    3218                 :            :     {
    3219                 :       1228 :       GEN p = NULL;
    3220 [ +  + ][ +  + ]:       1228 :       if (RgX_is_FpX(T, &p) && RgX_is_FpX(x, &p) && p)
                 [ +  + ]
    3221                 :            :       {
    3222                 :         10 :         T = RgX_to_FpX(T, p); x = RgX_to_FpX(x, p);
    3223         [ +  + ]:         10 :         if (lgefint(p) == 3)
    3224                 :            :         {
    3225                 :          5 :           ulong pp = p[2];
    3226                 :          5 :           a = Flxq_inv(ZX_to_Flx(x, pp), ZX_to_Flx(T, pp), pp);
    3227                 :          5 :           a = Flx_to_ZX(a);
    3228                 :            :         }
    3229                 :            :         else
    3230                 :          5 :           a = FpXQ_inv(x, T, p);
    3231                 :         10 :         a = FpX_to_mod(a, p);
    3232                 :         10 :         a = gerepileupto(av, a);
    3233                 :            :       }
    3234                 :            :       else {
    3235                 :       1218 :         avma = av;
    3236                 :       1228 :         a = RgXQ_inv(x, gel(z,1));
    3237                 :            :       }
    3238                 :            :     }
    3239                 :            :   }
    3240                 :       5273 :   gel(z,2) = a; return z;
    3241                 :            : }
    3242                 :            : GEN
    3243                 :    5186055 : ginv(GEN x)
    3244                 :            : {
    3245                 :            :   long s;
    3246                 :            :   pari_sp av, tetpil;
    3247                 :            :   GEN z, y, p1, p2;
    3248                 :            : 
    3249   [ +  +  +  +  :    5186055 :   switch(typ(x))
          +  +  +  +  +  
          +  +  +  +  +  
                +  -  - ]
    3250                 :            :   {
    3251                 :            :     case t_INT:
    3252         [ +  + ]:      44110 :       if (is_pm1(x)) return icopy(x);
    3253         [ -  + ]:      23881 :       s = signe(x); if (!s) pari_err_INV("ginv",gen_0);
    3254                 :      23881 :       z = cgetg(3,t_FRAC);
    3255         [ +  + ]:      23881 :       gel(z,1) = s<0? gen_m1: gen_1;
    3256                 :      23881 :       gel(z,2) = absi(x); return z;
    3257                 :            : 
    3258                 :     460438 :     case t_REAL: return invr(x);
    3259                 :            : 
    3260                 :      22250 :     case t_INTMOD: z=cgetg(3,t_INTMOD);
    3261                 :      22250 :       gel(z,1) = icopy(gel(x,1));
    3262                 :      22250 :       gel(z,2) = Fp_inv(gel(x,2),gel(x,1)); return z;
    3263                 :            : 
    3264                 :            :     case t_FRAC: {
    3265                 :      59836 :       GEN a = gel(x,1), b = gel(x,2);
    3266                 :      59836 :       s = signe(a);
    3267 [ +  + ][ +  + ]:      59836 :       if (is_pm1(a)) return s > 0? icopy(b): negi(b);
    3268                 :      18385 :       z = cgetg(3,t_FRAC);
    3269                 :      18385 :       gel(z,1) = icopy(b);
    3270                 :      18385 :       gel(z,2) = icopy(a);
    3271                 :      18385 :       normalize_frac(z); return z;
    3272                 :            :     }
    3273                 :            :     case t_COMPLEX:
    3274                 :     749401 :       av=avma;
    3275                 :     749401 :       p1=cxnorm(x);
    3276                 :     749401 :       p2=mkcomplex(gel(x,1), gneg(gel(x,2)));
    3277                 :     749401 :       tetpil=avma;
    3278                 :     749401 :       return gerepile(av,tetpil,divcR(p2,p1));
    3279                 :            : 
    3280                 :            :     case t_QUAD:
    3281                 :        240 :       av=avma; p1=gnorm(x); p2=gconj(x); tetpil=avma;
    3282                 :        240 :       return gerepile(av,tetpil,gdiv(p2,p1));
    3283                 :            : 
    3284                 :       1785 :     case t_PADIC: z = cgetg(5,t_PADIC);
    3285         [ +  + ]:       1785 :       if (!signe(gel(x,4))) pari_err_INV("ginv",x);
    3286                 :       1780 :       z[1] = _evalprecp(precp(x)) | evalvalp(-valp(x));
    3287                 :       1780 :       gel(z,2) = icopy(gel(x,2));
    3288                 :       1780 :       gel(z,3) = icopy(gel(x,3));
    3289                 :       1780 :       gel(z,4) = Fp_inv(gel(x,4),gel(z,3)); return z;
    3290                 :            : 
    3291                 :       5273 :     case t_POLMOD: return inv_polmod(gel(x,1), gel(x,2));
    3292                 :       3170 :     case t_FFELT: return FF_inv(x);
    3293                 :    3829822 :     case t_POL: return gred_rfrac_simple(gen_1,x);
    3294                 :        255 :     case t_SER: return gdiv(gen_1,x);
    3295                 :            : 
    3296                 :            :     case t_RFRAC:
    3297                 :            :     {
    3298                 :       2075 :       GEN n = gel(x,1), d = gel(x,2);
    3299                 :       2075 :       pari_sp av = avma, ltop;
    3300         [ -  + ]:       2075 :       if (gequal0(n)) pari_err_INV("ginv",x);
    3301                 :            : 
    3302                 :       2075 :       n = simplify_shallow(n);
    3303 [ +  + ][ +  - ]:       2075 :       if (typ(n) != t_POL || varn(n) != varn(d))
    3304                 :            :       {
    3305         [ +  + ]:       2075 :         if (gequal1(n)) { avma = av; return RgX_copy(d); }
    3306                 :        485 :         ltop = avma;
    3307                 :        485 :         z = RgX_Rg_div(d,n);
    3308                 :            :       } else {
    3309                 :          0 :         ltop = avma;
    3310                 :          0 :         z = cgetg(3,t_RFRAC);
    3311                 :          0 :         gel(z,1) = RgX_copy(d);
    3312                 :          0 :         gel(z,2) = RgX_copy(n);
    3313                 :            :       }
    3314                 :        485 :       stackdummy(av, ltop);
    3315                 :        485 :       return z;
    3316                 :            :     }
    3317                 :            : 
    3318                 :            :     case t_QFR:
    3319                 :          5 :       av = avma; z = cgetg(5, t_QFR);
    3320                 :          5 :       gel(z,1) = gel(x,1);
    3321                 :          5 :       gel(z,2) = negi( gel(x,2) );
    3322                 :          5 :       gel(z,3) = gel(x,3);
    3323                 :          5 :       gel(z,4) = negr( gel(x,4) );
    3324                 :          5 :       return gerepileupto(av, redreal(z));
    3325                 :            : 
    3326                 :            :     case t_QFI:
    3327                 :       6760 :       y = gcopy(x);
    3328 [ +  + ][ +  + ]:       6760 :       if (!equalii(gel(x,1),gel(x,2)) && !equalii(gel(x,1),gel(x,3)))
    3329                 :       6580 :         togglesign(gel(y,2));
    3330                 :       6760 :       return y;
    3331                 :            :     case t_MAT:
    3332                 :            :     {
    3333                 :        635 :       GEN ff = NULL;
    3334         [ +  + ]:        635 :       if (RgM_is_FFM(x,&ff))
    3335                 :         15 :         y = FFM_inv(x, ff);
    3336                 :            :       else
    3337                 :        620 :         y = RgM_inv(x);
    3338         [ -  + ]:        635 :       if (!y) pari_err_INV("ginv",x);
    3339                 :        635 :       return y;
    3340                 :            :     }
    3341                 :            :     case t_VECSMALL:
    3342                 :            :     {
    3343                 :          0 :       long i, lx = lg(x)-1;
    3344                 :          0 :       y = zero_zv(lx);
    3345         [ #  # ]:          0 :       for (i=1; i<=lx; i++)
    3346                 :            :       {
    3347                 :          0 :         long xi = x[i];
    3348 [ #  # ][ #  # ]:          0 :         if (xi<1 || xi>lx || y[xi])
                 [ #  # ]
    3349                 :          0 :           pari_err_TYPE("ginv [not a permutation]", x);
    3350                 :          0 :         y[xi] = i;
    3351                 :            :       }
    3352                 :          0 :       return y;
    3353                 :            :     }
    3354                 :            :   }
    3355                 :          0 :   pari_err_TYPE("inverse",x);
    3356                 :    5186040 :   return NULL; /* not reached */
    3357                 :            : }

Generated by: LCOV version 1.9