Random number generation without using bit operations

Question

I'm writing a vertex shader at the moment, and I need some random numbers. Vertex shader hardware doesn't have logical/bit operations, so I cannot implement any of the standard random number generators. Is it possible to make a random number generator using only standard arithmetic? the randomness doesn't have to be particularly good!

Answer 1

If you don't mind crappy randomness, a classic method is

x[n+1] = (x[n] * x[n] + C) mod N

where C and N are constants, C != 0 and C != -2, and N is prime. This is a typical pseudorandom generator for Pollard Rho factoring. Try C = 1 and N = 8051, those work ok.

Answer 2

Vertex shaders sometimes have built-in noise generators for you to use, such as cg's noise() function.

Answer 3

Use a linear congruential generator:

X_(n+1) = (a * X_n + c) mod m

Those aren't that strong, but at least they are well known and can have long periods. The Wikipedia page also has good recommendations:

The period of a general LCG is at most m, and for some choices of a much less than that. The LCG will have a full period if and only if:

1. c and m are relatively prime,
2. a - 1 is divisible by all prime factors of m,
3. a - 1 is a multiple of 4 if m is a multiple of 4

Answer 4

Believe it or not, I used newx = oldx * 5 + 1 (or a slight variation of it) in several videogames. The randomness is horrible--it's more of a scrambled sequence than a random generator. But sometimes that's all you need. If I recall correctly, it goes through all numbers before it repeats.

It has some terrible characteristics. It doesn't ever give you the same number twice in a row. A few of us did a bunch of tests on variations of it and we used some variations in other games.

We used it when there was no good modulo available to us. It's just a shift by two and two adds (or a multiply by 5 and one add). I would never use it nowadays for random numbers--I'd use an LCG--but maybe it would work OK for a shader where speed is crucial and your instruction set may be limited.