Pseudo-Random Number Generation

[high G]

Take the number above, and:
1. Square it
2. then find its modulus 377 (i.e. x² mod 377)

note: >modulo operation<
----------

100

[kaboom!]

100² mod 377 =

198.

[John Napier 698]

3. Use the result of n² / 337 as the next n.

example:

unsigned int n = 100;

unsigned int rand( void )
{
unsigned int result;

result = n * n % 377;
n = n * n / 377;

return result;
}

[John Napier 698]

198² mod 377 = 373

[The Sideromancer]

373^2 %377=16

[John Napier 698]

16^2%377 = 256

[John Napier 698]

256^2 = 65536 = 1
1%377 = 1

[The Sideromancer]

1^2=1
1%377=1
I think we broke it.

[John Napier 698]

Okay, let's try this. We keep n^2%377 to determine the random number, but we use the result of n^2/377 as the next n to apply to the next iteration.

Shall we begin?

100 ^ 2 % 377 = 198
next n = 100 ^ 2 / 377 = 26

[CrystalSeas]

Today is Avogado's Number Day at either 6.02 am or pm

6.02 x 10 to the 23rd

Why not start with that

[thejeff]

This is why actual random number generators are more complex. :)

198 ^ 2 % 377 = 373
26 ^2 / 377 = 1

I think that's actually guaranteed to quickly converge to 1. Since n always smaller than 377, when you divide by 377, the result will always be smaller than your previous n.

The first approach is better, but it's still limited. At best it repeats in less than 377 iterations. Assuming it doesn't hit a break point.

Which, by the way, it didn't:
256^2 = 65536 = 1 - we're dealing with math here, not computers and certainly not 16 bit integers. 32 bit is sufficient, since the biggest we'd need it 376^2.

So we're still at:
256^2 = 65536 % 377 = 315

315^2 % 377 = 74

[John Napier 698]

C implements random numbers like this:

static unsigned long int next = 1;

int rand(void) // RAND_MAX assumed to be 32767
{
next = next * 1103515245 + 12345;
return (unsigned int)(next/65536) % 32768;
}

void srand(unsigned int seed)
{
next = seed;
}