| View previous topic :: View next topic |
| Author |
Message |
Redbluefire
Joined: 04 Aug 2005
Posts: 3
|
 Posted: Thu Aug 04, 2005 6:12 am Post subject: Random Integer Generation |
 |
|
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 |
|
| Back to top |
|
 |
cwbowron
Joined: 06 May 2005
Posts: 76
Location: East Lansing, MI
|
| Posted: Thu Aug 04, 2005 6:40 am Post subject: Re: Random Integer Generation |
|
|
| Redbluefire wrote: | 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: | int get_random(int lo, int hi)
{
return (rand() % (hi-lo+1)) + lo
}
|
|
|
| Back to top |
|
|
Shine
Joined: 03 Dec 2004
Posts: 728
Location: Germany
|
| Posted: Thu Aug 04, 2005 6:49 am Post subject: Re: Random Integer Generation |
|
|
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: |
#include <cstdlib>
#include <ctime>
#include <iostream>
using namespace std;
class Random {
public:
Random(const int min, const int max) : m_min(min), m_max(max)
{
srand(clock());
}
int next() const
{
return (rand() % (m_max - m_min + 1)) + m_min;
}
private:
int m_min;
int m_max;
};
int main(int argc, char** argv)
{
Random random(1, 100);
for (int i = 0; i < 25; i++) cout << random.next() << endl;
return 0;
}
|
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: |
green = getColorNumber(0, 255, 0)
math.randomseed(os.time())
for y = 1,25 do
printText(10, y * 10, math.random(100), green)
end
flipScreen()
|
|
|
| Back to top |
|
|
patrickoneal
Joined: 02 Aug 2005
Posts: 3
|
| Posted: Thu Aug 04, 2005 6:57 am Post subject: |
|
|
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 |
|
| Back to top |
|
|
Agoln
Joined: 08 Jun 2005
Posts: 326
Location: Fort Wayne, IN
|
| Posted: Thu Aug 04, 2005 7:12 am Post subject: Re: Random Integer Generation |
|
|
| Shine wrote: |
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....
_________________
Lego of my Ago! |
|
| Back to top |
|
|
ector
Joined: 12 May 2005
Posts: 195
|
| Posted: Thu Aug 04, 2005 7:30 am Post subject: |
|
|
It's funny how noone ever seems to note that rand() % yourmaxvalue is biased toward lower values...
_________________
http://www.dtek.chalmers.se/~tronic/PSPTexTool.zip Free texture converter for PSP with source. More to come. |
|
| Back to top |
|
|
Shine
Joined: 03 Dec 2004
Posts: 728
Location: Germany
|
| Posted: Thu Aug 04, 2005 7:49 am Post subject: |
|
|
| ector wrote: | | 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: |
Random random(1, 100);
int c[101];
int i = 0;
for (i = 0; i <= 100; i++) c[i] = 0;
int max = 10000000;
for (i = 0; i < max; i++) c[random.next()]++;
for (i = 0; i <= 100; i++) cout << abs(max / 100 - c[i]) << 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. |
|
| Back to top |
|
|
patrickoneal
Joined: 02 Aug 2005
Posts: 3
|
| Posted: Thu Aug 04, 2005 7:49 am Post subject: |
|
|
Why is that, ector?
Patrick |
|
| Back to top |
|
|
cyod
Joined: 29 Apr 2005
Posts: 36
|
| Posted: Thu Aug 04, 2005 7:50 am Post subject: |
|
|
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: |
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.
Last edited by cyod on Thu Aug 04, 2005 8:09 am; edited 1 time in total |
|
| Back to top |
|
|
ector
Joined: 12 May 2005
Posts: 195
|
| Posted: Thu Aug 04, 2005 8:06 am Post subject: |
|
|
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.
_________________
http://www.dtek.chalmers.se/~tronic/PSPTexTool.zip Free texture converter for PSP with source. More to come. |
|
| Back to top |
|
|
Redbluefire
Joined: 04 Aug 2005
Posts: 3
|
| Posted: Thu Aug 04, 2005 8:07 am Post subject: |
|
|
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: |
int Rando(int min, int max)
{
int Diff = max - min;
return (rand() % Diff)+min;
}
|
this code from cwbowron always returns 34
| Code: |
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: |
void initSeeds()
{
seed1 = sceKernelLibcTime((void *) 0);
seed2 = sceKernelLibcTime((void *) 0);
}
unsigned int myRand()
{
seed1 = (seed1 + 46906481) ^ seed2;
seed2 = seed1 ^ ( ((seed2<<3) | (seed2 >> 29)) + 103995407);
return seed1 - seed2;
}
|
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 |
|
| Back to top |
|
|
Krevnik
Joined: 09 Mar 2005
Posts: 71
|
| Posted: Thu Aug 04, 2005 8:09 am Post subject: |
|
|
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: |
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( i = 0; i < 4; i++ )
{
randValue ^= blocks[i];
randValue *= blocks[i+1];
randValue ^= blocks[i];
}
randValue ^= blocks[4];
return (randValue % moduloVal) + minVal;
}
|
It isn't the fastest, but you get a more uniform distrobution of values from munging the hell out of the bits. :) |
|
| Back to top |
|
|
ector
Joined: 12 May 2005
Posts: 195
|
| Posted: Thu Aug 04, 2005 8:19 am Post subject: |
|
|
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...
_________________
http://www.dtek.chalmers.se/~tronic/PSPTexTool.zip Free texture converter for PSP with source. More to come. |
|
| Back to top |
|
|
Krevnik
Joined: 09 Mar 2005
Posts: 71
|
| Posted: Thu Aug 04, 2005 8:40 am Post subject: |
|
|
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: |
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). |
|
| Back to top |
|
|
Shine
Joined: 03 Dec 2004
Posts: 728
Location: Germany
|
| Posted: Thu Aug 04, 2005 8:51 am Post subject: |
|
|
| ector wrote: |
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. |
|
| Back to top |
|
|
ector
Joined: 12 May 2005
Posts: 195
|
| Posted: Thu Aug 04, 2005 8:52 am Post subject: |
|
|
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.
_________________
http://www.dtek.chalmers.se/~tronic/PSPTexTool.zip Free texture converter for PSP with source. More to come. |
|
| Back to top |
|
|
Shine
Joined: 03 Dec 2004
Posts: 728
Location: Germany
|
| Posted: Thu Aug 04, 2005 9:01 am Post subject: |
|
|
| Krevnik wrote: |
However, here is an integer version of the previous solution:
| Code: |
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". |
|
| Back to top |
|
|
cwbowron
Joined: 06 May 2005
Posts: 76
Location: East Lansing, MI
|
| Posted: Thu Aug 04, 2005 9:05 am Post subject: |
|
|
| Quote: |
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. |
|
| Back to top |
|
|
ector
Joined: 12 May 2005
Posts: 195
|
| Posted: Thu Aug 04, 2005 10:17 am Post subject: |
|
|
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.
_________________
http://www.dtek.chalmers.se/~tronic/PSPTexTool.zip Free texture converter for PSP with source. More to come. |
|
| Back to top |
|
|
Krevnik
Joined: 09 Mar 2005
Posts: 71
|
| Posted: Thu Aug 04, 2005 10:38 am Post subject: |
|
|
| Shine wrote: | | Krevnik wrote: |
However, here is an integer version of the previous solution:
| Code: |
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: |
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) :) |
|
| Back to top |
|
|
ector
Joined: 12 May 2005
Posts: 195
|
| Posted: Thu Aug 04, 2005 10:41 am Post subject: |
|
|
Not even converting to floating point will solve that since you still only have 5 outputs from the rand() :)
_________________
http://www.dtek.chalmers.se/~tronic/PSPTexTool.zip Free texture converter for PSP with source. More to come. |
|
| Back to top |
|
|
cyod
Joined: 29 Apr 2005
Posts: 36
|
| Posted: Thu Aug 04, 2005 1:07 pm Post subject: |
|
|
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: |
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() |
|
| Back to top |
|
|
Redbluefire
Joined: 04 Aug 2005
Posts: 3
|
| Posted: Fri Aug 05, 2005 3:28 am Post subject: |
|
|
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: | 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 :) |
|
| Back to top |
|
|
jason867
Joined: 24 Jul 2005
Posts: 78
|
| Posted: Fri Aug 05, 2005 2:19 pm Post subject: Mercenne Twister Random Integer Generator |
|
|
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.
_________________
Ask not for whom the bell tolls, it tolls for thee, besides, I'm playing my PSP, tee hee!
------------------------------------------------------
Visit my website for my PSP Homebrew! |
|
| Back to top |
|
|
Krevnik
Joined: 09 Mar 2005
Posts: 71
|
| Posted: Tue Aug 09, 2005 3:59 am Post subject: |
|
|
| ector wrote: | | 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. :) |
|
| Back to top |
|
|
TyRaNiD
Joined: 18 Jan 2004
Posts: 918
|
| Posted: Tue Aug 09, 2005 4:02 am Post subject: |
|
|
| 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). |
|
| Back to top |
|
|
|
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in to check your private messages
Log in
