for (unsigned int i = 0; i < 100; i++)
{
srand(i);
unsigned int x = rand() % 100;
display(x);
}
You will get this serie: 62, 72, 85, 95, 5, 14, 28, 37, 47, 60, 70, 80, 90, ... Which is obviously not random, as it's always increasing & wrapping. Any help greatly appreciated.. Y.
🔒 Locked
random function, again
Advertisement
Original Post
I'm looking for a random function, which has a number of properties: 1. Light cost. Results must look random enough, but not perfect either. Like the stdlib's rand() function. No loop involved in the implementation. Cost similar to rand(). 2. Does not use a global seed / variable. Lookup tables are ok if they're not too large. I need a "random" function that looks like r = f(x) with x being an integer argument. Giving the same value to x results in the same pseudo random value r returned. 3. No immediately visible relationship between f(x) and f(x + n) (that one is more tricky). In particular, the stdlib's rand() function does not pass the third condition. If you do:
Check out www.random.org. I believe they might have something. :)
Boost Random Number Library for all your random number needs.
Quote:
Original post by Lantz
You're not supposed to reseed on every use of rand. Try seeding once and you'll get totally different results.
Edit: Ah, I see, no global seed. Then rand isn't what you're looking for.
Exactly. And that's why i have no faith on boost or random.org. After a quick glance, they are made for random number generators (ie. you seed once, then you get a serie of random numbers), and i'm looking for a pseudo-random FUNCTION (ie. r = f(x) where "x" can be seen as the "seed").
Y.
I've had pretty good success with a Multiply-With-Carry Generator. Not much info on it, but I found it here (search for section q210.5.).
Here's a simple class based off of that (using a couple Win32 time calls for seeding, and VC++ style int types; alter accordingly):
Here's a simple class based off of that (using a couple Win32 time calls for seeding, and VC++ style int types; alter accordingly):
class c_RandomSequence{ public: c_RandomSequence(unsigned __int64 Seed = 0) { if (Seed == 0) { GetSystemTimeAsFileTime((FILETIME*)mNumber64); QueryPerformanceCounter((LARGE_INTEGER*)mConstant); mNumber64 ^= mConstant; } else { mNumber64 = Seed; } //Random crap to get a number 0-9 out of mNumber64 //Any of the following numbers will work well for mConstant //Try to make sure that both mConstant * 2^32 - 1 and // (mConstant * 2^32 - 2) / 2 are prime switch (((mNumber64) ^ (mNumber64 >> 4) ^ (mNumber64 >> 8)) % 10) { case 0: mConstant = 1075433238; break; case 1: mConstant = 1447497129; break; case 2: mConstant = 1517746329; break; case 3: mConstant = 1557985959; break; case 4: mConstant = 1606218150; break; case 5: mConstant = 1655692410; break; case 6: mConstant = 1781943330; break; case 7: mConstant = 1893513180; break; case 8: mConstant = 1967773755; break; case 9: mConstant = 2051013963; break; } } unsigned __int32 Random() { mNumber64 = mConstant * mNumber32 + mCarry32; return mNumber32; } private: union { struct { unsigned __int32 mNumber32; unsigned __int32 mCarry32; }; unsigned __int64 mNumber64; }; unsigned __int64 mConstant;};Quote:
Original post by Agony
I've had pretty good success with a Multiply-With-Carry Generator. Not much info on it, but I found it here (search for section q210.5.).
Here's a simple class based off of that (using a couple Win32 time calls for seeding, and VC++ style int types; alter accordingly):
*** Source Snippet Removed ***
That's some kind of reversed Multiple-With-Carry. Your base is a 32bit number(x) and you give two numbers(a, c) and perform:
res = a * x + c;
I'm not saying it's wrong, it's just that your c parameter will usually be zero for 32bit input. Using a constant for c could be more "useful".
That aside, the implementation of c_RandomSequence is quite complex, I'd say so complex, that it's hard to analize it's stability.
Why not simply use:
res = (a * x + c) % n;
Where a, c are proper constants and x is the input, n is the range?
Cheers.
/def
I'd probably make a function with several linear congruential generators(practically 0 cost since they take a single multiply and add in the simplified case - essentially what the code Agony posted does) all generating from the input number (so you'll get several individual numbers) and then put the numbers together in a buffer and finally do a hash of some knid (CRC32, MD5, SHA or something like that) on the buffer and use XOR to turn the hash result into a number of the proper size (ie MD5 returns 16 bytes IIRC and you'd want 4 for a 32-bit number so you'd do 4 XORs).
No idea how well that'd work, but it sounds easy to test out.
No idea how well that'd work, but it sounds easy to test out.
Quote:
Original post by Ysaneya
I'm looking for a random function, which has a number of properties:
[...]
3. No immediately visible relationship between f(x) and f(x + n) (that one is more tricky).
Could it be that you also require that for f(x) and f^n(x)?
In generating
That, however, could be done with linear congruention. That's why it's often more reliable that other more complex machines.
Cheers.
/def
Quote:
Original post by Ysaneya
i'm looking for a pseudo-random FUNCTION (ie. r = f(x) where "x" can be seen as the "seed").
I see what you mean. It's similar to Perlin noise, where it is random but the same random every time. Perlin's method returns random numbers from 0..255, so if you need intergers like this, then you may want to try his method:
http://www.noisemachine.com/talk1/17.html
http://www.noisemachine.com/talk1/18.html
Linear congruential pseudo-random number generator I recently wrote for a class:
Some minor implementation details are redundant for general use though necessary for the assignment specifications. This is similar to the standard rand function, but it stores an internal seed rather than relying on a global one; don't know if that cuts it for you.
class uniform{ mutable unsigned x; // current seed value unsigned a; // coefficient unsigned b; // increment unsigned m; // basepublic: // Initialise the generator with seed x0 and parameters a, b, m as above // Note: 0x7FFFFFFE = 2^31 - 1 uniform(unsigned x0=12345U, unsigned a=1103515245U, unsigned b=12345U, unsigned m=0x7FFFFFFEU); // Return a random number. Note that the internal seed changes even in a // const object (else the generator is quite useless). unsigned operator()() const; // Random number in [a, b) float operator()(float x0, float x1) const { return x0 + (static_cast<float>((*this)())/m * (x1-x0)); } // Set the seed to x0 and return a random number. A constant generator // cannot be reseeded. unsigned operator()(unsigned x0); unsigned max() const { return m; }};uniform::uniform(unsigned x0, unsigned a, unsigned b, unsigned m): x(x0), a(a), b(b), m(m){ ;}unsigned uniform::operator()() const{ return (x = (a*x + b) % m);}unsigned uniform::operator()(unsigned x0){ x = x0; return (*this)();}Some minor implementation details are redundant for general use though necessary for the assignment specifications. This is similar to the standard rand function, but it stores an internal seed rather than relying on a global one; don't know if that cuts it for you.
Has anyone ever thought of just using a Gold code or a JPL ranging code or something? They're designed to be maximal pseudo-noise generators...
Quote:
Exactly. And that's why i have no faith on boost or random.org. After a quick glance, they are made for random number generators (ie. you seed once, then you get a serie of random numbers), and i'm looking for a pseudo-random FUNCTION (ie. r = f(x) where "x" can be seen as the "seed").
You could just seed it with a fixed number at the start of the program.
Matthew:
The range of input values in Perlin noise is too low (actually in the slides you mentionned it says 0..255) and some patterns become visible. I need a function f(x) defined on the complete (positive) 32-bits integer range. If i had a small range i'd rather compute a noise lookup table. In addition the smoothing of Perlin noise is totally useless to me, as i want close values of x (like x and x+1) to give completely different noise values.
Miserable:
I'm afraid this will also have the same drawback than rand() (failing on point 3). It will generate a serie that is increasing & wrapping, although i'd have to test to be sure.
Deffer:
No i don't require that. As i said i'm not looking for a perfect number generator, it only has to be good enough.
Basically if i feed a serie of numbers in range [x;x+n] in a loop, i want all the returned values to look random and independant of each other. That's all.
Spoonbender:
I need the returned value to be exclusively dependant on the input value. Seeding at the start of the program gives you a random serie of numbers (as long as you don't change the seed). Again, i'm looking for a random *function*. Not a serie.
AP:
There is a strong relationship between similar input values of Perlin noise. Ie. f(x) ~ f(x+n) when n is small. In addition my input argument has to be integer.
I'm going to do it differently:
Coding challenge.
Here is a test program:
Assuming rangeMax > rangeMin, can you define the function MyRandom that will display on the screen a list of numbers that look pseudo-random ? (no increasing serie, no wrapping, no pattern).
Y.
The range of input values in Perlin noise is too low (actually in the slides you mentionned it says 0..255) and some patterns become visible. I need a function f(x) defined on the complete (positive) 32-bits integer range. If i had a small range i'd rather compute a noise lookup table. In addition the smoothing of Perlin noise is totally useless to me, as i want close values of x (like x and x+1) to give completely different noise values.
Miserable:
I'm afraid this will also have the same drawback than rand() (failing on point 3). It will generate a serie that is increasing & wrapping, although i'd have to test to be sure.
Deffer:
No i don't require that. As i said i'm not looking for a perfect number generator, it only has to be good enough.
Basically if i feed a serie of numbers in range [x;x+n] in a loop, i want all the returned values to look random and independant of each other. That's all.
Spoonbender:
I need the returned value to be exclusively dependant on the input value. Seeding at the start of the program gives you a random serie of numbers (as long as you don't change the seed). Again, i'm looking for a random *function*. Not a serie.
AP:
There is a strong relationship between similar input values of Perlin noise. Ie. f(x) ~ f(x+n) when n is small. In addition my input argument has to be integer.
I'm going to do it differently:
Coding challenge.
Here is a test program:
int rangeMin = GetUserInput();int rangeMax = GetUserInput();for (int x = rangeMin; x <= rangeMax; x++){ int result = MyRandom(x); printf("f(%d) = %d\n", x, result);}Assuming rangeMax > rangeMin, can you define the function MyRandom that will display on the screen a list of numbers that look pseudo-random ? (no increasing serie, no wrapping, no pattern).
Y.
I havn't thought this through completly, but with work this might provide what your after: (As evil as the code itself is.)
unsigned int Func(unsigned int in)
{
float ret = sin(&((float*)((void*)∈)));
return &((int*)((void*)&ret));
}
It does partially fail your requirements in that its not consistant between computers if they have different fpu's, so it won't work for consistancy in a networked computer game. It also fails in that the lower bits (i.e. the mantisa) will allways be the same due to the output range of sin. But different fpu operators (You have to be careful incase you give it a bit pattern that maps to 0, infinity or NAN - could throw an exception. infinity or nan will kill the code above unless you add traps.) some shifting and bit wise operators could provide what your after. (i.e. set some bits to make sure its never nan, 0 or infinity, do several different operations, then combine the bits via xor after some shifting so all bits can change arbitarilly.)
Probably too complicated to concider, but concidering nothing so far has been good enough you might find this idea useful!
lethe
unsigned int Func(unsigned int in)
{
float ret = sin(&((float*)((void*)∈)));
return &((int*)((void*)&ret));
}
It does partially fail your requirements in that its not consistant between computers if they have different fpu's, so it won't work for consistancy in a networked computer game. It also fails in that the lower bits (i.e. the mantisa) will allways be the same due to the output range of sin. But different fpu operators (You have to be careful incase you give it a bit pattern that maps to 0, infinity or NAN - could throw an exception. infinity or nan will kill the code above unless you add traps.) some shifting and bit wise operators could provide what your after. (i.e. set some bits to make sure its never nan, 0 or infinity, do several different operations, then combine the bits via xor after some shifting so all bits can change arbitarilly.)
Probably too complicated to concider, but concidering nothing so far has been good enough you might find this idea useful!
lethe
const unsigned long PRNF(const unsigned long p_Seed){ const unsigned long Num1 = (p_Seed * 0xFEA09B9DLU) + 1; const unsigned long Num2 = ((p_Seed * 0xB89C8895LU) + 1) >> 16; return Num1 ^ Num2;}If that isn't random enough for you, you can change the large constants and add more terms (ie Num2=...>>8, Num3=...>>16, Num4=...>>24). The constants are created by choosing a random number (however you want, bang some keys or something), multiply by 4, then add 1, but make sure the constant is relatively large (ie 7 or 8 hex digits long). Note that each Num*'s lower bits are less random, so using two numbers gives some more randomness to the lower bits, and using 4 evenly spaced would give even more randomness.
Using 2 numbers is about as fast as Visual Studio .Net 2002's rand(), and using 4 numbers comes out to about 2.5 times slower. You need to use at least 2 numbers, or the lower bits won't be random at all.
[Edited by - Extrarius on February 2, 2005 8:55:55 PM]
Extrarius: many thanks - i've been testing your solution and that's pretty much exactly what i was looking for. I generated one million numbers and the distribution looked "good enough", similar to what i get with rand(). Using 4 constants instead of 2 didn't seem to help.
Y.
Y.
Ok, so here's exactly what I'm using. For, I suppose, similar purpose as you(OP):
I often use it with nCount=2 or 3, so even for small numbers it gives "unpredictible" results.
All the bits are "meaningful".
/def
EDIT: Out of topic:
How do you put c++ code in your post, 'cause I' blinfd or stupid or whathever, so I didn't make it out yet ????
EDIT2: Yup, I just made it! Thank you very much, because I was really stupid not looking at the FAQ...
[Edited by - deffer on February 3, 2005 8:25:07 AM]
#define INT_BITS (sizeof(int)*8)#define INEG_MASK(x) (x >> (INT_BITS-1))#define Ran_MM 2147483647 // Mersenne's prime number#define Ran_AA 48217 // good at spectral test#define Ran_QQ 44488 // Ran_MM / Ran_AA#define Ran_QQ 3399 // Ran_MM % Ran_AAtemplate<int nCount>int randomLinear(int x){ // Most of the time all this checkings are obsolete, // cause we're passing quite small numbers as inputs, but for completeness sake... // On the other hand we are passing FtoDW(f) somethimes and those can be mess. // Cut negatives to positives. This results in distortion of negative numbers // construction, but we shouldn't care. // But if you do care, use the first sentence. /* x = ABS_INT(x); */ x &= 0x7FffFFff; // There is only small amount of space to fall out of range, so shr(x, 1) is sufficient. // Only that we would want to save last bit, so r(x) and r(x+1) wouldn't be the same, // so we're clearing the most significant bit instead. if ( x >= Ran_MM ) x &= 0x3FffFFff; // Hope compiler would expand this for nCount = 1,2 or 3. for (int i=0; i<nCount; i++) { // IOW this is x = (x * Ran_AA) % Ran_MM, but that way we avoid overflow ;) x = Ran_AA * (x % Ran_QQ) - Ran_RR * (x / Ran_QQ); // Negative x gives us INEG_MASK(x)=0xFFffFFff. /* if (x < 0) x += Ran_MM; */ x += Ran_MM & INEG_MASK(x); }; return x;}I often use it with nCount=2 or 3, so even for small numbers it gives "unpredictible" results.
All the bits are "meaningful".
/def
EDIT: Out of topic:
How do you put c++ code in your post, 'cause I' blinfd or stupid or whathever, so I didn't make it out yet ????
EDIT2: Yup, I just made it! Thank you very much, because I was really stupid not looking at the FAQ...
[Edited by - deffer on February 3, 2005 8:25:07 AM]
Quote:
Original post by deffer
)ut of topic:
How do you put c++ code in your post, 'cause I' blinfd or stupid or whathever, so I didn't make it out yet ????
Making up for my totally not-relevant post above, use [source][/source] tags, instead of [code] tags. I think you can even lang="cpp" to the opening tag, although cpp is the default anyway. (Check out the FAQ for more information.)
[edit]
Quote:Yarg! I was making up for my stupid post! How dare you steal that opportunity from me. [wink]
Original post by moagstar
Check out the faq at the top right of the forums section, it's difficult to show you in a forum post
[/edit]
[edit]
Yarg! on the forum replacing my [ with the literal '[' in the edit box and turning my tag examples into the actual tags.
[/edit]
Topic Locked
This topic has been locked by a moderator. New replies are not allowed.
Sign in to reply to this topic.
Advertisement