Initial numbers generated by Util/random.sml have unexpected regularities

[MortenRhiger]

Version

110.99.2

Operating System

• Any
• Linux
• macOS
• Windows
• Other Unix

OS Version

No response

Processor

• Any
• Arm (using Rosetta)
• PowerPC
• Sparc
• x86 (32-bit)
• x86-64 (64-bit)
• Other

System Component

SML/NJ Library

Severity

Minor

Description

The first ca. 1100 numbers (and perhaps more) produced by Random.randInt display unexpected (to me) regularities (see the charts below). The same regularities show up for the few seeds I tried.

Transcript

The numbers produced look almost like a sine wave scaled by the count. The same regularities show up for the few seeds I tried.

Here are the first 1100 numbers (seed (0, 1)):

And here are the first 300:

Expected Behavior

I am aware that a random sequence must contain long streaks of only positives and long streaks of only negatives (and even display sinusoidal behavior from time to time), but I didn't expect to find them so early in the sequence produced by a random-number generator.

If this is a known and desired symptom of the SWB algorithm, then the solution might be to describe it in the documentation.

Steps to Reproduce

val seed = Random.rand(0,1);
fun loop n = if n > 0 then
               ( print (Format.format "%d\n" [Format.INT (Random.randInt seed)]);
                 loop (n - 1) )
             else ();

Running loop 1200 writes the 1200 numbers plotted above.

Additional Information

No response

Email address

morten.rhiger@gmail.com

[JohnReppy]

It is probably time to replace the Random implementation with something better. I've ported the 64-bit Mersenne Twister implementation to SML, I just need to wrap it with an interface that is compatible with the RANDOM signature (and port the 32-bit version for 32-bit machines).

[JohnReppy]

I have replaced the Random structure with 32-bit and 64-bit versions of the Mersenne Twister implementation. I have tested these against the C reference implementation and they agree (at least for the first 1000 numbers). These new versions will be in the 110.99.4 and 2023.1 releases.