[phobos] fastDice

[David Simcha]

A decent Gaussian is trivial:

http://en.wikipedia.org/wiki/Box%E2%80%93Muller_transform

Also see my dstats.random lib.  Most of this stuff requires binary 
attribution because it was translated from the Numpy code, but the 
Box-Muller Gaussian is arguably not original enough to be copyrightable, 
i.e. you can't copyright algorithms, Box-Muller is a very well-known 
algorithm, and there's a very limited number of ways to express the 
algorithm in code once it's specified.

Poisson is a PITA IIRC.  (I have code to do it, but again it requires 
binary attribution.)

Where is Zipf used?  I left it out of my Numpy port that I did awhile 
back.  IIRC it was because Wikipedia didn't provide enough information 
on it to make my code reasonably testable.

On 1/2/2011 5:59 PM, Andrei Alexandrescu wrote:
> 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
> _______________________________________________
> phobos mailing list
> phobos at puremagic.com
> http://lists.puremagic.com/mailman/listinfo/phobos
>