User:Super mersenne/sandbox

The 64-bit Maximally Equidistributed F₂-Linear Generator with Mersenne Prime Period (MELG-64) is a family of 64-bit Mersenne-Twister-type pseudorandom number generators developed by Shin Harase and Takamitsu Kimoto between 2014 and 2017, and the corresponding paper was published on ACM TOMS in 2018. MELG-64 has 64-bit very long period based on linear recurrences over the two-element field F₂={0, 1} and is completely optimized in terms of the equidistribution properties with similar speed as 64-bit Mersenne Twisters.

Background

The 32-bit Mersenne Twister (MT) MT19937 is one of the most widely used pseudorandom number generator|pseudorandom number generators (PRNGs), but it is not completely optimized in terms of high-dimensional uniformity, which is a theoretical criterion of PRNGs. The 32-bit WELL generators was developed in order to overcome this weakness. As 64-bit PRNGs, MT19937-64 and SFMT19937 using SIMD were proposed, but there had existed no 64-bit MT-type PRNG completely optimized for high-dimensional uniformity.

Feature

• Fast generation competitive with 64-bit Mersenne Twisters.
• Very long period 2¹⁹⁹³⁷-1 ≈ 10⁶⁰⁰⁰.
  • This is the same period as widely used Mersenne Twisters.
  • Memory size requiring only 312 words (similarly to 64-bit Mersenne Twisters).
  • In accordance with memory size, implementations with various period lengths from 2⁶⁰⁷-1 to 2⁴⁴⁴⁹⁷-1 are provided.
• High-dimensional uniformity completely optimized.
  • This property is one of the most informative criterion for high dimensional uniformity of PRNGs.
  • In the case of 32-bit PRNGs, WELL generators were known, but 64-bit counterparts had not been developed.
• The non-zero coefficients of the characteristic polynomials drastically increased.
  • Approximately half of the coefficients of the characteristic polynomials are nonzero, and hence it is expected that MELG-64 recovers from 0-excess states very quickly.
• The algorithm based on linear recurrence over the two-element field F₂ and designed via several theoretical criteria.
• The jump-ahead algorithm implemented in order to obtain disjoint streams in parallel computing. (The default skip size is 2²⁵⁶.)

High-dimensional uniformity

An example of 2-dimensional equidiribution with 2-bit accuracy. We set the period P=2⁸-1 and transform unsigned binary integers x_i into floating point numbers u_i on the unit interval [0,1), and plot 2-dimensional output values (u_i, u_i+1) for the period P and add the origin (0, 0). If 2-dimensional equidistribution with 2-bit accuracy holds, the 2 most significant bits of u_i occur the same number of times over all possible (2×2)-bit patterns in the period P, except for the all-zero combination that occurs once less often. This means that if we partition the unit square [0, 1)² into 16 boxes of equal size by dividing the interval [0,1) into 2² segments, then each box contains the same number of points.

An example of not 2-dimensional equidistribution with 3-bit accuracy. The most significant 3 bits do not occur the same number of times over all possible (2×3)-bit patterns in the period P. Thus, if we partition the interval [0,1) into 2³ segments, each box does not contain the same number of points in the period P.

The high-dimensional uniformity is a theoretical criterion for PRNGs, which is assessed via the dimension of equidistribution with v-bit accuracy as follows.

Let

x₀, x₁, ..., x_P-1, x_P = x₀, ...

be an unsigned w-bit binary integer sequence with period P, where w is the word size of the intended machine. Let trunc_v(x_i) denote the number formed by the v most significant bits of x_i. Consider the kv-bit vectors for the entire period:

(trunc_v(x_i), trunc_v(x_i+1), ..., trunc_v(x_i+k-1)),   i = 0, ..., P-1.

A pseudorandom sequence x_i of w-bit integers of period P is said to be k-dimensionally equidistributed with v-bit accuracy if each of the 2^kv possible combinations of bits occurs the same number of times over the entire period P, except for the all-zero combination that occurs once less often.

The largest value of k with this property is called the dimension of equidistribution with v-bit accuracy, denoted by k(v).

This definition is based on the assumption that the higher digits are large numbers. In particular, the dimension of equidistribution ensures that the output values with the v most significant bits are uniformly distributed up to dimension k(v). Thus, as a criterion of uniformity, larger values of k(v) for each 1 ≤ v ≤ w is desirable.

Now we have a trivial upper bound

k(v) ≤ ⌊ log₂(P+1) / v ⌋

for each v = 1, 2, ...,w. Define the sum of the gaps

Δ := ∑ ⌊ log₂(P+1) / v ⌋ - k(v)),

where the sum is over all 1 ≤ v ≤ w.

If Δ = 0, the generator is said to be maximally equidistributed (ME).

Performance

The following table summarizes the CPU time (in seconds) taken to generate 10⁹ 64-bit unsigned integers and the figures of merit Δ and N₁. Here, N₁ is the number of nonzero coefficients of the characteristic polynomial and N₁ should be in the vicinity of the half of 19937.

Comparison: MT-type PRNGs corresponding to 64-bit output sequences.

Generators	CPU time(Intel)	CPU time(AMD)	Δ	N1
MELG19937-64	4.2123	6.2920	0	9603
MT19937-64	5.1002	6.6490	7820	285
MT19937-64 (ID3)	4.8993	6.7930	7940	5795
SFMT19937-64(with SIMD)	4.2654	5.6123	14095	6711
SFMT19937-64 (with SIMD)	1.8457	2.8806	14095	6711

Platforms (64-bit CPUs and OSs):

• CPU time (Intel): Intel Core i7-3770 (3.40GHz) Linux gcc compiler with -O3
• CPU time (AMD): AMD Phenom II X6 1045T (2.70 GHz) Linux gcc compiler with -O3

External links

• Implementing 64-bit Maximally Equidistributed F2-Linear Generators with Mersenne Prime Period
• SlideShares