cgul_random_lcg256.h File Reference

256-bit PRNG (LCG) More...

#include "cgul_common.h"
#include "cgul_big_integer.h"
#include "cgul_exception.h"

Include dependency graph for cgul_random_lcg256.h:

This graph shows which files directly or indirectly include this file:

Typedefs
typedef typedefCGUL_BEGIN_C struct cgul_random_lcg256 *	cgul_random_lcg256_t

Functions
CGUL_EXPORT cgul_random_lcg256_t	cgul_random_lcg256__new (cgul_exception_t *cex)
CGUL_EXPORT cgul_random_lcg256_t	cgul_random_lcg256__new_from_seed (cgul_exception_t *cex, cgul_big_integer_t seed)
CGUL_EXPORT void	cgul_random_lcg256__delete (cgul_random_lcg256_t r)
CGUL_EXPORT void	cgul_random_lcg256__next (cgul_exception_t *cex, cgul_random_lcg256_t r, cgul_big_integer_t next)
CGUL_EXPORT void	cgul_random_lcg256__next_in_range (cgul_exception_t *cex, cgul_random_lcg256_t r, cgul_big_integer_t next, cgul_big_integer_t range_max)

Detailed Description

256-bit linear congruential pseudo-random number generator.

Author

Paul Serice

Typedef Documentation

cgul_random_lcg256_t

typedef typedefCGUL_BEGIN_C struct cgul_random_lcg256* cgul_random_lcg256_t

Opaque pointer to a cgul_random_lcg256 instance.

Function Documentation

cgul_random_lcg256__new()

CGUL_EXPORT cgul_random_lcg256_t cgul_random_lcg256__new

(

cgul_exception_t *

cex

)

Create a new cgul_random_lcg256 object seeding it with the value returned by time(), i.e., the 32-bit seconds since the epoch. The caller is responsible for freeing the object by calling cgul_random_lcg256__delete(). If memory cannot be allocated, NULL is returned, and an exception is thrown.

Parameters

[in,out]

cex

c-style exception

Returns

new cgul_random_lcg256 instance

cgul_random_lcg256__new_from_seed()

CGUL_EXPORT cgul_random_lcg256_t cgul_random_lcg256__new_from_seed	(	cgul_exception_t *	cex,
		cgul_big_integer_t	seed
	)

Create a new cgul_random_lcg256 object seeding it with the value the user passes in seed. The caller is responsible for freeing the object by calling cgul_random_lcg256__delete(). If memory cannot be allocated, NULL is returned, and an exception is thrown.

Parameters

[in,out]	cex	c-style exception
[in]	seed	seed value

Returns

new cgul_random_lcg256 instance

cgul_random_lcg256__delete()

CGUL_EXPORT void cgul_random_lcg256__delete

(

cgul_random_lcg256_t

r

)

This method frees all internally allocated memory. Do not attempt to dereference r after calling this method.

Parameters

[in]

r

cgul_random_lcg256 instance

cgul_random_lcg256__next()

CGUL_EXPORT void cgul_random_lcg256__next	(	cgul_exception_t *	cex,
		cgul_random_lcg256_t	r,
		cgul_big_integer_t	next
	)

The next element in the random number sequence is returned in next. The random numbers returned are 256 bits wide. It is possible to generate larger random numbers by calling cgul_random_lcg256__next_in_range() which will assemble the larger numbers from multiple iterations of the generator.

The most common LCG implementation is to use a modulus that is a power of 2 allowing the modulo operation to be performed with a simple bit mask or intrinsic modulo 2 arithmetic (depending on the data type). The cgul_random_lcg256 implementation is no different; however, this results in the well-known problem that LCGs are non-random in their low-order bits. Specifically, the nth bit has a period of 2^n. Thus, the least-significant bit only has a period of 2 meaning it always just toggles between 0 and 1.

The way to get around this problem is to discard the low-order bits. This can be done by shifting to the right the value returned by this function or by using cgul_random_lcg256__next_in_range() which returns numbers based much more heavily on the high order bits.

Note

Do not use the value returned by this function without compensating for the non-random low-order bits (as described above).

Parameters

[in]	cex	c-style exception
[in]	r	cgul_random_lcg256 instance
[out]	next	next element in the random number sequence

See also

cgul_random_lcg256__next_in_range()

cgul_random_lcg256__next_in_range()

CGUL_EXPORT void cgul_random_lcg256__next_in_range	(	cgul_exception_t *	cex,
		cgul_random_lcg256_t	r,
		cgul_big_integer_t	next,
		cgul_big_integer_t	range_max
	)

If the value returned by cgul_random_lcg256__next() is not the exact range that is needed, this method can limit or extend the return value to [0, range_max). If range_max is larger than the number of bits that can be generated in one iteration, multiple iterations will be used. If the range needs to be extended beyond what can be generated in a single iteration, the Blum-Blum-Shub generator in cgul_random_bbs is probably a better choice.

It is highly recommended that this method be used when mapping the random numbers to a smaller range because (like most LCGs), the low order bits of this LCG are known to repeat much more quickly than all the bits taken as a whole. This method takes this problem into account to return a suitable pseudo-random number.

Parameters

[in]	cex	c-style exception
[in]	r	cgul_random_lcg256 instance
[out]	next	next element in the random number sequence
[in]	range_max	exclusive limit on the maximum value returned