Random number?

[raidho36]

You don't give any explanation

Here's the deal. PRNG uses strictly defined function for generating it's next value, specifically:

Code: Select all

#define RAND_MAX 0x00010000 /* that would be 65536 */
static unsigned int seed = 1;
void srand ( int s )
{
  seed = s;
}

unsigned int rand ( void )
{
  seed = seed * 0x00FACEXD + 0xDEADBEEF;
  return seed % RAND_MAX;
}

(this is almost line-to-line ripped from glibc, and msvcrt uses exactly the same)

This makes it obvious why same seed gives same sequence. This would be quite good enough, nevertheless it may be not. To increase entropy, you must interfere with an algorithm, particularry by modifying at random multiplication and addition values, or just the seed itself. To do that, you must somehow find a data that could not be predicted, i.e. being really random. Hardware random generators has noise generators which naturally source them truily random stream of data. Software emulation must gather "noise" from some of the sources available. One of such sources is user input. The other is natural fluctiations in program execution flow.

A player won't try to guess what the (P)RNG will give.

The whole point to use it in games is so the player won't see any pattern, not encryption or something.

I don't think you can increase the entropy of a random stream by seeding its own randomness to itself

In general, yes, you can't. But if you can't exactly predict how many times random is called between randomization, then it does increases entropy.

math.randomseed ( math.random ( ) ) is the same as math.randomseed(0) by the way. I guess you meant something different.

Probably. It was supposed to set new seed at random.

[vrld]

To increase entropy, you must interfere with an algorithm, particularry by modifying at random multiplication and addition values, or just the seed itself.

An often made fallacy, Boolsheet hinted at that: The sum of two uniformly distributed random values is no longer uniformly distributed. It doesn't matter whether the value is "really random" (what is that, by the way?) or not.

I don't think you can increase the entropy of a random stream by seeding its own randomness to itself

In general, yes, you can't. But if you can't exactly predict how many times random is called between randomization, then it does increases entropy.

Let's use Math to check that!
Although the Lua manual does not guarantee any "statistical properties", it also states that math.random returns a uniform pseudo-random integer, so let's assume this is true¹. This means we can measure the entropy of using math.random() with reseeding after some amount of time and just using math.random() without reseeding.
Information theory defines the entropy of a discrete random variable \(X\) as \[H(X) = E[I(X)] = \sum_{x\in\mathcal{X}}p(x)I(x) = -\sum_{x\in\mathcal{X}}p(x)\log p(x).\]We can only estimate the true distribution \(p(x)\), but the strong law of large numbers assures that a sample estimate (given indipendent, uniform distributed samples) almost surely converges on the expected value of the real distribution. The estimation is better when \(\mathcal{X}\) is small, so let's draw our samples from math.random(2). The entropy can be estimated as \[H(X) = \log N - \frac{1}{N}(n_1\log n_1 + n_2\log n_2),\] where \(n_1,n_2\) are the times we drew 1 or 2 respectively.

The following code³ is used to measure the entropy with reseeding. Similar code is used to measure without reseeding.

Code: Select all

math.randomseed(0) -- reproducibility - feel free to delete this line
t, dt_reseed, n = 0, math.random() * .1, {0,0}
function love.update(dt)
    t = t + dt
    if t > dt_reseed then
        t, dt = 0, math.random() * .1
        math.randomseed(math.random(2^30))
    end
    sample = math.random(1,2)
    n[sample] = n[sample] + 1
    if n[1] + n[2] > 10000 then -- more than enough, but feel free to increase this number
        print('Entropy:', math.log(n[1]+n[2]) - 1/(n[1]+n[2]) * (n[1] * math.log(n[1]) + n[2] * math.log(n[2])))
        love.event.push('quit')
    end
end

I get the following results (higher is better):
With reseeding: H(X) = 0.69314033691313
Without reseeding: H(X) = 0.6931395770614

So no, it doesn't.


¹ It wouldn't matter anyway, since we can't change the RNG anyway.²
² Well, actually there is love.math.random(), but we don't guarantee anything about that either.
³ This should be embedded in a real love game to make use of random frame times. I embedded it into Phlux and got the following results: with 0.6931457358482, without 0.69313705755048

[raidho36]

The sum of two uniformly distributed random values is no longer uniformly distributed.

Yes, it will be a "bell" distribution (I don't know the right term). How is it related to modifying the seed?

what is that, by the way?

The value is random if you can't predict it, come on.

Let's use Math to check that!

Load of invalid assumptions, I'm not buying it, sorry. But nice try.

What Lua manual says about random is that math.random almost directly invokes system rand function, period.

I guess it's time to acknowledge that "entropy" was the wrong term to describe randomness. But it was obvious that we all understood it as number randomness in general. The single most important property of random is being unpredictable, and additional randomizing improves this next-to-zero quality of PRNGs.

[Plu]

I don't know about you, but I'm not good enough at math to be able to predict the next output of a device that does a billion calculations per second. Can you point out some way in which the output from the random function would not be "unpredictable", as you say?

Because I've never noticed any patterns in it and I've been using it for years.

[raidho36]

If you did not, good for you. As I said, that simple random function is good enough for such applications, it's just may result in visible patterns if you have some kind of wild coincidence in your program. Additional randomizing solves it. You don't actually need to use it in any way, but doing so breaks any pattern that could possibly emerge.

[micha]

I'd be actually interested in a real example, where additional randomization makes a program better? I cannot come up with any example.

As a rule of thumb, I recommend everyone to just use math.random() as it is, without any modification (like addition randomization), because it simply does not improve the quality of the numbers one gets.

If anyone knows of a counterexample, I am happy to learn.

[bartbes]

it's just may result in visible patterns

Wait a second.. wasn't it guaranteed to be uniform? Also, this is a problem with human perception, we tend to see patterns in noise, in fact, so much that actual random things appear to have more patterns than a prng.

[raidho36]

wasn't it guaranteed to be uniform?

It never was. It's just said to be more or less seemingly random.

I'd be actually interested in a real example

this is a problem with human perception

Not exactly. PRNGs are known for giving you patterns, no point denying it. If your random application pattern does not match random generation pattern, then you won't notice patterns for quite long time (maybe long enough to forget any previous pattern), plus the whole big picture pattern would be a very long sequence. But if it match then you will see short loops of noticeable patterns that repeats over and over. I once wrote a program to generate random programs (lol) and it would consistently give me patterned output. You can think of it as a wallpaper: it has unique picture on it that goes on and on with new shapes and colors, but only until it hits pattern length, at which point you start clearly see the pattern in it.

[micha]

Can you post a .love that demonstrates this? I'd like to understand what you mean by patterns.

[vrld]

Yes, it will be a "bell" distribution (I don't know the right term).

I think you mean a normal or Gaussian distribution. It's the one prevalent in nature, but not the same as the uniform distribution. Repeatedly adding two uniformly distributed random variables converges on the normal distribution. Multiplication has nonlinear effects. I have explained this elsewhere. Reseeding doesn't seem to have any effect at all.

what is that, by the way?

The value is random if you can't predict it, come on.

I was asking for a proper definition and would have accepted a number of answers (e.g. "high entropy", "uniformly distributed"). But not a vague feeling, come on.

Load of invalid assumptions, I'm not buying it, sorry. But nice try.

All assumptions have been carefully considered and are valid within reason. If you don't feel this way, please be so kind to point out any errors. It would be even better if you provided a founded explanation of your point of view.

I guess it's time to acknowledge that "entropy" was the wrong term to describe randomness.

No, it is exactly the right term, as defined and used in information theory and statistics.