I am currently have difficulty coming up with a fast and low memory solution for a problem. I am attempting to solve using the binomial distribution. I have a binomial distribution that can take on 5 values, the probabilities of the values occurring is 1/16, 4/16, 6/16, 4/16, 1/16. I am currently using a 4 bit number to access a binomial distribution array of size 16 that contains the 5 values with occurrences proportional to their probabilities. Is there a way to compress the array to size 5 and still be able to quickly determine which element in the array to access. I considered using a Karnaugh map however the number of logical operations required slowed the entire process down. Is there some sort of compression or technique that exists to rapidly implement this, as I wish to increase the size of the binomial distribution, which is currently infeasible due to the increase in either memory 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];
}
When you generate a random number, each of the bits has a probability of 1/2 of being a 1. If you just count the bits, it is already giving you the index in your 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];
}