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.
Advantages of Procedural Generation:
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.
Thanks for reading this farπ.
Top comments (34)
Truly random number generators do not exist, since true randomness is only a theoretical concept.
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
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.
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?
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.
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.
So we can say that TRNGs exist maybe not scientifically 100% truly random but yeah , right?
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.
I think this information is enough to explain someone who doesn't have enough quantum realm info (like me) so thanks for that
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?
I think this is a topic where you can't either agree or disagree, what you think?
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 π
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?
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.
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?
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:
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.
Funny thing is - it was actually my physics professor who explained this.
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!
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".
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.
Newton was wrong. So was Einstein. And thatβs okayβ¦ | by Deep Breadth | Medium
Deep Breadth γ» γ»
Medium
Thanks for sharing this blog, looks interesting and surely matches our discussion
Yea but it's good enough for our uses
Agreed π―
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.
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.
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 likeRDSEED) if available. Exceptions (based on the used distro) exist.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.Glad I was able to help you understand something π
TLDR; truly random numbers aren't feasible but we do have some ways to create numbers that are "random enough" for most purposes.
Haha, that does sum up the blog
It was great
Ho, yeah, the good old Rapid Racer on PS1 and its fractal generator !
Haha never played it but based on your given link it does looks cool, reminds me of boats in GTA vice City
Be like Cloudfare, record bunch of lava lamps and hash the image into numbers.
Some comments may only be visible to logged-in visitors. Sign in to view all comments.