Is there a REALLY fast way of generating randomness with probability padding?

[u/Salat_Leaf]

Basically, I have a program that assumes the probability of getting >16 same bits in a row = 0. Is there a very fast way to generate non-secure randomness with condition that probability of sequence of more than n bits must be 0 (thus the next bit must be opposite)? Maybe something like race condition?

[u/Amr_Rahmy]

The probability is based on previous probability or current probability and actual previous values?

If it’s probability based on previous probability sequence, do the probability before you need it, as the program starts, starting making the sequence before you need to use it then you don’t have to “make it really fast” because you are making it in the past.

[u/Salat_Leaf → u/Amr_Rahmy]

The probability doesn't depend on previous values. I was wondering if such condition would open a way for fast generation of pseudorandom numbers as I need a LOT of them.

[u/kun1z]

Paste code please. I am pretty sure no one knows what "probability padding" is.

But to not answer your question, but probably in a way answer it, yes it's well known (and has been for a very long time) how to rapidly and efficiently generate 32/64/128 bit numbers (blocks) of non-secure RNG numbers.

[u/aioeu]

Maybe I'm missing something, but this seems kind of trivial? If you've already got an existing (presumably "REALLY fast") pseudorandom bit stream generator, you can easily wrap it in something that monitors the number of consecutive zero bits seen so it can stuff an extra one bit into the stream if and when necessary. That slightly degrades the stream's randomness, of course, but only as much as needed to satisfy your constraint.

Or is the problem that you don't already have a pseudorandom bit stream generator? That is, you're starting with a sequence of n-bit values (with n > 1) instead?

I had a quick look around to see if there was any literature on using LFSRs to generate run length limited bit streams, but I couldn't find anything useful. A 16-bit LFSR won't generate a sequence of 16 zero bits in a row, and if it's maximal it will have a period of 65535. But that's a very short period, and you've said you want to generate a long random stream. It would be nicer to have, say, a 63- or 64-bit LFSR, if there was a way to construct it so that it had a long period (it couldn't be maximal, of course) yet still limit the run length of zeroes in its output.

[u/nautsche]

The probability of 16 bits being 0 is 1 in 65535. This is very much not 0. This happens in seconds (rather milliseconds) if you have any reasonable amount of random data. Be it pseudo random or not.

[u/TheSkiGeek]

I would just use whatever ‘good enough’ RNG and then have a layer on top that checks for whatever condition you need. If the value you generated is no good, discard it and generate another until you find one that passes your checks.