Compressing the binomial distribution
I am currently having difficulty with fast and low memory solution to solve the problem. I am trying to solve using binomial distribution. I have a binomial distribution that can take 5 values, the probability of the values appearing is 1/16, 4/16, 6/16, 4/16, 1/16. I am currently using a 4 bit number to access a 16 binomial distribution array that contains 5 values with occurrences proportional to their probabilities. Is there a way to shrink the array down to size 5 and still be able to quickly determine which element in the array should be accessed. I considered using a Karnaugh map, but the amount of logical operations required slowing down the whole process. Is there some kind of compression or technique that exists to quickly implement it,since I want to increase the size of the binomial distribution, which is currently not feasible due to increased memory size or computation time.
binomialCoefficients[16]= {v1, v2, v2, v2, v2, v3, v3, v3, v3, v3, v3, v3, v4, v4, v4, v4, v5};
for (int i = 0; i < steps; i++) {
uint random = MWC64X(&seed2);
currentValue = currentValue * binomialCoefficients[random & 0b1111];
}
VS
binomialCompressed[5]={v1,v2,v3,v4,v5};
for (int i = 0; i < steps; i++) {
uint random = MWC64X(&seed2);
bool A = (random & 0b1000) >>3;
bool B = (random & 0b0100) >>2;
bool C = (random & 0b0010) >>1;
bool D = (random & 0b0001);
uint logicMappedIndex = (A&B&C&D)<<2 + (A&!B|...)<<1 +...;
currentValue = currentValue * binomialCompressed[logMappedIndex];
}
source to share
When you generate a random number, each bit has a probability that 1/2 is 1. If you just count the bits, that already gives you the index in the compressed array with binomial probabilities.
binomialCompressed[5]={v1,v2,v3,v4,v5};
for (int i = 0; i < steps; i++) {
uint random = MWC64X(&seed2) & 0b1111; //Get 4 bits only
uint count = popcount(random);
currentValue = currentValue * binomialCompressed[count];
}
source to share