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

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 (http://shoup.net/ntl/), so you need to install it before using these programs. NTL is written in C++.

For the compilation of C-codes using NTL, see http://www.shoup.net/ntl/doc/tour-unix.html. 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.