Appendix B: The Rand Module

This module encapsulates a random number generator. It is adapted from the Mersenne Twister as described by M. Matsumoto and T. Nishimura. The original code is copyrighted by A. Fog; see http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/emt.html. It is protected by the GNU General Public License, www.gnu.org/copyleft/gpl.html.

Prior to utilizing the random number generator a rand ID must be obtained by invoking RAND_create; when it is no longer needed, it must be destroyed by invoking RAND_destroy. After obtaining an ID, the random number generator may optionally be seeded by calling RAND_init or RAND_init_by_array. After (the optional) initialization, random integers may be obtained by sequentially invoking RAND_irandom.

I will not attempt to discuss random number generators here at length; a good list of references and examples may be found at http://random.mat.sbg.ac.at/links/rando.html. I will, however, point out a few general features that are relevant to testing our BTREE module,

1. Random number generators are deterministic; that is, a particular random number generator when invoked twice using the same seed will produce the same sequence of numbers both times.
2. Random number generators have a period; that is, after a certain number of iterations they will repeat the sequence of generated numbers. The Mersenne Twister has a very long period, well in excess of 10**5000.
3. A random number generator will generate duplicate numbers at least occasionally. For our purposes a random number generator that produces duplicates frequently will slow our tests appreciably. During our test of BTREE_balance the Mersenne Twister produced a single duplicate in the course of 100,000 invocations.

This module has been tested in both Microsoft Windows XP™ and Linux. The complete code for the rand module can be found in rand.c , rand.h and randp.h.