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 17931-6d987be) Lines: 682 767 88.9 %
Date: 2015-07-29 Functions: 98 106 92.5 %
Legend: Lines: hit not hit | Branches: + taken - not taken # not executed Branches: 436 542 80.4 %

           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                 :      32431 : check_ZV(GEN x, long l)
      19                 :            : {
      20                 :            :   long i;
      21         [ +  + ]:     197218 :   for (i=1; i<l; i++)
      22         [ +  + ]:     164871 :     if (typ(gel(x,i)) != t_INT) return 0;
      23                 :      32431 :   return 1;
      24                 :            : }
      25                 :            : void
      26                 :     432655 : RgV_check_ZV(GEN A, const char *s)
      27                 :            : {
      28         [ +  + ]:     432655 :   if (!RgV_is_ZV(A)) pari_err_TYPE(stack_strcat(s," [integer vector]"), A);
      29                 :     432641 : }
      30                 :            : void
      31                 :       9051 : RgM_check_ZM(GEN A, const char *s)
      32                 :            : {
      33                 :       9051 :   long n = lg(A);
      34         [ +  + ]:       9051 :   if (n != 1)
      35                 :            :   {
      36                 :       9016 :     long j, m = lgcols(A);
      37         [ +  + ]:      41363 :     for (j=1; j<n; j++)
      38         [ +  + ]:      32431 :       if (!check_ZV(gel(A,j), m))
      39                 :         84 :         pari_err_TYPE(stack_strcat(s," [integer matrix]"), A);
      40                 :            :   }
      41                 :       8967 : }
      42                 :            : 
      43                 :            : long
      44                 :      10612 : ZV_max_lg(GEN x)
      45                 :            : {
      46                 :      10612 :   long i, prec = 2, m = lg(x);
      47 [ +  + ][ +  + ]:      30072 :   for (i=1; i<m; i++) { long l = lgefint(gel(x,i)); if (l > prec) prec = l; }
      48                 :      10612 :   return prec;
      49                 :            : }
      50                 :            : long
      51                 :       1505 : ZM_max_lg(GEN x)
      52                 :            : {
      53                 :       1505 :   long i, prec = 2, n = lg(x);
      54         [ +  - ]:       1505 :   if (n != 1)
      55                 :            :   {
      56                 :       1505 :     long j, m = lgcols(x);
      57         [ +  + ]:      11557 :     for (j=1; j<n; j++)
      58                 :            :     {
      59                 :      10052 :       GEN c = gel(x,j);
      60 [ +  + ][ +  + ]:     167342 :       for (i=1; i<m; i++) { long l = lgefint(gel(c,i)); if (l > prec) prec = l; }
      61                 :            :     }
      62                 :            :   }
      63                 :       1505 :   return prec;
      64                 :            : }
      65                 :            : 
      66                 :            : GEN
      67                 :        854 : ZM_supnorm(GEN x)
      68                 :            : {
      69                 :        854 :   long i, j, h, lx = lg(x);
      70                 :        854 :   GEN s = gen_0;
      71         [ -  + ]:        854 :   if (lx == 1) return gen_1;
      72                 :        854 :   h = lgcols(x);
      73         [ +  + ]:       9002 :   for (j=1; j<lx; j++)
      74                 :            :   {
      75                 :       8148 :     GEN xj = gel(x,j);
      76         [ +  + ]:     163548 :     for (i=1; i<h; i++)
      77                 :            :     {
      78                 :     155400 :       GEN c = gel(xj,i);
      79         [ +  + ]:     155400 :       if (absi_cmp(c, s) > 0) s = c;
      80                 :            :     }
      81                 :            :   }
      82                 :        854 :   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                 :       3749 : ZM_nc_mul_i(GEN x, GEN y, long c, long l)
      93                 :            : {
      94                 :            :   long i, j;
      95                 :            :   pari_sp av;
      96                 :       3749 :   GEN z = cgetg(l,t_COL), s;
      97                 :            : 
      98         [ +  + ]:      77015 :   for (i=1; i<l; i++)
      99                 :            :   {
     100                 :      73266 :     av = avma; s = muliu(gcoeff(x,i,1),y[1]);
     101         [ +  + ]:    2274248 :     for (j=2; j<c; j++)
     102         [ +  + ]:    2200982 :       if (y[j]) s = addii(s, muliu(gcoeff(x,i,j),y[j]));
     103                 :      73266 :     gel(z,i) = gerepileuptoint(av,s);
     104                 :            :   }
     105                 :       3749 :   return z;
     106                 :            : }
     107                 :            : 
     108                 :            : /* x ZV, y a compatible zc. */
     109                 :            : GEN
     110                 :          0 : ZV_zc_mul(GEN x, GEN y)
     111                 :            : {
     112                 :          0 :   long j, l = lg(x);
     113                 :          0 :   pari_sp av = avma;
     114                 :          0 :   GEN s = mulis(gel(x,1),y[1]);
     115         [ #  # ]:          0 :   for (j=2; j<l; j++)
     116         [ #  # ]:          0 :     if (y[j]) s = addii(s, mulis(gel(x,j),y[j]));
     117                 :          0 :   return gerepileuptoint(av,s);
     118                 :            : }
     119                 :            : 
     120                 :            : /* x non-empty ZM, y a compatible zc (dimension > 0). */
     121                 :            : static GEN
     122                 :    1491514 : ZM_zc_mul_i(GEN x, GEN y, long c, long l)
     123                 :            : {
     124                 :            :   long i, j;
     125                 :            :   pari_sp av;
     126                 :    1491514 :   GEN z = cgetg(l,t_COL), s;
     127                 :            : 
     128         [ +  + ]:   12997099 :   for (i=1; i<l; i++)
     129                 :            :   {
     130                 :   11505585 :     av = avma; s = mulis(gcoeff(x,i,1),y[1]);
     131         [ +  + ]:  240714080 :     for (j=2; j<c; j++)
     132         [ +  + ]:  229208495 :       if (y[j]) s = addii(s, mulis(gcoeff(x,i,j),y[j]));
     133                 :   11505585 :     gel(z,i) = gerepileuptoint(av,s);
     134                 :            :   }
     135                 :    1491514 :   return z;
     136                 :            : }
     137                 :            : GEN
     138                 :    1378478 : ZM_zc_mul(GEN x, GEN y) {
     139                 :    1378478 :   long l = lg(x);
     140         [ -  + ]:    1378478 :   if (l == 1) return cgetg(1, t_COL);
     141                 :    1378478 :   return ZM_zc_mul_i(x,y, l, lgcols(x));
     142                 :            : }
     143                 :            : 
     144                 :            : /* x ZM, y a compatible zm (dimension > 0). */
     145                 :            : GEN
     146                 :      44702 : ZM_zm_mul(GEN x, GEN y)
     147                 :            : {
     148                 :      44702 :   long j, c, l = lg(x), ly = lg(y);
     149                 :      44702 :   GEN z = cgetg(ly, t_MAT);
     150         [ -  + ]:      44702 :   if (l == 1) return z;
     151                 :      44702 :   c = lgcols(x);
     152         [ +  + ]:     157738 :   for (j = 1; j < ly; j++) gel(z,j) = ZM_zc_mul_i(x, gel(y,j), l,c);
     153                 :      44702 :   return z;
     154                 :            : }
     155                 :            : /* x ZM, y a compatible zn (dimension > 0). */
     156                 :            : GEN
     157                 :        282 : ZM_nm_mul(GEN x, GEN y)
     158                 :            : {
     159                 :        282 :   long j, c, l = lg(x), ly = lg(y);
     160                 :        282 :   GEN z = cgetg(ly, t_MAT);
     161         [ -  + ]:        282 :   if (l == 1) return z;
     162                 :        282 :   c = lgcols(x);
     163         [ +  + ]:       4031 :   for (j = 1; j < ly; j++) gel(z,j) = ZM_nc_mul_i(x, gel(y,j), l,c);
     164                 :        282 :   return z;
     165                 :            : }
     166                 :            : 
     167                 :            : /* Strassen-Winograd algorithm */
     168                 :            : 
     169                 :            : /*
     170                 :            :   Return A[ma+1..ma+da, na+1..na+ea] - B[mb+1..mb+db, nb+1..nb+eb]
     171                 :            :   as an (m x n)-matrix, padding the input with zeroes as necessary.
     172                 :            : */
     173                 :            : static GEN
     174                 :      78512 : add_slices(long m, long n,
     175                 :            :            GEN A, long ma, long da, long na, long ea,
     176                 :            :            GEN B, long mb, long db, long nb, long eb)
     177                 :            : {
     178                 :      78512 :   long min_d = minss(da, db), min_e = minss(ea, eb), i, j;
     179                 :      78512 :   GEN M = cgetg(n + 1, t_MAT), C;
     180                 :            : 
     181         [ +  + ]:    2091838 :   for (j = 1; j <= min_e; j++) {
     182                 :    2013326 :     gel(M, j) = C = cgetg(m + 1, t_COL);
     183         [ +  + ]:   56458591 :     for (i = 1; i <= min_d; i++)
     184                 :   54445265 :       gel(C, i) = addii(gcoeff(A, ma + i, na + j),
     185                 :   54445265 :                         gcoeff(B, mb + i, nb + j));
     186         [ +  + ]:    2041452 :     for (; i <= da; i++)
     187                 :      28126 :       gel(C, i) = gcoeff(A, ma + i, na + j);
     188         [ -  + ]:    2013326 :     for (; i <= db; i++)
     189                 :          0 :       gel(C, i) = gcoeff(B, mb + i, nb + j);
     190         [ -  + ]:    2013326 :     for (; i <= m; i++)
     191                 :          0 :       gel(C, i) = gen_0;
     192                 :            :   }
     193         [ +  + ]:      80871 :   for (; j <= ea; j++) {
     194                 :       2359 :     gel(M, j) = C = cgetg(m + 1, t_COL);
     195         [ +  + ]:      70210 :     for (i = 1; i <= da; i++)
     196                 :      67851 :       gel(C, i) = gcoeff(A, ma + i, na + j);
     197         [ -  + ]:       2359 :     for (; i <= m; i++)
     198                 :          0 :       gel(C, i) = gen_0;
     199                 :            :   }
     200         [ -  + ]:      78512 :   for (; j <= eb; j++) {
     201                 :          0 :     gel(M, j) = C = cgetg(m + 1, t_COL);
     202         [ #  # ]:          0 :     for (i = 1; i <= db; i++)
     203                 :          0 :       gel(C, i) = gcoeff(B, mb + i, nb + j);
     204         [ #  # ]:          0 :     for (; i <= m; i++)
     205                 :          0 :       gel(C, i) = gen_0;
     206                 :            :   }
     207         [ -  + ]:      78512 :   for (; j <= n; j++)
     208                 :          0 :     gel(M, j) = zerocol(m);
     209                 :      78512 :   return M;
     210                 :            : }
     211                 :            : 
     212                 :            : /*
     213                 :            :   Return A[ma+1..ma+da, na+1..na+ea] - B[mb+1..mb+db, nb+1..nb+eb]
     214                 :            :   as an (m x n)-matrix, padding the input with zeroes as necessary.
     215                 :            : */
     216                 :            : static GEN
     217                 :      68698 : subtract_slices(long m, long n,
     218                 :            :                 GEN A, long ma, long da, long na, long ea,
     219                 :            :                 GEN B, long mb, long db, long nb, long eb)
     220                 :            : {
     221                 :      68698 :   long min_d = minss(da, db), min_e = minss(ea, eb), i, j;
     222                 :      68698 :   GEN M = cgetg(n + 1, t_MAT), C;
     223                 :            : 
     224         [ +  + ]:    1866725 :   for (j = 1; j <= min_e; j++) {
     225                 :    1798027 :     gel(M, j) = C = cgetg(m + 1, t_COL);
     226         [ +  + ]:   53858154 :     for (i = 1; i <= min_d; i++)
     227                 :   52060127 :       gel(C, i) = subii(gcoeff(A, ma + i, na + j),
     228                 :   52060127 :                         gcoeff(B, mb + i, nb + j));
     229         [ +  + ]:    1837948 :     for (; i <= da; i++)
     230                 :      39921 :       gel(C, i) = gcoeff(A, ma + i, na + j);
     231         [ +  + ]:    1834574 :     for (; i <= db; i++)
     232                 :      36547 :       gel(C, i) = negi(gcoeff(B, mb + i, nb + j));
     233         [ -  + ]:    1798027 :     for (; i <= m; i++)
     234                 :          0 :       gel(C, i) = gen_0;
     235                 :            :   }
     236         [ -  + ]:      68698 :   for (; j <= ea; j++) {
     237                 :          0 :     gel(M, j) = C = cgetg(m + 1, t_COL);
     238         [ #  # ]:          0 :     for (i = 1; i <= da; i++)
     239                 :          0 :       gel(C, i) = gcoeff(A, ma + i, na + j);
     240         [ #  # ]:          0 :     for (; i <= m; i++)
     241                 :          0 :       gel(C, i) = gen_0;
     242                 :            :   }
     243         [ +  + ]:      69832 :   for (; j <= eb; j++) {
     244                 :       1134 :     gel(M, j) = C = cgetg(m + 1, t_COL);
     245         [ +  + ]:      44464 :     for (i = 1; i <= db; i++)
     246                 :      43330 :       gel(C, i) = negi(gcoeff(B, mb + i, nb + j));
     247         [ -  + ]:       1134 :     for (; i <= m; i++)
     248                 :          0 :       gel(C, i) = gen_0;
     249                 :            :   }
     250         [ +  + ]:      69832 :   for (; j <= n; j++)
     251                 :       1134 :     gel(M, j) = zerocol(m);
     252                 :      68698 :   return M;
     253                 :            : }
     254                 :            : 
     255                 :            : static GEN ZM_mul_i(GEN x, GEN y, long l, long lx, long ly);
     256                 :            : 
     257                 :            : /* Strassen-Winograd matrix product A (m x n) * B (n x p) */
     258                 :            : static GEN
     259                 :       9814 : ZM_mul_sw(GEN A, GEN B, long m, long n, long p)
     260                 :            : {
     261                 :       9814 :   pari_sp av = avma;
     262                 :       9814 :   long m1 = (m + 1)/2, m2 = m/2,
     263                 :       9814 :     n1 = (n + 1)/2, n2 = n/2,
     264                 :       9814 :     p1 = (p + 1)/2, p2 = p/2;
     265                 :            :   GEN A11, A12, A22, B11, B21, B22,
     266                 :            :     S1, S2, S3, S4, T1, T2, T3, T4,
     267                 :            :     M1, M2, M3, M4, M5, M6, M7,
     268                 :            :     V1, V2, V3, C11, C12, C21, C22, C;
     269                 :            : 
     270                 :       9814 :   T2 = subtract_slices(n1, p2, B, 0, n1, p1, p2, B, n1, n2, p1, p2);
     271                 :       9814 :   S1 = subtract_slices(m2, n1, A, m1, m2, 0, n1, A, 0, m2, 0, n1);
     272                 :       9814 :   M2 = ZM_mul_i(S1, T2, m2 + 1, n1 + 1, p2 + 1);
     273         [ -  + ]:       9814 :   if (gc_needed(av, 1))
     274                 :          0 :     gerepileall(av, 2, &T2, &M2);  /* destroy S1 */
     275                 :       9814 :   T3 = subtract_slices(n1, p1, T2, 0, n1, 0, p2, B, 0, n1, 0, p1);
     276         [ -  + ]:       9814 :   if (gc_needed(av, 1))
     277                 :          0 :     gerepileall(av, 2, &M2, &T3);  /* destroy T2 */
     278                 :       9814 :   S2 = add_slices(m2, n1, A, m1, m2, 0, n1, A, m1, m2, n1, n2);
     279                 :       9814 :   T1 = subtract_slices(n1, p1, B, 0, n1, p1, p2, B, 0, n1, 0, p2);
     280                 :       9814 :   M3 = ZM_mul_i(S2, T1, m2 + 1, n1 + 1, p2 + 1);
     281         [ -  + ]:       9814 :   if (gc_needed(av, 1))
     282                 :          0 :     gerepileall(av, 4, &M2, &T3, &S2, &M3);  /* destroy T1 */
     283                 :       9814 :   S3 = subtract_slices(m1, n1, S2, 0, m2, 0, n1, A, 0, m1, 0, n1);
     284         [ -  + ]:       9814 :   if (gc_needed(av, 1))
     285                 :          0 :     gerepileall(av, 4, &M2, &T3, &M3, &S3);  /* destroy S2 */
     286                 :       9814 :   A11 = matslice(A, 1, m1, 1, n1);
     287                 :       9814 :   B11 = matslice(B, 1, n1, 1, p1);
     288                 :       9814 :   M1 = ZM_mul_i(A11, B11, m1 + 1, n1 + 1, p1 + 1);
     289         [ -  + ]:       9814 :   if (gc_needed(av, 1))
     290                 :          0 :     gerepileall(av, 5, &M2, &T3, &M3, &S3, &M1);  /* destroy A11, B11 */
     291                 :       9814 :   A12 = matslice(A, 1, m1, n1 + 1, n);
     292                 :       9814 :   B21 = matslice(B, n1 + 1, n, 1, p1);
     293                 :       9814 :   M4 = ZM_mul_i(A12, B21, m1 + 1, n2 + 1, p1 + 1);
     294         [ -  + ]:       9814 :   if (gc_needed(av, 1))
     295                 :          0 :     gerepileall(av, 6, &M2, &T3, &M3, &S3, &M1, &M4);  /* destroy A12, B21 */
     296                 :       9814 :   C11 = add_slices(m1, p1, M1, 0, m1, 0, p1, M4, 0, m1, 0, p1);
     297         [ -  + ]:       9814 :   if (gc_needed(av, 1))
     298                 :          0 :     gerepileall(av, 6, &M2, &T3, &M3, &S3, &M1, &C11);  /* destroy M4 */
     299                 :       9814 :   M5 = ZM_mul_i(S3, T3, m1 + 1, n1 + 1, p1 + 1);
     300                 :       9814 :   S4 = subtract_slices(m1, n2, A, 0, m1, n1, n2, S3, 0, m1, 0, n2);
     301         [ -  + ]:       9814 :   if (gc_needed(av, 1))
     302                 :          0 :     gerepileall(av, 7, &M2, &T3, &M3, &M1, &C11, &M5, &S4);  /* destroy S3 */
     303                 :       9814 :   T4 = add_slices(n2, p1, B, n1, n2, 0, p1, T3, 0, n2, 0, p1);
     304         [ -  + ]:       9814 :   if (gc_needed(av, 1))
     305                 :          0 :     gerepileall(av, 7, &M2, &M3, &M1, &C11, &M5, &S4, &T4);  /* destroy T3 */
     306                 :       9814 :   V1 = subtract_slices(m1, p1, M1, 0, m1, 0, p1, M5, 0, m1, 0, p1);
     307         [ -  + ]:       9814 :   if (gc_needed(av, 1))
     308                 :          0 :     gerepileall(av, 6, &M2, &M3, &S4, &T4, &C11, &V1);  /* destroy M1, M5 */
     309                 :       9814 :   B22 = matslice(B, n1 + 1, n, p1 + 1, p);
     310                 :       9814 :   M6 = ZM_mul_i(S4, B22, m1 + 1, n2 + 1, p2 + 1);
     311         [ -  + ]:       9814 :   if (gc_needed(av, 1))
     312                 :          0 :     gerepileall(av, 6, &M2, &M3, &T4, &C11, &V1, &M6);  /* destroy S4, B22 */
     313                 :       9814 :   A22 = matslice(A, m1 + 1, m, n1 + 1, n);
     314                 :       9814 :   M7 = ZM_mul_i(A22, T4, m2 + 1, n2 + 1, p1 + 1);
     315         [ -  + ]:       9814 :   if (gc_needed(av, 1))
     316                 :          0 :     gerepileall(av, 6, &M2, &M3, &C11, &V1, &M6, &M7);  /* destroy A22, T4 */
     317                 :       9814 :   V3 = add_slices(m1, p2, V1, 0, m1, 0, p2, M3, 0, m2, 0, p2);
     318                 :       9814 :   C12 = add_slices(m1, p2, V3, 0, m1, 0, p2, M6, 0, m1, 0, p2);
     319         [ -  + ]:       9814 :   if (gc_needed(av, 1))
     320                 :          0 :     gerepileall(av, 6, &M2, &M3, &C11, &V1, &M7, &C12);  /* destroy V3, M6 */
     321                 :       9814 :   V2 = add_slices(m2, p1, V1, 0, m2, 0, p1, M2, 0, m2, 0, p2);
     322         [ -  + ]:       9814 :   if (gc_needed(av, 1))
     323                 :          0 :     gerepileall(av, 5, &M3, &C11, &M7, &C12, &V2);  /* destroy V1, M2 */
     324                 :       9814 :   C21 = add_slices(m2, p1, V2, 0, m2, 0, p1, M7, 0, m2, 0, p1);
     325         [ -  + ]:       9814 :   if (gc_needed(av, 1))
     326                 :          0 :     gerepileall(av, 5, &M3, &C11, &C12, &V2, &C21);  /* destroy M7 */
     327                 :       9814 :   C22 = add_slices(m2, p2, V2, 0, m2, 0, p2, M3, 0, m2, 0, p2);
     328         [ -  + ]:       9814 :   if (gc_needed(av, 1))
     329                 :          0 :     gerepileall(av, 4, &C11, &C12, &C21, &C22);  /* destroy V2, M3 */
     330                 :       9814 :   C = mkmat2(mkcol2(C11, C21), mkcol2(C12, C22));
     331                 :       9814 :   return gerepileupto(av, matconcat(C));
     332                 :            : }
     333                 :            : 
     334                 :            : /* x[i,]*y. Assume lg(x) > 1 and 0 < i < lgcols(x) */
     335                 :            : static GEN
     336                 :  119847881 : ZMrow_ZC_mul_i(GEN x, GEN y, long i, long lx)
     337                 :            : {
     338                 :  119847881 :   pari_sp av = avma;
     339                 :  119847881 :   GEN c = mulii(gcoeff(x,i,1), gel(y,1)), ZERO = gen_0;
     340                 :            :   long k;
     341         [ +  + ]: 2100917964 :   for (k = 2; k < lx; k++)
     342                 :            :   {
     343                 : 1981070083 :     GEN t = mulii(gcoeff(x,i,k), gel(y,k));
     344         [ +  + ]: 1981070083 :     if (t != ZERO) c = addii(c, t);
     345                 :            :   }
     346                 :  119847881 :   return gerepileuptoint(av, c);
     347                 :            : }
     348                 :            : GEN
     349                 :   20687874 : ZMrow_ZC_mul(GEN x, GEN y, long i)
     350                 :   20687874 : { return ZMrow_ZC_mul_i(x, y, i, lg(x)); }
     351                 :            : 
     352                 :            : /* return x * y, 1 < lx = lg(x), l = lgcols(x) */
     353                 :            : static GEN
     354                 :   12080631 : ZM_ZC_mul_i(GEN x, GEN y, long lx, long l)
     355                 :            : {
     356                 :   12080631 :   GEN z = cgetg(l,t_COL);
     357                 :            :   long i;
     358         [ +  + ]:  111240638 :   for (i=1; i<l; i++) gel(z,i) = ZMrow_ZC_mul_i(x,y,i,lx);
     359                 :   12080631 :   return z;
     360                 :            : }
     361                 :            : 
     362                 :            : static GEN
     363                 :    1616421 : ZM_mul_classical(GEN x, GEN y, long l, long lx, long ly)
     364                 :            : {
     365                 :            :   long j;
     366                 :    1616421 :   GEN z = cgetg(ly, t_MAT);
     367         [ +  + ]:   10030057 :   for (j = 1; j < ly; j++)
     368                 :    8413636 :     gel(z, j) = ZM_ZC_mul_i(x, gel(y, j), lx, l);
     369                 :    1616421 :   return z;
     370                 :            : }
     371                 :            : 
     372                 :            : /* Strassen-Winograd used for dim >= ZM_sw_bound */
     373                 :            : static const long ZM_sw_bound = 36;
     374                 :            : 
     375                 :            : static GEN
     376                 :    1593349 : ZM_mul_i(GEN x, GEN y, long l, long lx, long ly)
     377                 :            : {
     378 [ +  + ][ +  + ]:    1593349 :   if (l <= ZM_sw_bound || lx <= ZM_sw_bound || ly <= ZM_sw_bound)
                 [ +  + ]
     379                 :    1583535 :     return ZM_mul_classical(x, y, l, lx, ly);
     380                 :            :   else
     381                 :    1593349 :     return ZM_mul_sw(x, y, l - 1, lx - 1, ly - 1);
     382                 :            : }
     383                 :            : 
     384                 :            : GEN
     385                 :    1527052 : ZM_mul(GEN x, GEN y)
     386                 :            : {
     387                 :    1527052 :   long lx=lg(x), ly=lg(y);
     388         [ +  + ]:    1527052 :   if (ly==1) return cgetg(1,t_MAT);
     389         [ +  + ]:    1524770 :   if (lx==1) return zeromat(0, ly-1);
     390                 :    1527052 :   return ZM_mul_i(x, y, lgcols(x), lx, ly);
     391                 :            : }
     392                 :            : /* assume result is symmetric */
     393                 :            : GEN
     394                 :          0 : ZM_multosym(GEN x, GEN y)
     395                 :            : {
     396                 :          0 :   long j, lx, ly = lg(y);
     397                 :            :   GEN M;
     398         [ #  # ]:          0 :   if (ly == 1) return cgetg(1,t_MAT);
     399                 :          0 :   lx = lg(x); /* = lgcols(y) */
     400         [ #  # ]:          0 :   if (lx == 1) return cgetg(1,t_MAT);
     401                 :            :   /* ly = lgcols(x) */
     402                 :          0 :   M = cgetg(ly, t_MAT);
     403         [ #  # ]:          0 :   for (j=1; j<ly; j++)
     404                 :            :   {
     405                 :          0 :     GEN z = cgetg(ly,t_COL), yj = gel(y,j);
     406                 :            :     long i;
     407         [ #  # ]:          0 :     for (i=1; i<j; i++) gel(z,i) = gcoeff(M,j,i);
     408         [ #  # ]:          0 :     for (i=j; i<ly; i++)gel(z,i) = ZMrow_ZC_mul_i(x,yj,i,lx);
     409                 :          0 :     gel(M,j) = z;
     410                 :            :   }
     411                 :          0 :   return M;
     412                 :            : }
     413                 :            : 
     414                 :            : /* assume lx > 1 is lg(x) = lg(y) */
     415                 :            : static GEN
     416                 :   11912234 : ZV_dotproduct_i(GEN x, GEN y, long lx)
     417                 :            : {
     418                 :   11912234 :   pari_sp av = avma;
     419                 :   11912234 :   GEN c = mulii(gel(x,1), gel(y,1));
     420                 :            :   long i;
     421         [ +  + ]:   95545882 :   for (i = 2; i < lx; i++)
     422                 :            :   {
     423                 :   83633648 :     GEN t = mulii(gel(x,i), gel(y,i));
     424         [ +  + ]:   83633648 :     if (t != gen_0) c = addii(c, t);
     425                 :            :   }
     426                 :   11912234 :   return gerepileuptoint(av, c);
     427                 :            : }
     428                 :            : 
     429                 :            : /* x~ * y, assuming result is symmetric */
     430                 :            : GEN
     431                 :     158361 : ZM_transmultosym(GEN x, GEN y)
     432                 :            : {
     433                 :     158361 :   long i, j, l, ly = lg(y);
     434                 :            :   GEN M;
     435         [ -  + ]:     158361 :   if (ly == 1) return cgetg(1,t_MAT);
     436                 :            :   /* lg(x) = ly */
     437                 :     158361 :   l = lgcols(y); /* = lgcols(x) */
     438                 :     158361 :   M = cgetg(ly, t_MAT);
     439         [ +  + ]:    1233480 :   for (i=1; i<ly; i++)
     440                 :            :   {
     441                 :    1075119 :     GEN xi = gel(x,i), c = cgetg(ly,t_COL);
     442                 :    1075119 :     gel(M,i) = c;
     443         [ +  + ]:    4786363 :     for (j=1; j<i; j++)
     444                 :    3711244 :       gcoeff(M,i,j) = gel(c,j) = ZV_dotproduct_i(xi,gel(y,j),l);
     445                 :    1075119 :     gel(c,i) = ZV_dotproduct_i(xi,gel(y,i),l);
     446                 :            :   }
     447                 :     158361 :   return M;
     448                 :            : }
     449                 :            : /* x~ * y */
     450                 :            : GEN
     451                 :        497 : ZM_transmul(GEN x, GEN y)
     452                 :            : {
     453                 :        497 :   long i, j, l, lx, ly = lg(y);
     454                 :            :   GEN M;
     455         [ -  + ]:        497 :   if (ly == 1) return cgetg(1,t_MAT);
     456                 :        497 :   lx = lg(x);
     457                 :        497 :   l = lgcols(y);
     458         [ -  + ]:        497 :   if (lgcols(x) != l) pari_err_OP("operation 'ZM_transmul'", x,y);
     459                 :        497 :   M = cgetg(ly, t_MAT);
     460         [ +  + ]:       1617 :   for (i=1; i<ly; i++)
     461                 :            :   {
     462                 :       1120 :     GEN yi = gel(y,i), c = cgetg(lx,t_COL);
     463                 :       1120 :     gel(M,i) = c;
     464         [ +  + ]:       5061 :     for (j=1; j<lx; j++) gel(c,j) = ZV_dotproduct_i(yi,gel(x,j),l);
     465                 :            :   }
     466                 :        497 :   return M;
     467                 :            : }
     468                 :            : 
     469                 :            : static GEN
     470                 :      32886 : ZM_sqr_i(GEN x, long l)
     471                 :            : {
     472         [ +  - ]:      32886 :   if (l <= ZM_sw_bound)
     473                 :      32886 :     return ZM_mul_classical(x, x, l, l, l);
     474                 :            :   else
     475                 :      32886 :     return ZM_mul_sw(x, x, l - 1, l - 1, l - 1);
     476                 :            : }
     477                 :            : 
     478                 :            : GEN
     479                 :      32886 : ZM_sqr(GEN x)
     480                 :            : {
     481                 :      32886 :   long lx=lg(x);
     482         [ -  + ]:      32886 :   if (lx==1) return cgetg(1,t_MAT);
     483                 :      32886 :   return ZM_sqr_i(x, lx);
     484                 :            : }
     485                 :            : GEN
     486                 :    3695031 : ZM_ZC_mul(GEN x, GEN y)
     487                 :            : {
     488                 :    3695031 :   long lx = lg(x);
     489         [ +  + ]:    3695031 :   return lx==1? cgetg(1,t_COL): ZM_ZC_mul_i(x, y, lx, lgcols(x));
     490                 :            : }
     491                 :            : 
     492                 :            : GEN
     493                 :       1883 : ZM_Z_div(GEN X, GEN c)
     494                 :            : {
     495                 :       1883 :   long i, j, h, l = lg(X);
     496                 :       1883 :   GEN A = cgetg(l, t_MAT);
     497         [ -  + ]:       1883 :   if (l == 1) return A;
     498                 :       1883 :   h = lgcols(X);
     499         [ +  + ]:      29967 :   for (j=1; j<l; j++)
     500                 :            :   {
     501                 :      28084 :     GEN a = cgetg(h, t_COL), x = gel(X, j);
     502         [ +  + ]:     719376 :     for (i = 1; i < h; i++) gel(a,i) = gred_frac2(gel(x,i), c);
     503                 :      28084 :     gel(A,j) = a;
     504                 :            :   }
     505                 :       1883 :   return A;
     506                 :            : }
     507                 :            : 
     508                 :            : long
     509                 :  125500697 : zv_dotproduct(GEN x, GEN y)
     510                 :            : {
     511                 :  125500697 :   long i, lx = lg(x);
     512                 :            :   ulong c;
     513         [ -  + ]:  125500697 :   if (lx == 1) return 0;
     514                 :  125500697 :   c = uel(x,1)*uel(y,1);
     515         [ +  + ]: 1947333227 :   for (i = 2; i < lx; i++)
     516                 : 1821832530 :     c += uel(x,i)*uel(y,i);
     517                 :  125500697 :   return c;
     518                 :            : }
     519                 :            : 
     520                 :            : GEN
     521                 :       3318 : ZV_ZM_mul(GEN x, GEN y)
     522                 :            : {
     523                 :       3318 :   long i, lx = lg(x), ly = lg(y);
     524                 :            :   GEN z;
     525         [ -  + ]:       3318 :   if (lx == 1) return zerovec(ly-1);
     526                 :       3318 :   z = cgetg(ly, t_VEC);
     527         [ +  + ]:      10129 :   for (i = 1; i < ly; i++) gel(z,i) = ZV_dotproduct_i(x, gel(y,i), lx);
     528                 :       3318 :   return z;
     529                 :            : }
     530                 :            : 
     531                 :            : GEN
     532                 :          0 : ZC_ZV_mul(GEN x, GEN y)
     533                 :            : {
     534                 :          0 :   long i,j, lx=lg(x), ly=lg(y);
     535                 :            :   GEN z;
     536         [ #  # ]:          0 :   if (ly==1) return cgetg(1,t_MAT);
     537                 :          0 :   z = cgetg(ly,t_MAT);
     538         [ #  # ]:          0 :   for (j=1; j < ly; j++)
     539                 :            :   {
     540                 :          0 :     gel(z,j) = cgetg(lx,t_COL);
     541         [ #  # ]:          0 :     for (i=1; i<lx; i++) gcoeff(z,i,j) = mulii(gel(x,i),gel(y,j));
     542                 :            :   }
     543                 :          0 :   return z;
     544                 :            : }
     545                 :            : 
     546                 :            : GEN
     547                 :    4044084 : ZV_dotsquare(GEN x)
     548                 :            : {
     549                 :            :   long i, lx;
     550                 :            :   pari_sp av;
     551                 :            :   GEN z;
     552                 :    4044084 :   lx = lg(x);
     553         [ -  + ]:    4044084 :   if (lx == 1) return gen_0;
     554                 :    4044084 :   av = avma; z = sqri(gel(x,1));
     555         [ +  + ]:   16097255 :   for (i=2; i<lx; i++) z = addii(z, sqri(gel(x,i)));
     556                 :    4044084 :   return gerepileuptoint(av,z);
     557                 :            : }
     558                 :            : 
     559                 :            : GEN
     560                 :   10046429 : ZV_dotproduct(GEN x,GEN y)
     561                 :            : {
     562                 :            :   long lx;
     563         [ +  + ]:   10046429 :   if (x == y) return ZV_dotsquare(x);
     564                 :    7115119 :   lx = lg(x);
     565         [ -  + ]:    7115119 :   if (lx == 1) return gen_0;
     566                 :   10046429 :   return ZV_dotproduct_i(x, y, lx);
     567                 :            : }
     568                 :            : 
     569                 :            : static GEN
     570                 :        217 : _ZM_mul(void *data /*ignored*/, GEN x, GEN y)
     571                 :        217 : { (void)data; return ZM_mul(x,y); }
     572                 :            : static GEN
     573                 :      32795 : _ZM_sqr(void *data /*ignored*/, GEN x)
     574                 :      32795 : { (void)data; return ZM_sqr(x); }
     575                 :            : GEN
     576                 :          0 : ZM_pow(GEN x, GEN n)
     577                 :            : {
     578                 :          0 :   pari_sp av = avma;
     579         [ #  # ]:          0 :   if (!signe(n)) return matid(lg(x)-1);
     580                 :          0 :   return gerepileupto(av, gen_pow(x, n, NULL, &_ZM_sqr, &_ZM_mul));
     581                 :            : }
     582                 :            : GEN
     583                 :      31339 : ZM_powu(GEN x, ulong n)
     584                 :            : {
     585                 :      31339 :   pari_sp av = avma;
     586         [ -  + ]:      31339 :   if (!n) return matid(lg(x)-1);
     587                 :      31339 :   return gerepileupto(av, gen_powu(x, n, NULL, &_ZM_sqr, &_ZM_mul));
     588                 :            : }
     589                 :            : /********************************************************************/
     590                 :            : /**                                                                **/
     591                 :            : /**                           ADD, SUB                             **/
     592                 :            : /**                                                                **/
     593                 :            : /********************************************************************/
     594                 :            : static GEN
     595                 :    1818776 : ZC_add_i(GEN x, GEN y, long lx)
     596                 :            : {
     597                 :    1818776 :   GEN A = cgetg(lx, t_COL);
     598                 :            :   long i;
     599         [ +  + ]:   36994511 :   for (i=1; i<lx; i++) gel(A,i) = addii(gel(x,i), gel(y,i));
     600                 :    1818776 :   return A;
     601                 :            : }
     602                 :            : GEN
     603                 :    1034412 : ZC_add(GEN x, GEN y) { return ZC_add_i(x, y, lg(x)); }
     604                 :            : GEN
     605                 :      69811 : ZC_Z_add(GEN x, GEN y)
     606                 :            : {
     607                 :      69811 :   long k, lx = lg(x);
     608                 :      69811 :   GEN z = cgetg(lx, t_COL);
     609         [ -  + ]:      69811 :   if (lx == 1) pari_err_TYPE2("+",x,y);
     610                 :      69811 :   gel(z,1) = addii(y,gel(x,1));
     611         [ +  + ]:     883995 :   for (k = 2; k < lx; k++) gel(z,k) = icopy(gel(x,k));
     612                 :      69811 :   return z;
     613                 :            : }
     614                 :            : 
     615                 :            : static GEN
     616                 :    1071498 : ZC_sub_i(GEN x, GEN y, long lx)
     617                 :            : {
     618                 :            :   long i;
     619                 :    1071498 :   GEN A = cgetg(lx, t_COL);
     620         [ +  + ]:    7030376 :   for (i=1; i<lx; i++) gel(A,i) = subii(gel(x,i), gel(y,i));
     621                 :    1071498 :   return A;
     622                 :            : }
     623                 :            : GEN
     624                 :    1019001 : ZC_sub(GEN x, GEN y) { return ZC_sub_i(x, y, lg(x)); }
     625                 :            : GEN
     626                 :          0 : ZC_Z_sub(GEN x, GEN y)
     627                 :            : {
     628                 :          0 :   long k, lx = lg(x);
     629                 :          0 :   GEN z = cgetg(lx, t_COL);
     630         [ #  # ]:          0 :   if (lx == 1) pari_err_TYPE2("+",x,y);
     631                 :          0 :   gel(z,1) = subii(gel(x,1), y);
     632         [ #  # ]:          0 :   for (k = 2; k < lx; k++) gel(z,k) = icopy(gel(x,k));
     633                 :          0 :   return z;
     634                 :            : }
     635                 :            : 
     636                 :            : GEN
     637                 :      37021 : ZM_add(GEN x, GEN y)
     638                 :            : {
     639                 :      37021 :   long lx = lg(x), l, j;
     640                 :            :   GEN z;
     641         [ +  + ]:      37021 :   if (lx == 1) return cgetg(1, t_MAT);
     642                 :      35719 :   z = cgetg(lx, t_MAT); l = lgcols(x);
     643         [ +  + ]:     820083 :   for (j = 1; j < lx; j++) gel(z,j) = ZC_add_i(gel(x,j), gel(y,j), l);
     644                 :      37021 :   return z;
     645                 :            : }
     646                 :            : GEN
     647                 :      10628 : ZM_sub(GEN x, GEN y)
     648                 :            : {
     649                 :      10628 :   long lx = lg(x), l, j;
     650                 :            :   GEN z;
     651         [ -  + ]:      10628 :   if (lx == 1) return cgetg(1, t_MAT);
     652                 :      10628 :   z = cgetg(lx, t_MAT); l = lgcols(x);
     653         [ +  + ]:      63125 :   for (j = 1; j < lx; j++) gel(z,j) = ZC_sub_i(gel(x,j), gel(y,j), l);
     654                 :      10628 :   return z;
     655                 :            : }
     656                 :            : /********************************************************************/
     657                 :            : /**                                                                **/
     658                 :            : /**                         LINEAR COMBINATION                     **/
     659                 :            : /**                                                                **/
     660                 :            : /********************************************************************/
     661                 :            : /* return X/c assuming division is exact */
     662                 :            : GEN
     663                 :    1417455 : ZC_Z_divexact(GEN X, GEN c)
     664                 :            : {
     665                 :    1417455 :   long i, l = lg(X);
     666                 :    1417455 :   GEN A = cgetg(l, t_COL);
     667         [ +  + ]:   46050138 :   for (i=1; i<l; i++) gel(A,i) = diviiexact(gel(X,i), c);
     668                 :    1417455 :   return A;
     669                 :            : }
     670                 :            : GEN
     671                 :      76988 : ZM_Z_divexact(GEN X, GEN c)
     672                 :            : {
     673                 :      76988 :   long i, l = lg(X);
     674                 :      76988 :   GEN A = cgetg(l, t_MAT);
     675         [ +  + ]:    1341227 :   for (i = 1; i < l; i++) gel(A,i) = ZC_Z_divexact(gel(X,i), c);
     676                 :      76988 :   return A;
     677                 :            : }
     678                 :            : /* Return c * X */
     679                 :            : GEN
     680                 :    2450360 : ZC_Z_mul(GEN X, GEN c)
     681                 :            : {
     682                 :            :   long i, l;
     683                 :            :   GEN A;
     684         [ +  + ]:    2450360 :   if (!signe(c)) return zerocol(lg(X)-1);
     685 [ +  + ][ +  + ]:    2428093 :   if (is_pm1(c)) return (signe(c) > 0)? ZC_copy(X): ZC_neg(X);
     686                 :    2353976 :   l = lg(X); A = cgetg(l, t_COL);
     687         [ +  + ]:   14359815 :   for (i=1; i<l; i++) gel(A,i) = mulii(c,gel(X,i));
     688                 :    2450360 :   return A;
     689                 :            : }
     690                 :            : GEN
     691                 :      13153 : ZC_z_mul(GEN X, long c)
     692                 :            : {
     693                 :            :   long i, l;
     694                 :            :   GEN A;
     695         [ +  + ]:      13153 :   if (!c) return zerocol(lg(X)-1);
     696         [ +  + ]:       6664 :   if (c == 1) return ZC_copy(X);
     697         [ +  + ]:       2191 :   if (c ==-1) return ZC_neg(X);
     698                 :        728 :   l = lg(X); A = cgetg(l, t_COL);
     699         [ +  + ]:       2198 :   for (i=1; i<l; i++) gel(A,i) = mulsi(c,gel(X,i));
     700                 :      13153 :   return A;
     701                 :            : }
     702                 :            : 
     703                 :            : GEN
     704                 :       4360 : zv_z_mul(GEN M, long n)
     705                 :            : {
     706                 :            :   long l;
     707                 :       4360 :   GEN N = cgetg_copy(M, &l);
     708         [ +  + ]:      18156 :   while (--l > 0) N[l] = M[l]*n;
     709                 :       4360 :   return N;
     710                 :            : }
     711                 :            : 
     712                 :            : /* return a ZM */
     713                 :            : GEN
     714                 :        282 : nm_Z_mul(GEN X, GEN c)
     715                 :            : {
     716                 :        282 :   long i, j, h, l = lg(X), s = signe(c);
     717                 :            :   GEN A;
     718         [ -  + ]:        282 :   if (l == 1) return cgetg(1, t_MAT);
     719                 :        282 :   h = lgcols(X);
     720         [ -  + ]:        282 :   if (!s) return zeromat(h-1, l-1);
     721         [ -  + ]:        282 :   if (is_pm1(c)) {
     722         [ #  # ]:          0 :     if (s > 0) return Flm_to_ZM(X);
     723                 :          0 :     X = Flm_to_ZM(X); ZM_togglesign(X); return X;
     724                 :            :   }
     725                 :        282 :   A = cgetg(l, t_MAT);
     726         [ +  + ]:       4031 :   for (j = 1; j < l; j++)
     727                 :            :   {
     728                 :       3749 :     GEN a = cgetg(h, t_COL), x = gel(X, j);
     729         [ +  + ]:      77015 :     for (i = 1; i < h; i++) gel(a,i) = muliu(c, x[i]);
     730                 :       3749 :     gel(A,j) = a;
     731                 :            :   }
     732                 :        282 :   return A;
     733                 :            : }
     734                 :            : GEN
     735                 :      62185 : ZM_Z_mul(GEN X, GEN c)
     736                 :            : {
     737                 :      62185 :   long i, j, h, l = lg(X);
     738                 :            :   GEN A;
     739         [ -  + ]:      62185 :   if (l == 1) return cgetg(1, t_MAT);
     740                 :      62185 :   h = lgcols(X);
     741         [ +  + ]:      62185 :   if (!signe(c)) return zeromat(h-1, l-1);
     742 [ +  + ][ +  + ]:      62122 :   if (is_pm1(c)) return (signe(c) > 0)? ZM_copy(X): ZM_neg(X);
     743                 :      45749 :   A = cgetg(l, t_MAT);
     744         [ +  + ]:     684542 :   for (j = 1; j < l; j++)
     745                 :            :   {
     746                 :     638793 :     GEN a = cgetg(h, t_COL), x = gel(X, j);
     747         [ +  + ]:   22271795 :     for (i = 1; i < h; i++) gel(a,i) = mulii(c, gel(x,i));
     748                 :     638793 :     gel(A,j) = a;
     749                 :            :   }
     750                 :      62185 :   return A;
     751                 :            : }
     752                 :            : 
     753                 :            : /* X <- X + v Y (elementary col operation) */
     754                 :            : void
     755                 :   35071755 : ZC_lincomb1_inplace(GEN X, GEN Y, GEN v)
     756                 :            : {
     757                 :   35071755 :   long i, m = lgefint(v);
     758         [ -  + ]:   70143510 :   if (m == 2) return; /* v = 0 */
     759         [ +  + ]:  762079284 :   for (i = lg(X)-1; i; i--) gel(X,i) = addmulii_inplace(gel(X,i), gel(Y,i), v);
     760                 :            : }
     761                 :            : void
     762                 :    7365973 : Flc_lincomb1_inplace(GEN X, GEN Y, ulong v, ulong q)
     763                 :            : {
     764                 :            :   long i;
     765         [ -  + ]:   14731946 :   if (!v) return; /* v = 0 */
     766         [ +  + ]:  261819377 :   for (i = lg(X)-1; i; i--) X[i] = Fl_add(X[i], Fl_mul(Y[i], v, q), q);
     767                 :            : }
     768                 :            : 
     769                 :            : /* X + v Y, wasteful if (v = 0) */
     770                 :            : static GEN
     771                 :    2351870 : ZC_lincomb1(GEN v, GEN X, GEN Y)
     772                 :            : {
     773                 :    2351870 :   long i, lx = lg(X);
     774                 :    2351870 :   GEN A = cgetg(lx,t_COL);
     775         [ +  + ]:   30038128 :   for (i=1; i<lx; i++) gel(A,i) = addmulii(gel(X,i), gel(Y,i), v);
     776                 :    2351870 :   return A;
     777                 :            : }
     778                 :            : /* -X + vY */
     779                 :            : static GEN
     780                 :     371015 : ZC_lincomb_1(GEN v, GEN X, GEN Y)
     781                 :            : {
     782                 :     371015 :   long i, lx = lg(X);
     783                 :     371015 :   GEN A = cgetg(lx,t_COL);
     784         [ +  + ]:    2096122 :   for (i=1; i<lx; i++) gel(A,i) = mulsubii(gel(Y,i), v, gel(X,i));
     785                 :     371015 :   return A;
     786                 :            : }
     787                 :            : /* X,Y compatible ZV; u,v in Z. Returns A = u*X + v*Y */
     788                 :            : GEN
     789                 :    7379846 : ZC_lincomb(GEN u, GEN v, GEN X, GEN Y)
     790                 :            : {
     791                 :            :   long su, sv;
     792                 :            :   GEN A;
     793                 :            : 
     794         [ -  + ]:    7379846 :   su = signe(u); if (!su) return ZC_Z_mul(Y, v);
     795         [ +  + ]:    7379846 :   sv = signe(v); if (!sv) return ZC_Z_mul(X, u);
     796         [ +  + ]:    7379832 :   if (is_pm1(v))
     797                 :            :   {
     798         [ +  + ]:    1641094 :     if (is_pm1(u))
     799                 :            :     {
     800         [ +  + ]:    1031048 :       if (su != sv) A = ZC_sub(X, Y);
     801                 :     458620 :       else          A = ZC_add(X, Y);
     802         [ +  + ]:    1031048 :       if (su < 0) ZV_togglesign(A); /* in place but was created above */
     803                 :            :     }
     804                 :            :     else
     805                 :            :     {
     806         [ +  + ]:     610046 :       if (sv > 0) A = ZC_lincomb1 (u, Y, X);
     807                 :     266670 :       else        A = ZC_lincomb_1(u, Y, X);
     808                 :            :     }
     809                 :            :   }
     810         [ +  + ]:    5738738 :   else if (is_pm1(u))
     811                 :            :   {
     812         [ +  + ]:    2112839 :     if (su > 0) A = ZC_lincomb1 (v, X, Y);
     813                 :     104345 :     else        A = ZC_lincomb_1(v, X, Y);
     814                 :            :   }
     815                 :            :   else
     816                 :            :   { /* not cgetg_copy: x may be a t_VEC */
     817                 :    3625899 :     long i, lx = lg(X);
     818                 :    3625899 :     A = cgetg(lx,t_COL);
     819         [ +  + ]:   21589381 :     for (i=1; i<lx; i++) gel(A,i) = lincombii(u,v,gel(X,i),gel(Y,i));
     820                 :            :   }
     821                 :    7379846 :   return A;
     822                 :            : }
     823                 :            : 
     824                 :            : /********************************************************************/
     825                 :            : /**                                                                **/
     826                 :            : /**                           CONVERSIONS                          **/
     827                 :            : /**                                                                **/
     828                 :            : /********************************************************************/
     829                 :            : GEN
     830                 :       1932 : ZV_to_nv(GEN z)
     831                 :            : {
     832                 :       1932 :   long i, l = lg(z);
     833                 :       1932 :   GEN x = cgetg(l, t_VECSMALL);
     834         [ +  + ]:       4347 :   for (i=1; i<l; i++) x[i] = itou(gel(z,i));
     835                 :       1932 :   return x;
     836                 :            : }
     837                 :            : 
     838                 :            : GEN
     839                 :      63903 : zm_to_ZM(GEN z)
     840                 :            : {
     841                 :      63903 :   long i, l = lg(z);
     842                 :      63903 :   GEN x = cgetg(l,t_MAT);
     843         [ +  + ]:     247807 :   for (i=1; i<l; i++) gel(x,i) = zc_to_ZC(gel(z,i));
     844                 :      63903 :   return x;
     845                 :            : }
     846                 :            : 
     847                 :            : GEN
     848                 :         63 : zmV_to_ZMV(GEN z)
     849                 :            : {
     850                 :         63 :   long i, l = lg(z);
     851                 :         63 :   GEN x = cgetg(l,t_VEC);
     852         [ +  + ]:        490 :   for (i=1; i<l; i++) gel(x,i) = zm_to_ZM(gel(z,i));
     853                 :         63 :   return x;
     854                 :            : }
     855                 :            : 
     856                 :            : /* same as Flm_to_ZM but do not assume positivity */
     857                 :            : GEN
     858                 :        238 : ZM_to_zm(GEN z)
     859                 :            : {
     860                 :        238 :   long i, l = lg(z);
     861                 :        238 :   GEN x = cgetg(l,t_MAT);
     862         [ +  + ]:     184548 :   for (i=1; i<l; i++) gel(x,i) = ZV_to_zv(gel(z,i));
     863                 :        238 :   return x;
     864                 :            : }
     865                 :            : 
     866                 :            : GEN
     867                 :     181720 : zv_to_Flv(GEN z, ulong p)
     868                 :            : {
     869                 :     181720 :   long i, l = lg(z);
     870                 :     181720 :   GEN x = cgetg(l,t_VECSMALL);
     871         [ +  + ]:    2877560 :   for (i=1; i<l; i++) x[i] = umodsu(z[i], p);
     872                 :     181720 :   return x;
     873                 :            : }
     874                 :            : 
     875                 :            : GEN
     876                 :      12460 : zm_to_Flm(GEN z, ulong p)
     877                 :            : {
     878                 :      12460 :   long i, l = lg(z);
     879                 :      12460 :   GEN x = cgetg(l,t_MAT);
     880         [ +  + ]:     194180 :   for (i=1; i<l; i++) gel(x,i) = zv_to_Flv(gel(z,i),p);
     881                 :      12460 :   return x;
     882                 :            : }
     883                 :            : 
     884                 :            : GEN
     885                 :          0 : ZMV_to_zmV(GEN z)
     886                 :            : {
     887                 :          0 :   long i,l = lg(z);
     888                 :          0 :   GEN x = cgetg(l, t_VEC);
     889         [ #  # ]:          0 :   for (i=1; i<l; i++) gel(x,i) = ZM_to_zm(gel(z,i));
     890                 :          0 :   return x;
     891                 :            : }
     892                 :            : 
     893                 :            : /********************************************************************/
     894                 :            : /**                                                                **/
     895                 :            : /**                         COPY, NEGATION                         **/
     896                 :            : /**                                                                **/
     897                 :            : /********************************************************************/
     898                 :            : GEN
     899                 :     630025 : ZC_copy(GEN x)
     900                 :            : {
     901                 :     630025 :   long i, lx = lg(x);
     902                 :     630025 :   GEN y = cgetg(lx, t_COL);
     903         [ +  + ]:    7922138 :   for (i=1; i<lx; i++)
     904                 :            :   {
     905                 :    7292113 :     GEN c = gel(x,i);
     906         [ +  + ]:    7292113 :     gel(y,i) = lgefint(c) == 2? gen_0: icopy(c);
     907                 :            :   }
     908                 :     630025 :   return y;
     909                 :            : }
     910                 :            : 
     911                 :            : GEN
     912                 :      41167 : ZM_copy(GEN x)
     913                 :            : {
     914                 :            :   long l;
     915                 :      41167 :   GEN y = cgetg_copy(x, &l);
     916         [ +  + ]:     450389 :   while (--l > 0) gel(y,l) = ZC_copy(gel(x,l));
     917                 :      41167 :   return y;
     918                 :            : }
     919                 :            : 
     920                 :            : void
     921                 :      57626 : ZV_neg_inplace(GEN M)
     922                 :            : {
     923                 :      57626 :   long l = lg(M);
     924         [ +  + ]:     437751 :   while (--l > 0) gel(M,l) = negi(gel(M,l));
     925                 :      57626 : }
     926                 :            : GEN
     927                 :    1239752 : ZC_neg(GEN M)
     928                 :            : {
     929                 :    1239752 :   long l = lg(M);
     930                 :    1239752 :   GEN N = cgetg(l, t_COL);
     931         [ +  + ]:    9944389 :   while (--l > 0) gel(N,l) = negi(gel(M,l));
     932                 :    1239752 :   return N;
     933                 :            : }
     934                 :            : GEN
     935                 :     187594 : zv_neg(GEN M)
     936                 :            : {
     937                 :            :   long l;
     938                 :     187594 :   GEN N = cgetg_copy(M, &l);
     939         [ +  + ]:    1593703 :   while (--l > 0) N[l] = -M[l];
     940                 :     187594 :   return N;
     941                 :            : }
     942                 :            : GEN
     943                 :        214 : zv_neg_inplace(GEN M)
     944                 :            : {
     945                 :        214 :   long l = lg(M);
     946         [ +  + ]:        840 :   while (--l > 0) M[l] = -M[l];
     947                 :        214 :   return M;
     948                 :            : }
     949                 :            : GEN
     950                 :       7357 : ZM_neg(GEN x)
     951                 :            : {
     952                 :            :   long l;
     953                 :       7357 :   GEN y = cgetg_copy(x, &l);
     954         [ +  + ]:      42714 :   while (--l > 0) gel(y,l) = ZC_neg(gel(x,l));
     955                 :       7357 :   return y;
     956                 :            : }
     957                 :            : 
     958                 :            : void
     959                 :     892884 : ZV_togglesign(GEN M)
     960                 :            : {
     961                 :     892884 :   long l = lg(M);
     962         [ +  + ]:   23917348 :   while (--l > 0) togglesign_safe(&gel(M,l));
     963                 :     892884 : }
     964                 :            : void
     965                 :          0 : ZM_togglesign(GEN M)
     966                 :            : {
     967                 :          0 :   long l = lg(M);
     968         [ #  # ]:          0 :   while (--l > 0) ZV_togglesign(gel(M,l));
     969                 :          0 : }
     970                 :            : 
     971                 :            : /********************************************************************/
     972                 :            : /**                                                                **/
     973                 :            : /**                        "DIVISION" mod HNF                      **/
     974                 :            : /**                                                                **/
     975                 :            : /********************************************************************/
     976                 :            : /* Reduce ZC x modulo ZM y in HNF, may return x itself (not a copy) */
     977                 :            : GEN
     978                 :     803839 : ZC_hnfremdiv(GEN x, GEN y, GEN *Q)
     979                 :            : {
     980                 :     803839 :   long i, l = lg(x);
     981                 :            :   GEN q;
     982                 :            : 
     983         [ +  + ]:     803839 :   if (Q) *Q = cgetg(l,t_COL);
     984         [ -  + ]:     803839 :   if (l == 1) return cgetg(1,t_COL);
     985         [ +  + ]:    4932412 :   for (i = l-1; i>0; i--)
     986                 :            :   {
     987                 :    4128573 :     q = diviiround(gel(x,i), gcoeff(y,i,i));
     988         [ +  + ]:    4128573 :     if (signe(q)) {
     989                 :    2303798 :       togglesign(q);
     990                 :    2303798 :       x = ZC_lincomb(gen_1, q, x, gel(y,i));
     991                 :            :     }
     992         [ +  + ]:    4128573 :     if (Q) gel(*Q, i) = q;
     993                 :            :   }
     994                 :     803839 :   return x;
     995                 :            : }
     996                 :            : 
     997                 :            : /* x = y Q + R, may return some columns of x (not copies) */
     998                 :            : GEN
     999                 :      29389 : ZM_hnfdivrem(GEN x, GEN y, GEN *Q)
    1000                 :            : {
    1001                 :      29389 :   long lx = lg(x), i;
    1002                 :      29389 :   GEN R = cgetg(lx, t_MAT);
    1003         [ +  + ]:      29389 :   if (Q)
    1004                 :            :   {
    1005                 :       3244 :     GEN q = cgetg(lx, t_MAT); *Q = q;
    1006         [ +  + ]:       6068 :     for (i=1; i<lx; i++) gel(R,i) = ZC_hnfremdiv(gel(x,i),y,(GEN*)(q+i));
    1007                 :            :   }
    1008                 :            :   else
    1009         [ +  + ]:      99596 :     for (i=1; i<lx; i++)
    1010                 :            :     {
    1011                 :      73451 :       pari_sp av = avma;
    1012                 :      73451 :       GEN z = ZC_hnfrem(gel(x,i),y);
    1013         [ +  + ]:      73451 :       gel(R,i) = (avma == av)? ZC_copy(z): gerepileupto(av, z);
    1014                 :            :     }
    1015                 :      29389 :   return R;
    1016                 :            : }
    1017                 :            : 
    1018                 :            : 
    1019                 :            : /********************************************************************/
    1020                 :            : /**                                                                **/
    1021                 :            : /**                               TESTS                            **/
    1022                 :            : /**                                                                **/
    1023                 :            : /********************************************************************/
    1024                 :            : int
    1025                 :   13929013 : zv_equal0(GEN V)
    1026                 :            : {
    1027                 :   13929013 :   long l = lg(V);
    1028         [ +  + ]:   22053528 :   while (--l > 0)
    1029         [ +  + ]:   17506839 :     if (V[l]) return 0;
    1030                 :   13929013 :   return 1;
    1031                 :            : }
    1032                 :            : 
    1033                 :            : int
    1034                 :     316769 : ZV_equal0(GEN V)
    1035                 :            : {
    1036                 :     316769 :   long l = lg(V);
    1037         [ +  + ]:    1381168 :   while (--l > 0)
    1038         [ +  + ]:    1307528 :     if (signe(gel(V,l))) return 0;
    1039                 :     316769 :   return 1;
    1040                 :            : }
    1041                 :            : 
    1042                 :            : static int
    1043                 :    8970301 : ZV_equal_lg(GEN V, GEN W, long l)
    1044                 :            : {
    1045         [ +  + ]:   16193161 :   while (--l > 0)
    1046         [ +  + ]:   14233283 :     if (!equalii(gel(V,l), gel(W,l))) return 0;
    1047                 :    8970301 :   return 1;
    1048                 :            : }
    1049                 :            : int
    1050                 :    7768101 : ZV_equal(GEN V, GEN W)
    1051                 :            : {
    1052                 :    7768101 :   long l = lg(V);
    1053         [ -  + ]:    7768101 :   if (lg(W) != l) return 0;
    1054                 :    7768101 :   return ZV_equal_lg(V, W, l);
    1055                 :            : }
    1056                 :            : int
    1057                 :     381934 : ZM_equal(GEN A, GEN B)
    1058                 :            : {
    1059                 :     381934 :   long i, m, l = lg(A);
    1060         [ +  + ]:     381934 :   if (lg(B) != l) return 0;
    1061         [ -  + ]:     381668 :   if (l == 1) return 1;
    1062                 :     381668 :   m = lgcols(A);
    1063         [ -  + ]:     381668 :   if (lgcols(B) != m) return 0;
    1064         [ +  + ]:    1540038 :   for (i = 1; i < l; i++)
    1065         [ +  + ]:    1202200 :     if (!ZV_equal_lg(gel(A,i), gel(B,i), m)) return 0;
    1066                 :     381934 :   return 1;
    1067                 :            : }
    1068                 :            : int
    1069                 :    3499222 : zv_equal(GEN V, GEN W)
    1070                 :            : {
    1071                 :    3499222 :   long l = lg(V);
    1072         [ +  + ]:    3499222 :   if (lg(W) != l) return 0;
    1073         [ +  + ]:   23898027 :   while (--l > 0)
    1074         [ +  + ]:   20792217 :     if (V[l] != W[l]) return 0;
    1075                 :    3499222 :   return 1;
    1076                 :            : }
    1077                 :            : 
    1078                 :            : int
    1079                 :        315 : zvV_equal(GEN V, GEN W)
    1080                 :            : {
    1081                 :        315 :   long l = lg(V);
    1082         [ +  + ]:        315 :   if (lg(W) != l) return 0;
    1083         [ +  + ]:      58352 :   while (--l > 0)
    1084         [ +  + ]:      58170 :     if (!zv_equal(gel(V,l),gel(W,l))) return 0;
    1085                 :        315 :   return 1;
    1086                 :            : }
    1087                 :            : 
    1088                 :            : int
    1089                 :      52127 : ZM_ishnf(GEN x)
    1090                 :            : {
    1091                 :      52127 :   long i,j, lx = lg(x);
    1092         [ +  + ]:     243694 :   for (i=1; i<lx; i++)
    1093                 :            :   {
    1094                 :     199260 :     GEN xii = gcoeff(x,i,i);
    1095         [ +  + ]:     199260 :     if (signe(xii) <= 0) return 0;
    1096         [ +  + ]:     746828 :     for (j=1; j<i; j++)
    1097         [ -  + ]:     548163 :       if (signe(gcoeff(x,i,j))) return 0;
    1098         [ +  + ]:     777971 :     for (j=i+1; j<lx; j++)
    1099                 :            :     {
    1100                 :     586404 :       GEN xij = gcoeff(x,i,j);
    1101 [ +  + ][ +  + ]:     586404 :       if (signe(xij)<0 || cmpii(xij,xii)>=0) return 0;
    1102                 :            :     }
    1103                 :            :   }
    1104                 :      52127 :   return 1;
    1105                 :            : }
    1106                 :            : int
    1107                 :      93711 : ZM_isidentity(GEN x)
    1108                 :            : {
    1109                 :      93711 :   long i,j, lx = lg(x);
    1110                 :            : 
    1111         [ -  + ]:      93711 :   if (lx == 1) return 1;
    1112         [ -  + ]:      93711 :   if (lx != lgcols(x)) return 0;
    1113         [ +  + ]:     772115 :   for (j=1; j<lx; j++)
    1114                 :            :   {
    1115                 :     678404 :     GEN c = gel(x,j), t;
    1116         [ +  + ]:    3322409 :     for (i=1; i<j; )
    1117         [ -  + ]:    2644005 :       if (signe(gel(c,i++))) return 0;
    1118                 :            :     /* i = j */
    1119                 :     678404 :     t = gel(c,i++);
    1120 [ +  - ][ -  + ]:     678404 :       if (!is_pm1(t) || signe(t) < 0) return 0;
    1121         [ +  + ]:    3322409 :     for (   ; i<lx; )
    1122         [ -  + ]:    2644005 :       if (signe(gel(c,i++))) return 0;
    1123                 :            :   }
    1124                 :      93711 :   return 1;
    1125                 :            : }
    1126                 :            : 
    1127                 :            : long
    1128                 :      23247 : ZC_is_ei(GEN x)
    1129                 :            : {
    1130                 :      23247 :   long i, j = 0, l = lg(x);
    1131         [ +  + ]:     329707 :   for (i = 1; i < l; i++)
    1132                 :            :   {
    1133                 :     306460 :     GEN c = gel(x,i);
    1134                 :     306460 :     long s = signe(c);
    1135         [ +  + ]:     306460 :     if (!s) continue;
    1136 [ +  - ][ +  - ]:      23240 :     if (s < 0 || !is_pm1(c) || j) return 0;
                 [ -  + ]
    1137                 :      23240 :     j = i;
    1138                 :            :   }
    1139                 :      23247 :   return j;
    1140                 :            : }
    1141                 :            : 
    1142                 :            : /********************************************************************/
    1143                 :            : /**                                                                **/
    1144                 :            : /**                       MISCELLANEOUS                            **/
    1145                 :            : /**                                                                **/
    1146                 :            : /********************************************************************/
    1147                 :            : /* assume lg(x) = lg(y), x,y in Z^n */
    1148                 :            : int
    1149                 :     413851 : ZV_cmp(GEN x, GEN y)
    1150                 :            : {
    1151                 :     413851 :   long fl,i, lx = lg(x);
    1152         [ +  + ]:     977391 :   for (i=1; i<lx; i++)
    1153         [ +  + ]:     820504 :     if (( fl = cmpii(gel(x,i), gel(y,i)) )) return fl;
    1154                 :     413851 :   return 0;
    1155                 :            : }
    1156                 :            : /* assume lg(x) = lg(y), x,y in Z^n */
    1157                 :            : int
    1158                 :       3480 : ZV_abscmp(GEN x, GEN y)
    1159                 :            : {
    1160                 :       3480 :   long fl,i, lx = lg(x);
    1161         [ +  + ]:      19454 :   for (i=1; i<lx; i++)
    1162         [ +  + ]:      19374 :     if (( fl = absi_cmp(gel(x,i), gel(y,i)) )) return fl;
    1163                 :       3480 :   return 0;
    1164                 :            : }
    1165                 :            : 
    1166                 :            : long
    1167                 :     858596 : zv_content(GEN x)
    1168                 :            : {
    1169                 :     858596 :   long i, s, l = lg(x);
    1170         [ +  + ]:     858596 :   if (l == 1) return 0;
    1171                 :     858589 :   s = labs(x[1]);
    1172 [ +  + ][ +  + ]:    1790880 :   for (i=2; i<l && s!=1; i++) s = cgcd(x[i],s);
    1173                 :     858596 :   return s;
    1174                 :            : }
    1175                 :            : GEN
    1176                 :       2919 : ZV_content(GEN x)
    1177                 :            : {
    1178                 :       2919 :   long i, l = lg(x);
    1179                 :       2919 :   pari_sp av = avma;
    1180                 :            :   GEN c;
    1181         [ -  + ]:       2919 :   if (l == 1) return gen_0;
    1182         [ +  + ]:       2919 :   if (l == 2) return absi(gel(x,1));
    1183                 :       1295 :   c = gel(x,1);
    1184         [ +  + ]:       2814 :   for (i = 2; i < l; i++)
    1185                 :            :   {
    1186                 :       1869 :     c = gcdii(c, gel(x,i));
    1187         [ +  + ]:       1869 :     if (is_pm1(c)) { avma = av; return gen_1; }
    1188                 :            :   }
    1189                 :       2919 :   return gerepileuptoint(av, c);
    1190                 :            : }
    1191                 :            : 
    1192                 :            : GEN
    1193                 :     583690 : ZM_det_triangular(GEN mat)
    1194                 :            : {
    1195                 :            :   pari_sp av;
    1196                 :     583690 :   long i,l = lg(mat);
    1197                 :            :   GEN s;
    1198                 :            : 
    1199 [ +  + ][ +  + ]:     583690 :   if (l<3) return l<2? gen_1: icopy(gcoeff(mat,1,1));
    1200                 :     568476 :   av = avma; s = gcoeff(mat,1,1);
    1201         [ +  + ]:    1672796 :   for (i=2; i<l; i++) s = mulii(s,gcoeff(mat,i,i));
    1202                 :     583690 :   return gerepileuptoint(av,s);
    1203                 :            : }
    1204                 :            : 
    1205                 :            : /* assumes no overflow */
    1206                 :            : long
    1207                 :     304301 : zv_prod(GEN v)
    1208                 :            : {
    1209                 :     304301 :   long n, i, l = lg(v);
    1210         [ +  + ]:     304301 :   if (l == 1) return 1;
    1211         [ +  + ]:     345213 :   n = v[1]; for (i = 2; i < l; i++) n *= v[i];
    1212                 :     304301 :   return n;
    1213                 :            : }
    1214                 :            : 
    1215                 :            : static GEN
    1216                 :     938115 : _mulii(void *E, GEN a, GEN b)
    1217                 :     938115 : { (void) E; return mulii(a, b); }
    1218                 :            : 
    1219                 :            : /* product of ulongs */
    1220                 :            : GEN
    1221                 :     365114 : zv_prod_Z(GEN v)
    1222                 :            : {
    1223                 :     365114 :   pari_sp av = avma;
    1224                 :     365114 :   long k, n = lg(v)-1, m;
    1225                 :            :   GEN x;
    1226         [ +  + ]:     365114 :   if (n == 0) return gen_1;
    1227         [ +  + ]:     345654 :   if (n == 1) return utoi(v[1]);
    1228         [ +  + ]:     289024 :   if (n == 2) return muluu(v[1], v[2]);
    1229                 :     163696 :   m = n >> 1;
    1230         [ +  + ]:     163696 :   x = cgetg(m + (odd(n)? 2: 1), t_VEC);
    1231         [ +  + ]:     368704 :   for (k = 1; k <= m; k++) gel(x,k) = muluu(v[k<<1], v[(k<<1)-1]);
    1232         [ +  + ]:     163696 :   if (odd(n)) gel(x,k) = utoipos(v[n]);
    1233                 :     365114 :   return gerepileuptoint(av, gen_product(x, NULL, _mulii));
    1234                 :            : }
    1235                 :            : 
    1236                 :            : GEN
    1237                 :      32384 : ZV_prod(GEN v)
    1238                 :            : {
    1239                 :      32384 :   pari_sp av = avma;
    1240                 :      32384 :   long i, l = lg(v);
    1241                 :            :   GEN n;
    1242         [ +  + ]:      32384 :   if (l == 1) return gen_1;
    1243         [ +  + ]:      31579 :   if (l > 7) return gerepileuptoint(av, gen_product(v, NULL, _mulii));
    1244                 :      23818 :   n = gel(v,1);
    1245         [ +  + ]:      23818 :   if (l == 2) return icopy(n);
    1246         [ +  + ]:      37733 :   for (i = 2; i < l; i++) n = mulii(n, gel(v,i));
    1247                 :      32384 :   return gerepileuptoint(av, n);
    1248                 :            : }
    1249                 :            : /* assumes no overflow */
    1250                 :            : long
    1251                 :       1582 : zv_sum(GEN v)
    1252                 :            : {
    1253                 :       1582 :   long n, i, l = lg(v);
    1254         [ +  + ]:       1582 :   if (l == 1) return 0;
    1255         [ +  + ]:       3115 :   n = v[1]; for (i = 2; i < l; i++) n += v[i];
    1256                 :       1582 :   return n;
    1257                 :            : }
    1258                 :            : GEN
    1259                 :         56 : ZV_sum(GEN v)
    1260                 :            : {
    1261                 :         56 :   pari_sp av = avma;
    1262                 :         56 :   long i, l = lg(v);
    1263                 :            :   GEN n;
    1264         [ -  + ]:         56 :   if (l == 1) return gen_0;
    1265                 :         56 :   n = gel(v,1);
    1266         [ -  + ]:         56 :   if (l == 2) return icopy(n);
    1267         [ +  + ]:        518 :   for (i = 2; i < l; i++) n = addii(n, gel(v,i));
    1268                 :         56 :   return gerepileuptoint(av, n);
    1269                 :            : }
    1270                 :            : 
    1271                 :            : /********************************************************************/
    1272                 :            : /**                                                                **/
    1273                 :            : /**         GRAM SCHMIDT REDUCTION (integer matrices)              **/
    1274                 :            : /**                                                                **/
    1275                 :            : /********************************************************************/
    1276                 :            : 
    1277                 :            : /* L[k,] += q * L[l,], l < k. Inefficient if q = 0 */
    1278                 :            : static void
    1279                 :     173023 : Zupdate_row(long k, long l, GEN q, GEN L, GEN B)
    1280                 :            : {
    1281                 :     173023 :   long i, qq = itos_or_0(q);
    1282         [ +  + ]:     173023 :   if (!qq)
    1283                 :            :   {
    1284         [ +  + ]:      18215 :     for(i=1;i<l;i++)  gcoeff(L,k,i) = addii(gcoeff(L,k,i),mulii(q,gcoeff(L,l,i)));
    1285                 :       5062 :     gcoeff(L,k,l) = addii(gcoeff(L,k,l), mulii(q,B));
    1286                 :     173023 :     return;
    1287                 :            :   }
    1288         [ +  + ]:     167961 :   if (qq == 1) {
    1289         [ +  + ]:      61559 :     for (i=1;i<l; i++) gcoeff(L,k,i) = addii(gcoeff(L,k,i),gcoeff(L,l,i));
    1290                 :      34297 :     gcoeff(L,k,l) = addii(gcoeff(L,k,l), B);
    1291         [ +  + ]:     133664 :   } else if (qq == -1) {
    1292         [ +  + ]:     152477 :     for (i=1;i<l; i++) gcoeff(L,k,i) = subii(gcoeff(L,k,i),gcoeff(L,l,i));
    1293                 :      81422 :     gcoeff(L,k,l) = addii(gcoeff(L,k,l), negi(B));
    1294                 :            :   } else {
    1295         [ +  + ]:     111874 :     for(i=1;i<l;i++) gcoeff(L,k,i) = addii(gcoeff(L,k,i),mulsi(qq,gcoeff(L,l,i)));
    1296                 :      52242 :     gcoeff(L,k,l) = addii(gcoeff(L,k,l), mulsi(qq,B));
    1297                 :            :   }
    1298                 :            : }
    1299                 :            : 
    1300                 :            : /* update L[k,] */
    1301                 :            : static void
    1302                 :     542165 : ZRED(long k, long l, GEN x, GEN L, GEN B)
    1303                 :            : {
    1304                 :     542165 :   GEN q = truedivii(addii(B,shifti(gcoeff(L,k,l),1)), shifti(B,1));
    1305         [ +  + ]:     715188 :   if (!signe(q)) return;
    1306                 :     173023 :   q = negi(q);
    1307                 :     173023 :   Zupdate_row(k,l,q,L,B);
    1308                 :     173023 :   gel(x,k) = ZC_lincomb(gen_1, q, gel(x,k), gel(x,l));
    1309                 :            : }
    1310                 :            : 
    1311                 :            : /* Gram-Schmidt reduction, x a ZM */
    1312                 :            : static void
    1313                 :     725051 : ZincrementalGS(GEN x, GEN L, GEN B, long k)
    1314                 :            : {
    1315                 :            :   long i, j;
    1316         [ +  + ]:    2605352 :   for (j=1; j<=k; j++)
    1317                 :            :   {
    1318                 :    1880301 :     pari_sp av = avma;
    1319                 :    1880301 :     GEN u = ZV_dotproduct(gel(x,k), gel(x,j));
    1320         [ +  + ]:    4426903 :     for (i=1; i<j; i++)
    1321                 :            :     {
    1322                 :    2546602 :       u = subii(mulii(gel(B,i+1), u), mulii(gcoeff(L,k,i), gcoeff(L,j,i)));
    1323                 :    2546602 :       u = diviiexact(u, gel(B,i));
    1324                 :            :     }
    1325                 :    1880301 :     gcoeff(L,k,j) = gerepileuptoint(av, u);
    1326                 :            :   }
    1327                 :     725051 :   gel(B,k+1) = gcoeff(L,k,k); gcoeff(L,k,k) = gen_1;
    1328                 :     725051 : }
    1329                 :            : 
    1330                 :            : /* Variant reducemodinvertible(ZC v, ZM y), when y singular.
    1331                 :            :  * Very inefficient if y is not LLL-reduced of maximal rank */
    1332                 :            : static GEN
    1333                 :     187219 : ZC_reducemodmatrix_i(GEN v, GEN y)
    1334                 :            : {
    1335                 :     187219 :   GEN B, L, x = shallowconcat(y, v);
    1336                 :     187219 :   long k, lx = lg(x), nx = lx-1;
    1337                 :            : 
    1338                 :     187219 :   B = scalarcol_shallow(gen_1, lx);
    1339                 :     187219 :   L = zeromatcopy(nx, nx);
    1340         [ +  + ]:     891333 :   for (k=1; k <= nx; k++) ZincrementalGS(x, L, B, k);
    1341         [ +  + ]:     704114 :   for (k = nx-1; k >= 1; k--) ZRED(nx,k, x,L,gel(B,k+1));
    1342                 :     187219 :   return gel(x,nx);
    1343                 :            : }
    1344                 :            : GEN
    1345                 :     187219 : ZC_reducemodmatrix(GEN v, GEN y) {
    1346                 :     187219 :   pari_sp av = avma;
    1347                 :     187219 :   return gerepilecopy(av, ZC_reducemodmatrix_i(v,y));
    1348                 :            : }
    1349                 :            : 
    1350                 :            : /* Variant reducemodinvertible(ZM v, ZM y), when y singular.
    1351                 :            :  * Very inefficient if y is not LLL-reduced of maximal rank */
    1352                 :            : static GEN
    1353                 :       4641 : ZM_reducemodmatrix_i(GEN v, GEN y)
    1354                 :            : {
    1355                 :            :   GEN B, L, V;
    1356                 :       4641 :   long j, k, lv = lg(v), nx = lg(y), lx = nx+1;
    1357                 :            : 
    1358                 :       4641 :   V = cgetg(lv, t_MAT);
    1359                 :       4641 :   B = scalarcol_shallow(gen_1, lx);
    1360                 :       4641 :   L = zeromatcopy(nx, nx);
    1361         [ +  + ]:      15302 :   for (k=1; k < nx; k++) ZincrementalGS(y, L, B, k);
    1362         [ +  + ]:      14917 :   for (j = 1; j < lg(v); j++)
    1363                 :            :   {
    1364                 :      10276 :     GEN x = shallowconcat(y, gel(v,j));
    1365                 :      10276 :     ZincrementalGS(x, L, B, nx); /* overwrite last */
    1366         [ +  + ]:      35546 :     for (k = nx-1; k >= 1; k--) ZRED(nx,k, x,L,gel(B,k+1));
    1367                 :      10276 :     gel(V,j) = gel(x,nx);
    1368                 :            :   }
    1369                 :       4641 :   return V;
    1370                 :            : }
    1371                 :            : GEN
    1372                 :       4641 : ZM_reducemodmatrix(GEN v, GEN y) {
    1373                 :       4641 :   pari_sp av = avma;
    1374                 :       4641 :   return gerepilecopy(av, ZM_reducemodmatrix_i(v,y));
    1375                 :            : }
    1376                 :            : 
    1377                 :            : GEN
    1378                 :     186624 : ZC_reducemodlll(GEN x,GEN y)
    1379                 :            : {
    1380                 :     186624 :   pari_sp av = avma;
    1381                 :     186624 :   GEN z = ZC_reducemodmatrix(x, ZM_lll(y, 0.75, LLL_INPLACE));
    1382                 :     186624 :   return gerepilecopy(av, z);
    1383                 :            : }
    1384                 :            : GEN
    1385                 :          0 : ZM_reducemodlll(GEN x,GEN y)
    1386                 :            : {
    1387                 :          0 :   pari_sp av = avma;
    1388                 :          0 :   GEN z = ZM_reducemodmatrix(x, ZM_lll(y, 0.75, LLL_INPLACE));
    1389                 :          0 :   return gerepilecopy(av, z);
    1390                 :            : }

Generated by: LCOV version 1.9