Ponycheck: randomness with gaussian distribution

[mfelsche]

It would be nice to control the distribution of values returned by the Randomness class. As Randomness is not created in user code, its methods should have an additional argument controlling the distribution (UniformDistribution beinf the default).

As first step a normal distribution or gaussian distribution should be implemented.

For implementation given a PRNG with uniform distribution: http://www.design.caltech.edu/erik/Misc/Gaussian.html

[chobeat]

I started playing around trying to solve this task. I'm facing a few problems. The first one is that your link is dead but I assume it links to the Box-Muller transformation.

While trying to implement it for all the possible types, I'm facing some non-trivial type conversion problems. Using the transformation, I need to multiply everything by a F32.pi() and then back. Same problem with the ln(x), that I don't even think it's defined anywhere. Then I need to convert back. For some types should be fine, for others I think it's not possible.

What would be the solution? Restrict the min,max values to safe ranges and never produce random numbers outside? I feel like all this stuff should be added to the stdlib though.

[mfelsche]

Nice, that you want to pick this up. I didn't look into this for a long time now. Another algorithm that doesn't require a float (as it seems) is the Ziggurat Algorithm. I didn't look too close into it, but it looks doable.

Also the only type that needs to be supported by such a Distribution-thing is a U64. This is the return type of Rand.next() which in turn is the basis for all other methods in Rand. It might be possible to make such a Distribution with a very limited interface (say only .next(): U64) extend Random from stdlib and thus make it a fully usable Random number generator for Randomness in ponycheck.

[chobeat]

But what about the existing one? I thought there was the need to have a unified interface with the existing one. You're saying that I should initialize the existing Randomness with my new Gaussian class instead of the normal Rand and then reuse the existing code? Or should I have two classes and have the current Randomness as an abstract class? I think the second looks better

[chobeat]

Anyway I've started implementing the ziggurat algorithm and it should be fine.

[chobeat]

Update: I'm proceeding very slowly, mostly because of my lack of knowledge of ponyc that costs me a lot of effort to write every line of code. The major problem though is the testability of parts of the algorithm for correctness: since there are stochastic behaviors to evaluate, writing unit tests requires lot of data-related tooling that doesn't exist yet in Pony and I would have to develop for the tests. Right now I'm in the situation where I have the core part of the algorithm done, the deterministic part tested but most of it is untested.

I hope that in the coming weeks I will find the motivation to focus more on this problem.

[ergl]

Do we want to provide certain distributions as part of the pony check library, or perhaps open up the possibility of supplying an interface type to the Randomness class (with a default for uniform, for example) so that distributions can be plugged in?

Perhaps user-generated distributions don't make much sense in this context, but it's something to keep in mind.