My main purpose is to spread a buffer over pixels of an image randomly and efficiently, but I'm stuck at generating distinct random numbers. What I simply want is to generate numbers between 0 and N, but I also want these numbers to be distinct. Also note that N usually will be quite large such as 20 million and the algorithm doesn't have to be cryptographically secure.
I can't use random shuffle method since N is quite large. I did some search and found Linear congruential generator but the parameter m is required to be prime, but my N is sometimes not.
Lastly, I tried the following approach but it's not quite efficient and reliable since it might throw maximum call stack size exceeded error.
next(max: number)
{
let num = LCG.next()
if (num <= max) return num
return next(max)
}
If numbers are distinct, then they are not random. Random numbers can repeat; distinct numbers are selected from an ever decreasing set. It is the difference between selecting numbers with replacement and without replacement.
You want numbers from 0 to 20 million. As you have found, that is too large for a shuffle. Better to use an encryption. Because an encryption is one-to-one, as long as you have distinct inputs you will get distinct outputs. Just encrypt 0, 1, 2, 3, ... and you will get distinct outputs.
You talk about using a linear congruential PRNG so I assume that security is not of great importance. 20 million is about 2^24 or 2^26 so you can write a simple four round Feistel cipher sized appropriately to do the work. Alternatively, use a standard library cipher with one of the Format preserving methods to keep the output within the bounds you want.