Announcement

Collapse
No announcement yet.

Rnd2 disscussion

Collapse
X
 
  • Filter
  • Time
  • Show
Clear All
new posts

  • #21
    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.

    Comment


    • #22
      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.
      Last edited by David Roberts; 3 Oct 2008, 07:03 AM.

      Comment


      • #23
        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???)
        Engineer's Motto: If it aint broke take it apart and fix it

        "If at 1st you don't succeed... call it version 1.0"

        "Half of Programming is coding"....."The other 90% is DEBUGGING"

        "Document my code????" .... "WHYYY??? do you think they call it CODE? "

        Comment


        • #24
          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:

          Comment


          • #25
            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.

            Comment


            • #26
              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.
              Attached Files

              Comment


              • #27
                [quote]
                Originally posted by John Gleason View Post
                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
                Attached Files

                Comment


                • #28
                  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.

                  Comment


                  • #29
                    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.

                    Engineer's Motto: If it aint broke take it apart and fix it

                    "If at 1st you don't succeed... call it version 1.0"

                    "Half of Programming is coding"....."The other 90% is DEBUGGING"

                    "Document my code????" .... "WHYYY??? do you think they call it CODE? "

                    Comment


                    • #30
                      >>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.

                      Comment


                      • #31
                        > 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.

                        Comment


                        • #32
                          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.
                          Last edited by David Roberts; 6 Oct 2008, 12:38 PM.

                          Comment


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

                            -- The universe tends toward maximum irony. Don't push it.

                            File Extension Seeker - Metasearch engine for file extensions / file types
                            Online TrID file identifier | TrIDLib - Identify thousands of file formats

                            Comment


                            • #34
                              >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?
                              Michael Mattias
                              Tal Systems (retired)
                              Port Washington WI USA
                              [email protected]
                              http://www.talsystems.com

                              Comment


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

                                Comment


                                • #36
                                  >>A small break: Experts Exchange - Rnd() values are changing every time in ASP.NET. Those experts are cwazy wascals.
                                  Last edited by John Gleason; 6 Oct 2008, 04:27 PM.

                                  Comment


                                  • #37
                                    Thanks John. Done.

                                    Comment


                                    • #38
                                      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?



                                      Code:
                                      '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

                                      Comment


                                      • #39
                                        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.

                                        Comment


                                        • #40
                                          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.

                                          Code:
                                          [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.

                                          Comment

                                          Working...
                                          X