Rnd2 disscussion

[Gary Ramey]

Regarding the use of RDTSC, the results might not be as predictable (or unpredictable) as things first appear. Is this instruction available and repeatable on all processors? Take a look at the wiki article http://en.wikipedia.org/wiki/RDTSC.

I need to look over the code section again, but it seems that we're still not gathering enough entropy information by simply taking a look at timing ratios.

[David Roberts]

I've got CPU-Z running at the moment and I'm looking at Core #0's multiplier changing between 6 and 10. It seems to me that over 10 seconds, say, it would be impossible to predict what the TSC would advance to. GetTickCount, on the other hand, would advance by 10000. If the TSC frequency was brought into account with the counter then we would also see an advance of 10000ms.

On the other hand if the duration considered was not 10 seconds but a very small amount then the future value of the TSC would be easier to predict.

The TSC is then a chaotic variable and not a random variable. With a random variable, being deterministic, the longer the duration considered the greater the certainty of the determinant. For example, the average number of heads on tossing an unbiased coin will tighten ever more so around 0.5 the longer the test. On an individual flip the best odds we get is 50/50.

We can see the effect of this chaos in the above code where 'QPC Age' is less than 'GetTickCount Age'. qFreq assumes a multiplier of 10, on my machine, for all of the increments that make qQPC. If we summed all of the increments/'associated frequency' then QPC's age would be the same as GetTickCount.

Since we do not know what the multiplier is at any given moment and for how long it is in force then QPC/TSC is not the way to go for timing long periods. GetTickCount is the way to go. For short durations and a high resolution then QPC/TSC is the way to go. I don't know what would qualify for 'short' and 'long'.

It doesn't follow either that when an app is running then the multiplier will be always 10. When I was watching the multiplier changing Diskeeper Pro was defragging in the background along with other processes kicking in and out.

> but it seems that we're still not gathering enough entropy information by simply taking a look at timing ratios

I agree with that Gary, if we want to use the term TrueRandom. The MS CPRNG uses everything except the kitchen sink. Welcome to the board, by the way.

Added: Just a thought but I have been coming round to the idea that whether a pseudo or crypto engine is used then there is a good argument for using a crypto starting handle in either event.

[Cliff Nichols]

Maybe a lil off or just overlooked, but to be truly random, why not just seed the random with the date and time (like when are we going to have the same date and time again?)

That way Random is always based from a completely different value (unless of course you can recompile in under a second???)

[John Gleason]

Gary, interesting article there. I think that it validates the idea of using the TSC unpredictability as a random source. One gist of the article is that the TSC can't be relied upon for accuracy--just what the statistician ordered.

Dave (and Gary & Cliff if you'd like to try it too): The final say as to whether we're getting any trueRandom between TSC reads within the function is to test it and see what happens. Between successive calls to randomise/trueRandom with a call to any significant other function interleaved, there is over one bit always. In the worst case scenario I show above, I still get 4/57ths of a bit per dword on the box I use. What are you seeing when you run it? ie. How many repeating dwords do you get on average before an oddball appears?

Cliff & Dave: The date or crypto handle are fine on startup, but I'm hoping for the ability to use randomise/trueRandom at will for effectively real-time randomness. Even now as both functions (rnd2 and revisited) currently exist, they seem to do this already. Dave has asked basically, so what's the advantage over a well seeded pseudo rng? Well, just the idea that we can say the numbers "are really random," instead of "aren't really random, but are the result of applying a pseudo-random transformation algorithm to a starting ("seed") value." :hmmm:

[David Roberts]

If we fire 100 photons at a sheet of glass some will come back at us. Depending upon the thickness of the glass it can be determined quite accurately how many, on average, will come back.

Given the momentum of an electron the location of an electron depends upon a probability density function, hence the term electron cloud, and vice versa. We cannot determine both - Heisenberg's Uncertainty Principle.

So, although we can calculate how many photons will be reflected we'll never be able to determine which.

That is "really random".

Given two rng which pass all Die Hard routines and not just a chi-squared test and one takes one ms and the other takes two ms which do we choose? Well, I'll take the one ms rng. However, if it were pointed out to me that the two ms rng produces numbers which "are really random", but not random in the photon/electron collision scenario sense, and it is " just the idea that we can say the numbers "are really random" " is not going to persuade me to give up the one ms rng. Introduce some more routines to the Die Hard suite such that the two ms rng still passes but the one ms falters then I'll be persuaded.

"for the ability to use randomise/trueRandom at will for effectively real-time randomnes" reading the TSC is not going to give anything like the uncertainty of a crypto engine which uses a list including the TSC and many other events as long as our arms.

[John Gleason]

The photon idea is a great analogy.
Here is how it can be applied to the above .exe code in post 18:
Each loop of the 2,000,000 in the for-next loop shoots one time value (photon).
Those that pass thru the cpu (glass) register in the optimal time.
Those that hit something register some time later--"something" likely being quantum effects of nanoscale architecture.
How often this happens depends on the particular CPU (type of glass), and the average rate will be consistent over time.
On which loop a specific hit will occur is nearly random (I say nearly because it has a tiny skew, but I'd bet photons off glass would have a skew too).

So, we can say for a given cpu, a certain number of hits will occur in the 2,000,000 loops--my machine averages ~11700 +/-200--but there is no way to predict which specific loops will hit.

Here's a little animated gif of the hits, showing 6 pages of 1280 timings / page.

[Gary Ramey]

[quote]

Here is how it can be applied to the above .exe code in post 18:

John,

I compiled, then ran the EXE from post #18 with all programs shut down and NAV2009 inactived. The results appear to be almost completely predictable. Perhaps I'm mistaken. Look at the attached file to see if this is what you were expecting. This laptop has a Centrino Duo 1.6GHz processor and Vista Home SP1. I compiled with PBWin9.

Gary

[John Gleason]

Thanks for running that Gary. I had an additional thought: if my suggestion re. quantum effects related to chip nano-structure has merit, modern chips should have progressively more randomness than larger older chips; the newer chips being closer to the theoretical "quantum wall" so to speak. I've looked at your data and it is hugely different than mine, but I'll try to figure out how much (if any ) randomness is in there.

[Cliff Nichols]

WOW did this conversation take a turn at Albuquerque
(Buggs Bunny Even)

My own personal thought of truly "Random" is something in nature, but being humans we can only theorize as to the extent of the random-ness

All ideas and theories around them will ultimately involve some sort of non random sequence (It just depends on how deep vs how deep are you looking?)

As far as "Quantum" ideas, the extent of my ability to think is "Quantum Leap" and even that had a pattern if you could picture it.

[John Gleason]

>>take a turn at Albuquerque
Yes, I'm just trying to come up with some justification for this data I'm seeing. Kinda brainstorming out loud whereas it's prolly best just to be thought out first.

Gary, I did stat tests of your file and it does have significantly more entropy than mine. It's much different tho than my file, so I'm not yet sure if I'm going to be able to come up with the irrefutable trueRandom cross CPU algo I had envisioned.

Dave, I can't try the functions you mentioned because win98 doesn't have them like xp does. But I do want to show the max possible that can be achieved via the TSC somehow.

[David Roberts]

> I can't try the functions you mentioned

Which functions, John?

> But I do want to show the max possible that can be achieved via the TSC somehow.

I know you do.

I cannot go along with you because I believe a TSC only approach is bound to fall short of true randomness.

[David Roberts]

I have posted an addendum to Rnd2 revisited.

It is a routine to complement John Gleason's Randomise/TrueRandom, called CryptoRandom and, not surprisingly, uses a cryptographic generator as opposed to a pseudo generator.

It does, however, come wih a caveat. It uses the function John cannot try, namely RtlGenRandom, which requires XP and/or Vista. Further, since an object is used, the posted routine requires CC5 and/or PB9.

If we go up a level to the Crypto API then we can use CryptGenRandom, available since Windows 95, as done in 'On cryptograhic random bytes, Part II' here but it is a bit of a dog's dinner if we only want random numbers.

CryptoRandom provides the multiplier index along with initial mwcRandom and mwcCarry figures.

It is about six times slower than John's Randomise/TrueRandom code. The entropy is got from an extensive list as mentioned in Michael Howard's Web Log (January 14, 2005 10:21 PM) which goes some way to explain why it takes as long as it does.

However, to put this in perspective this translates to about 120,000 CryptoRandoms per second on my machine.

If CryptoRandom/Rnd2 is used as we would with Randomize/RND then since a cryptograhic approach cannot be bettered it would be difficult to argue against the crypto approach for intializing a sequence of mwc random numbers and renders the argument of whether the TSC is sufficiently unpredictable and any other considerations as academic.

This argument is equally valid for the die example put forward by John. However, if speed is an issue then Randomise/TrueRandom should be considered. In the unlikely event that there is an issue with speed here as well then we should consider no re-seeding at all and leave the mwc to get on with it.

It should be noted that in so far as Chi-squared testing is concerned no evidence was found to suggest that any one of these three methods was better than the other two.

I favour CryptoRandom for initialization and no re-seeding in die type examples. If I attempt to justify that then I should be bound to a contradiction so I'll keep my mouth shut.

Perhaps John could suggest other routines to test the three approaches?

Update:

Bearing in mind that Rnd2, on my machine, knocks out about 28,000,000 per second the figures above looked suspect. I was counting the TIX of the routine and working from that. It was easier to edit the file which generated the chi-squared data. I then got about 1,200,000 CryptRandom's per second. Replacing CryptRandom with Randomise, CryptRandom was 2.4 times slower and not 6. With John's asm expertise that 2.4 could be reduced to, well, who knows.

[Marco Pontello]

A small break: Experts Exchange - Rnd() values are changing every time in ASP.NET

[Michael Mattias]

>A small break

Um, correct me if I'm wrong here, but isn't the poster essentially complaining that two plus two always equals four?

[John Gleason]

Dave, I think there's a case # overlap there, how about we make it CASE 6. CASE -1 reseeds like RND(-1) does.

[John Gleason]

>>A small break: Experts Exchange - Rnd() values are changing every time in ASP.NET. Those experts are cwazy wascals.

[David Roberts]

Thanks John. Done.

[Gary Ramey]

RND2(-integer) question

David and John,

Both of the "random" re-seed methods appear to produce great results. The PB9 test code below displays results from both methods.

I prefer the crypto-based approach. Regarding John's approach, I do not see the results as primarily attributable to slight variations of the timing counters. The RND2(1) algorithm itself does a great job of mixing things up.

I do have an observation about the use of fixed seed values (i.e., negative integers) to set the starting point for a sequence. Simply plotting the first value of a sequence and then progressing to another specific seed produces clearly non-random results. (See third graph from test code.) Are the linear patterns expected? Do we have a typo in one of the Sophie Germain primes?

'Graphical tests of variants of RND2 algorithm
#COMPILE EXE
#DIM ALL
#INCLUDE "win32api.inc"
'Use "trueRandom.inc" from PB Source Code forum post 38663,
'  with addition of CryptoRandom RND2(6) case.
#INCLUDE "trueRandom.inc" 

'~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
FUNCTION PBMAIN
    LET GetCrypto = CLASS "CCryptoRand"   'Connect to object
    LOCAL ii,jj AS LONG
    LOCAL hgWin AS DWORD
    LOCAL tDuration AS LONG
    '
    tDuration = 5000000
    '
    GRAPHIC WINDOW "Matrix", 0, 0, 800, 600 TO hgWin
    GRAPHIC ATTACH hgWin, 0 , REDRAW 
    GRAPHIC SCALE PIXELS 
    GRAPHIC SCALE (0,1.01) - ((tDuration), -.01)
    GRAPHIC COLOR %BLACK, %WHITE
    GRAPHIC CLEAR
    GRAPHIC LINE (0,0)-(tDuration,0), %GREEN
    GRAPHIC LINE (0,1)-(tDuration,1), %YELLOW
    GRAPHIC REDRAW
    '
    ' Randomise procedure (from post 38663) has good results
    FOR ii = 0 TO tDuration STEP 33 'no influence from step
        Randomise  'Re-seed using self-seed option
        GRAPHIC SET PIXEL (ii, RND2() )
    NEXT ii
    GRAPHIC REDRAW
    ? "Results from John's Randomise look okay." +$CR+$LF+ _
      "Press a key when ready"
    '
    GRAPHIC COLOR %BLUE, %WHITE    
    GRAPHIC CLEAR
    GRAPHIC LINE (0,0)-(tDuration,0), %GREEN
    GRAPHIC LINE (0,1)-(tDuration,1), %YELLOW
    GRAPHIC REDRAW
    ' David's CryptoRandom
    FOR ii = 0 TO tDuration STEP 33 'no influence from step
        CryptoRandom
        GRAPHIC SET PIXEL (ii, RND2() )
    NEXT ii
    GRAPHIC REDRAW
    ?  "Results from David's CryptoRandom look okay." +$CR+$LF+ _
       "Press a key when ready"
    '
    ' But WHY are we getting these line patterns when graphing 
    '  the 1st returned values from a series of "neg seed" values.
    GRAPHIC COLOR RGB(200,100,100), %WHITE
    GRAPHIC CLEAR
    GRAPHIC LINE (0,0)-(tDuration,0), %GREEN
    GRAPHIC LINE (0,1)-(tDuration,1), %YELLOW
    GRAPHIC REDRAW
    FOR ii = 1 TO tDuration STEP 33 'Severity of lines varies w/step
        RND2(-ii) 'Re-seed using negative integer
        GRAPHIC SET PIXEL (ii, RND2() )
    NEXT ii
    GRAPHIC REDRAW
    ? "This is case with re-seeds using RND2(-integer)." +$CR+$LF+ _
      "Plotting each first RND2() result after re-seed." +$CR+$LF+ _
      "Just testing. This is not our normal usage method." +$CR+$LF+ _ 
      "What is causing the line patterns?" +$CR+$LF+ _
      "Press a key when ready"
    '
    '    
    GetCrypto = NOTHING  ' Release this object
    '
END FUNCTION

[John Gleason]

Nice progam Gary, and you've only got 3 posts. I too wondered what would happen if I generated all 1st values, and so tried it, but it failed several of the Diehard tests (tho I recall it passed the Chi-square test). Like you say, this wouldn't be a normal use--the intention is to give an "ok" distribution of 2gig starting points. Once a starting point is set the generator does its 2^6x period of randoms, and each of those show no patterns. Btw no 2 are duplicate starting points, I checked that also.

The SG primes are all ok, and it'd have been cool if the rnd2(-val) starting points were also perfectly distributed, but it would require something like the code for rnd2(1) to do it.

[David Roberts]

Bear in mind that Rnd2(-n) is a function and not a command - it ends with 'GoTo noParams'.

We could have used

Graphic Set Pixel ( ii, RND2(-ii) )

That prompted me to advance a few before moving on.

[COLOR="Red"]For i = 1 To 10
  GoSub sRandomLong
Next[/COLOR]
GoSub gsStoreSeq
oneTime = 1
GoTo noParams

The lines persist.

The only constant is mwcCarry. Change it and watch all the pixels move east or west.