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 17784-cfd2407) Lines: 680 765 88.9 %
Date: 2015-04-27 Functions: 97 105 92.4 %
Legend: Lines: hit not hit | Branches: + taken - not taken # not executed Branches: 437 542 80.6 %

           Branch data     Line data    Source code
       1                 :            : /* Copyright (C) 2000  The PARI group.
       2                 :            : 
       3                 :            : This file is part of the PARI/GP package.
       4                 :            : 
       5                 :            : PARI/GP is free software; you can redistribute it and/or modify it under the
       6                 :            : terms of the GNU General Public License as published by the Free Software
       7                 :            : Foundation. It is distributed in the hope that it will be useful, but WITHOUT
       8                 :            : ANY WARRANTY WHATSOEVER.
       9                 :            : 
      10                 :            : Check the License for details. You should have received a copy of it, along
      11                 :            : with the package; see the file 'COPYING'. If not, write to the Free Software
      12                 :            : Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. */
      13                 :            : 
      14                 :            : #include "pari.h"
      15                 :            : #include "paripriv.h"
      16                 :            : 
      17                 :            : static int
      18                 :      32368 : check_ZV(GEN x, long l)
      19                 :            : {
      20                 :            :   long i;
      21         [ +  + ]:     196784 :   for (i=1; i<l; i++)
      22         [ +  + ]:     164500 :     if (typ(gel(x,i)) != t_INT) return 0;
      23                 :      32368 :   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                 :       9037 : RgM_check_ZM(GEN A, const char *s)
      32                 :            : {
      33                 :       9037 :   long n = lg(A);
      34         [ +  + ]:       9037 :   if (n != 1)
      35                 :            :   {
      36                 :       9002 :     long j, m = lgcols(A);
      37         [ +  + ]:      41286 :     for (j=1; j<n; j++)
      38         [ +  + ]:      32368 :       if (!check_ZV(gel(A,j), m))
      39                 :         84 :         pari_err_TYPE(stack_strcat(s," [integer matrix]"), A);
      40                 :            :   }
      41                 :       8953 : }
      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                 :       1498 : ZM_max_lg(GEN x)
      52                 :            : {
      53                 :       1498 :   long i, prec = 2, n = lg(x);
      54         [ +  - ]:       1498 :   if (n != 1)
      55                 :            :   {
      56                 :       1498 :     long j, m = lgcols(x);
      57         [ +  + ]:      11522 :     for (j=1; j<n; j++)
      58                 :            :     {
      59                 :      10024 :       GEN c = gel(x,j);
      60 [ +  + ][ +  + ]:     167202 :       for (i=1; i<m; i++) { long l = lgefint(gel(c,i)); if (l > prec) prec = l; }
      61                 :            :     }
      62                 :            :   }
      63                 :       1498 :   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                 :       3748 : ZM_nc_mul_i(GEN x, GEN y, long c, long l)
      93                 :            : {
      94                 :            :   long i, j;
      95                 :            :   pari_sp av;
      96                 :       3748 :   GEN z = cgetg(l,t_COL), s;
      97                 :            : 
      98         [ +  + ]:      77008 :   for (i=1; i<l; i++)
      99                 :            :   {
     100                 :      73260 :     av = avma; s = muliu(gcoeff(x,i,1),y[1]);
     101         [ +  + ]:    2274212 :     for (j=2; j<c; j++)
     102         [ +  + ]:    2200952 :       if (y[j]) s = addii(s, muliu(gcoeff(x,i,j),y[j]));
     103                 :      73260 :     gel(z,i) = gerepileuptoint(av,s);
     104                 :            :   }
     105                 :       3748 :   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                 :    1491479 : ZM_zc_mul_i(GEN x, GEN y, long c, long l)
     123                 :            : {
     124                 :            :   long i, j;
     125                 :            :   pari_sp av;
     126                 :    1491479 :   GEN z = cgetg(l,t_COL), s;
     127                 :            : 
     128         [ +  + ]:   12996945 :   for (i=1; i<l; i++)
     129                 :            :   {
     130                 :   11505466 :     av = avma; s = mulis(gcoeff(x,i,1),y[1]);
     131         [ +  + ]:  240707115 :     for (j=2; j<c; j++)
     132         [ +  + ]:  229201649 :       if (y[j]) s = addii(s, mulis(gcoeff(x,i,j),y[j]));
     133                 :   11505466 :     gel(z,i) = gerepileuptoint(av,s);
     134                 :            :   }
     135                 :    1491479 :   return z;
     136                 :            : }
     137                 :            : GEN
     138                 :    1378471 : ZM_zc_mul(GEN x, GEN y) {
     139                 :    1378471 :   long l = lg(x);
     140         [ -  + ]:    1378471 :   if (l == 1) return cgetg(1, t_COL);
     141                 :    1378471 :   return ZM_zc_mul_i(x,y, l, lgcols(x));
     142                 :            : }
     143                 :            : 
     144                 :            : /* x ZM, y a compatible zm (dimension > 0). */
     145                 :            : GEN
     146                 :      44695 : ZM_zm_mul(GEN x, GEN y)
     147                 :            : {
     148                 :      44695 :   long j, c, l = lg(x), ly = lg(y);
     149                 :      44695 :   GEN z = cgetg(ly, t_MAT);
     150         [ -  + ]:      44695 :   if (l == 1) return z;
     151                 :      44695 :   c = lgcols(x);
     152         [ +  + ]:     157703 :   for (j = 1; j < ly; j++) gel(z,j) = ZM_zc_mul_i(x, gel(y,j), l,c);
     153                 :      44695 :   return z;
     154                 :            : }
     155                 :            : /* x ZM, y a compatible zn (dimension > 0). */
     156                 :            : GEN
     157                 :        281 : ZM_nm_mul(GEN x, GEN y)
     158                 :            : {
     159                 :        281 :   long j, c, l = lg(x), ly = lg(y);
     160                 :        281 :   GEN z = cgetg(ly, t_MAT);
     161         [ -  + ]:        281 :   if (l == 1) return z;
     162                 :        281 :   c = lgcols(x);
     163         [ +  + ]:       4029 :   for (j = 1; j < ly; j++) gel(z,j) = ZM_nc_mul_i(x, gel(y,j), l,c);
     164                 :        281 :   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                 :      78344 : 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                 :      78344 :   long min_d = minss(da, db), min_e = minss(ea, eb), i, j;
     179                 :      78344 :   GEN M = cgetg(n + 1, t_MAT), C;
     180                 :            : 
     181         [ +  + ]:    2086532 :   for (j = 1; j <= min_e; j++) {
     182                 :    2008188 :     gel(M, j) = C = cgetg(m + 1, t_COL);
     183         [ +  + ]:   55972679 :     for (i = 1; i <= min_d; i++)
     184                 :   53964491 :       gel(C, i) = addii(gcoeff(A, ma + i, na + j),
     185                 :   53964491 :                         gcoeff(B, mb + i, nb + j));
     186         [ +  + ]:    2035817 :     for (; i <= da; i++)
     187                 :      27629 :       gel(C, i) = gcoeff(A, ma + i, na + j);
     188         [ -  + ]:    2008188 :     for (; i <= db; i++)
     189                 :          0 :       gel(C, i) = gcoeff(B, mb + i, nb + j);
     190         [ -  + ]:    2008188 :     for (; i <= m; i++)
     191                 :          0 :       gel(C, i) = gen_0;
     192                 :            :   }
     193         [ +  + ]:      80682 :   for (; j <= ea; j++) {
     194                 :       2338 :     gel(M, j) = C = cgetg(m + 1, t_COL);
     195         [ +  + ]:      68530 :     for (i = 1; i <= da; i++)
     196                 :      66192 :       gel(C, i) = gcoeff(A, ma + i, na + j);
     197         [ -  + ]:       2338 :     for (; i <= m; i++)
     198                 :          0 :       gel(C, i) = gen_0;
     199                 :            :   }
     200         [ -  + ]:      78344 :   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         [ -  + ]:      78344 :   for (; j <= n; j++)
     208                 :          0 :     gel(M, j) = zerocol(m);
     209                 :      78344 :   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                 :      68551 : 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                 :      68551 :   long min_d = minss(da, db), min_e = minss(ea, eb), i, j;
     222                 :      68551 :   GEN M = cgetg(n + 1, t_MAT), C;
     223                 :            : 
     224         [ +  + ]:    1859571 :   for (j = 1; j <= min_e; j++) {
     225                 :    1791020 :     gel(M, j) = C = cgetg(m + 1, t_COL);
     226         [ +  + ]:   53103274 :     for (i = 1; i <= min_d; i++)
     227                 :   51312254 :       gel(C, i) = subii(gcoeff(A, ma + i, na + j),
     228                 :   51312254 :                         gcoeff(B, mb + i, nb + j));
     229         [ +  + ]:    1830444 :     for (; i <= da; i++)
     230                 :      39424 :       gel(C, i) = gcoeff(A, ma + i, na + j);
     231         [ +  + ]:    1825887 :     for (; i <= db; i++)
     232                 :      34867 :       gel(C, i) = negi(gcoeff(B, mb + i, nb + j));
     233         [ -  + ]:    1791020 :     for (; i <= m; i++)
     234                 :          0 :       gel(C, i) = gen_0;
     235                 :            :   }
     236         [ -  + ]:      68551 :   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         [ +  + ]:      69685 :   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         [ +  + ]:      69685 :   for (; j <= n; j++)
     251                 :       1134 :     gel(M, j) = zerocol(m);
     252                 :      68551 :   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                 :       9793 : ZM_mul_sw(GEN A, GEN B, long m, long n, long p)
     260                 :            : {
     261                 :       9793 :   pari_sp av = avma;
     262                 :       9793 :   long m1 = (m + 1)/2, m2 = m/2,
     263                 :       9793 :     n1 = (n + 1)/2, n2 = n/2,
     264                 :       9793 :     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                 :       9793 :   T2 = subtract_slices(n1, p2, B, 0, n1, p1, p2, B, n1, n2, p1, p2);
     271                 :       9793 :   S1 = subtract_slices(m2, n1, A, m1, m2, 0, n1, A, 0, m2, 0, n1);
     272                 :       9793 :   M2 = ZM_mul_i(S1, T2, m2 + 1, n1 + 1, p2 + 1);
     273         [ -  + ]:       9793 :   if (gc_needed(av, 1))
     274                 :          0 :     gerepileall(av, 2, &T2, &M2);  /* destroy S1 */
     275                 :       9793 :   T3 = subtract_slices(n1, p1, T2, 0, n1, 0, p2, B, 0, n1, 0, p1);
     276         [ -  + ]:       9793 :   if (gc_needed(av, 1))
     277                 :          0 :     gerepileall(av, 2, &M2, &T3);  /* destroy T2 */
     278                 :       9793 :   S2 = add_slices(m2, n1, A, m1, m2, 0, n1, A, m1, m2, n1, n2);
     279                 :       9793 :   T1 = subtract_slices(n1, p1, B, 0, n1, p1, p2, B, 0, n1, 0, p2);
     280                 :       9793 :   M3 = ZM_mul_i(S2, T1, m2 + 1, n1 + 1, p2 + 1);
     281         [ -  + ]:       9793 :   if (gc_needed(av, 1))
     282                 :          0 :     gerepileall(av, 4, &M2, &T3, &S2, &M3);  /* destroy T1 */
     283                 :       9793 :   S3 = subtract_slices(m1, n1, S2, 0, m2, 0, n1, A, 0, m1, 0, n1);
     284         [ -  + ]:       9793 :   if (gc_needed(av, 1))
     285                 :          0 :     gerepileall(av, 4, &M2, &T3, &M3, &S3);  /* destroy S2 */
     286                 :       9793 :   A11 = matslice(A, 1, m1, 1, n1);
     287                 :       9793 :   B11 = matslice(B, 1, n1, 1, p1);
     288                 :       9793 :   M1 = ZM_mul_i(A11, B11, m1 + 1, n1 + 1, p1 + 1);
     289         [ -  + ]:       9793 :   if (gc_needed(av, 1))
     290                 :          0 :     gerepileall(av, 5, &M2, &T3, &M3, &S3, &M1);  /* destroy A11, B11 */
     291                 :       9793 :   A12 = matslice(A, 1, m1, n1 + 1, n);
     292                 :       9793 :   B21 = matslice(B, n1 + 1, n, 1, p1);
     293                 :       9793 :   M4 = ZM_mul_i(A12, B21, m1 + 1, n2 + 1, p1 + 1);
     294         [ -  + ]:       9793 :   if (gc_needed(av, 1))
     295                 :          0 :     gerepileall(av, 6, &M2, &T3, &M3, &S3, &M1, &M4);  /* destroy A12, B21 */
     296                 :       9793 :   C11 = add_slices(m1, p1, M1, 0, m1, 0, p1, M4, 0, m1, 0, p1);
     297         [ -  + ]:       9793 :   if (gc_needed(av, 1))
     298                 :          0 :     gerepileall(av, 6, &M2, &T3, &M3, &S3, &M1, &C11);  /* destroy M4 */
     299                 :       9793 :   M5 = ZM_mul_i(S3, T3, m1 + 1, n1 + 1, p1 + 1);
     300                 :       9793 :   S4 = subtract_slices(m1, n2, A, 0, m1, n1, n2, S3, 0, m1, 0, n2);
     301         [ -  + ]:       9793 :   if (gc_needed(av, 1))
     302                 :          0 :     gerepileall(av, 7, &M2, &T3, &M3, &M1, &C11, &M5, &S4);  /* destroy S3 */
     303                 :       9793 :   T4 = add_slices(n2, p1, B, n1, n2, 0, p1, T3, 0, n2, 0, p1);
     304         [ -  + ]:       9793 :   if (gc_needed(av, 1))
     305                 :          0 :     gerepileall(av, 7, &M2, &M3, &M1, &C11, &M5, &S4, &T4);  /* destroy T3 */
     306                 :       9793 :   V1 = subtract_slices(m1, p1, M1, 0, m1, 0, p1, M5, 0, m1, 0, p1);
     307         [ -  + ]:       9793 :   if (gc_needed(av, 1))
     308                 :          0 :     gerepileall(av, 6, &M2, &M3, &S4, &T4, &C11, &V1);  /* destroy M1, M5 */
     309                 :       9793 :   B22 = matslice(B, n1 + 1, n, p1 + 1, p);
     310                 :       9793 :   M6 = ZM_mul_i(S4, B22, m1 + 1, n2 + 1, p2 + 1);
     311         [ -  + ]:       9793 :   if (gc_needed(av, 1))
     312                 :          0 :     gerepileall(av, 6, &M2, &M3, &T4, &C11, &V1, &M6);  /* destroy S4, B22 */
     313                 :       9793 :   A22 = matslice(A, m1 + 1, m, n1 + 1, n);
     314                 :       9793 :   M7 = ZM_mul_i(A22, T4, m2 + 1, n2 + 1, p1 + 1);
     315         [ -  + ]:       9793 :   if (gc_needed(av, 1))
     316                 :          0 :     gerepileall(av, 6, &M2, &M3, &C11, &V1, &M6, &M7);  /* destroy A22, T4 */
     317                 :       9793 :   V3 = add_slices(m1, p2, V1, 0, m1, 0, p2, M3, 0, m2, 0, p2);
     318                 :       9793 :   C12 = add_slices(m1, p2, V3, 0, m1, 0, p2, M6, 0, m1, 0, p2);
     319         [ -  + ]:       9793 :   if (gc_needed(av, 1))
     320                 :          0 :     gerepileall(av, 6, &M2, &M3, &C11, &V1, &M7, &C12);  /* destroy V3, M6 */
     321                 :       9793 :   V2 = add_slices(m2, p1, V1, 0, m2, 0, p1, M2, 0, m2, 0, p2);
     322         [ -  + ]:       9793 :   if (gc_needed(av, 1))
     323                 :          0 :     gerepileall(av, 5, &M3, &C11, &M7, &C12, &V2);  /* destroy V1, M2 */
     324                 :       9793 :   C21 = add_slices(m2, p1, V2, 0, m2, 0, p1, M7, 0, m2, 0, p1);
     325         [ -  + ]:       9793 :   if (gc_needed(av, 1))
     326                 :          0 :     gerepileall(av, 5, &M3, &C11, &C12, &V2, &C21);  /* destroy M7 */
     327                 :       9793 :   C22 = add_slices(m2, p2, V2, 0, m2, 0, p2, M3, 0, m2, 0, p2);
     328         [ -  + ]:       9793 :   if (gc_needed(av, 1))
     329                 :          0 :     gerepileall(av, 4, &C11, &C12, &C21, &C22);  /* destroy V2, M3 */
     330                 :       9793 :   C = mkmat2(mkcol2(C11, C21), mkcol2(C12, C22));
     331                 :       9793 :   return gerepileupto(av, matconcat(C));
     332                 :            : }
     333                 :            : 
     334                 :            : /* x[i,]*y. Assume lg(x) > 1 and 0 < i < lgcols(x) */
     335                 :            : static GEN
     336                 :  114314597 : ZMrow_ZC_mul_i(GEN x, GEN y, long i, long lx)
     337                 :            : {
     338                 :  114314597 :   pari_sp av = avma;
     339                 :  114314597 :   GEN c = mulii(gcoeff(x,i,1), gel(y,1)), ZERO = gen_0;
     340                 :            :   long k;
     341         [ +  + ]: 2018633879 :   for (k = 2; k < lx; k++)
     342                 :            :   {
     343                 : 1904319282 :     GEN t = mulii(gcoeff(x,i,k), gel(y,k));
     344         [ +  + ]: 1904319282 :     if (t != ZERO) c = addii(c, t);
     345                 :            :   }
     346                 :  114314597 :   return gerepileuptoint(av, c);
     347                 :            : }
     348                 :            : GEN
     349                 :   20687636 : ZMrow_ZC_mul(GEN x, GEN y, long i)
     350                 :   20687636 : { 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                 :   11390987 : ZM_ZC_mul_i(GEN x, GEN y, long lx, long l)
     355                 :            : {
     356                 :   11390987 :   GEN z = cgetg(l,t_COL);
     357                 :            :   long i;
     358         [ +  + ]:  105017948 :   for (i=1; i<l; i++) gel(z,i) = ZMrow_ZC_mul_i(x,y,i,lx);
     359                 :   11390987 :   return z;
     360                 :            : }
     361                 :            : 
     362                 :            : static GEN
     363                 :    1508899 : ZM_mul_classical(GEN x, GEN y, long l, long lx, long ly)
     364                 :            : {
     365                 :            :   long j;
     366                 :    1508899 :   GEN z = cgetg(ly, t_MAT);
     367         [ +  + ]:    9232954 :   for (j = 1; j < ly; j++)
     368                 :    7724055 :     gel(z, j) = ZM_ZC_mul_i(x, gel(y, j), lx, l);
     369                 :    1508899 :   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                 :    1518692 : ZM_mul_i(GEN x, GEN y, long l, long lx, long ly)
     377                 :            : {
     378 [ +  + ][ +  + ]:    1518692 :   if (l <= ZM_sw_bound || lx <= ZM_sw_bound || ly <= ZM_sw_bound)
                 [ +  + ]
     379                 :    1508899 :     return ZM_mul_classical(x, y, l, lx, ly);
     380                 :            :   else
     381                 :    1518692 :     return ZM_mul_sw(x, y, l - 1, lx - 1, ly - 1);
     382                 :            : }
     383                 :            : 
     384                 :            : GEN
     385                 :    1452542 : ZM_mul(GEN x, GEN y)
     386                 :            : {
     387                 :    1452542 :   long lx=lg(x), ly=lg(y);
     388         [ +  + ]:    1452542 :   if (ly==1) return cgetg(1,t_MAT);
     389         [ +  + ]:    1450260 :   if (lx==1) return zeromat(0, ly-1);
     390                 :    1452542 :   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                 :   11901776 : ZV_dotproduct_i(GEN x, GEN y, long lx)
     417                 :            : {
     418                 :   11901776 :   pari_sp av = avma;
     419                 :   11901776 :   GEN c = mulii(gel(x,1), gel(y,1));
     420                 :            :   long i;
     421         [ +  + ]:   95462071 :   for (i = 2; i < lx; i++)
     422                 :            :   {
     423                 :   83560295 :     GEN t = mulii(gel(x,i), gel(y,i));
     424         [ +  + ]:   83560295 :     if (t != gen_0) c = addii(c, t);
     425                 :            :   }
     426                 :   11901776 :   return gerepileuptoint(av, c);
     427                 :            : }
     428                 :            : 
     429                 :            : /* x~ * y, assuming result is symmetric */
     430                 :            : GEN
     431                 :     158088 : ZM_transmultosym(GEN x, GEN y)
     432                 :            : {
     433                 :     158088 :   long i, j, l, ly = lg(y);
     434                 :            :   GEN M;
     435         [ -  + ]:     158088 :   if (ly == 1) return cgetg(1,t_MAT);
     436                 :            :   /* lg(x) = ly */
     437                 :     158088 :   l = lgcols(y); /* = lgcols(x) */
     438                 :     158088 :   M = cgetg(ly, t_MAT);
     439         [ +  + ]:    1231261 :   for (i=1; i<ly; i++)
     440                 :            :   {
     441                 :    1073173 :     GEN xi = gel(x,i), c = cgetg(ly,t_COL);
     442                 :    1073173 :     gel(M,i) = c;
     443         [ +  + ]:    4777823 :     for (j=1; j<i; j++)
     444                 :    3704650 :       gcoeff(M,i,j) = gel(c,j) = ZV_dotproduct_i(xi,gel(y,j),l);
     445                 :    1073173 :     gel(c,i) = ZV_dotproduct_i(xi,gel(y,i),l);
     446                 :            :   }
     447                 :     158088 :   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                 :            : GEN
     469                 :         56 : ZM_sqr(GEN x)
     470                 :            : {
     471                 :         56 :   long j, l, lx=lg(x);
     472                 :            :   GEN z;
     473         [ -  + ]:         56 :   if (lx==1) return cgetg(1,t_MAT);
     474                 :         56 :   l = lgcols(x); z = cgetg(lx,t_MAT);
     475         [ +  + ]:        168 :   for (j=1; j<lx; j++) gel(z,j) = ZM_ZC_mul_i(x, gel(x,j), lx, l);
     476                 :         56 :   return z;
     477                 :            : }
     478                 :            : GEN
     479                 :    3694856 : ZM_ZC_mul(GEN x, GEN y)
     480                 :            : {
     481                 :    3694856 :   long lx = lg(x);
     482         [ +  + ]:    3694856 :   return lx==1? cgetg(1,t_COL): ZM_ZC_mul_i(x, y, lx, lgcols(x));
     483                 :            : }
     484                 :            : 
     485                 :            : GEN
     486                 :       1883 : ZM_Z_div(GEN X, GEN c)
     487                 :            : {
     488                 :       1883 :   long i, j, h, l = lg(X);
     489                 :       1883 :   GEN A = cgetg(l, t_MAT);
     490         [ -  + ]:       1883 :   if (l == 1) return A;
     491                 :       1883 :   h = lgcols(X);
     492         [ +  + ]:      29967 :   for (j=1; j<l; j++)
     493                 :            :   {
     494                 :      28084 :     GEN a = cgetg(h, t_COL), x = gel(X, j);
     495         [ +  + ]:     719376 :     for (i = 1; i < h; i++) gel(a,i) = gred_frac2(gel(x,i), c);
     496                 :      28084 :     gel(A,j) = a;
     497                 :            :   }
     498                 :       1883 :   return A;
     499                 :            : }
     500                 :            : 
     501                 :            : long
     502                 :  125500697 : zv_dotproduct(GEN x, GEN y)
     503                 :            : {
     504                 :  125500697 :   long i, lx = lg(x);
     505                 :            :   ulong c;
     506         [ -  + ]:  125500697 :   if (lx == 1) return 0;
     507                 :  125500697 :   c = uel(x,1)*uel(y,1);
     508         [ +  + ]: 1947333227 :   for (i = 2; i < lx; i++)
     509                 : 1821832530 :     c += uel(x,i)*uel(y,i);
     510                 :  125500697 :   return c;
     511                 :            : }
     512                 :            : 
     513                 :            : GEN
     514                 :       3304 : ZV_ZM_mul(GEN x, GEN y)
     515                 :            : {
     516                 :       3304 :   long i, lx = lg(x), ly = lg(y);
     517                 :            :   GEN z;
     518         [ -  + ]:       3304 :   if (lx == 1) return zerovec(ly-1);
     519                 :       3304 :   z = cgetg(ly, t_VEC);
     520         [ +  + ]:      10094 :   for (i = 1; i < ly; i++) gel(z,i) = ZV_dotproduct_i(x, gel(y,i), lx);
     521                 :       3304 :   return z;
     522                 :            : }
     523                 :            : 
     524                 :            : GEN
     525                 :          0 : ZC_ZV_mul(GEN x, GEN y)
     526                 :            : {
     527                 :          0 :   long i,j, lx=lg(x), ly=lg(y);
     528                 :            :   GEN z;
     529         [ #  # ]:          0 :   if (ly==1) return cgetg(1,t_MAT);
     530                 :          0 :   z = cgetg(ly,t_MAT);
     531         [ #  # ]:          0 :   for (j=1; j < ly; j++)
     532                 :            :   {
     533                 :          0 :     gel(z,j) = cgetg(lx,t_COL);
     534         [ #  # ]:          0 :     for (i=1; i<lx; i++) gcoeff(z,i,j) = mulii(gel(x,i),gel(y,j));
     535                 :            :   }
     536                 :          0 :   return z;
     537                 :            : }
     538                 :            : 
     539                 :            : GEN
     540                 :    4043342 : ZV_dotsquare(GEN x)
     541                 :            : {
     542                 :            :   long i, lx;
     543                 :            :   pari_sp av;
     544                 :            :   GEN z;
     545                 :    4043342 :   lx = lg(x);
     546         [ -  + ]:    4043342 :   if (lx == 1) return gen_0;
     547                 :    4043342 :   av = avma; z = sqri(gel(x,1));
     548         [ +  + ]:   16092607 :   for (i=2; i<lx; i++) z = addii(z, sqri(gel(x,i)));
     549                 :    4043342 :   return gerepileuptoint(av,z);
     550                 :            : }
     551                 :            : 
     552                 :            : GEN
     553                 :   10043986 : ZV_dotproduct(GEN x,GEN y)
     554                 :            : {
     555                 :            :   long lx;
     556         [ +  + ]:   10043986 :   if (x == y) return ZV_dotsquare(x);
     557                 :    7113222 :   lx = lg(x);
     558         [ -  + ]:    7113222 :   if (lx == 1) return gen_0;
     559                 :   10043986 :   return ZV_dotproduct_i(x, y, lx);
     560                 :            : }
     561                 :            : 
     562                 :            : static GEN
     563                 :        217 : _ZM_mul(void *data /*ignored*/, GEN x, GEN y)
     564                 :        217 : { (void)data; return ZM_mul(x,y); }
     565                 :            : static GEN
     566                 :      32795 : _ZM_sqr(void *data /*ignored*/, GEN x)
     567                 :      32795 : { (void)data; return ZM_mul(x,x); }
     568                 :            : GEN
     569                 :          0 : ZM_pow(GEN x, GEN n)
     570                 :            : {
     571                 :          0 :   pari_sp av = avma;
     572         [ #  # ]:          0 :   if (!signe(n)) return matid(lg(x)-1);
     573                 :          0 :   return gerepileupto(av, gen_pow(x, n, NULL, &_ZM_sqr, &_ZM_mul));
     574                 :            : }
     575                 :            : GEN
     576                 :      31339 : ZM_powu(GEN x, ulong n)
     577                 :            : {
     578                 :      31339 :   pari_sp av = avma;
     579         [ -  + ]:      31339 :   if (!n) return matid(lg(x)-1);
     580                 :      31339 :   return gerepileupto(av, gen_powu(x, n, NULL, &_ZM_sqr, &_ZM_mul));
     581                 :            : }
     582                 :            : /********************************************************************/
     583                 :            : /**                                                                **/
     584                 :            : /**                           ADD, SUB                             **/
     585                 :            : /**                                                                **/
     586                 :            : /********************************************************************/
     587                 :            : static GEN
     588                 :    1818698 : ZC_add_i(GEN x, GEN y, long lx)
     589                 :            : {
     590                 :    1818698 :   GEN A = cgetg(lx, t_COL);
     591                 :            :   long i;
     592         [ +  + ]:   36993972 :   for (i=1; i<lx; i++) gel(A,i) = addii(gel(x,i), gel(y,i));
     593                 :    1818698 :   return A;
     594                 :            : }
     595                 :            : GEN
     596                 :    1034335 : ZC_add(GEN x, GEN y) { return ZC_add_i(x, y, lg(x)); }
     597                 :            : GEN
     598                 :      69811 : ZC_Z_add(GEN x, GEN y)
     599                 :            : {
     600                 :      69811 :   long k, lx = lg(x);
     601                 :      69811 :   GEN z = cgetg(lx, t_COL);
     602         [ -  + ]:      69811 :   if (lx == 1) pari_err_TYPE2("+",x,y);
     603                 :      69811 :   gel(z,1) = addii(y,gel(x,1));
     604         [ +  + ]:     883995 :   for (k = 2; k < lx; k++) gel(z,k) = icopy(gel(x,k));
     605                 :      69811 :   return z;
     606                 :            : }
     607                 :            : 
     608                 :            : static GEN
     609                 :    1071448 : ZC_sub_i(GEN x, GEN y, long lx)
     610                 :            : {
     611                 :            :   long i;
     612                 :    1071448 :   GEN A = cgetg(lx, t_COL);
     613         [ +  + ]:    7030131 :   for (i=1; i<lx; i++) gel(A,i) = subii(gel(x,i), gel(y,i));
     614                 :    1071448 :   return A;
     615                 :            : }
     616                 :            : GEN
     617                 :    1018980 : ZC_sub(GEN x, GEN y) { return ZC_sub_i(x, y, lg(x)); }
     618                 :            : GEN
     619                 :          0 : ZC_Z_sub(GEN x, GEN y)
     620                 :            : {
     621                 :          0 :   long k, lx = lg(x);
     622                 :          0 :   GEN z = cgetg(lx, t_COL);
     623         [ #  # ]:          0 :   if (lx == 1) pari_err_TYPE2("+",x,y);
     624                 :          0 :   gel(z,1) = subii(gel(x,1), y);
     625         [ #  # ]:          0 :   for (k = 2; k < lx; k++) gel(z,k) = icopy(gel(x,k));
     626                 :          0 :   return z;
     627                 :            : }
     628                 :            : 
     629                 :            : GEN
     630                 :      37020 : ZM_add(GEN x, GEN y)
     631                 :            : {
     632                 :      37020 :   long lx = lg(x), l, j;
     633                 :            :   GEN z;
     634         [ +  + ]:      37020 :   if (lx == 1) return cgetg(1, t_MAT);
     635                 :      35718 :   z = cgetg(lx, t_MAT); l = lgcols(x);
     636         [ +  + ]:     820081 :   for (j = 1; j < lx; j++) gel(z,j) = ZC_add_i(gel(x,j), gel(y,j), l);
     637                 :      37020 :   return z;
     638                 :            : }
     639                 :            : GEN
     640                 :      10620 : ZM_sub(GEN x, GEN y)
     641                 :            : {
     642                 :      10620 :   long lx = lg(x), l, j;
     643                 :            :   GEN z;
     644         [ -  + ]:      10620 :   if (lx == 1) return cgetg(1, t_MAT);
     645                 :      10620 :   z = cgetg(lx, t_MAT); l = lgcols(x);
     646         [ +  + ]:      63088 :   for (j = 1; j < lx; j++) gel(z,j) = ZC_sub_i(gel(x,j), gel(y,j), l);
     647                 :      10620 :   return z;
     648                 :            : }
     649                 :            : /********************************************************************/
     650                 :            : /**                                                                **/
     651                 :            : /**                         LINEAR COMBINATION                     **/
     652                 :            : /**                                                                **/
     653                 :            : /********************************************************************/
     654                 :            : /* return X/c assuming division is exact */
     655                 :            : GEN
     656                 :    1417321 : ZC_Z_divexact(GEN X, GEN c)
     657                 :            : {
     658                 :    1417321 :   long i, l = lg(X);
     659                 :    1417321 :   GEN A = cgetg(l, t_COL);
     660         [ +  + ]:   46049319 :   for (i=1; i<l; i++) gel(A,i) = diviiexact(gel(X,i), c);
     661                 :    1417321 :   return A;
     662                 :            : }
     663                 :            : GEN
     664                 :      76987 : ZM_Z_divexact(GEN X, GEN c)
     665                 :            : {
     666                 :      76987 :   long i, l = lg(X);
     667                 :      76987 :   GEN A = cgetg(l, t_MAT);
     668         [ +  + ]:    1341225 :   for (i = 1; i < l; i++) gel(A,i) = ZC_Z_divexact(gel(X,i), c);
     669                 :      76987 :   return A;
     670                 :            : }
     671                 :            : /* Return c * X */
     672                 :            : GEN
     673                 :    2449443 : ZC_Z_mul(GEN X, GEN c)
     674                 :            : {
     675                 :            :   long i, l;
     676                 :            :   GEN A;
     677         [ +  + ]:    2449443 :   if (!signe(c)) return zerocol(lg(X)-1);
     678 [ +  + ][ +  + ]:    2427176 :   if (is_pm1(c)) return (signe(c) > 0)? ZC_copy(X): ZC_neg(X);
     679                 :    2353059 :   l = lg(X); A = cgetg(l, t_COL);
     680         [ +  + ]:   14354068 :   for (i=1; i<l; i++) gel(A,i) = mulii(c,gel(X,i));
     681                 :    2449443 :   return A;
     682                 :            : }
     683                 :            : GEN
     684                 :      13153 : ZC_z_mul(GEN X, long c)
     685                 :            : {
     686                 :            :   long i, l;
     687                 :            :   GEN A;
     688         [ +  + ]:      13153 :   if (!c) return zerocol(lg(X)-1);
     689         [ +  + ]:       6664 :   if (c == 1) return ZC_copy(X);
     690         [ +  + ]:       2191 :   if (c ==-1) return ZC_neg(X);
     691                 :        728 :   l = lg(X); A = cgetg(l, t_COL);
     692         [ +  + ]:       2198 :   for (i=1; i<l; i++) gel(A,i) = mulsi(c,gel(X,i));
     693                 :      13153 :   return A;
     694                 :            : }
     695                 :            : 
     696                 :            : GEN
     697                 :       4360 : zv_z_mul(GEN M, long n)
     698                 :            : {
     699                 :            :   long l;
     700                 :       4360 :   GEN N = cgetg_copy(M, &l);
     701         [ +  + ]:      18156 :   while (--l > 0) N[l] = M[l]*n;
     702                 :       4360 :   return N;
     703                 :            : }
     704                 :            : 
     705                 :            : /* return a ZM */
     706                 :            : GEN
     707                 :        281 : nm_Z_mul(GEN X, GEN c)
     708                 :            : {
     709                 :        281 :   long i, j, h, l = lg(X), s = signe(c);
     710                 :            :   GEN A;
     711         [ -  + ]:        281 :   if (l == 1) return cgetg(1, t_MAT);
     712                 :        281 :   h = lgcols(X);
     713         [ -  + ]:        281 :   if (!s) return zeromat(h-1, l-1);
     714         [ -  + ]:        281 :   if (is_pm1(c)) {
     715         [ #  # ]:          0 :     if (s > 0) return Flm_to_ZM(X);
     716                 :          0 :     X = Flm_to_ZM(X); ZM_togglesign(X); return X;
     717                 :            :   }
     718                 :        281 :   A = cgetg(l, t_MAT);
     719         [ +  + ]:       4029 :   for (j = 1; j < l; j++)
     720                 :            :   {
     721                 :       3748 :     GEN a = cgetg(h, t_COL), x = gel(X, j);
     722         [ +  + ]:      77008 :     for (i = 1; i < h; i++) gel(a,i) = muliu(c, x[i]);
     723                 :       3748 :     gel(A,j) = a;
     724                 :            :   }
     725                 :        281 :   return A;
     726                 :            : }
     727                 :            : GEN
     728                 :      62178 : ZM_Z_mul(GEN X, GEN c)
     729                 :            : {
     730                 :      62178 :   long i, j, h, l = lg(X);
     731                 :            :   GEN A;
     732         [ -  + ]:      62178 :   if (l == 1) return cgetg(1, t_MAT);
     733                 :      62178 :   h = lgcols(X);
     734         [ +  + ]:      62178 :   if (!signe(c)) return zeromat(h-1, l-1);
     735 [ +  + ][ +  + ]:      62115 :   if (is_pm1(c)) return (signe(c) > 0)? ZM_copy(X): ZM_neg(X);
     736                 :      45742 :   A = cgetg(l, t_MAT);
     737         [ +  + ]:     684528 :   for (j = 1; j < l; j++)
     738                 :            :   {
     739                 :     638786 :     GEN a = cgetg(h, t_COL), x = gel(X, j);
     740         [ +  + ]:   22271739 :     for (i = 1; i < h; i++) gel(a,i) = mulii(c, gel(x,i));
     741                 :     638786 :     gel(A,j) = a;
     742                 :            :   }
     743                 :      62178 :   return A;
     744                 :            : }
     745                 :            : 
     746                 :            : /* X <- X + v Y (elementary col operation) */
     747                 :            : void
     748                 :   35065179 : ZC_lincomb1_inplace(GEN X, GEN Y, GEN v)
     749                 :            : {
     750                 :   35065179 :   long i, m = lgefint(v);
     751         [ -  + ]:   70130358 :   if (m == 2) return; /* v = 0 */
     752         [ +  + ]:  761925135 :   for (i = lg(X)-1; i; i--) gel(X,i) = addmulii_inplace(gel(X,i), gel(Y,i), v);
     753                 :            : }
     754                 :            : void
     755                 :    7361931 : Flc_lincomb1_inplace(GEN X, GEN Y, ulong v, ulong q)
     756                 :            : {
     757                 :            :   long i;
     758         [ -  + ]:   14723862 :   if (!v) return; /* v = 0 */
     759         [ +  + ]:  261782123 :   for (i = lg(X)-1; i; i--) X[i] = Fl_add(X[i], Fl_mul(Y[i], v, q), q);
     760                 :            : }
     761                 :            : 
     762                 :            : /* X + v Y, wasteful if (v = 0) */
     763                 :            : static GEN
     764                 :    2351828 : ZC_lincomb1(GEN v, GEN X, GEN Y)
     765                 :            : {
     766                 :    2351828 :   long i, lx = lg(X);
     767                 :    2351828 :   GEN A = cgetg(lx,t_COL);
     768         [ +  + ]:   30037862 :   for (i=1; i<lx; i++) gel(A,i) = addmulii(gel(X,i), gel(Y,i), v);
     769                 :    2351828 :   return A;
     770                 :            : }
     771                 :            : /* -X + vY */
     772                 :            : static GEN
     773                 :     371015 : ZC_lincomb_1(GEN v, GEN X, GEN Y)
     774                 :            : {
     775                 :     371015 :   long i, lx = lg(X);
     776                 :     371015 :   GEN A = cgetg(lx,t_COL);
     777         [ +  + ]:    2096094 :   for (i=1; i<lx; i++) gel(A,i) = mulsubii(gel(Y,i), v, gel(X,i));
     778                 :     371015 :   return A;
     779                 :            : }
     780                 :            : /* X,Y compatible ZV; u,v in Z. Returns A = u*X + v*Y */
     781                 :            : GEN
     782                 :    7379545 : ZC_lincomb(GEN u, GEN v, GEN X, GEN Y)
     783                 :            : {
     784                 :            :   long su, sv;
     785                 :            :   GEN A;
     786                 :            : 
     787         [ -  + ]:    7379545 :   su = signe(u); if (!su) return ZC_Z_mul(Y, v);
     788         [ +  + ]:    7379545 :   sv = signe(v); if (!sv) return ZC_Z_mul(X, u);
     789         [ +  + ]:    7379531 :   if (is_pm1(v))
     790                 :            :   {
     791         [ +  + ]:    1641017 :     if (is_pm1(u))
     792                 :            :     {
     793         [ +  + ]:    1030985 :       if (su != sv) A = ZC_sub(X, Y);
     794                 :     458557 :       else          A = ZC_add(X, Y);
     795         [ +  + ]:    1030985 :       if (su < 0) ZV_togglesign(A); /* in place but was created above */
     796                 :            :     }
     797                 :            :     else
     798                 :            :     {
     799         [ +  + ]:     610032 :       if (sv > 0) A = ZC_lincomb1 (u, Y, X);
     800                 :     266663 :       else        A = ZC_lincomb_1(u, Y, X);
     801                 :            :     }
     802                 :            :   }
     803         [ +  + ]:    5738514 :   else if (is_pm1(u))
     804                 :            :   {
     805         [ +  + ]:    2112811 :     if (su > 0) A = ZC_lincomb1 (v, X, Y);
     806                 :     104352 :     else        A = ZC_lincomb_1(v, X, Y);
     807                 :            :   }
     808                 :            :   else
     809                 :            :   { /* not cgetg_copy: x may be a t_VEC */
     810                 :    3625703 :     long i, lx = lg(X);
     811                 :    3625703 :     A = cgetg(lx,t_COL);
     812         [ +  + ]:   21588233 :     for (i=1; i<lx; i++) gel(A,i) = lincombii(u,v,gel(X,i),gel(Y,i));
     813                 :            :   }
     814                 :    7379545 :   return A;
     815                 :            : }
     816                 :            : 
     817                 :            : /********************************************************************/
     818                 :            : /**                                                                **/
     819                 :            : /**                           CONVERSIONS                          **/
     820                 :            : /**                                                                **/
     821                 :            : /********************************************************************/
     822                 :            : GEN
     823                 :        532 : ZV_to_nv(GEN z)
     824                 :            : {
     825                 :        532 :   long i, l = lg(z);
     826                 :        532 :   GEN x = cgetg(l, t_VECSMALL);
     827         [ +  + ]:        791 :   for (i=1; i<l; i++) x[i] = itou(gel(z,i));
     828                 :        532 :   return x;
     829                 :            : }
     830                 :            : 
     831                 :            : GEN
     832                 :      63896 : zm_to_ZM(GEN z)
     833                 :            : {
     834                 :      63896 :   long i, l = lg(z);
     835                 :      63896 :   GEN x = cgetg(l,t_MAT);
     836         [ +  + ]:     247772 :   for (i=1; i<l; i++) gel(x,i) = zc_to_ZC(gel(z,i));
     837                 :      63896 :   return x;
     838                 :            : }
     839                 :            : 
     840                 :            : GEN
     841                 :         63 : zmV_to_ZMV(GEN z)
     842                 :            : {
     843                 :         63 :   long i, l = lg(z);
     844                 :         63 :   GEN x = cgetg(l,t_VEC);
     845         [ +  + ]:        490 :   for (i=1; i<l; i++) gel(x,i) = zm_to_ZM(gel(z,i));
     846                 :         63 :   return x;
     847                 :            : }
     848                 :            : 
     849                 :            : /* same as Flm_to_ZM but do not assume positivity */
     850                 :            : GEN
     851                 :        238 : ZM_to_zm(GEN z)
     852                 :            : {
     853                 :        238 :   long i, l = lg(z);
     854                 :        238 :   GEN x = cgetg(l,t_MAT);
     855         [ +  + ]:     184548 :   for (i=1; i<l; i++) gel(x,i) = ZV_to_zv(gel(z,i));
     856                 :        238 :   return x;
     857                 :            : }
     858                 :            : 
     859                 :            : GEN
     860                 :     181720 : zv_to_Flv(GEN z, ulong p)
     861                 :            : {
     862                 :     181720 :   long i, l = lg(z);
     863                 :     181720 :   GEN x = cgetg(l,t_VECSMALL);
     864         [ +  + ]:    2877560 :   for (i=1; i<l; i++) x[i] = umodsu(z[i], p);
     865                 :     181720 :   return x;
     866                 :            : }
     867                 :            : 
     868                 :            : GEN
     869                 :      12460 : zm_to_Flm(GEN z, ulong p)
     870                 :            : {
     871                 :      12460 :   long i, l = lg(z);
     872                 :      12460 :   GEN x = cgetg(l,t_MAT);
     873         [ +  + ]:     194180 :   for (i=1; i<l; i++) gel(x,i) = zv_to_Flv(gel(z,i),p);
     874                 :      12460 :   return x;
     875                 :            : }
     876                 :            : 
     877                 :            : GEN
     878                 :          0 : ZMV_to_zmV(GEN z)
     879                 :            : {
     880                 :          0 :   long i,l = lg(z);
     881                 :          0 :   GEN x = cgetg(l, t_VEC);
     882         [ #  # ]:          0 :   for (i=1; i<l; i++) gel(x,i) = ZM_to_zm(gel(z,i));
     883                 :          0 :   return x;
     884                 :            : }
     885                 :            : 
     886                 :            : /********************************************************************/
     887                 :            : /**                                                                **/
     888                 :            : /**                         COPY, NEGATION                         **/
     889                 :            : /**                                                                **/
     890                 :            : /********************************************************************/
     891                 :            : GEN
     892                 :     629885 : ZC_copy(GEN x)
     893                 :            : {
     894                 :     629885 :   long i, lx = lg(x);
     895                 :     629885 :   GEN y = cgetg(lx, t_COL);
     896         [ +  + ]:    7921277 :   for (i=1; i<lx; i++)
     897                 :            :   {
     898                 :    7291392 :     GEN c = gel(x,i);
     899         [ +  + ]:    7291392 :     gel(y,i) = lgefint(c) == 2? gen_0: icopy(c);
     900                 :            :   }
     901                 :     629885 :   return y;
     902                 :            : }
     903                 :            : 
     904                 :            : GEN
     905                 :      41153 : ZM_copy(GEN x)
     906                 :            : {
     907                 :            :   long l;
     908                 :      41153 :   GEN y = cgetg_copy(x, &l);
     909         [ +  + ]:     450242 :   while (--l > 0) gel(y,l) = ZC_copy(gel(x,l));
     910                 :      41153 :   return y;
     911                 :            : }
     912                 :            : 
     913                 :            : void
     914                 :      57612 : ZV_neg_inplace(GEN M)
     915                 :            : {
     916                 :      57612 :   long l = lg(M);
     917         [ +  + ]:     437716 :   while (--l > 0) gel(M,l) = negi(gel(M,l));
     918                 :      57612 : }
     919                 :            : GEN
     920                 :    1239668 : ZC_neg(GEN M)
     921                 :            : {
     922                 :    1239668 :   long l = lg(M);
     923                 :    1239668 :   GEN N = cgetg(l, t_COL);
     924         [ +  + ]:    9943976 :   while (--l > 0) gel(N,l) = negi(gel(M,l));
     925                 :    1239668 :   return N;
     926                 :            : }
     927                 :            : GEN
     928                 :     187594 : zv_neg(GEN M)
     929                 :            : {
     930                 :            :   long l;
     931                 :     187594 :   GEN N = cgetg_copy(M, &l);
     932         [ +  + ]:    1593703 :   while (--l > 0) N[l] = -M[l];
     933                 :     187594 :   return N;
     934                 :            : }
     935                 :            : GEN
     936                 :        214 : zv_neg_inplace(GEN M)
     937                 :            : {
     938                 :        214 :   long l = lg(M);
     939         [ +  + ]:        840 :   while (--l > 0) M[l] = -M[l];
     940                 :        214 :   return M;
     941                 :            : }
     942                 :            : GEN
     943                 :       7350 : ZM_neg(GEN x)
     944                 :            : {
     945                 :            :   long l;
     946                 :       7350 :   GEN y = cgetg_copy(x, &l);
     947         [ +  + ]:      42693 :   while (--l > 0) gel(y,l) = ZC_neg(gel(x,l));
     948                 :       7350 :   return y;
     949                 :            : }
     950                 :            : 
     951                 :            : void
     952                 :     892142 : ZV_togglesign(GEN M)
     953                 :            : {
     954                 :     892142 :   long l = lg(M);
     955         [ +  + ]:   23899442 :   while (--l > 0) togglesign_safe(&gel(M,l));
     956                 :     892142 : }
     957                 :            : void
     958                 :          0 : ZM_togglesign(GEN M)
     959                 :            : {
     960                 :          0 :   long l = lg(M);
     961         [ #  # ]:          0 :   while (--l > 0) ZV_togglesign(gel(M,l));
     962                 :          0 : }
     963                 :            : 
     964                 :            : /********************************************************************/
     965                 :            : /**                                                                **/
     966                 :            : /**                        "DIVISION" mod HNF                      **/
     967                 :            : /**                                                                **/
     968                 :            : /********************************************************************/
     969                 :            : /* Reduce ZC x modulo ZM y in HNF, may return x itself (not a copy) */
     970                 :            : GEN
     971                 :     803832 : ZC_hnfremdiv(GEN x, GEN y, GEN *Q)
     972                 :            : {
     973                 :     803832 :   long i, l = lg(x);
     974                 :            :   GEN q;
     975                 :            : 
     976         [ +  + ]:     803832 :   if (Q) *Q = cgetg(l,t_COL);
     977         [ -  + ]:     803832 :   if (l == 1) return cgetg(1,t_COL);
     978         [ +  + ]:    4932398 :   for (i = l-1; i>0; i--)
     979                 :            :   {
     980                 :    4128566 :     q = diviiround(gel(x,i), gcoeff(y,i,i));
     981         [ +  + ]:    4128566 :     if (signe(q)) {
     982                 :    2303798 :       togglesign(q);
     983                 :    2303798 :       x = ZC_lincomb(gen_1, q, x, gel(y,i));
     984                 :            :     }
     985         [ +  + ]:    4128566 :     if (Q) gel(*Q, i) = q;
     986                 :            :   }
     987                 :     803832 :   return x;
     988                 :            : }
     989                 :            : 
     990                 :            : /* x = y Q + R, may return some columns of x (not copies) */
     991                 :            : GEN
     992                 :      29382 : ZM_hnfdivrem(GEN x, GEN y, GEN *Q)
     993                 :            : {
     994                 :      29382 :   long lx = lg(x), i;
     995                 :      29382 :   GEN R = cgetg(lx, t_MAT);
     996         [ +  + ]:      29382 :   if (Q)
     997                 :            :   {
     998                 :       3244 :     GEN q = cgetg(lx, t_MAT); *Q = q;
     999         [ +  + ]:       6068 :     for (i=1; i<lx; i++) gel(R,i) = ZC_hnfremdiv(gel(x,i),y,(GEN*)(q+i));
    1000                 :            :   }
    1001                 :            :   else
    1002         [ +  + ]:      99582 :     for (i=1; i<lx; i++)
    1003                 :            :     {
    1004                 :      73444 :       pari_sp av = avma;
    1005                 :      73444 :       GEN z = ZC_hnfrem(gel(x,i),y);
    1006         [ +  + ]:      73444 :       gel(R,i) = (avma == av)? ZC_copy(z): gerepileupto(av, z);
    1007                 :            :     }
    1008                 :      29382 :   return R;
    1009                 :            : }
    1010                 :            : 
    1011                 :            : 
    1012                 :            : /********************************************************************/
    1013                 :            : /**                                                                **/
    1014                 :            : /**                               TESTS                            **/
    1015                 :            : /**                                                                **/
    1016                 :            : /********************************************************************/
    1017                 :            : int
    1018                 :   13929006 : zv_equal0(GEN V)
    1019                 :            : {
    1020                 :   13929006 :   long l = lg(V);
    1021         [ +  + ]:   22053521 :   while (--l > 0)
    1022         [ +  + ]:   17506832 :     if (V[l]) return 0;
    1023                 :   13929006 :   return 1;
    1024                 :            : }
    1025                 :            : 
    1026                 :            : int
    1027                 :     316594 : ZV_equal0(GEN V)
    1028                 :            : {
    1029                 :     316594 :   long l = lg(V);
    1030         [ +  + ]:    1380958 :   while (--l > 0)
    1031         [ +  + ]:    1307318 :     if (signe(gel(V,l))) return 0;
    1032                 :     316594 :   return 1;
    1033                 :            : }
    1034                 :            : 
    1035                 :            : static int
    1036                 :    8970287 : ZV_equal_lg(GEN V, GEN W, long l)
    1037                 :            : {
    1038         [ +  + ]:   16193035 :   while (--l > 0)
    1039         [ +  + ]:   14233192 :     if (!equalii(gel(V,l), gel(W,l))) return 0;
    1040                 :    8970287 :   return 1;
    1041                 :            : }
    1042                 :            : int
    1043                 :    7768101 : ZV_equal(GEN V, GEN W)
    1044                 :            : {
    1045                 :    7768101 :   long l = lg(V);
    1046         [ -  + ]:    7768101 :   if (lg(W) != l) return 0;
    1047                 :    7768101 :   return ZV_equal_lg(V, W, l);
    1048                 :            : }
    1049                 :            : int
    1050                 :     381927 : ZM_equal(GEN A, GEN B)
    1051                 :            : {
    1052                 :     381927 :   long i, m, l = lg(A);
    1053         [ +  + ]:     381927 :   if (lg(B) != l) return 0;
    1054         [ -  + ]:     381661 :   if (l == 1) return 1;
    1055                 :     381661 :   m = lgcols(A);
    1056         [ -  + ]:     381661 :   if (lgcols(B) != m) return 0;
    1057         [ +  + ]:    1539996 :   for (i = 1; i < l; i++)
    1058         [ +  + ]:    1202186 :     if (!ZV_equal_lg(gel(A,i), gel(B,i), m)) return 0;
    1059                 :     381927 :   return 1;
    1060                 :            : }
    1061                 :            : int
    1062                 :    3208384 : zv_equal(GEN V, GEN W)
    1063                 :            : {
    1064                 :    3208384 :   long l = lg(V);
    1065         [ +  + ]:    3208384 :   if (lg(W) != l) return 0;
    1066         [ +  + ]:   21744534 :   while (--l > 0)
    1067         [ +  + ]:   18929562 :     if (V[l] != W[l]) return 0;
    1068                 :    3208384 :   return 1;
    1069                 :            : }
    1070                 :            : 
    1071                 :            : int
    1072                 :        315 : zvV_equal(GEN V, GEN W)
    1073                 :            : {
    1074                 :        315 :   long l = lg(V);
    1075         [ +  + ]:        315 :   if (lg(W) != l) return 0;
    1076         [ +  + ]:      58352 :   while (--l > 0)
    1077         [ +  + ]:      58170 :     if (!zv_equal(gel(V,l),gel(W,l))) return 0;
    1078                 :        315 :   return 1;
    1079                 :            : }
    1080                 :            : 
    1081                 :            : int
    1082                 :      52113 : ZM_ishnf(GEN x)
    1083                 :            : {
    1084                 :      52113 :   long i,j, lx = lg(x);
    1085         [ +  + ]:     243659 :   for (i=1; i<lx; i++)
    1086                 :            :   {
    1087                 :     199239 :     GEN xii = gcoeff(x,i,i);
    1088         [ +  + ]:     199239 :     if (signe(xii) <= 0) return 0;
    1089         [ +  + ]:     746800 :     for (j=1; j<i; j++)
    1090         [ -  + ]:     548156 :       if (signe(gcoeff(x,i,j))) return 0;
    1091         [ +  + ]:     777943 :     for (j=i+1; j<lx; j++)
    1092                 :            :     {
    1093                 :     586397 :       GEN xij = gcoeff(x,i,j);
    1094 [ +  + ][ +  + ]:     586397 :       if (signe(xij)<0 || cmpii(xij,xii)>=0) return 0;
    1095                 :            :     }
    1096                 :            :   }
    1097                 :      52113 :   return 1;
    1098                 :            : }
    1099                 :            : int
    1100                 :      93620 : ZM_isidentity(GEN x)
    1101                 :            : {
    1102                 :      93620 :   long i,j, lx = lg(x);
    1103                 :            : 
    1104         [ -  + ]:      93620 :   if (lx == 1) return 1;
    1105         [ -  + ]:      93620 :   if (lx != lgcols(x)) return 0;
    1106         [ +  + ]:     771254 :   for (j=1; j<lx; j++)
    1107                 :            :   {
    1108                 :     677634 :     GEN c = gel(x,j), t;
    1109         [ +  + ]:    3318678 :     for (i=1; i<j; )
    1110         [ -  + ]:    2641044 :       if (signe(gel(c,i++))) return 0;
    1111                 :            :     /* i = j */
    1112                 :     677634 :     t = gel(c,i++);
    1113 [ +  - ][ -  + ]:     677634 :       if (!is_pm1(t) || signe(t) < 0) return 0;
    1114         [ +  + ]:    3318678 :     for (   ; i<lx; )
    1115         [ -  + ]:    2641044 :       if (signe(gel(c,i++))) return 0;
    1116                 :            :   }
    1117                 :      93620 :   return 1;
    1118                 :            : }
    1119                 :            : 
    1120                 :            : long
    1121                 :      23247 : ZC_is_ei(GEN x)
    1122                 :            : {
    1123                 :      23247 :   long i, j = 0, l = lg(x);
    1124         [ +  + ]:     329707 :   for (i = 1; i < l; i++)
    1125                 :            :   {
    1126                 :     306460 :     GEN c = gel(x,i);
    1127                 :     306460 :     long s = signe(c);
    1128         [ +  + ]:     306460 :     if (!s) continue;
    1129 [ +  - ][ +  - ]:      23240 :     if (s < 0 || !is_pm1(c) || j) return 0;
                 [ -  + ]
    1130                 :      23240 :     j = i;
    1131                 :            :   }
    1132                 :      23247 :   return j;
    1133                 :            : }
    1134                 :            : 
    1135                 :            : /********************************************************************/
    1136                 :            : /**                                                                **/
    1137                 :            : /**                       MISCELLANEOUS                            **/
    1138                 :            : /**                                                                **/
    1139                 :            : /********************************************************************/
    1140                 :            : /* assume lg(x) = lg(y), x,y in Z^n */
    1141                 :            : int
    1142                 :     413823 : ZV_cmp(GEN x, GEN y)
    1143                 :            : {
    1144                 :     413823 :   long fl,i, lx = lg(x);
    1145         [ +  + ]:     977307 :   for (i=1; i<lx; i++)
    1146         [ +  + ]:     820427 :     if (( fl = cmpii(gel(x,i), gel(y,i)) )) return fl;
    1147                 :     413823 :   return 0;
    1148                 :            : }
    1149                 :            : /* assume lg(x) = lg(y), x,y in Z^n */
    1150                 :            : int
    1151                 :       3480 : ZV_abscmp(GEN x, GEN y)
    1152                 :            : {
    1153                 :       3480 :   long fl,i, lx = lg(x);
    1154         [ +  + ]:      19454 :   for (i=1; i<lx; i++)
    1155         [ +  + ]:      19374 :     if (( fl = absi_cmp(gel(x,i), gel(y,i)) )) return fl;
    1156                 :       3480 :   return 0;
    1157                 :            : }
    1158                 :            : 
    1159                 :            : long
    1160                 :     858596 : zv_content(GEN x)
    1161                 :            : {
    1162                 :     858596 :   long i, s, l = lg(x);
    1163         [ +  + ]:     858596 :   if (l == 1) return 0;
    1164                 :     858589 :   s = labs(x[1]);
    1165 [ +  + ][ +  + ]:    1790880 :   for (i=2; i<l && s!=1; i++) s = cgcd(x[i],s);
    1166                 :     858596 :   return s;
    1167                 :            : }
    1168                 :            : GEN
    1169                 :       2912 : ZV_content(GEN x)
    1170                 :            : {
    1171                 :       2912 :   long i, l = lg(x);
    1172                 :       2912 :   pari_sp av = avma;
    1173                 :            :   GEN c;
    1174         [ -  + ]:       2912 :   if (l == 1) return gen_0;
    1175         [ +  + ]:       2912 :   if (l == 2) return absi(gel(x,1));
    1176                 :       1295 :   c = gel(x,1);
    1177         [ +  + ]:       2814 :   for (i = 2; i < l; i++)
    1178                 :            :   {
    1179                 :       1869 :     c = gcdii(c, gel(x,i));
    1180         [ +  + ]:       1869 :     if (is_pm1(c)) { avma = av; return gen_1; }
    1181                 :            :   }
    1182                 :       2912 :   return gerepileuptoint(av, c);
    1183                 :            : }
    1184                 :            : 
    1185                 :            : GEN
    1186                 :     583648 : ZM_det_triangular(GEN mat)
    1187                 :            : {
    1188                 :            :   pari_sp av;
    1189                 :     583648 :   long i,l = lg(mat);
    1190                 :            :   GEN s;
    1191                 :            : 
    1192 [ +  + ][ +  + ]:     583648 :   if (l<3) return l<2? gen_1: icopy(gcoeff(mat,1,1));
    1193                 :     568448 :   av = avma; s = gcoeff(mat,1,1);
    1194         [ +  + ]:    1672740 :   for (i=2; i<l; i++) s = mulii(s,gcoeff(mat,i,i));
    1195                 :     583648 :   return gerepileuptoint(av,s);
    1196                 :            : }
    1197                 :            : 
    1198                 :            : /* assumes no overflow */
    1199                 :            : long
    1200                 :     304301 : zv_prod(GEN v)
    1201                 :            : {
    1202                 :     304301 :   long n, i, l = lg(v);
    1203         [ +  + ]:     304301 :   if (l == 1) return 1;
    1204         [ +  + ]:     345213 :   n = v[1]; for (i = 2; i < l; i++) n *= v[i];
    1205                 :     304301 :   return n;
    1206                 :            : }
    1207                 :            : 
    1208                 :            : static GEN
    1209                 :     928605 : _mulii(void *E, GEN a, GEN b)
    1210                 :     928605 : { (void) E; return mulii(a, b); }
    1211                 :            : 
    1212                 :            : /* product of ulongs */
    1213                 :            : GEN
    1214                 :     363706 : zv_prod_Z(GEN v)
    1215                 :            : {
    1216                 :     363706 :   pari_sp av = avma;
    1217                 :     363706 :   long k, n = lg(v)-1, m;
    1218                 :            :   GEN x;
    1219         [ +  + ]:     363706 :   if (n == 0) return gen_1;
    1220         [ +  + ]:     344260 :   if (n == 1) return utoi(v[1]);
    1221         [ +  + ]:     288274 :   if (n == 2) return muluu(v[1], v[2]);
    1222                 :     163618 :   m = n >> 1;
    1223         [ +  + ]:     163618 :   x = cgetg(m + (odd(n)? 2: 1), t_VEC);
    1224         [ +  + ]:     368186 :   for (k = 1; k <= m; k++) gel(x,k) = muluu(v[k<<1], v[(k<<1)-1]);
    1225         [ +  + ]:     163618 :   if (odd(n)) gel(x,k) = utoipos(v[n]);
    1226                 :     363706 :   return gerepileuptoint(av, gen_product(x, NULL, _mulii));
    1227                 :            : }
    1228                 :            : 
    1229                 :            : GEN
    1230                 :      26780 : ZV_prod(GEN v)
    1231                 :            : {
    1232                 :      26780 :   pari_sp av = avma;
    1233                 :      26780 :   long i, l = lg(v);
    1234                 :            :   GEN n;
    1235         [ +  + ]:      26780 :   if (l == 1) return gen_1;
    1236         [ +  + ]:      26108 :   if (l > 7) return gerepileuptoint(av, gen_product(v, NULL, _mulii));
    1237                 :      18393 :   n = gel(v,1);
    1238         [ +  + ]:      18393 :   if (l == 2) return icopy(n);
    1239         [ +  + ]:      31223 :   for (i = 2; i < l; i++) n = mulii(n, gel(v,i));
    1240                 :      26780 :   return gerepileuptoint(av, n);
    1241                 :            : }
    1242                 :            : /* assumes no overflow */
    1243                 :            : long
    1244                 :        196 : zv_sum(GEN v)
    1245                 :            : {
    1246                 :        196 :   long n, i, l = lg(v);
    1247         [ +  + ]:        196 :   if (l == 1) return 0;
    1248         [ +  + ]:        959 :   n = v[1]; for (i = 2; i < l; i++) n += v[i];
    1249                 :        196 :   return n;
    1250                 :            : }
    1251                 :            : GEN
    1252                 :         56 : ZV_sum(GEN v)
    1253                 :            : {
    1254                 :         56 :   pari_sp av = avma;
    1255                 :         56 :   long i, l = lg(v);
    1256                 :            :   GEN n;
    1257         [ -  + ]:         56 :   if (l == 1) return gen_0;
    1258                 :         56 :   n = gel(v,1);
    1259         [ -  + ]:         56 :   if (l == 2) return icopy(n);
    1260         [ +  + ]:        518 :   for (i = 2; i < l; i++) n = addii(n, gel(v,i));
    1261                 :         56 :   return gerepileuptoint(av, n);
    1262                 :            : }
    1263                 :            : 
    1264                 :            : /********************************************************************/
    1265                 :            : /**                                                                **/
    1266                 :            : /**         GRAM SCHMIDT REDUCTION (integer matrices)              **/
    1267                 :            : /**                                                                **/
    1268                 :            : /********************************************************************/
    1269                 :            : 
    1270                 :            : /* L[k,] += q * L[l,], l < k. Inefficient if q = 0 */
    1271                 :            : static void
    1272                 :     173023 : Zupdate_row(long k, long l, GEN q, GEN L, GEN B)
    1273                 :            : {
    1274                 :     173023 :   long i, qq = itos_or_0(q);
    1275         [ +  + ]:     173023 :   if (!qq)
    1276                 :            :   {
    1277         [ +  + ]:      18215 :     for(i=1;i<l;i++)  gcoeff(L,k,i) = addii(gcoeff(L,k,i),mulii(q,gcoeff(L,l,i)));
    1278                 :       5062 :     gcoeff(L,k,l) = addii(gcoeff(L,k,l), mulii(q,B));
    1279                 :     173023 :     return;
    1280                 :            :   }
    1281         [ +  + ]:     167961 :   if (qq == 1) {
    1282         [ +  + ]:      61559 :     for (i=1;i<l; i++) gcoeff(L,k,i) = addii(gcoeff(L,k,i),gcoeff(L,l,i));
    1283                 :      34297 :     gcoeff(L,k,l) = addii(gcoeff(L,k,l), B);
    1284         [ +  + ]:     133664 :   } else if (qq == -1) {
    1285         [ +  + ]:     152477 :     for (i=1;i<l; i++) gcoeff(L,k,i) = subii(gcoeff(L,k,i),gcoeff(L,l,i));
    1286                 :      81422 :     gcoeff(L,k,l) = addii(gcoeff(L,k,l), negi(B));
    1287                 :            :   } else {
    1288         [ +  + ]:     111874 :     for(i=1;i<l;i++) gcoeff(L,k,i) = addii(gcoeff(L,k,i),mulsi(qq,gcoeff(L,l,i)));
    1289                 :      52242 :     gcoeff(L,k,l) = addii(gcoeff(L,k,l), mulsi(qq,B));
    1290                 :            :   }
    1291                 :            : }
    1292                 :            : 
    1293                 :            : /* update L[k,] */
    1294                 :            : static void
    1295                 :     542165 : ZRED(long k, long l, GEN x, GEN L, GEN B)
    1296                 :            : {
    1297                 :     542165 :   GEN q = truedivii(addii(B,shifti(gcoeff(L,k,l),1)), shifti(B,1));
    1298         [ +  + ]:     715188 :   if (!signe(q)) return;
    1299                 :     173023 :   q = negi(q);
    1300                 :     173023 :   Zupdate_row(k,l,q,L,B);
    1301                 :     173023 :   gel(x,k) = ZC_lincomb(gen_1, q, gel(x,k), gel(x,l));
    1302                 :            : }
    1303                 :            : 
    1304                 :            : /* Gram-Schmidt reduction, x a ZM */
    1305                 :            : static void
    1306                 :     725051 : ZincrementalGS(GEN x, GEN L, GEN B, long k)
    1307                 :            : {
    1308                 :            :   long i, j;
    1309         [ +  + ]:    2605352 :   for (j=1; j<=k; j++)
    1310                 :            :   {
    1311                 :    1880301 :     pari_sp av = avma;
    1312                 :    1880301 :     GEN u = ZV_dotproduct(gel(x,k), gel(x,j));
    1313         [ +  + ]:    4426903 :     for (i=1; i<j; i++)
    1314                 :            :     {
    1315                 :    2546602 :       u = subii(mulii(gel(B,i+1), u), mulii(gcoeff(L,k,i), gcoeff(L,j,i)));
    1316                 :    2546602 :       u = diviiexact(u, gel(B,i));
    1317                 :            :     }
    1318                 :    1880301 :     gcoeff(L,k,j) = gerepileuptoint(av, u);
    1319                 :            :   }
    1320                 :     725051 :   gel(B,k+1) = gcoeff(L,k,k); gcoeff(L,k,k) = gen_1;
    1321                 :     725051 : }
    1322                 :            : 
    1323                 :            : /* Variant reducemodinvertible(ZC v, ZM y), when y singular.
    1324                 :            :  * Very inefficient if y is not LLL-reduced of maximal rank */
    1325                 :            : static GEN
    1326                 :     187219 : ZC_reducemodmatrix_i(GEN v, GEN y)
    1327                 :            : {
    1328                 :     187219 :   GEN B, L, x = shallowconcat(y, v);
    1329                 :     187219 :   long k, lx = lg(x), nx = lx-1;
    1330                 :            : 
    1331                 :     187219 :   B = scalarcol_shallow(gen_1, lx);
    1332                 :     187219 :   L = zeromatcopy(nx, nx);
    1333         [ +  + ]:     891333 :   for (k=1; k <= nx; k++) ZincrementalGS(x, L, B, k);
    1334         [ +  + ]:     704114 :   for (k = nx-1; k >= 1; k--) ZRED(nx,k, x,L,gel(B,k+1));
    1335                 :     187219 :   return gel(x,nx);
    1336                 :            : }
    1337                 :            : GEN
    1338                 :     187219 : ZC_reducemodmatrix(GEN v, GEN y) {
    1339                 :     187219 :   pari_sp av = avma;
    1340                 :     187219 :   return gerepilecopy(av, ZC_reducemodmatrix_i(v,y));
    1341                 :            : }
    1342                 :            : 
    1343                 :            : /* Variant reducemodinvertible(ZM v, ZM y), when y singular.
    1344                 :            :  * Very inefficient if y is not LLL-reduced of maximal rank */
    1345                 :            : static GEN
    1346                 :       4641 : ZM_reducemodmatrix_i(GEN v, GEN y)
    1347                 :            : {
    1348                 :            :   GEN B, L, V;
    1349                 :       4641 :   long j, k, lv = lg(v), nx = lg(y), lx = nx+1;
    1350                 :            : 
    1351                 :       4641 :   V = cgetg(lv, t_MAT);
    1352                 :       4641 :   B = scalarcol_shallow(gen_1, lx);
    1353                 :       4641 :   L = zeromatcopy(nx, nx);
    1354         [ +  + ]:      15302 :   for (k=1; k < nx; k++) ZincrementalGS(y, L, B, k);
    1355         [ +  + ]:      14917 :   for (j = 1; j < lg(v); j++)
    1356                 :            :   {
    1357                 :      10276 :     GEN x = shallowconcat(y, gel(v,j));
    1358                 :      10276 :     ZincrementalGS(x, L, B, nx); /* overwrite last */
    1359         [ +  + ]:      35546 :     for (k = nx-1; k >= 1; k--) ZRED(nx,k, x,L,gel(B,k+1));
    1360                 :      10276 :     gel(V,j) = gel(x,nx);
    1361                 :            :   }
    1362                 :       4641 :   return V;
    1363                 :            : }
    1364                 :            : GEN
    1365                 :       4641 : ZM_reducemodmatrix(GEN v, GEN y) {
    1366                 :       4641 :   pari_sp av = avma;
    1367                 :       4641 :   return gerepilecopy(av, ZM_reducemodmatrix_i(v,y));
    1368                 :            : }
    1369                 :            : 
    1370                 :            : GEN
    1371                 :     186624 : ZC_reducemodlll(GEN x,GEN y)
    1372                 :            : {
    1373                 :     186624 :   pari_sp av = avma;
    1374                 :     186624 :   GEN z = ZC_reducemodmatrix(x, ZM_lll(y, 0.75, LLL_INPLACE));
    1375                 :     186624 :   return gerepilecopy(av, z);
    1376                 :            : }
    1377                 :            : GEN
    1378                 :          0 : ZM_reducemodlll(GEN x,GEN y)
    1379                 :            : {
    1380                 :          0 :   pari_sp av = avma;
    1381                 :          0 :   GEN z = ZM_reducemodmatrix(x, ZM_lll(y, 0.75, LLL_INPLACE));
    1382                 :          0 :   return gerepilecopy(av, z);
    1383                 :            : }

Generated by: LCOV version 1.9