Sender: crough45 AT amc DOT de Message-Id: <97Jul15.191611gmt+0100.16648@internet01.amc.de> Date: Tue, 15 Jul 1997 18:20:21 +0100 From: Chris Croughton Mime-Version: 1.0 To: scochran AT shoalsnet DOT com Cc: djgpp AT delorie DOT com Subject: Re: Fast random number generator Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Precedence: bulk scochran AT shoalsnet DOT com wrote: >Alan Poppleton wrote in article ><33C91424 DOT 7615 AT wanadoo DOT fr>... >> I need a fast and simple algorithm which can produce a fairly random >> number given two seeds - x and y. Any ideas? It MUST be SIMPLE and >> FAST and it only needs to return a number between 0 and 15. > >okay.. Why don't you use standard C. It might be faster to use like chaos >or list of random numbers. I haven't looked into it but this should work >good for most applications. and then went on to suggest: >void randomxy(int &x, int &y) >{ > int r = random(225); > x = r / 15; > y = r % 15; >} For a start, using 'references' like that is NOT standard C. It's C++ only. Secondly, the function does not take "two seeds" and return "a number", it has a random seed (time(NULL) in the example) and returns two numbers. Thirdly, it does not return numbers "between 0 and 15", it returns numbers from 0 to 14 inclusive (admittedly the term 'between' is ambiguous - I suspect that the original question was asking for numbers from 0 to 15 inclusive, but it could also mean from 1 to 14 inclusive). Fourthly, there is no "standard C" function 'random(n)' which returns a value between 0 and n-1 inclusive (I believe Borland C does have such a function). However, the original question wasn't very clear either. Why two seeds? What are they expected to do? Do the seed values change during a 'run' or are they fixed for one sequence? If you're not too bothered about 'good' randomness, something like the following could work: static unsigned int sh, tot, mult, inc; void initmyrandom(int x, int y) { sh = x % 8 + 4; tot = x/8 + y; mult = y*2 + 31; inc = x%255 * y%255; } int myrandom(void) { tot = (tot * mult + inc) ^ (tot >> sh); return tot % 16; } The first function uses the seeds to generate a shift factor (4 to 12), a start total, a multiplier and an increment. The actual random number function does a standard "multiply by something odd and add something else", but it also exclusive-ors in some of the top bits to make it not just alternate between odd and even. It then returns the number modulo 16 to give a number from 0 to 15 inclusive. Because the shift, multiplier and increment are determined by the seed it will change its characteristics depending on the seed... As examples with different seeds (note that at least one of the seeds should be non-zero): > a.out 0 1 2 1 4 9 14 9 11 6 3 5 10 10 12 5 10 3 14 6 0 0 14 14 1 15 6 15 15 4 0 14 4 9 11 2 12 7 8 1 10 6 10 4 1 14 4 3 2 0 4 5 12 5 13 15 15 11 1 1 7 2 9 15 11 14 15 9 14 0 11 14 8 15 9 2 6 13 12 12 6 15 4 12 6 15 12 6 8 10 7 10 6 3 5 14 12 15 0 11 2 13 10 0 1 15 10 7 9 3 13 9 9 7 3 0 0 12 4 10 9 8 12 2 3 3 5 12 13 4 > a.out 0 2 7 2 12 9 1 15 11 15 0 1 7 4 8 5 12 1 10 15 13 2 4 8 3 2 15 4 0 5 2 5 0 11 0 1 3 14 4 10 7 4 0 10 11 14 1 4 12 4 0 0 8 10 3 12 12 12 14 6 6 10 13 15 13 8 9 2 3 14 4 4 4 8 11 1 3 3 5 10 3 14 12 11 12 4 7 10 14 5 0 9 0 2 2 5 4 12 1 13 3 7 2 3 5 0 13 11 4 3 4 15 9 10 12 0 2 12 8 4 3 6 5 4 6 3 5 10 6 6 > a.out 1 0 1 0 0 14 2 13 8 10 15 6 3 4 10 15 5 5 2 10 0 3 3 4 4 6 6 6 11 5 3 10 12 6 6 12 9 0 13 10 6 9 5 12 2 6 13 11 0 12 0 0 5 2 2 9 7 2 0 12 11 7 10 9 1 7 3 5 12 14 13 3 10 8 0 5 8 2 7 12 8 0 8 11 12 2 13 6 13 8 14 5 2 8 13 7 13 1 10 2 1 7 14 4 5 1 10 11 2 15 3 13 4 1 4 12 0 0 3 10 6 12 1 9 5 8 5 11 7 4 You can play about with the initialisation - as it is it doesn't start up very well if either of the seeds is close to zero. The results are evenly distributed, but I haven't run any other statistical tests on it... Chris