| 50 | } |
| 51 | |
| 52 | static int32 UnbiasedUniform(SimplePhilox* r, int32 n) { |
| 53 | CHECK_LE(0, n); |
| 54 | const uint32 range = ~static_cast<uint32>(0); |
| 55 | if (n == 0) { |
| 56 | return r->Rand32() * n; |
| 57 | } else if (0 == (n & (n - 1))) { |
| 58 | // N is a power of two, so just mask off the lower bits. |
| 59 | return r->Rand32() & (n - 1); |
| 60 | } else { |
| 61 | // Reject all numbers that skew the distribution towards 0. |
| 62 | |
| 63 | // Rand32's output is uniform in the half-open interval [0, 2^{32}). |
| 64 | // For any interval [m,n), the number of elements in it is n-m. |
| 65 | |
| 66 | uint32 rem = (range % n) + 1; |
| 67 | uint32 rnd; |
| 68 | |
| 69 | // rem = ((2^{32}-1) \bmod n) + 1 |
| 70 | // 1 <= rem <= n |
| 71 | |
| 72 | // NB: rem == n is impossible, since n is not a power of 2 (from |
| 73 | // earlier check). |
| 74 | |
| 75 | do { |
| 76 | rnd = r->Rand32(); // rnd uniform over [0, 2^{32}) |
| 77 | } while (rnd < rem); // reject [0, rem) |
| 78 | // rnd is uniform over [rem, 2^{32}) |
| 79 | // |
| 80 | // The number of elements in the half-open interval is |
| 81 | // |
| 82 | // 2^{32} - rem = 2^{32} - ((2^{32}-1) \bmod n) - 1 |
| 83 | // = 2^{32}-1 - ((2^{32}-1) \bmod n) |
| 84 | // = n \cdot \lfloor (2^{32}-1)/n \rfloor |
| 85 | // |
| 86 | // therefore n evenly divides the number of integers in the |
| 87 | // interval. |
| 88 | // |
| 89 | // The function v \rightarrow v % n takes values from [bias, |
| 90 | // 2^{32}) to [0, n). Each integer in the range interval [0, n) |
| 91 | // will have exactly \lfloor (2^{32}-1)/n \rfloor preimages from |
| 92 | // the domain interval. |
| 93 | // |
| 94 | // Therefore, v % n is uniform over [0, n). QED. |
| 95 | |
| 96 | return rnd % n; |
| 97 | } |
| 98 | } |
| 99 | |
| 100 | int WeightedPicker::Pick(SimplePhilox* rnd) const { |
| 101 | if (total_weight() == 0) return -1; |