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.

score 8 · Answer 1 · answered Feb 29 '12 at 02:18

8

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.

answered Feb 29 '12 at 02:18

Hot Licks

47,103
17
93
151

3

I guess the last division should be using float, otherwise `random` is always zero. – Axel Bregnsbo Jun 04 '21 at 11:49

dlras2 · Accepted Answer · 2012-02-29T17:47:13.010

5

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.}

edited Feb 29 '12 at 17:47

answered Feb 29 '12 at 02:08

dlras2

8,416
7
51
90

"..has been tested to be very cryptologically sound." Definitely not! MurmurHash is a relatively new hashing algorithm that has had lots of flaws and many tweaks applied to it - a good sign that the algorithm is weak. Sure, you can use it for generating psuedo-random numbers, but no-one should be using it for cryptographic operations. – adelphus Feb 29 '12 at 11:09
@adelphus—I'm no expert in cryptography, so I'll remove the statement, but I thought that being cryptologically sound simply meant good distribution, low collision, and low bias. @Peter O.—Good catch: I did indeed mean uniform. Oops. – dlras2 Feb 29 '12 at 17:46

score 4 · Answer 3 · edited Mar 06 '13 at 02:44

4

A linear congruential generator would be simple to implement. A nice implementation in pure C is available here.

edited Mar 06 '13 at 02:44

Community

1
1

answered Feb 29 '12 at 02:13

dan04

87,747
23
163
198

score 1 · Answer 4 · answered Feb 29 '12 at 02:11

You can try Multiply-with-carry by George Marsaglia.

Code from Wikipedia:

#include <stdint.h>

#define PHI 0x9e3779b9

static uint32_t Q[4096], c = 362436;

void init_rand(uint32_t x)
{
    int i;

    Q[0] = x;
    Q[1] = x + PHI;
    Q[2] = x + PHI + PHI;

    for (i = 3; i < 4096; i++)
            Q[i] = Q[i - 3] ^ Q[i - 2] ^ PHI ^ i;
}

uint32_t rand_cmwc(void)
{
    uint64_t t, a = 18782LL;
    static uint32_t i = 4095;
    uint32_t x, r = 0xfffffffe;
    i = (i + 1) & 4095;
    t = a * Q[i] + c;
    c = (t >> 32);
    x = t + c;
    if (x < c) {
            x++;
            c++;
    }
    return (Q[i] = r - x);
}

score 0 · Answer 5 · answered Feb 29 '12 at 10:37

0

Check the source code of the gsl library, a couple of well tested algorithms are implemented in it.

answered Feb 29 '12 at 10:37

Bort

2,423
14
22

score 0 · Answer 6 · answered Feb 29 '12 at 10:41

0

You may want to look for Mersenne Twister. There are lots of algorithms of higher quality. A good article with an overview you find here:

http://en.wikipedia.org/wiki/Pseudorandom_number_generator

answered Feb 29 '12 at 10:41

score 0 · Answer 7 · answered Feb 29 '12 at 20:39

0

You might try Isaac which is also available as part of CCAN here

answered Feb 29 '12 at 20:39

Spudd86

2,986
22
20

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

7 Answers7

Linked