🔒 Locked

linear congruential algorithm

Started by Xolution Jun 14, 2002 at 4:09 PM 7 replies 450+ views

Original Post

Jun 14, 2002 at 4:09 PM

I''m a little bit confused about this. This is what I''ve been doing.

    
int getRandom(int m) {
   static int x = time(0);
   int a = 2;
   int b = 3;
   x = (a * x + b) % m;
   return x;
}

If you say getRandom(5), you always get numbers 0 <= y < 5, but they repeat themselves in a really small pattern, like 0 3 4 1 0 3 4 1 0 3 4 1... How can I make this pattern larger?

Stoffel

Jun 14, 2002 at 4:29 PM

x is modulated by m, so if you always reset it using x % m, x will always be less than m.

You might try this instead (though I''m not really sure what you''re trying to do):

  
int getRandom(int m) {
   static int x = time(0);
   int a = 2; // why not static const?

   int b = 3; // ditto?

   x = (a * x + b); // no % m

   return x % m; // % m is here

}

BTW, if this is truly a method to get a random variable, it will be much less random and slower than rand () on MSVC (and possibly gcc, though I don''t know for sure).

Xolution

Jun 14, 2002 at 4:36 PM

well, if i do %m at the return instead of the x assignment, i wind up getting some negative values. I know it''s probably slower than using rand(), but I''m just fooling around (curious about how computers generate pseudo-random numbers). I also get negative numbers if i make a and b larger numbers (only tried very small numbers and fairly large numbers (tens of thousands), don''t know how high they''ll go before they start getting negative).

From my understanding linear congruential generators take the seed, create a random number, and then use the newly generated number as the seed for the next pass through the function. Maybe if someone could go into some more detail on linear congruential generators I''d understand better.

Thunder_Hawk

Jun 14, 2002 at 4:53 PM

Ok, I used your code using rand() in place of time(0) and I got the same result you described. Removing the static keyword fixed my version but with yours I would suggest adding some sort of reference to x when assigning x (i.e. adding it or multiplying it to time(0) or [please don''t do this] moding it). However this may cause a problem on the first time through. Hope this helps a bit

_____________________________

And the Phoenix shall rise from the ashes...

--Thunder_Hawk -- ¦þ
______________________________

Thunder_Hawk

Jun 14, 2002 at 5:02 PM

I think this is right...
You are getting negative values because your numbers go beyond the range of accuracy. Try using long instead or using the unsigned keyword. I remember having the same sort of problem in a simple even/odd program where I ended up getting huge numbers and negative numbers as a result of a "% 2" operation. Very weird...You probably won''t need such high numbers anyways.

_____________________________

And the Phoenix shall rise from the ashes...

--Thunder_Hawk -- ¦þ
______________________________

Thunder_Hawk

Jun 14, 2002 at 5:06 PM

I''m just post happy here...
I think the usual rand() function uses a lot of bit-wise operations, but I''m not really sure.

_____________________________

And the Phoenix shall rise from the ashes...

--Thunder_Hawk -- ¦þ
______________________________

Stoffel

Jun 14, 2002 at 6:43 PM

Source ships with most compilers. Here''s the single-threaded version of MSVC 7''s rand:

  
static long holdrand = 1L;
int __cdecl rand (
        void
        )
{
        return(((holdrand = holdrand * 214013L + 2531011L) >> 16) & 0x7fff);
}

Xolution

Jun 14, 2002 at 7:16 PM

I got this to work, but i''m not quite sure why it works...

  
static unsigned long seed = time(0);

long lgc(long s) {
  seed = 1999839 * seed + 2990079;
  return (seed / s % s);
}

Somewhere between 100,000 and 1,000,000 the numbers (while I assume are still pseudorandom) begin to get smaller.

If you put a very large number like 10,000,000,000 in, you get very small output (under ten!).

Thunder_Hawk

Jun 14, 2002 at 8:02 PM

Ok, short answer first...
Remove the "/s". You''ll notice this code suddenly looks a lot like your original code (1999839 = a and 2990079 = b). This works because your seed value is carried on to the next use of the function (thus causing a different seed value to be used each time you use the function).

When you divide by s when s is one huge honkin'' number you''re taking one huge number divided by another. When you do this you tend to get small numbers. Then when you took this small number modulus s (still a huge number) guess what happened... Ok, maybe that''s not the best way to perform explainations. Moding takes the first number divided by the second number and returns the remainder. As a result you do something like this: 8 / 1000000000000000000. What''s the remainder?...that''s right 1zillion doesn''t go into 8 so the remainder is 8. Sorry if that sounds harsh I just wanted to make sure it was easy to follow.

Hope that helps a bit

(maybe I should add this to my signature)

_____________________________

And the Phoenix shall rise from the ashes...

--Thunder_Hawk -- ¦þ
______________________________

Topic Locked

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