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 - polarit1.c (source / functions) Hit Total Coverage
Test: PARI/GP v2.8.0 lcov report (development 16741-1378b1c) Lines: 315 328 96.0 %
Date: 2014-08-17 Functions: 31 31 100.0 %
Legend: Lines: hit not hit | Branches: + taken - not taken # not executed Branches: 187 266 70.3 %

           Branch data     Line data    Source code
       1                 :            : /* Copyright (C) 2000-2004  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                 :            : /**               ARITHMETIC OPERATIONS ON POLYNOMIALS                **/
      17                 :            : /**                         (first part)                              **/
      18                 :            : /**                                                                   **/
      19                 :            : /***********************************************************************/
      20                 :            : #include "pari.h"
      21                 :            : #include "paripriv.h"
      22                 :            : /*******************************************************************/
      23                 :            : /*                                                                 */
      24                 :            : /*                  POLYNOMIAL EUCLIDEAN DIVISION                  */
      25                 :            : /*                                                                 */
      26                 :            : /*******************************************************************/
      27                 :            : /* x t_POLMOD, y t_POL in the same variable as x[1], return x % y */
      28                 :            : static GEN
      29                 :         20 : polmod_mod(GEN x, GEN y)
      30                 :            : {
      31                 :         20 :   GEN z, a, T = gel(x,1);
      32         [ +  + ]:         20 :   if (RgX_equal(T, y)) return gcopy(x);
      33                 :         10 :   z = cgetg(3,t_POLMOD); T = RgX_gcd(T,y); a = gel(x,2);
      34                 :         10 :   gel(z,1) = T;
      35 [ +  - ][ +  - ]:         10 :   gel(z,2) = (typ(a)==t_POL && varn(a)==varn(T))? RgX_rem(a, T): gcopy(a);
      36                 :         20 :   return z;
      37                 :            : }
      38                 :            : /* x,y two "scalars", return 0 with type info */
      39                 :            : static GEN
      40                 :          5 : rem_scal_scal(GEN x, GEN y)
      41                 :            : {
      42                 :          5 :   pari_sp av = avma;
      43                 :          5 :   GEN z = gadd(gmul(gen_0,x), gmul(gen_0,y));
      44         [ -  + ]:          5 :   if (gequal0(y)) pari_err_INV("grem",y);
      45                 :          5 :   return gerepileupto(av, simplify(z));
      46                 :            : }
      47                 :            : /* x pol, y "scalar", return 0 with type info */
      48                 :            : static GEN
      49                 :         80 : rem_pol_scal(GEN x, GEN y)
      50                 :            : {
      51                 :         80 :   pari_sp av = avma;
      52         [ -  + ]:         80 :   if (gequal0(y)) pari_err_INV("grem",y);
      53                 :         80 :   return gerepileupto(av, simplify(gmul(RgX_get_0(x),y)));
      54                 :            : }
      55                 :            : /* x "scalar", y pol, return x % y with type info */
      56                 :            : static GEN
      57                 :      41200 : rem_scal_pol(GEN x, GEN y)
      58                 :            : {
      59         [ +  - ]:      41200 :   if (degpol(y))
      60                 :            :   {
      61         [ -  + ]:      41200 :     if (!signe(y)) pari_err_INV("grem",y);
      62                 :      41200 :     return gmul(x, RgX_get_1(y));
      63                 :            :   }
      64                 :      41200 :   y = gel(y,2); return rem_scal_scal(x,y);
      65                 :            : }
      66                 :            : GEN
      67                 :        130 : poldivrem(GEN x, GEN y, GEN *pr)
      68                 :            : {
      69                 :        130 :   const char *f = "euclidean division";
      70                 :        130 :   long tx = typ(x), ty = typ(y), vx = gvar(x), vy = gvar(y);
      71                 :            :   GEN z;
      72                 :            : 
      73 [ +  - ][ -  + ]:        130 :   if (!is_extscalar_t(tx) || !is_extscalar_t(ty)) pari_err_TYPE2(f,x,y);
      74 [ +  + ][ +  + ]:        130 :   if (vx == vy && ((tx==t_POLMOD) ^ (ty==t_POLMOD))) pari_err_TYPE2(f,x,y);
      75 [ +  + ][ -  + ]:        120 :   if (ty != t_POL || varncmp(vx, vy) < 0) /* y "scalar" */
      76                 :            :   {
      77 [ +  - ][ -  + ]:         45 :     if (!pr || pr == ONLY_DIVIDES) return gdiv(x,y);
      78 [ +  - ][ -  + ]:         45 :     if (tx != t_POL || varncmp(vy, vx) < 0) /* x "scalar" */
      79                 :          0 :       z = rem_scal_scal(x,y);
      80                 :            :     else
      81                 :         45 :       z = rem_pol_scal(x,y);
      82         [ -  + ]:         45 :     if (pr == ONLY_REM) return z;
      83                 :         45 :     *pr = z; return gdiv(x,y);
      84                 :            :   }
      85 [ +  + ][ -  + ]:         75 :   if (tx != t_POL || varncmp(vx, vy) > 0) /* x "scalar" */
      86                 :            :   {
      87         [ +  + ]:         55 :     if (!degpol(y)) /* constant t_POL, treat as scalar */
      88                 :            :     {
      89                 :          5 :       y = gel(y,2);
      90 [ +  - ][ -  + ]:          5 :       if (!pr || pr == ONLY_DIVIDES) gdiv(x,y);
      91                 :          5 :       z = rem_scal_scal(x,y);
      92         [ -  + ]:          5 :       if (pr == ONLY_REM) return z;
      93                 :          5 :       *pr = z; return gdiv(x,y);
      94                 :            :     }
      95         [ -  + ]:         50 :     if (!signe(y)) pari_err_INV("poldivrem",y);
      96 [ +  - ][ -  + ]:         50 :     if (!pr || pr == ONLY_DIVIDES) return gequal0(x)? RgX_get_0(y): NULL;
                 [ #  # ]
      97                 :         50 :     z = gmul(x, RgX_get_1(y));
      98         [ -  + ]:         50 :     if (pr == ONLY_REM) return z;
      99                 :         50 :     *pr = z; return RgX_get_0(y);
     100                 :            :   }
     101                 :        120 :   return RgX_divrem(x,y,pr);
     102                 :            : }
     103                 :            : GEN
     104                 :        285 : gdeuc(GEN x, GEN y)
     105                 :            : {
     106                 :        285 :   const char *f = "euclidean division";
     107                 :        285 :   long tx = typ(x), ty = typ(y), vx = gvar(x), vy = gvar(y);
     108 [ +  + ][ -  + ]:        285 :   if (!is_extscalar_t(tx) || !is_extscalar_t(ty)) pari_err_TYPE2(f,x,y);
     109 [ +  + ][ +  + ]:        275 :   if (vx == vy && ((tx==t_POLMOD) ^ (ty==t_POLMOD))) pari_err_TYPE2(f,x,y);
     110 [ +  + ][ -  + ]:        255 :   if (ty != t_POL || varncmp(vx, vy) < 0) return gdiv(x,y); /* y "scalar" */
     111 [ +  + ][ -  + ]:        170 :   if (tx != t_POL || varncmp(vx, vy) > 0)
     112                 :            :   { /* x "scalar" */
     113         [ -  + ]:         95 :     if (!signe(y)) pari_err_INV("gdeuc",y);
     114         [ -  + ]:         95 :     if (!degpol(y)) return gdiv(x, gel(y,2)); /* constant */
     115                 :         95 :     return RgX_get_0(y);
     116                 :            :   }
     117                 :        255 :   return RgX_div(x,y);
     118                 :            : }
     119                 :            : GEN
     120                 :     382178 : grem(GEN x, GEN y)
     121                 :            : {
     122                 :     382178 :   const char *f = "euclidean division";
     123                 :     382178 :   long tx = typ(x), ty = typ(y), vx = gvar(x), vy = gvar(y);
     124                 :            : 
     125         [ +  + ]:     382178 :   if (ty == t_POL)
     126                 :            :   {
     127         [ +  - ]:     382138 :     if (varncmp(vx,vy) >= 0)
     128                 :            :     {
     129                 :            :       pari_sp av;
     130                 :            :       GEN z;
     131         [ -  + ]:     382138 :       if (!signe(y)) pari_err_INV("grem",y);
     132         [ +  + ]:     382138 :       if (vx != vy) return rem_scal_pol(x,y);
     133   [ +  +  +  +  :     340938 :       switch(tx)
                      - ]
     134                 :            :       {
     135                 :         20 :         case t_POLMOD: return polmod_mod(x,y);
     136                 :     340878 :         case t_POL: return RgX_rem(x,y);
     137                 :            :         case t_RFRAC:
     138                 :          5 :           av = avma; z = gmul(gel(x,1), RgXQ_inv(gel(x,2),y));
     139                 :          5 :           return gerepileupto(av, grem(z,y));
     140                 :            :         case t_SER:
     141         [ +  + ]:         35 :           if (RgX_is_monomial(y))
     142                 :            :           {
     143         [ +  + ]:         20 :             if (lg(x)-2 + valp(x) < degpol(y)) pari_err_OP("%",x,y);
     144                 :         15 :             av = avma;
     145                 :         15 :             return gerepileupto(av, gmod(ser2rfrac_i(x), y));
     146                 :            :           }
     147                 :         15 :         default: pari_err_TYPE2("%",x,y);
     148                 :            :       }
     149                 :            :     }
     150         [ #  # ]:          0 :     else switch(tx)
     151                 :            :     {
     152                 :            :       case t_POL:
     153                 :          0 :       case t_RFRAC: return rem_pol_scal(x,y);
     154                 :          0 :       default: pari_err_TYPE2("%",x,y);
     155                 :            :     }
     156                 :            :   }
     157 [ +  - ][ -  + ]:         40 :   if (!is_extscalar_t(tx) || !is_extscalar_t(ty)) pari_err_TYPE2(f,x,y);
     158 [ +  + ][ +  - ]:         40 :   if (vx == vy && ty==t_POLMOD) pari_err_TYPE2(f,x,y);
     159 [ +  - ][ -  + ]:         35 :   if (tx != t_POL || varncmp(vx,vy) > 0)
     160                 :            :   { /* x a "scalar" */
     161 [ #  # ][ #  # ]:          0 :     if (ty != t_POL || varncmp(vx, vy) < 0) return rem_scal_scal(x,y);
     162                 :          0 :     return rem_scal_pol(x,y);
     163                 :            :   }
     164 [ -  + ][ #  # ]:         35 :   if (ty != t_POL || varncmp(vx, vy) < 0) /* y a "scalar" */
     165                 :         35 :     return rem_pol_scal(x,y);
     166                 :     382153 :   return RgX_rem(x,y);
     167                 :            : }
     168                 :            : 
     169                 :            : /*******************************************************************/
     170                 :            : /*                                                                 */
     171                 :            : /*                  CONVERSIONS RELATED TO p-ADICS                 */
     172                 :            : /*                                                                 */
     173                 :            : /*******************************************************************/
     174                 :            : /* x t_PADIC, p a prime or NULL (unset). Consistency check */
     175                 :            : static void
     176                 :         60 : check_padic_p(GEN x, GEN p)
     177                 :            : {
     178                 :         60 :   GEN q = gel(x,2);
     179 [ +  + ][ +  + ]:         60 :   if (p && !equalii(p, q)) pari_err_MODULUS("Zp_to_Z", p,q);
     180                 :         45 : }
     181                 :            : /* shallow */
     182                 :            : static GEN
     183                 :        980 : Zp_to_Z(GEN x, GEN p) {
     184      [ +  +  - ]:        980 :   switch(typ(x))
     185                 :            :   {
     186                 :        940 :     case t_INT: break;
     187                 :            :     case t_PADIC:
     188                 :         40 :       check_padic_p(x, p);
     189                 :         25 :       x = gtrunc(x); break;
     190                 :          0 :     default: pari_err_TYPE("Zp_to_Z",x);
     191                 :            :   }
     192                 :        965 :   return x;
     193                 :            : }
     194                 :            : /* shallow */
     195                 :            : static GEN
     196                 :        205 : ZpX_to_ZX(GEN f, GEN p) {
     197                 :        205 :   long i, l = lg(f);
     198                 :        205 :   GEN F = cgetg_copy(f, &l); F[1] = f[1];
     199         [ +  + ]:       1125 :   for (i=2; i<l; i++) gel(F,i) = Zp_to_Z(gel(f,i), p);
     200                 :        195 :   return F;
     201                 :            : }
     202                 :            : 
     203                 :            : static GEN
     204                 :        210 : get_padic_content(GEN f, GEN p)
     205                 :            : {
     206                 :        210 :   GEN c = content(f);
     207         [ -  + ]:        210 :   if (gequal0(c)) /*  O(p^n) can occur */
     208                 :            :   {
     209         [ #  # ]:          0 :     if (typ(c) != t_PADIC) pari_err_TYPE("QpX_to_ZX",f);
     210                 :          0 :     check_padic_p(c, p);
     211                 :          0 :     c = powis(p, valp(c));
     212                 :            :   }
     213                 :        210 :   return c;
     214                 :            : }
     215                 :            : /* make f suitable for [root|factor]padic. Shallow */
     216                 :            : static GEN
     217                 :        190 : QpX_to_ZX(GEN f, GEN p)
     218                 :            : {
     219                 :        190 :   GEN c = get_padic_content(f, p);
     220                 :        190 :   f = RgX_Rg_div(f, c);
     221                 :        190 :   return ZpX_to_ZX(f, p);
     222                 :            : }
     223                 :            : 
     224                 :            : /* x in Z return x + O(pr), pr = p^r. Shallow */
     225                 :            : static GEN
     226                 :        945 : Z_to_Zp(GEN x, GEN p, GEN pr, long r)
     227                 :            : {
     228                 :            :   GEN y;
     229                 :        945 :   long v, sx = signe(x);
     230                 :            : 
     231         [ +  + ]:        945 :   if (!sx) return zeropadic_shallow(p,r);
     232                 :        775 :   v = Z_pvalrem(x,p,&x);
     233         [ +  + ]:        775 :   if (v) {
     234         [ +  + ]:        220 :     if (r <= v) return zeropadic_shallow(p,r);
     235                 :        195 :     r -= v;
     236                 :        195 :     pr = powiu(p,r);
     237                 :            :   }
     238                 :        750 :   y = cgetg(5,t_PADIC);
     239                 :        750 :   y[1] = evalprecp(r)|evalvalp(v);
     240                 :        750 :   gel(y,2) = p;
     241                 :        750 :   gel(y,3) = pr;
     242                 :        945 :   gel(y,4) = modii(x,pr); return y;
     243                 :            : }
     244                 :            : /* shallow */
     245                 :            : static GEN
     246                 :         35 : ZV_to_ZpV(GEN z, GEN p, long r)
     247                 :            : {
     248                 :         35 :   long i, l = lg(z);
     249                 :         35 :   GEN Z = cgetg(l, typ(z)), q = powiu(p, r);
     250         [ +  + ]:        115 :   for (i=1; i<lg(z); i++) gel(Z,i) = Z_to_Zp(gel(z,i),p,q,r);
     251                 :         35 :   return Z;
     252                 :            : }
     253                 :            : /* shallow */
     254                 :            : static GEN
     255                 :        260 : ZX_to_ZpX(GEN z, GEN p, GEN q, long r)
     256                 :            : {
     257                 :        260 :   long i, l = lg(z);
     258                 :        260 :   GEN Z = cgetg(l, t_POL); Z[1] = z[1];
     259         [ +  + ]:       1065 :   for (i=2; i<lg(z); i++) gel(Z,i) = Z_to_Zp(gel(z,i),p,q,r);
     260                 :        260 :   return Z;
     261                 :            : }
     262                 :            : /* return (x + O(p^r)) normalized (multiply by a unit such that leading coeff
     263                 :            :  * is a power of p), x in Z[X] (or Z_p[X]). Shallow */
     264                 :            : static GEN
     265                 :        260 : ZX_to_ZpX_normalized(GEN x, GEN p, GEN pr, long r)
     266                 :            : {
     267                 :        260 :   long i, lx = lg(x);
     268                 :        260 :   GEN z, lead = leading_term(x);
     269                 :            : 
     270         [ +  + ]:        260 :   if (gequal1(lead)) return ZX_to_ZpX(x, p, pr, r);
     271                 :         20 :   (void)Z_pvalrem(lead, p, &lead); lead = Fp_inv(lead, pr);
     272                 :         20 :   z = cgetg(lx,t_POL);
     273         [ +  + ]:         80 :   for (i=2; i < lx; i++) gel(z,i) = Z_to_Zp(mulii(lead,gel(x,i)),p,pr,r);
     274                 :        260 :   z[1] = x[1]; return z;
     275                 :            : }
     276                 :            : static GEN
     277                 :         15 : ZXV_to_ZpXQV(GEN z, GEN T, GEN p, long r)
     278                 :            : {
     279                 :         15 :   long i, l = lg(z);
     280                 :         15 :   GEN Z = cgetg(l, typ(z)), q = powiu(p, r);
     281                 :         15 :   T = ZX_copy(T);
     282         [ +  + ]:         35 :   for (i=1; i<lg(z); i++) gel(Z,i) = mkpolmod(ZX_to_ZpX(gel(z,i),p,q,r),T);
     283                 :         15 :   return Z;
     284                 :            : }
     285                 :            : /* shallow */
     286                 :            : static GEN
     287                 :         20 : QpXQX_to_ZXY(GEN f, GEN p)
     288                 :            : {
     289                 :         20 :   GEN c = get_padic_content(f, p);
     290                 :         20 :   long i, l = lg(f);
     291                 :         20 :   f = RgX_Rg_div(f,c);
     292         [ +  + ]:         80 :   for (i=2; i<l; i++)
     293                 :            :   {
     294                 :         65 :     GEN t = gel(f,i);
     295      [ +  -  + ]:         65 :     switch(typ(t))
     296                 :            :     {
     297                 :            :       case t_POLMOD:
     298                 :         15 :         t = gel(t,2);
     299         [ +  - ]:         15 :         t = (typ(t) == t_POL)? ZpX_to_ZX(t, p): Zp_to_Z(t, p);
     300                 :         15 :         break;
     301                 :          0 :       case t_POL: t = ZpX_to_ZX(t, p); break;
     302                 :         50 :       default: t = Zp_to_Z(t, p); break;
     303                 :            :     }
     304                 :         60 :     gel(f,i) = t;
     305                 :            :   }
     306                 :         15 :   return f;
     307                 :            : }
     308                 :            : 
     309                 :            : /*******************************************************************/
     310                 :            : /*                                                                 */
     311                 :            : /*                         p-ADIC ROOTS                            */
     312                 :            : /*                                                                 */
     313                 :            : /*******************************************************************/
     314                 :            : 
     315                 :            : /* f primitive ZX, squarefree, leading term prime to p; a in Z such that
     316                 :            :  * f(a) = 0 mod p. Return p-adic roots of f equal to a mod p, in
     317                 :            :  * precision >= prec */
     318                 :            : GEN
     319                 :        245 : ZX_Zp_root(GEN f, GEN a, GEN p, long prec)
     320                 :            : {
     321                 :        245 :   GEN z, R, a0 = modii(a, p);
     322                 :            :   long i, j, k, v;
     323                 :            : 
     324         [ +  + ]:        245 :   if (signe(FpX_eval(FpX_deriv(f, p), a0, p)))
     325                 :            :   { /* simple zero mod p, go all the way to p^prec */
     326         [ +  + ]:        140 :     if (prec > 1) a0 = ZpX_liftroot(f, a0, p, prec);
     327                 :        140 :     return mkcol(a0);
     328                 :            :   }
     329                 :            : 
     330                 :        105 :   f = ZX_unscale_div(RgX_translate(f,a), p); /* f(pX + a) / p */
     331                 :        105 :   v = ZX_pval(f,p);
     332         [ +  + ]:        105 :   if (v) f = ZX_Z_divexact(f, powiu(p,v));
     333                 :        105 :   z = cgetg(degpol(f)+1,t_COL);
     334                 :            : 
     335                 :        105 :   R = FpX_roots(f, p);
     336         [ +  + ]:        235 :   for (j=i=1; i<lg(R); i++)
     337                 :            :   {
     338                 :        130 :     GEN u = ZX_Zp_root(f, gel(R,i), p, prec-1);
     339         [ +  + ]:        240 :     for (k=1; k<lg(u); k++) gel(z,j++) = addii(a, mulii(p, gel(u,k)));
     340                 :            :   }
     341                 :        245 :   setlg(z,j); return z;
     342                 :            : }
     343                 :            : 
     344                 :            : /* a t_PADIC, return vector of p-adic roots of f equal to a (mod p)
     345                 :            :  * We assume 1) f(a) = 0 mod p,
     346                 :            :  *           2) leading coeff prime to p. */
     347                 :            : GEN
     348                 :         25 : Zp_appr(GEN f, GEN a)
     349                 :            : {
     350                 :         25 :   pari_sp av = avma;
     351                 :            :   long prec;
     352                 :            :   GEN z, p;
     353         [ +  + ]:         25 :   p = gel(a,2); prec = gequal0(a)? valp(a): precp(a);
     354                 :         25 :   f = QpX_to_ZX(f, p);
     355         [ -  + ]:         15 :   if (degpol(f) <= 0) pari_err_CONSTPOL("Zp_appr");
     356                 :         15 :   (void)ZX_gcd_all(f, ZX_deriv(f), &f);
     357                 :         15 :   z = ZX_Zp_root(f, gtrunc(a), p, prec);
     358                 :         15 :   return gerepilecopy(av, ZV_to_ZpV(z, p, prec));
     359                 :            : }
     360                 :            : /* vector of p-adic roots of the ZX f, leading term prime to p. Shallow */
     361                 :            : static GEN
     362                 :         20 : ZX_Zp_roots(GEN f, GEN p, long prec)
     363                 :            : {
     364                 :            :   GEN y, z, rac;
     365                 :            :   long lx, i, j, k;
     366                 :            : 
     367                 :         20 :   (void)ZX_gcd_all(f, ZX_deriv(f), &f);
     368                 :         20 :   rac = FpX_roots(f, p);
     369         [ -  + ]:         20 :   lx = lg(rac); if (lx == 1) return rac;
     370                 :         20 :   y = cgetg(degpol(f)+1,t_COL);
     371         [ +  + ]:         80 :   for (j=i=1; i<lx; i++)
     372                 :            :   {
     373                 :         60 :     z = ZX_Zp_root(f, gel(rac,i), p, prec);
     374         [ +  + ]:        125 :     for (k=1; k<lg(z); k++,j++) gel(y,j) = gel(z,k);
     375                 :            :   }
     376                 :         20 :   setlg(y,j); return ZV_to_ZpV(y, p, prec);
     377                 :            : }
     378                 :            : 
     379                 :            : /* f a ZX */
     380                 :            : static GEN
     381                 :        135 : pnormalize(GEN f, GEN p, long prec, long n, GEN *plead, long *pprec, int *prev)
     382                 :            : {
     383                 :        135 :   *plead = leading_term(f);
     384                 :        135 :   *pprec = prec;
     385                 :        135 :   *prev = 0;
     386         [ +  + ]:        135 :   if (!is_pm1(*plead))
     387                 :            :   {
     388                 :         15 :     long v = Z_pval(*plead,p), v1 = Z_pval(constant_term(f),p);
     389         [ +  - ]:         15 :     if (v1 < v)
     390                 :            :     {
     391                 :         15 :       *prev = 1; f = RgX_recip_shallow(f);
     392                 :            :      /* beware loss of precision from lc(factor), whose valuation is <= v */
     393                 :         15 :       *pprec += v; v = v1;
     394                 :            :     }
     395                 :         15 :     *pprec += v * n;
     396                 :            :   }
     397                 :        135 :   return ZX_Q_normalize(f, plead);
     398                 :            : }
     399                 :            : 
     400                 :            : /* return p-adic roots of f, precision prec */
     401                 :            : GEN
     402                 :         25 : rootpadic(GEN f, GEN p, long prec)
     403                 :            : {
     404                 :         25 :   pari_sp av = avma;
     405                 :            :   GEN lead,y;
     406                 :            :   long PREC,i,k;
     407                 :            :   int reverse;
     408                 :            : 
     409         [ -  + ]:         25 :   if (typ(p)!=t_INT) pari_err_TYPE("rootpadic",p);
     410         [ -  + ]:         25 :   if (typ(f)!=t_POL) pari_err_TYPE("rootpadic",f);
     411         [ -  + ]:         25 :   if (gequal0(f)) pari_err_ROOTS0("rootpadic");
     412         [ +  + ]:         25 :   if (prec <= 0)
     413                 :          5 :     pari_err_DOMAIN("rootpadic", "precision", "<=",gen_0,stoi(prec));
     414                 :         20 :   f = QpX_to_ZX(f, p);
     415                 :         20 :   f = pnormalize(f, p, prec, 1, &lead, &PREC, &reverse);
     416                 :         20 :   y = ZX_Zp_roots(f,p,PREC);
     417                 :         20 :   k = lg(y);
     418         [ +  - ]:         20 :   if (lead != gen_1)
     419         [ +  + ]:         85 :     for (i=1; i<k; i++) gel(y,i) = gdiv(gel(y,i), lead);
     420         [ -  + ]:         20 :   if (reverse)
     421         [ #  # ]:          0 :     for (i=1; i<k; i++) gel(y,i) = ginv(gel(y,i));
     422                 :         20 :   return gerepilecopy(av, y);
     423                 :            : }
     424                 :            : 
     425                 :            : /**************************************************************************/
     426                 :            : 
     427                 :            : static void
     428                 :         95 : scalar_getprec(GEN x, long *pprec, GEN *pp)
     429                 :            : {
     430         [ +  + ]:         95 :   if (typ(x)==t_PADIC)
     431                 :            :   {
     432         [ +  - ]:         20 :     long e = valp(x); if (signe(gel(x,4))) e += precp(x);
     433         [ +  - ]:         20 :     if (e < *pprec) *pprec = e;
     434                 :         20 :     check_padic_p(x, *pp);
     435                 :         20 :     *pp = gel(x,2);
     436                 :            :   }
     437                 :         95 : }
     438                 :            : static void
     439                 :         40 : getprec(GEN x, long *pprec, GEN *pp)
     440                 :            : {
     441                 :            :   long i;
     442         [ +  + ]:         40 :   if (typ(x) != t_POL) scalar_getprec(x, pprec, pp);
     443                 :            :   else
     444         [ +  + ]:        125 :     for (i = lg(x)-1; i>1; i--) scalar_getprec(gel(x,i), pprec, pp);
     445                 :         40 : }
     446                 :            : 
     447                 :            : static GEN
     448                 :         25 : ZXY_ZpQ_root(GEN f, GEN a, GEN T, GEN p, long prec)
     449                 :            : {
     450                 :            :   GEN z, R;
     451                 :            :   long i, j, k, lR;
     452         [ +  + ]:         25 :   if (signe(FqX_eval(FqX_deriv(f,T,p), a, T,p)))
     453                 :            :   { /* simple zero mod (T,p), go all the way to p^prec */
     454         [ +  - ]:         20 :     if (prec > 1) a = ZpXQX_liftroot(f, a, T, p, prec);
     455                 :         20 :     return mkcol(a);
     456                 :            :   }
     457                 :          5 :   f = RgX_unscale(RgXQX_translate(f, a, T), p);
     458                 :          5 :   f = RgX_Rg_div(f, powiu(p, gvaluation(f,p)));
     459                 :          5 :   z = cgetg(degpol(f)+1,t_COL);
     460                 :          5 :   R = FqX_roots(FqX_red(f,T,p), T, p); lR = lg(R);
     461         [ +  + ]:         15 :   for(j=i=1; i<lR; i++)
     462                 :            :   {
     463                 :         10 :     GEN u = ZXY_ZpQ_root(f, gel(R,i), T, p, prec-1);
     464         [ +  + ]:         20 :     for (k=1; k<lg(u); k++) gel(z,j++) = gadd(a, gmul(p, gel(u,k)));
     465                 :            :   }
     466                 :         25 :   setlg(z,j); return z;
     467                 :            : }
     468                 :            : 
     469                 :            : /* a belongs to finite extension of Q_p, return all roots of f equal to a
     470                 :            :  * mod p. We assume f(a) = 0 (mod p) [mod 4 if p=2] */
     471                 :            : GEN
     472                 :         45 : padicappr(GEN f, GEN a)
     473                 :            : {
     474                 :            :   GEN p, z, T;
     475                 :            :   long prec;
     476                 :         45 :   pari_sp av = avma;
     477                 :            : 
     478         [ -  + ]:         45 :   if (typ(f)!=t_POL) pari_err_TYPE("padicappr",f);
     479      [ +  +  - ]:         45 :   switch(typ(a)) {
     480                 :         25 :     case t_PADIC: return Zp_appr(f,a);
     481                 :         20 :     case t_POLMOD: break;
     482                 :          0 :     default: pari_err_TYPE("padicappr",a);
     483                 :            :   }
     484         [ -  + ]:         20 :   if (gequal0(f)) pari_err_ROOTS0("padicappr");
     485                 :         20 :   z = RgX_gcd(f, RgX_deriv(f));
     486         [ -  + ]:         20 :   if (degpol(z) > 0) f = RgX_div(f,z);
     487                 :         20 :   T = gel(a,1); a = gel(a,2);
     488                 :         20 :   p = NULL; prec = LONG_MAX;
     489                 :         20 :   getprec(a, &prec, &p);
     490         [ -  + ]:         20 :   getprec(T, &prec, &p); if (!p) pari_err_TYPE("padicappr",T);
     491                 :         20 :   f = QpXQX_to_ZXY(f, p);
     492                 :         15 :   a = QpX_to_ZX(a,p);
     493                 :         15 :   T = QpX_to_ZX(T,p);
     494                 :         15 :   z = ZXY_ZpQ_root(f, a, T, p, prec);
     495                 :         30 :   return gerepilecopy(av, ZXV_to_ZpXQV(z, T, p, prec));
     496                 :            : }
     497                 :            : 
     498                 :            : /*******************************************************************/
     499                 :            : /*                                                                 */
     500                 :            : /*             FACTORIZATION in Zp[X], using ROUND4                */
     501                 :            : /*                                                                 */
     502                 :            : /*******************************************************************/
     503                 :            : 
     504                 :            : int
     505                 :        105 : cmp_padic(GEN x, GEN y)
     506                 :            : {
     507                 :            :   long vx, vy;
     508         [ -  + ]:        105 :   if (x == gen_0) return -1;
     509         [ -  + ]:        105 :   if (y == gen_0) return  1;
     510                 :        105 :   vx = valp(x);
     511                 :        105 :   vy = valp(y);
     512         [ -  + ]:        105 :   if (vx < vy) return  1;
     513         [ +  + ]:        105 :   if (vx > vy) return -1;
     514                 :        105 :   return cmpii(gel(x,4), gel(y,4));
     515                 :            : }
     516                 :            : 
     517                 :            : static int
     518                 :        330 : expo_is_squarefree(GEN e)
     519                 :            : {
     520                 :        330 :   long i, l = lg(e);
     521         [ +  + ]:        400 :   for (i=1; i<l; i++)
     522         [ +  + ]:        350 :     if (e[i] != 1) return 0;
     523                 :        330 :   return 1;
     524                 :            : }
     525                 :            : 
     526                 :            : /* assume f a ZX with leading_term 1, degree > 0 */
     527                 :            : GEN
     528                 :        335 : ZX_monic_factorpadic(GEN f, GEN p, long prec)
     529                 :            : {
     530                 :            :   GEN w, poly, p1, p2, ex, P, E;
     531                 :        335 :   long n=degpol(f), i, k, j;
     532                 :            : 
     533         [ +  + ]:        335 :   if (n==1) return mkmat2(mkcol(f), mkcol(gen_1));
     534                 :            : 
     535                 :        315 :   poly = ZX_squff(f,&ex);
     536                 :        315 :   P = cgetg(n+1,t_COL);
     537                 :        315 :   E = cgetg(n+1,t_COL); n = lg(poly);
     538         [ +  + ]:        645 :   for (j=i=1; i<n; i++)
     539                 :            :   {
     540                 :        330 :     pari_sp av1 = avma;
     541                 :        330 :     GEN fx = gel(poly,i), fa = FpX_factor(fx,p);
     542                 :        330 :     w = gel(fa,1);
     543         [ +  + ]:        330 :     if (expo_is_squarefree(gel(fa,2)))
     544                 :            :     { /* no repeated factors: Hensel lift */
     545                 :         50 :       p1 = ZpX_liftfact(fx, w, NULL, p, prec, powiu(p,prec));
     546                 :         50 :       p2 = utoipos(ex[i]);
     547         [ +  + ]:        120 :       for (k=1; k<lg(p1); k++,j++)
     548                 :            :       {
     549                 :         70 :         gel(P,j) = gel(p1,k);
     550                 :         70 :         gel(E,j) = p2;
     551                 :            :       }
     552                 :         50 :       continue;
     553                 :            :     }
     554                 :            :     /* use Round 4 */
     555                 :        280 :     p2 = maxord_i(p, fx, ZpX_disc_val(fx,p), w, prec);
     556         [ +  + ]:        280 :     if (p2)
     557                 :            :     {
     558                 :        110 :       p2 = gerepilecopy(av1,p2);
     559                 :        110 :       p1 = gel(p2,1);
     560                 :        110 :       p2 = gel(p2,2);
     561         [ +  + ]:        355 :       for (k=1; k<lg(p1); k++,j++)
     562                 :            :       {
     563                 :        245 :         gel(P,j) = gel(p1,k);
     564                 :        245 :         gel(E,j) = muliu(gel(p2,k),ex[i]);
     565                 :            :       }
     566                 :            :     }
     567                 :            :     else
     568                 :            :     {
     569                 :        170 :       avma = av1;
     570                 :        170 :       gel(P,j) = fx;
     571                 :        170 :       gel(E,j) = utoipos(ex[i]); j++;
     572                 :            :     }
     573                 :            :   }
     574                 :        315 :   setlg(P,j);
     575                 :        335 :   setlg(E,j); return mkmat2(P, E);
     576                 :            : }
     577                 :            : 
     578                 :            : GEN
     579                 :        120 : factorpadic(GEN f,GEN p,long r)
     580                 :            : {
     581                 :        120 :   pari_sp av = avma;
     582                 :            :   GEN y, P, ppow, lead, lt;
     583                 :        120 :   long i, l, pr, n = degpol(f);
     584                 :        120 :   int reverse = 0;
     585                 :            : 
     586         [ -  + ]:        120 :   if (typ(f)!=t_POL) pari_err_TYPE("factorpadic",f);
     587         [ -  + ]:        120 :   if (typ(p)!=t_INT) pari_err_TYPE("factorpadic",p);
     588         [ +  + ]:        120 :   if (r <= 0) pari_err_DOMAIN("factorpadic", "precision", "<=",gen_0,stoi(r));
     589         [ -  + ]:        115 :   if (!signe(f)) return prime_fact(f);
     590         [ -  + ]:        115 :   if (n == 0) return trivial_fact();
     591                 :            : 
     592                 :        115 :   f = QpX_to_ZX(f, p); (void)Z_pvalrem(leading_term(f), p, &lt);
     593                 :        115 :   f = pnormalize(f, p, r, n-1, &lead, &pr, &reverse);
     594                 :        115 :   y = ZX_monic_factorpadic(f, p, pr);
     595                 :        115 :   P = gel(y,1); l = lg(P);
     596         [ +  - ]:        115 :   if (lead != gen_1)
     597         [ +  + ]:        375 :     for (i=1; i<l; i++) gel(P,i) = Q_primpart( RgX_unscale(gel(P,i), lead) );
     598                 :        115 :   ppow = powiu(p,r);
     599         [ +  + ]:        375 :   for (i=1; i<l; i++)
     600                 :            :   {
     601                 :        260 :     GEN t = gel(P,i);
     602         [ +  + ]:        260 :     if (reverse) t = normalizepol(RgX_recip_shallow(t));
     603                 :        260 :     gel(P,i) = ZX_to_ZpX_normalized(t,p,ppow,r);
     604                 :            :   }
     605         [ -  + ]:        115 :   if (!gequal1(lt)) gel(P,1) = gmul(gel(P,1), lt);
     606                 :        115 :   return gerepilecopy(av, sort_factor_pol(y, cmp_padic));
     607                 :            : }

Generated by: LCOV version 1.9