Seeding rand with a specific value is supposed to ensure that every time you call rand(), you get the same sequence. I don't know if this is actually true, once you start taking other people's hardware into account.
Let's say I write a program, and compile it, and give you the .exe. You and I both run it. Are we guaranteed to get the same sequence of numbers? That's the basis for this question:
Take a series of N bits. Make a square out of it. Let's say we have 8192 bytes, for unsigned short number of bits. It looks like this:It doesn't matter what we fill it in with. Just fill it with stuff, that way it's the same for everyone. It's static, constant, and we never change it. Everyone has this same block of bits.Code:unsigned char bits[ 256 ][ 32 ] = { ...all of our bits... };
Now we all start at the same point, doesn't matter where. Let's say we 'seed' with 12345. First, we find the 12345th bit. Do a bit of math, that should put us oh let's say:
12345 / 256 = 48
256 * 48 = 12288
12345 - 12288 = 57
57 / 8 = 7
8*7 = 56
57 - 56 = 1
So what's that give us? 1st bit, in the 7th byte in the 48th row? Good enough. So that's where we start. At that point, we take 2 bits:
01 /* 00 north, 01 east, 10 south, 11 west */
Doesn't matter what it is. That tells us we need to go. We are in fact taking the integer you want from the bits to the east of where we are. You wanted an integer, so we take the next 32 bits for you. We copy them off into your return value, and there's your rand. We save where we are for the next call to rand.
The next call picks the first 2 bits from where we left off, to see where to go next. Doesn't matter what it is, that's what we use. It also takes the 2 bits after that, to skip that direction that many bits. I could make that number be the number of bytes we skip, the number of rows, whatever. Doesn't matter, as long as it is consistent. Then I give you your number, and repeat this process for every rand call.
My question is this: Given consecutive calls to rand, how likely am I to encounter running into the same loop, or short series of numbers? Like this:
rand 0 = go 2 the east, pop out your number
rand 1 = go north, pop out your number
rand 2 = go west, ...
rand 3 = go south
Damnit, I'm in aloop now. I will always get the same four consecutive numbers!
Now it doesn't have to be an immediate loop of four. I'm just wondering if I do the above, how likely am I to get stuck in a pattern, and how likely is it to be a small noticeable pattern? I could fiddle with those numbers a bit. I don't need to use 2 bits. I could 11 or 17 or whatever to tell me where to skip.
Say I just call rand in a loop, plotting x/y on a graph. With a small set of bits (65k~), how likely am I to encounter a repeating loop?
Quzah.