Seeding the Random Number Generator

Topics related to the API, programming discussions & questions, coding tips, bugs, etc. should go here.
User avatar
PitfallJones
Posts: 39
Joined: Mon Aug 16, 2010 12:01 am

Seeding the Random Number Generator

Post by PitfallJones »

Hi,

Does anyone know a good way of seeding the random number generator so I can get a truly random sequence of numbers.

e.g. sometime like srand( HARDWARE_COUNTER );

HARDWARE_COUNTER = ??

Amazing the emulator seems to agree with a real Uzebox and is always the same!

Thanks

- PJ
User avatar
D3thAdd3r
Posts: 3221
Joined: Wed Apr 29, 2009 10:00 am
Location: Minneapolis, United States

Re: Seeding the Random Number Generator

Post by D3thAdd3r »

I highly recommend rolling your own random number generator using a Linear Feedback Shift Register. Where by rolling your own, I mean copying one from wikipedia.

Code: Select all

    uint16_t lfsr = 0xACE1u;  /* Any nonzero start state will work. */
 
    //...
	uint16_t prng(){//pseudo random number generator
        /* taps: 16 14 13 11; feedback polynomial: x^16 + x^14 + x^13 + x^11 + 1 */
        uint16_t bit  = ((lfsr >> 0) ^ (lfsr >> 2) ^ (lfsr >> 3) ^ (lfsr >> 5) ) & 1;
        lfsr =  (lfsr >> 1) | (bit << 15);
		return lfsr;
	}

//.......good way to seed so the stream of numbers is always different each time you play AKA random
	void TitleScreen(){

	//draw stuff..
	while(true){
		for(uint8_t i=0;i<60;i++){
			ReadButtons();//make the kernel recheck the gamepad more than 60hz
			if(ReadJoypad(0) & BTN_START)
				break;		
			prng();//keep updating the lfsr so when its game time we will be at a random position in the stream
		}

		WaitVsync();
	}
	//....
This has given me good results with good performance. To answer the question you actually asked, there is nothing that is not deterministic inside the '644 so you must use something from the outside world to get something that is actually random. Conveniently people take a fairly random amount of time to push start at the title screen or to do most any kind of input so that is a classic way to seed.
User avatar
uze6666
Site Admin
Posts: 4801
Joined: Tue Aug 12, 2008 9:13 pm
Location: Montreal, Canada
Contact:

Re: Seeding the Random Number Generator

Post by uze6666 »

I use the same technique to seed the random number generator. It's very unlikely you'll press start at exactly the same frame.
User avatar
PitfallJones
Posts: 39
Joined: Mon Aug 16, 2010 12:01 am

Re: Seeding the Random Number Generator

Post by PitfallJones »

Hi,

Thanks for that - a nice idea - it sounds like it will definitely work.

I'd really like to display a random message when the program first loads but waiting for a key press will suffice I guess...

I've been reading about it... and on PCs you can call a function called rdtsc() to do the seed but alas that's not available from the Uze libraries.

It's a bit like Tron, the Uze needs to be able to reach out to the real world to get back some additional info...

- PJ
User avatar
D3thAdd3r
Posts: 3221
Joined: Wed Apr 29, 2009 10:00 am
Location: Minneapolis, United States

Re: Seeding the Random Number Generator

Post by D3thAdd3r »

PitfallJones wrote:on PCs you can call a function called rdtsc()
Yep even that(in an ideal world) is deterministic as it's just cycles since reset, the randomness there being how long it took for the user to start the program OR if it was auto executed when windows loaded, then whatever random time windows takes to load(most likely the mechanics of the hard drive being the biggest variable there, cold or warm boot, etc)

Edit-In the real world I would wager you are totally right though, and it would end up being pretty random as a PC has a lot more subsystems going on.
User avatar
uze6666
Site Admin
Posts: 4801
Joined: Tue Aug 12, 2008 9:13 pm
Location: Montreal, Canada
Contact:

Re: Seeding the Random Number Generator

Post by uze6666 »

What about this: True random number generation on an Atmel AVR microcontroller. They use the jitter of the internal RC oscillator as a random source. Alas, it's a paywalled article. :(
It's a bit like Tron, the Uze needs to be able to reach out to the real world to get back some additional info...
With a net interface we could call a random generator service...
User avatar
D3thAdd3r
Posts: 3221
Joined: Wed Apr 29, 2009 10:00 am
Location: Minneapolis, United States

Re: Seeding the Random Number Generator

Post by D3thAdd3r »

I was too cheap to pay to read that article but I googled a bit and think I get the jist of it. That would be a nice feature to have in the kernel I think, 8bit or 16bit compile time switch? It seems like it would be impractical to get 30 16bit random number a second from this method, but it could make a nice seed for an LFSR in demo programs that require no user interaction.
User avatar
uze6666
Site Admin
Posts: 4801
Joined: Tue Aug 12, 2008 9:13 pm
Location: Montreal, Canada
Contact:

Re: Seeding the Random Number Generator

Post by uze6666 »

I agree, that it seems too slow for in game use. But all is needed is to generate the seed value at the beginning. Do you have more details on the technique?
User avatar
D3thAdd3r
Posts: 3221
Joined: Wed Apr 29, 2009 10:00 am
Location: Minneapolis, United States

Re: Seeding the Random Number Generator

Post by D3thAdd3r »

Well I think I get the idea enough to know what they are even talking about is all I mean :lol: I acquired an interesting document, check your PM and let me know what you think about it. I am a bit confused, so the RC clock is disabled on uzebox as far as clocking the processor...but we can still read it?
User avatar
uze6666
Site Admin
Posts: 4801
Joined: Tue Aug 12, 2008 9:13 pm
Location: Montreal, Canada
Contact:

Re: Seeding the Random Number Generator

Post by uze6666 »

Did you had a chance to test out the ideas in the paper? I've read some specs that says the internal rc oscillators can deviate by as much as 1%. So that could be as much as 280k cycles off per second compared to the crystal oscillator.
Post Reply