TinyMT Jump Function

For a given 128-bit integer N, this jump function executes the N-step jump. Namely, from the given state, obtain the state of tinyMT after N steps generation. This is equivalent to call the tiny_mt generation N times with discarding the outputs. However, even for huge N, this jump function calculates the jump state in much less than 1 micro second. A typical usage of a jump function is to obtain distinct sub streams from a whole period of pseudorandom number sequence generated by one tinyMT.

The jump function is written in the standard C language, with standard library. Note that the function uses stdint.h and inttypes.h, which are parts of C99 standard.

Three Methods for parallel generation of pseudorandom numbers using TinyMT

Getting multiple sequences of pseudorandom numbers by using one same parameter set and different seeds for initialization. The sequences obtained by this method are sub sequences of one long period sequence; the starting point of the sequence depends on the seed. If the seeds are randomly chosen, it is difficult to know the distance between the starting points. With a small (usually negligible) probability, the sequences may overlap. A merit of this method is smaller consumption of memory (in shared memory parallel programing models like multiple threads model), by sharing one same parameter set in the shared constant memory among the threads.
Getting multiple sequences of pseudorandom numbers by jump. The situation is the same as the above, except that instead of the random choice of the seeds, a large integer N is fixed, and the states of tinyMTs have distance N. Namely, the state of the first tinyMT is randomly seeded, and the 2nd tinyMT is given the state computed by jumping ahead by N steps from the 1st, the 3rd is given the state jumping ahead by N steps from the 2nd, and so on. Differently from the random seeding, the distance between the starting points in one long period sequence is a multiple of N. This method has the same merit by sharing the parameter set as above.
Getting multiple sequences of pseudorandom numbers by using multiple parameter sets. The sequences obtained this method would be considered to be almost independent from each other. This method consumes more memory than the former methods.

The jump function provides the second method. Our program is not written to share the parameter set. If users wants to share the parameter set to use less memory, the users need to change the tinymt structure and need to define parameters as constant.

Download

TinyMTJump-src-1.2.tar.gz header files are changed to fit to C++.
TinyMTJump-src-1.2.zip header files are changed to fit to C++.
TinyMTJump-src-1.1.tar.gz Document adn sample are refined.
TinyMTJump-src-1.1.zip Document adn sample are refined.
TinyMTJump-src-1.0.tar.gz
TinyMTJump-src-1.0.zip

Usage

Compilation of test programs

Test program needs source programs of TinyMT to be compiled. And it needs the output parameter set of TinyMTDC for execution.

Expand archive file
Copy jump directory in TinyMTJump-src-xxxx to the directory of TinyMT.

TinyMT-src-xxx
   +---dc
   +---tinymt
   +---jump

Change directory to copied jump directory
Type make all to compile test program.
Type ./jump_test32 d8524022ed8dff4a8dcc50c798faba43 8f7011ee fc78ff1f 3793fdff 1298
Check if OK is showed and no NG

description of jump function

void tinymt32_jump(tinymt32c_t *tiny,
                   uint64_t lower_step,
                   uint64_t upper_step,
                   const char * poly_str);

This function changes the internal state of tinymt32 into the state after N steps generation, where N is a 128-bit integer specified by lower_step (lower 64-bit) and upper_step (upper 64-bit). N should be between 0 and 2¹²⁸-1. This function calls calculate_jump_polynomial and tinymt32_jump_by_polynomial.: tiny is a structure of type tinymt32_t. tiny must be initialized. tiny is overwritten by the new state (i.e. the state after jumping N steps).; lower_step and upper_step specify N; i.e. the number of steps for jumping-ahead. Users can specify zero to 2¹²⁸-1 steps, using two 64-bit arguments. However, note that the period of the sequence is 2¹²⁷-1.; poly_str is a string of characteristic polynomial, which is in the first column of outputs of tinymt32dc.

void calculate_jump_polynomial(f2_polynomial *jump_poly,
                               uint64_t lower_step,
                               uint64_t upper_step,
                               const char * poly_str);

From ver. 1.1
This function calculates jump polynomial from the characteristic polynomial, lower_step and upper_step. This function is time-consuming (but less than 1 micro second) compared with the next function that computes the jump using jump polynomial.: jump_polynomial will be overwritten by a calculated jump polynomial.; lower_step and upper_step specifies how many steps tinymt jumps. Users can specify from zero to 2¹²⁸-1 steps, using two 64-bit arguments.; poly_str is a string of characteristic polynomial, which is in the first column of outputs of tinymt32dc.

void tinymt32_jump_by_polynomial(tinymt32_t *tiny,
				 f2_polynomial * jump_poly);

From ver. 1.1
This function changes the internal state of tinymt32 into the state after N steps generation, using jump_poly. jump_poly must be calculated using the characteristic polynomial of tiny before this function is called. This function is much faster than calculate_jump_polynomial. The information of N is encoded in jump_poly. As far as the same parameter set is used, calling this function with jump_poly yields N-step jumping ahead, regardless to the present state. Thus, if N is fixed and N-step jumping is required several times, then jump_poly may be computed just once by calculate_jump_polynomial, and may be used many times by this function tinymt32_jump_by_polynomial to compute N-step jump.: tiny is a structure of type tinymt32_t. tiny must be initialized. tiny is overwritten by new jumped state.

Sample program

Here is a sample program sample.c

Back to TintMT Home Page