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-bordeaux.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 - matperm.c (source / functions) Hit Total Coverage
Test: PARI/GP v2.10.0 lcov report (development 21343-6216058) Lines: 76 76 100.0 %
Date: 2017-11-19 06:21:17 Functions: 4 4 100.0 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : /* Copyright (C) 2016 The PARI group.
       2             : 
       3             : This file is part of the PARI/GP package.
       4             : 
       5             : PARI/GP is free software; you can redistribute it and/or modify it under the
       6             : terms of the GNU General Public License as published by the Free Software
       7             : Foundation. It is distributed in the hope that it will be useful, but WITHOUT
       8             : ANY WARRANTY WHATSOEVER.
       9             : 
      10             : Check the License for details. You should have received a copy of it, along
      11             : with the package; see the file 'COPYING'. If not, write to the Free Software
      12             : Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. */
      13             : 
      14             : /********************************************************************/
      15             : /**                                                                **/
      16             : /**             MATRIX PERMANENT, via RYSER'S FORMULA              **/
      17             : /**            (initial implementation: C. Greathouse)             **/
      18             : /**                                                                **/
      19             : /********************************************************************/
      20             : #include "pari.h"
      21             : #include "paripriv.h"
      22             : 
      23             : /* Ryser's formula */
      24             : GEN
      25         154 : matpermanent(GEN M)
      26             : {
      27             :   pari_sp av;
      28         154 :   long n = lg(M)-1, i, x, upper;
      29             :   GEN p, in;
      30         154 :   if (typ(M) != t_MAT) pari_err_TYPE("matpermanent", M);
      31         154 :   if (!n) return gen_1;
      32         147 :   if (n != nbrows(M)) pari_err_DIM("matpermanent");
      33             : #ifdef LONG_IS_64BIT /* because of vals(long x) => x <= LONG_MAX */
      34         120 :   if (n > 63) pari_err_IMPL("large matrix permanent");
      35             : #else
      36          20 :   if (n > 31) pari_err_IMPL("large matrix permanent");
      37             : #endif
      38         133 :   if (n == 1) return gcopy(gcoeff(M,1,1));
      39             : 
      40         112 :   av = avma;
      41         112 :   if (RgM_is_QM(M))
      42             :   {
      43             :     GEN cM;
      44          98 :     M = Q_primitive_part(M, &cM);
      45          98 :     p = ZM_permanent(M);
      46          98 :     if (cM) p = gerepileupto(av, gmul(p, gpowgs(cM,n)));
      47          98 :     return p;
      48             :   }
      49             : 
      50          14 :   p = gen_0;
      51          14 :   in = const_vec(n, gen_0);
      52          14 :   upper = 1L << n;
      53         112 :   for (x = 1; x < upper; x++)
      54             :   {
      55          98 :     long gray = x ^ (x>>1), k = vals(x);
      56          98 :     GEN col = gel(M,k+1);
      57          98 :     if (gray & (1L<<k))
      58          56 :     { for (i=1; i <= n; ++i) gel(in, i) = gadd(gel(in, i), gel(col, i)); }
      59             :     else
      60          42 :     { for (i=1; i <= n; ++i) gel(in, i) = gsub(gel(in, i), gel(col, i)); }
      61          98 :     if (hammingl(gray)&1)
      62          56 :       p = gsub(p, RgV_prod(in));
      63             :     else
      64          42 :       p = gadd(p, RgV_prod(in));
      65          98 :     if (gc_needed(av, 1)) gerepileall(av, 2, &in, &p);
      66             :   }
      67          14 :   if (n&1) p = gneg(p);
      68          14 :   return gerepileupto(av, p);
      69             : }
      70             : 
      71             : /* ||M||_oo = max_i \sum_j | M[i,j] | */
      72             : static GEN
      73          98 : ZM_normoo(GEN M)
      74             : {
      75          98 :   long i, j, m, l = lg(M);
      76          98 :   GEN N = NULL;
      77          98 :   if (l == 1) return gen_0;
      78          98 :   m = lgcols(M);
      79         938 :   for (i = 1; i < m; i++)
      80             :   {
      81         840 :     GEN s = mpabs_shallow(gcoeff(M,i,1));
      82         840 :     for (j = 2; j < l; j++) s = addii(s, mpabs_shallow(gcoeff(M,i,j)));
      83         840 :     if (!N || abscmpii(N, s) < 0) N = s;
      84             :   }
      85          98 :   return N;
      86             : }
      87             : 
      88             : /* Assumes M square; dimensions <= 31x31 (32-bit) or 63x63 (64-bit). */
      89             : GEN
      90          98 : ZM_permanent(GEN M)
      91             : {
      92          98 :   pari_sp av = avma;
      93             :   GEN p, in;
      94          98 :   long i, x, upper, n = lg(M)-1;
      95          98 :   if (!is_bigint(ZM_normoo(M)))
      96          91 :     return gerepileuptoint(av, zm_permanent(ZM_to_zm(M)));
      97           7 :   p = gen_0;
      98           7 :   in = const_col(n, gen_0);
      99           7 :   upper = (1L<<n);
     100     7340032 :   for (x = 1; x < upper; x++)
     101             :   {
     102     7340025 :     long gray = x ^ (x>>1), k = vals(x);
     103     7340025 :     GEN c, col = gel(M, k+1);
     104     7340025 :     if (gray & (1L<<k))
     105     3670016 :     { for (i=1; i <= n; ++i) gel(in, i) = addii(gel(in,i), gel(col,i)); }
     106             :     else
     107     3670009 :     { for (i=1; i <= n; ++i) gel(in, i) = subii(gel(in,i), gel(col,i)); }
     108     7340025 :     c = ZV_prod(in);
     109     7340025 :     if (hammingl(gray)&1) togglesign_safe(&c);
     110     7340025 :     p = addii(p, c);
     111     7340025 :     if (gc_needed(av, 1)) gerepileall(av, 2, &in, &p);
     112             :   }
     113           7 :   if (n&1) togglesign_safe(&p);
     114           7 :   return gerepilecopy(av, p);
     115             : }
     116             : 
     117             : /* Assumes M square; dimensions <= 31x31 (32-bit) or 63x63 (64-bit). */
     118             : GEN
     119          91 : zm_permanent(GEN M)
     120             : {
     121          91 :   pari_sp av = avma;
     122          91 :   long x, n = lg(M)-1, upper = (1L<<n);
     123          91 :   GEN p = gen_0, in = const_vecsmall(n, 0);
     124          91 :   pari_sp av2 = avma;
     125    14694484 :   for (x = 1; x < upper; x++)
     126             :   {
     127    14694393 :     long i, gray = x ^ (x>>1), k = vals(x);
     128    14694393 :     GEN c, col = gel(M, k+1);
     129    14694393 :     if (gray & (1L<<k))
     130     7347242 :     { for (i = 1; i <= n; ++i) in[i] += col[i]; }
     131             :     else
     132     7347151 :     { for (i = 1; i <= n; ++i) in[i] -= col[i]; }
     133    14694393 :     c = vecsmall_prod(in);
     134    14694393 :     if (hammingl(gray)&1) togglesign_safe(&c);
     135    14694393 :     p = addii(p, c);
     136    14694393 :     if (gc_needed(av2, 1)) p = gerepileuptoint(av2, p);
     137             :   }
     138          91 :   if (n&1) togglesign_safe(&p);
     139          91 :   return gerepileuptoint(av, p);
     140             : }

Generated by: LCOV version 1.11