8-bit random (unsigned)

[David Makin]

Hi all, does anyone know the correct coding for an 8-bit equivalent of the 32 or 64 bit Mersenne Twister pseudo-random algorithm ?

Edit: I mean the correct bits to test/shift etc. to produce a complete sequence that is as statistically random for the number range as the standard 32-bit version is.

[cKleinhuis]

lol, i just know the 8 bit use of c64 time cia to generate random pattrerns

[hobold]

May I ask what is limiting you? Is it just a matter of efficiency, so that you don't generate 32 random bits but throw away 24 of those? Or do you actually have to run on 8 bit hardware?

And if it is an 8 bit machine, why do you need to have the very high quality of a Mersenne Twister, when that poor little processor would need maybe hundreds of years to begin repeating the sequence?

Or is it about running lots and lots of independent random number generators in parallel on SIMD (vector ALU, GPU) hardware?

Just curious. Maybe a much simpler random number generator would already be sufficient for your purposes.

[David Makin]

May I ask what is limiting you? Is it just a matter of efficiency, so that you don't generate 32 random bits but throw away 24 of those? Or do you actually have to run on 8 bit hardware?

And if it is an 8 bit machine, why do you need to have the very high quality of a Mersenne Twister, when that poor little processor would need maybe hundreds of years to begin repeating the sequence?

Or is it about running lots and lots of independent random number generators in parallel on SIMD (vector ALU, GPU) hardware?

Just curious. Maybe a much simpler random number generator would already be sufficient for your purposes.

SIMD - and a "simpler" algorithm simply will *not* do, unless you know one that is both faster and as statistically random *at all sample bit sizes* as the Mersenne - 32 bits *would* do, or indeed 16 or anything 8+.
Exceptionally good statistical randomness is necessary as data produced is used in a tiered manner by xor-ing values together and in that case any bias is greatly magnified.
Come to think of it, it's possible that splitting the 32 bit Mersenne into 4 separate streams of 8 may do just as good a job as a "correct" 8-bit version - I wouldn't know without testing using the brute-force method i.e. suck it and see
I was hoping that those more mathematically educated than myself may be able to help.

[hobold]

I'm told that the Mersenne Twister produces pseudo random sequences of excellent statistical quality (only cryptographically secure generators are significantly better, but also significantly slower). So you should be able to, say, run 32 bit generators in those SIMD lanes and then use the result as four packed bytes.

[ker2x]

you could probably adapt the xorshift algorithm to 8.
the randomness is not crypto-secure but it's good enough for montecarlo-based fractal stuff.
I use the regular 32bits version in my openCL code.

eg : http://www.arklyffe.com/main/2010/08/29/xorshift-pseudorandom-number-generator/

Code:

// returns values from 1 to 255 inclusive, period is 255
uint8_t xorshift8(void) {
    y8 ^= (y8 << 7);
    y8 ^= (y8 >> 5);
    return y8 ^= (y8 << 3);
}

you can add more register to have a longer period.

[David Makin]

I'm told that the Mersenne Twister produces pseudo random sequences of excellent statistical quality (only cryptographically secure generators are significantly better, but also significantly slower). So you should be able to, say, run 32 bit generators in those SIMD lanes and then use the result as four packed bytes.

Thanks, that actually makes things pretty straightforward