gbadev.org forum archive

This is a read-only mirror of the content originally found on forum.gbadev.org (now offline), salvaged from Wayback machine copies. A new forum can be found here.

Coding > Returning a random value between X and Y

#346 - sgeos - Mon Jan 06, 2003 6:42 pm

For as long as I have been programming I've used the following code to return a number between X (from) and Y (to) inclusive:

return
(
from +
(int)((to - from + 1) * ((double)rng() / RNG_MAX_PLUS))
);

Where rng() is a call to an RNG (random number generator) and RNG_MAX_PLUS is one more than the highest number the RNG will return. Depending on the RNG, I'll do something like this:

(double) (rng() >> 16) / 0x10000

I realize that the GBA deals with floats slowly, but I continued to use the above code because it is extremely useful. Now that I'm learning ASM I'd like an ASM equivalent. This is the best solution I've come up with yet:
A) get a random number
B) mask off the high bits of (to - from + 1), depending on the value.
C) If the result is too big toss it and go to step A
D) add from

Assuming that this is the best solution, I'll still need a way to clear the high bits depending on the value of (to - from + 1). If that comes out to 17, then we need to and the 32 bit random number with 0x1F. If it is 500, then the mask needs to be 1FF.

*Any* help or insight will be greatly appreciated.

-Brendan

#357 - Touchstone - Mon Jan 06, 2003 8:39 pm

Well, you could just implement this in asm:
Code:
val = min + (rand() % (max-min));

With the division system call (no. 6) you can get the remainder aswell as the result and as we all know the remainder of a division is basically what you get when you use the % operator in C. After a division systemcall the remainder is located in register r1.

However this will not make it possible to get 'max' back from the function, highest possible out would be 'max-1'.

#366 - sgeos - Mon Jan 06, 2003 9:45 pm

Touchstone wrote:
However this will not make it possible to get 'max' back from the function, highest possible out would be 'max-1'.


That is why it needs to be % (max - min + 1). When dealing with small numbers in particular an error is introduced when using mod. Let's say that we want a number from zero to four, and we have a RNG that returns one of 16 possibilities.

01234
56789
abcde
f

The chances of getting zero are 1/4, the chances of getting 1, or 2... are 3/16.

I wonder... maybe if (max - min + 1) is never greater than 2^16 (65535) then this might work:
A) put rng() >> 16 on a register (this is no more than 2^16)
B) multiply (max - min + 1) with that register (no more than 2^32)
C) divide by 0x10000
D) add min

Somehow it seems like I've come up with that solution before... =P Regardless, does anyone see any problems?

-Brendan

#379 - Costis - Tue Jan 07, 2003 2:41 am

Hi,

The above code may be find if you're not doing anything GBA processor intensive. Otherwise, I suggest you study the Mersene-Twister random number generator algorithm. It's fast and doesn't require much memory. Plus, the library call "rand()" and the "%" modulus operator are very slow.

Costis

#384 - col - Tue Jan 07, 2003 3:36 am

Costis wrote:
Hi,

...I suggest you study the Mersene-Twister random number generator algorithm. It's fast and doesn't require much memory...

Costis


I suggest you don't !!!

The Mersene twister uses a fairly large table of values that can be used only once each. When they're all gone, you have to generate a new table, thats the last thing you want to be doing realtime!

if you want good random numbers with shifts and adds a better bet would be a tausworthe generator.

http://www.iro.umontreal.ca/~lecuyer/myftp/papers/tausme.ps
this paper has all the gory details and most importantly a nice simple code example :)

for most things you don't need high quality randomness so you'd be best with one of the faster techniques discussed on the gbadev yahoo group

http://groups.yahoo.com/group/gbadev/message/11186

hope this helps.

cheers

col.

#387 - sgeos - Tue Jan 07, 2003 4:51 am

Costis wrote:
The above code may be find if you're not doing anything GBA processor intensive. Otherwise, I suggest you study the Mersene-Twister random number generator algorithm. It's fast and doesn't require much memory. Plus, the library call "rand()" and the "%" modulus operator are very slow.


I don't use rand(), I write my own RNGs. As for % or even division on the GBA, I know that they are slow, but I'm not going to be wanting a value between X and Y very often. Most RNG intensive stuff I can just mask off bits:

something = rng() & 0xFFFF;

I was actually inspired to write my own RNGs by the mersenne twister. I write bit scramblers. I like the notion of pseudorandom, but wanted something that goes in reverse as well as forward. =)

-Brendan

#388 - sgeos - Tue Jan 07, 2003 4:56 am

[quote="col]
The Mersene twister uses a fairly large table of values that can be used only once each. When they're all gone, you have to generate a new table, thats the last thing you want to be doing realtime!
[/quote]

That I did not know! Currently I'm using a custom fibonacci sequence based bit scrambler (mixer)

Thanks for the sites. I imagine that they'll be interesting. It's so sad that neither one of you read my profile. I clearly list custom RNGs as an interest.

-Brendan

#466 - col - Tue Jan 07, 2003 11:23 pm

sgeos wrote:
[quote="col]
The Mersene twister uses a fairly large table of values that can be used only once each. When they're all gone, you have to generate a new table, thats the last thing you want to be doing realtime!


That I did not know! Currently I'm using a custom fibonacci sequence based bit scrambler (mixer)

Thanks for the sites. I imagine that they'll be interesting. It's so sad that neither one of you read my profile. I clearly list custom RNGs as an interest.

-Brendan[/quote]


Sorry for not reading your profile - my post was a response to costis reccomendation of the Mersenne Twister for GBA development.

However I'm surprised that someone with such an interest in RNGs hasn't read up on this, and also that you are asking such a (with all due respect)basic question to start the thread - maybe this is why we took the tone we did ;-)

To answer your initial question I would pick an RNG that gives a 0...1 range and multiply the result by max-min, finally adding min to the result.

As i'm sure you know, you should be using fixed point arithmetic, in this case a 32 bit random number can always be between 0 and 1

and if you used a little inline ARM assembly, you can use the umull 64bit multiply to speed things up without a loss of precision.

r0 is max
r1 is min
r2 is randomNum

sub r0,r0,r1
umull r3,r0,r2,r0
add r0,r0,r1

r0 is now random within the required range

(if you want max and min to be fractional (fixed point) you'll need to rotate the 64bit umull answer to account for this...
and i'll leave it as an exercise to work out the fiddly inline asm syntax in your chosen compiler)

there you go - no division required just a SUB, an ADD and a UMULL :)


cheers

col
(who spent two whole evenings reading up on RNGs, but has no particular interest in them beyond their utility value)

#470 - ampz - Wed Jan 08, 2003 12:38 am

For a perfectly good random number source, set a timer to count at a very high speed, and read the few least significant bits out of the timer when the user press a button.
If you need more bits, then just combine the bits from several key presses.

For a random number between min and max w/o consuming too much CPU power: (pretty much same thing as the previous poster, but in C)

rn is a random number between 0 and 255.
min is the lower limit
max is the upper limit + 1

result=min+(rn*(max-min))>>8;

This works well if your range (max-min) is smaller than let's say 100, if your range is larger then you have to use random numbers (rn) with a larger range too. 0-65536 for example. In that case you should also bitshift the result 16 steps instead of 8.

No floats, no % operators, no divisions.

#482 - Touchstone - Wed Jan 08, 2003 1:48 am

ampz wrote:
For a perfectly good random number source, set a timer to count at a very high speed, and read the few least significant bits out of the timer when the user press a button.

The backside of this method of retreiving random numbers is that you cannot expect getting the same random number pattern twice thus it cannot be used for network code for instance when the behaviour of an enemy is independently decided for all four machines.
_________________
You can't beat our meat

#622 - ampz - Thu Jan 09, 2003 12:56 am

Uuuh, what???? The master system decides the behaviour of the enemies, the slave systems just do what the master tells them to do.

A random number generator is _supposed_ to generate random numbers. You are not supposed to be able to predict the result. Even under two identical conditions (like two networked and synced GBA's) it's not supposed to generate the same number.

#683 - Nessie - Thu Jan 09, 2003 6:39 pm

I agree with Col. There are certain kinds of applications where getting very high quality random numbers is extremely important, issues like security, etc. ...but this does not apply to most games.

So, I honestly believe that it would be far better to use a very fast, zero memory solution to generate your random numbers. People can talk about bad random number generation and how it usually results in clumpy distributions, but what's the point? The GBA isn't capable of very high quality *real-time* simulations anyway...so we have to settle for approximations. Not that this is a bad thing...rather, I'd suggest that allocating any memory, short of a couple of static u16's, for random number generation is a foolish waste of limited resources. :)

#684 - Nessie - Thu Jan 09, 2003 6:43 pm

Actually ampz, there might be cases where having a random number generator that can be "seeded" and generate consistent "random" results could be a very clever network optimization.

Example, say you have a game where random enemies can spawn in at a given spot. The enemy could be of random type with random health, armor, gold, experience, etc. Ideally the master should control any global behaviours, like spawning, so instead of passing all that crap across the network cable, just pass the seed used to generate those random numbers and all clients automatically would generate the same results. The master would not have to be limited in any way as far as how it generates the seed....just so long as you know that the result of the seed is consistent for itself and all clients.

I'm not saying that you'd always want to do this, but it certainly is a valid way to optimize network transmission if bandwidth is a serious issue....

#687 - Touchstone - Thu Jan 09, 2003 7:08 pm

Ampz, I didn't say your method was wrong, I just pointed out the downsides of having a true random number generator instead of a psuedo-random number generator.
_________________
You can't beat our meat

#693 - sgeos - Thu Jan 09, 2003 7:48 pm

Thanks alot. This is actually what I was looking for:
result=min+(rn*(max-min))>>8;
The shifting by 8. Stupidity got the better of me and I was thinking "divide by 0x100".

My original question simple? Sure. I'm going to be making a fool of myself often and ask a lot of simple questions. There is no better way to learn IMHO.

As far as the timer method goes, if you check user input once a frame, will that method still work? I personally like the notion of pseudo random-ness, and nothing prevents including both a reseedable RNG and a "real RNG".

-Brendan

#711 - ampz - Thu Jan 09, 2003 10:48 pm

You need a real random source to seed the pseudo random source in any case.

#718 - Touchstone - Thu Jan 09, 2003 11:19 pm

Actually, you don't need a real random source if you go with pseudo-random numbers. Just look at the mersenne twister for instance. http://www.math.keio.ac.jp/~matumoto/emt.html Mersenne twister is a really good pseudo-random number generator btw. It's fast, doesn't require that much memory and it's japanese. :)
_________________
You can't beat our meat

#720 - Nessie - Thu Jan 09, 2003 11:39 pm

I completely agree...pseudo-random number generation is plenty sufficient for most games...I'd choose a solution that is fast and doesn't use much ( or any memory ) and be done with it.

#722 - coca77 - Thu Jan 09, 2003 11:44 pm

I'd love to use an algorithm with the tagline 'A 623-Dimensionally Equidistributed Uniform Pseudo-Random Number Generator' but the 624 words it needs is a bit much isn't it?

#727 - Touchstone - Fri Jan 10, 2003 12:14 am

I'm not sure how much memory other random number generators use byt with approx. 2500 bytes memory used you've gotten away quite cheap. It is possible that you can reduce the size of it's buffer to, I don't know.
_________________
You can't beat our meat

#731 - Nessie - Fri Jan 10, 2003 12:33 am

The rand generator I use requires 2 u16's...no divides, mod's, or array look-ups....just shifts, mult's and masking...so it's fast.

Of course, maybe I should write a util to graph out the results and see if the distribution is terrible. : ) Still, it seems to work fine for what I'm using it for. And I highly doubt that someone playing my game is going to even know the difference.

#732 - squeakytoy - Fri Jan 10, 2003 1:02 am

coca77 wrote:
I'd love to use an algorithm with the tagline 'A 623-Dimensionally Equidistributed Uniform Pseudo-Random Number Generator' but the 624 words it needs is a bit much isn't it?


Can't you can reduce that if your happy to have a smaller period of results?

#741 - col - Fri Jan 10, 2003 4:03 am

sgeos wrote:
Thanks alot. This is actually what I was looking for:
result=min+(rn*(max-min))>>8;
The shifting by 8. Stupidity got the better of me and I was thinking "divide by 0x100".

My original question simple? Sure. I'm going to be making a fool of myself often and ask a lot of simple questions. There is no better way to learn IMHO.

As far as the timer method goes, if you check user input once a frame, will that method still work? I personally like the notion of pseudo random-ness, and nothing prevents including both a reseedable RNG and a "real RNG".

-Brendan


hehe - you ain't no fool for asking a simple question.
remember there are no stupid questions, only stupid answers ;-)

glad you got it sorted anyway, cheers

col

#744 - sgeos - Fri Jan 10, 2003 4:18 am

Here is a link to a C implementation of my "Mixer":
http://granicus.if.org/~sgeos/mixer.c

Although it is not grounded in anything academic (only "that should scramble them bits up real good!"), it is a special type of RNG. If every operation is preformed in reverse oreder, you can actually get the *previous* term. Useful if you are generating *stuff* pseudo-randomly:

A) Ambidextrous if the RNG returns between 0xFD6F and 0xFFFF.
B) Work backwards to find all ambidextrous characters
C) Find that ambidextrous, red-eyed, scorpio, wind element, etc,etc

After I (have time to) make an ASM implementation you can all have fun shooting holes in it until it's bullet proof, if you want to. =)

-Brendan

PS Has anybody found a non hobby-ist RNG with this property?

#763 - AnthC - Fri Jan 10, 2003 1:29 pm

I use a quick n dirty random number generator

U32 RandN;

U32 Rand(void)
{
RandN*=17;
RandN+=0x17250381;
if (RandN>=0x80000000U) RandN+=1;
return RandN;
}

Then I just mask off the stuff I want using % or &

#785 - sgeos - Fri Jan 10, 2003 5:43 pm

AnthC wrote:
if (RandN>=0x80000000U) RandN+=1;


It looks more or less like a LCG, except that I do not understand the above line? What does it do?

-Brendan

#804 - AnthC - Fri Jan 10, 2003 7:29 pm

Carry propagation - it was back from when I used to use a combination of a shift and add

#806 - grumpycat - Fri Jan 10, 2003 7:45 pm

AnthC wrote:
I use a quick n dirty random number generator

U32 RandN;

U32 Rand(void)
{
RandN*=17;
RandN+=0x17250381;
if (RandN>=0x80000000U) RandN+=1;
return RandN;
}

Then I just mask off the stuff I want using % or &


That's almost the same as mine. I've been using:

rnd = rnd * 5 + 17

since my 6502 days.

It's pretty cool, as if you call that function 2^N times, and use the result masked with 2^N - 1, it is guaranteed to give you every value - very nice for copying an image into the display for a Star Trek transporter-like effect.

Generally, it's just a weak, but good enough, random number generator.

Grumpy.

#43335 - Deanonious - Sun May 22, 2005 6:31 am

Okay I am trying to implement a Taus88 Algorithm that generates Random-Numbers between 0 and 1 and I need to make it so that I can generate more useful numbers that are not doubles and then write a function that bounds the results between a minimum and a maximum value. I've read through most of the posts that I could find on the forum and havn't seemed to find a suitable answer, but then again maybe I am blind lol

#43345 - tepples - Sun May 22, 2005 2:47 pm

Deanonious wrote:
Okay I am trying to implement a Taus88 Algorithm that generates Random-Numbers between 0 and 1

There are no integers strictly between 0 and 1, and the GBA is very slow at floating-point arithmetic. Or are you using fixed-point?
_________________
-- Where is he?
-- Who?
-- You know, the human.
-- I think he moved to Tilwick.

#43384 - Deanonious - Sun May 22, 2005 10:20 pm

Well the algorithm is a combined Tausworthe Generator designed by Pierre L'Ecuyer with a period of 2^88. I believed that Col mentioned it earlier in this thread, granted it is a fairly old thread.

The algorithm runs exceptionally fast on many computers... for instance it generated 1 million random numbers on a Sun SPARCstation 20 in only 0.9 seconds and 3.2 seconds on a 33MHz 486. Granted both of those systems contained an FPU even if they are old by modern standards.

Right now I was writing it mainly as a general use Generator and I was going to do some testing to see just how inefficient it ran on the GBA, but assumed it may be useful to me either way as an alternative to the rand() function during PC development. It's a learning experience. I have found that sgeos dice() function (using unsigned long's instead of signed long's, as signed longs give me sign errors occassionally) from another thread or your ayn() function from that same thread will probably work best for GBA game development.

It does make extensive use of Floating-Point Math, as you are correct there does not exist any Integers between 0 and 1. I am also looking into methods of utilizing fixed-point math, but for right now would rather have a stable implementation and worry about optimizations later.

The C-Function that I am using is almost verbatim out of Dr. L'Ecuyer's paper but I shall post it here for simplicity.


Code:

double Taus88RNG( void )
{
   B = ( ( ( Seed1 << 13 ) ^ Seed1 ) >> 19 );

   Seed1 = ( ( ( Seed1 & 4294967294 ) << 12 ) ^ B );

   B = ( ( ( Seed2 << 2 ) ^ Seed2 ) >> 25 );

   Seed2 = ( ( ( Seed2 & 4294967288 ) << 4 ) ^ B );

   B = ( ( ( Seed3 << 3 ) ^ Seed3 ) >> 11 );

   Seed3 = ( ( ( Seed3 & 4294967280 ) << 17 ) ^ B );

   return ( ( Seed1 ^ Seed2 ^ Seed3 ) * 2.3283064365e-10 );
}

#43386 - strager - Sun May 22, 2005 10:34 pm

I am assuming that the topic writter means this:
I want a function like int rand(int min, int max), no?

Just do a random number function, then check if it is in the bounds. If not, recalculate.

Or are you talking about something else (I haven't read the topic yet).

#43388 - poslundc - Sun May 22, 2005 11:12 pm

strager wrote:
Just do a random number function, then check if it is in the bounds. If not, recalculate.


Please, please, don't ever do this. This method is both wasteful and runs in non-deterministic time.

Deanonious: If you want to use Tau88 on a computer with an FPU that's fine, but if you're looking to adapt it to the GBA then it seems rather pointless as it's clearly designed to operate on intervals useful for floating-point. Just use a simple LCG or any of the other algorithms you can find by searching this forum.

Dan.

#43389 - strager - Mon May 23, 2005 12:26 am

I've got it (I think).

Code:
/* rand() must return a u16 value */
u32 rrand(u32 min, u32 max)
{
    u32 ret = rand();

    ret *= max - min;
    ret >>= 16;
    ret += min;

    return(ret);
};


I've worked it out mentally and it seems logical.

#43392 - tepples - Mon May 23, 2005 12:56 am

poslundc wrote:
Please, please, don't ever do this. This method is both wasteful and runs in non-deterministic time.

This may be true of the GBA, where 'umull' runs with blazing speed, but a lot of us come from platforms where multiplication is slow and PRNGs in a non-power-of-two-sized range require various hacks to get around this.

Quote:
Deanonious: If you want to use Tau88 on a computer with an FPU that's fine, but if you're looking to adapt it to the GBA then it seems rather pointless as it's clearly designed to operate on intervals useful for floating-point. Just use a simple LCG or any of the other algorithms you can find by searching this forum.

The body of the function uses integer arithmetic and results in a number (Seed1 ^ Seed2 ^ Seed3) distributed uniformly in [0, 1<<32). Only the final multiplication by 2.3283064365e-10 uses the FPU, and that's easily converted to fixed point with the 'umull' instruction.

Untested code that illustrates what I'm talking about:
Code:
u32 Seed1, Seed2, Seed3;

/* Generates a pseudorandom number in [0, (1<<32) - 1]. */
u32 Taus88RNG_int( void )
{
   B = ( ( ( Seed1 << 13 ) ^ Seed1 ) >> 19 );

   Seed1 = ( ( ( Seed1 & 4294967294 ) << 12 ) ^ B );

   B = ( ( ( Seed2 << 2 ) ^ Seed2 ) >> 25 );

   Seed2 = ( ( ( Seed2 & 4294967288 ) << 4 ) ^ B );

   B = ( ( ( Seed3 << 3 ) ^ Seed3 ) >> 11 );

   Seed3 = ( ( ( Seed3 & 4294967280 ) << 17 ) ^ B );

   return ( Seed1 ^ Seed2 ^ Seed3 );
}

/* Generates the next uniform pseudorandom number in [min, max-1].
   GCC uses the umull instruction when computing r_scaled. */
unsigned int Taus88RNG_range(unsigned int min, unsigned int max)
{
  unsigned int r = Taus88RNG_int();
  unsigned int r_scaled = ((max - min) * (unsigned long long)r) >> 32;
  return min + r_scaled;
}

_________________
-- Where is he?
-- Who?
-- You know, the human.
-- I think he moved to Tilwick.

#43535 - Deanonious - Tue May 24, 2005 6:26 am

Dear Tepples,

Thank you very much for your time and effort in replying to my messages. I feel stupid by how blatantly simple my first question was to answer, the one about getting Integer results from the algorithm. The scaler routine is a bit trickier. I am amazed at how helpful everyone is in the group, and your comments regarding the Taus88 Algorithm were both very insightful and helpful. Also, your code worked like a charm. Thanks again!!!

Sincerely,
Dean

#43863 - sgeos - Fri May 27, 2005 11:21 am

Deanonious wrote:
I have found that sgeos dice() function (using unsigned long's instead of signed long's, as signed longs give me sign errors occassionally) from another thread or your ayn() function from that same thread will probably work best for GBA game development.

This was one of my first threads. Wild that it got bumped. IIRC the signed version of my goofy dice() function will work properly if you call dice(-17, 53)- ie it will return negative values. I think it also works properly if called dice(100, -100)- ie dice(max, min), although that is a goofy way to call it. If signed longs give sign error, you must be working with fairly large numbers.

The Taus88RNG looks neat. Wish I had time to carefully read it. Good luck!

-Brendan

#43909 - Deanonious - Fri May 27, 2005 10:54 pm

Dear Sqeos,

The Taus88 Algoritm runs about 1/2 as fast as your Dice() algorithm on an Athlon 2500+ Barton CPU, it can generate 100million random numbers in 3,422ms whereas your Dice() algorithm takes only about 1,750ms both are tested under MS Visual C++ 6.0 with /02 (Speed Optimizations) on Windows XP. I have yet to test it out on the GBA but plan to do so soon.

Dean

#43921 - sgeos - Sat May 28, 2005 3:18 am

I'm not concerned about speed. I have a general interest in RNGs, and Taus88 looks really nifty. I'm currently using something like this:
Code:
typedef signed long   rng_state_t;

#define RNG_M    0x00010DCD
#define RNG_IM   0xA5E2A705   /* 32 bit inverse multiplier */
#define RNG_C    1
#define RNG_BITS_IN_BTYE   8
#define RNG_SHIFT          ( (RNG_BITS_IN_BTYE * sizeof(rng_state_t)) / 2 )

rng_state_t rng_f       (void);
rng_state_t rng_b       (void);
void        rng_reverse (void);
rng_state_t rng_range   (rng_state_t p_min, rng_state_t p_max);

rng_state_t   m_rng_state;
rng_state_t   (*rng)(void)   = rng_f;

rng_state_t rng_f(void)
{
   m_rng_state *= RNG_M;
   m_rng_state += RNG_C;
   return m_rng_state;
}

rng_state_t rng_b(void)
{
   m_rng_state -= RNG_C;
   m_rng_state *= RNG_IM;
   return m_rng_state;
}

void rng_reverse(void)
{
   if (rng_f == rng)
      rng = rng_b;
   else /* rng_b == rng */
      rng = rng_f;
}

rng_state_t rng_range(rng_state_t p_min, rng_state_t p_max)
{
   rng_state_t base   = p_min;
   rng_state_t range  = p_max - p_min + 1;
   rng_state_t result = rng();

   result = result >> RNG_SHIFT;
   result *= range;
   result /= (1 << RNG_SHIFT);
   return (result + base);
}


If you want to jump around in a pseudorandom sequence, you can use something like this:
Code:
rng_state_t rng_skip(int p_skip)
{
   int result;
   int max;
   int i;

   if (p_skip < 0)
   {
      rng_reverse();
      max = -p_skip;
   }
   else
      max = p_skip;
   for (i = 0; i < max; i++)
      result = rng();
   if (p_skip < 0)
      rng_reverse();
   return result;
}


-Brendan