SFMT Jump

Japanese Version
dSFMT jump
SFMT page

Index

About SFMT jump function

For any given integer N, this jump function executes the N-step jump. Namely, from the given state, it computes the state of SFMT after N steps generation. This is equivalent to call the SFMT 32-bit integer generation 4N 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 SFMT.

SFMT is a random number generator with period being a Mersenne prime, namely, a prime of the form 2MEXP-1, with an integer MEXP (an acronym of Mersenne Exponent). MEXP=607, 1279, ..., 216091 are supported.

There are two stages for executing this jump: 1. calculation of the jump polynomial corresponding to N, and 2. change of the state into the state with N-step jump-ahead.

Stage 1: Calculations of the jump polynomial

From the characteristic polynomial ϕ of a linear random number generator and an integer N, we obtain the jump polynomial ψ

ψ = XN mod ϕ.
This is the definition of the (N-step) jump polynomial. Consequently, the degree of the jump polynomial ψ is less than the degree (=MEXP) of the characteristic polynomial ϕ, regardless of the jump step N.

The characteristic polynomial of SFMT with given degree (=MEXP) is stored in the file named 'characteristic.MEXP.txt' (where "MEXP" should be replaced with an appropriate Mersenne prime) included in the SFMT-jump archive file.

The executable binary file 'calc-jump' (created by using standard "make") calculates the (N-step) jump polynomial from the command line. Here is a usage: 

./calc-jump jump-step characteristic-file [no.]
    jump-step: This is "N" above. It is an arbitrary number between zero and 2^{SFMT_MEXP}-1.
               Indeed, arbitrary large integer may be used (by representing in the decimal form).
    characteristic-file: one of characteristic.{MEXP}.txt file
    [no.]: specifies which characteristic polynomial in
           the list of them in the file should be used. 0 is used if omitted.
           this is used for files in params directory.

Users can also call a C++ function 'sfmt::calc_jump' declared in the C++ header file 'SFMT-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. You must install this library in advance.

This Stage 1 does not refer to the SFMT internal state.

Stage 2: Jumping the internal state of SFMT ahead by using the jump polynomial.

This stage depends on MEXPs of SFMT, and the characteristic polynomial of SFMT should be identical with the one used in the jump polynomial calculation in Stage 1.

The function SFMT_jump written in C language executes this stage. For our convenience, we used C structure for SFMT internal state, and almost of all functions provided in SFMT ver. 1.3 were re-written to use SFMT structures. No support for ALTIVEC or BIG ENDIAN.

Download

SFMTJump-src-0.1.tar.gz
SFMTJump-src-0.1.zip

Install, Compile and Test

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

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

test-jump-MXXX files made by above, if invoked with '-s' argument, will report the CPU-time for (1) computing the jump polynomial and (2) computing the jumping ahead of the state, as follows: 

$ ./test-jump-M19937 -s
mexp 19937 jump 10^04 steps calc_jump: 0.806ms
mexp 19937 jump 10^04 steps SFMT_jump: 0.319ms
mexp 19937 jump 10^06 steps calc_jump: 3.562ms
mexp 19937 jump 10^06 steps SFMT_jump: 3.248ms
mexp 19937 jump 10^08 steps calc_jump: 6.480ms
mexp 19937 jump 10^08 steps SFMT_jump: 3.275ms
mexp 19937 jump 10^10 steps calc_jump: 9.385ms
mexp 19937 jump 10^10 steps SFMT_jump: 3.267ms
mexp 19937 jump 10^12 steps calc_jump:12.720ms
mexp 19937 jump 10^12 steps SFMT_jump: 3.273ms
mexp 19937 jump 10^14 steps calc_jump:15.429ms
mexp 19937 jump 10^14 steps SFMT_jump: 3.280ms
mexp 19937 jump 10^16 steps calc_jump:18.377ms
mexp 19937 jump 10^16 steps SFMT_jump: 3.301ms
mexp 19937 jump 10^18 steps calc_jump:21.416ms
mexp 19937 jump 10^18 steps SFMT_jump: 3.297ms
mexp 19937 jump 10^20 steps calc_jump:24.440ms
mexp 19937 jump 10^20 steps SFMT_jump: 3.233ms
mexp 19937 jump 10^22 steps calc_jump:27.389ms
mexp 19937 jump 10^22 steps SFMT_jump: 3.283ms

Jumping-ahead again for the same jumping step size

If the characteristic polynomial is identical, and the jumping step size N is identical, then one can reuse the computed jump polynomial in Stage 1. Namely, one does Stage 1 only once, and then from any state, by applying Stage 2, one obtains the state with N-steps jumping ahead. When MEXP is large (say > 10000), Stage 1 is much more time consuming than Stage 2. Thus, one may want to compute Stage 1 only once.

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 6 SFMT instances. This sample is included in the archive. sample2.c

License

SFMT-jump, as well as SFMT, can be used freely for any purpose, including commercial use.
See LICENSE.txt for detail.