alrand - a pseudo random number generation library

#

                   alrand - a pseudo random number generation library

                                     version 1.0.1

alrand is a library offering a generic interface to various random number generation algorithms. It can be used both in thread safe mode (where the user explicitely supplies the state to use) and in traditional mode, where a global state is automatically maintained. Moreover, states are persistent and can be saved and restored using predefined or user supplied load/save routines.

The different generators supported by alrand have their own interface which can be used directly, as some generators have extra optional properties which are not available through the generic interface.

alrand's homepage can be found at http://lyrian.obnix.com/alrand/

alrand is Copyright 2002 Vincent Penquerc'h and is distributed under the terms of the Lesser General Public License (LGPL). See file LGPL.txt in the archive for more information.

#include <std_disclaimer.h>
"I do not accept responsibility for any effects, adverse or otherwise, that this code may have on you, your computer, your sanity, your dog, and anything else that you can think of. Use it at your own risk."

# Contents

- Building alrand
- Using alrand
- Library basics
- The generic interface
- The global interface
- State persistence
- The Mersenne Twister interface
- The linear congruential interface

- Building alrand
- Using alrand
- Library basics
  - alrand_exit
  - alrand_init
- The generic interface
  - alrand_create
  - alrand_destroy
  - alrand_generate
  - alrand_seed
- The global interface
  - alrand_get_global_generator_type
  - alrand_rand
  - alrand_set_global_generator_type
  - alrand_srand
- State persistence
  - alrand_load
  - alrand_load_from_allegro_packfile
  - alrand_load_from_bzfile
  - alrand_load_from_fd
  - alrand_load_from_gzfile
  - alrand_load_from_stdio_file
  - alrand_save
  - alrand_save_to_allegro_packfile
  - alrand_save_to_bzfile
  - alrand_save_to_fd
  - alrand_save_to_gzfile
  - alrand_save_to_stdio_file
- The Mersenne Twister interface
  - alrand_mersenne_twister_create
  - alrand_mersenne_twister_destroy
  - alrand_mersenne_twister_generate
  - alrand_mersenne_twister_seed
  - alrand_mersenne_twister_seed_v
- The linear congruential interface
  - alrand_lcg_create
  - alrand_lcg_create_custom
  - alrand_lcg_destroy
  - alrand_lcg_generate
  - alrand_lcg_seed

# Building alrand

alrand does not require extra libraries besides the usual libc.

alrand is written in C, and should be compilable with any C compiler. It was written using GCC 2.95 on Linux. If you are using GCC and GNU make, then building is a very simple matter:

    make

You may also want to install the library:

    make install

or, if you want to install it somewhere else than /usr/local:

    make install PREFIX=/home/user/alrand

alrand has a test program, which you can use to check that alrand is working correctly. You can run it this way:

    make test

# Using alrand

Using alrand is very simple: you need only include one file:

    #include <alrand/alrand.h>

and link against one library:

    libalrand.a

If you wish to use directly the different generators, you will have to include its specific header:

>     #include <alrand/mersenne.h>

You may want to use a specific generator directly to access some of their advanced properties: for instance, the Mersenne Twister algorithm can be seeded with 19937 bits of data, though the alrand generic interface only supports seeding with 32 bits of data.

Note that the algorithms used in alrand are not cryptographically secure. If you're looking for a cryptographic quality pseudo random number generator, you might want to have a look at Yarrow at http://www.counterpane.com/yarrow.html.

# Library basics

Following are some macros useful for allowing building with different versions of alrand.

ALRAND_MAJOR This is the major number of alrand's version. It is the x in x.y.z.

ALRAND_MINOR This is the minor number of alrand's version. It is the y in x.y.z.

ALRAND_PATCH This is the patch number of alrand's version. It is the z in x.y.z.

ALRAND_MAKE_VERSION This helper macro allows one to build a version number in the format of ALRAND_VERSION from the major, minor and patch numbers, ready to be tested against ALRAND_VERSION.

ALRAND_VERSION This is the patch number of alrand's version. It is a decimal number made up of the three version number components presented above. It is equal to ALRAND_VERSION * 10000 + ALRAND_MINOR * 100 + ALRAND_PATCH, which makes it easy to test if alrand x.y.z or newer is available with a simple comparison.

ALRAND_ID This text string identifies alrand and its version in a suitable form for displaying to the user.

void alrand_init();
Initialises the internal state of the alrand library. This should be called before calling any other alrand routine.

> See also: alrand_exit.

void alrand_exit();
This function cleans up the internal state of the alrand library. No other alrand routine apart from alrand_init should be called after calling alrand_exit until alrand_init is called again.

> See also: alrand_init.

# The generic interface

This interface allows access to the different generators supported by alrand using the same unified interface. Generators which expose extra information and/or configuration can be used through this interface, but these extra capabilities will be hidden. If you want to use them, you will have to access the appropriate generator directly through its own interface.

alrand_state *alrand_create(alrand_generator_type type,alrand_int32_t seed);
This function creates a generator of the given type. It should be destroyed with alrand_destroy. The generator is automatically seeded with the given seed. It is possible to seed the generator again at any time until it is destroyed. NULL is returned on error (usually memory shortage, but certain generators can also fail for other reasons).

> See also: alrand_generate, alrand_destroy, alrand_seed.

void alrand_destroy(alrand_state *state);
This function destroys a generator previously created with alrand_create. Do not use this generator ever again.

> See also: alrand_create.

void alrand_seed(alrand_state *state,alrand_uint32_t seed);
This function seeds the given generator with new data. Note that the generators are automatically seeded when created. Also note that different generators may use the data differently. Refer to each generator's specific documentation for more details.

> See also: alrand_create, alrand_generate.

alrand_int32_t alrand_generate(alrand_state *state);
This function generates a pseudo random number. This function can be called repeatedly until the generator is destroyed.

> See also: alrand_create, alrand_seed.

# The global interface

This interface uses a global generator, and is therefore not suitable for multithreaded programs unless appropriate care is taken (eg locking access to alrand, or ensuring that only one thread calls alrand, etc).

The global interface offers two API calls designed to mimic the standard C library calls srand and rand.

void alrand_srand(alrand_int32_t seed);
Initializes the global random number generator using the given seed. This does not need to be called before calling alrand_rand. If not called, the global random number generator will use a default seed of 4357. The default generator used is the Mersenne Twister.

> See also: alrand_rand, alrand_create.

alrand_int32_t alrand_rand();
Uses the global random number generator to generate a single random number. It is not necessary to call alrand_srand before using alrand_rand. If alrand_srand is not called, a default seed of 4357 is used.

> See also: alrand_srand, alrand_generate.

void alrand_set_global_generator_type(alrand_generator_type type);
Sets the generator type to use as the global generator. This will reset the global generator (re-seed it with the default seed), even if the type set is the same as the current type. The default global generator type is the Mersenne Twister.

> See also: alrand_get_global_generator_type.

alrand_generator_type alrand_get_global_generator_type();
Retrieves the global generator type. This can be called even if it has not been used yet.

> See also: alrand_set_global_generator_type.

# State persistence

alrand can save and restore a state using predefined routines or user defined ones. This allows a user program to ensure that a random number generator will yield the exact same stream of pseudo random numbers after being loaded as if it hadn't been saved and loaded back.

The generic routines to load and save a state take pointers to routines to save and load alrand_uint32_t data. alrand comes with sample routines and wrappers to use several different formats.

int alrand_save(alrand_state *state,void (*write)(alrand_uint32_t,void*),void*);
This function saves the specified state using the supplied writing routine. This routine must save a 32 bit unsigned data. The void* pointer passed to it is the one that is passed to alrand_save. Typically, it will be an identifier for the file to write to (eg, if using <stdio.h>'s FILE routines, it would be a FILE*).

> See also: alrand_load.

alrand_state *alrand_load(alrand_uint32_t (*read)(void*),void*);
This function loads a state using the supplied reading routine, returning NULL if it could not do it. The reading routine must read a 32 bit unsigned data. The void* pointer passed to it is the one that is passed to alrand_load. Typically, if will be an identifier for the file to read from (eg, if using <stdio.h>'s FILE routines, it would be a FILE*).

There are sample load/save routines supplied for convenience. Only one of them (the Allegro one) is endianness independant (as it uses Allegro's endian independant read/write routines). You may want to take these samples as a guide to write load/save routines for the format you want.

Note that these sample routines are meant to be a guide, and do not include error checking, and are assuming sizes of certain data types. For instance, you should check for any errors (I/O, etc) after saving and loading states. They should be used as a starting point to build your own routines.

> See also: alrand_save.

int alrand_save_to_fd(alrand_state *state,int fd);
Saves a state to the file descriptor fd. fd is assumed to be an open writeable descriptor.

> See also: alrand_save, alrand_load_from_fd.

alrand_state *alrand_load_from_fd(int fd);
Loads a state from the file descriptor fd. fd is assumed to be an open readable descriptor.

> See also: alrand_load, alrand_save_to_fd.

int alrand_save_to_stdio_file(alrand_state *state,FILE *f);
Saves a state to the file f. f is assumed to be an open writeable file.

> See also: alrand_save, alrand_load_from_stdio_file.

alrand_state *alrand_load_from_stdio_file(FILE *f);
Loads a state from the file fd. fd is assumed to be an open readable file.

> See also: alrand_load, alrand_save_to_stdio_file.

int alrand_save_to_allegro_packfile(alrand_state *state,PACKFILE *f);
Saves a state to the Allegro packfile f. f is assumed to be an open writeable packfile. The state is saved in an endianness independant fashion.

> See also: alrand_save, alrand_load_from_allegro_packfile.

alrand_state *alrand_load_from_allegro_packfile(PACKFILE *f);
Loads a state from the Allegro packfile f. f is assumed to be an open readable packfile. The state is loaded in an endianness independant fashion, as saved by alrand_save_to_allegro_packfile.

> See also: alrand_load, alrand_save_to_allegro_packfile.

int alrand_save_to_gzfile(alrand_state *state,gzFile file);
Saves a state to the gzFile zlib compressed file. file is assumed to be an open writeable zlib compressed file.

> See also: alrand_save, alrand_load_from_gzfile.

alrand_state *alrand_load_from_gzfile(gzFile file);
Loads a state from the gzFile zlib compressed file. file is assumed to be an open readable zlib compressed file.

> See also: alrand_load, alrand_save_to_gzfile.

int alrand_save_to_bzfile(alrand_state *state,BZFILE *file);
Saves a state to the BZFILE bzip2 compressed file. file is assumed to be an open writeable bzip2 compressed file.

> See also: alrand_save, alrand_load_from_bzfile.

alrand_state *alrand_load_from_bzfile(BZFILE *file);
Loads a state from the BZFILE bzip2 compressed file. file is assumed to be an open readable bzip2 compressed file.

> See also: alrand_load, alrand_save_to_bzfile.

# The Mersenne Twister interface

The Mersenne Twister was designed with the goal of overcoming the flaws found in many other pseudo random number generators, mainly the short period (the Mersenne Twister has a period of 2^19937-1) and the predictability of the distribution of generated numbers.

More info about the Mersenne Twister can be found at http://www.math.keio.ac.jp/~matumoto/emt.html.

Note: A Mersenne Twister generator state saves 626 32-bit words.

alrand_state *alrand_mersenne_twister_create(alrand_uint32_t seed);
This function creates a new state using the Mersenne Twister algorithm.

> See also: alrand_mersenne_twister_seed, alrand_create, alrand_mersenne_twister_destroy.

void alrand_mersenne_twister_seed(alrand_state *state,alrand_uint32_t seed);
This function seeds the Mersenne Twister algorithm. Note that since this algorithm has a much wider state than 32 bits, you can use alrand_mersenne_twister_seed_v to seed the algorithm with more data.

> See also: alrand_mersenne_twister_seed_v, alrand_mersenne_twister_create, alrand_mersenne_twister_generate.

void alrand_mersenne_twister_seed_v(alrand_state *state,alrand_uint32_t *seed);
This function seeds the Mersenne Twister algorithm. seed should point to at least 2496 bytes (19968 bits) of seed data. Note that the low 31 bits of the first 32 bit word of the seed data are ignored, so the effective seed size is 19968-31=19937 bits.

> See also: alrand_mersenne_twister_seed, alrand_mersenne_twister_create, alrand_mersenne_twister_generate.

alrand_uint32_t alrand_mersenne_twister_generate(alrand_state *state);
This function generates a new number using the Mersenne Twister algorithm.

> See also: alrand_generate, alrand_mersenne_twister_create, alrand_mersenne_twister_seed, alrand_mersenne_twister_seed_v.

void alrand_mersenne_twister_destroy(alrand_state *state);
This function destroys a Mersenne Twister state.

> See also: alrand_destroy, alrand_mersenne_twister_create.

# The linear congruential interface

LCG is a very fast algorithm, but it has very weak randomness properties. However, it is often good enough for simple needs, as in most games. Each generated number is computed from the previous one (the original one being the seed) from the formula:

>     x(n+1) = (x(n) * M + A) mod T

M and A being large primes. alrand's implementation uses an implicit T (2^32).

Is is to be noted that due to the fact that the state is 32 bit wide, the period of any LCG can't be more than 2^32, as once you generate the same number as a previous run, the same stream of numbers will follow. The period will also be different for each M,A pair. As a trivial example, the pair 1,0 yields a period of 1 (eg, all generated numbers are equal to the seed).

If you want to use different M,A pairs, you may use the mkprimes.c program supplied in the alrand archive. This program will print all primes smaller than a given number. By default, this number is 48*1024*1024, but you can increase it if you want. Just remember that the algorithm used here needs one bit of memory per number, so finding primes up to 48*1024*1024 requires 48 megabytes of memory. There is an easy optimization that checks only every second number, but since I didn't need it, I didn't bother. There are also other algorithms, but this one was the only one I knew offhand.

Note: A linear congruential generator state saves 4 32-bit words.

alrand_state *alrand_lcg_create(alrand_uint32_t seed);
This function creates a new LCG state with default M and A parameters.

> See also: alrand_create, alrand_lcg_create_custom, alrand_lcg_generate, alrand_lcg_destroy, alrand_lcg_seed.

alrand_state *alrand_lcg_create_custom(alrand_uint32_t seed,alrand_uint32_t mult,alrand_uint32_t add);
This function creates a new LCG state user supplied M and A parameters. For best quality, these parameters should be large primes.

> See also: alrand_create, alrand_lcg_create, alrand_lcg_generate, alrand_lcg_destroy, alrand_lcg_seed.

void alrand_lcg_destroy(alrand_state *state);
This function destroys an existing LCG state. Usually, there is no reason using this function directly, as it will be called by alrand_destroy if the supplied state is an LCG state.

> See also: alrand_destroy, alrand_lcg_create.

void alrand_lcg_seed(alrand_state *state,alrand_uint32_t seed);
This function seeds the given LCG with the supplied seed. The LCG uses only the normal 32 bits of seed data.

> See also: alrand_seed, alrand_lcg_create, alrand_lcg_create_custom.

alrand_uint32_t alrand_lcg_generate(alrand_state *state);
This functon generates a new number based on the above formula. The starting number x(n) is the previously generated number or, if no numbers were generated since last time the state was seeded, the seed itself. Each number generated becomes the seed for next call to alrand_lcg_generate.