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 17236-ec2ebc9) Lines: 136 138 98.6 %
Date: 2014-12-19 Functions: 16 16 100.0 %
Legend: Lines: hit not hit | Branches: + taken - not taken # not executed Branches: 95 109 87.2 %

           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                 :            : 
      29                 :            : #ifdef LONG_IS_64BIT
      30                 :            :   typedef ulong u64;
      31                 :            :   static THREAD ulong state[64];
      32                 :            :   #define u64state(i)      ((u64)state[(i)])
      33                 :            :   #define u64stateset(i,x) state[(i)] = (ulong) (x);
      34                 :            : #else
      35                 :            :   typedef unsigned long long u64;
      36                 :            :   static THREAD ulong state[128];
      37                 :            :   #define u64state(i)      _32to64(state[2*(i)],state[2*(i)+1])
      38                 :            :   #define u64stateset(i,x) _64to32(x,state+2*(i),state+2*(i)+1)
      39                 :            : static u64
      40                 :    6556269 : _32to64(ulong a, ulong b) { u64 v = a; return (v<<32)|b; }
      41                 :            : static void
      42                 :    3369903 : _64to32(u64 v, ulong *a, ulong *b) { *a = v>>32; *b = v&0xFFFFFFFF; }
      43                 :            : #endif
      44                 :            : static THREAD u64 xorgen_w;
      45                 :            : static THREAD int xorgen_i;
      46                 :            : /* weyl = odd approximation to 2^64*(sqrt(5)-1)/2. */
      47                 :            : static const u64 weyl = (((u64)0x61c88646U)<<32)|((u64)0x80b583ebU);
      48                 :            : 
      49                 :            : static u64
      50                 :   22945143 : block(void)
      51                 :            : {
      52                 :   22945143 :   const int r = 64;
      53                 :   22945143 :   const int a = 33, b = 26, c = 27, d = 29, s = 53;
      54                 :            :   u64 t, v, w;
      55                 :   22945143 :   xorgen_i = (xorgen_i+1)&(r-1);
      56                 :   22945143 :   t = u64state(xorgen_i);
      57                 :   22945143 :   v = u64state((xorgen_i+(r-s))&(r-1));   /* index is (i-s) mod r */
      58                 :   22945143 :   t ^= t<<a; t ^= t>>b;                   /* (I + L^a)(I + R^b) */
      59                 :   22945143 :   v ^= v<<c; v ^= v>>d;                   /* (I + L^c)(I + R^d) */
      60                 :   22945143 :   w = t^v;
      61                 :   22945143 :   u64stateset(xorgen_i, w);               /* update circular array */
      62                 :   22945143 :   return w;
      63                 :            : }
      64                 :            : 
      65                 :            : static void
      66                 :       5191 : init_xor4096i(ulong seed)
      67                 :            : {
      68                 :       5191 :   const int r = 64;
      69                 :       5191 :   u64 v = seed; /* v must be nonzero */
      70                 :            :   int k;
      71                 :            : 
      72         [ +  + ]:     337415 :   for (k = r; k > 0; k--) {/* avoid correlations for close seeds */
      73                 :     332224 :     v ^= v<<10; v ^= v>>15; /* recurrence has period 2**64-1 */
      74                 :     332224 :     v ^= v<<4;  v ^= v>>13;
      75                 :            :   }
      76 [ +  + ][ +  + ]:     337415 :   for (xorgen_w = v, k = 0; k < r; k++) { /* initialise circular array */
      77                 :     332224 :     v ^= v<<10; v ^= v>>15;
      78                 :     332224 :     v ^= v<<4;  v ^= v>>13;
      79                 :     332224 :     u64stateset(k, v + (xorgen_w+=weyl));
      80                 :            :   }
      81                 :            :   /* discard first 4*r results */
      82         [ +  + ]:    1334087 :   for (xorgen_i = r-1, k = 4*r; k > 0; k--) (void)block();
      83                 :       5191 : }
      84                 :            : 
      85                 :       1243 : void pari_init_rand(void) { init_xor4096i(1); }
      86                 :            : 
      87                 :            : static u64
      88                 :   21616247 : rand64(void)
      89                 :            : {
      90                 :   21616247 :   u64 v = block();
      91                 :   21616247 :   xorgen_w += weyl; /* update Weyl generator */
      92                 :   21616247 :   return v + (xorgen_w ^ (xorgen_w>>27));
      93                 :            : }
      94                 :            : 
      95                 :            : /* One random number uniformly distributed in [0..2**BIL) is returned, where
      96                 :            :  * BIL = 8*sizeof(ulong) = 32 or 64. */
      97                 :            : ulong
      98                 :         20 : pari_rand(void) { return rand64(); }
      99                 :            : 
     100                 :            : void
     101                 :       4003 : setrand(GEN x)
     102                 :            : {
     103                 :       4003 :   const int r2 = sizeof(state)/sizeof(ulong);
     104                 :            :   ulong useed;
     105                 :            :   long i;
     106                 :            :   GEN xp;
     107         [ -  + ]:       4003 :   if (typ(x)!=t_INT)
     108                 :          0 :     pari_err_TYPE("setrand",x);
     109         [ -  + ]:       4003 :   if (signe(x) <= 0) return;
     110                 :       4003 :   useed = itou_or_0(x);
     111         [ +  + ]:       4003 :   if (useed > 0) { init_xor4096i(useed); return; }
     112         [ -  + ]:         55 :   if (lgefint(x)!=2+r2+2+(r2==128))
     113                 :          0 :     pari_err_TYPE("setrand",x);
     114                 :         55 :   xp = int_LSW(x);
     115         [ +  + ]:       4023 :   for (i = 0; i < r2; i++) { state[i] = *xp; xp = int_nextW(xp); }
     116                 :            : #ifdef LONG_IS_64BIT
     117                 :         48 :   xorgen_w = *xp; xp = int_nextW(xp);
     118                 :            : #else
     119                 :          7 :   xorgen_w = _32to64(*xp, *int_nextW(xp)); xp = int_nextW(int_nextW(xp));
     120                 :            : #endif
     121                 :       4003 :   xorgen_i =  (*xp) & 63;
     122                 :            : }
     123                 :            : 
     124                 :            : GEN
     125                 :     214828 : getrand(void)
     126                 :            : {
     127                 :     214828 :   const int r2 = sizeof(state)/sizeof(ulong);
     128                 :            :   GEN x;
     129                 :            :   ulong *xp;
     130                 :            :   long i;
     131         [ -  + ]:     214828 :   if (xorgen_i < 0) init_xor4096i(1);
     132                 :            : 
     133                 :     214828 :   x = cgetipos(2+r2+2+(r2==128)); xp = (ulong *) int_LSW(x);
     134         [ +  + ]:   15944748 :   for (i = 0; i < r2; i++) { *xp = state[i]; xp = int_nextW(xp); }
     135                 :            : #ifdef LONG_IS_64BIT
     136                 :     183876 :   *xp = xorgen_w; xp = int_nextW(xp);
     137                 :            : #else
     138                 :      30952 :   _64to32(xorgen_w, xp, int_nextW(xp)); xp = int_nextW(int_nextW(xp));
     139                 :            : #endif
     140 [ +  + ][ +  + ]:     214828 :   *xp = xorgen_i? xorgen_i: 64; return x;
     141                 :            : }
     142                 :            : 
     143                 :            : /* assume 0 <= k <= BITS_IN_LONG. Return uniform random 0 <= x < (1<<k) */
     144                 :            : long
     145                 :    8724804 : random_bits(long k) { return rand64() >> (64-k); }
     146                 :            : 
     147                 :            : /********************************************************************/
     148                 :            : /*                                                                  */
     149                 :            : /*                         GENERIC ROUTINES                         */
     150                 :            : /*                                                                  */
     151                 :            : /********************************************************************/
     152                 :            : 
     153                 :            : /* assume n > 0 */
     154                 :            : ulong
     155                 :    9705993 : random_Fl(ulong n)
     156                 :            : {
     157                 :            :   ulong d;
     158                 :            :   int shift;
     159                 :            : #ifdef LONG_IS_64BIT
     160                 :    8321034 :   int SHIFT = 0;
     161                 :            : #else
     162                 :    1384959 :   int SHIFT = 32;
     163                 :            : #endif
     164                 :            : 
     165         [ +  + ]:    9705993 :   if (n == 1) return 0;
     166                 :            : 
     167 [ +  + ][ +  + ]:    9705531 :   shift = bfffo(n); /* 2^(BIL-shift) > n >= 2^(BIL-shift-1)*/
         [ +  + ][ +  + ]
     168                 :            :   /* if N a power of 2, increment shift. No reject */
     169 [ +  + ][ +  + ]:    9705531 :   if ((n << shift) == HIGHBIT) return rand64() >> (SHIFT+shift+1);
     170                 :            :   for (;;) {
     171                 :   12086192 :     d = rand64() >> (SHIFT+shift); /* d < 2^(64-shift) uniformly distributed */
     172                 :            :     /* reject strategy: proba success = n 2^(shift-64), in [1/2, 1[ */
     173         [ +  + ]:   12086192 :     if (d < n) return d;
     174                 :   12761104 :   }
     175                 :            : }
     176                 :            : 
     177                 :            : /* assume N > 0, see random_Fl() for algorithm. Make sure that 32-bit and
     178                 :            :  * 64-bit architectures produce the same integers (consuming random bits
     179                 :            :  * by packets of 64) */
     180                 :            : GEN
     181                 :    2996927 : randomi(GEN N)
     182                 :            : {
     183                 :    2996927 :   long lx = lgefint(N);
     184                 :            :   GEN x, d;
     185                 :            :   int shift;
     186                 :            : 
     187         [ +  + ]:    2996927 :   if (lx == 3) return utoi( random_Fl(N[2]) );
     188                 :            : 
     189 [ +  + ][ +  + ]:      19098 :   shift = bfffo(*int_MSW(N));
         [ +  + ][ +  + ]
     190                 :            :   /* if N a power of 2, increment shift */
     191 [ +  + ][ +  - ]:      19098 :   if (Z_ispow2(N) && ++shift == BITS_IN_LONG) { shift = 0; lx--; }
         [ +  + ][ +  - ]
     192                 :      19098 :   x = cgetipos(lx);
     193                 :            :   for (;;) {
     194                 :      35969 :     GEN y, MSW = int_MSW(x), STOP = MSW;
     195                 :            : #ifdef LONG_IS_64BIT
     196         [ +  + ]:      53694 :     for (d = int_LSW(x); d != STOP; d = int_nextW(d)) *d = rand64();
     197                 :      26760 :     *d = rand64() >> shift;
     198                 :            : #else
     199         [ +  + ]:       9209 :     if (!odd(lx)) STOP = int_precW(STOP);
     200                 :            :     /* STOP points to where MSW would in 64-bit */
     201         [ +  + ]:      13652 :     for (d = int_LSW(x); d != STOP; d = int_nextW(d))
     202                 :            :     {
     203                 :       4443 :       ulong a, b; _64to32(rand64(), &a,&b);
     204                 :       4443 :       *d = b; d = int_nextW(d);
     205                 :       4443 :       *d = a;
     206                 :            :     }
     207                 :            :     {
     208                 :       9209 :       ulong a, b; _64to32(rand64() >> shift, &a,&b);
     209         [ +  + ]:       9209 :       if (d == MSW) /* 32 bits needed */
     210                 :       4353 :         *d = a;
     211                 :            :       else
     212                 :            :       { /* 64 bits needed */
     213                 :       4856 :         *d = b; d = int_nextW(d);
     214                 :       4856 :         *d = a;
     215                 :            :       }
     216                 :            :     }
     217                 :            : #endif
     218                 :      35969 :     y = int_normalize(x, 0);
     219         [ +  + ]:      35969 :     if (absi_cmp(y, N) < 0) return y;
     220                 :    3013798 :   }
     221                 :            : }
     222                 :            : 
     223                 :            : GEN
     224                 :      62837 : random_F2x(long d, long vs)
     225                 :            : {
     226                 :      62837 :   long i, l = nbits2lg(d+1), n = l-1;
     227                 :      62837 :   GEN y = cgetg(l,t_VECSMALL); y[1] = vs;
     228                 :            : #ifdef LONG_IS_64BIT
     229         [ +  + ]:     107904 :   for (i=2; i<=n; i++) y[i] = rand64();
     230                 :            : #else
     231         [ +  + ]:       9227 :   for (i=2; i<=n; i++)
     232                 :            :   {
     233                 :       9205 :     u64 v = rand64();
     234                 :       9205 :     y[i] = v & 0xFFFFFFFFUL;
     235                 :       9205 :     i++;
     236         [ +  + ]:       9205 :     if (i > n) break;
     237                 :        104 :     y[i] = v>>32;
     238                 :        104 :     i++;
     239         [ +  + ]:        104 :     if (i > n) { v = rand64(); break; }
     240                 :            :   }
     241                 :            : #endif
     242                 :      62837 :   y[n] &= (1UL<<remsBIL(d))-1UL;
     243                 :      62837 :   return F2x_renormalize(y,l);
     244                 :            : }
     245                 :            : 
     246                 :            : GEN
     247                 :          7 : randomr(long prec)
     248                 :            : {
     249                 :            :   pari_sp av;
     250                 :            :   long b;
     251                 :            :   GEN x, y;
     252         [ -  + ]:          7 :   if (prec <= 2) return real_0_bit(0);
     253                 :          7 :   x = cgetr(prec); av = avma;
     254                 :          7 :   b = prec2nbits(prec);
     255                 :          7 :   y = randomi(int2n(b));
     256         [ -  + ]:          7 :   if (!signe(y)) return real_0_bit(b);
     257                 :          7 :   affir(y, x); shiftr_inplace(x, - b);
     258                 :          7 :   avma = av; return x;
     259                 :            : }
     260                 :            : 
     261                 :            : static GEN
     262                 :          7 : polrandom(GEN N) /* assume N!=0 */
     263                 :            : {
     264                 :          7 :   long i, d = lg(N);
     265                 :          7 :   GEN z = leading_term(N);
     266                 :          7 :   GEN y = cgetg(d,t_POL);
     267                 :          7 :   y[1] = evalsigne(1) | evalvarn(varn(N));
     268         [ +  + ]:         49 :   for (i=2; i<d; i++) gel(y,i) = genrand(z);
     269                 :          7 :   return normalizepol_lg(y,d);
     270                 :            : }
     271                 :            : 
     272                 :            : GEN
     273                 :    2850288 : genrand(GEN N)
     274                 :            : {
     275                 :            :   GEN z;
     276         [ +  + ]:    2850288 :   if (!N) return utoi( random_bits(31) );
     277   [ +  +  +  +  :    2849616 :   switch(typ(N))
                +  +  + ]
     278                 :            :   {
     279                 :            :     case t_INT:
     280         [ +  + ]:    2183629 :       if (signe(N)<=0) pari_err_DOMAIN("random","N","<=",gen_0,gen_0);
     281                 :    2183622 :       return randomi(N);
     282                 :            :     case t_REAL:
     283                 :          7 :       return randomr(realprec(N));
     284                 :            :     case t_INTMOD:
     285                 :     560217 :       z = cgetg(3, t_INTMOD);
     286                 :     560217 :       gel(z,1) = icopy(gel(N,1));
     287                 :     560217 :       gel(z,2) = randomi(gel(N,1)); return z;
     288                 :            :     case t_FFELT:
     289                 :      12068 :       return ffrandom(N);
     290                 :            :     case t_POL:
     291         [ -  + ]:          7 :       if (signe(N)==0) return pol_0(varn(N));
     292                 :          7 :       return polrandom(N);
     293                 :            :     case t_VEC:
     294         [ +  + ]:      93681 :       if (lg(N) == 3)
     295                 :            :       {
     296                 :         70 :         pari_sp av = avma;
     297                 :         70 :         GEN a = gel(N,1), b = gel(N,2), d;
     298         [ -  + ]:         70 :         if (typ(a) != t_INT) a = gceil(a);
     299         [ -  + ]:         70 :         if (typ(b) != t_INT) b = gfloor(b);
     300 [ +  - ][ -  + ]:         70 :         if (typ(a) != t_INT || typ(b) != t_INT) pari_err_TYPE("random", N);
     301                 :         70 :         d = subii(b,a);
     302         [ -  + ]:         70 :         if (signe(d) < 0) pari_err_TYPE("random([a,b]) (a > b)", N);
     303                 :         70 :         return gerepileuptoint(av, addii(a, randomi(addis(d,1))));
     304                 :            :       }
     305                 :      93611 :       return ellrandom(N);
     306                 :            :     default:
     307                 :          7 :       pari_err_TYPE("genrand",N);
     308                 :    2850274 :       return NULL;/*not reached*/
     309                 :            :   }
     310                 :            : }

Generated by: LCOV version 1.9