CCayley Class Reference

The Cayley PRNG. More...

#include <Cayley.h>

Inheritance diagram for CCayley:

Public Member Functions
	CCayley (uint32_t n)
	Constructor. More...
	~CCayley ()
	Destructor. More...
virtual void	srand (uint64_t(*rnd)(void))
	Seed the generator. More...
CPerm	GetGenerator (int i) const
	Get generator. More...
const CPerm &	GetPerm () const
	Get current permutation. More...
const uint32_t	GetSize () const
	Get permutation size. More...

Protected Member Functions
void	ChooseGenerators (uint64_t(*rnd)(void))
	Choose generators. More...
void	NextPerm ()
	Compute next permutation. More...

Protected Attributes
uint32_t	m_nSize = 0
	Size of permutations.
uint32_t	m_nOrder = 0
	Order of generators.
CPowerTable	m_nPower [2]
	Power tables for a pair of generators.
CPerm *	m_pCurPerm = nullptr
	Current permutation.
uint64_t	m_nDelayLine [m_nDelay]
	Delay line. More...
int	m_nTail = 0
	Index of last element in delay line.

Static Protected Attributes
static const int	m_nDelay = 32
	Delay size.

Detailed Description

CCayley is a templated class that allows you to declare instances of Cayley that generate 8-bit, 16-bit, 32-bit, or 64-bit pseudorandom numbers (CCayley<uint8_t>, CCayley<uint16_t>, CCayley<uint32_t>, and CCayley<uint64_t>, respectively) using a symmetric group of any size permitted by the declaration of CPerm. Given access to another PRNG for initialization purposes, it will construct a pair of pseudorandom generators for the symmetric group and pseudorandom masks. It is recommended that this functionality be used during initial exploration and testing, and that a further class be derived from this one using fixed permutation size, generators, and masks that pass any test for pseudorandomness that you might prefer, such as DieHarder.

Definition at line 24 of file Cayley.h.

Constructor & Destructor Documentation

CCayley()

CCayley::CCayley

(

uint32_t

n

)

Construct the current permutation and set the order of the generators using the Landau table.

Parameters

n	The permutation size.

Definition at line 39 of file Cayley.cpp.

~CCayley()

CCayley::~CCayley

(

)

The destructor.

Definition at line 49 of file Cayley.cpp.

Member Function Documentation

ChooseGenerators()

void CCayley::ChooseGenerators ( uint64_t(*)(void)  rnd )

protected

Choose a pair of pseudorandom odd permutations of maximal order that have no common fixed point. It is unlikely that a pair of random permutations will have the same fixed point but it is possible. Build tables of powers of these generators to speed up the computation.

Parameters

rnd	An external PRNG for seeding.

Definition at line 68 of file Cayley.cpp.

GetGenerator()

CPerm CCayley::GetGenerator

(

int

i

)

const

Reader function for the generators.

Parameters

i	Generator number, either 0 or 1.

Returns

Hex string of generator reverse lexicographic number.

Definition at line 57 of file Cayley.cpp.

GetPerm()

const CPerm & CCayley::GetPerm

(

)

const

Reader function for the current permutation.

Returns

Const reference to the current permutation.

Definition at line 109 of file Cayley.cpp.

GetSize()

const uint32_t CCayley::GetSize

(

)

const

Reader function for the the permutation size, that is, the number of items permuted by the curret permutation and the generators.

Returns

The permutation size.

Definition at line 117 of file Cayley.cpp.

NextPerm()

void CCayley::NextPerm ( )

protected

Generate the next pseudo-random permutation as follows. Get the exponent \(k\) from the delay line and multiply the current permutation \(\phi\) by the current generator \(\sigma_i\) to the power \(k\).

Definition at line 128 of file Cayley.cpp.

srand()

void CCayley::srand ( uint64_t(*)(void)  rand )

virtual

Initialize the pseudo-random number generator by choosing the generators and the initial permutation.

Parameters

rand	An external random number generator to use as a seed.

Definition at line 101 of file Cayley.cpp.

Member Data Documentation

m_nDelayLine

uint64_t CCayley::m_nDelayLine[m_nDelay]

protected

Initial value:

= { 
      0x57ea5e79bb7b58dc, 0x03198e239ff8ba7d,
      0x7779bd2aeb666379, 0x5de2cf0e048781c3,
      0x89faeceacabe7821, 0xbf5a9b43b4e550ae,
      0x24e37a696814c67e, 0x45e199269f6ad385,
      0xf1df54ec42d8fba8, 0x089f41735277a11d,
      0x602c3888033edae0, 0xc71fee188d41a646,
      0x379121f47085af73, 0x9419d15d410b8eeb,
      0x760744f26b4c05b0, 0x3c68c1fb83c9a47e,
      0xa10d29f01e2f225e, 0x39792d6f9700f5cb,
      0xf5016c43b32d066c, 0x692d0a2cbcc083c0,
      0x229bfc31ea3beeff, 0xe9e6fd8bbf4033b8,
      0x74e8c4ad7bd95bd0, 0xeedb9cede270c79b,
      0x9abd1906822b22ac, 0x3b57c6458e330f89,
      0x7fc8519dfd26353d, 0x2874406cd5a54ba0,
      0x9fe7daf93fe577a2, 0x83d1c7bb3d29cd1f,
      0xbb2d2cbb68483f3d, 0x39af233d402946ec
    }

Definition at line 34 of file Cayley.h.