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 - ZV.c (source / functions) Hit Total Coverage
Test: PARI/GP v2.8.0 lcov report (development 16375-9f41ae0) Lines: 543 585 92.8 %
Date: 2014-04-19 Functions: 88 94 93.6 %
Legend: Lines: hit not hit | Branches: + taken - not taken # not executed Branches: 360 422 85.3 %

           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                 :            : #include "pari.h"
      15                 :            : #include "paripriv.h"
      16                 :            : 
      17                 :            : static int
      18                 :       8629 : check_ZV(GEN x, long l)
      19                 :            : {
      20                 :            :   long i;
      21         [ +  + ]:      32719 :   for (i=1; i<l; i++)
      22         [ +  + ]:      24174 :     if (typ(gel(x,i)) != t_INT) return 0;
      23                 :       8629 :   return 1;
      24                 :            : }
      25                 :            : void
      26                 :     452273 : RgV_check_ZV(GEN A, const char *s)
      27                 :            : {
      28         [ +  + ]:     452273 :   if (!RgV_is_ZV(A)) pari_err_TYPE(stack_strcat(s," [integer vector]"), A);
      29                 :     452259 : }
      30                 :            : void
      31                 :       4514 : RgM_check_ZM(GEN A, const char *s)
      32                 :            : {
      33                 :       4514 :   long n = lg(A);
      34         [ +  + ]:       4514 :   if (n != 1)
      35                 :            :   {
      36                 :       4479 :     long j, m = lgcols(A);
      37         [ +  + ]:      13024 :     for (j=1; j<n; j++)
      38         [ +  + ]:       8629 :       if (!check_ZV(gel(A,j), m))
      39                 :         84 :         pari_err_TYPE(stack_strcat(s," [integer matrix]"), A);
      40                 :            :   }
      41                 :       4430 : }
      42                 :            : 
      43                 :            : long
      44                 :      10598 : ZV_max_lg(GEN x)
      45                 :            : {
      46                 :      10598 :   long i, prec = 2, m = lg(x);
      47 [ +  + ][ +  + ]:      30044 :   for (i=1; i<m; i++) { long l = lgefint(gel(x,i)); if (l > prec) prec = l; }
      48                 :      10598 :   return prec;
      49                 :            : }
      50                 :            : long
      51                 :        567 : ZM_max_lg(GEN x)
      52                 :            : {
      53                 :        567 :   long i, prec = 2, n = lg(x);
      54         [ +  - ]:        567 :   if (n != 1)
      55                 :            :   {
      56                 :        567 :     long j, m = lgcols(x);
      57         [ +  + ]:       5943 :     for (j=1; j<n; j++)
      58                 :            :     {
      59                 :       5376 :       GEN c = gel(x,j);
      60 [ +  + ][ +  + ]:     118650 :       for (i=1; i<m; i++) { long l = lgefint(gel(c,i)); if (l > prec) prec = l; }
      61                 :            :     }
      62                 :            :   }
      63                 :        567 :   return prec;
      64                 :            : }
      65                 :            : 
      66                 :            : GEN
      67                 :         56 : ZM_supnorm(GEN x)
      68                 :            : {
      69                 :         56 :   long i, j, h, lx = lg(x);
      70                 :         56 :   GEN s = gen_0;
      71         [ -  + ]:         56 :   if (lx == 1) return gen_1;
      72                 :         56 :   h = lgcols(x);
      73         [ +  + ]:        329 :   for (j=1; j<lx; j++)
      74                 :            :   {
      75                 :        273 :     GEN xj = gel(x,j);
      76         [ +  + ]:       2814 :     for (i=1; i<h; i++)
      77                 :            :     {
      78                 :       2541 :       GEN c = gel(xj,i);
      79         [ +  + ]:       2541 :       if (absi_cmp(c, s) > 0) s = c;
      80                 :            :     }
      81                 :            :   }
      82                 :         56 :   return absi(s);
      83                 :            : }
      84                 :            : 
      85                 :            : /********************************************************************/
      86                 :            : /**                                                                **/
      87                 :            : /**                           MULTIPLICATION                       **/
      88                 :            : /**                                                                **/
      89                 :            : /********************************************************************/
      90                 :            : /* x non-empty ZM, y a compatible nc (dimension > 0). */
      91                 :            : static GEN
      92                 :       2786 : ZM_nc_mul_i(GEN x, GEN y, long c, long l)
      93                 :            : {
      94                 :            :   long i, j;
      95                 :            :   pari_sp av;
      96                 :       2786 :   GEN z = cgetg(l,t_COL), s;
      97                 :            : 
      98         [ +  + ]:      44039 :   for (i=1; i<l; i++)
      99                 :            :   {
     100                 :      41253 :     av = avma; s = muliu(gcoeff(x,i,1),y[1]);
     101         [ +  + ]:     691117 :     for (j=2; j<c; j++)
     102         [ +  + ]:     649864 :       if (y[j]) s = addii(s, muliu(gcoeff(x,i,j),y[j]));
     103                 :      41253 :     gel(z,i) = gerepileuptoint(av,s);
     104                 :            :   }
     105                 :       2786 :   return z;
     106                 :            : }
     107                 :            : /* x non-empty ZM, y a compatible zc (dimension > 0). */
     108                 :            : static GEN
     109                 :    2150117 : ZM_zc_mul_i(GEN x, GEN y, long c, long l)
     110                 :            : {
     111                 :            :   long i, j;
     112                 :            :   pari_sp av;
     113                 :    2150117 :   GEN z = cgetg(l,t_COL), s;
     114                 :            : 
     115         [ +  + ]:   18775850 :   for (i=1; i<l; i++)
     116                 :            :   {
     117                 :   16625733 :     av = avma; s = mulis(gcoeff(x,i,1),y[1]);
     118         [ +  + ]:  287166209 :     for (j=2; j<c; j++)
     119         [ +  + ]:  270540476 :       if (y[j]) s = addii(s, mulis(gcoeff(x,i,j),y[j]));
     120                 :   16625733 :     gel(z,i) = gerepileuptoint(av,s);
     121                 :            :   }
     122                 :    2150117 :   return z;
     123                 :            : }
     124                 :            : GEN
     125                 :    2107423 : ZM_zc_mul(GEN x, GEN y) {
     126                 :    2107423 :   long l = lg(x);
     127         [ -  + ]:    2107423 :   if (l == 1) return cgetg(1, t_COL);
     128                 :    2107423 :   return ZM_zc_mul_i(x,y, l, lgcols(x));
     129                 :            : }
     130                 :            : 
     131                 :            : /* x ZM, y a compatible zm (dimension > 0). */
     132                 :            : GEN
     133                 :       9575 : ZM_zm_mul(GEN x, GEN y)
     134                 :            : {
     135                 :       9575 :   long j, c, l = lg(x), ly = lg(y);
     136                 :       9575 :   GEN z = cgetg(ly, t_MAT);
     137         [ -  + ]:       9575 :   if (l == 1) return z;
     138                 :       9575 :   c = lgcols(x);
     139         [ +  + ]:      52269 :   for (j = 1; j < ly; j++) gel(z,j) = ZM_zc_mul_i(x, gel(y,j), l,c);
     140                 :       9575 :   return z;
     141                 :            : }
     142                 :            : /* x ZM, y a compatible zn (dimension > 0). */
     143                 :            : GEN
     144                 :        188 : ZM_nm_mul(GEN x, GEN y)
     145                 :            : {
     146                 :        188 :   long j, c, l = lg(x), ly = lg(y);
     147                 :        188 :   GEN z = cgetg(ly, t_MAT);
     148         [ -  + ]:        188 :   if (l == 1) return z;
     149                 :        188 :   c = lgcols(x);
     150         [ +  + ]:       2974 :   for (j = 1; j < ly; j++) gel(z,j) = ZM_nc_mul_i(x, gel(y,j), l,c);
     151                 :        188 :   return z;
     152                 :            : }
     153                 :            : 
     154                 :            : /* x[i,]*y. Assume lg(x) > 1 and 0 < i < lgcols(x) */
     155                 :            : static GEN
     156                 :   94141169 : ZMrow_ZC_mul_i(GEN x, GEN y, long i, long lx)
     157                 :            : {
     158                 :   94141169 :   pari_sp av = avma;
     159                 :   94141169 :   GEN c = mulii(gcoeff(x,i,1), gel(y,1)), ZERO = gen_0;
     160                 :            :   long k;
     161         [ +  + ]:  967812946 :   for (k = 2; k < lx; k++)
     162                 :            :   {
     163                 :  873671777 :     GEN t = mulii(gcoeff(x,i,k), gel(y,k));
     164         [ +  + ]:  873671777 :     if (t != ZERO) c = addii(c, t);
     165                 :            :   }
     166                 :   94141169 :   return gerepileuptoint(av, c);
     167                 :            : }
     168                 :            : GEN
     169                 :   50935112 : ZMrow_ZC_mul(GEN x, GEN y, long i)
     170                 :   50935112 : { return ZMrow_ZC_mul_i(x, y, i, lg(x)); }
     171                 :            : 
     172                 :            : /* return x * y, 1 < lx = lg(x), l = lgcols(x) */
     173                 :            : static GEN
     174                 :    9163998 : ZM_ZC_mul_i(GEN x, GEN y, long lx, long l)
     175                 :            : {
     176                 :    9163998 :   GEN z = cgetg(l,t_COL);
     177                 :            :   long i;
     178         [ +  + ]:   52370055 :   for (i=1; i<l; i++) gel(z,i) = ZMrow_ZC_mul_i(x,y,i,lx);
     179                 :    9163998 :   return z;
     180                 :            : }
     181                 :            : GEN
     182                 :    1293296 : ZM_mul(GEN x, GEN y)
     183                 :            : {
     184                 :    1293296 :   long j, l, lx=lg(x), ly=lg(y);
     185                 :            :   GEN z;
     186         [ +  + ]:    1293296 :   if (ly==1) return cgetg(1,t_MAT);
     187         [ +  + ]:    1291847 :   if (lx==1) return zeromat(0, ly-1);
     188                 :    1291714 :   l = lgcols(x); z = cgetg(ly,t_MAT);
     189         [ +  + ]:    6132639 :   for (j=1; j<ly; j++) gel(z,j) = ZM_ZC_mul_i(x, gel(y,j), lx, l);
     190                 :    1293296 :   return z;
     191                 :            : }
     192                 :            : /* assume result is symmetric */
     193                 :            : GEN
     194                 :          0 : ZM_multosym(GEN x, GEN y)
     195                 :            : {
     196                 :          0 :   long j, lx, ly = lg(y);
     197                 :            :   GEN M;
     198         [ #  # ]:          0 :   if (ly == 1) return cgetg(1,t_MAT);
     199                 :          0 :   lx = lg(x); /* = lgcols(y) */
     200         [ #  # ]:          0 :   if (lx == 1) return cgetg(1,t_MAT);
     201                 :            :   /* ly = lgcols(x) */
     202                 :          0 :   M = cgetg(ly, t_MAT);
     203         [ #  # ]:          0 :   for (j=1; j<ly; j++)
     204                 :            :   {
     205                 :          0 :     GEN z = cgetg(ly,t_COL), yj = gel(y,j);
     206                 :            :     long i;
     207         [ #  # ]:          0 :     for (i=1; i<j; i++) gel(z,i) = gcoeff(M,j,i);
     208         [ #  # ]:          0 :     for (i=j; i<ly; i++)gel(z,i) = ZMrow_ZC_mul_i(x,yj,i,lx);
     209                 :          0 :     gel(M,j) = z;
     210                 :            :   }
     211                 :          0 :   return M;
     212                 :            : }
     213                 :            : 
     214                 :            : /* assume lx > 1 is lg(x) = lg(y) */
     215                 :            : static GEN
     216                 :    8479243 : ZV_dotproduct_i(GEN x, GEN y, long lx)
     217                 :            : {
     218                 :    8479243 :   pari_sp av = avma;
     219                 :    8479243 :   GEN c = mulii(gel(x,1), gel(y,1));
     220                 :            :   long i;
     221         [ +  + ]:   59861789 :   for (i = 2; i < lx; i++)
     222                 :            :   {
     223                 :   51382546 :     GEN t = mulii(gel(x,i), gel(y,i));
     224         [ +  + ]:   51382546 :     if (t != gen_0) c = addii(c, t);
     225                 :            :   }
     226                 :    8479243 :   return gerepileuptoint(av, c);
     227                 :            : }
     228                 :            : 
     229                 :            : /* x~ * y, assuming result is symmetric */
     230                 :            : GEN
     231                 :       2974 : ZM_transmultosym(GEN x, GEN y)
     232                 :            : {
     233                 :       2974 :   long i, j, l, ly = lg(y);
     234                 :            :   GEN M;
     235         [ -  + ]:       2974 :   if (ly == 1) return cgetg(1,t_MAT);
     236                 :            :   /* lg(x) = ly */
     237                 :       2974 :   l = lgcols(y); /* = lgcols(x) */
     238                 :       2974 :   M = cgetg(ly, t_MAT);
     239         [ +  + ]:      35074 :   for (i=1; i<ly; i++)
     240                 :            :   {
     241                 :      32100 :     GEN xi = gel(x,i), c = cgetg(ly,t_COL);
     242                 :      32100 :     gel(M,i) = c;
     243         [ +  + ]:     309852 :     for (j=1; j<i; j++)
     244                 :     277752 :       gcoeff(M,i,j) = gel(c,j) = ZV_dotproduct_i(xi,gel(y,j),l);
     245                 :      32100 :     gel(c,i) = ZV_dotproduct_i(xi,gel(y,i),l);
     246                 :            :   }
     247                 :       2974 :   return M;
     248                 :            : }
     249                 :            : GEN
     250                 :    4357635 : ZM_ZC_mul(GEN x, GEN y)
     251                 :            : {
     252                 :    4357635 :   long lx = lg(x);
     253         [ +  + ]:    4357635 :   return lx==1? cgetg(1,t_COL): ZM_ZC_mul_i(x, y, lx, lgcols(x));
     254                 :            : }
     255                 :            : 
     256                 :            : long
     257                 :  123005518 : zv_dotproduct(GEN x, GEN y)
     258                 :            : {
     259                 :  123005518 :   long i, lx = lg(x);
     260                 :            :   ulong c;
     261         [ -  + ]:  123005518 :   if (lx == 1) return 0;
     262                 :  123005518 :   c = uel(x,1)*uel(y,1);
     263         [ +  + ]: 1907407331 :   for (i = 2; i < lx; i++)
     264                 : 1784401813 :     c += uel(x,i)*uel(y,i);
     265                 :  123005518 :   return c;
     266                 :            : }
     267                 :            : 
     268                 :            : GEN
     269                 :        903 : ZV_ZM_mul(GEN x, GEN y)
     270                 :            : {
     271                 :        903 :   long i, lx = lg(x), ly = lg(y);
     272                 :            :   GEN z;
     273         [ -  + ]:        903 :   if (lx == 1) return zerovec(ly-1);
     274                 :        903 :   z = cgetg(ly, t_VEC);
     275         [ +  + ]:       2898 :   for (i = 1; i < ly; i++) gel(z,i) = ZV_dotproduct_i(x, gel(y,i), lx);
     276                 :        903 :   return z;
     277                 :            : }
     278                 :            : 
     279                 :            : GEN
     280                 :          0 : ZC_ZV_mul(GEN x, GEN y)
     281                 :            : {
     282                 :          0 :   long i,j, lx=lg(x), ly=lg(y);
     283                 :            :   GEN z;
     284         [ #  # ]:          0 :   if (ly==1) return cgetg(1,t_MAT);
     285                 :          0 :   z = cgetg(ly,t_MAT);
     286         [ #  # ]:          0 :   for (j=1; j < ly; j++)
     287                 :            :   {
     288                 :          0 :     gel(z,j) = cgetg(lx,t_COL);
     289         [ #  # ]:          0 :     for (i=1; i<lx; i++) gcoeff(z,i,j) = mulii(gel(x,i),gel(y,j));
     290                 :            :   }
     291                 :          0 :   return z;
     292                 :            : }
     293                 :            : 
     294                 :            : GEN
     295                 :    4744184 : ZV_dotsquare(GEN x)
     296                 :            : {
     297                 :            :   long i, lx;
     298                 :            :   pari_sp av;
     299                 :            :   GEN z;
     300                 :    4744184 :   lx = lg(x);
     301         [ -  + ]:    4744184 :   if (lx == 1) return gen_0;
     302                 :    4744184 :   av = avma; z = sqri(gel(x,1));
     303         [ +  + ]:   18376588 :   for (i=2; i<lx; i++) z = addii(z, sqri(gel(x,i)));
     304                 :    4744184 :   return gerepileuptoint(av,z);
     305                 :            : }
     306                 :            : 
     307                 :            : GEN
     308                 :   11658744 : ZV_dotproduct(GEN x,GEN y)
     309                 :            : {
     310                 :            :   long lx;
     311         [ +  + ]:   11658744 :   if (x == y) return ZV_dotsquare(x);
     312                 :    8167396 :   lx = lg(x);
     313         [ -  + ]:    8167396 :   if (lx == 1) return gen_0;
     314                 :   11658744 :   return ZV_dotproduct_i(x, y, lx);
     315                 :            : }
     316                 :            : 
     317                 :            : static GEN
     318                 :        217 : _ZM_mul(void *data /*ignored*/, GEN x, GEN y)
     319                 :        217 : { (void)data; return ZM_mul(x,y); }
     320                 :            : static GEN
     321                 :      48933 : _ZM_sqr(void *data /*ignored*/, GEN x)
     322                 :      48933 : { (void)data; return ZM_mul(x,x); }
     323                 :            : GEN
     324                 :         49 : ZM_pow(GEN x, GEN n)
     325                 :            : {
     326                 :         49 :   pari_sp av = avma;
     327         [ -  + ]:         49 :   if (!signe(n)) return matid(lg(x)-1);
     328                 :         49 :   return gerepileupto(av, gen_pow(x, n, NULL, &_ZM_sqr, &_ZM_mul));
     329                 :            : }
     330                 :            : GEN
     331                 :      47967 : ZM_powu(GEN x, ulong n)
     332                 :            : {
     333                 :      47967 :   pari_sp av = avma;
     334         [ -  + ]:      47967 :   if (!n) return matid(lg(x)-1);
     335                 :      47967 :   return gerepileupto(av, gen_powu(x, n, NULL, &_ZM_sqr, &_ZM_mul));
     336                 :            : }
     337                 :            : /********************************************************************/
     338                 :            : /**                                                                **/
     339                 :            : /**                           ADD, SUB                             **/
     340                 :            : /**                                                                **/
     341                 :            : /********************************************************************/
     342                 :            : static GEN
     343                 :     795046 : ZC_add_i(GEN x, GEN y, long lx)
     344                 :            : {
     345                 :     795046 :   GEN A = cgetg(lx, t_COL);
     346                 :            :   long i;
     347         [ +  + ]:    6363596 :   for (i=1; i<lx; i++) gel(A,i) = addii(gel(x,i), gel(y,i));
     348                 :     795046 :   return A;
     349                 :            : }
     350                 :            : GEN
     351                 :     789568 : ZC_add(GEN x, GEN y) { return ZC_add_i(x, y, lg(x)); }
     352                 :            : GEN
     353                 :      64325 : ZC_Z_add(GEN x, GEN y)
     354                 :            : {
     355                 :      64325 :   long k, lx = lg(x);
     356                 :      64325 :   GEN z = cgetg(lx, t_COL);
     357         [ -  + ]:      64325 :   if (lx == 1) pari_err_TYPE2("+",x,y);
     358                 :      64325 :   gel(z,1) = addii(y,gel(x,1));
     359         [ +  + ]:     832250 :   for (k = 2; k < lx; k++) gel(z,k) = icopy(gel(x,k));
     360                 :      64325 :   return z;
     361                 :            : }
     362                 :            : 
     363                 :            : static GEN
     364                 :    1068789 : ZC_sub_i(GEN x, GEN y, long lx)
     365                 :            : {
     366                 :            :   long i;
     367                 :    1068789 :   GEN A = cgetg(lx, t_COL);
     368         [ +  + ]:    6457148 :   for (i=1; i<lx; i++) gel(A,i) = subii(gel(x,i), gel(y,i));
     369                 :    1068789 :   return A;
     370                 :            : }
     371                 :            : GEN
     372                 :    1020607 : ZC_sub(GEN x, GEN y) { return ZC_sub_i(x, y, lg(x)); }
     373                 :            : GEN
     374                 :          0 : ZC_Z_sub(GEN x, GEN y)
     375                 :            : {
     376                 :          0 :   long k, lx = lg(x);
     377                 :          0 :   GEN z = cgetg(lx, t_COL);
     378         [ #  # ]:          0 :   if (lx == 1) pari_err_TYPE2("+",x,y);
     379                 :          0 :   gel(z,1) = subii(gel(x,1), y);
     380         [ #  # ]:          0 :   for (k = 2; k < lx; k++) gel(z,k) = icopy(gel(x,k));
     381                 :          0 :   return z;
     382                 :            : }
     383                 :            : 
     384                 :            : GEN
     385                 :       2904 : ZM_add(GEN x, GEN y)
     386                 :            : {
     387                 :       2904 :   long lx = lg(x), l, j;
     388                 :            :   GEN z;
     389         [ +  + ]:       2904 :   if (lx == 1) return cgetg(1, t_MAT);
     390                 :       2064 :   z = cgetg(lx, t_MAT); l = lgcols(x);
     391         [ +  + ]:       7542 :   for (j = 1; j < lx; j++) gel(z,j) = ZC_add_i(gel(x,j), gel(y,j), l);
     392                 :       2904 :   return z;
     393                 :            : }
     394                 :            : GEN
     395                 :      10008 : ZM_sub(GEN x, GEN y)
     396                 :            : {
     397                 :      10008 :   long lx = lg(x), l, j;
     398                 :            :   GEN z;
     399         [ -  + ]:      10008 :   if (lx == 1) return cgetg(1, t_MAT);
     400                 :      10008 :   z = cgetg(lx, t_MAT); l = lgcols(x);
     401         [ +  + ]:      58190 :   for (j = 1; j < lx; j++) gel(z,j) = ZC_sub_i(gel(x,j), gel(y,j), l);
     402                 :      10008 :   return z;
     403                 :            : }
     404                 :            : /********************************************************************/
     405                 :            : /**                                                                **/
     406                 :            : /**                         LINEAR COMBINATION                     **/
     407                 :            : /**                                                                **/
     408                 :            : /********************************************************************/
     409                 :            : /* return X/c assuming division is exact */
     410                 :            : GEN
     411                 :     296068 : ZC_Z_divexact(GEN X, GEN c)
     412                 :            : {
     413                 :     296068 :   long i, l = lg(X);
     414                 :     296068 :   GEN A = cgetg(l, t_COL);
     415         [ +  + ]:    3730779 :   for (i=1; i<l; i++) gel(A,i) = diviiexact(gel(X,i), c);
     416                 :     296068 :   return A;
     417                 :            : }
     418                 :            : GEN
     419                 :      49274 : ZM_Z_divexact(GEN X, GEN c)
     420                 :            : {
     421                 :      49274 :   long i, l = lg(X);
     422                 :      49274 :   GEN A = cgetg(l, t_MAT);
     423         [ +  + ]:     207677 :   for (i = 1; i < l; i++) gel(A,i) = ZC_Z_divexact(gel(X,i), c);
     424                 :      49274 :   return A;
     425                 :            : }
     426                 :            : /* Return c * X */
     427                 :            : GEN
     428                 :    2679604 : ZC_Z_mul(GEN X, GEN c)
     429                 :            : {
     430                 :            :   long i, l;
     431                 :            :   GEN A;
     432         [ +  + ]:    2679604 :   if (!signe(c)) return zerocol(lg(X)-1);
     433 [ +  + ][ +  + ]:    2668988 :   if (is_pm1(c)) return (signe(c) > 0)? ZC_copy(X): ZC_neg(X);
     434                 :    2584415 :   l = lg(X); A = cgetg(l, t_COL);
     435         [ +  + ]:   15613299 :   for (i=1; i<l; i++) gel(A,i) = mulii(c,gel(X,i));
     436                 :    2679604 :   return A;
     437                 :            : }
     438                 :            : GEN
     439                 :      12467 : ZC_z_mul(GEN X, long c)
     440                 :            : {
     441                 :            :   long i, l;
     442                 :            :   GEN A;
     443         [ +  + ]:      12467 :   if (!c) return zerocol(lg(X)-1);
     444         [ +  + ]:       6783 :   if (c == 1) return ZC_copy(X);
     445         [ +  + ]:       2331 :   if (c ==-1) return ZC_neg(X);
     446                 :        966 :   l = lg(X); A = cgetg(l, t_COL);
     447         [ +  + ]:       2982 :   for (i=1; i<l; i++) gel(A,i) = mulsi(c,gel(X,i));
     448                 :      12467 :   return A;
     449                 :            : }
     450                 :            : 
     451                 :            : GEN
     452                 :       4379 : zv_z_mul(GEN M, long n)
     453                 :            : {
     454                 :            :   long l;
     455                 :       4379 :   GEN N = cgetg_copy(M, &l);
     456         [ +  + ]:      18278 :   while (--l > 0) N[l] = M[l]*n;
     457                 :       4379 :   return N;
     458                 :            : }
     459                 :            : 
     460                 :            : /* return a ZM */
     461                 :            : GEN
     462                 :        188 : nm_Z_mul(GEN X, GEN c)
     463                 :            : {
     464                 :        188 :   long i, j, h, l = lg(X), s = signe(c);
     465                 :            :   GEN A;
     466         [ -  + ]:        188 :   if (l == 1) return cgetg(1, t_MAT);
     467                 :        188 :   h = lgcols(X);
     468         [ -  + ]:        188 :   if (!s) return zeromat(h-1, l-1);
     469         [ -  + ]:        188 :   if (is_pm1(c)) {
     470         [ #  # ]:          0 :     if (s > 0) return Flm_to_ZM(X);
     471                 :          0 :     X = Flm_to_ZM(X); ZM_togglesign(X); return X;
     472                 :            :   }
     473                 :        188 :   A = cgetg(l, t_MAT);
     474         [ +  + ]:       2974 :   for (j = 1; j < l; j++)
     475                 :            :   {
     476                 :       2786 :     GEN a = cgetg(h, t_COL), x = gel(X, j);
     477         [ +  + ]:      44039 :     for (i = 1; i < h; i++) gel(a,i) = muliu(c, x[i]);
     478                 :       2786 :     gel(A,j) = a;
     479                 :            :   }
     480                 :        188 :   return A;
     481                 :            : }
     482                 :            : GEN
     483                 :      22989 : ZM_Z_mul(GEN X, GEN c)
     484                 :            : {
     485                 :      22989 :   long i, j, h, l = lg(X);
     486                 :            :   GEN A;
     487         [ -  + ]:      22989 :   if (l == 1) return cgetg(1, t_MAT);
     488                 :      22989 :   h = lgcols(X);
     489         [ +  + ]:      22989 :   if (!signe(c)) return zeromat(h-1, l-1);
     490 [ +  + ][ +  - ]:      22954 :   if (is_pm1(c)) return (signe(c) > 0)? ZM_copy(X): ZM_neg(X);
     491                 :      20895 :   A = cgetg(l, t_MAT);
     492         [ +  + ]:      74352 :   for (j = 1; j < l; j++)
     493                 :            :   {
     494                 :      53457 :     GEN a = cgetg(h, t_COL), x = gel(X, j);
     495         [ +  + ]:     237928 :     for (i = 1; i < h; i++) gel(a,i) = mulii(c, gel(x,i));
     496                 :      53457 :     gel(A,j) = a;
     497                 :            :   }
     498                 :      22989 :   return A;
     499                 :            : }
     500                 :            : 
     501                 :            : /* X <- X + v Y (elementary col operation) */
     502                 :            : void
     503                 :   41754265 : ZC_lincomb1_inplace(GEN X, GEN Y, GEN v)
     504                 :            : {
     505                 :   41754265 :   long i, m = lgefint(v);
     506         [ -  + ]:   83508530 :   if (m == 2) return; /* v = 0 */
     507         [ +  + ]:  828055498 :   for (i = lg(X)-1; i; i--) gel(X,i) = addmulii_inplace(gel(X,i), gel(Y,i), v);
     508                 :            : }
     509                 :            : void
     510                 :    7139656 : Flc_lincomb1_inplace(GEN X, GEN Y, ulong v, ulong q)
     511                 :            : {
     512                 :            :   long i;
     513         [ -  + ]:   14279312 :   if (!v) return; /* v = 0 */
     514         [ +  + ]:  255537961 :   for (i = lg(X)-1; i; i--) X[i] = Fl_add(X[i], Fl_mul(Y[i], v, q), q);
     515                 :            : }
     516                 :            : 
     517                 :            : /* X + v Y, wasteful if (v = 0) */
     518                 :            : static GEN
     519                 :    2566074 : ZC_lincomb1(GEN v, GEN X, GEN Y)
     520                 :            : {
     521                 :    2566074 :   long i, lx = lg(X);
     522                 :    2566074 :   GEN A = cgetg(lx,t_COL);
     523         [ +  + ]:   28270849 :   for (i=1; i<lx; i++) gel(A,i) = addmulii(gel(X,i), gel(Y,i), v);
     524                 :    2566074 :   return A;
     525                 :            : }
     526                 :            : /* -X + vY */
     527                 :            : static GEN
     528                 :     503983 : ZC_lincomb_1(GEN v, GEN X, GEN Y)
     529                 :            : {
     530                 :     503983 :   long i, lx = lg(X);
     531                 :     503983 :   GEN A = cgetg(lx,t_COL);
     532         [ +  + ]:    3069289 :   for (i=1; i<lx; i++) gel(A,i) = mulsubii(gel(Y,i), v, gel(X,i));
     533                 :     503983 :   return A;
     534                 :            : }
     535                 :            : /* X,Y compatible ZV; u,v in Z. Returns A = u*X + v*Y */
     536                 :            : GEN
     537                 :    8730323 : ZC_lincomb(GEN u, GEN v, GEN X, GEN Y)
     538                 :            : {
     539                 :            :   long su, sv;
     540                 :            :   GEN A;
     541                 :            : 
     542         [ -  + ]:    8730323 :   su = signe(u); if (!su) return ZC_Z_mul(Y, v);
     543         [ +  + ]:    8730323 :   sv = signe(v); if (!sv) return ZC_Z_mul(X, u);
     544         [ +  + ]:    8730309 :   if (is_pm1(v))
     545                 :            :   {
     546         [ +  + ]:    1825823 :     if (is_pm1(u))
     547                 :            :     {
     548         [ +  + ]:    1083380 :       if (su != sv) A = ZC_sub(X, Y);
     549                 :     486255 :       else          A = ZC_add(X, Y);
     550         [ +  + ]:    1083380 :       if (su < 0) ZV_togglesign(A); /* in place but was created above */
     551                 :            :     }
     552                 :            :     else
     553                 :            :     {
     554         [ +  + ]:     742443 :       if (sv > 0) A = ZC_lincomb1 (u, Y, X);
     555                 :     330920 :       else        A = ZC_lincomb_1(u, Y, X);
     556                 :            :     }
     557                 :            :   }
     558         [ +  + ]:    6904486 :   else if (is_pm1(u))
     559                 :            :   {
     560         [ +  + ]:    2327614 :     if (su > 0) A = ZC_lincomb1 (v, X, Y);
     561                 :     173063 :     else        A = ZC_lincomb_1(v, X, Y);
     562                 :            :   }
     563                 :            :   else
     564                 :            :   { /* not cgetg_copy: x may be a t_VEC */
     565                 :    4576872 :     long i, lx = lg(X);
     566                 :    4576872 :     A = cgetg(lx,t_COL);
     567         [ +  + ]:   29007070 :     for (i=1; i<lx; i++) gel(A,i) = lincombii(u,v,gel(X,i),gel(Y,i));
     568                 :            :   }
     569                 :    8730323 :   return A;
     570                 :            : }
     571                 :            : 
     572                 :            : /********************************************************************/
     573                 :            : /**                                                                **/
     574                 :            : /**                           CONVERSIONS                          **/
     575                 :            : /**                                                                **/
     576                 :            : /********************************************************************/
     577                 :            : GEN
     578                 :        469 : ZV_to_nv(GEN z)
     579                 :            : {
     580                 :        469 :   long i, l = lg(z);
     581                 :        469 :   GEN x = cgetg(l, t_VECSMALL);
     582         [ +  + ]:        682 :   for (i=1; i<l; i++) x[i] = itou(gel(z,i));
     583                 :        469 :   return x;
     584                 :            : }
     585                 :            : 
     586                 :            : GEN
     587                 :      12999 : zm_to_ZM(GEN z)
     588                 :            : {
     589                 :      12999 :   long i, l = lg(z);
     590                 :      12999 :   GEN x = cgetg(l,t_MAT);
     591         [ +  + ]:      94805 :   for (i=1; i<l; i++) gel(x,i) = zc_to_ZC(gel(z,i));
     592                 :      12999 :   return x;
     593                 :            : }
     594                 :            : 
     595                 :            : GEN
     596                 :         63 : zmV_to_ZMV(GEN z)
     597                 :            : {
     598                 :         63 :   long i, l = lg(z);
     599                 :         63 :   GEN x = cgetg(l,t_VEC);
     600         [ +  + ]:        476 :   for (i=1; i<l; i++) gel(x,i) = zm_to_ZM(gel(z,i));
     601                 :         63 :   return x;
     602                 :            : }
     603                 :            : 
     604                 :            : /* same as Flm_to_ZM but do not assume positivity */
     605                 :            : GEN
     606                 :        238 : ZM_to_zm(GEN z)
     607                 :            : {
     608                 :        238 :   long i, l = lg(z);
     609                 :        238 :   GEN x = cgetg(l,t_MAT);
     610         [ +  + ]:     184548 :   for (i=1; i<l; i++) gel(x,i) = ZV_to_zv(gel(z,i));
     611                 :        238 :   return x;
     612                 :            : }
     613                 :            : 
     614                 :            : GEN
     615                 :     174296 : zv_to_Flv(GEN z, ulong p)
     616                 :            : {
     617                 :     174296 :   long i, l = lg(z);
     618                 :     174296 :   GEN x = cgetg(l,t_VECSMALL);
     619         [ +  + ]:    2740984 :   for (i=1; i<l; i++) x[i] = smodss(z[i],p);
     620                 :     174296 :   return x;
     621                 :            : }
     622                 :            : 
     623                 :            : GEN
     624                 :      12050 : zm_to_Flm(GEN z, ulong p)
     625                 :            : {
     626                 :      12050 :   long i, l = lg(z);
     627                 :      12050 :   GEN x = cgetg(l,t_MAT);
     628         [ +  + ]:     186346 :   for (i=1; i<l; i++) gel(x,i) = zv_to_Flv(gel(z,i),p);
     629                 :      12050 :   return x;
     630                 :            : }
     631                 :            : 
     632                 :            : GEN
     633                 :          0 : ZMV_to_zmV(GEN z)
     634                 :            : {
     635                 :          0 :   long i,l = lg(z);
     636                 :          0 :   GEN x = cgetg(l, t_VEC);
     637         [ #  # ]:          0 :   for (i=1; i<l; i++) gel(x,i) = ZM_to_zm(gel(z,i));
     638                 :          0 :   return x;
     639                 :            : }
     640                 :            : 
     641                 :            : /********************************************************************/
     642                 :            : /**                                                                **/
     643                 :            : /**                         COPY, NEGATION                         **/
     644                 :            : /**                                                                **/
     645                 :            : /********************************************************************/
     646                 :            : GEN
     647                 :     494440 : ZC_copy(GEN x)
     648                 :            : {
     649                 :     494440 :   long i, lx = lg(x);
     650                 :     494440 :   GEN y = cgetg(lx, t_COL);
     651         [ +  + ]:    2787888 :   for (i=1; i<lx; i++)
     652                 :            :   {
     653                 :    2293448 :     GEN c = gel(x,i);
     654         [ +  + ]:    2293448 :     gel(y,i) = lgefint(c) == 2? gen_0: icopy(c);
     655                 :            :   }
     656                 :     494440 :   return y;
     657                 :            : }
     658                 :            : 
     659                 :            : GEN
     660                 :      26903 : ZM_copy(GEN x)
     661                 :            : {
     662                 :            :   long l;
     663                 :      26903 :   GEN y = cgetg_copy(x, &l);
     664         [ +  + ]:     238074 :   while (--l > 0) gel(y,l) = ZC_copy(gel(x,l));
     665                 :      26903 :   return y;
     666                 :            : }
     667                 :            : 
     668                 :            : void
     669                 :      32625 : ZV_neg_inplace(GEN M)
     670                 :            : {
     671                 :      32625 :   long l = lg(M);
     672         [ +  + ]:     360268 :   while (--l > 0) gel(M,l) = negi(gel(M,l));
     673                 :      32625 : }
     674                 :            : GEN
     675                 :    1437902 : ZC_neg(GEN M)
     676                 :            : {
     677                 :    1437902 :   long l = lg(M);
     678                 :    1437902 :   GEN N = cgetg(l, t_COL);
     679         [ +  + ]:   10871092 :   while (--l > 0) gel(N,l) = negi(gel(M,l));
     680                 :    1437902 :   return N;
     681                 :            : }
     682                 :            : GEN
     683                 :     241300 : zv_neg(GEN M)
     684                 :            : {
     685                 :            :   long l;
     686                 :     241300 :   GEN N = cgetg_copy(M, &l);
     687         [ +  + ]:    1940544 :   while (--l > 0) N[l] = -M[l];
     688                 :     241300 :   return N;
     689                 :            : }
     690                 :            : GEN
     691                 :         84 : zv_neg_inplace(GEN M)
     692                 :            : {
     693                 :         84 :   long l = lg(M);
     694         [ +  + ]:        321 :   while (--l > 0) M[l] = -M[l];
     695                 :         84 :   return M;
     696                 :            : }
     697                 :            : GEN
     698                 :        616 : ZM_neg(GEN x)
     699                 :            : {
     700                 :            :   long l;
     701                 :        616 :   GEN y = cgetg_copy(x, &l);
     702         [ +  + ]:       3283 :   while (--l > 0) gel(y,l) = ZC_neg(gel(x,l));
     703                 :        616 :   return y;
     704                 :            : }
     705                 :            : 
     706                 :            : void
     707                 :     873145 : ZV_togglesign(GEN M)
     708                 :            : {
     709                 :     873145 :   long l = lg(M);
     710         [ +  + ]:   23864556 :   while (--l > 0) togglesign_safe(&gel(M,l));
     711                 :     873145 : }
     712                 :            : void
     713                 :          0 : ZM_togglesign(GEN M)
     714                 :            : {
     715                 :          0 :   long l = lg(M);
     716         [ #  # ]:          0 :   while (--l > 0) ZV_togglesign(gel(M,l));
     717                 :          0 : }
     718                 :            : 
     719                 :            : /********************************************************************/
     720                 :            : /**                                                                **/
     721                 :            : /**                        "DIVISION" mod HNF                      **/
     722                 :            : /**                                                                **/
     723                 :            : /********************************************************************/
     724                 :            : /* Reduce ZC x modulo ZM y in HNF, may return x itself (not a copy) */
     725                 :            : GEN
     726                 :     853771 : ZC_hnfremdiv(GEN x, GEN y, GEN *Q)
     727                 :            : {
     728                 :     853771 :   long i, l = lg(x);
     729                 :            :   GEN q;
     730                 :            : 
     731         [ +  + ]:     853771 :   if (Q) *Q = cgetg(l,t_COL);
     732         [ -  + ]:     853771 :   if (l == 1) return cgetg(1,t_COL);
     733         [ +  + ]:    5096562 :   for (i = l-1; i>0; i--)
     734                 :            :   {
     735                 :    4242791 :     q = diviiround(gel(x,i), gcoeff(y,i,i));
     736         [ +  + ]:    4242791 :     if (signe(q)) {
     737                 :    2405812 :       togglesign(q);
     738                 :    2405812 :       x = ZC_lincomb(gen_1, q, x, gel(y,i));
     739                 :            :     }
     740         [ +  + ]:    4242791 :     if (Q) gel(*Q, i) = q;
     741                 :            :   }
     742                 :     853771 :   return x;
     743                 :            : }
     744                 :            : 
     745                 :            : /* x = y Q + R, may return some columns of x (not copies) */
     746                 :            : GEN
     747                 :      28029 : ZM_hnfdivrem(GEN x, GEN y, GEN *Q)
     748                 :            : {
     749                 :      28029 :   long lx = lg(x), i;
     750                 :      28029 :   GEN R = cgetg(lx, t_MAT);
     751         [ +  + ]:      28029 :   if (Q)
     752                 :            :   {
     753                 :       2716 :     GEN q = cgetg(lx, t_MAT); *Q = q;
     754         [ +  + ]:       5408 :     for (i=1; i<lx; i++) gel(R,i) = ZC_hnfremdiv(gel(x,i),y,(GEN*)(q+i));
     755                 :            :   }
     756                 :            :   else
     757         [ +  + ]:      96822 :     for (i=1; i<lx; i++)
     758                 :            :     {
     759                 :      71509 :       pari_sp av = avma;
     760                 :      71509 :       GEN z = ZC_hnfrem(gel(x,i),y);
     761         [ +  + ]:      71509 :       gel(R,i) = (avma == av)? ZC_copy(z): gerepileupto(av, z);
     762                 :            :     }
     763                 :      28029 :   return R;
     764                 :            : }
     765                 :            : 
     766                 :            : 
     767                 :            : /********************************************************************/
     768                 :            : /**                                                                **/
     769                 :            : /**                               TESTS                            **/
     770                 :            : /**                                                                **/
     771                 :            : /********************************************************************/
     772                 :            : int
     773                 :   13711447 : zv_equal0(GEN V)
     774                 :            : {
     775                 :   13711447 :   long l = lg(V);
     776         [ +  + ]:   21757839 :   while (--l > 0)
     777         [ +  + ]:   17311103 :     if (V[l]) return 0;
     778                 :   13711447 :   return 1;
     779                 :            : }
     780                 :            : 
     781                 :            : int
     782                 :     286301 : ZV_equal0(GEN V)
     783                 :            : {
     784                 :     286301 :   long l = lg(V);
     785         [ +  + ]:    1076471 :   while (--l > 0)
     786         [ +  + ]:    1007950 :     if (signe(gel(V,l))) return 0;
     787                 :     286301 :   return 1;
     788                 :            : }
     789                 :            : 
     790                 :            : static int
     791                 :    9154642 : ZV_equal_lg(GEN V, GEN W, long l)
     792                 :            : {
     793         [ +  + ]:   17060115 :   while (--l > 0)
     794         [ +  + ]:   14793633 :     if (!equalii(gel(V,l), gel(W,l))) return 0;
     795                 :    9154642 :   return 1;
     796                 :            : }
     797                 :            : int
     798                 :    7623679 : ZV_equal(GEN V, GEN W)
     799                 :            : {
     800                 :    7623679 :   long l = lg(V);
     801         [ -  + ]:    7623679 :   if (lg(W) != l) return 0;
     802                 :    7623679 :   return ZV_equal_lg(V, W, l);
     803                 :            : }
     804                 :            : int
     805                 :     494551 : ZM_equal(GEN A, GEN B)
     806                 :            : {
     807                 :     494551 :   long i, m, l = lg(A);
     808         [ +  + ]:     494551 :   if (lg(B) != l) return 0;
     809         [ -  + ]:     494187 :   if (l == 1) return 1;
     810                 :     494187 :   m = lgcols(A);
     811         [ -  + ]:     494187 :   if (lgcols(B) != m) return 0;
     812         [ +  + ]:    1985357 :   for (i = 1; i < l; i++)
     813         [ +  + ]:    1530963 :     if (!ZV_equal_lg(gel(A,i), gel(B,i), m)) return 0;
     814                 :     494551 :   return 1;
     815                 :            : }
     816                 :            : int
     817                 :    2251961 : zv_equal(GEN V, GEN W)
     818                 :            : {
     819                 :    2251961 :   long l = lg(V);
     820         [ +  + ]:    2251961 :   if (lg(W) != l) return 0;
     821         [ +  + ]:   14795069 :   while (--l > 0)
     822         [ +  + ]:   12931598 :     if (V[l] != W[l]) return 0;
     823                 :    2251961 :   return 1;
     824                 :            : }
     825                 :            : 
     826                 :            : int
     827                 :        315 : zvV_equal(GEN V, GEN W)
     828                 :            : {
     829                 :        315 :   long l = lg(V);
     830         [ +  + ]:        315 :   if (lg(W) != l) return 0;
     831         [ +  + ]:      58352 :   while (--l > 0)
     832         [ +  + ]:      58170 :     if (!zv_equal(gel(V,l),gel(W,l))) return 0;
     833                 :        315 :   return 1;
     834                 :            : }
     835                 :            : 
     836                 :            : int
     837                 :      49926 : ZM_ishnf(GEN x)
     838                 :            : {
     839                 :      49926 :   long i,j, lx = lg(x);
     840         [ +  + ]:     234227 :   for (i=1; i<lx; i++)
     841                 :            :   {
     842                 :     191390 :     GEN xii = gcoeff(x,i,i);
     843         [ +  + ]:     191390 :     if (signe(xii) <= 0) return 0;
     844         [ +  + ]:     718424 :     for (j=1; j<i; j++)
     845         [ -  + ]:     527503 :       if (signe(gcoeff(x,i,j))) return 0;
     846         [ +  + ]:     746957 :     for (j=i+1; j<lx; j++)
     847                 :            :     {
     848                 :     562656 :       GEN xij = gcoeff(x,i,j);
     849 [ +  + ][ +  + ]:     562656 :       if (signe(xij)<0 || cmpii(xij,xii)>=0) return 0;
     850                 :            :     }
     851                 :            :   }
     852                 :      49926 :   return 1;
     853                 :            : }
     854                 :            : int
     855                 :       2265 : ZM_isidentity(GEN x)
     856                 :            : {
     857                 :       2265 :   long i,j, lx = lg(x);
     858                 :            : 
     859         [ -  + ]:       2265 :   if (lx == 1) return 1;
     860         [ -  + ]:       2265 :   if (lx != lgcols(x)) return 0;
     861         [ +  + ]:       9990 :   for (j=1; j<lx; j++)
     862                 :            :   {
     863                 :       7725 :     GEN c = gel(x,j), t;
     864         [ +  + ]:      29147 :     for (i=1; i<j; )
     865         [ -  + ]:      21422 :       if (signe(gel(c,i++))) return 0;
     866                 :            :     /* i = j */
     867                 :       7725 :     t = gel(c,i++);
     868 [ +  - ][ -  + ]:       7725 :       if (!is_pm1(t) || signe(t) < 0) return 0;
     869         [ +  + ]:      29147 :     for (   ; i<lx; )
     870         [ -  + ]:      21422 :       if (signe(gel(c,i++))) return 0;
     871                 :            :   }
     872                 :       2265 :   return 1;
     873                 :            : }
     874                 :            : 
     875                 :            : /********************************************************************/
     876                 :            : /**                                                                **/
     877                 :            : /**                       MISCELLANEOUS                            **/
     878                 :            : /**                                                                **/
     879                 :            : /********************************************************************/
     880                 :            : /* assume lg(x) = lg(y), x,y in Z^n */
     881                 :            : int
     882                 :     464153 : ZV_cmp(GEN x, GEN y)
     883                 :            : {
     884                 :     464153 :   long fl,i, lx = lg(x);
     885         [ +  + ]:    1078428 :   for (i=1; i<lx; i++)
     886         [ +  + ]:     936524 :     if (( fl = cmpii(gel(x,i), gel(y,i)) )) return fl;
     887                 :     464153 :   return 0;
     888                 :            : }
     889                 :            : /* assume lg(x) = lg(y), x,y in Z^n */
     890                 :            : int
     891                 :       3375 : ZV_abscmp(GEN x, GEN y)
     892                 :            : {
     893                 :       3375 :   long fl,i, lx = lg(x);
     894         [ +  + ]:      19302 :   for (i=1; i<lx; i++)
     895         [ +  + ]:      19215 :     if (( fl = absi_cmp(gel(x,i), gel(y,i)) )) return fl;
     896                 :       3375 :   return 0;
     897                 :            : }
     898                 :            : 
     899                 :            : long
     900                 :    1677360 : zv_content(GEN x)
     901                 :            : {
     902                 :    1677360 :   long i, l = lg(x), s = labs(x[1]);
     903 [ +  + ][ +  + ]:    3484581 :   for (i=2; i<l && s!=1; i++) s = cgcd(x[i],s);
     904                 :    1677360 :   return s;
     905                 :            : }
     906                 :            : GEN
     907                 :       2786 : ZV_content(GEN x)
     908                 :            : {
     909                 :       2786 :   long i, l = lg(x);
     910                 :       2786 :   pari_sp av = avma;
     911                 :            :   GEN c;
     912         [ -  + ]:       2786 :   if (l == 1) return gen_1;
     913         [ +  + ]:       2786 :   if (l == 2) return absi(gel(x,1));
     914                 :       1190 :   c = gel(x,1);
     915         [ +  + ]:       2576 :   for (i = 2; i < l; i++)
     916                 :            :   {
     917                 :       1694 :     c = gcdii(c, gel(x,i));
     918         [ +  + ]:       1694 :     if (is_pm1(c)) { avma = av; return gen_1; }
     919                 :            :   }
     920                 :       2786 :   return gerepileuptoint(av, c);
     921                 :            : }
     922                 :            : 
     923                 :            : GEN
     924                 :     712114 : ZM_det_triangular(GEN mat)
     925                 :            : {
     926                 :            :   pari_sp av;
     927                 :     712114 :   long i,l = lg(mat);
     928                 :            :   GEN s;
     929                 :            : 
     930 [ +  + ][ +  + ]:     712114 :   if (l<3) return l<2? gen_1: icopy(gcoeff(mat,1,1));
     931                 :     697526 :   av = avma; s = gcoeff(mat,1,1);
     932         [ +  + ]:    2082295 :   for (i=2; i<l; i++) s = mulii(s,gcoeff(mat,i,i));
     933                 :     712114 :   return gerepileuptoint(av,s);
     934                 :            : }
     935                 :            : 
     936                 :            : /* assumes no overflow */
     937                 :            : long
     938                 :     289447 : zv_prod(GEN v)
     939                 :            : {
     940                 :     289447 :   long n, i, l = lg(v);
     941         [ +  + ]:     289447 :   if (l == 1) return 1;
     942         [ +  + ]:     322340 :   n = v[1]; for (i = 2; i < l; i++) n *= v[i];
     943                 :     289447 :   return n;
     944                 :            : }
     945                 :            : /* product of ulongs */
     946                 :            : GEN
     947                 :     363468 : zv_prod_Z(GEN v)
     948                 :            : {
     949                 :     363468 :   pari_sp av = avma;
     950                 :     363468 :   long k, n = lg(v)-1, m;
     951                 :            :   GEN x;
     952         [ +  + ]:     363468 :   if (n == 0) return gen_1;
     953         [ +  + ]:     344029 :   if (n == 1) return utoi(v[1]);
     954         [ +  + ]:     288050 :   if (n == 2) return muluu(v[1], v[2]);
     955                 :     163380 :   m = n >> 1;
     956         [ +  + ]:     163380 :   x = cgetg(m + (odd(n)? 2: 1), t_VEC);
     957         [ +  + ]:     367157 :   for (k = 1; k <= m; k++) gel(x,k) = muluu(v[k<<1], v[(k<<1)-1]);
     958         [ +  + ]:     163380 :   if (odd(n)) gel(x,k) = utoipos(v[n]);
     959                 :     363468 :   return gerepileuptoint(av, divide_conquer_prod(x, mulii));
     960                 :            : }
     961                 :            : 
     962                 :            : GEN
     963                 :      18155 : ZV_prod(GEN v)
     964                 :            : {
     965                 :      18155 :   pari_sp av = avma;
     966                 :      18155 :   long i, l = lg(v);
     967                 :            :   GEN n;
     968         [ +  + ]:      18155 :   if (l == 1) return gen_1;
     969         [ +  + ]:      17476 :   if (l > 7) return gerepileuptoint(av, divide_conquer_prod(v, mulii));
     970                 :      15137 :   n = gel(v,1);
     971         [ +  + ]:      15137 :   if (l == 2) return icopy(n);
     972         [ +  + ]:      25604 :   for (i = 2; i < l; i++) n = mulii(n, gel(v,i));
     973                 :      18155 :   return gerepileuptoint(av, n);
     974                 :            : }
     975                 :            : /* assumes no overflow */
     976                 :            : long
     977                 :        203 : zv_sum(GEN v)
     978                 :            : {
     979                 :        203 :   long n, i, l = lg(v);
     980         [ +  + ]:        203 :   if (l == 1) return 0;
     981         [ +  + ]:        980 :   n = v[1]; for (i = 2; i < l; i++) n += v[i];
     982                 :        203 :   return n;
     983                 :            : }
     984                 :            : GEN
     985                 :         56 : ZV_sum(GEN v)
     986                 :            : {
     987                 :         56 :   pari_sp av = avma;
     988                 :         56 :   long i, l = lg(v);
     989                 :            :   GEN n;
     990         [ -  + ]:         56 :   if (l == 1) return gen_0;
     991                 :         56 :   n = gel(v,1);
     992         [ -  + ]:         56 :   if (l == 2) return icopy(n);
     993         [ +  + ]:        518 :   for (i = 2; i < l; i++) n = addii(n, gel(v,i));
     994                 :         56 :   return gerepileuptoint(av, n);
     995                 :            : }
     996                 :            : 
     997                 :            : /********************************************************************/
     998                 :            : /**                                                                **/
     999                 :            : /**         GRAM SCHMIDT REDUCTION (integer matrices)              **/
    1000                 :            : /**                                                                **/
    1001                 :            : /********************************************************************/
    1002                 :            : 
    1003                 :            : /* L[k,] += q * L[l,], l < k. Inefficient if q = 0 */
    1004                 :            : static void
    1005                 :     208737 : Zupdate_row(long k, long l, GEN q, GEN L, GEN B)
    1006                 :            : {
    1007                 :     208737 :   long i, qq = itos_or_0(q);
    1008         [ +  + ]:     208737 :   if (!qq)
    1009                 :            :   {
    1010         [ +  + ]:      16223 :     for(i=1;i<l;i++)  gcoeff(L,k,i) = addii(gcoeff(L,k,i),mulii(q,gcoeff(L,l,i)));
    1011                 :       4647 :     gcoeff(L,k,l) = addii(gcoeff(L,k,l), mulii(q,B));
    1012                 :     208737 :     return;
    1013                 :            :   }
    1014         [ +  + ]:     204090 :   if (qq == 1) {
    1015         [ +  + ]:      84427 :     for (i=1;i<l; i++) gcoeff(L,k,i) = addii(gcoeff(L,k,i),gcoeff(L,l,i));
    1016                 :      47863 :     gcoeff(L,k,l) = addii(gcoeff(L,k,l), B);
    1017         [ +  + ]:     156227 :   } else if (qq == -1) {
    1018         [ +  + ]:     182692 :     for (i=1;i<l; i++) gcoeff(L,k,i) = subii(gcoeff(L,k,i),gcoeff(L,l,i));
    1019                 :      99457 :     gcoeff(L,k,l) = addii(gcoeff(L,k,l), negi(B));
    1020                 :            :   } else {
    1021         [ +  + ]:     113292 :     for(i=1;i<l;i++) gcoeff(L,k,i) = addii(gcoeff(L,k,i),mulsi(qq,gcoeff(L,l,i)));
    1022                 :      56770 :     gcoeff(L,k,l) = addii(gcoeff(L,k,l), mulsi(qq,B));
    1023                 :            :   }
    1024                 :            : }
    1025                 :            : 
    1026                 :            : /* update L[k,] */
    1027                 :            : static void
    1028                 :     683038 : ZRED(long k, long l, GEN x, GEN L, GEN B)
    1029                 :            : {
    1030                 :     683038 :   GEN q = truedivii(addii(B,shifti(gcoeff(L,k,l),1)), shifti(B,1));
    1031         [ +  + ]:     891775 :   if (!signe(q)) return;
    1032                 :     208737 :   q = negi(q);
    1033                 :     208737 :   Zupdate_row(k,l,q,L,B);
    1034                 :     208737 :   gel(x,k) = ZC_lincomb(gen_1, q, gel(x,k), gel(x,l));
    1035                 :            : }
    1036                 :            : 
    1037                 :            : /* Gram-Schmidt reduction, x a ZM */
    1038                 :            : static void
    1039                 :     913552 : ZincrementalGS(GEN x, GEN L, GEN B, long k)
    1040                 :            : {
    1041                 :            :   long i, j;
    1042         [ +  + ]:    3247418 :   for (j=1; j<=k; j++)
    1043                 :            :   {
    1044                 :    2333866 :     pari_sp av = avma;
    1045                 :    2333866 :     GEN u = ZV_dotproduct(gel(x,k), gel(x,j));
    1046         [ +  + ]:    5250051 :     for (i=1; i<j; i++)
    1047                 :            :     {
    1048                 :    2916185 :       u = subii(mulii(gel(B,i+1), u), mulii(gcoeff(L,k,i), gcoeff(L,j,i)));
    1049                 :    2916185 :       u = diviiexact(u, gel(B,i));
    1050                 :            :     }
    1051                 :    2333866 :     gcoeff(L,k,j) = gerepileuptoint(av, u);
    1052                 :            :   }
    1053                 :     913552 :   gel(B,k+1) = gcoeff(L,k,k); gcoeff(L,k,k) = gen_1;
    1054                 :     913552 : }
    1055                 :            : 
    1056                 :            : /* Variant reducemodinvertible(ZC v, ZM y), when y singular.
    1057                 :            :  * Very inefficient if y is not LLL-reduced of maximal rank */
    1058                 :            : static GEN
    1059                 :     234395 : ZC_reducemodmatrix_i(GEN v, GEN y)
    1060                 :            : {
    1061                 :     234395 :   GEN B, L, x = shallowconcat(y, v);
    1062                 :     234395 :   long k, lx = lg(x), nx = lx-1;
    1063                 :            : 
    1064                 :     234395 :   B = scalarcol_shallow(gen_1, lx);
    1065                 :     234395 :   L = zeromatcopy(nx, nx);
    1066         [ +  + ]:    1128066 :   for (k=1; k <= nx; k++) ZincrementalGS(x, L, B, k);
    1067         [ +  + ]:     893671 :   for (k = nx-1; k >= 1; k--) ZRED(nx,k, x,L,gel(B,k+1));
    1068                 :     234395 :   return gel(x,nx);
    1069                 :            : }
    1070                 :            : GEN
    1071                 :     234395 : ZC_reducemodmatrix(GEN v, GEN y) {
    1072                 :     234395 :   pari_sp av = avma;
    1073                 :     234395 :   return gerepilecopy(av, ZC_reducemodmatrix_i(v,y));
    1074                 :            : }
    1075                 :            : 
    1076                 :            : /* Variant reducemodinvertible(ZM v, ZM y), when y singular.
    1077                 :            :  * Very inefficient if y is not LLL-reduced of maximal rank */
    1078                 :            : static GEN
    1079                 :       4401 : ZM_reducemodmatrix_i(GEN v, GEN y)
    1080                 :            : {
    1081                 :            :   GEN B, L, V;
    1082                 :       4401 :   long j, k, lv = lg(v), nx = lg(y), lx = nx+1;
    1083                 :            : 
    1084                 :       4401 :   V = cgetg(lv, t_MAT);
    1085                 :       4401 :   B = scalarcol_shallow(gen_1, lx);
    1086                 :       4401 :   L = zeromatcopy(nx, nx);
    1087         [ +  + ]:      14601 :   for (k=1; k < nx; k++) ZincrementalGS(y, L, B, k);
    1088         [ +  + ]:      14082 :   for (j = 1; j < lg(v); j++)
    1089                 :            :   {
    1090                 :       9681 :     GEN x = shallowconcat(y, gel(v,j));
    1091                 :       9681 :     ZincrementalGS(x, L, B, nx); /* overwrite last */
    1092         [ +  + ]:      33443 :     for (k = nx-1; k >= 1; k--) ZRED(nx,k, x,L,gel(B,k+1));
    1093                 :       9681 :     gel(V,j) = gel(x,nx);
    1094                 :            :   }
    1095                 :       4401 :   return V;
    1096                 :            : }
    1097                 :            : GEN
    1098                 :       4401 : ZM_reducemodmatrix(GEN v, GEN y) {
    1099                 :       4401 :   pari_sp av = avma;
    1100                 :       4401 :   return gerepilecopy(av, ZM_reducemodmatrix_i(v,y));
    1101                 :            : }
    1102                 :            : 
    1103                 :            : GEN
    1104                 :     234346 : ZC_reducemodlll(GEN x,GEN y)
    1105                 :            : {
    1106                 :     234346 :   pari_sp av = avma;
    1107                 :     234346 :   GEN z = ZC_reducemodmatrix(x, ZM_lll(y, 0.75, LLL_INPLACE));
    1108                 :     234346 :   return gerepilecopy(av, z);
    1109                 :            : }
    1110                 :            : GEN
    1111                 :          0 : ZM_reducemodlll(GEN x,GEN y)
    1112                 :            : {
    1113                 :          0 :   pari_sp av = avma;
    1114                 :          0 :   GEN z = ZM_reducemodmatrix(x, ZM_lll(y, 0.75, LLL_INPLACE));
    1115                 :          0 :   return gerepilecopy(av, z);
    1116                 :            : }

Generated by: LCOV version 1.9