arkouda icon indicating copy to clipboard operation
arkouda copied to clipboard

Add Ziggurat as a method for `standard_normal`

Open stress-tess opened this issue 8 months ago • 2 comments

Right now our implementation of standard_normal does a box-muller transform, but numpy uses the Ziggurat algorithm. Ziggurat algorithm's wikipedia page says:

Nevertheless, the algorithm is computationally much faster than the two most commonly used methods of generating normally distributed random numbers, the Marsaglia polar method and the Box–Muller transform, which require at least one logarithm and one square root calculation for each pair of generated values. However, since the ziggurat algorithm is more complex to implement it is best used when large quantities of random numbers are required.

considering it's used by numpy and we're likely to need to generate large quantities of numbers, I think it would be worthwhile. It's also used in numpy's implementation of other distributions such as exponential which will be added in #3183

Numpy's c based implementation can be found here

This will require saving off some constants . The nature of chpl means we'll want these constants on each locale or else we'll kill performance by going back and forth to the lookup tables on locale 0. This has caused us issues previously (see https://github.com/Bears-R-Us/arkouda/pull/2354)

stress-tess avatar Jun 03 '24 20:06 stress-tess