Generating multiple disjoint streams of pseudorandom number sequences


  1. A Fast Jump Ahead Algorithm for Linear Recurrences in a Polynomial Space
  2. Efficient Jump Ahead for F2-Linear Random Number Generators

C and C++ Codes

jump_ahead_1.01.tar.gz (2013/01/16 modified by saito)
jump_ahead_1.02.tar.gz (2013/01/25 modified by saito, according to the suggestion by Pierre Schweitzer and David Hill for speed up)

We have implemented the codes of the jumping-ahead for MT19937 and WELL19937, in C and C++ languages.

Since these codes were implemented for the purpose of measuring the computing times, they are not polished.

minipoly_mt19937.c computes the minimal polynomial of MT19937, and computes the remainder of t^J divided by this minimal polynomial, where J is the number of steps (in minipoly_mt19937.c, J corresponds the variable jump_step.)

This program generates a file "clist_mt19937.txt", which consists of the coefficients of the remainder polynomial.

The data contained in clist_mt19937.txt is used in the actual jumping computation programs (i.e. to compute the state corresponding to the J steps jumping ahead) for MT19937 below, namely, jump_mt19937.c and pm-jump-mt19937.c. For one J and for MT, the file clist_mt19937.txt is only once need to be computed: the file data is valid for any state, so you can efficiently compute J-step jumping once you compute clist_mt19937.txt.

Similarly, the data contained in clist_well19937.txt (generated by calling minipoly_well19937.c with argument J) can be used for J steps jumping ahead for any state of WELL19937.

These codes use the NTL (Number theory library) by Shoup (, so you need to install it before using these programs. NTL is written in C++.

For the compilation of C-codes using NTL, see After installing NTL, you can obtain the executable file by compiling minipoly_mt19937.c as follows:

      % g++ -I$HOME/sw/include -L$HOME/sw/lib minipoly_mt19937.c -lntl -lm

jump_mt19937.c and jump_well19937.c are the codes of the jumping-ahead using Sliding window algorithm. Both codes are written with standard C-language only.

pm-jump-mt19937.c is the code using Polynomial Multiplication method. It needs NTL because it uses Karatsuba Polynomial Multiplication algorithm.

Both jump_mt19937.c and pm-jump-mt19937.c use the file clist_mt19937.txt. You have to compile and generate the file clist_mt19937.txt before you compile jump_mt19937.c / pm-jump-mt19937.c.

jump_well19937.c is the code of the jumping-ahead using Sliding window algorithm, which is written with standard C-language. It is necessary to generate clist_well19937.txt before you compile jump_well19937.c.