Random number gen w/ seed acting non-deterministic

Question

I have programmed for many years, and the issue I am presenting now is probably one of the strangest I have come across.

There is a block of code in my app which randomly generates a sequence of tokens, with three possible types, let's say A, B or C.

So 10 tokens might be ABCCAAABAC.

At the beginning of the block of code, the random number generator seed is initialised like so:

math.randomseed(seed)
math.random()

Now, unsurprisingly when the seed value stays constant, I always get the same sequence of tokens, because the random generation code executes in a deterministic manner. Well, almost always.

Actually, on rare occasions, out of the blue, I will get a different random sequence given the same seed. Then it's back to normal before I know it. You're probably thinking - ah, side effects, this is probably a state related issue whereby the block of code which generates the random sequence of tokens utilises a variable which changes how many times it calls random() (for instance). However, I am 99% certain that I've controlled for all obvious side effects. There's only a few places in the block of code which access the external state, and they all remain constant.

The plot thickens even more - this issue has only been apparent to me on an Android deployment of the app that I've been building. Admittedly, this is a rare bug, and I can't seem to reliably repeat it. So it might also be present in the iOS deployments. But I've yet to come across it on other platforms. I might as well mention that I'm using lua scripting via the Corona SDK to develop the app.

I have given this issue much thought, and have narrowed it down to a few possibilities:

1. Interaction with another thread which uses the same random number generator, which I'm unaware of
2. (Is this even possible in lua?) Some sort of heap corruption is leading to strange side effects
3. I've messed up and there's some damn obvious reference to external state which I've missed throughout many hours of debugging

The most painful aspect of all this is the non-repeatability of the bug. Most of the time the block of code acts perfectly deterministically given a repeated seed. Then it is as though there's a phase of non-determinism, which then dissipates again after some unknown amount of time. I would love to pick the brains of an expert here.

What could be going on here? Also - is it possible there could be anything platform specific going on with this particular issue, since I've only seen it on Android deployments?

For reference, here is the full block of code. It's actually generating tokens with two random properties (one of three colours, and one of three shapes), but that doesn't mean much in terms of the essence of the problem.

math.randomseed(currentRandomSeed)
math.random()

local tokenListPlan = {}

-- randomly assign weighting distribution
local thresh1, thresh2
while (true) do
    local s0 = math.random(1, 99)
    local s1 = math.random(1, 99)
    local c0 = s0
    local c1 = s1 - c0
    local c2 = 100 - c1 - c0
    if (c0 >= eng.DEVIATION_THRESHOLD and c1 >= eng.DEVIATION_THRESHOLD and c2 >= eng.DEVIATION_THRESHOLD) then
        thresh1 = c0
        thresh2 = c0 + c1
        break
    end
end

-- generate tokens (deterministic based on seed)
for i = 1, sortedCountTarget do
    local token
    local c = 1

    local rnd = math.random(1, 100)
    if (rnd < thresh1) then -- skewed dist
        c = 1
    elseif (rnd < thresh2) then
        c = 2
    else
        c = 3
    end

    if (paramGameMode == eng.GAME_MODE_COLOR) then
        local rnd46 = math.random(4, 6)
        token = {color = c, shape = rnd46}
    elseif (paramGameMode == eng.GAME_MODE_SHAPE) then
        local rnd13 = math.random(1, 3)
        token = {color = rnd13, shape = c + 3}
    else
        local rnd13 = math.random(1, 3)
        local rnd46 = math.random(4, 6)
        token = {color = rnd13, shape = rnd46}
    end

    tokenListPlan[#tokenListPlan + 1] = token
end

Flatling

where exactly do you set the randomseed? it may be that, in android, the randomseed setting line is run more than once for whatever reason. – Neither

Just before the block of code (nothing in between), I'll edit the post to be less ambiguous here. Unfortunately I can't see any way it could be executing more than once, especially not sporadically... – Flatling

In some cases does math.random fire more than just the expected amount during the time this code is running? Try wrapping it into a function which uses a closure to count the amount it's been called. See if it changed when you get different results. – Squatter

You could simply create your own RNG, e.g., as in this SO Q&A. – Antipyrine

@DougCurrie Yep I have been considering doing this. In fact I can get around the whole issue by just storing the entire generated sequence in memory and reusing it when required, instead of regenerating with the same seed. But I suppose this question is of academic interest as much as it is practical - and also to rule out any potential serious issues in my program that might have caused this as a side effect. – Flatling

@Squatter I've already tried variants of that to locate any issues, but it's a good idea, I'll have a go at exactly what you mentioned at some point and see if it yields anything interesting. As I said though, I'm almost certain there's no way external state is influencing the flow of execution (i.e. the number of times random() is called) – Flatling

Probably, ANSI C rand() function is not thread-safe on your platform – Poucher

Answer 1

https://docs.coronalabs.com/api/library/math/random.html states:

This function is an interface to the simple pseudo-random generator function rand provided by ANSI C. No guarantees can be given for its statistical properties.

This makes me wonder if other programs use the same function. That could lead to those conflicts, while also more or less explaining why they only happen sometimes.

Patroclus