George Marsaglia posted several relatively simple generators to the old newsgroups many, many years ago. They're decent generators, and simple to implement. Alternatively, the boost library offers up good choices for high-quality generators, including lagged Fibonacci and Mersenne Twister. Knuth, of course, as you posted in your edit is always a good authority on PRNGs.

For games in general, you are mostly going to be looking for speed, as opposed to high-quality. Especially in noise applications, where you are layering many layers of noise together, you want your PRNG hash to be a fast as possible while still providing decent output. The reference implementation of Perlin noise provides a hash algorithm that makes use of a look-up table to "fold" bytes together to get the lattice hash for each point. The benefit of a look up table in this manner is relatively fast performance. As well, for a noise implementation you want to avoid any generator that requires internal state. Mersenne Twister, for example, stores internal tables and is complicated to seed, thus making it unsuitable for noise generation.

The link in my signature goes to the sourceforge page for my personal noise library. It's still (perpetually) under construction. As well, I have written quite a few journal posts regarding noise generation, seamless noise, etc... a few of which were published in Game Developer Magazine last year.

I would recommend you read Knuth for a solid background on pseudorandom number generation from a theoretical perspective. There is no source better.

For simple noise generation in a game you certainly don't need cryptographic quality PRNGs. You want something fast with broad spectral characteristics and possibly a long sequence. A lagged Fibonacci generator with block rejection is probably the best time-space tradeoff. The classic linear congruential generator has very poor spectral characteristics and makes a poor choice for noise. The Mersenne Twister has excellent spectral characteristics at the expense of greatly increased computation and memory footprint.

If you're using C++, the standard library (<random> in the current standard, or <tr1/random> for ancient compilers) provides a really excellent selection of pseudorandom number generators and useful distribution adapters [disclaimer: I wrote an implementation that comes with a popular compiler]. Easy to use, well documented, and well tested.

Alright so it's faster to generate all of the random numbers at the start and then iterate through them one by one?
I'm not familiar with Hashes at all - I'll check my book and google for more info, of course.[/quote]
I suppose it would be faster in a sense but it's not practical, imagine you need trillions of random numbers for a very long-running simulation (this is not uncommon), you aren't gonna be able to precalculate them all at the beginning. And the performance gain is probably not worth the increased memory use.

So I could do this with two or three tables of different lengths and XOR the results and get a lot of randomness right?
And it would still be fast?
Or should I just create one really, really big table at the start?[/quote]
No you don't need to do this. You just call the PRNG each time you need a pseudorandom number, it will give you one quickly. Remember that while memory probably abounds on your laptops and desktops, embedded devices also need some form of pseudorandom number generator, and it probably can't afford kilobytes of memory. Pseudorandom theory has improved enough to let us generate a virtual infinity of very high quality pseudorandom numbers very efficiently on a computer in O(1) memory, we should use this to our advantage.

The basic idea is to start with an initial "seed" and mix/diffuse the state's bits around in a very unpredictable, nonrepeating (hopefully) way, and use that as the next random number. Then you start again with the new state, ad infinitum (or until the sequence starts repeating, anyway). There are other methods but this is pretty much the gold standard.

A fun exercise is to create your own PRNG with a small state (say, 32 bits) to facilitate analysis, and then run various tests on it (e.g. what it its period, etc...). You might be surprised! Then, modify some workings of the algorithm used and see how this modifies the results. It's quite fascinating.

EDIT: you can combine the outputs of two generators by XOR if you want but remember this will only result in a sequence that's as pseudorandom as the most pseudorandom of the two, and your speed is also halved, so in general it's best to just use a single, good pseudorandom number generator. There are exceptions, particularly in hardware (combining multiple shift registers, which are very fast, for instance), but these are special cases.

Would it typically be a bad idea to XOR x{n} with x{n-1} or x{n-2}? Then I won't need to generate more numbers but since they have something in common that's probably bad right?[/quote]
No because then you'd have the sequence:
x{n}
x{n - 1}
x{n - 2}
x{n - 3}
...

And:
x{n} xor x{n - 1}
x{n} xor x{n - 2}
x{n} xor x{n - 3}
...

These two sequences are clearly correlated because if you XOR one with the other, you always obtain the same number: x{n}. Such a characteristic means that the numbers you thought were pseudorandom actually exhibit nonrandom behaviour, which makes them unsuitable for use (they don't satisfy all properties of random numbers so using them in a simulation or something would completely flaw it, as the correctness of the simulation relies on the numbers being random).

Here is a simple example of a very simple pseudorandom number generator (an algorithm). It takes as an input two bytes A and B and outputs two bytes A2 and B2 (and you can iterate it to generate a whole sequence of numbers):
A2 = A + B
B2 = (B <<< 3) xor A

Where <<< represents bit rotation (here, rotation three bits to the left). Try and feed it with two arbitrary numbers, say 44 and 171, and see what the output is. Then keep repeating it on the previous output and see when it eventually settles into a cycle (it will, but how big will the cycle be?). Does it produce the same output for two distinct inputs? Now what if you work on 16-bit words instead of bytes, or what if you change the rotation value to something else? Etc...

Looks like I don't have the math skills to grasp much of the theory, though. That's a shame.[/quote]
Yeah the math around pseudorandom numbers is pretty tough but much of it can be understood intuitively, and it's not like you need to know the theory to enjoy playing around with algorithms

Can anyone link me to some pseudo-random papers or websites?

http://people.seas.h...cnotes/list.htm

Harvard graduate course on the subject, taught by a expert, with free book/lecture notes! Kabam!