I have to write pseudo-random generator on assembler without any float/double operations and functions, like sin/cos, sqrt e.t.c. So I can't use general methods to do that. Also I have limit for random-numbers: 00-0F. How can I do this?
As I understood, I need to generate uniform-number at first. I did it like this: x = (13 * x + 7) % 16; (but it has a problem - it's the unifromest distribution ever. If it generated 15 numbers and I know all of them, I can say 16th with 100% probability, because where is no repetition in period which is 16 (module) ).
And after that, I need to regenerate those numbers to gaussian. I found this solution in the internet, but it doesn't work.
for (i = 0; i < N; ++i) // N - amount of randomized numbers
{
++gx[x = (a * x + c) % m]; //gx - histogram of x
xm[i] = x; // xm - massive of randomized numbers in uniform
y = 0;
for (j = 0; j < i + 1; ++j)
{
y += xm[j] * n - j; // n - primitive number. I choose 13
}
y = y / (i + 1);
y %= m;
ym[i] = y; // ym - massive of randomized numbers in gaussian
++gy[y]; //gy - histogram of y
}
What should I do with it? (I know nothing about probability theory)
I get this output of gx and gy:
Uniform
0 4 ****
1 4 ****
2 4 ****
3 4 ****
4 4 ****
5 4 ****
6 4 ****
7 4 ****
8 4 ****
9 4 ****
10 4 ****
11 4 ****
12 4 ****
13 4 ****
14 4 ****
15 4 ****
Normal
0 2 **
1 3 ***
2 8 ********
3 4 ****
4 10 **********
5 4 ****
6 1 *
7 2 **
8 1 *
9 3 ***
10 8 ********
11 4 ****
12 5 *****
13 6 ******
14 1 *
15 2 **
Assuming that a "Gaussian" distribution over the integers in [0, 15] means the binomial distribution B(15, 1/2), the obvious approach is to generate two random bytes, mask the second by 0x7f, and count the number of bits set. The three-bit version looks like this.
0 *
1 *******
2 *********************
3 ***********************************
4 ***********************************
5 *********************
6 *******
7 *
If this assumption is incorrect, then please edit your question to specify the exact probability desired for each integer in [0, 15].
If your target platform has an 8-bit multiply with 16-bit output, then it should be possible to get an efficient Complementary-multiply-with-carry generator, for example, b = 256 and r = 256 and a = 207, or b = 256 and r = 32 and a = 211. (I'm not sure how much space you have for the generator state or if these parameter choices pass randomness tests.)
Collected from the Internet
Please contact [email protected] to delete if infringement.
Comments