Self-Avoiding Random Walk Test

Test Purpose
The test evaluates the randomness of the output vector of the generator. The stable response is the frequency of achieving the upper side of the lattice by the point walking randomly along the sites.
First Level Test
A random particle walks along the sites of a square lattice. With each new step, the particle moves in one of possible directions one step forward corner-wise. A square lattice has two types of sides: the lower and left-hand sides are totally reflecting, while the upper and right-hand sides are totally adsorbing. Reaching the lower and left-hand sides, the vector of the movement direction makes a 90-degree bend. The upper and right-hand sides adsorb the particle when it reaches them and the walking process completes. The particle starts its movement from the lower left-hand site of the lattice in the northeast direction. If the particle encounters an unvisited site, it changes the direction vector with a 1/2 probability clockwise or counter-clockwise by 90 degrees and continues the walking process. If the particle encounters an already visited site of the lattice, it defines the movement direction according to the conditions of inadmissibility of re-tracing at least a part оf the passed path.
Due to the symmetry of the task, either upper or the right-hand side should equiprobably adsorb the particle. The test determines the frequency of the achievement of the upper side of the lattice by the result of 500 iterations of the walking process. If
is the number of attempts when the particle reaches the upper side, then
= (2
- 500)/√
has the close to standard normal distribution
. The result of the first level test is the p-value
p = Φ(K)
Second Level Test
The test performs the first level test ten times. The result of each iteration of the first level test is the p-value
= 1, 2, ..., 10. The test applies the Kolmogorov-Smirnov goodness-of-fit test with Anderson-Darling statistics to the obtained p-values of
= 1, 2, ..., 10. If the resulting p-value is
< 0.05 or
> 0.95, the test fails.
Final Result Interpretation
The final result of the test is the percentage FAIL of the failed second level tests. The test performs the second level test ten times. The acceptable result is the value of FAIL < 50%.
Tested Generators
Function Name
not applicable

Product and Performance Information


Intel's compilers may or may not optimize to the same degree for non-Intel microprocessors for optimizations that are not unique to Intel microprocessors. These optimizations include SSE2, SSE3, and SSSE3 instruction sets and other optimizations. Intel does not guarantee the availability, functionality, or effectiveness of any optimization on microprocessors not manufactured by Intel. Microprocessor-dependent optimizations in this product are intended for use with Intel microprocessors. Certain optimizations not specific to Intel microarchitecture are reserved for Intel microprocessors. Please refer to the applicable product User and Reference Guides for more information regarding the specific instruction sets covered by this notice.

Notice revision #20110804