CODEWITHSUNDEEP
crandomsrand
nonouco
nonouco

Reputation: 1170

C custom random function

I would like to create a fast lightweight function in C language that returns a pseudo random unsigned char. The challenging part for me (an ANSI C programmer)is that I cannot use the <stdio.h> or any other ready made functions. Any suggestions..?

by "fast" I meant: avoid unnecessary code (Eg if statements, loops etc) by "lightweight" I meant: use as less variables as possible

thanks

Upvotes: 4

Views: 7366

Answers (4)

Peter G.
Peter G.

Reputation: 15134

Use a Linear Congruential Generator

E.g.

uint32_t state = 777;

char myRand()
{
   state = state * 1664525 + 1013904223;
   return state >> 24;
}

Note that myRand returns the high bits, they are more pseudo-random than the low bits.

Linear Congruence Generators were introduced by D. H. Lehmer in 1949 (see Proc. 2nd Symp. on Large-Scale Digital Calculating Machinery (Cambridge, Mass.: Harvard University Press, 1951), 141-146). The concrete numeric constants I gave seem to originate from Press, William H.; et al. (1992). Numerical Recipes in Fortran 77: The Art of Scientific Computing (2nd ed.). ISBN 978-0-521-43064-7.

Upvotes: 5

zwol
zwol

Reputation: 140748

Inventing your own random number generator is a bad idea of the same class as inventing your own cryptography: it is easy to construct something that appears to do the job but is in fact disastrously ineffective; constructing something that actually does do the job is much harder. Read the cautionary tale of RANDU, then download one of the variants of the Mersenne Twister and use that.

Upvotes: 3

Vinicius Kamakura
Vinicius Kamakura

Reputation: 7778

From the linux kernel source code (random32.c)

the values in rnd_state should be initialized like: s1 > 1, s2 > 7, s3 > 15.

The paper claims this is a maximally equidistributed combined Tausworthe generator based on code from GNU Scientific Library 1.5 (30 Jun 2004)

struct rnd_state {
    u32 s1, s2, s3;
};

static u32 __random32(struct rnd_state *state)
{
#define TAUSWORTHE(s,a,b,c,d) ((s&c)<<d) ^ (((s <<a) ^ s)>>b)

    state->s1 = TAUSWORTHE(state->s1, 13, 19, 4294967294UL, 12);
    state->s2 = TAUSWORTHE(state->s2, 2, 25, 4294967288UL, 4);
    state->s3 = TAUSWORTHE(state->s3, 3, 11, 4294967280UL, 17);

    return (state->s1 ^ state->s2 ^ state->s3);
}

Academia: http://www.iro.umontreal.ca/~lecuyer/myftp/papers/tausme.ps

Upvotes: 5

Mark Ransom
Mark Ransom

Reputation: 308392

There's a whole list of pseudo-random number generators at Wikipedia: http://en.wikipedia.org/wiki/List_of_pseudorandom_number_generators

Upvotes: 1

Related Questions