Random Number Generator - No Extra Cog

ryfitzger227

Hey guys!

I need help with something. I'm in need of some type of random generator that gives true random values. I know there's some stuff in the Object Exchange, but not any that doesn't require an extra cog - something I don't have in this project. I need something that just gets a random value between 1 or 2, but I can also deal with 0-9 (in that case odd would equal 1 and even would equal 2 - still a 50% chance like 1-2). What I was thinking was to take the last character in cnt, but everything I tried wouldn't work. Any ideas on how I could do that, or just get a random number without an extra cog?

Thanks.
- Ryan

Heater.

I have just the thing for you:
http://forums.parallax.com/showthread.php/136975-JKISS32-High-quality-PRNG-with-RealRandom-seed-save-a-COG.
Basically the idea is to use a simple but high quality pseudo random number generator, which does not need a COG, and seed it from the RealRandom object, which does use a COG. Once the seeding is done the RealRandom COG is shut down and can be reused.

Depends what you mean by "True Random". You could of course do this with the Spin built in random operator but it is not a very good generator. The pseudo random number generator above will provide you with seeming randomness that does not repeat itself for thousands of years and gives a different sequence every time you reset. It does very well when tested with all the statistical tests of randomness I could find.

If you only need two values out, heads or tails, just use the first bit of each number generated. Or shift 32 bits out of each one.

lonesock

So, as a fun exercise, I tried just straight porting the RealRandom code to Spin...it _seems_ to work:

EDIT: fixed a bug on Feb 13

PUB RealRandomSpin( bits ) : rn | rmask, rbit_old, rbit_new, got_subbits

  ' set up the counter
  ctra := constant( %00001_111 << 23 )                  'set ctra to internal pll mode, select x16 tap    
  frqa := constant( $020 << 23 )                        'set frqa to system clock frequency / 16 
  vcfg := constant( $040 << 23 )                        'set vcfg to discrete output, but without pins
  vscl := 70                                            'set vscl to 70 pixel clocks per waitvid

  repeat bits

    ' flag that we don't have any sub-bits yet
    got_subbits := 0
    
    ' get one random bit
    repeat

      ' get at least 2 sub-bits, and make sure they don't match!   
      repeat
        rbit_old := rbit_new
        waitvid( 0, 0 )
        rmask := phsa & %10111
        rbit_new := rmask
        ' basically checking if the number of 1's in rmask is odd or even
        repeat 
          rbit_new ^= (rmask >>= 1)        
        while rmask
        rbit_new &= 1
        ' work that odd or even back into phsa (rcr), and then mix in the counter
        phsa := (phsa & -2 + rbit_new) -> 1 + cnt
      until got_subbits++
      
    until rbit_old ^ rbit_new
    
    ' save this latest bit
    rn += rn + rbit_new

Now, this has in NO WAY been tested, other than watching a histogram for a while. I leave it to the PRNG gurus to figure out how to test the randomness of this code. Also note that this will step on CTRA for the calling cog.

Jonathan

Ariba

If you initialize the random number with the cnt value at begin and then use the Spin random operator (?) you get quite good randomness:

pub Main | random,rnd12
  random := cnt                  'init with random seed

  repeat
    random?                      'generate 32bit random
    rnd12 := (random & 1) + 1    'use bit0 for random 1 or 2

Andy

JonnyMac

I use RealRandom to seed Heater's PRNG object, then unload RealRandom -- cog is used for just a moment and I get excellent results.

Heater.

It all depends what you mean by "quite good".

The Spin pseudo random number generator has a very short cycle time and fails all statistical tests for randomness.

According to the manual :

Upon power-up/reset, the System Counter starts with an arbitrary value and counts upwards
from there, incrementing with every System Clock cycle.

Not sure what that means. Sounds like it is not set to any fixed value like zero on reset which might be OK but presumably from power up it may always find itself in the same starting position (might vary from chip to chip). If that is the case using it as a seed is hardly random at all.

This kind of thing used to be the flaw in on-line poker sites back in the day making them easily abusable.

Things like JKISS32 and a real random seed are order of magnitude better. But even they are not recommended for use in cryptographic applications where security is a prime concern. However cryptographically safe random number generators are a lot more complex and slower.

Looks like lonesock has just made my JKISS32 scheme obsolete. Except there are times when you do actually want a pseudo random number generator. When comparing simulation models that driven by random input for example. And of course there is that stepping on the Props hardware to consider.

P.S. Of course even statistical tests of randomness can't produce absolute yes/no answers to the question "Is this random".

lonesock

Heater. wrote: »

...
Looks like lonesock has just made my JKISS32 scheme obsolete. Except there are times when you do actually want a pseudo random number generator. When comparing simulation models that driven by random input for example. And of course there is that stepping on the Props hardware to consider.
...

Also, the RealRandomSpin routine is both slow, and the timing is indeterminate. Because it requires that back to back sub-bit samples be opposite, it may take a while to grab another bit. Note that the PASM version always grabbed two fresh sub-bits. For a tiny speed boost I just used a loop comparing current to last (after an initial seed), and take current once it is different from last (if that makes any sense). It's possible that is bad behavior, for example, if the underlying mechanism returns a string of 1s, then a string of 0s, then 1s again etc., the output number would always look like %010101. And once again I'm out of my depth. [8^)

Of course, if the Spin version of RealRandom does work, or can be made to work, it might be a nice alternative to using a cog every once in a while in your JKISS32 object.

Jonathan

lonesock

I made a little test harness, with a lame ASCII histogram display over serial, and found a bug. There was a RCR in the original code that was accidentally converted to a RCL. Fixing that, the output looks pretty nice. Attached it the test harness, and I will edit my above post to update the code snippet.

Jonathan

Heater.

lonesock.

Cool.

Sounds like I have to run your random output through the Die Hard and other tests of randomness.

I wonder which is quicker, JKISS32 or just going straight to your RealRandom.

lonesock

JKISS32 will be significantly faster.

EDIT: RealRandomSpin takes about 13 [ms] per 32-bit long! So, at 77 random longs per second, yeah, definitely use it only as a seed for a decent PRNG! [8^)

Jonathan

lonesock

Well, going against the spirit of this thread, but trying for a fast really random generator, I mixed Chip's RealRandom PASM code, and translated Heater's JKISS32 code into PASM. Now what it does is run a cycle of JKISS32 and update the hub long with the value, then get 2 sub-bits. All of that happens in a loop, as tight as I can get it. Then, every time 32 valid random bits are extracted from the PLL jitter, that newly constructed really random 32-bit long replaces one of the 5 state variables of JKISS32. So, X is updated to a new really random value, then Y, Z, W, C, then back to X, etc.

The worst total period I have observed < 320 clocks, so you can have about 250k random numbers a second. A new state variable is swapped out every 60 periods or so, so all 5 will have been replaced about 1000 times a second or so (at 80MHz). Meanwhile the JKISS32 code is mixing it's heart out for every period.

All in all, barring unfortunate bugs of mine, it should be a nice way to get lots of really random numbers quickly. It really needs more testing though.

EDIT: I removed the code...the new version is a few posts down.

Jonathan

lonesock

So, I found 2 bugs in my JKISS32 code:
1 - I used a SAR when I should have used a SHR (Heater's code had it done correctly, as the original C code used unsigned integers)
2 - The carry variable C should not be 0/1, but rather 0/-1 (Heater, I think this is an issue in your Spin code as well? Not sure how much it matters, of course.)

I will update the object in my previous post.

EDIT: curses, I was wrong on the comparison going to -1...hanging head in shame and updating code once again!

Jonathan

Heater.

Jonathan.

No need for shame. I hit those exact same signedness problems.

Here is a funny story:

Professor George Marsaglia, who invented the random number generating technique that JKISS32 is based on, published a CD of random numbers back in 1995.

Problem is that the published CD fails the "Die Hard" statistical tests of randomness.

What happened?

Turns out that when he copied the binary file under MSDOS it was copied as a text file instead of a binary file. So every OxOD got replaced with a 0x0A0x0D. Or whatever it MSDOS does when it sees an end of line in a text file.

As a result there are statistically to many 0x0d0x0a or 0x0a0x0d sequences in the file on that CD ROM.

Another great man screwed over by MicroSoft.

lonesock

Thanks, Heater.

I did find one more bug (this one _was_ cause for shame...copy-n-paste error [8^), sped up the code, and used 32 real random bits when updating the X/Y/Z/W state variables, but only 1 real random bit when updating the C state variable. I also added in the RealRandomSpin function, just to have all this in one place. I'm posting it here, but I don't think I will do much more to this code unless someone needs something else?

Jonathan