Seeding PRNGs with the Time Stamp Counter

General discussion for topics related to the FreeBASIC project or its community.
Post Reply
deltarho[1859]
Posts: 4316
Joined: Jan 02, 2017 0:34
Location: UK
Contact:

Seeding PRNGs with the Time Stamp Counter

Post by 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
Posts: 514
Joined: Jan 05, 2014 12:33
Location: Belgium

Re: Seeding PRNGs with the Time Stamp Counter

Post by Provoni »

deltarho[1859] wrote: Apr 15, 2024 21:45 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 wrote: Mar 10, 2023 6:57 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]
Posts: 4316
Joined: Jan 02, 2017 0:34
Location: UK
Contact:

Re: Seeding PRNGs with the Time Stamp Counter

Post by deltarho[1859] »

Provoni wrote: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
Site Admin
Posts: 4354
Joined: Nov 04, 2005 14:23
Location: Ontario, Canada
Contact:

Re: Seeding PRNGs with the Time Stamp Counter

Post by coderJeff »

deltarho[1859] wrote: Apr 15, 2024 21:45 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. :P
deltarho[1859]
Posts: 4316
Joined: Jan 02, 2017 0:34
Location: UK
Contact:

Re: Seeding PRNGs with the Time Stamp Counter

Post by deltarho[1859] »

coderJeff wrote:.. and I don't know which world I am in. :P
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
Site Admin
Posts: 4354
Joined: Nov 04, 2005 14:23
Location: Ontario, Canada
Contact:

Re: Seeding PRNGs with the Time Stamp Counter

Post by 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]
Posts: 4316
Joined: Jan 02, 2017 0:34
Location: UK
Contact:

Re: Seeding PRNGs with the Time Stamp Counter

Post by 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
Posts: 1787
Joined: May 27, 2005 7:15
Location: FRANCE

Re: Seeding PRNGs with the Time Stamp Counter

Post by SARG »

deltarho[1859] wrote: 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]
Posts: 4316
Joined: Jan 02, 2017 0:34
Location: UK
Contact:

Re: Seeding PRNGs with the Time Stamp Counter

Post by deltarho[1859] »

SARG wrote: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
Posts: 1787
Joined: May 27, 2005 7:15
Location: FRANCE

Re: Seeding PRNGs with the Time Stamp Counter

Post by SARG »

Ok so that's not really with rdtsc but with only its lower 32bits.
Maybe I'm too 'punctilious' :-)
deltarho[1859]
Posts: 4316
Joined: Jan 02, 2017 0:34
Location: UK
Contact:

Re: Seeding PRNGs with the Time Stamp Counter

Post by deltarho[1859] »

SARG wrote:Maybe I'm too 'punctilious' :-)
That goes with the territory of being a master asm coder. :wink:
deltarho[1859]
Posts: 4316
Joined: Jan 02, 2017 0:34
Location: UK
Contact:

Re: Seeding PRNGs with the Time Stamp Counter

Post by deltarho[1859] »

Yours truly wrote: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².

:)
deltarho[1859]
Posts: 4316
Joined: Jan 02, 2017 0:34
Location: UK
Contact:

Re: Seeding PRNGs with the Time Stamp Counter

Post by deltarho[1859] »

Yours truly wrote: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.

Not a good idea. The distribution is poor. I am now using two 32-bit seeds combined into a 64-bit seed.
To further 'muddy' the waters, we could apply a Fisher Yates/Knuth shuffle on the values got.

Another bad idea. It isn't really necessary unless obfuscation is required, and I doubt many will need that.

Here are the seeding functions:

Code: Select all

Extern "c"
   Declare Function __builtin_popcount (Byval x As Ulong) As Long
   Declare Function __builtin_popcountll (Byval x As Ulongint) As Long
End Extern
 
Function HammingSeed32() As Ulong
Dim As Ulong Seed, CopySeed, numBits
While numBits <> 16
  Asm
    rdtsc    ' Get a fast changing number from the processor
    bswap eax
    mov Dword Ptr [Seed], eax
  End Asm
  CopySeed = Seed : numBits = 0
  While CopySeed <> 0 ' by adeyblue
    CopySeed = CopySeed And CopySeed - 1
    numBits = numBits + 1
  Wend
Wend
Return Seed
End Function
 
Function HammingSeed64() As Ulongint
Dim As Ulongint res
Cast(Ulong Ptr,@res)[0] = HammingSeed32
Cast(Ulong Ptr,@res)[1] = HammingSeed32
Return res
End Function

HammingSeed32 uses adeyblue's asm popcnt emulator, as some of you have old machines which do not support asm popcnt. For reasons surrounding AI asm popcnt will be a system requirement in the next Windows 11 update. For those who have managed to get Windows 11 on 15-year-old chips to work, it will now be broken. There is no workaround. dodicat has a faster emulator. I prefer adeyblue's emulator because it is the most elegant that I have seen and still fast.

Microsoft could have used an emulator. Are they using it in AI for speed reasons only? How many times will they go past asm popcnt? Hmm? Is there an ulterior motive here from our friendly OS provider?

Here is HammingSeed32 using asm popcnt.

Code: Select all

Function HammingSeed32() As Ulong
Dim As Ulong Seed, numBits
  While numBits <> 16
    Asm
      rdtsc
      bswap eax  ' Fast moving to upper bits
      mov Dword Ptr [Seed], eax
      popcnt ebx, eax
      mov Dword Ptr [numBits], ebx
    End Asm
  Wend
  Return Seed
End Function

That should work for most of you.

Here are some tests:

With '0 To 2^31-1' how many have a 32-bit Hamming weight of 16? The answer is 14%. That is higher than I thought it would be.so getting an optimal Hamming weight should be fast. How fast?

Using gcc -O2: Ten million HammingSeed32's were executed, and the longest time was noted. Twenty tests were carried out. The longest time was 214 micro-seconds using adeyblue's emulator. Using asm popcnt the longest time was 138 micro-seconds.

With HammingSeed64 I got: 258 micro-seconds for adeyblue's emulator and 148 microseconds for asm popcnt.

Either way, seeding via HammingSeed is blindingly fast.

Sebastian Vigna's xoshiro256** needs four 64-bit unsigned integers as seeds. We can supply top quality seeds in, probably, less than two milliseconds.

How about distribution of rdtsc. One billion reads were made and totalled. The average was compared to the average of '0 To 2^32-1' and I got 1.00001254. No problems there.

Warming up:

Sebastiano Vigna some years ago showed how seeds with poor Hamming weights generated early numbers with low levels of uncertainty. Effectively, we land in the tails of a normal distribution. By 'burning' numbers or warming up, we drift toward the central part of the normal distribution, where the 'better' seeds are. Two questions arise: Do all generators require a warm-up; how long should a warm-up be?

It seems that not all generators require much of a warm-up. In some cases, ten samples may be enough. Some need hundreds of samples to be burned and some thousands.

We can dispense with a warm-up by ensuring that seeds come from the central part of the normal distribution from the outset. This is what HammingSeed32 and HammingSeed64 do. Vigna referred to warming up as 'Escaping zeroland'. I call my HammingSeed method 'Jumping from zeroland.

It does not do any harm by using an optimal Hamming weight for a generator which does not require a warm up. If it does then we don't need to know how long a warm up should be by using an optimal Hamming weight from the outset. The two questions asked above are now academic.

Most of FB's generators require a warm-up, but who does one?

I have mentioned a few times that we should not use Randomize [Timer]. Since the fractional part of a double seed is clipped, Timer will give a limited number of entry points to the generator's sequence, especially if Randomize [Timer] is used on Windows shortly after a system Restart.

A much better way is to use 'Randomize HammingSeed32'. No warm up needed and 4 Gigs worth of sequence entry points — much more than with Randomize [Timer]. Randomize cannot handle a seed greater than 2^32-1 so DO NOT use Randomize HammingSeed64 otherwise you may get the initial Rnd repeated for different values of HammingSeed64. I am not sure why, but HammingSeed32 is safe.

This is not the case with Mersenne Twister which uses the given seed for a 'basic' generator to populate the Twister's state vector. The 'basic' generator will benefit from 'Randomize HammingSeed32' and the Twister's state vector may be better quality. My RndMT populates the state vector differently. I won't be going back to that since modern generators in the past ten years or so are much better than Mersenne Twister.

To repeat an intial sequence we simply use:
Seed = HammingSeed32
Randomize Seed
and repeat 'Randomize Seed' as and when required.

This what it is all about:

Code: Select all

Dim As Ulong x
For i As Ulong = 1 to 6
  x = HammingSeed32
  Print x,  __builtin_popcount(x)
Next
?
Dim As Ulongint y
For i As Ulong = 1 to 6
  y = HammingSeed64
  ? y, __builtin_popcountll(y)
Next

Code: Select all

1477266877     16
80186813       16
246458813      16
87868861       16
2714951869     16
306249149      16
 
4300978043854070974          32
14887282704484286654         32
11557745990473899198         32
5431473909731457214          32
9939607922729063614          32
17078433456667543486         32
To summarize if you need 32-bit seeds then use HammingSeed32. If you require 64-bit seeds, then use HammingSeed64. You need not be concerned with warming up.

If you are using a FB generator, then use 'Randomize HammingSeed32'.

:)
srvaldez
Posts: 3394
Joined: Sep 25, 2005 21:54

Re: Seeding PRNGs with the Time Stamp Counter

Post by srvaldez »

👍
Post Reply