probsys / fast-loaded-dice-roller Goto Github PK

See the analysis in https://issues.apache.org/jira/browse/RNG-179

While writing a code generator based on the Fast Loaded Dice Roller, I've noticed that two equivalent sets of integer weights (where one is an integer multiple of the other) can have a different table size. For example:

• One weight set, 1, 9, 6, turns into a 4x5 table by the Fast Loaded Dice Roller.
• However, an equivalent weight set, 1000, 9000, 6000, turns into a 14x5 table this way.

This shows that it might be helpful in some cases to divide the weights by their greatest common divisor (ignoring zero weights) to achieve an equivalent weight set that minimizes table sizes.

1. Remove initialization of H to -1; instead, use calloc for initalizatio nto 0 and index the samples by 1, ..., n+1; also make sure to update the sampler to check if the sample is <= n, and return one minus

https://github.com/probcomp/fast-loaded-dice-roller/blob/2fb32e94a04c744c86aa4cb54b3ee0259894e777/src/c/fldr.c#L55
https://github.com/probcomp/fast-loaded-dice-roller/blob/2fb32e94a04c744c86aa4cb54b3ee0259894e777/src/c/fldr.c#L97-L98

2. Remove unneeded additions
   https://github.com/probcomp/fast-loaded-dice-roller/blob/2fb32e94a04c744c86aa4cb54b3ee0259894e777/src/c/fldr.c#L57
   https://github.com/probcomp/fast-loaded-dice-roller/blob/2fb32e94a04c744c86aa4cb54b3ee0259894e777/src/c/fldr.c#L65

3. Change bool to int
   https://github.com/probcomp/fast-loaded-dice-roller/blob/2fb32e94a04c744c86aa4cb54b3ee0259894e777/src/c/fldr.c#L56
   https://github.com/probcomp/fast-loaded-dice-roller/blob/2fb32e94a04c744c86aa4cb54b3ee0259894e777/src/c/fldr.c#L64

The main bottleneck in preprocessing is bit extraction from the a[i]. It might more efficient to compute the probability matrix in reverse order (i.e., with the least significant bit in the first column) and using integer division on the running values of a[i], instead of bit shifts/masking.

Using a uniform distribution with floating-point values seems to result in only 0 or 1 values while sampling.

from fldr import fldrf_preprocess
from fldr import fldr_sample
x = fldrf_preprocess([0.1 for _ in range(10)])
print([fldr_sample(x) for _ in range(20)])

[0, 1, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 1]

rand() returns a random 31-bit integer packed into a 32-bit integer (whose sign bit is always zero). The positions of the extracted bits should then be 0, ..., 30. However, by setting k=30, flip_pos = k, and flip_pos --, we only ever extract bits the bits at locations 0, ..., 29.

Also the code can be made more general to determine k automatically from limits.h and RAND_MAX.

Not sure if this is expected or if it's a bug.

python -m timeit -s "from fldr import fldr_preprocess; from fldr import fldr_sample; l = range(10000); x = fldr_preprocess([1 for _ in l])" "fldr_sample(x)"

50000 loops, best of 5: 6 usec per loop

python -m timeit -s "from fldr import fldrf_preprocess; from fldr import fldr_sample; l = range(10000); x = fldrf_preprocess([1/len(l) for _ in l])" "fldr_sample(x)"

50 loops, best of 5: 5.1 msec per loop