Samyak Jain

Posted on

# Are Random numbers really random?

So recently a thought struck me that we use random functions in our software all the time right? Either in games or in machine learning models, cryptographic software, etc.

But are these "randomly" generated numbers are actually random? I mean there must be some algorithm that calculates this so-called random number right? And if it's calculated it's not really "random" now is it?

So today I'll try to explain how random is a random number in programming languages.

So all the random functions in different programming languages like Math.random() in Javascript are not "True" random number generators, they are called PRNGs (Psuedo Random Number Generators)

The word Psuedo is self-explanatory that these random generators are not truly random. So now the question that arises is - Okay random number generators are not truly random then to what extent these numbers are random?

This is the question that measures the quality of a PRNG.

There are many algorithms that are used to generate random numbers, but what all of them have in common is a Period and a Seed.

## Seed

A seed is an initial value that is passed in the random function to create a random number.
To understand how a seed works in a PRNG, Let's take a look at an algorithm called LCG (Linear congruential generator)

LCG

For those familiar with random number generator algorithms, do you have a favorite? Whether it's LCG, Xorshift, or another algorithm, do share your preferences and experiences with different generators.

• Back to the example of LCG

So the formula of an LCG is X = (a.Xcurrent + C) % mod m
where,
X is the sequence of pseudo-random numbers
m, ( > 0) the modulus
a, (0, m) the multiplier
c, (0, m) the increment
Xcurrent , [0, m) β Current Seed

So what happens is once the initial seed is selected it is passed in this equation where Xcurrent is the only thing that is variable and everything else is a constant, so the seed is passed in this equation as Xcurrent, and the operations are done, once the answer is generated, next time the previous answer is used as seed and so on.

Here is an example of how does it look

Let's consider an LCG with a specific set of constants:

`a = 7,`
`c = 5,`
`m = 32,`
and initial seed as 3

so
`1. X = (7*3 + 5) mod 32 = 26 => X = 26`
`2. X = (7*26 + 5) mod 32 = 11 => X = 11`
`3. X = (7*11 + 5) mod 32 = 22 => X = 22`
`4. X = (7*22 + 5) mod 32 = 19 => X = 19`
`5. X = (7*19 + 5) mod 32 = 26 => X = 26`
`6. X = (7*26 + 5) mod 32 = 11 => X = 11`

This is how once a seed is decided the generated value is used as a seed to create the next random number, Now am sure you must have noticed something strange in this sequence right? After point 4 the sequence started to repeat. First 26 and then 11 and so on?

## Period

So there are multiple algorithms to generate a PRN, like LCG or Xorshift128+ (Used by the v8 engine) but what all of them have in common is that there is a limit to producing random numbers before which they start to repeat the sequence. This is what is known as a Period. Every PRNG has repeatability after a point, now how long the sequence is before the numbers start to repeat is what tests the quality of the PRNG.

## Why there is a Period?

But why does this happen? Why do numbers start to repeat?

It might sound like a silly question, but it was bugging me so I tried to understand this,

what I understood is that this happens because computers have a limit to generate numbers, sure there are infinite numbers, but there is a limit till which a computer can comprehend, like in a 64-bit architecture that limit is β9,223,372,036,854,775,808 to 9,223,372,036,854,775,808 so computer needs to maintain the number in that limit.

So algorithms try to keep this number in range like in LCG after multiplication and addition in the seed, a modulus is performed so that the number does not keep increasing till the point that the computer can't comprehend it anymore.

And if there are only finite numbers that the computer can generate through an algorithm then after a while it's inevitable that the seed that started the sequence will be generated and once that number is generated the whole sequence will be repeated.

So yeah if you know the seed you can predict the whole sequence.
Here is a replit link for you to try I have set a seed and ran a loop for 10 values no matter how many times you run the loop it will have the same result.

Now if you are a Minecraft player you must have heard "seed" before as well. When you enter a seed that is shared by someone else you also get spawned in the same area as them. Why? Because Minecraft uses a random generator to create an area, and if it's random then it also has some seed, and if you have that same seed then yes you will get the same output.

Have you ever played a game that allowed you to input a 'seed' for generating the game world? Share your experience and any interesting outcomes!

While talking about PRNGs it is important to note that PRNGs are not cryptographically secure as also mentioned in the v8 Docs.

It is not recommended for hashing, signature generation, and encryption/decryption.

For those purposes you can use `window.crypto.getRandomValues` "but" at the cost of performance.

So why do we use PRNGs if it has so many flaws?

I mean you know the seed and voilΓ  you know the sequence, it's not cryptographically secure then where is it used?

## Applications of PRNGs

Well PRNGs are very efficient and fast they are very useful in games like you want to spawn the player at a random place and spawn some buildings randomly, but you don't want it to be truly random and efficient because games need to render everything fast.

If we go back to the example of Minecraft, Minecraft does not create the whole environment as soon as you enter in the game, because if that had been the case there would have been a great toll on the game and a huge storage space used by the game. Instead, it creates environments on the fly as players start to move in a direction.

Minecraft features randomly generated structures such as villages, temples, and dungeons. The placement of these structures adds surprises to the landscape, and their designs vary based on procedural algorithms.

Scalability: Minecraft's procedural generation allows the game to scale infinitely without the need for massive storage space for pre-designed maps.

Exploration: As players traverse the world, new chunks of terrain are generated dynamically, providing a sense of discovery and unpredictability.

Replayability: Different seed values and the randomness in terrain generation enhance the replayability of the game, as players can experience entirely new worlds with each playthrough.

Impact on Performance:

Generating terrain in real-time as players explore reduces the initial loading time and minimizes the demand on system resources compared to loading an entire pre-designed world.

PRNGs are also used for debugging, where engineers can pre-define the seed and can run iterations on a fixed sequence to run some tests.

Truly Random Number Generators are great but they come at the cost of performance so it's up to us to decide the tradeoff. Overall it was a great topic to read and learn about.

As a developer, how often do you use random number generators in your projects? Do you have any favorite algorithms or tips for ensuring randomness in your applications?

In conclusion, while pseudorandom number generators (PRNGs) play a crucial role in various applications, from gaming to simulations, understanding their limitations is equally important. The predictable nature of PRNGs, marked by periods and seed-dependent sequences, raises questions about their suitability for cryptographic purposes. As developers, we navigate the trade-off between efficiency and true randomness, opting for PRNGs in scenarios where rapid, reproducible results are paramount. Reflect on the challenges posed by the inherent predictability of PRNGs and consider: How do we balance the convenience of PRNGs with the need for cryptographic security in our applications?

If there is anything that I missed about PRNGs that could have made the blog better or you have any questions related to it please let me know in the comments.

Jon Randy ποΈ

Truly random number generators do not exist, since true randomness is only a theoretical concept.

Samyak Jain

Well True Random generators do exist, here is a site which let's you generate True Random numbers - random.org/

They have also explained how they are generating these true randoms

Jon Randy ποΈ • Edited

The fact that they can explain their method makes them not random. For something to be truly random, it would depend on nothing, and be 'chosen without method'. It's a purely theoretical concept.

Samyak Jain

Doesn't truly random mean that you can't predict it? What does it have to do with "chosen method"? I mean they are relying on environment and I think that's random enough right?

Jon Randy ποΈ

With enough information, you could predict that. That's the point.

You said it correctly with your phrasing 'random enough' - it's probably beyond the practical reach of anyone to predict it... but that doesn't make it truly random.

Thibaut Andrieu

random.org seems based on "atmospheric noise" as they said. I didn't check the details, but this seems chaotic enough to make the random sequence be unpredictable in practice.

There is also qrandom.io/, which seems to generate random values based on quantum random generator. These generators are truly unpredictable, even if you know the exact state of the whole universe.

Samyak Jain

So we can say that TRNGs exist maybe not scientifically 100% truly random but yeah , right?

Thibaut Andrieu

As I know, (I have good scientific background, but I'm not an expert), quantum mechanism is non-deterministic.

When you flip a coin, if you exactly know its mass, its speed, the gravity, etc... you can predict on which face it will fall. So, even if you have 50% chance having heads, 50% tails, there is a way to predict the actual value. Its like for PRNG. If you exactly know the system, you can predict it.

BUT, assuming you flip a "quantum coin", you know it has 50% chance having heads, 50% tails, but you CANNOT predict the result. It's difficult to understand, but even if you put your coin under a microscope, even if you know the exact state of the coin, you cannot predict the value you will read. So, quantum based random generator are... truly random. You cannot predict them, even if you know in which state they are.

Samyak Jain

I think this information is enough to explain someone who doesn't have enough quantum realm info (like me) so thanks for that

Jon Randy ποΈ

Again this is an assumption based on incomplete knowledge, but probably again 'random enough'.

The funny thing is, 'true' randomness is impossible to check for because... what would you check for?

Samyak Jain

I think this is a topic where you can't either agree or disagree, what you think?

Thibaut Andrieu • Edited

No no no, it's not non-deterministic because we have incomplete knowledge. It has been proved to be non-deterministic, and not because of chaotic behavior or imprecision in measure, or incomplete knowledge, but in essence. There are formal demonstration that involve high level mathematic I don't even understand, but I trust the guys that did it π

One of the explanation is that, you just cannot know the exact state of a quantum system because of Uncertainty principle.

By analogy, to measure something, you have to "light it up". Else, it's just dark and you see nothing. But if you "light it up", you send energy in the system, that will interact and change its state. So you cannot measure a system without changing it, even a little bit. But to predict a system, you have to know its current state. So you have to measure it. So, you will change its state...
In the end, it is impossible to know the current state of a quantum system. That's why we say it is in "state overlap". We know the probability for the system to be in one or the other state, but we don't know which one, until we measure it. But as we saw, measuring it change its state π€ͺ

You can disagree with this. But this means you disagree with the whole quantum physic. You can, and that's how science advances. But up to you to find a better model π

Samyak Jain

No, I think at this point I can't disagree, this explanation is enough to prove that TRNGs do exist. And it's a good one and now I have gotten an interest in reading about Quantum real a bit too maybe I won't get it? But what's the harm in checking it out right?

Jon Randy ποΈ • Edited

We have incomplete knowledge of quantum physics - it is something we made up to fit observations, it isn't an absolute. To the best of our knowledge, it appears to be non-deterministic, but we don't know that for sure. A random number depending on it is depending upon a human assumption that could well be wrong.

I've studied physics, and understand the uncertainty principle - but there's nothing to say that a discovery tomorrow couldn't suddenly render all the theories of quantum physics wrong - or not as non-deterministic as we thought.

Truly random is an abstract, unachievable concept - but we can get close enough to it to the ideal to make it 'random enough' for our purposes.

Samyak Jain

I think any generator is called a True random generator as long as any "human" can't predict it, as @tandrieu also pointed out that no one can predict the state in the quantum realm, "no one" and this no one is us the humans and as long as humans can't find a way to predict it, it can be called True random right? I mean we do need to find a difference between generators we can predict right now vs the ones we cant right?

Jon Randy ποΈ

No-one can predict quantum states yet - but we cannot assume this will never be the case - and for the same reason we cannot call a RNG based on it truly random.

For something to be truly random - as the defintion of the word 'random' states - the event should be:

made, done, happening, or chosen without method or conscious decision

i.e. free of any outside, measurable influence. An effect without a cause if you will. To my knowledge, no known mechanism for this exists... and things that claim to be have just come from theories posited by scientists to explain their observations. There is no way to prove true randomness - that would be contradiction in itself, but we certainly cannot say that something is truly random if it is relying on assumptions/theories.

If you want the definition of a TRNG to be one that produces output that cannot be predicted by any human right now - then fine - TRNGs definitely do exist... and I don't doubt that.

Trying to make something truly, completely random though - is a fool's errand.

Jon Randy ποΈ

Funny thing is - it was actually my physics professor who explained this.

Samyak Jain

Haha, you do have a lot of knowledge about this topic. I'm sure you must have had a good debate with your professor as well? Also, I'm sure people will learn a lot from the comment section alone now. Haha!

Thibaut Andrieu

Interesting debate π

For quantum state, I have doubt we manage one day to predict them. The model seems quite robust, and has for now resisted to all tests to fail it. If we manage to do such a thing, the whole quantum physic would collapse, and we would have discovered a brand-new science. God, that would be so awesome !

Mathematic contains an infinity of things that cannot be demonstrated. They are just "true" (or "false"), and you have to admit it. I'm quite sure real world also contains those kinds of singularities. Thing that are "just the ways they are".

Jon Randy ποΈ • Edited

That's the great thing about Science - we never really know if it's "correct", and good science will always be open to new evidence, interpretations, and theories - which, if proven - will refine our understanding.

βAll models are wrong, but some are useful.β - George E.P. Box

Samyak Jain

Thanks for sharing this blog, looks interesting and surely matches our discussion

Lev N.

Yea but it's good enough for our uses

Samyak Jain

Agreed π―

Florian Rappl

Unfortunately the assumption that all random functions somewhere are PRNGs is wrong. We have true random number generator built into hardware. Since these are usually quite slow they mostly serve as seed input for a PRNGs.

Most likely of your machine can also produce real random numbers using the RDRAND instruction.

Samyak Jain

Yeah, I agree and that's why I only mentioned the programming language's random functions, although am curious how does hardware generates this random number? Atmospheric noise? I thought for PRNGs we normally use timestamp.

Florian Rappl

That depends on the hardware RNG - it can be thermal-based / brownian motion, but atmospheric noise or general current fluctuations are also a viable source. There are also more sophisticated methods. In general such hardware RNGs don't give better performance (as mentioned they are quite slow) and are also not used in applications where randomness is crucial (the classic MT19937 is still sufficiently good). They are good, however, for cryptographic applications under certain circumstances (e.g., OpenSSL allows you to use them).

If you refer to timestamps for the seed of a PRNG that can be true (in cases no seed has been given), but then again it fully depends on the framework and usage. Consider `/dev/random` - they use a mix of different sources incl. `RDRAND` (and similar like `RDSEED`) if available. Exceptions (based on the used distro) exist.

Sohail Pathan

Wow.. I remember using `Random.nextInt()` for testing against a test case. I was curious but was too lazy to know what goes underneath. Now, I understand the underlying mechanism.

Samyak Jain

Scott Reno

TLDR; truly random numbers aren't feasible but we do have some ways to create numbers that are "random enough" for most purposes.

Samyak Jain

Haha, that does sum up the blog

Thibaut Andrieu

Have you ever played a game that allowed you to input a 'seed' for generating the game world?

Ho, yeah, the good old Rapid Racer on PS1 and its fractal generator !

Samyak Jain

Haha never played it but based on your given link it does looks cool, reminds me of boats in GTA vice City

Techie Kho

Be like Cloudfare, record bunch of lava lamps and hash the image into numbers.