Fast dice rolls

[Chris Cain]

On Monday, 18 November 2013 at 03:10:22 UTC, bearophile wrote:
> See also:
> http://d.puremagic.com/issues/show_bug.cgi?id=5849
>
> Bye,
> bearophile

Nice one, bearophile. You called it.

I've done a bit of testing with the solution you've attached to 
that bug report. It's 10-50% faster than my solution depending on 
how many proportions are provided (I've tested as much as 
500_000). Despite mine being O(log(n)) to find the next dice roll 
and your solution being O(1), there really isn't that much of a 
difference. Strangely (to me), your solution actually seems to 
grow faster than mine as the number of proportions grow larger 
despite the proof claiming it should grow slower (although 
testing for > 500_000 seems pointless until actual data demands 
it).

As far as integer proportions go, I think my solution might be 
better overall because it's effectively equivalent to the current 
dice implementation (meaning it could be used as a near drop-in 
replacement and get precisely the same results, as long as the 
proportions are floating point values) and the code is simpler 
and avoids hiding any real bugs.

(That said, the original implementation has a bug that was easy 
to spot on my second comb-through)
--- in popFront:
// Return the number of elements that are not strictly greater 
than point
         _front = _propCumSumSorted.length - 
_propCumSumSorted.upperBound!pol(point).length;
---

On the other hand, a cumulative sum array approach (like mine and 
the std.random.dice implementation) will likely suffer major 
precision issues with floating point numbers. Especially if the 
first proportions are very large and the later proportions are 
very small. I haven't closely looked through the algorithm you're 
using to see whether it fares better, but I can't imagine it 
doing much worse.