Skip to main content
gamedev.net
🔒 Locked

random function, again

Started by Ysaneya Feb 2, 2005 at 6:30 AM 43 replies 6.8k views
Original Post
Ysaneya
Ysaneya
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:

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.
Spoonbender
Spoonbender
Check out www.random.org. I believe they might have something. :)
Lantz
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.
Ysaneya
Ysaneya
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.
Agony
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):
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;};
"We should have a great fewer disputes in the world if words were taken for what they are, the signs of our ideas nly, and not for things themselves." - John Locke o
deffer
deffer
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
Extrarius
Extrarius
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.
"Walk not the trodden path, for it has borne it's burden." -John, Flying Monk
deffer
deffer
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 of random numbers as f(x), f(f(x)), ... , f^n(x), most of the generators will fail in a small loop after some time. Unless you can really analize the stability of your generator, you could not say it passes this requiment.

That, however, could be done with linear congruention. That's why it's often more reliable that other more complex machines.

Cheers.
/def
Matthew Doucette
Matthew Doucette
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
Matthew Doucette, Xona Games
Miserable
Miserable
Linear congruential pseudo-random number generator I recently wrote for a class:

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.
python_regious
python_regious
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...
If at first you don't succeed, redefine success.
Spoonbender
Spoonbender
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.
Ysaneya
Ysaneya
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:
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.
Lethe
Lethe
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
Extrarius
Extrarius
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]
"Walk not the trodden path, for it has borne it's burden." -John, Flying Monk
Ysaneya
Ysaneya
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.
deffer
deffer
Ok, so here's exactly what I'm using. For, I suppose, similar purpose as you(OP):

#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]
moagstar
moagstar
Quote:


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 ????



Check out the faq at the top right of the forums section, it's difficult to show you in a forum post
Agony
Agony
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:
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
Yarg! I was making up for my stupid post! How dare you steal that opportunity from me. [wink]
[/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]
"We should have a great fewer disputes in the world if words were taken for what they are, the signs of our ideas nly, and not for things themselves." - John Locke o

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.

Sign in to reply to this topic.