Nick -4 years ago 52

C++ Question

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];

}

Recommended for you: Get network issues from **WhatsUp Gold**. **Not end users.**

Answer Source

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];
}
```

Recommended from our users: **Dynamic Network Monitoring from WhatsUp Gold from IPSwitch**. ** Free Download**

Latest added