Re: Random number generator
Re: Random number generator
- Subject: Re: Random number generator
- From: Mike Morton <email@hidden>
- Date: Tue, 9 Aug 2005 08:55:40 -0700
James DiPalma wrote:
A suggestion: fill an NSMutable array or an NSMutableIndexSet with a
set of unique values that will be randomly selected (or randomly
ordered which seems like our ultimate goal). During each cycle
randomly choose one of these values and remove it from this set. By
maintaining a set of unchosen unique values, each cycle will always
use one call to srandomdev() or similar to generate an unchosen unique
value. Your code has no need to validate this unique value since it
was pre-validated by being in your unchosen set.
You can generate pseudorandom integers 1 .. (2^n)-1 very quickly with a
software equivalent of a linear feedback shift register
<http://en.wikipedia.org/wiki/Linear_feedback_shift_register>
The code is something like:
/* CAUTION: not tested, not even compiled */
unsigned int element = 1;
do
{
printf ("%d", element);
// shift off the rightmost bit
if ((element & 1) != 0)
element = (element >> 1) ^ MAGIC;
else
element = (element >> 1);
} while (element != 1); // until we repeat
The value of the constant MAGIC determines how high the sequence goes.
You'll want to pick a value which goes up to some (2^n)-1 larger than
you need, then skip iterations whose value is more than your real upper
limit.
For a 2-D sequence generator derived from this 1-D sequence, and one
set of magic constants (search for seqMasks in second link), see these
ancient articles.
http://www.mactech.com/articles/mactech/Vol.01/01.13/
DissBitsSubroutine/index.html
http://www.mactech.com/articles/mactech/Vol.06/06.12/SafeDissolve/
index.html
-- Mike
_______________________________________________
Do not post admin requests to the list. They will be ignored.
Cocoa-dev mailing list (email@hidden)
Help/Unsubscribe/Update your Subscription:
This email sent to email@hidden