Seeding PRNGs with the Time Stamp Counter

[deltarho[1859]]

“The uncertainty principle, also known as Heisenberg's indeterminacy principle, is a fundamental concept in quantum mechanics. It states that there is a limit to the precision with which certain pairs of physical properties, such as position and momentum, can be simultaneously known. In other words, the more accurately one property is measured, the less accurately the other property can be known.”

Such a pair may be the behaviour of a PC's time stamp counter. On the one hand, we have the speed of incrementing the counter and its value at a given time. The speed is the CPU frequency. We have full precision with that. It follows then that we have no precision on the counter's value at a given time if the uncertainty principle applies here.

My CPU's base frequency is 3.5GHz. It is impossible to get two readings within that frequency as that would require a higher frequency so a second reading cannot be determined with any certainty. It is then uncertain.

Taking the lower 32 bits of the counter, 'spinnng' at a faster rate than the upper 32 bis, will be a good way of getting a 32-bit seed for a PRNG.

Given an uncertain number, A say, if we add a constant, C say, then A + C is also uncertain. We could allow a rotation of the counter by a fixed amount, avoiding another reading. Concatenating the first reading with the second 'reading' will give a 64-bit seed for a PRNG.

To further 'muddy' the waters, we could apply a Fisher Yates/Knuth shuffle on the values got. Of course, the shuffle requires an uncertain number. We do not need a seed for that if we use a cryptographic generator like FB's generator FB_RND_REAL (5). We could then generate many seeds, and they would have no relationship to other seeds.

By using rdtsc are we entering Heisenberg's uncertainty principle? No. In the quantum world, the very act of looking at something changes what we are looking at. This is not the case in the macro world. In a room with no contact with the outside world after we enter, we may be told that there is a 75% chance that it is raining outside. It follows then that there is a 25% chance that it is not raining outside. Outside, then it is both raining and not raining. That is consistent with the quantum law of “If it is not prohibited, then it is mandatory.” When we do look outside, Schrödinger's wave equation collapses, and we will see rain 75% of the time. This is a variation of Schrödinger's cat. The analogy with the uncertainty principle breaks down when we start talking about the Planck's constant and the wave-particle duality.

Melissa O’Neill, author of the PCG random number generator, is an advocate of using the time stamp counter for seeding.

Notice that we have not used the term random in the above. Randomness implies uncertainty, but uncertainty does not imply randomness.

I would even go as far as to say that randomness may not actually exist. What we have is levels of uncertainty.

PractRand does not prove randomness. A 16TiB success simply shows that no level of certainty was established and we then deem the result as being a good quality 'random' number generator. Since a Pseudo Random Number Generator implies the existence of random numbers, then it follows a PRNG is a false statement; according to my belief. A PRNG is a number generator where future numbers have a degree of uncertainty. The uncertainty of modern generators is exceptionally high compared with older generators such as the Linear congruential generators [LCG] with PractRand treating them with extreme prejudice.

The seeding method above is used in the MsWsII generator.

Using a fixed seed is not a good way for repeating sequences unless we ensure that it has a good Hamming weight; that is, an equal number of set bits and unset bits. A poor Hamming weight may lead to an unacceptable level of certainty in the early stages of generation, requiring a so called 'warm up'. The Mersenne Twister needs the longest warm up of any generator, and yet most people start using it from the outset and don't request that many numbers; the worst scenario. Yes, it managers to satisfy PractRand, up to 256GiB of ulongs before it goes 'belly up'. Periods of certainty may be too short-lived for PracRand to spot them. That could mean a failure just after 128GiB of ulongs or 32GiB of floats. That is OK for many applications when even a LCG would do, but not serious scientific work. A better 'fixed seed' way is to use an uncertain seed and take a snapshot of the state vector. We cannot do that with the FB generators. Repeating a sequence with an uncertain seed is simply got by restoring the state vector snapshot. That is also used by MsWsII. Bernard Widynski does not mention using a warm-up in his March 22, 2022 paper; Middle-Square Weyl Sequence. Being non-linear, I don't believe that it needs one, and MsWsII does not use one. Having said that, seeds are still subject to a Hamming test. I am doing a 'Bernard Shaw' here who, on his deathbed bed, asked for a priest. A friend asked why, since Shaw was an atheist. “I know”, said Shaw, “I am just playing it safe.”

So, there we have it. A bloke who has knocked out more than his fair share of PRNG implementations believing in randomness ending up being, how can I put it, uncertain whether randomness actually exists?

[Provoni]

So, there we have it. A bloke who has knocked out more than his fair share of PRNG implementations believing in randomness ending up being, how can I put it, uncertain whether randomness actually exists?

Through the years I have followed your threads about rng's with interest and the topic of randomness intrigues me highly.

It is a deeply profound concept and something which I consider to be an anti-primitive since I cannot think or fathom any process that could produce true random numbers in the most absolute and highest meaning of the word 'randomness'.

Yet we do understand the concept and know how it should behave and invent algorithms that approximate its behaviour for various meaningful reasons. Yet we cannot truly have it. For me, this is typical of life, handle it with grace and you will do well.

Also, the amount of randomness / uncertainty we can produce artificially is limited by the amount of compute we have available. And I also think that randomness, compression and intelligence are linked somehow. Just to throw some stuff in. :p

[deltarho[1859]]

And I also think that randomness, compression and intelligence are linked somehow.

In Star Trek 'Space-Time continuum' is mentioned several times. Being set in the 23rd century, they should have known better or, perhaps, Gene Roddenberry should have known better. There is no such thing as 'Space-Time continuum'. Both space and time exist as packets or quanta as Planck called them.

You missed one out: Light. Here we are talking about photons. For compression whether space or mass we are talking about gravitons. For randomness, I am not talking about anything because I doubt that it exists.

The link is then quanta.

What do you mean by intelligence? Human intelligence? Regarding the uncertainty principle with biological or transitioned females we are talking about feminism. I am reminded of a comment made by Jack Nicholson in one of his movies when asked how he portrays women so well in his novels. “That's easy,” he said, “I just think of a man and remove the reasoning and accountability”.

Just kidding, ladies, I think.

[coderJeff]

When we do look outside, Schrödinger's wave equation collapses, and we will see rain 75% of the time. This is a variation of Schrödinger's cat.

Oh, pish posh! The cat, the box, the observer, the inside and outside, are all part of one system (Everett's interpretation), so there is no collapse of the wave function and the measurement is inherent to the whole shebang. So, my take on that then is that true randomness can not exist, but in my world it must exist because I can not measure the outcomes of all the other many worlds .. and I don't know which world I am in.

[deltarho[1859]]

.. and I don't know which world I am in.

That is easy enough. If it is raining outside when you go outside, then the world that you are currently in is the one where it is raining outside and the chance of being in that world is 75%.

We could be talking true randomness here, as the outcome is deterministic. With coin tossing and an unbiased coin, we don't know whether we will get a head or a tail on a single toss, but as the number of tosses tends to infinity, what we know for certain is the average will tend to to 50/50. Going outside an infinite number of times will see it raining 75% of the time. Going outside just once, and we will not know whether it will be raining or not, and we will not know which world we are in until we go outside.

With rdtsc we have 2^32 possible worlds. If read an infinite number of times, the average will be 2^31. It is deterministic.

[coderJeff]

For a guy that may be uncertain whether randomness actually exists, your response ... not what I expected. so I now learn that 'true random number generator' is a defined thing apparently ... which is not what I meant by 'true' (if that is what you thought). Anyway, my post intended to point out that consideration of randomness under a many worlds interpretation of quantum physics may yield different conclusions.

[deltarho[1859]]

True randomness exists in mathematics. Infinity exists in mathematics. In the natural world, I do not believe either exist. I allowed a coin to be tossed an infinite number of times, which of course is not possible.

It is often written that at the centre of a black hole space is curved to such an extent the gravitational 'pull' is infinite and gravitational time dilation sees time stop. That would be true if Space-Time was a continuum, but since they both exist as quanta, then it isn't true. As n tends to infinity, 1/n tends to zero, but the centre of a black hole does not vanish. What we have is what I call a 'natural' singularity and not a mathematical singularity. The initial condition of the Big Bang is also said to be a singularity. I reckon that was also a 'natural' singularity and not a mathematical singularity. It follows for me then that time existed before the Bang, although it was ticking 'slowly'. What has always had me scratching my head is what caused the 'Bang'.

Black body radiation had an issue with infinity until Planck came up with quanta.

So in mathematics it is convenient to allow randomness and infinity to exist. The term 'at the point of infinity' is used in mathematics, but it is absurd in any other discipline.

I think 'many worlds' allows infinity, which I have a problem with.

[SARG]

With rdtsc we have 2^32 possible worlds.

Why 2^32 ? as 2 32bit registers are used (EDX:EAX). On 64bit RDX:RAX with upper 32 bits cleared.

[deltarho[1859]]

Why 2^32 ? as 2 32bit registers are used (EDX:EAX).

From opening post:
“Taking the lower 32 bits of the counter, 'spinnng' at a faster rate than the upper 32 bis, will be a good way of getting a 32-bit seed for a PRNG.”

[SARG]

Ok so that's not really with rdtsc but with only its lower 32bits.
Maybe I'm too 'punctilious'

[deltarho[1859]]

Maybe I'm too 'punctilious'

That goes with the territory of being a master asm coder.

[deltarho[1859]]

It follows for me then that time existed before the Bang, although it was ticking 'slowly'.

Professor Brian Cox, here, is saying the same. We use a different language, but he is effectively saying that the Big Bang was a natural singularity and not a mathematical singularity. Prof Cox theorises that there was a time before the Big Bang in which the Universe existed. Before this time, he says, there was no matter at all but simply space-time and an ocean of energy, almost still but gently rippling.

This space had no structures, but soon, a process known as inflation caused an “unimaginably violent expansion” in which things began to buzz. So, no indication why it went 'Bang'.

The article was written three days before my post, but I have just seen it.

Sir Roger Penrose, a British mathematical physicist from the University of Oxford, is also questioning the mathematical singularity.

“…an ocean of energy” ? Converted into mass from, you've guessed it, E = mc².