[phobos] fastDice

[Andrei Alexandrescu]

On 9/11/10 3:29 PM, David Simcha wrote:
> I've written a few functions that generate random numbers from an
> arbitrary discrete distribution in O(log N) time, where N is the number
> of possible values, using SortedRange.lowerBound(). It's similar to
> dice() except that in exchange for O(N) auxiliary space and upfront
> initialization cost you get O(log N) generation. I've attached the code,
> which is fairly simple. Should this go in std.random, or is needing this
> O(log N) performance on dice() niche enough that this belongs in my
> dstats lib instead?

I'm not sure. You may want to ask the question on the newsgroup.

BTW, I think std.random is in dire need of a few classic distribution 
(Gaussian, Poisson, Zipf come to mind). Anyone inclined?


Andrei