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 17236-ec2ebc9) Lines: 1749 1919 91.1 %
Date: 2014-12-19 Functions: 87 87 100.0 %
Legend: Lines: hit not hit | Branches: + taken - not taken # not executed Branches: 1164 1428 81.5 %

           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                 :         21 : kro_quad(GEN x, GEN y)
      35                 :            : {
      36                 :         21 :   pari_sp av=avma;
      37                 :         21 :   long k = kronecker(quad_disc(x), y);
      38                 :         21 :   avma = av; return k;
      39                 :            : }
      40                 :            : 
      41                 :            : /* is -1 not a square in Zp, assume p prime */
      42                 :            : INLINE int
      43                 :         28 : 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                 :   32390425 : addRc(GEN x, GEN y) {
      56                 :   32390425 :   GEN z = cgetg(3,t_COMPLEX);
      57                 :   32390425 :   gel(z,1) = gadd(x,gel(y,1));
      58                 :   32390425 :   gel(z,2) = gcopy(gel(y,2)); return z;
      59                 :            : }
      60                 :            : static GEN
      61                 :   40759830 : mulRc(GEN x, GEN y) {
      62                 :   40759830 :   GEN z = cgetg(3,t_COMPLEX);
      63         [ +  + ]:   40759830 :   gel(z,1) = isintzero(gel(y,1))? gen_0: gmul(x,gel(y,1));
      64                 :   40759830 :   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                 :         35 : mulRc_direct(GEN x, GEN y) {
      69                 :         35 :   GEN z = cgetg(3,t_COMPLEX);
      70                 :         35 :   gel(z,1) = gmul(x,gel(y,1));
      71                 :         35 :   gel(z,2) = gmul(x,gel(y,2)); return z;
      72                 :            : }
      73                 :            : static GEN
      74                 :     216318 : divRc(GEN x, GEN y) {
      75                 :     216318 :   GEN t = gdiv(x, cxnorm(y)), mt = gneg(t); /* left on stack for efficiency */
      76                 :     216318 :   GEN z = cgetg(3,t_COMPLEX);
      77         [ +  + ]:     216318 :   gel(z,1) = isintzero(gel(y,1))? gen_0: gmul(t, gel(y,1));
      78                 :     216318 :   gel(z,2) = gmul(mt, gel(y,2));
      79                 :     216318 :   return z;
      80                 :            : }
      81                 :            : static GEN
      82                 :    1667727 : divcR(GEN x, GEN y) {
      83                 :    1667727 :   GEN z = cgetg(3,t_COMPLEX);
      84         [ +  + ]:    1667727 :   gel(z,1) = isintzero(gel(x,1))? gen_0: gdiv(gel(x,1), y);
      85                 :    1667727 :   gel(z,2) = gdiv(gel(x,2), y); return z;
      86                 :            : }
      87                 :            : static GEN
      88                 :        581 : addRq(GEN x, GEN y) {
      89                 :        581 :   GEN z = cgetg(4,t_QUAD);
      90                 :        581 :   gel(z,1) = ZX_copy(gel(y,1));
      91                 :        581 :   gel(z,2) = gadd(x, gel(y,2));
      92                 :        581 :   gel(z,3) = gcopy(gel(y,3)); return z;
      93                 :            : }
      94                 :            : static GEN
      95                 :       1820 : mulRq(GEN x, GEN y) {
      96                 :       1820 :   GEN z = cgetg(4,t_QUAD);
      97                 :       1820 :   gel(z,1) = ZX_copy(gel(y,1));
      98                 :       1820 :   gel(z,2) = gmul(x,gel(y,2));
      99                 :       1820 :   gel(z,3) = gmul(x,gel(y,3)); return z;
     100                 :            : }
     101                 :            : static GEN
     102                 :         14 : addqf(GEN x, GEN y, long prec) { pari_sp av = avma;
     103                 :         14 :   long i = gexpo(x) - gexpo(y);
     104         [ +  - ]:         14 :   if (i > 0) prec += nbits2extraprec( i );
     105                 :         14 :   return gerepileupto(av, gadd(y, quadtofp(x, prec)));
     106                 :            : }
     107                 :            : static GEN
     108                 :     994749 : mulrfrac(GEN x, GEN y)
     109                 :            : {
     110                 :     994749 :   pari_sp av = avma;
     111                 :     994749 :   GEN z, a = gel(y,1), b = gel(y,2);
     112         [ +  + ]:     994749 :   if (is_pm1(a)) /* frequent special case */
     113                 :            :   {
     114                 :     248921 :     z = divri(x, b);
     115         [ +  + ]:     248921 :     if (signe(a) < 0) togglesign(z);
     116                 :     248921 :     return z;
     117                 :            :   }
     118                 :     994749 :   return gerepileuptoleaf(av, divri(mulri(x,gel(y,1)), gel(y,2)));
     119                 :            : }
     120                 :            : static GEN
     121                 :         14 : mulqf(GEN x, GEN y, long prec) { pari_sp av = avma;
     122                 :         14 :   return gerepileupto(av, gmul(y, quadtofp(x, prec)));
     123                 :            : }
     124                 :            : static GEN
     125                 :         28 : divqf(GEN x, GEN y, long prec) { pari_sp av = avma;
     126                 :         28 :   return gerepileupto(av, gdiv(quadtofp(x,prec), y));
     127                 :            : }
     128                 :            : static GEN
     129                 :          7 : divfq(GEN x, GEN y, long prec) { pari_sp av = avma;
     130                 :          7 :   return gerepileupto(av, gdiv(x, quadtofp(y,prec)));
     131                 :            : }
     132                 :            : /* y PADIC, x + y by converting x to padic */
     133                 :            : static GEN
     134                 :          7 : addTp(GEN x, GEN y) { pari_sp av = avma; GEN z;
     135                 :            : 
     136         [ -  + ]:          7 :   if (!valp(y)) z = cvtop2(x,y);
     137                 :            :   else {
     138         [ -  + ]:          7 :     long l = signe(gel(y,4))? valp(y) + precp(y): valp(y);
     139                 :          7 :     z  = cvtop(x, gel(y,2), l);
     140                 :            :   }
     141                 :          7 :   return gerepileupto(av, addsub_pp(z, y, addii));
     142                 :            : }
     143                 :            : /* y PADIC, x * y by converting x to padic */
     144                 :            : static GEN
     145                 :      39004 : mulTp(GEN x, GEN y) { pari_sp av = avma;
     146                 :      39004 :   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                 :         63 : divTp(GEN x, GEN y) { pari_sp av = avma;
     151                 :         63 :   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                 :        889 : divpT(GEN x, GEN y) { pari_sp av = avma;
     157                 :        889 :   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                 :    1009600 : add_intmod_same(GEN z, GEN X, GEN x, GEN y) {
     164         [ +  + ]:    1009600 :   if (lgefint(X) == 3) {
     165                 :     977352 :     ulong u = Fl_add(itou(x),itou(y), X[2]);
     166                 :     977352 :     avma = (pari_sp)z; gel(z,2) = utoi(u);
     167                 :            :   }
     168                 :            :   else {
     169         [ +  + ]:      32248 :     GEN u = addii(x,y); if (cmpii(u, X) >= 0) u = subii(u, X);
     170                 :      32248 :     gel(z,2) = gerepileuptoint((pari_sp)z, u);
     171                 :            :   }
     172                 :    1009600 :   gel(z,1) = icopy(X); return z;
     173                 :            : }
     174                 :            : static GEN
     175                 :     121272 : sub_intmod_same(GEN z, GEN X, GEN x, GEN y) {
     176         [ +  + ]:     121272 :   if (lgefint(X) == 3) {
     177                 :     101790 :     ulong u = Fl_sub(itou(x),itou(y), X[2]);
     178                 :     101790 :     avma = (pari_sp)z; gel(z,2) = utoi(u);
     179                 :            :   }
     180                 :            :   else {
     181         [ +  + ]:      19482 :     GEN u = subii(x,y); if (signe(u) < 0) u = addii(u, X);
     182                 :      19482 :     gel(z,2) = gerepileuptoint((pari_sp)z, u);
     183                 :            :   }
     184                 :     121272 :   gel(z,1) = icopy(X); return z;
     185                 :            : }
     186                 :            : /* cf add_intmod_same */
     187                 :            : static GEN
     188                 :    2435580 : mul_intmod_same(GEN z, GEN X, GEN x, GEN y) {
     189         [ +  + ]:    2435580 :   if (lgefint(X) == 3) {
     190                 :    2326337 :     ulong u = Fl_mul(itou(x),itou(y), X[2]);
     191                 :    2326337 :     avma = (pari_sp)z; gel(z,2) = utoi(u);
     192                 :            :   }
     193                 :            :   else
     194                 :     109243 :     gel(z,2) = gerepileuptoint((pari_sp)z, remii(mulii(x,y), X) );
     195                 :    2435580 :   gel(z,1) = icopy(X); return z;
     196                 :            : }
     197                 :            : /* cf add_intmod_same */
     198                 :            : static GEN
     199                 :      27804 : div_intmod_same(GEN z, GEN X, GEN x, GEN y)
     200                 :            : {
     201         [ +  + ]:      27804 :   if (lgefint(X) == 3) {
     202                 :      20230 :     ulong m = uel(X,2), u = Fl_div(itou(x), itou(y), m);
     203                 :      20223 :     avma = (pari_sp)z; gel(z,2) = utoi(u);
     204                 :            :   }
     205                 :            :   else
     206                 :       7574 :     gel(z,2) = gerepileuptoint((pari_sp)z, remii(mulii(x, Fp_inv(y,X)), X) );
     207                 :      27797 :   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                 :    9374248 : rfrac_denom_mul_scal(GEN d, GEN y)
     220                 :            : {
     221                 :    9374248 :   GEN D = RgX_Rg_mul(d, y);
     222         [ -  + ]:    9374248 :   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                 :    9374248 :   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                 :   54133825 : gred_rfrac_simple(GEN n, GEN d)
     233                 :            : {
     234                 :            :   GEN c, cn, cd, z;
     235                 :   54133825 :   long dd = degpol(d);
     236                 :            : 
     237         [ +  + ]:   54133825 :   if (dd <= 0)
     238                 :            :   {
     239         [ -  + ]:       5705 :     if (dd < 0) pari_err_INV("gred_rfrac_simple", d);
     240                 :       5705 :     n = gdiv(n, gel(d,2));
     241 [ +  + ][ +  + ]:       5705 :     if (typ(n) != t_POL || varn(n) != varn(d)) n = scalarpol(n, varn(d));
     242                 :       5705 :     return n;
     243                 :            :   }
     244                 :            : 
     245                 :   54128120 :   cd = content(d);
     246 [ +  + ][ +  + ]:   54128120 :   cn = (typ(n) == t_POL && varn(n) == varn(d))? content(n): n;
     247         [ +  + ]:   54128120 :   if (!gequal1(cd)) {
     248                 :    6547958 :     d = RgX_Rg_div(d,cd);
     249         [ +  + ]:    6547958 :     if (!gequal1(cn))
     250                 :            :     {
     251         [ -  + ]:    1302145 :       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         [ +  + ]:    1302145 :         n = (cn != n)? RgX_Rg_div(n,cn): gen_1;
     257                 :    1302145 :         c = gdiv(cn,cd);
     258                 :            :       }
     259                 :            :     }
     260                 :            :     else
     261                 :    5245813 :       c = ginv(cd);
     262                 :            :   } else {
     263         [ +  + ]:   47580162 :     if (!gequal1(cn))
     264                 :            :     {
     265         [ +  + ]:    2555364 :       if (gequal0(cn)) {
     266         [ +  + ]:         77 :         if (isexactzero(cn)) return scalarpol(cn, varn(d));
     267                 :          7 :         c = gen_1;
     268                 :            :       } else {
     269         [ +  + ]:    2555287 :         n = (cn != n)? RgX_Rg_div(n,cn): gen_1;
     270                 :    2555287 :         c = cn;
     271                 :            :       }
     272                 :            :     } else {
     273                 :   45024798 :       GEN y = cgetg(3,t_RFRAC);
     274                 :   45024798 :       gel(y,1) = gcopy(n);
     275                 :   45024798 :       gel(y,2) = RgX_copy(d); return y;
     276                 :            :     }
     277                 :            :   }
     278                 :            : 
     279         [ +  + ]:    9103252 :   if (typ(c) == t_POL)
     280                 :            :   {
     281                 :     906784 :     z = c;
     282         [ +  + ]:     949589 :     do { z = content(z); } while (typ(z) == t_POL);
     283                 :     906784 :     cd = denom(z);
     284                 :     906784 :     cn = gmul(c, cd);
     285                 :            :   }
     286                 :            :   else
     287                 :            :   {
     288                 :    8196468 :     cn = numer(c);
     289                 :    8196468 :     cd = denom(c);
     290                 :            :   }
     291                 :    9103252 :   z = cgetg(3,t_RFRAC);
     292                 :    9103252 :   gel(z,1) = gmul(n, cn);
     293                 :    9103252 :   gel(z,2) = rfrac_denom_mul_scal(d, cd);
     294                 :   54133825 :   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                 :     155463 : fix_rfrac(GEN x, long d)
     300                 :            : {
     301                 :            :   GEN z, N, D;
     302 [ +  + ][ -  + ]:     155463 :   if (!d || typ(x) == t_POL) return x;
     303                 :     153993 :   z = cgetg(3, t_RFRAC);
     304                 :     153993 :   N = gel(x,1);
     305                 :     153993 :   D = gel(x,2);
     306         [ +  + ]:     153993 :   if (d > 0) {
     307         [ +  - ]:     153923 :     gel(z, 1) = (typ(N)==t_POL && varn(N)==varn(D))? RgX_shift(N,d)
     308         [ +  - ]:     307846 :                                                    : monomialcopy(N,d,varn(D));
     309                 :     153923 :     gel(z, 2) = RgX_copy(D);
     310                 :            :   } else {
     311                 :         70 :     gel(z, 1) = gcopy(N);
     312                 :         70 :     gel(z, 2) = RgX_shift(D, -d);
     313                 :            :   }
     314                 :     155463 :   return z;
     315                 :            : }
     316                 :            : 
     317                 :            : /* assume d != 0 */
     318                 :            : static GEN
     319                 :   43548856 : gred_rfrac2_i(GEN n, GEN d)
     320                 :            : {
     321                 :            :   GEN y, z;
     322                 :            :   long v, vd, vn;
     323                 :            : 
     324                 :   43548856 :   n = simplify_shallow(n);
     325         [ +  + ]:   43548856 :   if (isrationalzero(n)) return gcopy(n);
     326                 :   36750951 :   d = simplify_shallow(d);
     327         [ +  + ]:   36750951 :   if (typ(d) != t_POL) return gdiv(n,d);
     328                 :   35517551 :   vd = varn(d);
     329         [ +  + ]:   35517551 :   if (typ(n) != t_POL)
     330                 :            :   {
     331         [ +  + ]:   19890947 :     if (varncmp(vd, gvar(n)) >= 0) return gdiv(n,d);
     332         [ +  - ]:   19889540 :     if (varncmp(vd, gvar2(n)) < 0) return gred_rfrac_simple(n,d);
     333                 :          0 :     pari_err_BUG("gred_rfrac2_i [incompatible variables]");
     334                 :            :   }
     335                 :   15626604 :   vn = varn(n);
     336         [ +  + ]:   15626604 :   if (varncmp(vd, vn) < 0) return gred_rfrac_simple(n,d);
     337         [ +  + ]:   15485248 :   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                 :   15324768 :   v = RgX_valrem(n, &n) - RgX_valrem(d, &d);
     341         [ +  + ]:   15324768 :   if (!degpol(d))
     342                 :            :   {
     343                 :   12333442 :     n = RgX_Rg_div(n,gel(d,2));
     344         [ +  + ]:   12333442 :     return v? RgX_mulXn(n,v): n;
     345                 :            :   }
     346                 :            : 
     347                 :            :   /* X does not divide gcd(n,d), deg(d) > 0 */
     348 [ +  + ][ +  - ]:    2991326 :   if (!isinexact(n) && !isinexact(d))
     349                 :            :   {
     350                 :    2991319 :     y = RgX_divrem(n, d, &z);
     351 [ +  + ][ +  + ]:    2991319 :     if (!signe(z)) { cgiv(z); return v? RgX_mulXn(y, v): y; }
     352                 :     155456 :     z = RgX_gcd(d, z);
     353         [ +  + ]:     155456 :     if (degpol(z)) { n = RgX_div(n,z); d = RgX_div(d,z); }
     354                 :            :   }
     355                 :   43548856 :   return fix_rfrac(gred_rfrac_simple(n,d), v);
     356                 :            : }
     357                 :            : 
     358                 :            : GEN
     359                 :   18290004 : gred_rfrac2(GEN x1, GEN x2)
     360                 :            : {
     361                 :   18290004 :   pari_sp av = avma;
     362                 :   18290004 :   return gerepileupto(av, gred_rfrac2_i(x1, x2));
     363                 :            : }
     364                 :            : 
     365                 :            : /* x1,x2 t_INT, return x1/x2 in reduced form */
     366                 :            : GEN
     367                 :   11447552 : gred_frac2(GEN x1, GEN x2)
     368                 :            : {
     369                 :   11447552 :   GEN r, y = dvmdii(x1,x2,&r);
     370                 :            :   pari_sp av;
     371                 :            : 
     372         [ +  + ]:   11447524 :   if (r == gen_0) return y; /* gen_0 intended */
     373                 :    3216047 :   av = avma; r = gcdii(x2,r);
     374         [ +  + ]:    3216047 :   if (lgefint(r) == 3)
     375                 :            :   {
     376                 :    3023112 :     ulong rr = r[2];
     377                 :    3023112 :     avma = av;
     378         [ +  + ]:    3023112 :     if (rr == 1) y = mkfraccopy(x1, x2);
     379                 :            :     else
     380                 :            :     {
     381                 :    1505043 :       y = cgetg(3,t_FRAC);
     382                 :    1505043 :       gel(y,1) = diviuexact(x1, rr);
     383                 :    1505043 :       gel(y,2) = diviuexact(x2, rr);
     384                 :            :     }
     385                 :            :   }
     386                 :            :   else
     387                 :            :   { /* rare: r left on stack for efficiency */
     388                 :     192935 :     y = cgetg(3,t_FRAC);
     389                 :     192935 :     gel(y,1) = diviiexact(x1,r);
     390                 :     192935 :     gel(y,2) = diviiexact(x2,r);
     391                 :            :   }
     392                 :   11447524 :   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                 :      12481 : quad_polmod_conj(GEN x, GEN y)
     403                 :            : {
     404                 :            :   GEN z, u, v, a, b;
     405                 :            :   pari_sp av;
     406         [ -  + ]:      12481 :   if (typ(x) != t_POL) return gcopy(x);
     407 [ +  - ][ -  + ]:      12481 :   if (varn(x) != varn(y) || degpol(x) <= 0) return RgX_copy(x);
     408                 :      12481 :   a = gel(y,4); u = gel(x,3); /*Mod(ux + v, ax^2 + bx + c)*/
     409                 :      12481 :   b = gel(y,3); v = gel(x,2);
     410                 :      12481 :   z = cgetg(4, t_POL); z[1] = x[1]; av = avma;
     411                 :      12481 :   gel(z,2) = gerepileupto(av, gsub(v, gdiv(gmul(u,b), a)));
     412                 :      12481 :   gel(z,3) = gneg(u); return z;
     413                 :            : }
     414                 :            : static GEN
     415                 :      12481 : quad_polmod_norm(GEN x, GEN y)
     416                 :            : {
     417                 :            :   GEN z, u, v, a, b, c;
     418                 :            :   pari_sp av;
     419 [ +  - ][ +  - ]:      12481 :   if (typ(x) != t_POL || varn(x) != varn(y) || degpol(x) <= 0)
                 [ -  + ]
     420                 :          0 :     return gsqr(x);
     421                 :      12481 :   a = gel(y,4); u = gel(x,3); /*Mod(ux + v, ax^2 + bx + c)*/
     422                 :      12481 :   b = gel(y,3); v = gel(x,2);
     423                 :      12481 :   c = gel(y,2); av = avma;
     424                 :      12481 :   z = gmul(u, gsub(gmul(c,u), gmul(b,v)));
     425         [ +  + ]:      12481 :   if (!gequal1(a)) z = gdiv(z, a);
     426                 :      12481 :   return gerepileupto(av, gadd(z, gsqr(v)));
     427                 :            : }
     428                 :            : 
     429                 :            : GEN
     430                 :     531961 : gconj(GEN x)
     431                 :            : {
     432                 :            :   long lx, i;
     433                 :            :   GEN y;
     434                 :            : 
     435   [ +  +  +  +  :     531961 :   switch(typ(x))
             +  +  -  - ]
     436                 :            :   {
     437                 :            :     case t_INT: case t_REAL:
     438                 :      61766 :       return mpcopy(x);
     439                 :            : 
     440                 :            :     case t_INTMOD: case t_FRAC: case t_PADIC:
     441                 :       1400 :       return gcopy(x);
     442                 :            : 
     443                 :            :     case t_COMPLEX:
     444                 :     464359 :       y = cgetg(3,t_COMPLEX);
     445                 :     464359 :       gel(y,1) = gcopy(gel(x,1));
     446                 :     464359 :       gel(y,2) = gneg(gel(x,2));
     447                 :     464359 :       break;
     448                 :            : 
     449                 :            :     case t_QUAD:
     450                 :        595 :       y = cgetg(4,t_QUAD);
     451                 :        595 :       gel(y,1) = ZX_copy(gel(x,1));
     452                 :        595 :       gel(y,2) = gequal0(gmael(x,1,3))? gcopy(gel(x,2))
     453         [ +  + ]:        595 :                                     : gadd(gel(x,2), gel(x,3));
     454                 :        595 :       gel(y,3) = gneg(gel(x,3));
     455                 :        595 :       break;
     456                 :            : 
     457                 :            :     case t_POL: case t_SER:
     458                 :         21 :       y = cgetg_copy(x, &lx); y[1] = x[1];
     459         [ +  + ]:         63 :       for (i=2; i<lx; i++) gel(y,i) = gconj(gel(x,i));
     460                 :         21 :       break;
     461                 :            : 
     462                 :            :     case t_RFRAC: case t_VEC: case t_COL: case t_MAT:
     463                 :       3820 :       y = cgetg_copy(x, &lx);
     464         [ +  + ]:      25201 :       for (i=1; i<lx; i++) gel(y,i) = gconj(gel(x,i));
     465                 :       3820 :       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                 :     531961 :   return y;
     483                 :            : }
     484                 :            : 
     485                 :            : GEN
     486                 :         42 : conjvec(GEN x,long prec)
     487                 :            : {
     488                 :            :   long lx, s, i;
     489                 :            :   GEN z;
     490                 :            : 
     491   [ -  -  +  -  :         42 :   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                 :         28 :       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                 :         14 :       GEN T = gel(x,1), r;
     516                 :            :       pari_sp av;
     517                 :            : 
     518                 :         14 :       lx = lg(T);
     519         [ -  + ]:         14 :       if (lx <= 3) return cgetg(1,t_COL);
     520                 :         14 :       x = gel(x,2);
     521         [ +  + ]:         42 :       for (i=2; i<lx; i++)
     522                 :            :       {
     523                 :         35 :         GEN c = gel(T,i);
     524      [ +  +  - ]:         35 :         switch(typ(c)) {
     525                 :            :           case t_INTMOD: {
     526                 :          7 :             GEN p = gel(c,1);
     527                 :            :             pari_sp av;
     528 [ -  + ][ #  # ]:          7 :             if (typ(x) != t_POL) retconst_col(lx-3, Rg_to_Fp(x, p));
     529                 :          7 :             av = avma;
     530                 :          7 :             T = RgX_to_FpX(T,p);
     531                 :          7 :             x = RgX_to_FpX(x, p);
     532         [ -  + ]:          7 :             if (varn(x) != varn(T)) pari_err_VAR("conjvec",x,T);
     533                 :          7 :             z = FpXQC_to_mod(FpXQ_conjvec(x, T , p), T, p);
     534                 :          7 :             return gerepileupto(av, z);
     535                 :            :           }
     536                 :            :           case t_INT:
     537                 :         28 :           case t_FRAC: break;
     538                 :          0 :           default: pari_err_TYPE("conjvec [not a rational t_POL]",T);
     539                 :            :         }
     540                 :            :       }
     541         [ -  + ]:          7 :       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         [ -  + ]:          7 :       if (!RgX_is_QX(x)) pari_err_TYPE("conjvec", x);
     548                 :          7 :       av = avma;
     549         [ -  + ]:          7 :       if (varn(x) != varn(T)) pari_err_VAR("conjvec",x,T);
     550                 :          7 :       r = cleanroots(T,prec);
     551                 :          7 :       z = cgetg(lx-2,t_COL);
     552         [ +  + ]:         28 :       for (i=1; i<=lx-3; i++) gel(z,i) = poleval(x, gel(r,i));
     553                 :          7 :       return gerepileupto(av, z);
     554                 :            :     }
     555                 :            : 
     556                 :            :     default:
     557                 :          0 :       pari_err_TYPE("conjvec",x);
     558                 :          0 :       return NULL; /* not reached */
     559                 :            :   }
     560                 :         42 :   return z;
     561                 :            : }
     562                 :            : 
     563                 :            : 
     564                 :            : /********************************************************************/
     565                 :            : /**                                                                **/
     566                 :            : /**                           ADDITION                             **/
     567                 :            : /**                                                                **/
     568                 :            : /********************************************************************/
     569                 :            : /* x, y compatible PADIC, op = add or sub */
     570                 :            : static GEN
     571                 :     217518 : addsub_pp(GEN x, GEN y, GEN (*op)(GEN,GEN))
     572                 :            : {
     573                 :     217518 :   pari_sp av = avma;
     574                 :            :   long d,e,r,rx,ry;
     575                 :     217518 :   GEN u, z, mod, p = gel(x,2);
     576                 :            :   int swap;
     577                 :            : 
     578                 :     217518 :   (void)new_chunk(5 + lgefint(gel(x,3)) + lgefint(gel(y,3)));
     579                 :     217518 :   e = valp(x);
     580                 :     217518 :   r = valp(y); d = r-e;
     581         [ +  + ]:     217518 :   if (d < 0) { swap = 1; swap(x,y); e = r; d = -d; } else swap = 0;
     582                 :     217518 :   rx = precp(x);
     583                 :     217518 :   ry = precp(y);
     584         [ +  + ]:     217518 :   if (d) /* v(x) < v(y) */
     585                 :            :   {
     586                 :      71764 :     r = d+ry; z = powiu(p,d);
     587         [ +  + ]:      71764 :     if (r < rx) mod = mulii(z,gel(y,3)); else { r = rx; mod = gel(x,3); }
     588                 :      71764 :     z = mulii(z,gel(y,4));
     589         [ +  + ]:      71764 :     u = swap? op(z, gel(x,4)): op(gel(x,4), z);
     590                 :            :   }
     591                 :            :   else
     592                 :            :   {
     593                 :            :     long c;
     594         [ +  + ]:     145754 :     if (ry < rx) { r=ry; mod = gel(y,3); } else { r=rx; mod = gel(x,3); }
     595         [ -  + ]:     145754 :     u = swap? op(gel(y,4), gel(x,4)): op(gel(x,4), gel(y,4));
     596 [ +  + ][ +  + ]:     145754 :     if (!signe(u) || (c = Z_pvalrem(u,p,&u)) >= r)
     597                 :            :     {
     598                 :       2954 :       avma = av; return zeropadic(p, e+r);
     599                 :            :     }
     600         [ +  + ]:     142800 :     if (c)
     601                 :            :     {
     602                 :      15918 :       mod = diviiexact(mod, powiu(p,c));
     603                 :      15918 :       r -= c;
     604                 :      15918 :       e += c;
     605                 :            :     }
     606                 :            :   }
     607                 :     214564 :   u = modii(u, mod);
     608                 :     214564 :   avma = av; z = cgetg(5,t_PADIC);
     609                 :     214564 :   z[1] = evalprecp(r) | evalvalp(e);
     610                 :     214564 :   gel(z,2) = icopy(p);
     611                 :     214564 :   gel(z,3) = icopy(mod);
     612                 :     217518 :   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                 :      70336 : addQp(GEN x, GEN y)
     618                 :            : {
     619                 :      70336 :   pari_sp av = avma;
     620                 :      70336 :   long tx,d,r,e, vy = valp(y), py = precp(y);
     621                 :      70336 :   GEN z,q,p1,p2,mod,u, p = gel(y,2);
     622                 :            : 
     623                 :      70336 :   tx = typ(x);
     624                 :      70336 :   e = (tx == t_INT)? Z_pvalrem(x,p,&p1)
     625         [ +  + ]:      71862 :                    : Z_pvalrem(gel(x,1),p,&p1) -
     626                 :       1526 :                      Z_pvalrem(gel(x,2),p,&p2);
     627                 :      70336 :   d = vy - e; r = d + py;
     628         [ +  + ]:      70336 :   if (r <= 0) { avma = av; return gcopy(y); }
     629                 :      70154 :   mod = gel(y,3);
     630                 :      70154 :   u   = gel(y,4);
     631                 :      70154 :   (void)new_chunk(5 + ((lgefint(mod) + lgefint(p)*labs(d)) << 1));
     632                 :            : 
     633         [ +  + ]:      70154 :   if (d > 0)
     634                 :            :   {
     635                 :      63322 :     q = powiu(p,d);
     636                 :      63322 :     mod = mulii(mod, q);
     637                 :      63322 :     u   = mulii(u, q);
     638 [ +  + ][ +  + ]:      63322 :     if (tx != t_INT && !is_pm1(p2)) p1 = mulii(p1, Fp_inv(p2,mod));
     639                 :      63322 :     u = addii(u, p1);
     640                 :            :   }
     641         [ +  + ]:       6832 :   else if (d < 0)
     642                 :            :   {
     643                 :        553 :     q = powiu(p,-d);
     644 [ +  + ][ +  + ]:        553 :     if (tx != t_INT && !is_pm1(p2)) p1 = mulii(p1, Fp_inv(p2,mod));
     645                 :        553 :     p1 = mulii(p1, q);
     646                 :        553 :     u = addii(u, p1);
     647                 :        553 :     r = py; e = vy;
     648                 :            :   }
     649                 :            :   else
     650                 :            :   {
     651                 :            :     long c;
     652 [ +  + ][ +  + ]:       6279 :     if (tx != t_INT && !is_pm1(p2)) p1 = mulii(p1, Fp_inv(p2,mod));
     653                 :       6279 :     u = addii(u, p1);
     654 [ +  + ][ +  + ]:       6279 :     if (!signe(u) || (c = Z_pvalrem(u,p,&u)) >= r)
     655                 :            :     {
     656                 :        399 :       avma = av; return zeropadic(p,e+r);
     657                 :            :     }
     658         [ +  + ]:       5880 :     if (c)
     659                 :            :     {
     660                 :       3367 :       mod = diviiexact(mod, powiu(p,c));
     661                 :       3367 :       r -= c;
     662                 :       3367 :       e += c;
     663                 :            :     }
     664                 :            :   }
     665                 :      69755 :   u = modii(u, mod);
     666                 :      69755 :   avma = av; z = cgetg(5,t_PADIC);
     667                 :      69755 :   z[1] = evalprecp(r) | evalvalp(e);
     668                 :      69755 :   gel(z,2) = icopy(p);
     669                 :      69755 :   gel(z,3) = icopy(mod);
     670                 :      70336 :   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                 :        616 : addsub_polmod(GEN X, GEN Y, GEN x, GEN y, GEN(*op)(GEN,GEN))
     678                 :            : {
     679                 :        616 :   long T[3] = { evaltyp(t_POLMOD) | _evallg(3),0,0 };
     680                 :        616 :   GEN z = cgetg(3,t_POLMOD);
     681                 :        616 :   long vx = varn(X), vy = varn(Y);
     682         [ -  + ]:        616 :   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         [ +  - ]:        616 :   if (varncmp(vx, vy) < 0)
     688                 :        616 :   { 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                 :        616 :   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                 :    2658067 : addsub_polmod_scal(GEN Y, GEN y, GEN x, GEN(*op)(GEN,GEN))
     696                 :            : {
     697                 :    2658067 :   GEN z = cgetg(3,t_POLMOD);
     698                 :    2658067 :   gel(z,1) = RgX_copy(Y);
     699                 :    2658067 :   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                 :       4221 : add_ser_scal(GEN y, GEN x)
     705                 :            : {
     706                 :            :   long i, l, ly, vy;
     707                 :            :   GEN z;
     708                 :            : 
     709         [ +  + ]:       4221 :   if (isrationalzero(x)) return gcopy(y);
     710                 :       3703 :   ly = lg(y);
     711                 :       3703 :   l = valp(y);
     712         [ +  + ]:       3703 :   if (l < 3-ly) return gcopy(y);
     713                 :            :   /* l + ly >= 3 */
     714         [ +  + ]:       3696 :   if (l < 0)
     715                 :            :   {
     716                 :        301 :     z = cgetg(ly,t_SER); z[1] = y[1];
     717         [ +  + ]:       1148 :     for (i = 2; i <= 1-l; i++) gel(z,i) = gcopy(gel(y,i));
     718                 :        301 :     gel(z,i) = gadd(x,gel(y,i)); i++;
     719         [ +  + ]:       1400 :     for (     ; i < ly; i++)   gel(z,i) = gcopy(gel(y,i));
     720                 :        301 :     return z;
     721                 :            :   }
     722                 :       3395 :   vy = varn(y);
     723         [ +  + ]:       3395 :   if (l > 0)
     724                 :            :   {
     725         [ +  + ]:       2961 :     if (ser_isexactzero(y))
     726         [ +  + ]:       1057 :       return scalarser(ly == 2? x: gadd(x,gel(y,2)), vy, l);
     727                 :       1904 :     y -= l; ly += l;
     728                 :       1904 :     z = cgetg(ly,t_SER);
     729                 :       1904 :     x = gcopy(x);
     730         [ +  + ]:       3493 :     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                 :        434 :     z = cgetg(ly,t_SER);
     735                 :        434 :     x = gadd(x, gel(y,2));
     736                 :        434 :     i = 3;
     737                 :            :   }
     738         [ +  + ]:      14154 :   for (; i<ly; i++) gel(z,i) = gcopy(gel(y,i));
     739                 :       2338 :   gel(z,2) = x;
     740                 :       2338 :   z[1] = evalsigne(1) | _evalvalp(0) | evalvarn(vy);
     741         [ +  + ]:       4221 :   return gequal0(x)? normalize(z): z;
     742                 :            : }
     743                 :            : static long
     744         [ +  + ]:      74342 : 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                 :      37542 : ser_add(GEN x, GEN y)
     748                 :            : {
     749                 :      37542 :   long i, lx,ly, n = valp(y) - valp(x);
     750                 :            :   GEN z;
     751         [ +  + ]:      37542 :   if (n < 0) { n = -n; swap(x,y); }
     752                 :            :   /* valp(x) <= valp(y) */
     753                 :      37542 :   lx = serprec(x);
     754         [ +  + ]:      37542 :   if (lx == 2) /* don't lose type information */
     755                 :        742 :     return scalarser(gadd(RgX_get_0(x), RgX_get_0(y)), varn(x), valp(x));
     756         [ +  + ]:      36800 :   ly = serprec(y) + n; if (lx < ly) ly = lx;
     757         [ +  + ]:      36800 :   if (n)
     758                 :            :   {
     759         [ +  + ]:       7322 :     if (n+2 > lx) return gcopy(x);
     760                 :       6629 :     z = cgetg(ly,t_SER);
     761         [ +  + ]:      29302 :     for (i=2; i<=n+1; i++) gel(z,i) = gcopy(gel(x,i));
     762         [ +  + ]:      22365 :     for (   ; i < ly; i++) gel(z,i) = gadd(gel(x,i),gel(y,i-n));
     763                 :            :   } else {
     764                 :      29478 :     z = cgetg(ly,t_SER);
     765         [ +  + ]:     147289 :     for (i=2; i < ly; i++) gel(z,i) = gadd(gel(x,i),gel(y,i));
     766                 :            :   }
     767                 :      37542 :   z[1] = x[1]; return normalize(z);
     768                 :            : }
     769                 :            : /* typ(y) == RFRAC, x polynomial in same variable or "scalar" */
     770                 :            : static GEN
     771                 :    8349368 : add_rfrac_scal(GEN y, GEN x)
     772                 :            : {
     773                 :            :   pari_sp av;
     774                 :            :   GEN n;
     775                 :            : 
     776         [ +  + ]:    8349368 :   if (isintzero(x)) return gcopy(y); /* frequent special case */
     777                 :    4624349 :   av = avma; n = gadd(gmul(x, gel(y,2)), gel(y,1));
     778                 :    8349368 :   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                 :   13345894 : add_scal(GEN y, GEN x, long ty)
     784                 :            : {
     785   [ +  +  +  -  :   13345894 :   switch(ty)
                   +  - ]
     786                 :            :   {
     787                 :    8890614 :     case t_POL: return RgX_Rg_add(y, x);
     788                 :       4221 :     case t_SER: return add_ser_scal(y, x);
     789                 :    4241038 :     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         [ +  - ]:     210021 :       if (isintzero(x)) return gcopy(y);
     793                 :          0 :       break;
     794                 :            :   }
     795                 :          0 :   pari_err_TYPE2("+",x,y);
     796                 :   13345894 :   return NULL; /* not reached */
     797                 :            : }
     798                 :            : 
     799                 :            : static GEN
     800                 :   14513414 : addsub_frac(GEN x, GEN y, GEN (*op)(GEN,GEN))
     801                 :            : {
     802                 :   14513414 :   pari_sp av = avma;
     803                 :   14513414 :   GEN x1 = gel(x,1), x2 = gel(x,2), z = cgetg(3,t_FRAC);
     804                 :   14513414 :   GEN y1 = gel(y,1), y2 = gel(y,2), q, r, n, d, delta;
     805                 :   14513414 :   int s = cmpii(x2, y2);
     806                 :            : 
     807         [ +  + ]:   14513414 :   if (!s)
     808                 :            :   { /* common denominator: (x1 op y1) / x2 */
     809                 :    5911567 :     n = op(x1, y1);
     810         [ +  + ]:    5911567 :     if (!signe(n)) { avma = av; return gen_0; }
     811                 :    5560277 :     d = x2;
     812                 :    5560277 :     q = dvmdii(n, d, &r);
     813         [ +  + ]:    5560277 :     if (r == gen_0) { avma = av; return icopy(q); }
     814                 :    5020451 :     r = gcdii(d, r);
     815         [ +  + ]:    5020451 :     if (!is_pm1(r)) { n = diviiexact(n, r); d = diviiexact(d, r); }
     816                 :    5020451 :     gel(z,1) = icopy_avma(n, (pari_sp)z);
     817                 :    5020451 :     gel(z,2) = icopy_avma(d, (pari_sp)gel(z,1));
     818                 :    5020451 :     avma = (pari_sp)gel(z,2); return z;
     819                 :            :   }
     820         [ +  + ]:    8601847 :   if (s < 0)
     821                 :            :   {
     822                 :    3861385 :     GEN Q = dvmdii(y2, x2, &r);
     823         [ +  + ]:    3861385 :     if (r == gen_0)
     824                 :            :     { /* y2 = Q x2: 1/x2 . (Q x1 op y1)/Q, where latter is in coprime form */
     825                 :    2945802 :       pari_sp av = avma;
     826                 :    2945802 :       n = op(mulii(Q,x1), y1);
     827                 :    2945802 :       q = dvmdii(n, x2, &r);
     828         [ +  + ]:    2945802 :       if (r == gen_0)
     829                 :            :       {
     830                 :     464016 :         gel(z,1) = gerepileuptoint(av, q);
     831                 :     464016 :         gel(z,2) = Q; return z;
     832                 :            :       }
     833                 :    2481786 :       r = gcdii(x2, r);
     834         [ +  + ]:    2481786 :       if (!is_pm1(r)) { n = diviiexact(n, r); x2 = diviiexact(x2, r); }
     835                 :    2481786 :       d = mulii(x2,Q);
     836                 :    2481786 :       gel(z,1) = icopy_avma(n, (pari_sp)z);
     837                 :    2481786 :       gel(z,2) = icopy_avma(d, (pari_sp)gel(z,1));
     838                 :    2481786 :       avma = (pari_sp)gel(z,2); return z;
     839                 :            :     }
     840                 :     915583 :     delta = gcdii(x2,r);
     841                 :            :   }
     842                 :            :   else
     843                 :            :   {
     844                 :    4740462 :     GEN Q = dvmdii(x2, y2, &r);
     845         [ +  + ]:    4740462 :     if (r == gen_0)
     846                 :            :     { /* x2 = Q y2: 1/y2 . (x1 op Q y1)/Q, where latter is in coprime form */
     847                 :    3977883 :       pari_sp av = avma;
     848                 :    3977883 :       n = op(x1, mulii(Q,y1));
     849                 :    3977883 :       q = dvmdii(n, y2, &r);
     850         [ +  + ]:    3977883 :       if (r == gen_0)
     851                 :            :       {
     852                 :      64164 :         gel(z,1) = gerepileuptoint(av, q);
     853                 :      64164 :         gel(z,2) = Q; return z;
     854                 :            :       }
     855                 :    3913719 :       r = gcdii(y2, r);
     856         [ +  + ]:    3913719 :       if (!is_pm1(r)) { n = diviiexact(n, r); y2 = diviiexact(y2, r); }
     857                 :    3913719 :       d = mulii(y2,Q);
     858                 :    3913719 :       gel(z,1) = icopy_avma(n, (pari_sp)z);
     859                 :    3913719 :       gel(z,2) = icopy_avma(d, (pari_sp)gel(z,1));
     860                 :    3913719 :       avma = (pari_sp)gel(z,2); return z;
     861                 :            :     }
     862                 :     762579 :     delta = gcdii(y2,r);
     863                 :            :   }
     864                 :            :   /* delta = gcd(x2,y2) */
     865         [ +  + ]:    1678162 :   if (is_pm1(delta))
     866                 :            :   { /* numerator is non-zero */
     867                 :     100876 :     gel(z,1) = gerepileuptoint((pari_sp)z, op(mulii(x1,y2), mulii(y1,x2)));
     868                 :     100876 :     gel(z,2) = mulii(x2,y2); return z;
     869                 :            :   }
     870                 :    1577286 :   x2 = diviiexact(x2,delta);
     871                 :    1577286 :   y2 = diviiexact(y2,delta);
     872                 :    1577286 :   n = op(mulii(x1,y2), mulii(y1,x2));
     873         [ -  + ]:    1577286 :   if (!signe(n)) { avma = av; return gen_0; }
     874                 :    1577286 :   d = mulii(x2, y2);
     875                 :    1577286 :   q = dvmdii(n, delta, &r);
     876         [ +  + ]:    1577286 :   if (r == gen_0)
     877                 :            :   {
     878         [ -  + ]:      84967 :     if (is_pm1(d)) { avma = av; return icopy(q); }
     879                 :      84967 :     avma = (pari_sp)z;
     880                 :      84967 :     gel(z,2) = icopy(d);
     881                 :      84967 :     gel(z,1) = icopy(q); return z;
     882                 :            :   }
     883                 :    1492319 :   r = gcdii(delta, r);
     884         [ +  + ]:    1492319 :   if (!is_pm1(r))
     885                 :            :   {
     886                 :     347448 :     n     = diviiexact(n, r);
     887                 :     347448 :     delta = diviiexact(delta, r);
     888                 :            :   }
     889                 :    1492319 :   d = mulii(d,delta); avma = (pari_sp)z;
     890                 :    1492319 :   gel(z,1) = icopy(n);
     891                 :   14513414 :   gel(z,2) = icopy(d); return z;
     892                 :            : }
     893                 :            : 
     894                 :            : /* assume x2, y2 are t_POLs in the same variable */
     895                 :            : static GEN
     896                 :    2781648 : add_rfrac(GEN x, GEN y)
     897                 :            : {
     898                 :    2781648 :   pari_sp av = avma;
     899                 :    2781648 :   GEN x1 = gel(x,1), x2 = gel(x,2);
     900                 :    2781648 :   GEN y1 = gel(y,1), y2 = gel(y,2), q, r, n, d, delta;
     901                 :            : 
     902                 :    2781648 :   delta = RgX_gcd(x2,y2);
     903         [ +  + ]:    2781648 :   if (!degpol(delta))
     904                 :            :   {
     905                 :        623 :     n = simplify_shallow( gadd(gmul(x1,y2), gmul(y1,x2)) );
     906                 :        623 :     d = RgX_mul(x2, y2);
     907                 :        623 :     return gerepileupto(av, gred_rfrac_simple(n, d));
     908                 :            :   }
     909                 :    2781025 :   x2 = RgX_div(x2,delta);
     910                 :    2781025 :   y2 = RgX_div(y2,delta);
     911                 :    2781025 :   n = gadd(gmul(x1,y2), gmul(y1,x2));
     912         [ +  + ]:    2781025 :   if (!signe(n))
     913                 :            :   {
     914                 :     680797 :     n = simplify_shallow(n);
     915         [ +  + ]:     680797 :     if (isrationalzero(n)) return gerepileupto(av, n);
     916                 :          7 :     return gerepilecopy(av, mkrfrac(n, RgX_mul(gel(x,2),y2)));
     917                 :            :   }
     918         [ +  + ]:    2100228 :   if (degpol(n) == 0)
     919                 :    1138189 :     return gerepileupto(av, gred_rfrac_simple(gel(n,2), RgX_mul(gel(x,2),y2)));
     920                 :     962039 :   q = RgX_divrem(n, delta, &r); /* we want gcd(n,delta) */
     921         [ +  + ]:     962039 :   if (isexactzero(r))
     922                 :            :   {
     923                 :            :     GEN z;
     924                 :     208970 :     d = RgX_mul(x2, y2);
     925                 :            :     /* "constant" denominator ? */
     926         [ +  + ]:     208970 :     z = lg(d) == 3? RgX_Rg_div(q, gel(d,2)): gred_rfrac_simple(q, d);
     927                 :     208970 :     return gerepileupto(av, z);
     928                 :            :   }
     929                 :     753069 :   r = RgX_gcd(delta, r);
     930         [ +  + ]:     753069 :   if (degpol(r))
     931                 :            :   {
     932                 :     148371 :     n = RgX_div(n, r);
     933                 :     148371 :     d = RgX_mul(RgX_mul(x2,y2), RgX_div(delta, r));
     934                 :            :   }
     935                 :            :   else
     936                 :     604698 :     d = RgX_mul(gel(x,2), y2);
     937                 :    2781648 :   return gerepileupto(av, gred_rfrac_simple(n, d));
     938                 :            : }
     939                 :            : 
     940                 :            : GEN
     941                 :  890893076 : gadd(GEN x, GEN y)
     942                 :            : {
     943                 :  890893076 :   long tx = typ(x), ty = typ(y), vx, vy, lx, i, l;
     944                 :            :   pari_sp av, tetpil;
     945                 :            :   GEN z, p1;
     946                 :            : 
     947 [ +  + ][ +  +  :  890893076 :   if (tx == ty) switch(tx) /* shortcut to generic case */
          +  +  +  +  +  
          +  +  +  +  +  
             +  +  +  - ]
     948                 :            :   {
     949                 :  503198554 :     case t_INT: return addii(x,y);
     950                 :  204725700 :     case t_REAL: return addrr(x,y);
     951                 :     581989 :     case t_INTMOD:  { GEN X = gel(x,1), Y = gel(y,1);
     952                 :     581989 :       z = cgetg(3,t_INTMOD);
     953 [ +  + ][ +  + ]:     581989 :       if (X==Y || equalii(X,Y))
     954                 :     581982 :         return add_intmod_same(z, X, gel(x,2), gel(y,2));
     955                 :          7 :       gel(z,1) = gcdii(X,Y);
     956                 :          7 :       av = avma; p1 = addii(gel(x,2),gel(y,2));
     957                 :          7 :       gel(z,2) = gerepileuptoint(av, remii(p1, gel(z,1))); return z;
     958                 :            :     }
     959                 :   10990113 :     case t_FRAC: return addsub_frac(x,y,addii);
     960                 :   25165066 :     case t_COMPLEX: z = cgetg(3,t_COMPLEX);
     961                 :   25165066 :       gel(z,2) = gadd(gel(x,2),gel(y,2));
     962         [ +  + ]:   25165066 :       if (isintzero(gel(z,2)))
     963                 :            :       {
     964                 :        231 :         avma = (pari_sp)(z+3);
     965                 :        231 :         return gadd(gel(x,1),gel(y,1));
     966                 :            :       }
     967                 :   25164835 :       gel(z,1) = gadd(gel(x,1),gel(y,1));
     968                 :   25164835 :       return z;
     969                 :            :     case t_PADIC:
     970         [ -  + ]:     129220 :       if (!equalii(gel(x,2),gel(y,2))) pari_err_OP("+",x,y);
     971                 :     129220 :       return addsub_pp(x,y, addii);
     972                 :        301 :     case t_QUAD: z = cgetg(4,t_QUAD);
     973         [ -  + ]:        301 :       if (!ZX_equal(gel(x,1),gel(y,1))) pari_err_OP("+",x,y);
     974                 :        301 :       gel(z,1) = ZX_copy(gel(x,1));
     975                 :        301 :       gel(z,2) = gadd(gel(x,2),gel(y,2));
     976                 :        301 :       gel(z,3) = gadd(gel(x,3),gel(y,3)); return z;
     977                 :            :     case t_POLMOD:
     978         [ +  + ]:    1188384 :       if (RgX_equal_var(gel(x,1), gel(y,1)))
     979                 :    1187796 :         return addsub_polmod_same(gel(x,1), gel(x,2), gel(y,2), &gadd);
     980                 :        588 :       return addsub_polmod(gel(x,1), gel(y,1), gel(x,2), gel(y,2), &gadd);
     981                 :     546300 :     case t_FFELT: return FF_add(x,y);
     982                 :            :     case t_POL:
     983                 :   14561713 :       vx = varn(x);
     984                 :   14561713 :       vy = varn(y);
     985         [ +  + ]:   14561713 :       if (vx != vy) {
     986         [ +  + ]:     788887 :         if (varncmp(vx, vy) < 0) return RgX_Rg_add(x, y);
     987                 :      18688 :         else                     return RgX_Rg_add(y, x);
     988                 :            :       }
     989                 :   13772826 :       return RgX_add(x, y);
     990                 :            :     case t_SER:
     991                 :      34875 :       vx = varn(x);
     992                 :      34875 :       vy = varn(y);
     993         [ -  + ]:      34875 :       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                 :      34875 :       return ser_add(x, y);
     998                 :            :     case t_RFRAC:
     999                 :    4073551 :       vx = varn(gel(x,2));
    1000                 :    4073551 :       vy = varn(gel(y,2));
    1001         [ +  + ]:    4073551 :       if (vx != vy) {
    1002         [ +  + ]:    1291903 :         if (varncmp(vx, vy) < 0) return add_rfrac_scal(x, y);
    1003                 :     536802 :         else                     return add_rfrac_scal(y, x);
    1004                 :            :       }
    1005                 :    2781648 :       return add_rfrac(x,y);
    1006                 :            :     case t_VEC:
    1007         [ -  + ]:     447203 :       if (lg(y) != lg(x)) pari_err_OP("+",x,y);
    1008                 :     447203 :       return RgV_add(x,y);
    1009                 :            :     case t_COL:
    1010         [ -  + ]:    4244654 :       if (lg(y) != lg(x)) pari_err_OP("+",x,y);
    1011                 :    4244654 :       return RgC_add(x,y);
    1012                 :            :     case t_MAT:
    1013                 :        644 :       lx = lg(x);
    1014         [ -  + ]:        644 :       if (lg(y) != lx) pari_err_OP("+",x,y);
    1015         [ -  + ]:        644 :       if (lx == 1) return cgetg(1, t_MAT);
    1016         [ +  + ]:        644 :       if (lgcols(y) != lgcols(x)) pari_err_OP("+",x,y);
    1017                 :        637 :       return RgM_add(x,y);
    1018                 :            : 
    1019                 :          0 :     default: pari_err_TYPE2("+",x,y);
    1020                 :            :   }
    1021                 :            :   /* tx != ty */
    1022         [ +  + ]:  121004809 :   if (tx > ty) { swap(x,y); lswap(tx,ty); }
    1023                 :            : 
    1024 [ +  + ][ +  +  :  121004809 :   if (is_const_t(ty)) switch(tx) /* tx < ty, is_const_t(tx) && is_const_t(ty) */
          +  +  -  +  -  
                      - ]
    1025                 :            :   {
    1026                 :            :     case t_INT:
    1027   [ +  +  +  +  :   96389373 :       switch(ty)
             +  +  +  - ]
    1028                 :            :       {
    1029                 :   59963366 :         case t_REAL: return addir(x,y);
    1030                 :            :         case t_INTMOD:
    1031                 :     424055 :           z = cgetg(3, t_INTMOD);
    1032                 :     424055 :           return add_intmod_same(z, gel(y,1), gel(y,2), modii(x, gel(y,1)));
    1033                 :   10363296 :         case t_FRAC: z = cgetg(3,t_FRAC);
    1034                 :   10363296 :           gel(z,1) = gerepileuptoint((pari_sp)z, addii(gel(y,1), mulii(gel(y,2),x)));
    1035                 :   10363296 :           gel(z,2) = icopy(gel(y,2)); return z;
    1036                 :   25331607 :         case t_COMPLEX: return addRc(x, y);
    1037                 :            :         case t_PADIC:
    1038         [ +  + ]:      73395 :           if (!signe(x)) return gcopy(y);
    1039                 :      68810 :           return addQp(x,y);
    1040                 :        567 :         case t_QUAD: return addRq(x, y);
    1041                 :     233087 :         case t_FFELT: return FF_Z_add(y,x);
    1042                 :            :       }
    1043                 :            : 
    1044                 :            :     case t_REAL:
    1045   [ +  +  +  - ]:    7752994 :       switch(ty)
    1046                 :            :       {
    1047                 :            :         case t_FRAC:
    1048         [ -  + ]:     742210 :           if (!signe(gel(y,1))) return rcopy(x);
    1049         [ +  + ]:     742210 :           if (!signe(x))
    1050                 :            :           {
    1051                 :       4585 :             lx = expi(gel(y,1)) - expi(gel(y,2)) - expo(x);
    1052         [ -  + ]:       4585 :             return lx <= 0? rcopy(x): fractor(y, nbits2prec(lx));
    1053                 :            :           }
    1054                 :     737625 :           av=avma; z=addir(gel(y,1),mulir(gel(y,2),x)); tetpil=avma;
    1055                 :     737625 :           return gerepile(av,tetpil,divri(z,gel(y,2)));
    1056                 :    7010777 :         case t_COMPLEX: return addRc(x, y);
    1057         [ -  + ]:          7 :         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   [ +  +  +  -  :       3964 :       switch(ty)
                   +  - ]
    1064                 :            :       {
    1065                 :       3500 :         case t_FRAC: { GEN X = gel(x,1);
    1066                 :       3500 :           z = cgetg(3, t_INTMOD);
    1067                 :       3500 :           p1 = Fp_div(gel(y,1), gel(y,2), X);
    1068                 :       3500 :           return add_intmod_same(z, X, p1, gel(x,2));
    1069                 :            :         }
    1070                 :            :         case t_FFELT:
    1071         [ -  + ]:        394 :           if (!equalii(gel(x,1),FF_p_i(y)))
    1072                 :          0 :             pari_err_OP("+",x,y);
    1073                 :        394 :           return FF_Z_add(y,gel(x,2));
    1074                 :         56 :         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                 :         14 :         case t_QUAD: return addRq(x, y);
    1080                 :            :       }
    1081                 :            : 
    1082                 :            :     case t_FRAC:
    1083   [ +  +  -  +  :      50939 :       switch (ty)
                      - ]
    1084                 :            :       {
    1085                 :      47971 :         case t_COMPLEX: return addRc(x, y);
    1086                 :            :         case t_PADIC:
    1087         [ -  + ]:       1526 :           if (!signe(gel(x,1))) return gcopy(y);
    1088                 :       1526 :           return addQp(x,y);
    1089                 :          0 :         case t_QUAD: return addRq(x, y);
    1090                 :       1442 :         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      [ +  +  - ]:         28 :       switch(ty)
    1098                 :            :       {
    1099                 :            :         case t_PADIC:
    1100         [ +  + ]:         21 :           return Zp_nosquare_m1(gel(y,2))? addRc(y, x): addTp(x, y);
    1101                 :            :         case t_QUAD:
    1102         [ -  + ]:          7 :           lx = precision(x); if (!lx) pari_err_OP("+",x,y);
    1103         [ -  + ]:          7 :           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   [ +  +  +  + ]:   16807511 :   switch(ty)
    1111                 :            :   {
    1112                 :            :     case t_MAT:
    1113         [ -  + ]:      12726 :       if (is_matvec_t(tx)) pari_err_TYPE2("+",x,y);
    1114         [ +  + ]:      12726 :       if (isrationalzero(x)) return gcopy(y);
    1115                 :      12614 :       return RgM_Rg_add(y, x);
    1116                 :            :     case t_COL:
    1117         [ -  + ]:      33497 :       if (tx == t_VEC) pari_err_TYPE2("+",x,y);
    1118                 :      33497 :       return RgC_Rg_add(y, x);
    1119                 :            :     case t_POLMOD: /* is_const_t(tx) in this case */
    1120                 :     592149 :       return addsub_polmod_scal(gel(y,1), gel(y,2), x, &gadd);
    1121                 :            :   }
    1122         [ +  + ]:   16169139 :   if (is_scalar_t(tx))  {
    1123         [ +  + ]:   13346646 :     if (tx == t_POLMOD)
    1124                 :            :     {
    1125                 :      19362 :       vx = varn(gel(x,1));
    1126                 :      19362 :       vy = gvar(y);
    1127         [ +  + ]:      19362 :       if (vx == vy) y = gmod(y, gel(x,1)); /* error if ty == t_SER */
    1128                 :            :       else
    1129         [ +  + ]:      15603 :         if (varncmp(vx,vy) > 0) return add_scal(y, x, ty);
    1130                 :       3801 :       return addsub_polmod_scal(gel(x,1), gel(x,2), y, &gadd);
    1131                 :            :     }
    1132                 :   13327284 :     return add_scal(y, x, ty);
    1133                 :            :   }
    1134                 :            :   /* x and y are not scalars, ty != t_MAT */
    1135                 :    2822493 :   vx = gvar(x);
    1136                 :    2822493 :   vy = gvar(y);
    1137         [ +  + ]:    2822493 :   if (vx != vy) { /* x or y is treated as a scalar */
    1138 [ +  - ][ +  + ]:       3056 :     if (is_vec_t(tx) || is_vec_t(ty)) pari_err_TYPE2("+",x,y);
    1139                 :       6098 :     return (varncmp(vx, vy) < 0)? add_scal(x, y, tx)
    1140         [ +  + ]:       3049 :                                 : add_scal(y, x, ty);
    1141                 :            :   }
    1142                 :            :   /* vx = vy */
    1143      [ +  +  - ]:    2819437 :   switch(tx)
    1144                 :            :   {
    1145                 :            :     case t_POL:
    1146      [ +  +  - ]:    2819108 :       switch (ty)
    1147                 :            :       {
    1148                 :            :         case t_SER:
    1149         [ +  + ]:       2681 :           if (lg(x) == 2) return gcopy(y);
    1150                 :       2667 :           i = lg(y) + valp(y) - RgX_val(x);
    1151         [ -  + ]:       2667 :           if (i < 3) return gcopy(y);
    1152                 :            : 
    1153                 :       2667 :           p1 = RgX_to_ser(x,i); y = ser_add(p1,y);
    1154                 :       2667 :           settyp(p1, t_VECSMALL); /* p1 left on stack */
    1155                 :       2667 :           return y;
    1156                 :            : 
    1157                 :    2816427 :         case t_RFRAC: return add_rfrac_scal(y, x);
    1158                 :            :       }
    1159                 :          0 :       break;
    1160                 :            : 
    1161                 :            :     case t_SER:
    1162         [ +  - ]:        329 :       if (ty == t_RFRAC)
    1163                 :            :       {
    1164                 :            :         GEN n, d;
    1165                 :            :         long vn, vd;
    1166                 :        329 :         av = avma;
    1167                 :        329 :         n = gel(y,1); vn = gval(n, vy);
    1168                 :        329 :         d = gel(y,2); vd = RgX_valrem(d, &d);
    1169                 :            : 
    1170                 :        329 :         l = lg(x) + valp(x) - (vn - vd);
    1171         [ -  + ]:        329 :         if (l < 3) { avma = av; return gcopy(x); }
    1172                 :            : 
    1173                 :            :         /* take advantage of y = t^n ! */
    1174         [ +  + ]:        329 :         if (degpol(d))
    1175                 :         56 :           y = gdiv(n, RgX_to_ser_inexact(d,l));
    1176                 :            :         else {
    1177                 :        273 :           y = gdiv(n, gel(d,2));
    1178         [ +  + ]:        273 :           if (gvar(y) == vy) y = RgX_to_ser(y,l); else y = scalarser(y, vy, l);
    1179                 :            :         }
    1180                 :        329 :         setvalp(y, valp(y) - vd);
    1181                 :        329 :         return gerepileupto(av, gadd(y, x));
    1182                 :            :       }
    1183                 :          0 :       break;
    1184                 :            :   }
    1185                 :          0 :   pari_err_TYPE2("+",x,y);
    1186                 :  890893062 :   return NULL; /* not reached */
    1187                 :            : }
    1188                 :            : 
    1189                 :            : GEN
    1190                 :    2654385 : gaddsg(long x, GEN y)
    1191                 :            : {
    1192                 :    2654385 :   long ty = typ(y);
    1193                 :            :   GEN z;
    1194                 :            : 
    1195   [ +  +  +  +  :    2654385 :   switch(ty)
                   +  + ]
    1196                 :            :   {
    1197                 :     126057 :     case t_INT:  return addsi(x,y);
    1198                 :    1134129 :     case t_REAL: return addsr(x,y);
    1199                 :            :     case t_INTMOD:
    1200                 :         14 :       z = cgetg(3, t_INTMOD);
    1201                 :         14 :       return add_intmod_same(z, gel(y,1), gel(y,2), modsi(x, gel(y,1)));
    1202                 :      29750 :     case t_FRAC: z = cgetg(3,t_FRAC);
    1203                 :      29750 :       gel(z,1) = gerepileuptoint((pari_sp)z, addii(gel(y,1), mulis(gel(y,2),x)));
    1204                 :      29750 :       gel(z,2) = icopy(gel(y,2)); return z;
    1205                 :            :     case t_COMPLEX:
    1206                 :    1018796 :       z = cgetg(3, t_COMPLEX);
    1207                 :    1018796 :       gel(z,1) = gaddsg(x, gel(y,1));
    1208                 :    1018796 :       gel(z,2) = gcopy(gel(y,2)); return z;
    1209                 :            : 
    1210                 :    2654385 :     default: return gadd(stoi(x), y);
    1211                 :            :   }
    1212                 :            : }
    1213                 :            : 
    1214                 :            : GEN
    1215                 :     296077 : gsubsg(long x, GEN y)
    1216                 :            : {
    1217                 :            :   GEN z, a, b;
    1218                 :            :   pari_sp av;
    1219                 :            : 
    1220   [ +  +  +  +  :     296077 :   switch(typ(y))
                   +  + ]
    1221                 :            :   {
    1222                 :     173128 :     case t_INT:  return subsi(x,y);
    1223                 :      58882 :     case t_REAL: return subsr(x,y);
    1224                 :            :     case t_INTMOD:
    1225                 :         49 :       z = cgetg(3, t_INTMOD); a = gel(y,1); b = gel(y,2);
    1226                 :         49 :       return add_intmod_same(z, a, Fp_neg(b,a), modsi(x, a));
    1227                 :         42 :     case t_FRAC: z = cgetg(3,t_FRAC); a = gel(y,1); b = gel(y,2);
    1228                 :         42 :       gel(z,1) = gerepileuptoint((pari_sp)z, subii(mulis(b,x), a));
    1229                 :         42 :       gel(z,2) = icopy(gel(y,2)); return z;
    1230                 :            :     case t_COMPLEX:
    1231                 :      41023 :       z = cgetg(3, t_COMPLEX);
    1232                 :      41023 :       gel(z,1) = gsubsg(x, gel(y,1));
    1233                 :      41023 :       gel(z,2) = gneg(gel(y,2)); return z;
    1234                 :            :   }
    1235                 :      22953 :   av = avma;
    1236                 :     296077 :   return gerepileupto(av, gadd(stoi(x), gneg_i(y)));
    1237                 :            : }
    1238                 :            : 
    1239                 :            : /********************************************************************/
    1240                 :            : /**                                                                **/
    1241                 :            : /**                          SUBTRACTION                           **/
    1242                 :            : /**                                                                **/
    1243                 :            : /********************************************************************/
    1244                 :            : 
    1245                 :            : GEN
    1246                 : 1325060297 : gsub(GEN x, GEN y)
    1247                 :            : {
    1248                 : 1325060297 :   long tx = typ(x), ty = typ(y);
    1249                 :            :   pari_sp av;
    1250                 :            :   GEN z;
    1251 [ +  + ][ +  +  : 1325060297 :   if (tx == ty) switch(tx) /* shortcut to generic case */
          +  +  +  +  +  
          +  +  +  +  +  
                +  +  - ]
    1252                 :            :   {
    1253                 : 1176590844 :     case t_INT: return subii(x,y);
    1254                 :  110721172 :     case t_REAL: return subrr(x,y);
    1255                 :     121279 :     case t_INTMOD:  { GEN p1, X = gel(x,1), Y = gel(y,1);
    1256                 :     121279 :       z = cgetg(3,t_INTMOD);
    1257 [ +  - ][ +  + ]:     121279 :       if (X==Y || equalii(X,Y))
    1258                 :     121272 :         return sub_intmod_same(z, X, gel(x,2), gel(y,2));
    1259                 :          7 :       gel(z,1) = gcdii(X,Y);
    1260                 :          7 :       av = avma; p1 = subii(gel(x,2),gel(y,2));
    1261                 :          7 :       gel(z,2) = gerepileuptoint(av, modii(p1, gel(z,1))); return z;
    1262                 :            :     }
    1263                 :    3523301 :     case t_FRAC: return addsub_frac(x,y, subii);
    1264                 :   13315483 :     case t_COMPLEX: z = cgetg(3,t_COMPLEX);
    1265                 :   13315483 :       gel(z,2) = gsub(gel(x,2),gel(y,2));
    1266         [ +  + ]:   13315483 :       if (isintzero(gel(z,2)))
    1267                 :            :       {
    1268                 :       4336 :         avma = (pari_sp)(z+3);
    1269                 :       4336 :         return gsub(gel(x,1),gel(y,1));
    1270                 :            :       }
    1271                 :   13311147 :       gel(z,1) = gsub(gel(x,1),gel(y,1));
    1272                 :   13311147 :       return z;
    1273                 :            :     case t_PADIC:
    1274         [ -  + ]:      88291 :       if (!equalii(gel(x,2),gel(y,2))) pari_err_OP("+",x,y);
    1275                 :      88291 :       return addsub_pp(x,y, subii);
    1276                 :        567 :     case t_QUAD: z = cgetg(4,t_QUAD);
    1277         [ -  + ]:        567 :       if (!ZX_equal(gel(x,1),gel(y,1))) pari_err_OP("+",x,y);
    1278                 :        567 :       gel(z,1) = ZX_copy(gel(x,1));
    1279                 :        567 :       gel(z,2) = gsub(gel(x,2),gel(y,2));
    1280                 :        567 :       gel(z,3) = gsub(gel(x,3),gel(y,3)); return z;
    1281                 :            :     case t_POLMOD:
    1282         [ +  + ]:     874349 :       if (RgX_equal_var(gel(x,1), gel(y,1)))
    1283                 :     874321 :         return addsub_polmod_same(gel(x,1), gel(x,2), gel(y,2), &gsub);
    1284                 :         28 :       return addsub_polmod(gel(x,1), gel(y,1), gel(x,2), gel(y,2), &gsub);
    1285                 :     183593 :     case t_FFELT: return FF_sub(x,y);
    1286                 :            :     case t_POL: {
    1287                 :    4855468 :       long vx = varn(x);
    1288                 :    4855468 :       long vy = varn(y);
    1289         [ +  + ]:    4855468 :       if (vx != vy) {
    1290         [ +  + ]:      10690 :         if (varncmp(vx, vy) < 0) return RgX_Rg_sub(x, y);
    1291                 :       1351 :         else                     return Rg_RgX_sub(x, y);
    1292                 :            :       }
    1293                 :    4844778 :       return RgX_sub(x, y);
    1294                 :            :     }
    1295                 :            :     case t_VEC:
    1296         [ -  + ]:      50547 :       if (lg(y) != lg(x)) pari_err_OP("+",x,y);
    1297                 :      50547 :       return RgV_sub(x,y);
    1298                 :            :     case t_COL:
    1299         [ -  + ]:    1163333 :       if (lg(y) != lg(x)) pari_err_OP("+",x,y);
    1300                 :    1163333 :       return RgC_sub(x,y);
    1301                 :            :     case t_MAT: {
    1302                 :       5278 :       long lx = lg(x);
    1303         [ -  + ]:       5278 :       if (lg(y) != lx) pari_err_OP("+",x,y);
    1304         [ -  + ]:       5278 :       if (lx == 1) return cgetg(1, t_MAT);
    1305         [ -  + ]:       5278 :       if (lgcols(y) != lgcols(x)) pari_err_OP("+",x,y);
    1306                 :       5278 :       return RgM_sub(x,y);
    1307                 :            :     }
    1308                 :    1662660 :     case t_RFRAC: case t_SER: break;
    1309                 :            : 
    1310                 :          0 :     default: pari_err_TYPE2("+",x,y);
    1311                 :            :   }
    1312                 :   13566792 :   av = avma;
    1313                 : 1325060297 :   return gerepileupto(av, gadd(x,gneg_i(y)));
    1314                 :            : }
    1315                 :            : 
    1316                 :            : /********************************************************************/
    1317                 :            : /**                                                                **/
    1318                 :            : /**                        MULTIPLICATION                          **/
    1319                 :            : /**                                                                **/
    1320                 :            : /********************************************************************/
    1321                 :            : static GEN
    1322                 :     189008 : mul_ser_scal(GEN y, GEN x) {
    1323                 :            :   long ly, i;
    1324                 :            :   GEN z;
    1325         [ +  + ]:     189008 :   if (isexactzero(x)) return gmul(RgX_get_0(y), x);
    1326         [ +  + ]:     187720 :   if (ser_isexactzero(y))
    1327                 :            :   {
    1328         [ +  - ]:        434 :     if (lg(y) == 2) return gcopy(y);
    1329                 :          0 :     return scalarser(gmul(x,gel(y,2)), varn(y), valp(y));
    1330                 :            :   }
    1331                 :     187286 :   z = cgetg_copy(y, &ly); z[1] = y[1];
    1332         [ +  + ]:     964770 :   for (i = 2; i < ly; i++) gel(z,i) = gmul(x,gel(y,i));
    1333                 :     189008 :   return normalize(z);
    1334                 :            : }
    1335                 :            : /* (n/d) * x, x "scalar" or polynomial in the same variable as d
    1336                 :            :  * [n/d a valid RFRAC]  */
    1337                 :            : static GEN
    1338                 :    9512961 : mul_rfrac_scal(GEN n, GEN d, GEN x)
    1339                 :            : {
    1340                 :    9512961 :   pari_sp av = avma;
    1341                 :            :   GEN z;
    1342                 :            : 
    1343      [ -  +  + ]:    9512961 :   switch(typ(x))
    1344                 :            :   {
    1345                 :            :     case t_PADIC:
    1346                 :          0 :       n = gmul(n, x);
    1347         [ #  # ]:          0 :       d = gcvtop(d, gel(x,2), signe(gel(x,4))? precp(x): 1);
    1348                 :          0 :       return gerepileupto(av, gdiv(n,d));
    1349                 :            : 
    1350                 :            :     case t_INTMOD: case t_POLMOD:
    1351                 :         14 :       n = gmul(n, x);
    1352                 :         14 :       d = gmul(d, gmodulo(gen_1, gel(x,1)));
    1353                 :         14 :       return gerepileupto(av, gdiv(n,d));
    1354                 :            :   }
    1355                 :    9512947 :   z = gred_rfrac2_i(x, d);
    1356                 :    9512947 :   n = simplify_shallow(n);
    1357         [ +  + ]:    9512947 :   if (typ(z) == t_RFRAC)
    1358                 :            :   {
    1359                 :    7119711 :     n = gmul(gel(z,1), n);
    1360                 :    7119711 :     d = gel(z,2);
    1361 [ +  + ][ +  + ]:    7119711 :     if (typ(n) == t_POL && varncmp(varn(n), varn(d)) < 0)
    1362                 :        168 :       z = RgX_Rg_div(n, d);
    1363                 :            :     else
    1364                 :    7119711 :       z = gred_rfrac_simple(n, d);
    1365                 :            :   }
    1366                 :            :   else
    1367                 :    2393236 :     z = gmul(z, n);
    1368                 :    9512961 :   return gerepileupto(av, z);
    1369                 :            : }
    1370                 :            : static GEN
    1371                 :   54518958 : mul_scal(GEN y, GEN x, long ty)
    1372                 :            : {
    1373   [ +  +  +  -  :   54518958 :   switch(ty)
                      - ]
    1374                 :            :   {
    1375                 :            :     case t_POL:
    1376         [ +  + ]:   46290189 :       if (lg(y) == 2) return scalarpol(gmul(gen_0,x), varn(y));
    1377                 :   45366395 :       return RgX_Rg_mul(y, x);
    1378                 :     117244 :     case t_SER: return mul_ser_scal(y, x);
    1379                 :    8111525 :     case t_RFRAC: return mul_rfrac_scal(gel(y,1),gel(y,2), x);
    1380                 :            :     case t_QFI: case t_QFR:
    1381 [ #  # ][ #  # ]:          0 :       if (typ(x) == t_INT && gequal1(x)) return gcopy(y); /* fall through */
    1382                 :            :   }
    1383                 :          0 :   pari_err_TYPE2("*",x,y);
    1384                 :   54518951 :   return NULL; /* not reached */
    1385                 :            : }
    1386                 :            : 
    1387                 :            : static GEN
    1388                 :     160830 : mul_gen_rfrac(GEN X, GEN Y)
    1389                 :            : {
    1390                 :     160830 :   GEN y1 = gel(Y,1), y2 = gel(Y,2);
    1391                 :     160830 :   long vx = gvar(X), vy = varn(y2);
    1392         [ +  + ]:     166570 :   return (varncmp(vx, vy) <= 0)? mul_scal(Y, X, typ(Y)):
    1393                 :       5740 :                                  gred_rfrac_simple(gmul(y1,X), y2);
    1394                 :            : }
    1395                 :            : /* (x1/x2) * (y1/y2) */
    1396                 :            : static GEN
    1397                 :    7746396 : mul_rfrac(GEN x1, GEN x2, GEN y1, GEN y2)
    1398                 :            : {
    1399                 :            :   GEN z, X, Y;
    1400                 :    7746396 :   pari_sp av = avma;
    1401                 :            : 
    1402                 :    7746396 :   X = gred_rfrac2_i(x1, y2);
    1403                 :    7746396 :   Y = gred_rfrac2_i(y1, x2);
    1404         [ +  + ]:    7746396 :   if (typ(X) == t_RFRAC)
    1405                 :            :   {
    1406         [ +  + ]:    6479540 :     if (typ(Y) == t_RFRAC) {
    1407                 :    6399615 :       x1 = gel(X,1);
    1408                 :    6399615 :       x2 = gel(X,2);
    1409                 :    6399615 :       y1 = gel(Y,1);
    1410                 :    6399615 :       y2 = gel(Y,2);
    1411                 :    6399615 :       z = gred_rfrac_simple(gmul(x1,y1), gmul(x2,y2));
    1412                 :            :     } else
    1413                 :      79925 :       z = mul_gen_rfrac(Y, X);
    1414                 :            :   }
    1415         [ +  + ]:    1266856 :   else if (typ(Y) == t_RFRAC)
    1416                 :      80905 :     z = mul_gen_rfrac(X, Y);
    1417                 :            :   else
    1418                 :    1185951 :     z = gmul(X, Y);
    1419                 :    7746396 :   return gerepileupto(av, z);
    1420                 :            : }
    1421                 :            : /* (x1/x2) /y2, x2 and y2 are t_POL in the same variable */
    1422                 :            : static GEN
    1423                 :     253113 : div_rfrac_pol(GEN x1, GEN x2, GEN y2)
    1424                 :            : {
    1425                 :     253113 :   pari_sp av = avma;
    1426                 :     253113 :   GEN X = gred_rfrac2_i(x1, y2);
    1427 [ +  + ][ +  + ]:     253113 :   if (typ(X) == t_RFRAC && varn(gel(X,2)) == varn(x2))
    1428                 :            :   {
    1429                 :     246561 :     x2 = RgX_mul(gel(X,2), x2);
    1430                 :     246561 :     x1 = gel(X,1);
    1431                 :            :   }
    1432                 :            :   else
    1433                 :       6552 :     x1 = X;
    1434                 :     253113 :   return gerepileupto(av, gred_rfrac_simple(x1, x2));
    1435                 :            : }
    1436                 :            : 
    1437                 :            : /* Mod(y, Y) * x,  assuming x scalar */
    1438                 :            : static GEN
    1439                 :    1054179 : mul_polmod_scal(GEN Y, GEN y, GEN x)
    1440                 :            : {
    1441                 :    1054179 :   GEN z = cgetg(3,t_POLMOD);
    1442                 :    1054179 :   gel(z,1) = RgX_copy(Y);
    1443                 :    1054179 :   gel(z,2) = gmul(x,y); return z;
    1444                 :            : }
    1445                 :            : 
    1446                 :            : /* cf mulqq */
    1447                 :            : static GEN
    1448                 :     987751 : quad_polmod_mul(GEN P, GEN x, GEN y)
    1449                 :            : {
    1450                 :     987751 :   GEN T = cgetg(4, t_POL), b = gel(P,3), c = gel(P,2), p1, p2, p3, p4;
    1451                 :     987751 :   pari_sp tetpil, av = avma;
    1452                 :     987751 :   T[1] = x[1];
    1453                 :     987751 :   p2 = gmul(gel(x,2), gel(y,2));
    1454                 :     987751 :   p3 = gmul(gel(x,3), gel(y,3));
    1455                 :     987751 :   p1 = gmul(gneg_i(c),p3);
    1456                 :            :   /* operands are usually small: gadd ~ gmul and Karatsuba is a waste */
    1457         [ +  - ]:     987751 :   if (typ(b) == t_INT)
    1458                 :            :   {
    1459         [ +  + ]:     987751 :     if (signe(b))
    1460                 :            :     {
    1461                 :     730372 :       p4 = gadd(gmul(gel(x,2), gel(y,3)), gmul(gel(x,3), gel(y,2)));
    1462         [ +  + ]:     730372 :       if (is_pm1(b))
    1463                 :            :       {
    1464         [ +  + ]:     730288 :         if (signe(b) > 0) p3 = gneg(p3);
    1465                 :            :       }
    1466                 :            :       else
    1467                 :         84 :         p3 = gmul(negi(b), p3);
    1468                 :            :     }
    1469                 :            :     else
    1470                 :            :     {
    1471                 :     257379 :       p3 = gmul(gel(x,2),gel(y,3));
    1472                 :     257379 :       p4 = gmul(gel(x,3),gel(y,2));
    1473                 :            :     }
    1474                 :            :   }
    1475                 :            :   else
    1476                 :            :   {
    1477                 :          0 :     p4 = gadd(gmul(gel(x,2), gel(y,3)), gmul(gel(x,3), gel(y,2)));
    1478                 :          0 :     p3 = gmul(gneg_i(b), p3);
    1479                 :            :   }
    1480                 :     987751 :   tetpil = avma;
    1481                 :     987751 :   gel(T,2) = gadd(p2, p1);
    1482                 :     987751 :   gel(T,3) = gadd(p4, p3);
    1483                 :     987751 :   gerepilecoeffssp(av,tetpil,T+2,2);
    1484                 :     987751 :   return normalizepol_lg(T,4);
    1485                 :            : }
    1486                 :            : /* Mod(x,T) * Mod(y,T) */
    1487                 :            : static GEN
    1488                 :    1635850 : mul_polmod_same(GEN T, GEN x, GEN y)
    1489                 :            : {
    1490                 :    1635850 :   GEN z = cgetg(3,t_POLMOD), a;
    1491                 :    1635850 :   long v = varn(T), lx = lg(x), ly = lg(y);
    1492                 :    1635850 :   gel(z,1) = RgX_copy(T);
    1493                 :            :   /* x * y mod T optimised */
    1494 [ +  + ][ +  + ]:    1635850 :   if (typ(x) != t_POL || varn(x) != v || lx <= 3
                 [ +  + ]
    1495 [ +  + ][ +  - ]:    1283683 :    || typ(y) != t_POL || varn(y) != v || ly <= 3)
                 [ +  + ]
    1496                 :     477629 :     a = gmul(x, y);
    1497                 :            :   else
    1498                 :            :   {
    1499 [ +  + ][ +  + ]:    1158221 :     if (lg(T) == 5 && isint1(gel(T,4))) /* quadratic fields */
    1500                 :     986575 :       a = quad_polmod_mul(T, x, y);
    1501                 :            :     else
    1502                 :            :     {
    1503                 :     171646 :       pari_sp av = avma;
    1504                 :     171646 :       GEN p = NULL;
    1505 [ +  + ][ +  + ]:     171646 :       if (RgX_is_FpX(T, &p) && RgX_is_FpX(x, &p) && RgX_is_FpX(y, &p) && p)
         [ +  + ][ +  + ]
    1506                 :            :       {
    1507                 :      37121 :         T = RgX_to_FpX(T, p); x = RgX_to_FpX(x, p); y = RgX_to_FpX(y, p);
    1508         [ +  + ]:      37121 :         if (lgefint(p) == 3)
    1509                 :            :         {
    1510                 :      32284 :           ulong pp = p[2];
    1511                 :      32284 :           a = Flxq_mul(ZX_to_Flx(x, pp), ZX_to_Flx(y, pp), ZX_to_Flx(T, pp), pp);
    1512                 :      32284 :           a = Flx_to_ZX(a);
    1513                 :            :         }
    1514                 :            :         else
    1515                 :       4837 :           a = FpXQ_mul(x, y, T, p);
    1516                 :      37121 :         a = FpX_to_mod(a, p);
    1517                 :            :       }
    1518                 :            :       else
    1519                 :     134525 :         a = RgXQ_mul(x, y, gel(z,1));
    1520                 :     171646 :       a = gerepileupto(av, a);
    1521                 :            :     }
    1522                 :            :   }
    1523                 :    1635850 :   gel(z,2) = a; return z;
    1524                 :            : }
    1525                 :            : static GEN
    1526                 :      21703 : sqr_polmod(GEN T, GEN x)
    1527                 :            : {
    1528                 :      21703 :   GEN a, z = cgetg(3,t_POLMOD);
    1529                 :      21703 :   gel(z,1) = RgX_copy(T);
    1530 [ +  + ][ +  - ]:      21703 :   if (typ(x) != t_POL || varn(x) != varn(T) || lg(x) <= 3)
                 [ +  + ]
    1531                 :       2662 :     a = gsqr(x);
    1532                 :            :   else
    1533                 :            :   {
    1534                 :      19041 :     pari_sp av = avma;
    1535                 :      19041 :     GEN p = NULL;
    1536 [ +  - ][ +  + ]:      19041 :     if (RgX_is_FpX(T, &p) && RgX_is_FpX(x, &p) && p)
                 [ +  + ]
    1537                 :            :     {
    1538                 :         14 :       T = RgX_to_FpX(T, p); x = RgX_to_FpX(x, p);
    1539         [ +  + ]:         14 :       if (lgefint(p) == 3)
    1540                 :            :       {
    1541                 :          7 :         ulong pp = p[2];
    1542                 :          7 :         a = Flxq_sqr(ZX_to_Flx(x, pp), ZX_to_Flx(T, pp), pp);
    1543                 :          7 :         a = Flx_to_ZX(a);
    1544                 :            :       }
    1545                 :            :       else
    1546                 :          7 :         a = FpXQ_sqr(x, T, p);
    1547                 :         14 :       a = FpX_to_mod(a, p);
    1548                 :            :     }
    1549                 :            :     else
    1550                 :      19027 :       a = RgXQ_sqr(x, gel(z,1));
    1551                 :      19041 :     a = gerepileupto(av, a);
    1552                 :            :   }
    1553                 :      21703 :   gel(z,2) = a; return z;
    1554                 :            : }
    1555                 :            : /* Mod(x,X) * Mod(y,Y) */
    1556                 :            : static GEN
    1557                 :       1148 : mul_polmod(GEN X, GEN Y, GEN x, GEN y)
    1558                 :            : {
    1559                 :       1148 :   long T[3] = { evaltyp(t_POLMOD) | _evallg(3),0,0 };
    1560                 :       1148 :   long vx = varn(X), vy = varn(Y);
    1561                 :       1148 :   GEN z = cgetg(3,t_POLMOD);
    1562                 :            : 
    1563         [ -  + ]:       1148 :   if (vx==vy) {
    1564                 :            :     pari_sp av;
    1565                 :          0 :     gel(z,1) = RgX_gcd(X,Y); av = avma;
    1566                 :          0 :     gel(z,2) = gerepileupto(av, gmod(gmul(x, y), gel(z,1)));
    1567                 :          0 :     return z;
    1568                 :            :   }
    1569         [ +  + ]:       1148 :   if (varncmp(vx, vy) < 0)
    1570                 :         21 :   { gel(z,1) = RgX_copy(X); gel(T,1) = Y; gel(T,2) = y; y = T; }
    1571                 :            :   else
    1572                 :       1127 :   { gel(z,1) = RgX_copy(Y); gel(T,1) = X; gel(T,2) = x; x = T; }
    1573                 :       1148 :   gel(z,2) = gmul(x, y); return z;
    1574                 :            : }
    1575                 :            : 
    1576                 :            : #if 0 /* used by 3M only */
    1577                 :            : /* set z = x+y and return 1 if x,y have the same sign
    1578                 :            :  * set z = x-y and return 0 otherwise */
    1579                 :            : static int
    1580                 :            : did_add(GEN x, GEN y, GEN *z)
    1581                 :            : {
    1582                 :            :   long tx = typ(x), ty = typ(y);
    1583                 :            :   if (tx == ty) switch(tx)
    1584                 :            :   {
    1585                 :            :     case t_INT: *z = addii(x,y); return 1;
    1586                 :            :     case t_FRAC: *z = addsub_frac(x,y,addii); return 1;
    1587                 :            :     case t_REAL:
    1588                 :            :       if (signe(x) == -signe(y))
    1589                 :            :       { *z = subrr(x,y); return 0; }
    1590                 :            :       else
    1591                 :            :       { *z = addrr(x,y); return 1; }
    1592                 :            :   }
    1593                 :            :   if (tx == t_REAL) switch(ty)
    1594                 :            :   {
    1595                 :            :     case t_INT:
    1596                 :            :       if (signe(x) == -signe(y))
    1597                 :            :       { *z = subri(x,y); return 0; }
    1598                 :            :       else
    1599                 :            :       { *z = addri(x,y); return 1; }
    1600                 :            :     case t_FRAC:
    1601                 :            :       if (signe(x) == -signe(gel(y,1)))
    1602                 :            :       { *z = gsub(x,y); return 0; }
    1603                 :            :       else
    1604                 :            :       { *z = gadd(x,y); return 1; }
    1605                 :            :   }
    1606                 :            :   else if (ty == t_REAL) switch(tx)
    1607                 :            :   {
    1608                 :            :     case t_INT:
    1609                 :            :       if (signe(x) == -signe(y))
    1610                 :            :       { *z = subir(x,y); return 0; }
    1611                 :            :       else
    1612                 :            :       { *z = addir(x,y); return 1; }
    1613                 :            :     case t_FRAC:
    1614                 :            :       if (signe(gel(x,1)) == -signe(y))
    1615                 :            :       { *z = gsub(x,y); return 0; }
    1616                 :            :       else
    1617                 :            :       { *z = gadd(x,y); return 1; }
    1618                 :            :   }
    1619                 :            :   *z = gadd(x,y); return 1;
    1620                 :            : }
    1621                 :            : #endif
    1622                 :            : /* x * I * y, x t_COMPLEX with non-intzero real part, y non-intzero "scalar" */
    1623                 :            : static GEN
    1624                 :     691756 : mulcIR(GEN x, GEN y)
    1625                 :            : {
    1626                 :     691756 :   GEN z = cgetg(3,t_COMPLEX);
    1627                 :     691756 :   pari_sp av = avma;
    1628                 :     691756 :   gel(z,1) = gerepileupto(av, gneg(gmul(y,gel(x,2))));
    1629                 :     691756 :   gel(z,2) = gmul(y, gel(x,1));
    1630                 :     691756 :   return z;
    1631                 :            : 
    1632                 :            : }
    1633                 :            : /* x,y COMPLEX */
    1634                 :            : static GEN
    1635                 :   48585928 : mulcc(GEN x, GEN y)
    1636                 :            : {
    1637                 :   48585928 :   GEN xr = gel(x,1), xi = gel(x,2);
    1638                 :   48585928 :   GEN yr = gel(y,1), yi = gel(y,2);
    1639                 :            :   GEN p1, p2, p3, p4, z;
    1640                 :            :   pari_sp tetpil, av;
    1641                 :            : 
    1642         [ +  + ]:   48585928 :   if (isintzero(xr))
    1643                 :            :   {
    1644         [ +  + ]:     694349 :     if (isintzero(yr)) {
    1645                 :     110788 :       av = avma;
    1646                 :     110788 :       return gerepileupto(av, gneg(gmul(xi,yi)));
    1647                 :            :     }
    1648                 :     583561 :     return mulcIR(y, xi);
    1649                 :            :   }
    1650         [ +  + ]:   47891579 :   if (isintzero(yr)) return mulcIR(x, yi);
    1651                 :            : 
    1652                 :   47783384 :   z = cgetg(3,t_COMPLEX); av = avma;
    1653                 :            : #if 0
    1654                 :            :   /* 3M method avoiding catastrophic cancellation, BUT loses accuracy due to
    1655                 :            :    * e.g. xr + xi if exponents differ */
    1656                 :            :   if (did_add(xr, xi, &p3))
    1657                 :            :   {
    1658                 :            :     if (did_add(yr, yi, &p4)) {
    1659                 :            :     /* R = xr*yr - xi*yi
    1660                 :            :      * I = (xr+xi)(yr+yi) - xr*yr - xi*yi */
    1661                 :            :       p1 = gmul(xr,yr);
    1662                 :            :       p2 = gmul(xi,yi); p2 = gneg(p2);
    1663                 :            :       p3 = gmul(p3, p4);
    1664                 :            :       p4 = gsub(p2, p1);
    1665                 :            :     } else {
    1666                 :            :     /* R = (xr + xi) * (yr - yi) + (xr * yi - xi * yr)
    1667                 :            :      * I = xr*yi + xi*yr */
    1668                 :            :       p1 = gmul(p3,p4);
    1669                 :            :       p3 = gmul(xr,yi);
    1670                 :            :       p4 = gmul(xi,yr);
    1671                 :            :       p2 = gsub(p3, p4);
    1672                 :            :     }
    1673                 :            :   } else {
    1674                 :            :     if (did_add(yr, yi, &p4)) {
    1675                 :            :      /* R = (xr - xi) * (yr + yi) + (xi * yr - xr * yi)
    1676                 :            :       * I = xr*yi +xi*yr */
    1677                 :            :       p1 = gmul(p3,p4);
    1678                 :            :       p3 = gmul(xr,yi);
    1679                 :            :       p4 = gmul(xi,yr);
    1680                 :            :       p2 = gsub(p4, p3);
    1681                 :            :     } else {
    1682                 :            :     /* R = xr*yr - xi*yi
    1683                 :            :      * I = -(xr-xi)(yr-yi) + xr*yr + xi*yi */
    1684                 :            :       p3 = gneg( gmul(p3, p4) );
    1685                 :            :       p1 = gmul(xr,yr);
    1686                 :            :       p2 = gmul(xi,yi);
    1687                 :            :       p4 = gadd(p1, p2);
    1688                 :            : 
    1689                 :            :       p2 = gneg(p2);
    1690                 :            :     }
    1691                 :            :   }
    1692                 :            :   tetpil = avma;
    1693                 :            :   gel(z,1) = gadd(p1,p2);
    1694                 :            :   gel(z,2) = gadd(p3,p4);
    1695                 :            : #else
    1696 [ +  + ][ +  + ]:   47783384 :   if (typ(xr)==t_INT && typ(yr)==t_INT && typ(xi)==t_INT && typ(yi)==t_INT)
         [ +  - ][ +  + ]
    1697                 :            :   { /* 3M formula */
    1698                 :        161 :     p3 = addii(xr,xi);
    1699                 :        161 :     p4 = addii(yr,yi);
    1700                 :        161 :     p1 = mulii(xr,yr);
    1701                 :        161 :     p2 = mulii(xi,yi);
    1702                 :        161 :     p3 = mulii(p3,p4);
    1703                 :        161 :     p4 = addii(p2,p1);
    1704                 :        161 :     tetpil = avma;
    1705                 :        161 :     gel(z,1) = subii(p1,p2);
    1706                 :        161 :     gel(z,2) = subii(p3,p4);
    1707         [ +  + ]:        161 :     if (!signe(gel(z,2)))
    1708                 :         49 :       return gerepileuptoint((pari_sp)(z+3), gel(z,1));
    1709                 :            :   }
    1710                 :            :   else
    1711                 :            :   { /* naive 4M formula: avoid all loss of accuracy */
    1712                 :   47783223 :     p1 = gmul(xr,yr);
    1713                 :   47783223 :     p2 = gmul(xi,yi);
    1714                 :   47783223 :     p3 = gmul(xr,yi);
    1715                 :   47783223 :     p4 = gmul(xi,yr);
    1716                 :   47783223 :     tetpil = avma;
    1717                 :   47783223 :     gel(z,1) = gsub(p1,p2);
    1718                 :   47783223 :     gel(z,2) = gadd(p3,p4);
    1719         [ +  + ]:   47783223 :     if (isintzero(gel(z,2)))
    1720                 :            :     {
    1721                 :       7522 :       cgiv(gel(z,2));
    1722                 :       7522 :       return gerepileupto((pari_sp)(z+3), gel(z,1));
    1723                 :            :     }
    1724                 :            :   }
    1725                 :            : #endif
    1726                 :            : 
    1727                 :   48585928 :   gerepilecoeffssp(av,tetpil, z+1,2); return z;
    1728                 :            : }
    1729                 :            : /* x,y PADIC */
    1730                 :            : static GEN
    1731                 :     299649 : mulpp(GEN x, GEN y) {
    1732                 :     299649 :   long l = valp(x) + valp(y);
    1733                 :            :   pari_sp av;
    1734                 :            :   GEN z, t;
    1735         [ -  + ]:     299649 :   if (!equalii(gel(x,2),gel(y,2))) pari_err_OP("*",x,y);
    1736         [ +  + ]:     299649 :   if (!signe(gel(x,4))) return zeropadic(gel(x,2), l);
    1737         [ +  + ]:     298578 :   if (!signe(gel(y,4))) return zeropadic(gel(x,2), l);
    1738                 :            : 
    1739         [ +  + ]:     297836 :   t = (precp(x) > precp(y))? y: x;
    1740                 :     297836 :   z = cgetp(t); setvalp(z,l); av = avma;
    1741                 :     297836 :   affii(remii(mulii(gel(x,4),gel(y,4)), gel(t,3)), gel(z,4));
    1742                 :     299649 :   avma = av; return z;
    1743                 :            : }
    1744                 :            : /* x,y QUAD */
    1745                 :            : static GEN
    1746                 :       1344 : mulqq(GEN x, GEN y) {
    1747                 :       1344 :   GEN z = cgetg(4,t_QUAD);
    1748                 :       1344 :   GEN p1, p2, p3, p4, P = gel(x,1), b = gel(P,3), c = gel(P,2);
    1749                 :            :   pari_sp av, tetpil;
    1750         [ -  + ]:       1344 :   if (!ZX_equal(P, gel(y,1))) pari_err_OP("*",x,y);
    1751                 :            : 
    1752                 :       1344 :   gel(z,1) = ZX_copy(P); av = avma;
    1753                 :       1344 :   p2 = gmul(gel(x,2),gel(y,2));
    1754                 :       1344 :   p3 = gmul(gel(x,3),gel(y,3));
    1755                 :       1344 :   p1 = gmul(gneg_i(c),p3);
    1756                 :            : 
    1757         [ +  + ]:       1344 :   if (signe(b))
    1758                 :       1239 :     p4 = gadd(gmul(gel(x,2),gel(y,3)), gmul(gel(x,3),gel(y,2)));
    1759                 :            :   else
    1760                 :            :   {
    1761                 :        105 :     p3 = gmul(gel(x,2),gel(y,3));
    1762                 :        105 :     p4 = gmul(gel(x,3),gel(y,2));
    1763                 :            :   }
    1764                 :       1344 :   tetpil = avma;
    1765                 :       1344 :   gel(z,2) = gadd(p2,p1);
    1766                 :       1344 :   gel(z,3) = gadd(p4,p3);
    1767                 :       1344 :   gerepilecoeffssp(av,tetpil,z+2,2); return z;
    1768                 :            : }
    1769                 :            : 
    1770                 :            : GEN
    1771                 :    1682800 : mulcxI(GEN x)
    1772                 :            : {
    1773                 :            :   GEN z;
    1774      [ +  +  + ]:    1682800 :   switch(typ(x))
    1775                 :            :   {
    1776                 :            :     case t_INT: case t_REAL: case t_FRAC:
    1777                 :     409524 :       return mkcomplex(gen_0, x);
    1778                 :            :     case t_COMPLEX:
    1779         [ +  + ]:    1273220 :       if (isintzero(gel(x,1))) return gneg(gel(x,2));
    1780                 :    1271099 :       z = cgetg(3,t_COMPLEX);
    1781                 :    1271099 :       gel(z,1) = gneg(gel(x,2));
    1782                 :    1271099 :       gel(z,2) = gel(x,1); return z;
    1783                 :            :     default:
    1784                 :    1682800 :       return gmul(gen_I(), x);
    1785                 :            :   }
    1786                 :            : }
    1787                 :            : GEN
    1788                 :      47852 : mulcxmI(GEN x)
    1789                 :            : {
    1790                 :            :   GEN z;
    1791      [ +  +  + ]:      47852 :   switch(typ(x))
    1792                 :            :   {
    1793                 :            :     case t_INT: case t_REAL: case t_FRAC:
    1794                 :       2065 :       return mkcomplex(gen_0, gneg(x));
    1795                 :            :     case t_COMPLEX:
    1796         [ +  + ]:      45731 :       if (isintzero(gel(x,1))) return gel(x,2);
    1797                 :      44744 :       z = cgetg(3,t_COMPLEX);
    1798                 :      44744 :       gel(z,1) = gel(x,2);
    1799                 :      44744 :       gel(z,2) = gneg(gel(x,1)); return z;
    1800                 :            :     default:
    1801                 :      47852 :       return gmul(mkcomplex(gen_0, gen_m1), x);
    1802                 :            :   }
    1803                 :            : }
    1804                 :            : 
    1805                 :            : /* fill in coefficients of t_SER z from coeffs of t_POL y */
    1806                 :            : static GEN
    1807                 :     117013 : fill_ser(GEN z, GEN y)
    1808                 :            : {
    1809                 :     117013 :   long i, lx = lg(z), ly = lg(y);
    1810         [ +  + ]:     117013 :   if (ly >= lx) {
    1811         [ +  + ]:     500670 :     for (i = 2; i < lx; i++) gel(z,i) = gel(y,i);
    1812                 :            :   } else {
    1813         [ +  + ]:      15701 :     for (i = 2; i < ly; i++) gel(z,i) = gel(y,i);
    1814         [ +  + ]:      12537 :     for (     ; i < lx; i++) gel(z,i) = gen_0;
    1815                 :            :   }
    1816                 :     117013 :   return normalize(z);
    1817                 :            : }
    1818                 :            : 
    1819                 :            : GEN
    1820                 : 2378587754 : gmul(GEN x, GEN y)
    1821                 :            : {
    1822                 :            :   long tx, ty, lx, ly, vx, vy, i, l;
    1823                 :            :   pari_sp av, tetpil;
    1824                 :            :   GEN z, p1, p2;
    1825                 :            : 
    1826         [ +  + ]: 2378587754 :   if (x == y) return gsqr(x);
    1827                 : 1461315853 :   tx = typ(x); ty = typ(y);
    1828 [ +  + ][ +  +  : 1461315853 :   if (tx == ty) switch(tx)
          +  +  +  +  +  
          +  +  +  +  +  
             +  +  +  -  
                      - ]
    1829                 :            :   {
    1830                 :  745056858 :     case t_INT: return mulii(x,y);
    1831                 :  353593542 :     case t_REAL: return mulrr(x,y);
    1832                 :     882749 :     case t_INTMOD: { GEN X = gel(x,1), Y = gel(y,1);
    1833                 :     882749 :       z = cgetg(3,t_INTMOD);
    1834 [ +  - ][ +  - ]:     882749 :       if (X==Y || equalii(X,Y))
    1835                 :     882749 :         return mul_intmod_same(z, X, gel(x,2), gel(y,2));
    1836                 :          0 :       gel(z,1) = gcdii(X,Y); av = avma; p1 = mulii(gel(x,2),gel(y,2));
    1837                 :          0 :       gel(z,2) = gerepileuptoint(av, remii(p1, gel(z,1))); return z;
    1838                 :            :     }
    1839                 :            :     case t_FRAC:
    1840                 :            :     {
    1841                 :    6085987 :       GEN x1 = gel(x,1), x2 = gel(x,2);
    1842                 :    6085987 :       GEN y1 = gel(y,1), y2 = gel(y,2);
    1843                 :    6085987 :       z=cgetg(3,t_FRAC);
    1844                 :    6085987 :       p1 = gcdii(x1, y2);
    1845         [ +  + ]:    6085987 :       if (!is_pm1(p1)) { x1 = diviiexact(x1,p1); y2 = diviiexact(y2,p1); }
    1846                 :    6085987 :       p1 = gcdii(x2, y1);
    1847         [ +  + ]:    6085987 :       if (!is_pm1(p1)) { x2 = diviiexact(x2,p1); y1 = diviiexact(y1,p1); }
    1848                 :    6085987 :       tetpil = avma;
    1849                 :    6085987 :       gel(z,2) = mulii(x2,y2);
    1850                 :    6085987 :       gel(z,1) = mulii(x1,y1);
    1851         [ +  + ]:    6085987 :       fix_frac_if_int_GC(z,tetpil); return z;
    1852                 :            :     }
    1853                 :   48215879 :     case t_COMPLEX: return mulcc(x, y);
    1854                 :     259938 :     case t_PADIC: return mulpp(x, y);
    1855                 :       1022 :     case t_QUAD: return mulqq(x, y);
    1856                 :    1493934 :     case t_FFELT: return FF_mul(x, y);
    1857                 :            :     case t_POLMOD:
    1858         [ +  + ]:    1496046 :       if (RgX_equal_var(gel(x,1), gel(y,1)))
    1859                 :    1494898 :         return mul_polmod_same(gel(x,1), gel(x,2), gel(y,2));
    1860                 :       1148 :       return mul_polmod(gel(x,1), gel(y,1), gel(x,2), gel(y,2));
    1861                 :            :     case t_POL:
    1862                 :   33786160 :       vx = varn(x);
    1863                 :   33786160 :       vy = varn(y);
    1864         [ +  + ]:   33786160 :       if (vx != vy) {
    1865         [ +  + ]:    4837855 :         if (varncmp(vx, vy) < 0) return RgX_Rg_mul(x, y);
    1866                 :    1990103 :         else                     return RgX_Rg_mul(y, x);
    1867                 :            :       }
    1868 [ +  + ][ +  + ]:   28948305 :       if (RgX_is_ZX(x) && RgX_is_ZX(y)) return ZX_mul(x,y);
    1869                 :    5236374 :       return RgX_mul(x, y);
    1870                 :            : 
    1871                 :            :     case t_SER: {
    1872                 :     117181 :       GEN p = NULL;
    1873                 :     117181 :       vx = varn(x);
    1874                 :     117181 :       vy = varn(y);
    1875         [ -  + ]:     117181 :       if (vx != vy) {
    1876         [ #  # ]:          0 :         if (varncmp(vx, vy) < 0) return mul_ser_scal(x, y);
    1877                 :          0 :         else                     return mul_ser_scal(y, x);
    1878                 :            :       }
    1879                 :     117181 :       lx = lg(x);
    1880         [ +  + ]:     117181 :       ly = lg(y); if (lx > ly) { lx = ly; swap(x, y); }
    1881         [ +  + ]:     117181 :       if (lx == 2) return zeroser(vx, valp(x)+valp(y));
    1882                 :     117006 :       z = cgetg(lx,t_SER);
    1883                 :     117006 :       z[1] = evalvalp(valp(x)+valp(y)) | evalvarn(vx) | evalsigne(1);
    1884                 :     117006 :       x = ser2pol_i(x, lx);
    1885                 :     117006 :       y = ser2pol_i(y, lx);
    1886 [ +  + ][ +  + ]:     117006 :       if (RgX_is_FpX(x,&p) && RgX_is_FpX(y,&p))
    1887                 :            :       {
    1888         [ +  + ]:       9073 :         if (!p) y = ZX_mul(x,y);
    1889                 :            :         else
    1890                 :            :         {
    1891                 :         21 :           x = RgX_to_FpX(x, p);
    1892                 :         21 :           y = RgX_to_FpX(y, p);
    1893                 :         21 :           y = FpX_to_mod(ZX_mul(x,y), p);
    1894                 :            :         }
    1895                 :            :       }
    1896                 :            :       else
    1897                 :     107954 :         y = RgXn_mul(x, y, lx-2);
    1898                 :     117006 :       z = fill_ser(z, y);
    1899                 :     117181 :       return gerepilecopy((pari_sp)(z + lx), z);
    1900                 :            :     }
    1901                 :      46347 :     case t_QFI: return qficomp(x,y);
    1902                 :          7 :     case t_QFR: return qfrcomp(x,y);
    1903                 :    6557631 :     case t_RFRAC: return mul_rfrac(gel(x,1),gel(x,2), gel(y,1),gel(y,2));
    1904                 :      22909 :     case t_MAT: return RgM_mul(x, y);
    1905                 :            : 
    1906                 :            :     case t_VECSMALL: /* multiply as permutation. cf perm_mul */
    1907                 :          0 :       z = cgetg_copy(x, &l);
    1908         [ #  # ]:          0 :       if (l != lg(y)) break;
    1909         [ #  # ]:          0 :       for (i=1; i<l; i++)
    1910                 :            :       {
    1911                 :          0 :         long yi = y[i];
    1912 [ #  # ][ #  # ]:          0 :         if (yi < 1 || yi >= l) pari_err_TYPE2("*",x,y);
    1913                 :          0 :         z[i] = x[yi];
    1914                 :            :       }
    1915                 :          0 :       return z;
    1916                 :            : 
    1917                 :            : 
    1918                 :            :     default:
    1919                 :          0 :       pari_err_TYPE2("*",x,y);
    1920                 :            :   }
    1921                 :            :   /* tx != ty */
    1922 [ +  + ][ +  + ]:  263699663 :   if (is_const_t(ty) && is_const_t(tx))  {
    1923         [ +  + ]:  199336052 :     if (tx > ty) { swap(x,y); lswap(tx,ty); }
    1924   [ +  +  +  +  :  199336052 :     switch(tx) {
             -  +  +  - ]
    1925                 :            :     case t_INT:
    1926   [ +  +  +  +  :  177520465 :       switch(ty)
             +  +  +  - ]
    1927                 :            :       {
    1928         [ +  + ]:  101690807 :         case t_REAL: return signe(x)? mulir(x,y): gen_0;
    1929                 :            :         case t_INTMOD:
    1930                 :    1552831 :           z = cgetg(3, t_INTMOD);
    1931                 :    1552831 :           return mul_intmod_same(z, gel(y,1), gel(y,2), modii(x, gel(y,1)));
    1932                 :            :         case t_FRAC:
    1933         [ +  + ]:   32649591 :           if (!signe(x)) return gen_0;
    1934                 :   15314658 :           z=cgetg(3,t_FRAC);
    1935                 :   15314658 :           p1 = gcdii(x,gel(y,2));
    1936         [ +  + ]:   15314658 :           if (is_pm1(p1))
    1937                 :            :           {
    1938                 :    9768403 :             avma = (pari_sp)z;
    1939                 :    9768403 :             gel(z,2) = icopy(gel(y,2));
    1940                 :    9768403 :             gel(z,1) = mulii(gel(y,1), x);
    1941                 :            :           }
    1942                 :            :           else
    1943                 :            :           {
    1944                 :    5546255 :             x = diviiexact(x,p1); tetpil = avma;
    1945                 :    5546255 :             gel(z,2) = diviiexact(gel(y,2), p1);
    1946                 :    5546255 :             gel(z,1) = mulii(gel(y,1), x);
    1947         [ +  + ]:    5546255 :             fix_frac_if_int_GC(z,tetpil);
    1948                 :            :           }
    1949                 :   15314658 :           return z;
    1950         [ +  + ]:   41401069 :         case t_COMPLEX: return signe(x)? mulRc(x, y): gen_0;
    1951         [ +  + ]:      39732 :         case t_PADIC: return signe(x)? mulTp(x, y): gen_0;
    1952                 :       1267 :         case t_QUAD: return mulRq(x,y);
    1953                 :     185168 :         case t_FFELT: return FF_Z_mul(y,x);
    1954                 :            :       }
    1955                 :            : 
    1956                 :            :     case t_REAL:
    1957   [ +  +  +  + ]:   21732458 :       switch(ty)
    1958                 :            :       {
    1959                 :     994749 :         case t_FRAC: return mulrfrac(x, y);
    1960                 :   20737695 :         case t_COMPLEX: return mulRc(x, y);
    1961                 :          7 :         case t_QUAD: return mulqf(y, x, lg(x));
    1962                 :          7 :         default: pari_err_TYPE2("*",x,y);
    1963                 :            :       }
    1964                 :            : 
    1965                 :            :     case t_INTMOD:
    1966   [ +  +  -  +  :       5086 :       switch(ty)
                   +  - ]
    1967                 :            :       {
    1968                 :        504 :         case t_FRAC: { GEN X = gel(x,1);
    1969                 :        504 :           z = cgetg(3, t_INTMOD); p1 = Fp_mul(gel(y,1), gel(x,2), X);
    1970                 :        504 :           return div_intmod_same(z, X, p1, remii(gel(y,2), X));
    1971                 :            :         }
    1972                 :         35 :         case t_COMPLEX: return mulRc_direct(x,y);
    1973                 :          0 :         case t_PADIC: { GEN X = gel(x,1);
    1974                 :          0 :           z = cgetg(3, t_INTMOD);
    1975                 :          0 :           return mul_intmod_same(z, X, gel(x,2), padic_to_Fp(y, X));
    1976                 :            :         }
    1977                 :         42 :         case t_QUAD: return mulRq(x, y);
    1978                 :            :         case t_FFELT:
    1979         [ -  + ]:       4505 :           if (!equalii(gel(x,1),FF_p_i(y)))
    1980                 :          0 :             pari_err_OP("*",x,y);
    1981                 :       4505 :           return FF_Z_mul(y,gel(x,2));
    1982                 :            :       }
    1983                 :            : 
    1984                 :            :     case t_FRAC:
    1985   [ +  +  +  +  :      78008 :       switch(ty)
                      - ]
    1986                 :            :       {
    1987                 :      73577 :         case t_COMPLEX: return mulRc(x, y);
    1988         [ +  - ]:       2198 :         case t_PADIC: return signe(gel(x,1))? mulTp(x, y): gen_0;
    1989                 :        455 :         case t_QUAD:  return mulRq(x, y);
    1990                 :       1778 :         case t_FFELT: return FF_Z_Z_muldiv(y, gel(x,1),gel(x,2));
    1991                 :            :       }
    1992                 :            : 
    1993                 :            :     case t_FFELT:
    1994                 :          0 :       pari_err_TYPE2("*",x,y);
    1995                 :            : 
    1996                 :            :     case t_COMPLEX:
    1997      [ +  +  - ]:         14 :       switch(ty)
    1998                 :            :       {
    1999                 :            :         case t_PADIC:
    2000         [ -  + ]:          7 :           return Zp_nosquare_m1(gel(y,2))? mulRc(y, x): mulTp(x, y);
    2001                 :            :         case t_QUAD:
    2002         [ -  + ]:          7 :           lx = precision(x); if (!lx) pari_err_OP("*",x,y);
    2003                 :          7 :           return mulqf(y, x, lx);
    2004                 :            :       }
    2005                 :            : 
    2006                 :            :     case t_PADIC: /* ty == t_QUAD */
    2007         [ +  + ]:         21 :       return (kro_quad(y,gel(x,2))== -1)? mulRq(x, y): mulTp(y, x);
    2008                 :            :     }
    2009                 :            :   }
    2010                 :            : 
    2011         [ +  + ]:   64363611 :   if (is_matvec_t(ty))
    2012                 :            :   {
    2013         [ +  + ]:    7173484 :     if (!is_matvec_t(tx))
    2014                 :            :     {
    2015         [ -  + ]:    6889953 :       if (is_noncalc_t(tx)) pari_err_TYPE2( "*",x,y); /* necessary if ly = 1 */
    2016                 :    6889953 :       z = cgetg_copy(y, &ly);
    2017         [ +  + ]:  130861893 :       for (i=1; i<ly; i++) gel(z,i) = gmul(x,gel(y,i));
    2018                 :    6889953 :       return z;
    2019                 :            :     }
    2020   [ +  +  +  - ]:     283531 :     switch(tx)
    2021                 :            :     {
    2022                 :            :       case t_VEC:
    2023      [ +  +  - ]:     197621 :         switch(ty) {
    2024                 :     181025 :           case t_COL: return RgV_RgC_mul(x,y);
    2025                 :      16596 :           case t_MAT: return RgV_RgM_mul(x,y);
    2026                 :            :         }
    2027                 :          0 :         break;
    2028                 :            :       case t_COL:
    2029      [ +  -  - ]:          7 :         switch(ty) {
    2030                 :          7 :           case t_VEC: return RgC_RgV_mul(x,y);
    2031                 :          0 :           case t_MAT: return RgC_RgM_mul(x,y);
    2032                 :            :         }
    2033                 :          0 :         break;
    2034                 :            :       case t_MAT:
    2035      [ -  +  - ]:      85903 :         switch(ty) {
    2036                 :          0 :           case t_VEC: return RgM_RgV_mul(x,y);
    2037                 :      85903 :           case t_COL: return RgM_RgC_mul(x,y);
    2038                 :            :         }
    2039                 :            :     }
    2040                 :            :   }
    2041         [ +  + ]:   57190127 :   if (is_matvec_t(tx))
    2042                 :            :   {
    2043         [ -  + ]:     212923 :     if (is_noncalc_t(ty)) pari_err_TYPE2( "*",x,y); /* necessary if lx = 1 */
    2044                 :     212923 :     z = cgetg_copy(x, &lx);
    2045         [ +  + ]:    1062668 :     for (i=1; i<lx; i++) gel(z,i) = gmul(y,gel(x,i));
    2046                 :     212923 :     return z;
    2047                 :            :   }
    2048         [ +  + ]:   56977204 :   if (tx > ty) { swap(x,y); lswap(tx,ty); }
    2049                 :            :   /* tx < ty, !ismatvec(x and y) */
    2050                 :            : 
    2051         [ +  + ]:   56977204 :   if (ty == t_POLMOD) /* is_const_t(tx) in this case */
    2052                 :    1053521 :     return mul_polmod_scal(gel(y,1), gel(y,2), x);
    2053         [ +  + ]:   55923683 :   if (is_scalar_t(tx)) {
    2054         [ +  + ]:   53091348 :     if (tx == t_POLMOD) {
    2055                 :     167966 :       vx = varn(gel(x,1));
    2056                 :     167966 :       vy = gvar(y);
    2057         [ +  + ]:     167966 :       if (vx != vy) {
    2058         [ +  + ]:      27161 :         if (varncmp(vx,vy) > 0) return mul_scal(y, x, ty);
    2059                 :        658 :         return mul_polmod_scal(gel(x,1), gel(x,2), y);
    2060                 :            :       }
    2061                 :            :       /* error if ty == t_SER */
    2062                 :     140805 :       av = avma; y = gmod(y, gel(x,1));
    2063                 :     140798 :       return gerepileupto(av, mul_polmod_same(gel(x,1), gel(x,2), y));
    2064                 :            :     }
    2065                 :   52923382 :     return mul_scal(y, x, ty);
    2066                 :            :   }
    2067                 :            : 
    2068                 :            :   /* x and y are not scalars, nor matvec */
    2069                 :    2832335 :   vx = gvar(x);
    2070                 :    2832335 :   vy = gvar(y);
    2071         [ +  + ]:    2832335 :   if (vx != vy) /* x or y is treated as a scalar */
    2072                 :    2827966 :     return (varncmp(vx, vy) < 0)? mul_scal(x, y, tx)
    2073         [ +  + ]:    1413983 :                                 : mul_scal(y, x, ty);
    2074                 :            :   /* vx = vy */
    2075      [ +  -  - ]:    1418352 :   switch(tx)
    2076                 :            :   {
    2077                 :            :     case t_POL:
    2078      [ +  +  - ]:    1418352 :       switch (ty)
    2079                 :            :       {
    2080                 :            :         case t_SER:
    2081                 :            :         {
    2082                 :            :           long vn;
    2083         [ -  + ]:      74375 :           if (lg(x) == 2) return zeropol(vx);
    2084         [ +  + ]:      74375 :           if (lg(y) == 2) return zeroser(vx, valp(y)+RgX_val(x));
    2085                 :      74165 :           av = avma;
    2086                 :      74165 :           vn = RgX_valrem(x, &x);
    2087                 :            :           /* take advantage of x = t^n ! */
    2088         [ +  + ]:      74165 :           if (degpol(x)) {
    2089                 :       2401 :             p1 = RgX_to_ser(x,lg(y));
    2090         [ -  + ]:       2401 :             if (vn) settyp(x, t_VECSMALL); /* *new* x left on stack */
    2091                 :       2401 :             p2 = gmul(p1,y);
    2092                 :       2401 :             settyp(p1, t_VECSMALL); /* p1 left on stack */
    2093                 :            :           } else {
    2094                 :      71764 :             avma = av;
    2095                 :      71764 :             p2 = mul_ser_scal(y, gel(x,2));
    2096                 :            :           }
    2097                 :      74165 :           setvalp(p2, valp(p2) + vn);
    2098                 :      74165 :           return p2;
    2099                 :            :         }
    2100                 :            : 
    2101                 :    1343977 :         case t_RFRAC: return mul_rfrac_scal(gel(y,1),gel(y,2), x);
    2102                 :            :       }
    2103                 :          0 :       break;
    2104                 :            : 
    2105                 :            :     case t_SER:
    2106         [ #  # ]:          0 :       switch (ty)
    2107                 :            :       {
    2108                 :            :         case t_RFRAC:
    2109                 :          0 :           av = avma;
    2110                 :          0 :           return gerepileupto(av, gdiv(gmul(gel(y,1),x), gel(y,2)));
    2111                 :            :       }
    2112                 :          0 :       break;
    2113                 :            :   }
    2114                 :          0 :   pari_err_TYPE2("*",x,y);
    2115                 : 2378587726 :   return NULL; /* not reached */
    2116                 :            : }
    2117                 :            : 
    2118                 :            : int
    2119                 :      28245 : ff_poltype(GEN *x, GEN *p, GEN *pol)
    2120                 :            : {
    2121                 :      28245 :   GEN Q, P = *x;
    2122         [ +  + ]:      28245 :   if (!signe(P)) return 0;
    2123 [ +  + ][ +  + ]:      28161 :   if (!RgX_is_FpXQX(P,pol,p) || !*p || !*pol || typ(*pol)!=t_POL)
         [ +  + ][ +  - ]
    2124                 :      28161 :     return 0;
    2125                 :          0 :   Q = RgX_to_FpX(*pol, *p);
    2126                 :          0 :   P = RgX_to_FpXQX(P, Q, *p);
    2127                 :          0 :   *x = ZXX_to_Kronecker(P, degpol(Q));
    2128                 :          0 :   *pol = Q;
    2129                 :      28245 :   return 1;
    2130                 :            : }
    2131                 :            : 
    2132                 :            : /* return a non-normalized result */
    2133                 :            : GEN
    2134                 :       4151 : sqr_ser_part(GEN x, long l1, long l2)
    2135                 :            : {
    2136                 :            :   long i, j, l;
    2137                 :            :   pari_sp av;
    2138                 :            :   GEN Z, z, p1, p2;
    2139                 :            :   long mi;
    2140         [ +  + ]:       4151 :   if (l2 < l1) return zeroser(varn(x), 2*valp(x));
    2141                 :       4144 :   p2 = cgetg(l2+2, t_VECSMALL)+1; /* left on stack on exit */
    2142                 :       4144 :   Z = cgetg(l2-l1+3, t_SER);
    2143                 :       4144 :   Z[1] = evalvalp(2*valp(x)) | evalvarn(varn(x));
    2144                 :       4144 :   z = Z + 2-l1;
    2145                 :       4144 :   x += 2; mi = 0;
    2146         [ +  + ]:      10745 :   for (i=0; i<l1; i++)
    2147                 :            :   {
    2148         [ +  + ]:       6601 :     p2[i] = !isrationalzero(gel(x,i)); if (p2[i]) mi = i;
    2149                 :            :   }
    2150                 :            : 
    2151         [ +  + ]:      20601 :   for (i=l1; i<=l2; i++)
    2152                 :            :   {
    2153         [ +  + ]:      16457 :     p2[i] = !isrationalzero(gel(x,i)); if (p2[i]) mi = i;
    2154                 :      16457 :     p1=gen_0; av=avma; l=((i+1)>>1) - 1;
    2155         [ +  + ]:      26719 :     for (j=i-mi; j<=minss(l,mi); j++)
    2156 [ +  + ][ +  + ]:      10262 :       if (p2[j] && p2[i-j]) p1 = gadd(p1, gmul(gel(x,j),gel(x,i-j)));
    2157                 :      16457 :     p1 = gshift(p1,1);
    2158 [ +  + ][ +  + ]:      16457 :     if ((i&1) == 0 && p2[i>>1])
    2159                 :       5173 :       p1 = gadd(p1, gsqr(gel(x,i>>1)));
    2160                 :      16457 :     gel(z,i) = gerepileupto(av,p1);
    2161                 :            :   }
    2162                 :       4151 :   return Z;
    2163                 :            : }
    2164                 :            : 
    2165                 :            : GEN
    2166                 :  947499283 : gsqr(GEN x)
    2167                 :            : {
    2168                 :            :   long i, lx;
    2169                 :            :   pari_sp av, tetpil;
    2170                 :            :   GEN z, p1, p2, p3, p4;
    2171                 :            : 
    2172   [ +  +  +  +  :  947499283 :   switch(typ(x))
          +  +  +  +  +  
          +  +  +  +  +  
                +  -  - ]
    2173                 :            :   {
    2174                 :  926568461 :     case t_INT: return sqri(x);
    2175                 :   14549666 :     case t_REAL: return sqrr(x);
    2176                 :     139741 :     case t_INTMOD: { GEN X = gel(x,1);
    2177                 :     139741 :       z = cgetg(3,t_INTMOD);
    2178                 :     139741 :       gel(z,2) = gerepileuptoint((pari_sp)z, remii(sqri(gel(x,2)), X));
    2179                 :     139741 :       gel(z,1) = icopy(X); return z;
    2180                 :            :     }
    2181                 :     134387 :     case t_FRAC: return sqrfrac(x);
    2182                 :            : 
    2183                 :            :     case t_COMPLEX:
    2184         [ +  + ]:    2776052 :       if (isintzero(gel(x,1))) {
    2185                 :      16221 :         av = avma;
    2186                 :      16221 :         return gerepileupto(av, gneg(gsqr(gel(x,2))));
    2187                 :            :       }
    2188                 :    2759831 :       z = cgetg(3,t_COMPLEX); av = avma;
    2189                 :    2759831 :       p1 = gadd(gel(x,1),gel(x,2));
    2190                 :    2759831 :       p2 = gsub(gel(x,1), gel(x,2));
    2191                 :    2759831 :       p3 = gmul(gel(x,1),gel(x,2));
    2192                 :    2759831 :       tetpil = avma;
    2193                 :    2759831 :       gel(z,1) = gmul(p1,p2);
    2194                 :    2759831 :       gel(z,2) = gshift(p3,1); gerepilecoeffssp(av,tetpil,z+1,2); return z;
    2195                 :            : 
    2196                 :            :     case t_PADIC:
    2197                 :       1841 :       z = cgetg(5,t_PADIC);
    2198 [ +  + ][ +  - ]:       1841 :       i = (equaliu(gel(x,2), 2) && signe(gel(x,4)))? 1: 0;
    2199 [ +  + ][ +  + ]:       1841 :       if (i && precp(x) == 1) i = 2; /* (1 + O(2))^2 = 1 + O(2^3) */
    2200                 :       1841 :       z[1] = evalprecp(precp(x)+i) | evalvalp(valp(x) << 1);
    2201                 :       1841 :       gel(z,2) = icopy(gel(x,2));
    2202                 :       1841 :       gel(z,3) = shifti(gel(x,3), i); av = avma;
    2203                 :       1841 :       gel(z,4) = gerepileuptoint(av, remii(sqri(gel(x,4)), gel(z,3)));
    2204                 :       1841 :       return z;
    2205                 :            : 
    2206                 :         28 :     case t_QUAD: z = cgetg(4,t_QUAD);
    2207                 :         28 :       p1 = gel(x,1);
    2208                 :         28 :       gel(z,1) = ZX_copy(p1); av = avma;
    2209                 :         28 :       p2 = gsqr(gel(x,2));
    2210                 :         28 :       p3 = gsqr(gel(x,3));
    2211                 :         28 :       p4 = gmul(gneg_i(gel(p1,2)),p3);
    2212                 :            : 
    2213         [ +  + ]:         28 :       if (gequal0(gel(p1,3)))
    2214                 :            :       {
    2215                 :          7 :         tetpil = avma;
    2216                 :          7 :         gel(z,2) = gerepile(av,tetpil,gadd(p4,p2));
    2217                 :          7 :         av = avma;
    2218                 :          7 :         p2 = gmul(gel(x,2),gel(x,3)); tetpil = avma;
    2219                 :          7 :         gel(z,3) = gerepile(av,tetpil,gmul2n(p2,1)); return z;
    2220                 :            :       }
    2221                 :            : 
    2222                 :         21 :       p1 = gmul2n(gmul(gel(x,2),gel(x,3)), 1);
    2223                 :         21 :       tetpil = avma;
    2224                 :         21 :       gel(z,2) = gadd(p2,p4);
    2225                 :         21 :       gel(z,3) = gadd(p1,p3);
    2226                 :         21 :       gerepilecoeffssp(av,tetpil,z+2,2); return z;
    2227                 :            : 
    2228                 :            :     case t_POLMOD:
    2229                 :      21703 :       return sqr_polmod(gel(x,1), gel(x,2));
    2230                 :            : 
    2231                 :    2198558 :     case t_FFELT: return FF_sqr(x);
    2232                 :            : 
    2233                 :            :     case t_POL:
    2234                 :            :     {
    2235                 :    1011581 :       GEN a = x, p = NULL, pol = NULL;
    2236                 :    1011581 :       av = avma;
    2237         [ +  + ]:    1011581 :       if (RgX_is_ZX(x)) return ZX_sqr(x);
    2238         [ -  + ]:      28245 :       if (ff_poltype(&x,&p,&pol))
    2239                 :            :       {
    2240                 :          0 :         z = ZX_sqr(x);
    2241         [ #  # ]:          0 :         if (p) z = FpX_to_mod(z,p);
    2242         [ #  # ]:          0 :         if (pol) z = Kronecker_to_mod(z,pol);
    2243                 :          0 :         z = gerepileupto(av, z);
    2244                 :            :       }
    2245                 :      28245 :       else { avma = av; z = RgX_sqr(a); }
    2246                 :    1011581 :       return z;
    2247                 :            :     }
    2248                 :            : 
    2249                 :            :     case t_SER:
    2250                 :       1729 :       lx = lg(x);
    2251         [ +  + ]:       1729 :       if (ser_isexactzero(x)) {
    2252                 :          7 :         GEN z = gcopy(x);
    2253                 :          7 :         setvalp(z, 2*valp(x));
    2254                 :          7 :         return z;
    2255                 :            :       }
    2256         [ +  + ]:       1722 :       if (lx < 40)
    2257                 :       1715 :         return normalize( sqr_ser_part(x, 0, lx-3) );
    2258                 :            :       else
    2259                 :            :       {
    2260                 :          7 :         pari_sp av = avma;
    2261                 :          7 :         GEN z = cgetg(lx,t_SER), p = NULL;
    2262                 :          7 :         z[1] = evalvalp(2*valp(x)) | evalvarn(varn(x)) | evalsigne(1);
    2263                 :          7 :         x = ser2pol_i(x,lx);
    2264         [ +  - ]:          7 :         if (RgX_is_FpX(x,&p))
    2265                 :            :         {
    2266         [ +  - ]:          7 :           if (!p) x = ZX_sqr(x);
    2267                 :            :           else
    2268                 :            :           {
    2269                 :          0 :             x = RgX_to_FpX(x, p);
    2270                 :          0 :             x = FpX_to_mod(ZX_sqr(x), p);
    2271                 :            :           }
    2272                 :            :         }
    2273                 :            :         else
    2274                 :          0 :           x = RgXn_sqr(x, lx-2);
    2275                 :          7 :         z = fill_ser(z, x);
    2276                 :          7 :         return gerepilecopy(av, z);
    2277                 :            :       }
    2278                 :            : 
    2279                 :          7 :     case t_RFRAC: z = cgetg(3,t_RFRAC);
    2280                 :          7 :       gel(z,1) = gsqr(gel(x,1));
    2281                 :          7 :       gel(z,2) = gsqr(gel(x,2)); return z;
    2282                 :            : 
    2283                 :        245 :     case t_MAT: return RgM_sqr(x);
    2284                 :         14 :     case t_QFR: return qfrsqr(x);
    2285                 :      95270 :     case t_QFI: return qfisqr(x);
    2286                 :            :     case t_VECSMALL:
    2287                 :          0 :       z = cgetg_copy(x, &lx);
    2288         [ #  # ]:          0 :       for (i=1; i<lx; i++)
    2289                 :            :       {
    2290                 :          0 :         long xi = x[i];
    2291 [ #  # ][ #  # ]:          0 :         if (xi < 1 || xi >= lx) pari_err_TYPE2("*",x,x);
    2292                 :          0 :         z[i] = x[xi];
    2293                 :            :       }
    2294                 :          0 :       return z;
    2295                 :            :   }
    2296                 :          0 :   pari_err_TYPE2("*",x,x);
    2297                 :  947499283 :   return NULL; /* not reached */
    2298                 :            : }
    2299                 :            : 
    2300                 :            : /********************************************************************/
    2301                 :            : /**                                                                **/
    2302                 :            : /**                           DIVISION                             **/
    2303                 :            : /**                                                                **/
    2304                 :            : /********************************************************************/
    2305                 :            : static GEN
    2306                 :     270996 : div_rfrac_scal(GEN x, GEN y)
    2307                 :            : {
    2308                 :     270996 :   pari_sp av = avma;
    2309                 :     270996 :   GEN d = rfrac_denom_mul_scal(gel(x,2), y);
    2310                 :     270996 :   return gerepileupto(av, gred_rfrac_simple(gel(x,1), d));
    2311                 :            : }
    2312                 :            : static GEN
    2313                 :    1003766 : div_scal_rfrac(GEN x, GEN y)
    2314                 :            : {
    2315                 :    1003766 :   GEN y1 = gel(y,1), y2 = gel(y,2);
    2316                 :    1003766 :   pari_sp av = avma;
    2317 [ +  + ][ +  + ]:    1003766 :   if (typ(y1) == t_POL && varn(y2) == varn(y1) && degpol(y1) > 0)
                 [ -  + ]
    2318                 :          0 :     return gerepileupto(av, gred_rfrac_simple(gmul(x, y2), y1));
    2319                 :    1003766 :   return RgX_Rg_mul(y2, gdiv(x,y1));
    2320                 :            : }
    2321                 :            : static GEN
    2322                 :    1188765 : div_rfrac(GEN x, GEN y)
    2323                 :    1188765 : { return mul_rfrac(gel(x,1),gel(x,2), gel(y,2),gel(y,1)); }
    2324                 :            : 
    2325                 :            : static GEN
    2326                 :       5523 : div_ser_scal(GEN x, GEN y) {
    2327                 :            :   long i, lx;
    2328                 :            :   GEN z;
    2329         [ +  + ]:       5523 :   if (ser_isexactzero(x))
    2330                 :            :   {
    2331         [ +  - ]:          7 :     if (lg(x) == 2) return gcopy(x);
    2332                 :          0 :     return scalarser(gdiv(gel(x,2), y), varn(x), valp(x));
    2333                 :            :   }
    2334                 :       5516 :   z = cgetg_copy(x, &lx); z[1] = x[1];
    2335         [ +  + ]:      40684 :   for (i=2; i<lx; i++) gel(z,i) = gdiv(gel(x,i),y);
    2336                 :       5523 :   return normalize(z);
    2337                 :            : }
    2338                 :            : GEN
    2339                 :         56 : ser_normalize(GEN x)
    2340                 :            : {
    2341                 :         56 :   long i, lx = lg(x);
    2342                 :            :   GEN c, z;
    2343         [ -  + ]:         56 :   if (lx == 2) return x;
    2344         [ +  + ]:         56 :   c = gel(x,2); if (gequal1(c)) return x;
    2345                 :         28 :   z = cgetg(lx, t_SER); z[1] = x[1]; gel(z,2) = gen_1;
    2346         [ +  + ]:        147 :   for (i=3; i<lx; i++) gel(z,i) = gdiv(gel(x,i),c);
    2347                 :         56 :   return z;
    2348                 :            : }
    2349                 :            : 
    2350                 :            : static GEN
    2351                 :     789469 : div_T_scal(GEN x, GEN y, long tx) {
    2352   [ +  +  +  - ]:     789469 :   switch(tx)
    2353                 :            :   {
    2354                 :     516674 :     case t_POL: return RgX_Rg_div(x, y);
    2355                 :       5523 :     case t_SER: return div_ser_scal(x, y);
    2356                 :     267272 :     case t_RFRAC: return div_rfrac_scal(x,y);
    2357                 :            :   }
    2358                 :          0 :   pari_err_TYPE2("/",x,y);
    2359                 :     789469 :   return NULL; /* not reached */
    2360                 :            : }
    2361                 :            : 
    2362                 :            : static GEN
    2363                 :    8187846 : div_scal_pol(GEN x, GEN y) {
    2364                 :    8187846 :   long ly = lg(y);
    2365                 :            :   pari_sp av;
    2366         [ +  + ]:    8187846 :   if (ly == 3) return scalarpol(gdiv(x,gel(y,2)), varn(y));
    2367         [ +  + ]:    8143763 :   if (isrationalzero(x)) return zeropol(varn(y));
    2368                 :    6093807 :   av = avma;
    2369                 :    8187846 :   return gerepileupto(av, gred_rfrac_simple(x,y));
    2370                 :            : }
    2371                 :            : static GEN
    2372                 :        553 : div_scal_ser(GEN x, GEN y) { /* TODO: improve */
    2373                 :            :   GEN z;
    2374                 :            :   long ly, i;
    2375         [ -  + ]:        553 :   if (gequal0(x)) { pari_sp av=avma; return gerepileupto(av, gmul(x, ginv(y))); }
    2376                 :        553 :   ly = lg(y); z = (GEN)pari_malloc(ly*sizeof(long));
    2377                 :        553 :   z[0] = evaltyp(t_SER) | evallg(ly);
    2378                 :        553 :   z[1] = evalsigne(1) | _evalvalp(0) | evalvarn(varn(y));
    2379         [ +  + ]:       6363 :   gel(z,2) = x; for (i=3; i<ly; i++) gel(z,i) = gen_0;
    2380                 :        553 :   y = gdiv(z,y); pari_free(z); return y;
    2381                 :            : }
    2382                 :            : static GEN
    2383                 :    9146553 : div_scal_T(GEN x, GEN y, long ty) {
    2384   [ +  +  +  - ]:    9146553 :   switch(ty)
    2385                 :            :   {
    2386                 :    8142990 :     case t_POL: return div_scal_pol(x, y);
    2387                 :        553 :     case t_SER: return div_scal_ser(x, y);
    2388                 :    1003010 :     case t_RFRAC: return div_scal_rfrac(x, y);
    2389                 :            :   }
    2390                 :          0 :   pari_err_TYPE2("/",x,y);
    2391                 :    9146553 :   return NULL; /* not reached */
    2392                 :            : }
    2393                 :            : 
    2394                 :            : /* assume tx = ty = t_SER, same variable vx */
    2395                 :            : static GEN
    2396                 :     267106 : div_ser(GEN x, GEN y, long vx)
    2397                 :            : {
    2398                 :     267106 :   long i, j, l = valp(x) - valp(y), lx = lg(x), ly = lg(y);
    2399                 :            :   GEN y_lead, p1, p2, z;
    2400                 :            : 
    2401         [ -  + ]:     267106 :   if (!signe(y)) pari_err_INV("div_ser", y);
    2402         [ +  + ]:     267106 :   if (ser_isexactzero(x))
    2403                 :            :   {
    2404         [ +  + ]:        511 :     if (lx == 2) return zeroser(vx, l);
    2405                 :          7 :     return scalarser(gmul(gel(x,2),RgX_get_0(y)), varn(x), l);
    2406                 :            :   }
    2407                 :     266595 :   y_lead = gel(y,2);
    2408         [ +  + ]:     266595 :   if (gequal0(y_lead)) /* normalize denominator if leading term is 0 */
    2409                 :            :   {
    2410                 :         14 :     pari_warn(warner,"normalizing a series with 0 leading term");
    2411         [ +  - ]:         14 :     for (l--, ly--,y++; ly > 2; l--, ly--, y++)
    2412                 :            :     {
    2413                 :         14 :       y_lead = gel(y,2);
    2414         [ +  - ]:         14 :       if (!gequal0(y_lead)) break;
    2415                 :            :     }
    2416         [ -  + ]:         14 :     if (ly <= 2) pari_err_INV("div_ser", y);
    2417                 :            :   }
    2418         [ +  + ]:     266595 :   if (ly < lx) lx = ly;
    2419                 :     266595 :   p2 = cgetg(lx, t_VECSMALL); /* left on stack for efficiency */
    2420         [ +  + ]:     832419 :   for (i=3; i<lx; i++)
    2421                 :            :   {
    2422                 :     565824 :     p1 = gel(y,i);
    2423         [ +  + ]:     565824 :     if (isrationalzero(p1)) p1 = NULL;
    2424                 :     565824 :     gel(p2,i) = p1;
    2425                 :            :   }
    2426                 :     266595 :   z = cgetg(lx,t_SER);
    2427                 :     266595 :   z[1] = evalvalp(l) | evalvarn(vx) | evalsigne(1);
    2428                 :     266595 :   gel(z,2) = gdiv(gel(x,2), y_lead);
    2429         [ +  + ]:     832419 :   for (i=3; i<lx; i++)
    2430                 :            :   {
    2431                 :     565824 :     pari_sp av = avma;
    2432                 :     565824 :     p1 = gel(x,i);
    2433         [ +  + ]:    1539055 :     for (j=2, l=i; j<i; j++, l--)
    2434         [ +  + ]:     973231 :       if (p2[l]) p1 = gsub(p1, gmul(gel(z,j), gel(p2,l)));
    2435                 :     565824 :     gel(z,i) = gerepileupto(av, gdiv(p1, y_lead));
    2436                 :            :   }
    2437                 :     267106 :   return normalize(z);
    2438                 :            : }
    2439                 :            : /* x,y compatible PADIC */
    2440                 :            : static GEN
    2441                 :      40313 : divpp(GEN x, GEN y) {
    2442                 :            :   pari_sp av;
    2443                 :            :   long a, b;
    2444                 :            :   GEN z, M;
    2445                 :            : 
    2446         [ +  + ]:      40313 :   if (!signe(gel(y,4))) pari_err_INV("divpp",y);
    2447         [ +  + ]:      40306 :   if (!signe(gel(x,4))) return zeropadic(gel(x,2), valp(x)-valp(y));
    2448                 :      40299 :   a = precp(x);
    2449         [ +  + ]:      40299 :   b = precp(y); if (a > b) { M = gel(y,3); } else { M = gel(x,3); b = a; }
    2450                 :      40299 :   z = cgetg(5, t_PADIC);
    2451                 :      40299 :   z[1] = _evalprecp(b) | evalvalp(valp(x) - valp(y));
    2452                 :      40299 :   gel(z,2) = icopy(gel(x,2));
    2453                 :      40299 :   gel(z,3) = icopy(M); av = avma;
    2454                 :      40299 :   gel(z,4) = gerepileuptoint(av, remii(mulii(gel(x,4), Fp_inv(gel(y,4), M)), M) );
    2455                 :      40306 :   return z;
    2456                 :            : }
    2457                 :            : static GEN
    2458                 :      31962 : div_polmod_same(GEN T, GEN x, GEN y)
    2459                 :            : {
    2460                 :      31962 :   long v = varn(T);
    2461                 :      31962 :   GEN a, z = cgetg(3, t_POLMOD);
    2462                 :      31962 :   gel(z,1) = RgX_copy(T);
    2463 [ +  + ][ +  - ]:      31962 :   if (typ(y) != t_POL || varn(y) != v || lg(y) <= 3)
                 [ +  + ]
    2464                 :      25977 :     a = gdiv(x, y);
    2465 [ +  + ][ +  - ]:       5985 :   else if (typ(x) != t_POL || varn(x) != v || lg(x) <= 3)
                 [ +  + ]
    2466                 :       4382 :   {
    2467                 :       4382 :     pari_sp av = avma;
    2468                 :       4382 :     a = gerepileupto(av, gmul(x, RgXQ_inv(y, T)));
    2469                 :            :   }
    2470 [ +  + ][ +  + ]:       1603 :   else if (degpol(T) == 2 && isint1(gel(T,4))) /* quadratic fields */
    2471                 :       1176 :   {
    2472                 :       1176 :     pari_sp av = avma;
    2473                 :       1176 :     a = quad_polmod_mul(T, x, quad_polmod_conj(y, T));
    2474                 :       1176 :     a = RgX_Rg_div(a, quad_polmod_norm(y, T));
    2475                 :       1176 :     a = gerepileupto(av, a);
    2476                 :            :   }
    2477                 :            :   else
    2478                 :            :   {
    2479                 :        427 :     pari_sp av = avma;
    2480                 :        427 :     GEN p = NULL;
    2481 [ +  - ][ +  + ]:        427 :     if (RgX_is_FpX(T, &p) && RgX_is_FpX(x, &p) && RgX_is_FpX(y, &p) && p)
         [ +  + ][ +  + ]
    2482                 :            :     {
    2483                 :         14 :       T = RgX_to_FpX(T, p); x = RgX_to_FpX(x, p); y = RgX_to_FpX(y, p);
    2484         [ +  + ]:         14 :       if (lgefint(p) == 3)
    2485                 :            :       {
    2486                 :          7 :         ulong pp = p[2];
    2487                 :          7 :         x = ZX_to_Flx(x, pp);
    2488                 :          7 :         y = ZX_to_Flx(y, pp);
    2489                 :          7 :         T = ZX_to_Flx(T, pp);
    2490                 :          7 :         a = Flxq_mul(x, Flxq_inv(y,T,pp),T,pp);
    2491                 :          7 :         a = Flx_to_ZX(a);
    2492                 :            :       }
    2493                 :            :       else
    2494                 :          7 :         a = FpXQ_div(x, y, T, p);
    2495                 :         14 :       a = FpX_to_mod(a, p);
    2496                 :            :     } else
    2497                 :        413 :       a = RgXQ_mul(x, ginvmod(y, gel(z,1)), gel(z,1));
    2498                 :        427 :     a = gerepileupto(av, a);
    2499                 :            :   }
    2500                 :      31962 :   gel(z,2) = a; return z;
    2501                 :            : }
    2502                 :            : GEN
    2503                 :   85816089 : gdiv(GEN x, GEN y)
    2504                 :            : {
    2505                 :   85816089 :   long tx = typ(x), ty = typ(y), lx, ly, vx, vy, i;
    2506                 :            :   pari_sp av, tetpil;
    2507                 :            :   GEN z, p1, p2;
    2508                 :            : 
    2509 [ +  + ][ +  +  :   85816089 :   if (tx == ty) switch(tx)
          +  +  +  +  +  
          +  +  +  +  +  
             -  -  -  - ]
    2510                 :            :   {
    2511                 :            :     case t_INT:
    2512 [ +  + ][ +  + ]:   44483186 :       if (is_pm1(y)) return (signe(y) < 0)? negi(x): icopy(x);
    2513         [ +  + ]:   14346733 :       if (is_pm1(x)) {
    2514                 :    3407353 :         long s = signe(y);
    2515         [ +  + ]:    3407353 :         if (!s) pari_err_INV("gdiv",y);
    2516         [ +  + ]:    3407283 :         if (signe(x) < 0) s = -s;
    2517                 :    3407283 :         z = cgetg(3, t_FRAC);
    2518         [ +  + ]:    3407283 :         gel(z,1) = s<0? gen_m1: gen_1;
    2519                 :    3407283 :         gel(z,2) = absi(y); return z;
    2520                 :            :       }
    2521                 :   10939380 :       return gred_frac2(x,y);
    2522                 :            : 
    2523                 :    5307633 :     case t_REAL: return divrr(x,y);
    2524                 :      19425 :     case t_INTMOD: { GEN X = gel(x,1), Y = gel(y,1);
    2525                 :      19425 :       z = cgetg(3,t_INTMOD);
    2526 [ +  + ][ +  - ]:      19425 :       if (X==Y || equalii(X,Y))
    2527                 :      19425 :         return div_intmod_same(z, X, gel(x,2), gel(y,2));
    2528                 :          0 :       gel(z,1) = gcdii(X,Y); av = avma;
    2529                 :          0 :       p1 = mulii(gel(x,2), Fp_inv(gel(y,2), gel(z,1)));
    2530                 :          0 :       gel(z,2) = gerepileuptoint(av, remii(p1, gel(z,1))); return z;
    2531                 :            :     }
    2532                 :            :     case t_FRAC: {
    2533                 :     454350 :       GEN x1 = gel(x,1), x2 = gel(x,2);
    2534                 :     454350 :       GEN y1 = gel(y,1), y2 = gel(y,2);
    2535                 :     454350 :       z = cgetg(3, t_FRAC);
    2536                 :     454350 :       p1 = gcdii(x1, y1);
    2537         [ +  + ]:     454350 :       if (!is_pm1(p1)) { x1 = diviiexact(x1,p1); y1 = diviiexact(y1,p1); }
    2538                 :     454350 :       p1 = gcdii(x2, y2);
    2539         [ +  + ]:     454350 :       if (!is_pm1(p1)) { x2 = diviiexact(x2,p1); y2 = diviiexact(y2,p1); }
    2540                 :     454350 :       tetpil = avma;
    2541                 :     454350 :       gel(z,2) = mulii(x2,y1);
    2542                 :     454350 :       gel(z,1) = mulii(x1,y2);
    2543                 :     454350 :       normalize_frac(z);
    2544         [ +  + ]:     454350 :       fix_frac_if_int_GC(z,tetpil);
    2545                 :     454350 :       return z;
    2546                 :            :     }
    2547                 :            :     case t_COMPLEX:
    2548         [ +  + ]:     378148 :       if (isintzero(gel(y,1)))
    2549                 :            :       {
    2550                 :       8099 :         y = gel(y,2);
    2551         [ +  + ]:       8099 :         if (isintzero(gel(x,1))) return gdiv(gel(x,2), y);
    2552                 :       8043 :         z = cgetg(3,t_COMPLEX);
    2553                 :       8043 :         gel(z,1) = gdiv(gel(x,2), y);
    2554                 :       8043 :         av = avma;
    2555                 :       8043 :         gel(z,2) = gerepileupto(av, gneg(gdiv(gel(x,1), y)));
    2556                 :       8043 :         return z;
    2557                 :            :       }
    2558                 :     370049 :       av = avma; p1 = cxnorm(y); p2 = mulcc(x, gconj(y)); tetpil = avma;
    2559                 :     370049 :       return gerepile(av, tetpil, gdiv(p2,p1));
    2560                 :            : 
    2561                 :            :     case t_PADIC:
    2562         [ -  + ]:       2450 :       if (!equalii(gel(x,2),gel(y,2))) pari_err_OP("/",x,y);
    2563                 :       2450 :       return divpp(x, y);
    2564                 :            : 
    2565                 :            :     case t_QUAD:
    2566         [ -  + ]:        322 :       if (!ZX_equal(gel(x,1),gel(y,1))) pari_err_OP("/",x,y);
    2567                 :        322 :       av = avma; p1 = quadnorm(y); p2 = mulqq(x, gconj(y)); tetpil = avma;
    2568                 :        322 :       return gerepile(av, tetpil, gdiv(p2,p1));
    2569                 :            : 
    2570                 :      56168 :     case t_FFELT: return FF_div(x,y);
    2571                 :            : 
    2572                 :            :     case t_POLMOD:
    2573         [ +  - ]:      31962 :       if (RgX_equal_var(gel(x,1), gel(y,1)))
    2574                 :      31962 :         z = div_polmod_same(gel(x,1), gel(x,2), gel(y,2));
    2575                 :            :       else {
    2576                 :          0 :         av = avma;
    2577                 :          0 :         z = gerepileupto(av, gmul(x, ginv(y)));
    2578                 :            :       }
    2579                 :      31962 :       return z;
    2580                 :            : 
    2581                 :            :     case t_POL:
    2582                 :   18502454 :       vx = varn(x);
    2583                 :   18502454 :       vy = varn(y);
    2584         [ +  + ]:   18502454 :       if (vx != vy) {
    2585         [ +  + ]:      95123 :         if (varncmp(vx, vy) < 0) return RgX_Rg_div(x, y);
    2586                 :      44856 :                             else return div_scal_pol(x, y);
    2587                 :            :       }
    2588         [ -  + ]:   18407331 :       if (!signe(y)) pari_err_INV("gdiv",y);
    2589         [ +  + ]:   18407331 :       if (lg(y) == 3) return RgX_Rg_div(x,gel(y,2));
    2590                 :   18290004 :       return gred_rfrac2(x,y);
    2591                 :            : 
    2592                 :            :     case t_SER:
    2593                 :       6832 :       vx = varn(x);
    2594                 :       6832 :       vy = varn(y);
    2595         [ -  + ]:       6832 :       if (vx != vy) {
    2596         [ #  # ]:          0 :         if (varncmp(vx, vy) < 0) return div_ser_scal(x, y);
    2597                 :          0 :                             else return div_scal_ser(x, y);
    2598                 :            :       }
    2599                 :       6832 :       return div_ser(x, y, vx);
    2600                 :            :     case t_RFRAC:
    2601                 :    1193245 :       vx = varn(gel(x,2));
    2602                 :    1193245 :       vy = varn(gel(y,2));
    2603         [ +  + ]:    1193245 :       if (vx != vy) {
    2604         [ +  + ]:       4480 :         if (varncmp(vx, vy) < 0) return div_rfrac_scal(x, y);
    2605                 :        756 :                             else return div_scal_rfrac(x, y);
    2606                 :            :       }
    2607                 :    1188765 :       return div_rfrac(x,y);
    2608                 :            : 
    2609                 :          0 :     case t_QFI: av = avma; return gerepileupto(av, qficomp(x, ginv(y)));
    2610                 :          0 :     case t_QFR: av = avma; return gerepileupto(av, qfrcomp(x, ginv(y)));
    2611                 :            : 
    2612                 :            :     case t_MAT:
    2613                 :          0 :       av = avma; p1 = RgM_inv(y);
    2614         [ #  # ]:          0 :       if (!p1) pari_err_INV("gdiv",y);
    2615                 :          0 :       return gerepileupto(av, RgM_mul(x, p1));
    2616                 :            : 
    2617                 :          0 :     default: pari_err_TYPE2("/",x,y);
    2618                 :            :   }
    2619                 :            : 
    2620 [ +  + ][ +  + ]:   15379914 :   if (tx==t_INT && is_const_t(ty)) /* optimized for speed */
    2621                 :            :   {
    2622                 :     995632 :     long s = signe(x);
    2623         [ +  + ]:     995632 :     if (!s) {
    2624         [ -  + ]:      37084 :       if (gequal0(y)) pari_err_INV("gdiv",y);
    2625      [ +  +  + ]:      37084 :       switch (ty)
    2626                 :            :       {
    2627                 :      33941 :       default: return gen_0;
    2628                 :            :       case t_INTMOD:
    2629                 :         14 :         z = cgetg(3,t_INTMOD);
    2630                 :         14 :         gel(z,1) = icopy(gel(y,1));
    2631                 :         14 :         gel(z,2) = gen_0; return z;
    2632                 :       3129 :       case t_FFELT: return FF_zero(y);
    2633                 :            :       }
    2634                 :            :     }
    2635         [ +  + ]:     958548 :     if (is_pm1(x)) {
    2636         [ +  + ]:     540092 :       if (s > 0) return ginv(y);
    2637                 :      20433 :       av = avma; return gerepileupto(av, ginv(gneg(y)));
    2638                 :            :     }
    2639   [ +  +  +  +  :     418456 :     switch(ty)
             +  +  +  - ]
    2640                 :            :     {
    2641                 :     310246 :       case t_REAL: return divir(x,y);
    2642                 :            :       case t_INTMOD:
    2643                 :         42 :         z = cgetg(3, t_INTMOD);
    2644                 :         42 :         return div_intmod_same(z, gel(y,1), modii(x, gel(y,1)), gel(y,2));
    2645                 :            :       case t_FRAC:
    2646                 :      41730 :         z = cgetg(3,t_FRAC); p1 = gcdii(x,gel(y,1));
    2647         [ +  + ]:      41730 :         if (is_pm1(p1))
    2648                 :            :         {
    2649                 :      34283 :           avma = (pari_sp)z;
    2650                 :      34283 :           gel(z,2) = icopy(gel(y,1));
    2651                 :      34283 :           gel(z,1) = mulii(gel(y,2), x);
    2652                 :      34283 :           normalize_frac(z);
    2653         [ +  + ]:      34283 :           fix_frac_if_int(z);
    2654                 :            :         }
    2655                 :            :         else
    2656                 :            :         {
    2657                 :       7447 :           x = diviiexact(x,p1); tetpil = avma;
    2658                 :       7447 :           gel(z,2) = diviiexact(gel(y,1), p1);
    2659                 :       7447 :           gel(z,1) = mulii(gel(y,2), x);
    2660                 :       7447 :           normalize_frac(z);
    2661         [ +  + ]:       7447 :           fix_frac_if_int_GC(z,tetpil);
    2662                 :            :         }
    2663                 :      41730 :         return z;
    2664                 :            : 
    2665                 :        217 :       case t_FFELT: return Z_FF_div(x,y);
    2666                 :      66137 :       case t_COMPLEX: return divRc(x,y);
    2667                 :         42 :       case t_PADIC: return divTp(x, y);
    2668                 :            :       case t_QUAD:
    2669                 :         42 :         av = avma; p1 = quadnorm(y); p2 = mulRq(x, gconj(y)); tetpil = avma;
    2670                 :         42 :         return gerepile(av, tetpil, gdiv(p2,p1));
    2671                 :            :     }
    2672                 :            :   }
    2673 [ +  + ][ -  + ]:   14384282 :   if (gequal0(y) && ty != t_MAT) pari_err_INV("gdiv",y);
    2674                 :            : 
    2675 [ +  + ][ +  + ]:   14384282 :   if (is_const_t(tx) && is_const_t(ty)) switch(tx)
           [ +  +  +  +  
             +  +  +  - ]
    2676                 :            :   {
    2677                 :            :     case t_REAL:
    2678   [ +  +  +  +  :    2621187 :       switch(ty)
                      + ]
    2679                 :            :       {
    2680                 :    2361260 :         case t_INT: return divri(x,y);
    2681                 :            :         case t_FRAC:
    2682                 :     110516 :           av = avma; z = divri(mulri(x,gel(y,2)), gel(y,1));
    2683                 :     110516 :           return gerepileuptoleaf(av, z);
    2684                 :     149383 :         case t_COMPLEX: return divRc(x, y);
    2685                 :          7 :         case t_QUAD: return divfq(x, y, lg(x));
    2686                 :         21 :         default: pari_err_TYPE2("/",x,y);
    2687                 :            :       }
    2688                 :            : 
    2689                 :            :     case t_INTMOD:
    2690   [ +  +  +  -  :        560 :       switch(ty)
             +  +  +  - ]
    2691                 :            :       {
    2692                 :            :         case t_INT:
    2693                 :        427 :           z = cgetg(3, t_INTMOD);
    2694                 :        427 :           return div_intmod_same(z, gel(x,1), gel(x,2), modii(y, gel(x,1)));
    2695                 :         28 :         case t_FRAC: { GEN X = gel(x,1);
    2696                 :         28 :           z = cgetg(3,t_INTMOD); p1 = remii(mulii(gel(y,2), gel(x,2)), X);
    2697                 :         28 :           return div_intmod_same(z, X, p1, modii(gel(y,1), X));
    2698                 :            :         }
    2699                 :            :         case t_FFELT:
    2700         [ -  + ]:         63 :           if (!equalii(gel(x,1),FF_p_i(y)))
    2701                 :          0 :             pari_err_OP("/",x,y);
    2702                 :         63 :           return Z_FF_div(gel(x,2),y);
    2703                 :            : 
    2704                 :            :         case t_COMPLEX:
    2705                 :          0 :           av = avma;
    2706                 :          0 :           return gerepileupto(av, mulRc_direct(gdiv(x,cxnorm(y)), gconj(y)));
    2707                 :            : 
    2708                 :            :         case t_QUAD:
    2709                 :          7 :           av = avma; p1 = quadnorm(y); p2 = gmul(x,gconj(y)); tetpil = avma;
    2710                 :          7 :           return gerepile(av,tetpil, gdiv(p2,p1));
    2711                 :            : 
    2712                 :          7 :         case t_PADIC: { GEN X = gel(x,1);
    2713                 :          7 :           z = cgetg(3, t_INTMOD);
    2714                 :          7 :           return div_intmod_same(z, X, gel(x,2), padic_to_Fp(y, X));
    2715                 :            :         }
    2716                 :         28 :         case t_REAL: pari_err_TYPE2("/",x,y);
    2717                 :            :       }
    2718                 :            : 
    2719                 :            :     case t_FRAC:
    2720   [ +  +  +  +  :     309090 :       switch(ty)
             +  +  +  - ]
    2721                 :            :       {
    2722                 :     295657 :         case t_INT: z = cgetg(3, t_FRAC);
    2723                 :     295657 :         p1 = gcdii(y,gel(x,1));
    2724         [ +  + ]:     295657 :         if (is_pm1(p1))
    2725                 :            :         {
    2726                 :     136660 :           avma = (pari_sp)z; tetpil = 0;
    2727                 :     136660 :           gel(z,1) = icopy(gel(x,1));
    2728                 :            :         }
    2729                 :            :         else
    2730                 :            :         {
    2731                 :     158997 :           y = diviiexact(y,p1); tetpil = avma;
    2732                 :     158997 :           gel(z,1) = diviiexact(gel(x,1), p1);
    2733                 :            :         }
    2734                 :     295657 :         gel(z,2) = mulii(gel(x,2),y);
    2735                 :     295657 :         normalize_frac(z);
    2736 [ +  + ][ -  + ]:     295657 :         if (tetpil) fix_frac_if_int_GC(z,tetpil);
    2737                 :     295657 :         return z;
    2738                 :            : 
    2739                 :            :         case t_REAL:
    2740                 :      12579 :           av=avma; p1=mulri(y,gel(x,2)); tetpil=avma;
    2741                 :      12579 :           return gerepile(av, tetpil, divir(gel(x,1), p1));
    2742                 :            : 
    2743                 :          7 :         case t_INTMOD: { GEN Y = gel(y,1);
    2744                 :          7 :           z = cgetg(3,t_INTMOD); p1 = remii(mulii(gel(y,2),gel(x,2)), Y);
    2745                 :          7 :           return div_intmod_same(z, Y, modii(gel(x,1), Y), p1);
    2746                 :            :         }
    2747                 :            : 
    2748                 :         28 :         case t_FFELT: av=avma;
    2749                 :         28 :           return gerepileupto(av,Z_FF_div(gel(x,1),FF_Z_mul(y,gel(x,2))));
    2750                 :            : 
    2751                 :        798 :         case t_COMPLEX: return divRc(x, y);
    2752                 :            : 
    2753                 :            :         case t_PADIC:
    2754         [ -  + ]:         14 :           if (!signe(gel(x,1))) return gen_0;
    2755                 :         14 :           return divTp(x, y);
    2756                 :            : 
    2757                 :            :         case t_QUAD:
    2758                 :          7 :           av=avma; p1=quadnorm(y); p2=gmul(x,gconj(y)); tetpil=avma;
    2759                 :          7 :           return gerepile(av,tetpil,gdiv(p2,p1));
    2760                 :            :       }
    2761                 :            : 
    2762                 :            :     case t_FFELT:
    2763   [ +  +  +  + ]:       4459 :       switch (ty)
    2764                 :            :       {
    2765                 :       4340 :         case t_INT: return FF_Z_Z_muldiv(x,gen_1,y);
    2766                 :         28 :         case t_FRAC: return FF_Z_Z_muldiv(x,gel(y,2),gel(y,1));
    2767                 :            :         case t_INTMOD:
    2768         [ -  + ]:         49 :           if (!equalii(gel(y,1),FF_p_i(x)))
    2769                 :          0 :             pari_err_OP("/",x,y);
    2770                 :         49 :           return FF_Z_Z_muldiv(x,gen_1,gel(y,2));
    2771                 :            :         default:
    2772                 :         42 :         pari_err_TYPE2("/",x,y);
    2773                 :            :       }
    2774                 :          0 :       break;
    2775                 :            : 
    2776                 :            :     case t_COMPLEX:
    2777   [ +  -  -  -  :     597714 :       switch(ty)
                      - ]
    2778                 :            :       {
    2779                 :     597714 :         case t_INT: case t_REAL: case t_FRAC: return divcR(x,y);
    2780                 :          0 :         case t_INTMOD: return mulRc_direct(ginv(y), x);
    2781                 :            :         case t_PADIC:
    2782         [ #  # ]:          0 :           return Zp_nosquare_m1(gel(y,2))? divcR(x,y): divTp(x, y);
    2783                 :            :         case t_QUAD:
    2784         [ #  # ]:          0 :           lx = precision(x); if (!lx) pari_err_OP("/",x,y);
    2785                 :          0 :           return divfq(x, y, lx);
    2786                 :            :       }
    2787                 :            : 
    2788                 :            :     case t_PADIC:
    2789   [ +  +  +  +  :        973 :       switch(ty)
                      + ]
    2790                 :            :       {
    2791                 :        924 :         case t_INT: case t_FRAC: { GEN p = gel(x,2);
    2792                 :        924 :           return signe(gel(x,4))? divpT(x, y)
    2793         [ +  + ]:        924 :                             : zeropadic(p, valp(x) - Q_pval(y,p));
    2794                 :            :         }
    2795                 :          7 :         case t_INTMOD: { GEN Y = gel(y,1);
    2796                 :          7 :           z = cgetg(3, t_INTMOD);
    2797                 :          7 :           return div_intmod_same(z, Y, padic_to_Fp(x, Y), gel(y,2));
    2798                 :            :         }
    2799                 :            :         case t_COMPLEX: case t_QUAD:
    2800                 :          7 :           av=avma; p1=gmul(x,gconj(y)); p2=gnorm(y); tetpil=avma;
    2801                 :          7 :           return gerepile(av,tetpil,gdiv(p1,p2));
    2802                 :            : 
    2803                 :         28 :         case t_REAL: pari_err_TYPE2("/",x,y);
    2804                 :            :       }
    2805                 :            : 
    2806                 :            :     case t_QUAD:
    2807   [ +  +  +  -  :        889 :       switch (ty)
                      + ]
    2808                 :            :       {
    2809                 :            :         case t_INT: case t_INTMOD: case t_FRAC:
    2810                 :        840 :           z = cgetg(4,t_QUAD);
    2811                 :        840 :           gel(z,1) = ZX_copy(gel(x,1));
    2812                 :        840 :           gel(z,2) = gdiv(gel(x,2), y);
    2813                 :        840 :           gel(z,3) = gdiv(gel(x,3), y); return z;
    2814                 :         28 :         case t_REAL: return divqf(x, y, lg(y));
    2815                 :          7 :         case t_PADIC: return divTp(x, y);
    2816                 :            :         case t_COMPLEX:
    2817         [ #  # ]:          0 :           ly = precision(y); if (!ly) pari_err_OP("/",x,y);
    2818                 :          0 :           return divqf(x, y, ly);
    2819                 :            :       }
    2820                 :            :   }
    2821   [ +  +  -  + ]:   10849431 :   switch(ty) {
    2822                 :            :     case t_REAL: case t_INTMOD: case t_PADIC: case t_POLMOD:
    2823                 :      22709 :       return gmul(x, ginv(y)); /* missing gerepile, for speed */
    2824                 :            :     case t_MAT:
    2825                 :         28 :       av = avma; p1 = RgM_inv(y);
    2826         [ +  + ]:         28 :       if (!p1) pari_err_INV("gdiv",y);
    2827                 :         21 :       return gerepileupto(av, gmul(x, p1));
    2828                 :            :     case t_VEC: case t_COL:
    2829                 :            :     case t_LIST: case t_STR: case t_VECSMALL: case t_CLOSURE:
    2830                 :          0 :       pari_err_TYPE2("/",x,y);
    2831                 :            :   }
    2832      [ +  -  + ]:   10826694 :   switch(tx) {
    2833                 :            :     case t_VEC: case t_COL: case t_MAT:
    2834                 :     290153 :       z = cgetg_copy(x, &lx);
    2835         [ +  + ]:    1117165 :       for (i=1; i<lx; i++) gel(z,i) = gdiv(gel(x,i),y);
    2836                 :     290153 :       return z;
    2837                 :            :     case t_LIST: case t_STR: case t_VECSMALL: case t_CLOSURE:
    2838                 :          0 :       pari_err_TYPE2("/",x,y);
    2839                 :            :   }
    2840                 :            : 
    2841                 :   10536541 :   vy = gvar(y);
    2842         [ +  + ]:   10536541 :   if (tx == t_POLMOD) { GEN X = gel(x,1);
    2843                 :       7434 :     vx = varn(X);
    2844         [ +  + ]:       7434 :     if (vx != vy) {
    2845         [ +  + ]:       7273 :       if (varncmp(vx, vy) > 0) return div_scal_T(x, y, ty);
    2846                 :       7042 :       z = cgetg(3,t_POLMOD);
    2847                 :       7042 :       gel(z,1) = RgX_copy(X);
    2848                 :       7042 :       gel(z,2) = gdiv(gel(x,2), y); return z;
    2849                 :            :     }
    2850                 :            :     /* y is POL, SER or RFRAC */
    2851                 :        161 :     av = avma;
    2852         [ -  + ]:        161 :     switch(ty)
    2853                 :            :     {
    2854                 :          0 :       case t_RFRAC: y = gmod(ginv(y), X); break;
    2855                 :        161 :       default: y = ginvmod(gmod(y,X), X);
    2856                 :            :     }
    2857                 :        154 :     return gerepileupto(av, mul_polmod_same(X, gel(x,2), y));
    2858                 :            :   }
    2859                 :            :   /* x and y are not both is_scalar_t. If one of them is scalar, it's not a
    2860                 :            :    * POLMOD (done already), hence its variable is NO_VARIABLE. If the other has
    2861                 :            :    * variable NO_VARIABLE, then the operation is incorrect */
    2862                 :   10529107 :   vx = gvar(x);
    2863         [ +  + ]:   10529107 :   if (vx != vy) { /* includes cases where one is scalar */
    2864         [ +  + ]:    9935791 :     if (varncmp(vx, vy) < 0) return div_T_scal(x, y, tx);
    2865                 :    9146322 :                         else return div_scal_T(x, y, ty);
    2866                 :            :   }
    2867   [ +  +  +  + ]:     593316 :   switch(tx)
    2868                 :            :   {
    2869                 :            :     case t_POL:
    2870      [ +  +  - ]:      79838 :       switch(ty)
    2871                 :            :       {
    2872                 :            :         case t_SER:
    2873         [ -  + ]:         28 :           if (lg(y) == 2)
    2874                 :          0 :             return zeroser(vx, RgX_val(x) - valp(y));
    2875                 :         28 :           p1 = RgX_to_ser(x,lg(y));
    2876                 :         28 :           p2 = div_ser(p1, y, vx);
    2877                 :         28 :           settyp(p1, t_VECSMALL); /* p1 left on stack */
    2878                 :         28 :           return p2;
    2879                 :            : 
    2880                 :            :         case t_RFRAC:
    2881                 :            :         {
    2882                 :      79810 :           GEN y1 = gel(y,1), y2 = gel(y,2);
    2883 [ +  + ][ +  + ]:      79810 :           if (typ(y1) == t_POL && varn(y1) == vx)
    2884                 :      57431 :             return mul_rfrac_scal(y2, y1, x);
    2885                 :      22379 :           av = avma;
    2886                 :      22379 :           return gerepileupto(av, RgX_Rg_div(RgX_mul(y2, x), y1));
    2887                 :            :         }
    2888                 :            :       }
    2889                 :          0 :       break;
    2890                 :            : 
    2891                 :            :     case t_SER:
    2892      [ +  -  - ]:     260351 :       switch(ty)
    2893                 :            :       {
    2894                 :            :         case t_POL:
    2895         [ +  + ]:     260351 :           if (lg(x) == 2)
    2896                 :        105 :             return zeroser(vx, valp(x) - RgX_val(y));
    2897                 :     260246 :           p1 = RgX_to_ser_inexact(y,lg(x));
    2898                 :     260246 :           p2 = div_ser(x, p1, vx);
    2899                 :     260246 :           settyp(p1, t_VECSMALL); /* p1 left on stack */
    2900                 :     260246 :           return p2;
    2901                 :            :         case t_RFRAC:
    2902                 :          0 :           av = avma;
    2903                 :          0 :           return gerepileupto(av, gdiv(gmul(x,gel(y,2)), gel(y,1)));
    2904                 :            :       }
    2905                 :          0 :       break;
    2906                 :            : 
    2907                 :            :     case t_RFRAC:
    2908      [ +  -  - ]:     253113 :       switch(ty)
    2909                 :            :       {
    2910                 :     253113 :         case t_POL: return div_rfrac_pol(gel(x,1),gel(x,2), y);
    2911                 :            :         case t_SER:
    2912                 :          0 :           av = avma; z = RgX_to_ser_inexact(gel(x,2), lg(y));
    2913                 :          0 :           return gerepileupto(av, gdiv(gel(x,1), gmul(z,y)));
    2914                 :            :       }
    2915                 :          0 :       break;
    2916                 :            :   }
    2917                 :         14 :   pari_err_TYPE2("/",x,y);
    2918                 :   85815809 :   return NULL; /* not reached */
    2919                 :            : }
    2920                 :            : 
    2921                 :            : /********************************************************************/
    2922                 :            : /**                                                                **/
    2923                 :            : /**                     SIMPLE MULTIPLICATION                      **/
    2924                 :            : /**                                                                **/
    2925                 :            : /********************************************************************/
    2926                 :            : GEN
    2927                 :   14897459 : gmulsg(long s, GEN y)
    2928                 :            : {
    2929                 :            :   long ly, i;
    2930                 :            :   pari_sp av;
    2931                 :            :   GEN z;
    2932                 :            : 
    2933   [ +  +  +  +  :   14897459 :   switch(typ(y))
          +  +  +  +  +  
             +  +  +  +  
                      - ]
    2934                 :            :   {
    2935                 :    7403863 :     case t_INT:  return mulsi(s,y);
    2936                 :    5613222 :     case t_REAL: return mulsr(s,y);
    2937                 :     166152 :     case t_INTMOD: { GEN p = gel(y,1);
    2938                 :     166152 :       z = cgetg(3,t_INTMOD);
    2939                 :     166152 :       gel(z,2) = gerepileuptoint((pari_sp)z, modii(mulsi(s,gel(y,2)), p));
    2940                 :     166152 :       gel(z,1) = icopy(p); return z;
    2941                 :            :     }
    2942                 :     259357 :     case t_FFELT: return FF_Z_mul(y,stoi(s));
    2943                 :            :     case t_FRAC:
    2944         [ +  + ]:      87045 :       if (!s) return gen_0;
    2945                 :      86835 :       z = cgetg(3,t_FRAC);
    2946                 :      86835 :       i = cgcd(s, smodis(gel(y,2), s));
    2947         [ +  + ]:      86835 :       if (i == 1)
    2948                 :            :       {
    2949                 :      73857 :         gel(z,2) = icopy(gel(y,2));
    2950                 :      73857 :         gel(z,1) = mulis(gel(y,1), s);
    2951                 :            :       }
    2952                 :            :       else
    2953                 :            :       {
    2954                 :      12978 :         gel(z,2) = divis(gel(y,2), i);
    2955                 :      12978 :         gel(z,1) = mulis(gel(y,1), s/i);
    2956         [ +  + ]:      12978 :         fix_frac_if_int(z);
    2957                 :            :       }
    2958                 :      86835 :       return z;
    2959                 :            : 
    2960                 :     947553 :     case t_COMPLEX: z = cgetg(3, t_COMPLEX);
    2961                 :     947553 :       gel(z,1) = gmulsg(s,gel(y,1));
    2962                 :     947553 :       gel(z,2) = gmulsg(s,gel(y,2)); return z;
    2963                 :            : 
    2964                 :            :     case t_PADIC:
    2965         [ -  + ]:        714 :       if (!s) return gen_0;
    2966                 :        714 :       av = avma; return gerepileupto(av, mulpp(cvtop2(stoi(s),y), y));
    2967                 :            : 
    2968                 :          7 :     case t_QUAD: z = cgetg(4, t_QUAD);
    2969                 :          7 :       gel(z,1) = ZX_copy(gel(y,1));
    2970                 :          7 :       gel(z,2) = gmulsg(s,gel(y,2));
    2971                 :          7 :       gel(z,3) = gmulsg(s,gel(y,3)); return z;
    2972                 :            : 
    2973                 :       4907 :     case t_POLMOD: z = cgetg(3, t_POLMOD);
    2974                 :       4907 :       gel(z,1) = RgX_copy(gel(y,1));
    2975                 :       4907 :       gel(z,2) = gmulsg(s,gel(y,2)); return z;
    2976                 :            : 
    2977                 :            :     case t_POL:
    2978         [ +  + ]:     225897 :       if (!signe(y)) return RgX_copy(y);
    2979         [ +  + ]:     221858 :       if (!s) return scalarpol(RgX_get_0(y), varn(y));
    2980                 :     217798 :       z = cgetg_copy(y, &ly); z[1]=y[1];
    2981         [ +  + ]:     922712 :       for (i=2; i<ly; i++) gel(z,i) = gmulsg(s,gel(y,i));
    2982                 :     217798 :       return normalizepol_lg(z, ly);
    2983                 :            : 
    2984                 :            :     case t_SER:
    2985         [ -  + ]:      18614 :       if (ser_isexactzero(y)) return gcopy(y);
    2986         [ -  + ]:      18614 :       if (!s) return scalarser(RgX_get_0(y), varn(y), valp(y));
    2987                 :      18614 :       z = cgetg_copy(y, &ly); z[1]=y[1];
    2988         [ +  + ]:      56583 :       for (i=2; i<ly; i++) gel(z,i) = gmulsg(s,gel(y,i));
    2989                 :      18614 :       return normalize(z);
    2990                 :            : 
    2991                 :            :     case t_RFRAC:
    2992         [ -  + ]:         14 :       if (!s) return zeropol(varn(gel(y,2)));
    2993         [ -  + ]:         14 :       if (s == 1) return gcopy(y);
    2994         [ -  + ]:         14 :       if (s == -1) return gneg(y);
    2995                 :         14 :       return mul_rfrac_scal(gel(y,1), gel(y,2), stoi(s));
    2996                 :            : 
    2997                 :            :     case t_VEC: case t_COL: case t_MAT:
    2998                 :     170114 :       z = cgetg_copy(y, &ly);
    2999         [ +  + ]:     678369 :       for (i=1; i<ly; i++) gel(z,i) = gmulsg(s,gel(y,i));
    3000                 :     170114 :       return z;
    3001                 :            :   }
    3002                 :          0 :   pari_err_TYPE("gmulsg",y);
    3003                 :   14897459 :   return NULL; /* not reached */
    3004                 :            : }
    3005                 :            : 
    3006                 :            : /********************************************************************/
    3007                 :            : /**                                                                **/
    3008                 :            : /**                       SIMPLE DIVISION                          **/
    3009                 :            : /**                                                                **/
    3010                 :            : /********************************************************************/
    3011                 :            : 
    3012                 :            : GEN
    3013                 :    4210170 : gdivgs(GEN x, long s)
    3014                 :            : {
    3015                 :            :   long lx, i;
    3016                 :            :   pari_sp av;
    3017                 :            :   GEN z, y, p1;
    3018                 :            : 
    3019         [ -  + ]:    4210170 :   if (!s) pari_err_INV("gdivgs",gen_0);
    3020   [ +  +  +  +  :    4210170 :   switch(typ(x))
          +  +  +  -  +  
             +  +  +  - ]
    3021                 :            :   {
    3022                 :            :     case t_INT:
    3023                 :     219372 :       av = avma; z = divis_rem(x,s,&i);
    3024         [ +  + ]:     219372 :       if (!i) return z;
    3025                 :            : 
    3026                 :     158151 :       i = cgcd(s, i);
    3027                 :     158151 :       avma=av; z = cgetg(3,t_FRAC);
    3028         [ +  + ]:     158151 :       if (i == 1) y = icopy(x); else { s /= i; y = diviuexact(x, i); }
    3029                 :     158151 :       gel(z,1) = y;
    3030                 :     158151 :       gel(z,2) = stoi(s); normalize_frac(z); return z;
    3031                 :            : 
    3032                 :            :     case t_REAL:
    3033                 :    2746002 :       return divrs(x,s);
    3034                 :            : 
    3035                 :            :     case t_INTMOD:
    3036                 :       7350 :       z = cgetg(3, t_INTMOD);
    3037                 :       7350 :       return div_intmod_same(z, gel(x,1), gel(x,2), modsi(s, gel(x,1)));
    3038                 :            : 
    3039                 :        399 :     case t_FFELT: return FF_Z_Z_muldiv(x,gen_1,stoi(s));
    3040                 :            : 
    3041                 :      36708 :     case t_FRAC: z = cgetg(3, t_FRAC);
    3042                 :      36708 :       i = cgcd(s, smodis(gel(x,1), s));
    3043         [ +  + ]:      36708 :       if (i == 1)
    3044                 :            :       {
    3045                 :      32844 :         gel(z,2) = mulsi(s, gel(x,2));
    3046                 :      32844 :         gel(z,1) = icopy(gel(x,1));
    3047                 :            :       }
    3048                 :            :       else
    3049                 :            :       {
    3050                 :       3864 :         gel(z,2) = mulsi(s/i, gel(x,2));
    3051                 :       3864 :         gel(z,1) = divis(gel(x,1), i);
    3052                 :            :       }
    3053                 :      36708 :       normalize_frac(z);
    3054         [ +  + ]:      36708 :       fix_frac_if_int(z); return z;
    3055                 :            : 
    3056                 :    1159032 :     case t_COMPLEX: z = cgetg(3, t_COMPLEX);
    3057                 :    1159032 :       gel(z,1) = gdivgs(gel(x,1),s);
    3058                 :    1159032 :       gel(z,2) = gdivgs(gel(x,2),s); return z;
    3059                 :            : 
    3060                 :            :     case t_PADIC: /* divpT */
    3061                 :            :     {
    3062                 :      37296 :       GEN p = gel(x,2);
    3063         [ +  + ]:      37296 :       if (!signe(gel(x,4))) return zeropadic(p, valp(x) - u_pval(s,p));
    3064                 :      36918 :       av = avma;
    3065                 :      36918 :       return gerepileupto(av, divpp(x, cvtop2(stoi(s),x)));
    3066                 :            :     }
    3067                 :            : 
    3068                 :          0 :     case t_QUAD: z = cgetg(4, t_QUAD);
    3069                 :          0 :       gel(z,1) = ZX_copy(gel(x,1));
    3070                 :          0 :       gel(z,2) = gdivgs(gel(x,2),s);
    3071                 :          0 :       gel(z,3) = gdivgs(gel(x,3),s); return z;
    3072                 :            : 
    3073                 :       1477 :     case t_POLMOD: z = cgetg(3, t_POLMOD);
    3074                 :       1477 :       gel(z,1) = RgX_copy(gel(x,1));
    3075                 :       1477 :       gel(z,2) = gdivgs(gel(x,2),s); return z;
    3076                 :            : 
    3077                 :            :     case t_RFRAC:
    3078                 :         91 :       av = avma;
    3079                 :         91 :       p1 = ggcd(stoi(s),gel(x,1));
    3080         [ +  + ]:         91 :       if (typ(p1) == t_INT)
    3081                 :            :       {
    3082                 :         35 :         avma = av;
    3083                 :         35 :         z = cgetg(3, t_RFRAC);
    3084                 :         35 :         i = p1[2];
    3085         [ +  - ]:         35 :         if (i == 1)
    3086                 :            :         {
    3087                 :         35 :           gel(z,1) = gcopy(gel(x,1));
    3088                 :         35 :           gel(z,2) = gmulsg(s,gel(x,2));
    3089                 :            :         }
    3090                 :            :         else
    3091                 :            :         {
    3092                 :          0 :           gel(z,1) = gdivgs(gel(x,1), i);
    3093                 :          0 :           gel(z,2) = gmulgs(gel(x,2), s/i);
    3094                 :            :         }
    3095                 :            :       }
    3096                 :            :       else /* t_FRAC */
    3097                 :            :       {
    3098                 :         56 :         z = cgetg(3, t_RFRAC);
    3099                 :         56 :         gel(z,1) = gdiv(gel(x,1), p1);
    3100                 :         56 :         gel(z,2) = RgX_Rg_mul(gel(x,2), gdivsg(s,p1));
    3101                 :         56 :         z = gerepilecopy(av, z);
    3102                 :            :       }
    3103                 :         91 :       return z;
    3104                 :            : 
    3105                 :            :     case t_POL: case t_SER:
    3106                 :       2401 :       z = cgetg_copy(x, &lx); z[1] = x[1];
    3107         [ +  + ]:       7497 :       for (i=2; i<lx; i++) gel(z,i) = gdivgs(gel(x,i),s);
    3108                 :       2401 :       return z;
    3109                 :            :     case t_VEC: case t_COL: case t_MAT:
    3110                 :         42 :       z = cgetg_copy(x, &lx);
    3111         [ +  + ]:        126 :       for (i=1; i<lx; i++) gel(z,i) = gdivgs(gel(x,i),s);
    3112                 :         42 :       return z;
    3113                 :            : 
    3114                 :            :   }
    3115                 :          0 :   pari_err_TYPE2("/",x, stoi(s));
    3116                 :    4210170 :   return NULL; /* not reached */
    3117                 :            : }
    3118                 :            : 
    3119                 :            : /* True shift (exact multiplication by 2^n) */
    3120                 :            : GEN
    3121                 :   28807385 : gmul2n(GEN x, long n)
    3122                 :            : {
    3123                 :            :   long lx, i, k, l;
    3124                 :            :   GEN z, a, b;
    3125                 :            : 
    3126   [ +  +  +  +  :   28807385 :   switch(typ(x))
          +  +  +  +  +  
             +  +  +  +  
                      - ]
    3127                 :            :   {
    3128                 :            :     case t_INT:
    3129         [ +  + ]:   20785910 :       if (n>=0) return shifti(x,n);
    3130         [ +  + ]:     105350 :       if (!signe(x)) return gen_0;
    3131                 :      55181 :       l = vali(x); n = -n;
    3132         [ +  + ]:      55181 :       if (n<=l) return shifti(x,-n);
    3133                 :      34741 :       z = cgetg(3,t_FRAC);
    3134                 :      34741 :       gel(z,1) = shifti(x,-l);
    3135                 :      34741 :       gel(z,2) = int2n(n-l); return z;
    3136                 :            : 
    3137                 :            :     case t_REAL:
    3138                 :    4245697 :       return shiftr(x,n);
    3139                 :            : 
    3140                 :      73178 :     case t_INTMOD: b = gel(x,1); a = gel(x,2);
    3141                 :      73178 :       z = cgetg(3,t_INTMOD);
    3142         [ +  + ]:      73178 :       if (n <= 0) return div_intmod_same(z, b, a, modii(int2n(-n), b));
    3143                 :      73171 :       gel(z,2) = gerepileuptoint((pari_sp)z, modii(shifti(a,n), b));
    3144                 :      73171 :       gel(z,1) = icopy(b); return z;
    3145                 :            : 
    3146                 :      92754 :     case t_FFELT: return FF_mul2n(x,n);
    3147                 :            : 
    3148                 :      80797 :     case t_FRAC: a = gel(x,1); b = gel(x,2);
    3149                 :      80797 :       l = vali(a);
    3150                 :      80797 :       k = vali(b);
    3151         [ +  + ]:      80797 :       if (n+l >= k)
    3152                 :            :       {
    3153         [ +  + ]:      50926 :         if (expi(b) == k) return shifti(a,n-k); /* b power of 2 */
    3154                 :      43681 :         l = n-k; k = -k;
    3155                 :            :       }
    3156                 :            :       else
    3157                 :            :       {
    3158                 :      29871 :         k = -(l+n); l = -l;
    3159                 :            :       }
    3160                 :      73552 :       z = cgetg(3,t_FRAC);
    3161                 :      73552 :       gel(z,1) = shifti(a,l);
    3162                 :      73552 :       gel(z,2) = shifti(b,k); return z;
    3163                 :            : 
    3164                 :    2515810 :     case t_COMPLEX: z = cgetg(3,t_COMPLEX);
    3165                 :    2515810 :       gel(z,1) = gmul2n(gel(x,1),n);
    3166                 :    2515810 :       gel(z,2) = gmul2n(gel(x,2),n); return z;
    3167                 :            : 
    3168                 :         14 :     case t_QUAD: z = cgetg(4,t_QUAD);
    3169                 :         14 :       gel(z,1) = ZX_copy(gel(x,1));
    3170                 :         14 :       gel(z,2) = gmul2n(gel(x,2),n);
    3171                 :         14 :       gel(z,3) = gmul2n(gel(x,3),n); return z;
    3172                 :            : 
    3173                 :      13245 :     case t_POLMOD: z = cgetg(3,t_POLMOD);
    3174                 :      13245 :       gel(z,1) = RgX_copy(gel(x,1));
    3175                 :      13245 :       gel(z,2) = gmul2n(gel(x,2),n); return z;
    3176                 :            : 
    3177                 :            :     case t_POL:
    3178                 :     259564 :       z = cgetg_copy(x, &lx); z[1] = x[1];
    3179         [ +  + ]:    2154417 :       for (i=2; i<lx; i++) gel(z,i) = gmul2n(gel(x,i),n);
    3180                 :     259564 :       return normalizepol_lg(z, lx); /* needed if char = 2 */
    3181                 :            :     case t_SER:
    3182         [ +  + ]:      50967 :       if (ser_isexactzero(x)) return gcopy(x);
    3183                 :      50953 :       z = cgetg_copy(x, &lx); z[1] = x[1];
    3184         [ +  + ]:     827806 :       for (i=2; i<lx; i++) gel(z,i) = gmul2n(gel(x,i),n);
    3185                 :      50953 :       return normalize(z); /* needed if char = 2 */
    3186                 :            :     case t_VEC: case t_COL: case t_MAT:
    3187                 :     687041 :       z = cgetg_copy(x, &lx);
    3188         [ +  + ]:    2811045 :       for (i=1; i<lx; i++) gel(z,i) = gmul2n(gel(x,i),n);
    3189                 :     687041 :       return z;
    3190                 :            : 
    3191                 :            :     case t_RFRAC: /* int2n wrong if n < 0 */
    3192                 :         14 :       return mul_rfrac_scal(gel(x,1),gel(x,2), gmul2n(gen_1,n));
    3193                 :            : 
    3194                 :            :     case t_PADIC: /* int2n wrong if n < 0 */
    3195                 :       2394 :       return gmul(gmul2n(gen_1,n),x);
    3196                 :            :   }
    3197                 :          0 :   pari_err_TYPE("gmul2n",x);
    3198                 :   28807385 :   return NULL; /* not reached */
    3199                 :            : }
    3200                 :            : 
    3201                 :            : /*******************************************************************/
    3202                 :            : /*                                                                 */
    3203                 :            : /*                              INVERSE                            */
    3204                 :            : /*                                                                 */
    3205                 :            : /*******************************************************************/
    3206                 :            : static GEN
    3207                 :      23285 : inv_polmod(GEN T, GEN x)
    3208                 :            : {
    3209                 :      23285 :   GEN z = cgetg(3,t_POLMOD), a;
    3210                 :      23285 :   gel(z,1) = RgX_copy(T);
    3211 [ +  + ][ +  + ]:      23285 :   if (typ(x) != t_POL || varn(x) != varn(T) || lg(x) <= 3)
                 [ +  + ]
    3212                 :       8575 :     a = ginv(x);
    3213                 :            :   else
    3214                 :            :   {
    3215                 :      14710 :     pari_sp av = avma;
    3216         [ +  + ]:      14710 :     if (lg(T) == 5) /* quadratic fields */
    3217                 :      11305 :       a = RgX_Rg_div(quad_polmod_conj(x,T), quad_polmod_norm(x,T));
    3218                 :            :     else
    3219                 :            :     {
    3220                 :       3405 :       GEN p = NULL;
    3221 [ +  + ][ +  + ]:       3405 :       if (RgX_is_FpX(T, &p) && RgX_is_FpX(x, &p) && p)
                 [ +  + ]
    3222                 :            :       {
    3223                 :         14 :         T = RgX_to_FpX(T, p); x = RgX_to_FpX(x, p);
    3224         [ +  + ]:         14 :         if (lgefint(p) == 3)
    3225                 :            :         {
    3226                 :          7 :           ulong pp = p[2];
    3227                 :          7 :           a = Flxq_inv(ZX_to_Flx(x, pp), ZX_to_Flx(T, pp), pp);
    3228                 :          7 :           a = Flx_to_ZX(a);
    3229                 :            :         }
    3230                 :            :         else
    3231                 :          7 :           a = FpXQ_inv(x, T, p);
    3232                 :         14 :         a = FpX_to_mod(a, p);
    3233                 :         14 :         a = gerepileupto(av, a);
    3234                 :            :       }
    3235                 :            :       else {
    3236                 :       3391 :         avma = av;
    3237                 :       3405 :         a = RgXQ_inv(x, gel(z,1));
    3238                 :            :       }
    3239                 :            :     }
    3240                 :            :   }
    3241                 :      23285 :   gel(z,2) = a; return z;
    3242                 :            : }
    3243                 :            : GEN
    3244                 :    7221034 : ginv(GEN x)
    3245                 :            : {
    3246                 :            :   long s;
    3247                 :            :   pari_sp av, tetpil;
    3248                 :            :   GEN z, y, p1, p2;
    3249                 :            : 
    3250   [ +  +  +  +  :    7221034 :   switch(typ(x))
          +  +  +  +  +  
          +  +  +  +  +  
                +  -  - ]
    3251                 :            :   {
    3252                 :            :     case t_INT:
    3253         [ +  + ]:      72296 :       if (is_pm1(x)) return icopy(x);
    3254         [ -  + ]:      40089 :       s = signe(x); if (!s) pari_err_INV("ginv",gen_0);
    3255                 :      40089 :       z = cgetg(3,t_FRAC);
    3256         [ +  + ]:      40089 :       gel(z,1) = s<0? gen_m1: gen_1;
    3257                 :      40089 :       gel(z,2) = absi(x); return z;
    3258                 :            : 
    3259                 :     652490 :     case t_REAL: return invr(x);
    3260                 :            : 
    3261                 :        763 :     case t_INTMOD: z=cgetg(3,t_INTMOD);
    3262                 :        763 :       gel(z,1) = icopy(gel(x,1));
    3263                 :        763 :       gel(z,2) = Fp_inv(gel(x,2),gel(x,1)); return z;
    3264                 :            : 
    3265                 :            :     case t_FRAC: {
    3266                 :      91015 :       GEN a = gel(x,1), b = gel(x,2);
    3267                 :      91015 :       s = signe(a);
    3268 [ +  + ][ +  + ]:      91015 :       if (is_pm1(a)) return s > 0? icopy(b): negi(b);
    3269                 :      28133 :       z = cgetg(3,t_FRAC);
    3270                 :      28133 :       gel(z,1) = icopy(b);
    3271                 :      28133 :       gel(z,2) = icopy(a);
    3272                 :      28133 :       normalize_frac(z); return z;
    3273                 :            :     }
    3274                 :            :     case t_COMPLEX:
    3275                 :    1070013 :       av=avma;
    3276                 :    1070013 :       p1=cxnorm(x);
    3277                 :    1070013 :       p2=mkcomplex(gel(x,1), gneg(gel(x,2)));
    3278                 :    1070013 :       tetpil=avma;
    3279                 :    1070013 :       return gerepile(av,tetpil,divcR(p2,p1));
    3280                 :            : 
    3281                 :            :     case t_QUAD:
    3282                 :        203 :       av=avma; p1=gnorm(x); p2=gconj(x); tetpil=avma;
    3283                 :        203 :       return gerepile(av,tetpil,gdiv(p2,p1));
    3284                 :            : 
    3285                 :       2506 :     case t_PADIC: z = cgetg(5,t_PADIC);
    3286         [ +  + ]:       2506 :       if (!signe(gel(x,4))) pari_err_INV("ginv",x);
    3287                 :       2499 :       z[1] = _evalprecp(precp(x)) | evalvalp(-valp(x));
    3288                 :       2499 :       gel(z,2) = icopy(gel(x,2));
    3289                 :       2499 :       gel(z,3) = icopy(gel(x,3));
    3290                 :       2499 :       gel(z,4) = Fp_inv(gel(x,4),gel(z,3)); return z;
    3291                 :            : 
    3292                 :      23285 :     case t_POLMOD: return inv_polmod(gel(x,1), gel(x,2));
    3293                 :       4438 :     case t_FFELT: return FF_inv(x);
    3294                 :    5289822 :     case t_POL: return gred_rfrac_simple(gen_1,x);
    3295                 :        343 :     case t_SER: return gdiv(gen_1,x);
    3296                 :            : 
    3297                 :            :     case t_RFRAC:
    3298                 :            :     {
    3299                 :       2905 :       GEN n = gel(x,1), d = gel(x,2);
    3300                 :       2905 :       pari_sp av = avma, ltop;
    3301         [ -  + ]:       2905 :       if (gequal0(n)) pari_err_INV("ginv",x);
    3302                 :            : 
    3303                 :       2905 :       n = simplify_shallow(n);
    3304 [ +  + ][ +  - ]:       2905 :       if (typ(n) != t_POL || varn(n) != varn(d))
    3305                 :            :       {
    3306         [ +  + ]:       2905 :         if (gequal1(n)) { avma = av; return RgX_copy(d); }
    3307                 :        679 :         ltop = avma;
    3308                 :        679 :         z = RgX_Rg_div(d,n);
    3309                 :            :       } else {
    3310                 :          0 :         ltop = avma;
    3311                 :          0 :         z = cgetg(3,t_RFRAC);
    3312                 :          0 :         gel(z,1) = RgX_copy(d);
    3313                 :          0 :         gel(z,2) = RgX_copy(n);
    3314                 :            :       }
    3315                 :        679 :       stackdummy(av, ltop);
    3316                 :        679 :       return z;
    3317                 :            :     }
    3318                 :            : 
    3319                 :            :     case t_QFR:
    3320                 :          7 :       av = avma; z = cgetg(5, t_QFR);
    3321                 :          7 :       gel(z,1) = gel(x,1);
    3322                 :          7 :       gel(z,2) = negi( gel(x,2) );
    3323                 :          7 :       gel(z,3) = gel(x,3);
    3324                 :          7 :       gel(z,4) = negr( gel(x,4) );
    3325                 :          7 :       return gerepileupto(av, redreal(z));
    3326                 :            : 
    3327                 :            :     case t_QFI:
    3328                 :       9737 :       y = gcopy(x);
    3329 [ +  + ][ +  + ]:       9737 :       if (!equalii(gel(x,1),gel(x,2)) && !equalii(gel(x,1),gel(x,3)))
    3330                 :       9478 :         togglesign(gel(y,2));
    3331                 :       9737 :       return y;
    3332                 :            :     case t_MAT:
    3333                 :            :     {
    3334                 :       1211 :       GEN ff = NULL;
    3335         [ +  + ]:       1211 :       if (RgM_is_FFM(x,&ff))
    3336                 :         21 :         y = FFM_inv(x, ff);
    3337                 :            :       else
    3338                 :       1190 :         y = RgM_inv(x);
    3339         [ -  + ]:       1211 :       if (!y) pari_err_INV("ginv",x);
    3340                 :       1211 :       return y;
    3341                 :            :     }
    3342                 :            :     case t_VECSMALL:
    3343                 :            :     {
    3344                 :          0 :       long i, lx = lg(x)-1;
    3345                 :          0 :       y = zero_zv(lx);
    3346         [ #  # ]:          0 :       for (i=1; i<=lx; i++)
    3347                 :            :       {
    3348                 :          0 :         long xi = x[i];
    3349 [ #  # ][ #  # ]:          0 :         if (xi<1 || xi>lx || y[xi])
                 [ #  # ]
    3350                 :          0 :           pari_err_TYPE("ginv [not a permutation]", x);
    3351                 :          0 :         y[xi] = i;
    3352                 :            :       }
    3353                 :          0 :       return y;
    3354                 :            :     }
    3355                 :            :   }
    3356                 :          0 :   pari_err_TYPE("inverse",x);
    3357                 :    7221020 :   return NULL; /* not reached */
    3358                 :            : }

Generated by: LCOV version 1.9