Last week I wrote about a mental random number generator designed by George Marsaglia. It’s terrible compared to any software RNG, but it produces better output than most people would if asked to say a list of random digits.

Marsaglia’s RNG starts with a two-digit number as a seed state, then at each step replaces n with the 10s digit of n plus 6 times the 1s digit. Here’s the generator in Python form, taken from the earlier post.

state = 42 # Set the seed to any two digit number

def random_digit():
    tens = lambda n: n // 10
    ones = lambda n: n % 10
    global state
    state = tens(state) + 6*ones(state)
    return ones(state)

Only the last digit of the state is returned: the state has two digits but the output has one digit.

Alexander Janßen left an interesting comment on Mastodon regarding the generator:

I’m not sure if it’s already documented anywhere, but a random seed of 59 sticks and always returns a 9. This is similiar to the initial state of 0 (which is more trivial). In return that means, that the state 59 is never reached from any other sequence.

To explore this further, let’s look at just the states of the mental RNG, not the output digits.

If you start with the state 1, you will produce each of the numbers from 1 to 58 in a cycle. It follows that if you start at any number between 1 and 58 you’ll produce the same sequence of states in a cycle, though starting at a different point in the cycle.

… → 1 → 6 → 36 → 39 → … → 1 → …

If you start at 59, you’ll stay at 59 because 5 + 6×9 = 59. In this case, the RNG literally does what is described in the Dilbert cartoon below.

Collatz interlude

If you start with a seed larger than 59, you’ll eventually land on a state less than 59, and then produce the same cycle as described above. This is reminiscent of the Collatz conjecture, which I describe here as follows.

The Collatz conjecture asks whether the following procedure always terminates at 1. Take any positive integer n. If it’s odd, multiply it by 3 and add 1. Otherwise, divide it by 2. For obvious reasons the Collatz conjecture is also known as the 3n + 1 conjecture.

The Collatz conjecture remains an open question, though there has been some progress on the problem. I routinely get email from people who say they have no training in math but believe they have solved the problem. Recently they have begun to explain how an LLM led them to their proof.

Does the Collatz sequence get stuck in a cycle for some starting point? Nobody knows. But we can show every starting point for Marsaglia’s mental RNG ends up in a cycle.

Back to Marsaglia

If we start the mental RNG with 99, we next get 63, and then 24. So starting at 99, we end up in a cycle after two steps. The same is true starting at 69 or 89. Otherwise, any starting point between 60 and 98 leads us to a cycle after one step.

Marsaglia’s generator is supposed to be seeded with a two-digit number. What if we seed it with a larger number? For example, what if we start at 1066 and consider the 1os “digit” to be 106?

Each step of the algorithm reduces the state by an order of magnitude, and so if we start with a state greater than 1000, we eventually get to a state less than 1000. Then every state between 100 and 1000 leads to a cycle, usually the permutation of the digits 1 through 58, but the following three-digit states lead to the fixed point of 59.

118, 177, 236, 295, 354, 413, 472, 531, 590

Related posts

• Polynomial analog of the Collatz conjecture
• Evolution of random number generators
• How to test a random number generator

If you have a triangle with vertices A, B, and C, how would you generate random points inside the triangle ABC?

Barycentric coordinates

One idea would be to use barycentric coordinates.

1. Generate random numbers α, β, and γ from the interval [0, 1].
2. Normalize the points to have sum 1 by dividing each by their sum.
3. Return αA + βB + γC.

This generates points inside the triangle, but not uniformly.

Accept-reject

Another idea is to use an accept-reject method. Draw a rectangle around the triangle, generate points in the square, and throw them away if they land outside the triangle.

An advantage to this method is that it obviously works because it doesn’t rely on anything subtle. Three cheers for brute force!

The method is fairly efficient; on average only half the points will be rejected.

A disadvantage to all accept-reject methods is that they have variable runtime, though this only matters in some applications.

Accept-flip

There is a clever variation on the accept-reject method. Create a parallelogram by attaching a flipped copy of the triangle. Now randomly sample from the parallelogram. Every sample point will either land inside the original triangle or in its flipped twin. If it landed in the original triangle, keep it. If it landed in the twin, flip it back over and use that point.

This is like an accept-reject method, except there’s no waste. Every point is kept, possibly after flipping.

You can find code for implementing this method on Stack Overflow.

Barycentric coordinates fixed

Felix left a note in the comments that the barycentric approach would work if you draw the random weights from an exponential distribution rather than a uniform distribution. That goes against my intuition. I thought about using a different distribution on the weights, but I didn’t work out what it would need to be, but I did not expect it to be exponential. Apparently it works. Here’s a proof by plot:

Related posts

• Random points on a sphere
• Regular solinds and Monte Carlo integration
• Fibonacci lattice on a sphere