C Random Number Generation (pure C code, no libraries or functions)

Question

I need to generate some random numbers in C for testing and debugging the system. The system is a custom hardware (SoC) with a limited set of functions so I can only use basic mathematical operations.

And no, I can't use random number generators in stdlib or math.h. I need to write it myself. So is there some sort of algorithm for generating random numbers?

I know that a simple solution is to generate the numbers here on my workstation and embed them into the module, but I don't want to do that.

Answer 1

Just dig up the article by Park and Miller in the Oct 88 issue of CACM.

The general algorithm they propose is:

a = 16807;
m = 2147483647;
seed = (a * seed) mod m;
random = seed / m;

Though the article includes several refinements.

Answer 2

A random number generator is basically a special^* hash function which runs recursively from a starting seed.

I've used the MurmurHash2 algorithm in my C# code to good effect. It's extremely fast and simple to implement and has been tested to be very well distributed with low collision rates. The project has several different open source hash functions written in C++ which should be easily convertible to C.

---

^{* By special I mean that running the hash function on a value should return another seemingly random (but determinate) value, so that the output doesn't appear to form patterns. Also, the distribution of the returned value should have a uniform distribution.}