RCG: Add Gaussian noise part

Uniform noise part already exists. I don't know if there's a simple constant time platform, so a new part is needed for those that don't want to write a custom C module.

added RCG label

Chris Wipf suggests https://en.wikipedia.org/wiki/Marsaglia_polar_method for generating Gaussian noise.

I've learned today that algorithms for non-uniform distributions are not constant time. Are, in fact, open ended. This may be a problem for the RCG. Would a truncated gaussian be ok?

Are you thinking that the do-while loop that tests on the random variable becomes an infinite loop, in the worst case? That's true, but would be safe to disregard since it's vanishingly unlikely to happen.

Assuming a miss chance of (1 - pi/4) and 16k channel we might expect 18 consecutive misses in a year, with a reasonable chance of more.

I think you're right that we can handle that though I'm not sure how fast our RNG is.

Based on some models I've seen running with dozens of noise blocks in them, I think we'd need to get into hundreds or thousands of misses before it would be a problem.

By the way, if avoiding the runtime jitter is important, there are other methods like inverse transform sampling that would run in constant time. Apparently GNU R chose this approach and has a C implementation.

I am also interested in getting a Gaussian noise block. One thing that @tega-edo and I were thinking is that you could hold a buffer of possible values (maybe like the last 500 generated values) then if you had a miss, you could randomly select from that list; then you would not have a possibility of a non-completing loop. I'm not sure if it would work for a permanent implementation but it is something we are thinking of for our own gaussian noise block

changed milestone to %advligorts 5.0.0

added todo label

mentioned in merge request !354 (merged)

closed