GP2X Random Numbers


Feeg

Still Fresh
Joined
Apr 29, 2006
Messages
99
Age
39
Location
Sydney, Au
Website
Visit site
Am I right in thinking that if I'm avoiding using established libs, I'll need to write a pseudo random number generator myself if I want to incorporate randomness into an application written along similar lines to DZZ's demo tutorial thread?

I've checked the various reference documents and can't find anything useful, so I suspect I'll have to do something myself. My only worry is that without a real clock on the machine I won't have much to seed with. I guess I could go with the least significant digits in the difference in time since bootup. That'd be sufficient for my needs.

Before I jump in though, there's nothing in the ARM instruction set that'll help is there?

Cheers :D
 
Feeg posted on Sep 3 2006 at 02:24 AM said:
Am I right in thinking that if I'm avoiding using established libs, I'll need to write a pseudo random number generator myself if I want to incorporate randomness into an application written along similar lines to DZZ's demo tutorial thread?

I've checked the various reference documents and can't find anything useful, so I suspect I'll have to do something myself. My only worry is that without a real clock on the machine I won't have much to seed with. I guess I could go with the least significant digits in the difference in time since bootup. That'd be sufficient for my needs.

Before I jump in though, there's nothing in the ARM instruction set that'll help is there?

Cheers :D

couldn't you seed with SDL_GetTicks?

Er, unless you're avoiding the SDL library, that is.
 
Last edited by a moderator:
Feeg posted on Sep 2 2006 at 07:24 PM said:
Am I right in thinking that if I'm avoiding using established libs, I'll need to write a pseudo random number generator myself if I want to incorporate randomness into an application written along similar lines to DZZ's demo tutorial thread?

I've checked the various reference documents and can't find anything useful, so I suspect I'll have to do something myself. My only worry is that without a real clock on the machine I won't have much to seed with. I guess I could go with the least significant digits in the difference in time since bootup. That'd be sufficient for my needs.

Before I jump in though, there's nothing in the ARM instruction set that'll help is there?

Cheers :D
Google knows about lots of algorithms for making "random" numbers.

You do have a clock you can access to seed an algorithm, it's register address 0x0A00
 
Last edited by a moderator:
Thanks Dzz.

I've already had a quick google around and the algorithms don't seem particularly complex, but in terms of performance I'm guessing I might need to precalc a bunch of numbers during initialisation and stuff them in an array.

Is that fairly standard for library independant demos? Presumably so, just like pre calculating sine tables..

and now I'm rambling... Cheers for the clock hint.
 
Linux has /dev/random too (or /dev/urandom if you're really paranoid about randomness, but it's not guaranteed to return a value immediately). It won't be as high performance as a built in RNG though, but could be useful for seeding.
 
It really depends why you need random numbers and how random they need to be. My tinylife program uses a simple LCRNG, which requires 12 bytes of data storage including constants, and for most purposes generates perfectly good random numbers, provided you ignore the bottom 16 bits of the result!

Here's the relevant code...

Code:
lcrng_params:
	.word   0x00000000	// lcrng_seed
	.word   0x0019660d	// lcrng_A
	.word   0x3c6ef35f	// lcrng_B
...
random:
	adr	 r3, lcrng_params	 // locate the parameter block
	ldmia   r3, { r0, r1, r2 }   // load the parameters
	mla	 r0, r1, r0, r2	   // multiply and accumulate into the seed
	str	 r0, [r3]			 // store the new seed back to the paramter block
	mov	 r0, r0, lsr #16	  // discard low bits
	mov	 pc, lr			   // return to caller

If you need a lot of random numbers at once, you can load the parameter block once and repeat the mla line to pull as many numbers as you need, and only save the seed when you're done. This is what I did in tinylife, and one advantage of the LCRNG in that context is that it requires very little data storage and hardly any code.

You still need to set the seed - I'd just call gettimeofday and use the microseconds value, which ought to give different enough values on successive runs. gettimeofday is system call 78, and needs a pointer to 8 bytes in r0 and zero in r1 on entry.

Code:
	sub sp, sp, #8		  // reserve 8 bytes on the stack
	mov r0, sp			  // point r0 at those bytes
	mov r1, #0			  // r1 should be NULL
	swi #0x900000+78		// sys_gettimeofday
	ldr r0, [r0, #4]		// load microseconds field
	str r0, lcrng_params	// store random seed
	add sp, sp, #8		  // pop the reserved bytes off the stack

I haven't tested either the seeding code or the actual random function - they're just based on the working code in tinylife - so apologies if they don't work straight away.
 
a good MAQR random that uses 1 32bit word for seeding.
(easy to save/load state...)

Code:
#include <time.h>
#include "rnd.h"

long rnd_seed;

void reset_rnd_seed(void)
{
	set_rnd_seed((time(NULL)%(RNG_M-1))+1);
}

void set_rnd_seed(long seedval)
{
	rnd_seed=seedval;
}

long get_rnd_seed(void)
{
	return(rnd_seed);
}


long rnd(void)
{
	long low, high, test;

	high = rnd_seed / RNG_Q;
	low = rnd_seed % RNG_Q;
	test = RNG_A * low - RNG_R * high;
	if(test>0)
		rnd_seed = test;
	else
		rnd_seed = test + RNG_M;

	return rnd_seed;
}

long xrnd(long maxrnd)
{
	if(maxrnd==0L)
		return rnd();
	else
		return((rnd())%maxrnd);
}

and the header

Code:
#ifndef RND_H
#define RND_H

#ifdef __cplusplus
extern "C"{
#endif

#define RNG_M 2147483647L	/* m = 2^31 - 1 */
#define RNG_A 48271L
#define RNG_Q 127773L		/* m div a */
#define RNG_R 2836L			/* m mod a */

extern long	get_rnd_seed(void);
extern void	reset_rnd_seed(void);
extern void	set_rnd_seed(long seedval);
extern long	rnd(void);
extern long	xrnd(long maxrnd);

#ifdef __cplusplus
};
#endif
#endif
 
Back
Top