FPGA Implementations of Tiny Mersenne Twister

Random number generators are essential in many computing applications, such as Artificial Intelligence like genetic algorithms and automated opponents, random game content, simulation of complex phenomena such as weather and fire, numerical methods such as Monte-Carlo integration, cryptography algorithms such as RSA use random numbers for key generation, digital signal processing and communications, etc. Pseudo-random Number Generators (PRNGs) generate a sequence of “random” numbers using an algorithm, operating on an internal state, such as Linear Congruential Generator, Truncated Linear Congruential Generator, Linear Feedback Shift Register, Inversive Congruential Generator, Lagged Fibonacci Generator, Cellular Automata, Mersenne Twister, etc. The Mersenne Twister method, which avoided many of the problems with earlier generators and widely used in many applications, was proposed in 1998. In 2011, a tiny version of Mersenne Twister (TinyMT) was proposed. In some applications for example, where the large state size (19937 bits) of Mersenne Twister may be an obstruction for implementation. TinyMT is designed for such situation, with small state size and good randomness for that size of internal state. In this paper, FPGA implementations of four different TinyMT architectures were proposed and realized on Xilinx Virtex-4 FPGAs for the first time. The proposed designs can achieve very high throughput but with relatively very small areas.