Japanese Version
SFMT jump
SFMT page
For a given integer N, this jump function executes the N-step jump. Namely, from the given state, obtain the state of dSFMT after N steps generation. This is equivalent to call the dSFMT double precision floating point number generation 2N times with discarding the outputs. A typical usage of a jump function is to obtain distinct sub streams from a whole period of pseudorandom number sequence generated by one dSFMT.
There are two steps for doing jump. Calculations of jump polynomial and changing internal state.
To calculate jump polynomial, we use pre-calculated polynomials for
MEXPs, we omit explanation of the polynomial.
The pre-calculated polynomials are stored in
'poly.{MEXP}.txt files.
The executable binary file 'calc-jump' calculates jump polynomial
from command line. Here is a usage:
./calc-jump jump-step polynomial-file
jump-step: a number between zero and 2^{DSFMT_MEXP}-1.
large decimal number is allowed.
polynomial-file: one of poly.{DSFMT_MEXP}.txt file
Users can call C++ function 'dsfmt::calc_jump' in C++ header file 'dSFMT-calc-jump.hpp' to calculate jump polynomials.
NTL: A Library for doing Number Theory by Victor Shoup is used for polynomial calculation and handling large integers.
This step does not use dSFMT internal state and independent from MEXPs except file names of the pre-calculated polynomials.
This step depends on MEXPs of dSFMT, and the polynomial file dSFMT should be the same as one used for the jump polynomial calculation.
The function dSFMT_jump written in C language does this step. For our convenience, we used C structure for dSFMT internal state, and almost of all functions provided in dSFMT ver. 2.2 were re-written to use dSFMT structures.
dSFMTJump-src-0.1.tar.gz
dSFMTJump-src-0.1.zip
Test program needs source programs of SFMT ver. 2.2 to be compiled.
SFMT-src-2.2 +---html +---jump
#LIBGF2X = -lgf2x #LIBGMP = -lgmp
make all make check
test-jump-MXXX files made by above can invoke with '-s' argument like this:
$ ./test-jump-M19937 -s mexp 19937 jump 10^04 steps calc_jump: 0.707ms mexp 19937 jump 10^04 steps dSFMT_jump: 0.166ms mexp 19937 jump 10^06 steps calc_jump: 3.527ms mexp 19937 jump 10^06 steps dSFMT_jump: 3.657ms mexp 19937 jump 10^08 steps calc_jump: 6.310ms mexp 19937 jump 10^08 steps dSFMT_jump: 3.628ms mexp 19937 jump 10^10 steps calc_jump: 9.221ms mexp 19937 jump 10^10 steps dSFMT_jump: 3.579ms mexp 19937 jump 10^12 steps calc_jump:12.175ms mexp 19937 jump 10^12 steps dSFMT_jump: 3.638ms mexp 19937 jump 10^14 steps calc_jump:15.176ms mexp 19937 jump 10^14 steps dSFMT_jump: 3.630ms mexp 19937 jump 10^16 steps calc_jump:18.064ms mexp 19937 jump 10^16 steps dSFMT_jump: 3.626ms mexp 19937 jump 10^18 steps calc_jump:20.959ms mexp 19937 jump 10^18 steps dSFMT_jump: 3.606ms mexp 19937 jump 10^20 steps calc_jump:23.884ms mexp 19937 jump 10^20 steps dSFMT_jump: 3.600ms mexp 19937 jump 10^22 steps calc_jump:26.920ms mexp 19937 jump 10^22 steps dSFMT_jump: 3.592ms
sample1.c file included in the archive shows generation of 5 distinct sub-sequences using 1020 steps jump. As far as the length of each sub-sequence is smaller than 1020 the sub-sequences are not overlapping.
Getting distinct sub sequences is an important purpose of
jump function, however jump function is also available to get
a sub-sequence using parallel computing.
Here is a sample of generating a sequence using 5 dSFMT instances.
This sample is included in the archive.
sample2.c
sSFMT-jump, as well as sSFMT, can be used freely for any purpose,
including commercial use.
See LICENSE.txt for detail.