Japanese Version

dSFMT jump

SFMT page

- About SFMT jump function
- Download
- Install, Compile and Test
- Jumping-ahead again for the same jumping step size
- Samples of Parallel generation
- License

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 2^{MEXP}-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.

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

ψ = X^{N} mod ϕ.

This is the definition of the (N-step) jump polynomial.
Consequently, the degree of the jump polynomial 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.

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.

SFMTJump-src-0.1.tar.gz

SFMTJump-src-0.1.zip

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

- Install NTL if not installed.
- Expand archive file
- Copy
**jump**directory in SFMTJump-src-xxxx to the directory of SFMT. - Change directory to copied the jump directory
- If you specify gmp or gf2x when you installed NTL, you need to uncomment one of the below two lines in Makefile.
- make
- Check if OK is showed and no NG

SFMT-src-1.4 +---html +---params +---jump

#LIBGF2X = -lgf2x #LIBGMP = -lgmp

make all make check

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

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.

sample1.c file included in the
archive shows generation of
5 distinct sub-sequences using 10^{20} steps jump.
As far as the length of each sub-sequence is smaller than
10^{20} 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

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

See LICENSE.txt for detail.