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 - random.c (source / functions) Hit Total Coverage
Test: PARI/GP v2.8.0 lcov report (development 16375-9f41ae0) Lines: 100 100 100.0 %
Date: 2014-04-19 Functions: 10 10 100.0 %
Legend: Lines: hit not hit | Branches: + taken - not taken # not executed Branches: 76 90 84.4 %

           Branch data     Line data    Source code
       1                 :            : /* Copyright (C) 2000  The PARI group.
       2                 :            : 
       3                 :            : This file is part of the PARI/GP package.
       4                 :            : 
       5                 :            : PARI/GP is free software; you can redistribute it and/or modify it under the
       6                 :            : terms of the GNU General Public License as published by the Free Software
       7                 :            : Foundation. It is distributed in the hope that it will be useful, but WITHOUT
       8                 :            : ANY WARRANTY WHATSOEVER.
       9                 :            : 
      10                 :            : Check the License for details. You should have received a copy of it, along
      11                 :            : with the package; see the file 'COPYING'. If not, write to the Free Software
      12                 :            : Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. */
      13                 :            : /********************************************************************/
      14                 :            : /*                                                                  */
      15                 :            : /*                      PSEUDO-RANDOM INTEGERS                      */
      16                 :            : /*                                                                  */
      17                 :            : /********************************************************************/
      18                 :            : #include "pari.h"
      19                 :            : #include "paripriv.h"
      20                 :            : /********************************************************************/
      21                 :            : /*                    XORGEN (Richard P. Brent)                     */
      22                 :            : /*          http://wwwmaths.anu.edu.au/~brent/random.html           */
      23                 :            : /*        (initial adaptation to PARI/GP by Randall Rathbun)        */
      24                 :            : /********************************************************************/
      25                 :            : /* Adapted from xorgens.c version 3.04, Richard P. Brent, 20060628 (GPL).
      26                 :            :  * 32-bit or 64-bit integer random number generator with period at
      27                 :            :  * least 2**4096-1. It is assumed that "ulong" is a 32-bit or 64-bit integer */
      28                 :            : static THREAD ulong xorgen_w;
      29                 :            : static THREAD int xorgen_i;
      30                 :            : 
      31                 :            : #ifdef LONG_IS_64BIT /* weyl = odd approximation to 2^BIL*(sqrt(5)-1)/2. */
      32                 :            :   static const ulong weyl = 0x61c8864680b583ebUL;
      33                 :            :   static const int ws = 27, r = 64,  s = 53, a = 33, b = 26, c = 27, d = 29;
      34                 :            :   static THREAD ulong state[64]; /* size r */
      35                 :            : #else
      36                 :            :   static const ulong weyl = 0x61c88647UL;
      37                 :            :   static const int ws = 16, r = 128, s = 95, a = 17, b = 12, c = 13, d = 15;
      38                 :            :   static THREAD ulong state[128]; /* size r */
      39                 :            : #endif
      40                 :            : 
      41                 :            : static void
      42                 :       1818 : init_xor4096i(ulong seed)
      43                 :            : {
      44                 :       1818 :   ulong t, v = seed;  /* v must be nonzero */
      45                 :            :   int k;
      46                 :            : 
      47         [ +  + ]:     110042 :   for (k = BITS_IN_LONG; k > 0; k--) {/* Avoid correlations for close seeds */
      48                 :     108224 :     v ^= v<<10; v ^= v>>15;      /* Recurrence has period 2**BIL -1 */
      49                 :     108224 :     v ^= v<<4;  v ^= v>>13;
      50                 :            :   }
      51         [ +  + ]:     134426 :   for (xorgen_w = v, k = 0; k < r; k++) { /* Initialise circular array */
      52                 :     132608 :     v ^= v<<10; v ^= v>>15;
      53                 :     132608 :     v ^= v<<4;  v ^= v>>13;
      54                 :     132608 :     state[k] = v + (xorgen_w+=weyl);
      55                 :            :   }
      56         [ +  + ]:     532250 :   for (xorgen_i = r-1, k = 4*r; k > 0; k--) { /* Discard first 4*r results */
      57                 :     530432 :     t = state[xorgen_i = (xorgen_i+1)&(r-1)]; t ^= t<<a;  t ^= t>>b;
      58                 :     530432 :     v = state[(xorgen_i+(r-s))&(r-1)];        v ^= v<<c;  v ^= v>>d;
      59                 :     530432 :     state[xorgen_i] = t^v;
      60                 :            :   }
      61                 :       1818 : }
      62                 :            : 
      63                 :       1153 : void pari_init_rand(void) { init_xor4096i(1); }
      64                 :            : 
      65                 :            : /* One random number uniformly distributed in [0..2**BIL) is returned, where
      66                 :            :  * BIL = 8*sizeof(ulong) = 32 or 64. */
      67                 :            : ulong
      68                 :   17965352 : pari_rand(void)
      69                 :            : {
      70                 :            :   ulong t, v;
      71                 :            : 
      72                 :   17965352 :   t = state[xorgen_i = (xorgen_i+1)&(r-1)];
      73                 :   17965352 :   v = state[(xorgen_i+(r-s))&(r-1)];   /* Index is (xorgen_i-s) mod r */
      74                 :   17965352 :   t ^= t<<a;  t ^= t>>b;               /* (I + L^a)(I + R^b) */
      75                 :   17965352 :   v ^= v<<c;  v ^= v>>d;               /* (I + L^c)(I + R^d) */
      76                 :   17965352 :   state[xorgen_i] = (v ^= t);          /* Update circular array */
      77                 :   17965352 :   xorgen_w += weyl;                    /* Update Weyl generator */
      78                 :   17965352 :   return v + (xorgen_w ^ (xorgen_w>>ws));
      79                 :            : }
      80                 :            : 
      81                 :            : void
      82                 :        672 : setrand(GEN seed) {
      83      [ +  +  - ]:        672 :   switch (typ(seed))
      84                 :            :   {
      85                 :            :     case t_VECSMALL:
      86                 :            :     {
      87                 :          7 :       GEN xd = seed+1;
      88                 :            :       long i;
      89         [ -  + ]:          7 :       if (lg(seed) != r+2 + 1) break;
      90         [ +  + ]:        519 :       for (i = 0; i < r; i++) state[i] = xd[i];
      91                 :          7 :       xorgen_i = xd[i++];
      92                 :          7 :       xorgen_w = xd[i++];
      93                 :          7 :       return;
      94                 :            :     }
      95         [ +  - ]:        665 :     case t_INT: if (signe(seed) > 0) { init_xor4096i( itou(seed) ); return; }
      96                 :            :   }
      97                 :        672 :   pari_err_TYPE("setrand",seed);
      98                 :            : }
      99                 :            : GEN
     100                 :     267775 : getrand(void) {
     101                 :            :   GEN x, xd;
     102                 :            :   long i;
     103         [ -  + ]:     267775 :   if (xorgen_i < 0) init_xor4096i(1);
     104                 :            : 
     105                 :     267775 :   x = cgetg(r+2 + 1, t_VECSMALL); xd = x+1;
     106         [ +  + ]:   19561215 :   for (i = 0; i < r; i++) xd[i] = state[i];
     107                 :     267775 :   xd[i++] = xorgen_i;
     108                 :     267775 :   xd[i++] = xorgen_w;
     109                 :     267775 :   return x;
     110                 :            : }
     111                 :            : 
     112                 :            : /********************************************************************/
     113                 :            : /*                                                                  */
     114                 :            : /*                         GENERIC ROUTINES                         */
     115                 :            : /*                                                                  */
     116                 :            : /********************************************************************/
     117                 :            : 
     118                 :            : /* assume n > 0 */
     119                 :            : ulong
     120                 :    7130286 : random_Fl(ulong n)
     121                 :            : {
     122                 :            :   ulong d;
     123                 :            :   int shift;
     124                 :            : 
     125         [ -  + ]:    7130286 :   if (n == 1) return 0;
     126                 :            : 
     127 [ +  + ][ +  + ]:    7130286 :   shift = bfffo(n); /* 2^(BIL-shift) > n >= 2^(BIL-shift-1)*/
         [ +  + ][ +  + ]
     128                 :            :   /* if N a power of 2, increment shift. No reject */
     129 [ +  + ][ +  + ]:    7130286 :   if ((n << shift) == HIGHBIT) return pari_rand() >> (shift+1);
     130                 :            :   for (;;) {
     131                 :    8460762 :     d = pari_rand() >> shift; /* d < 2^(BIL-shift) uniformly distributed */
     132                 :            :     /* reject strategy: proba success = n 2^(shift-BIL), in [1/2, 1[ */
     133         [ +  + ]:    8460762 :     if (d < n) return d;
     134                 :    9099268 :   }
     135                 :            : }
     136                 :            : 
     137                 :            : /* assume N > 0, see random_Fl() for algorithm */
     138                 :            : GEN
     139                 :    2787294 : randomi(GEN N)
     140                 :            : {
     141                 :    2787294 :   long lx = lgefint(N);
     142                 :            :   GEN d, NMSW;
     143                 :            :   pari_sp av;
     144                 :            :   int shift;
     145                 :            : 
     146         [ +  + ]:    2787294 :   if (lx == 3) return utoi( random_Fl(N[2]) );
     147                 :            : 
     148 [ +  + ][ +  + ]:      19035 :   NMSW = int_MSW(N); shift = bfffo(*NMSW);
         [ +  + ][ +  + ]
     149 [ +  + ][ +  + ]:      19035 :   if (((ulong)*NMSW << shift) == HIGHBIT)
     150                 :            :   { /* if N a power of 2, increment shift */
     151         [ +  + ]:      16639 :     for (d = int_LSW(N); !*d; d = int_nextW(d)) /* empty */;
     152 [ +  + ][ +  - ]:      16624 :     if (d == NMSW && ++shift == BITS_IN_LONG) { shift = 0; lx--; }
     153                 :            :   }
     154                 :      19035 :   for (av = avma;; avma = av) {
     155                 :      36750 :     GEN x = cgetipos(lx), xMSW = int_MSW(x);
     156         [ +  + ]:      78582 :     for (d = int_LSW(x); d != xMSW; d = int_nextW(d)) *d = pari_rand();
     157                 :      36750 :     *d = pari_rand() >> shift;
     158                 :      36750 :     x = int_normalize(x, 0);
     159         [ +  + ]:      36750 :     if (absi_cmp(x, N) < 0) return x;
     160                 :    2805009 :   }
     161                 :            : }
     162                 :            : 
     163                 :            : GEN
     164                 :          7 : randomr(long prec)
     165                 :            : {
     166                 :            :   pari_sp av;
     167                 :            :   long b;
     168                 :            :   GEN x, y;
     169         [ -  + ]:          7 :   if (prec <= 2) return real_0_bit(0);
     170                 :          7 :   x = cgetr(prec); av = avma;
     171                 :          7 :   b = prec2nbits(prec);
     172                 :          7 :   y = randomi(int2n(b));
     173         [ -  + ]:          7 :   if (!signe(y)) return real_0_bit(b);
     174                 :          7 :   affir(y, x); shiftr_inplace(x, - b);
     175                 :          7 :   avma = av; return x;
     176                 :            : }
     177                 :            : 
     178                 :            : static GEN
     179                 :          7 : polrandom(GEN N) /* assume N!=0 */
     180                 :            : {
     181                 :          7 :   long i, d = lg(N);
     182                 :          7 :   GEN z = leading_term(N);
     183                 :          7 :   GEN y = cgetg(d,t_POL);
     184                 :          7 :   y[1] = evalsigne(1) | evalvarn(varn(N));
     185         [ +  + ]:         49 :   for (i=2; i<d; i++) gel(y,i) = genrand(z);
     186                 :          7 :   return normalizepol_lg(y,d);
     187                 :            : }
     188                 :            : 
     189                 :            : GEN
     190                 :    2729357 : genrand(GEN N)
     191                 :            : {
     192                 :            :   GEN z;
     193         [ +  + ]:    2729357 :   if (!N) return utoi( random_bits(31) );
     194   [ +  +  +  +  :    2727992 :   switch(typ(N))
                +  +  + ]
     195                 :            :   {
     196                 :            :     case t_INT:
     197         [ +  + ]:    2102024 :       if (signe(N)<=0) pari_err_DOMAIN("random","N","<=",gen_0,gen_0);
     198                 :    2102017 :       return randomi(N);
     199                 :            :     case t_REAL:
     200                 :          7 :       return randomr(realprec(N));
     201                 :            :     case t_INTMOD:
     202                 :     520201 :       z = cgetg(3, t_INTMOD);
     203                 :     520201 :       gel(z,1) = icopy(gel(N,1));
     204                 :     520201 :       gel(z,2) = randomi(gel(N,1)); return z;
     205                 :            :     case t_FFELT:
     206                 :      12086 :       return ffrandom(N);
     207                 :            :     case t_POL:
     208         [ -  + ]:          7 :       if (signe(N)==0) return pol_0(varn(N));
     209                 :          7 :       return polrandom(N);
     210                 :            :     case t_VEC:
     211         [ +  + ]:      93660 :       if (lg(N) == 3)
     212                 :            :       {
     213                 :         70 :         pari_sp av = avma;
     214                 :         70 :         GEN a = gel(N,1), b = gel(N,2), d;
     215         [ -  + ]:         70 :         if (typ(a) != t_INT) a = gceil(a);
     216         [ -  + ]:         70 :         if (typ(b) != t_INT) b = gfloor(b);
     217 [ +  - ][ -  + ]:         70 :         if (typ(a) != t_INT || typ(b) != t_INT) pari_err_TYPE("random", N);
     218                 :         70 :         d = subii(b,a);
     219         [ -  + ]:         70 :         if (signe(d) < 0) pari_err_TYPE("random([a,b]) (a > b)", N);
     220                 :         70 :         return gerepileuptoint(av, addii(a, randomi(addis(d,1))));
     221                 :            :       }
     222                 :      93590 :       return ellrandom(N);
     223                 :            :     default:
     224                 :          7 :       pari_err_TYPE("genrand",N);
     225                 :    2729343 :       return NULL;/*not reached*/
     226                 :            :   }
     227                 :            : }

Generated by: LCOV version 1.9