in ,

Romu – Fine random number generators, Hacker News

This page: What is Romu? One Snowflake in History Top Quality Fast Capacity The Competition List of Romu Generators

More Information

Test suites: PractRand BigCrush (in TestU

Popular generators: Lagged Fibonacci Blackman-Vigna LCG PCG Mersenne Twister

What is Romu?

Romu is a new family of random-number generators that match the statistical quality (randomness) of the best popular generators, but are faster. In fact, due to the processor’s ILP (explained below), Romu generators add () delay to an application when inlined. In effect, Romu generators are infinitely fast when inlined. And they’re very fast when not inlined.

Such speed and high quality are possible because Romu generators are nonlinear, unlike most popular generators. A Romu generator combines the linear operation of multiplication with the nonlinear operation of rotation, yielding better randomness at higher speed.

Romu stands for rotate-multiply , which are the two arithmetic operations that all Romu generators employ. Most also perform one or more additions and / or subtractions. The names of Romu generators are suffixed with the name of the number of internal – bit variables they contain (which is their (state) ), so the three-variable version is named RomuTrio . We highly recommend RomuTrio because its state-size is large enough to make trouble overwhelmingly unlikely, and is small enough to not consume too many registers in the processor, which would slow down an application due to a phenomenon called register pressure . RomuQuad is a larger version for those running gigantic jobs while wanting even lower probabilities of trouble. RomuDuo might be faster due to its lower register pressure. RomuDuoJr might be even faster faster, and it’s very simple, consisting of only three arithmetic operations, but it might lose some randomness on large jobs.

You can learn all the details about Romu generators in the paper . Although this is a formal academic paper, the math in it isn’t overwhelming because it’s at the level of advanced algebra (except for one integral). The math derives equations for probabilities of trouble, such as the snowflake probability described next.

One Snowflake in History

Above, we mentioned that Romu generators are nonlinear. There is a reason people have avoided nonlinear generators in the past: Unlike a linear generator, a nonlinear generator does not have one cycle that covers all possible internal state-values. Instead, it gives you a random permutation of those values. Random permutations are known to consist of multiple cycles of random lengths. In the past, when generators stored their state in one – bit variable, these random cycle -lengths would cause users to sometimes encounter cycles that were too short. That problem eliminated nonlinear generators from consideration.

But nowadays, processors can easily handle – bit variables , and having two or three such variables In the generator’s state is no problem, which makes encountering a too-short cycle all but impossible. For example, if you gave RomuTrio (with (bits of state) the impossibly large job of outputting 2

numbers in one stream, the probability of encountering a too-short cycle is around that of randomly selecting a specific snowflake among all snowflakes that have fallen in Earth’s history (2


and also randomly selecting the Queen of England out of all of Earth’s population (2

. That inconceivably low probability of 2

– means that you will

never encounter a cycle that’s too short.

Some people might insist that a generator have one cycle with a guaranteed period (which eliminates nonlinear generators). That is unwise because they will lose the substantial benefit of higher speed in order to avoid a will-never-happen problem. The chance of randomly selecting one snowflake in Earth’s history and the Queen is nil. Losing a benefit to avoid that nil is unwise.

The snowflake-and-Queen probability tells us that the problem of too-short cycles has been solved, and now we can enjoy the increased speed that nonlinear generators can provide.

Top Quality

The Romu family has unusually good randomness, which is verified by passing the toughest test suites: BigCrush and PractRand. Both are brutal to random number generators, especially PractRand (which is newer). All Romu random number generators using – bit arithmetic pass both suites with no signs of stress. RomuDuoJr is the worst such generator, and even it passes easily.

It’s easier to appreciate the improved randomness of Romu generators using dot-plots of consecutive pairs of random numbers. Below, the left plot is from an LCG (linear congruential generator), which is historically the most common. The right plot is from a simple Romu generator. To make their patterns obvious, both generators were scaled down to 16 bits of state and run for their entire periods. The nonlinear Romu is obviously more random than the linear LCG.

(LCG (linear)) nonlinear) nonlinear) Fast

There are several reasons why Romu generators are faster than others:

126 Their nonlinear arithmetic requires fewer operations to attain a given level of randomness.    That improved randomness means that post-process scrambling of output is not needed, making Romu even faster.

What do you think?

Leave a Reply

Your email address will not be published.

GIPHY App Key not set. Please check settings

Three Years of Metal (2019), Hacker News

Three Years of Metal (2019), Hacker News

How a hacker’s mom broke into prison — and the warden’s computer, Ars Technica

How a hacker’s mom broke into prison — and the warden’s computer, Ars Technica