dSFMT Jump

Japanese Version
SFMT jump
SFMT page


About dSFMT jump function

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.

Step 1: Calculations of jump polynomial

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.

Step 2: Changing internal state of dSFMT to jumped state.

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.



Install, Compile and Test

Test program needs source programs of SFMT ver. 2.2 to be compiled.

  1. Install NTL if not installed.
  2. Expand archive file
  3. Copy jump directory in dSFMTJump-src-xxxx to the directory of dSFMT.
  4. SFMT-src-2.2
  5. Change directory to copied jump directory
  6. If you specify gmp or gf2x when you installed NTL, you need to uncomment one of below lines in Makefile.
  7. #LIBGF2X = -lgf2x
    #LIBGMP = -lgmp
  8. make
  9. make all
    make check
  10. Check if OK is showed and no NG

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

Samples of Parallel generation

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.