runs.c

随机数算法

/*************************************************
*                                                *
*  Runs test                                     *
*  This is same math as NIST.                    *
*  Enter with source pointer, endianness, and    *
*   number of bits to scan.                      *
*  Returns p-value as explained in section 3.3   *
*   of NIST docs.  Note that frequency tests out *
*  of range give 0.0 p-value (if prob > 2/(n)^.5 *
*  NIST says this math breaks down)              *
*                                                *
*************************************************/

#include <math.h>
#include "randtest.h"

double runs( SRCPTR *src, int endian, int numbits)
{
  double freq, Vn, chi;
  unsigned char mask, nxtbit, thsbit;
  int count;

  count = numbits;
  Vn = 1.0;
  freq = 0.0;
  mask = 1 << src->bitpos;
  while( count)
  {
    thsbit = (mask & *src->byteptr) ? 1 : 0;
    if( endian)
    {
      src->bitpos--;
      mask >>= 1;
      if( !(mask & 0xff))
      {
	mask = 0x80;
	src->byteptr++;
	src->bitpos = 7;
      }
    }
    else
    {
      src->bitpos++;
      mask <<= 1;
      if( !(mask & 0xff))
      {
	mask = 1;
	src->byteptr++;
	src->bitpos = 0;
      }
    }
    nxtbit = (mask & *src->byteptr) ? 1 : 0;
    if( thsbit) freq += 1.0;
    if( (count>1) && (thsbit ^ nxtbit)) Vn += 1.0;
    count--;
  }
  freq /= numbits;
  if( fabs( freq - 0.5) > 2.0/sqrt(numbits)) 
    return (0.0);
  chi = fabs( Vn - 2.0*numbits*freq*(1.0 - freq));
  chi /= 2.0*sqrt( 2.0*numbits)*freq*(1.0 - freq);
  chi = erfc(chi);
  return(chi);
}