TinyMT Jump Function
Japanese Version
For a given 128bit integer N, this jump function executes the
Nstep 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
TinyMTJumpsrc1.2.tar.gz
header files are changed to fit to C++.
TinyMTJumpsrc1.2.zip
header files are changed to fit to C++.
TinyMTJumpsrc1.1.tar.gz
Document adn sample are refined.
TinyMTJumpsrc1.1.zip
Document adn sample are refined.
TinyMTJumpsrc1.0.tar.gz
TinyMTJumpsrc1.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 TinyMTJumpsrcxxxx to
the directory of TinyMT.
TinyMTsrcxxx
+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 128bit
integer specified by lower_step (lower 64bit) and upper_step
(upper 64bit).
N should be between 0 and 2^{128}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 jumpingahead.
Users can specify zero to 2^{128}1 steps,
using two 64bit arguments. However, note that the period of the
sequence is 2^{127}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 timeconsuming (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^{128}1 steps,
using two 64bit 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 Nstep jumping
ahead, regardless to the present state.
Thus, if N is fixed and Nstep 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 Nstep 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