Random Integer Generation

[Redbluefire]

Im going to get straight to the point, Generating a random Integer between one and one hundred has been hell on me, its hard enough to generate an integer between two set integers in normal C++, would anyone mind helping (See: Spoonfeeding) Me with this? Thanks.





-Rbf

[cwbowron]

Im going to get straight to the point, Generating a random Integer between one and one hundred has been hell on me, its hard enough to generate an integer between two set integers in normal C++, would anyone mind helping (See: Spoonfeeding) Me with this? Thanks.

rand() function in <stdlib.h> will return a random number between 0 and the largest representable positive integer in C. srand() will seed the random number generator.

If you are stuck on how to get it between 1 and 100 you do this:


int n = rand() % 100 + 1;

general form, something like this:

Code: Select all

int get_random(int lo, int hi)
{
    return (rand() % (hi-lo+1)) + lo
}

[Shine]

You could write a general C++ class for calculating random values between two limits. A sample with this class in ANSI C++ could look like this:

Code: Select all

#include <cstdlib>
#include <ctime>
#include <iostream>

using namespace std;

class Random &#123;
public&#58;
	Random&#40;const int min, const int max&#41; &#58; m_min&#40;min&#41;, m_max&#40;max&#41;
	&#123;
		srand&#40;clock&#40;&#41;&#41;;
	&#125;
	
	int next&#40;&#41; const
	&#123;
		return &#40;rand&#40;&#41; % &#40;m_max - m_min + 1&#41;&#41; + m_min;
	&#125;

private&#58;
	int m_min;
	int m_max;	
&#125;;


int main&#40;int argc, char** argv&#41;
&#123;
	Random random&#40;1, 100&#41;;
	for &#40;int i = 0; i < 25; i++&#41; cout << random.next&#40;&#41; << endl;
	return 0;
&#125;

Of course, in Lua it's simpler, but please ignore it, C++ is much more powerful and real man don't use script languages :-)

Code: Select all

green = getColorNumber(0, 255, 0) 
math.randomseed(os.time())
for y = 1,25 do
	printText(10, y * 10, math.random(100), green)
end
flipScreen() 

[patrickoneal]

I would just google for random number generator algorithms, and use a modulus function to limit the results, something like

int foo, foo2;

foo = random_function_I_found with_ google();

foo2 = foo % 101;

Not that I assume you don't know, but the modulus function(%) divides the first operand by the second and returns the remainder, so this would yield a number between 0 and 100.

If you really wanted between 1 and 100 you could use:

foo2 = foo % 100; //yields a number between 0 and 99

foo2 = foo2 + 1; //changes range to 1 to 100

or even

foo2 = foo2 + 5 //yield a number between 5 and 104

Of course all of this can be condensed to a single line, I wanted to be verbose for clarity. I've never written any code for the psp, but if modulus is there you should be able to just cut and paste an RNG from somewhere else. If modulus isn't available, you should be able to write your own function fairly easily. Off the top of my head it would be this(very inefficient):

int modulus(int foo, int divide_by){

while(true){
if (foo>divide_by)
foo = foo-divide_by;
else
break;
}
return foo;
}

Hope this helps,

Patrick

[Agoln]

Of course, in Lua it's simpler, but please ignore it, C++ is much more powerful and real man don't use script languages :-)

Thank you for realizing that REAL men dont use script languages. Welcome to the dark side :). Now, I just have to finish my PHP website....

[ector]

It's funny how noone ever seems to note that rand() % yourmaxvalue is biased toward lower values...

[Shine]

It's funny how noone ever seems to note that rand() % yourmaxvalue is biased toward lower values...

Why? rand is random, so using rand()%value should be random, too. I've tried it with this loop:

Code: Select all

	Random random(1, 100);
	int c[101];
	int i = 0;
	for &#40;i = 0; i <= 100; i++&#41; c&#91;i&#93; = 0;
	int max = 10000000;
	for &#40;i = 0; i < max; i++&#41; c&#91;random.next&#40;&#41;&#93;++;
	for &#40;i = 0; i <= 100; i++&#41; cout << abs&#40;max / 100 - c&#91;i&#93;&#41; << endl;
	return 0;

(and changed the constructor of my original code to "srand(time(NULL))") and it looks not biased. Summing the first 50 values and the second 50 doesn't show a bias.

[patrickoneal]

Why is that, ector?

Patrick

[cyod]

It is true that it is baised such that the original random function generates a number on a range such that the highest number does not divide evenly. This is somewhat negligable when the random number function has extremely large intervals and is acceptable for the average program.

Edit: This can be seen with a smaller example. If you had a rand() that randomly returned a number between 0 and 2 then you do rand()%2

Code: Select all

rand |  rand%2
0           0
1           1
2           0

You can see that 0 would be twice as likely as 1. This difference in probably greatly decreases as the interval of rand() gets larger with comparsion to what you are modding by as the statistical difference occurs due to the final few highest numbers not being modded evenly, like if you had rand() that generated 0 to 65535 and you did rand()%3 then 21846 different numbers generate 0, and 21845 numbers would generate each of 1 and 2. In otherwords there is a ~33.33435% chance of 0 and ~33.33285% chance of 1 or 2 when it should be ~33.33333% of each.

[ector]

Yup, cyad has the right explanation there.

A more correct way is rand() * yourRange / RAND_MAX.

Although for most purposes and small ranges, % yourRange is good enough.

[Redbluefire]

Thanks for all the help guys, but theres one flaw in the code, which is why i came to ask:

This was my code from help with cyberbill, it always returned 66:

Code: Select all

int Rando(int min, int max)
             {
              int Diff = max - min;
              return (rand() % Diff)+min;
             }

this code from cwbowron always returns 34

Code: Select all

int rando(int lo, int hi)
{
    return (rand() % (hi-lo+1)) + lo;
} 

i was wondering if you could help me with some code like the snake game uses, based off the clock:

Code: Select all

void initSeeds() 
{ 
   seed1 = sceKernelLibcTime((void *) 0); 
   seed2 = sceKernelLibcTime((void *) 0); 
} 

unsigned int myRand() 
{ 
   seed1 = (seed1 + 46906481) ^ seed2; 
   seed2 = seed1 ^ &#40; &#40;&#40;seed2<<3&#41; | &#40;seed2 >> 29&#41;&#41; + 103995407&#41;; 
    
   return seed1 - seed2; 
&#125;

My main problem was just changing that, so it only gives results between 1 and 100

Sorry about not being more specific in the first post, but i Really do appreaciate the help.



-Rbf

[Krevnik]

The bias is from a flaw in the RNG, rather than from the modulo. I personally tend to like constructing a number through a couple levels of rand() in a fashion that crypto tends to liken to obfuscation of the ciphertext.

Here is a way to get something a little less biased....

Code: Select all

unsigned long genRandom(unsigned long minVal, unsigned long maxVal) {
    unsigned long blocks[5];
    unsigned long randValue;
    unsigned long moduloVal = maxVal - minVal;

    blocks[0] = rand(); blocks[1] = rand(); blocks[2] = rand(); 
    blocks[3] = rand(); blocks[4] = rand();
 
    randValue = rand();
    for&#40; i = 0; i < 4; i++ &#41; 
    &#123;
        randValue ^= blocks&#91;i&#93;;
        randValue *= blocks&#91;i+1&#93;;
        randValue ^= blocks&#91;i&#93;;
    &#125;
    randValue ^= blocks&#91;4&#93;;
    
    return &#40;randValue % moduloVal&#41; + minVal;
&#125;

It isn't the fastest, but you get a more uniform distrobution of values from munging the hell out of the bits. :)

[ector]

Krevnik, read cyod's post again. The bias comes DIRECTLY from the modulo.
Modulo is not some magic range restricting function. If you have an RNG giving you numbers 0-5 and use a modulo 4, you will get on average twice as many zeros and ones as twos and threes. The same problem scales upwards although becomes smaller and smaller as the size of your RNG output values increase.

It's amazing how many people don't understand this...

[Krevnik]

Yes, well, I was reading the wrong aspect. I am gonna nitpick though and state that your original comment was vague and didn't specify the zero problem, and I completely forgot (been awhile since I mucked with RNGs) about that particular nastiness. Otherwise, any bias is from the RNG, and further munging will help that to an extent. Also, my post was written after you posted that comment, but not the discussion that followed, so my post got slapped onto the page before I had a chance to get the clarification.

However, here is an integer version of the previous solution:

Code: Select all

value = (((rand() >> 1) + 1) % range) + minValue;

This line will remove the bias, but it does reduce the effectiveness of the RNG by one bit (31 bits of randomness, rather than a full 32).

[Shine]

A more correct way is rand() * yourRange / RAND_MAX.

This doesn't help. For example if RAND_MAX is 2 and you want 0 or 1, then it looks like this:

rand(), rand()*1/2:
0, 0
1, 0
2, 1

So you'll get twice as often 0 than 1. The only difference is, that your solution uses the higher-order bits (if not overflowed) and "%" uses the lower-order bits, so it might be better, because in some algorithms the lower-order bits are not as much random as the higher-order bits.

But if you have a RAND_MAX of 2147483647 and all bits are random, then the error for small numbers is very low, as cyod explained.

[ector]

You still don't get it. Read my above post again. It has nothing to do with zero. The problem is that modulo is not generally an exact n->1 mapping with the same n for each input number. In my example with a rand function that gives output 0-5 and use modulo 4, 0 and 4 will map to 0, 1 and 5 will map to 1, only 2 will map to 2 and 3 to 3. Therefore, the chances of getting a zero or a one is greater than getting a 2 or a 3.

If you still don't understand the problem, read this post again. And yes the problem shrinks quickly with RAND_MAX but it's always there unless RAND_MAX is an exact multiple of your max value.

[Shine]

However, here is an integer version of the previous solution:

Code: Select all

value = (((rand() >> 1) + 1) % range) + minValue;

This line will remove the bias, but it does reduce the effectiveness of the RNG by one bit (31 bits of randomness, rather than a full 32).

It doesn't remove the bias, for example for RAND_MAX=4, range=2 and minValue=0:

rand(), (((rand() >> 1) + 1) % range) + minValue
0, 1
1, 1
2, 0
3, 0
4, 1

so you have three times "1" and two times "0".

[cwbowron]

i was wondering if you could help me with some code like the snake game uses, based off the clock:

srand(time(NULL)) should seed with the current time, then you can use rand() to get a pseudorandom number.

[ector]

In other news to some people here, the standard C rand() returns a number from 0 to 32767, not the full 32 bits. That's another thing to be aware of.

[Krevnik]

However, here is an integer version of the previous solution:

Code: Select all

value = (((rand() >> 1) + 1) % range) + minValue;

This line will remove the bias, but it does reduce the effectiveness of the RNG by one bit (31 bits of randomness, rather than a full 32).

It doesn't remove the bias, for example for RAND_MAX=4, range=2 and minValue=0:

rand(), (((rand() >> 1) + 1) % range) + minValue
0, 1
1, 1
2, 0
3, 0
4, 1

so you have three times "1" and two times "0".

IIRC, a RAND_MAX of 4 gives values of 0-3, not 0-4. Still, you are right I don't remove the bias. However, I just realized something as well: In the case of an even number of output values desired, with an odd number of output values from the RNG, you cannot remove the bias (in integer math). Which means my solution is wrong, as well as Ector's.

A real solution to /minimize/ bias is to convert the output of rand() into a floating point value of [0.0f,1.0f). Do all math in floating point, and convert to integer at the last possible point. The only solution to do this in integer only math is to create your own RNG designed specifically for the cases you use it in to minimize bias. This thread has been fun though, as it got my brain working again, and made me remember why we call them psudeo random number generators. :)

And just to be bitter and get back at Ector for no real reason...

Ector's solution:

Code: Select all

rand() * yourRange / RAND_MAX

...is no better in this corner case, if your desired result is an integer (Assuming a 'fixed' RAND_MAX of 5):
0, 0
1, 0
2, 0
3, 1
4, 1

So there. (apply sarcasm and joking tone liberally, bake until golden brown) :)

[ector]

Not even converting to floating point will solve that since you still only have 5 outputs from the rand() :)

[cyod]

You would need to set a check to see if its above a certain value and choose a new rand() until its below the value... so like

Code: Select all

rand()     newRand (rand%2)
0              0
1              1
2              0
3              1
4              -choose a new random-

Thats the only thing I can think of when your rand() gives results in that manner. Once again this is all fairly academic for the usual usage of rand()

[Redbluefire]

Thanks to all of you, especially cwbowron and cyberbill, i got it working and it can be found here: http://www.uploadhut.com/upload/242248.zip??

the code used is:

Code: Select all

int Rando(int min, int max)
             {   
              srand(sceKernelLibcTime(NULL));
              int Diff = max - min;
              return (rand() % Diff)+min;
             }

And dont worry, Rando() is only called once, so srand() is only called once :)

[jason867]

I don't know if this would help, but I was making a rand function for use in GBA programming. And a friend who helped me recommended using the Mercenne Twister code.

My original code used a timer and some random calculations to make random numbers, and it seemed random enough. But I used it in a random pixel generator, which randomly placed randomly colored pixels on the screen, and you could tell it was biased because of areas of the screen having a general color to them.

Then I implemented the Mercenne Twister code and it was perfect. There were no patterns anywhere to speak of.

Just do a google search for Mercenne Twister Random integer generator, or something similiar, and you should find the code. I'm pretty sure it's free for public use.

[Krevnik]

Not even converting to floating point will solve that since you still only have 5 outputs from the rand() :)

Well, I was pointing out that if you kept the floating point for your calcs AFTER the rand generation, and only moved to integer at the very end of your series of calcs (which include what you are feeding the random value into), then you can /minimize/ bias, as your calculations will be more complex and start to swallow up some of the bias in the process... but yeah, hard to remove.

Although I do say the post above mine is a definite good piece of advice. :)

[TyRaNiD]

For info, there is a mersenne twister (19937 variant) built into the psp's firmware, check out psputils.h for the function information (sceKernelUtilsMt19937Init and sceKernelUtilsMt19937UInt).