4 ms·

> But, as Dr Aimone’s colleague Darby Smith notes, the real world that computer modellers are trying to model does not work like this. For example, the temperat

> But, as Dr Aimone’s colleague Darby Smith notes, the real world that computer modellers are trying to model does not work like this. For example, the temperature in London in December may vary between -7°C and 17°C, but is most likely to be in the range 3°C to 8°C. [...] Distorting uniform distributions of random numbers to take account of these realities is tedious and unsatisfactory. As Dr Smith observes, it would be more efficient if the random numbers used corresponded to the natural distribution in the first place. I have a hard time understanding how this is a problem. Using uniform random numbers to choose the x-axis value on a graph of an integrated probability distribution function and mapping it to the y-axis is pretty garsh darn simple and normal. This is the crux of monte carlo methods and is stupidly fast these days. What are they talking about?

sgillen 5y ago
Though I agree we have good solutions to this, I also think it's a more nuanced problem than it seems at first glance. See for example this stack overflow post: https://stackoverflow.com/questions/75677/converting-a-uniform-distribution-to-a-normal-distribution https://stackoverflow.com/questions/75677/converting-a-unifo.... To convert uniform to a Gaussian there are at least four different competing methods, all with subtle tradeoffs. Besides that there are certainly other continuous distributions we might be interested in transforming to, which are useful but not as nice as a Gaussian.
- TheDudeMan 5y ago
  > there are at least four different competing methods, all with subtle tradeoffs So choose one at random for each sample :)
- dwohnitmok 5y ago
  > there are at least four different competing methods, all with subtle tradeoffs. As is the case with most implementations of things, even elementary things, that have to do with the real numbers on discrete hardware (see numerical integration, square roots and inverses, trig functions, various approximations of the real numbers themselves, etc.). Real numbers are hard. It's a blessing only a minority of computer programs need to actually deal with them (or their approximations).
- dahart 5y ago
  Methods to simulate a Normal distribution doesn’t really help you simulate a measured distribution of data, which was the stated problem, wasn’t it? The parent comment’s suggestion to use the tabulated Inverse Transform method is already likely to be the optimal choice for simulating a discrete data distribution. There’s one alternative called the Alias Method that is fast to sample, but uses a discontinuous mapping so it compromises your ability to benefit from stratified or Quasi-Random sampling, which means it loses significant efficiency for Monte Carlo applications and thus doesn’t get used very often. (This is true of Ziggurat as well, and aside from Ziggurat the SO page you linked only has two other decent suggestions and one of them is the Inverse Transform method. Box-Muller is historically interesting, but I think doesn’t really “compete”.) So, anyway, FWIW, it doesn’t really seem super nuanced. I’m guessing the article’s author was just writing for a non-technical audience and isn’t clearly stating the problems being investigated by the COINFLIPS team.
macrolocal 5y ago
For what it's worth, I once struggled to implement random walks on custom hardware because its ISA lacked trig support and I couldn't generate N(0,1)s quickly enough. For that application, tens of fp32 maccs to transform from uniform data was a non-starter.
riskneutral 5y ago
Producing large samples of uniform pseudo-random numbers in high dimensions is very tricky. If COINFLIPS can solve that problem then that would be very useful. That said, I don't know if there are many computational workloads where the basic random number generation step is the performance bottleneck.
xscott 5y ago
Yes, you can use an inverse CDF to implement a fairly efficient generator for pretty much any probability distribution. (I'm sure there's some pathological, and uncommon, counterexample.) It's just a small/quick lookup table, and you can interpolate if you need extra resolution.
- tommiegannert 5y ago
  Isn't the problem that the normal distribution doesn't have an (inverse) CDF in closed form? So even the most common non-uniform distribution becomes a pathological example. https://en.wikipedia.org/wiki/Probit https://en.wikipedia.org/wiki/Probit
  - klipt 5y ago
    You can approximate it and throw away some samples to get the true distribution. See https://en.wikipedia.org/wiki/Ziggurat_algorithm https://en.wikipedia.org/wiki/Ziggurat_algorithm for one method which I believe statistical languages like R currently use to generate normal random variables.
  - xscott 5y ago
    Nope, that's not a problem. You don't need a closed form and simple equation to build the lookup table (inverse CDF). Use whatever expensive and iterative functions you want to build it. For the normal distribution, you can use a bisection on the math.h erf() function to invert it. This is expensive, but you're only going to do it to make your lookup table once. Build that table to reasonably fit in your cache, and then use your uniform pseudo random integers to peak into that table. As I mentioned above, you can interpolate between values in the table if you need more resolution. There are other tricks for specific distributions, but the technique is very general.
jameshart 5y ago
Random scalars definitely don't seem like somethign that needs radical technical solutions, no. I wonder if the tricky part is in choosing random vectors? Just doing simple things like choosing a uniformly distributed random point in a disk or on the surface of a sphere are awkward enough to do efficiently; choosing a bunch of random points drawn from the London temperature/pressure/rainfall distribution for December is much worse. I wonder if that might be part of the complexity that is being elided to bring this article to a popular-science-reader level?
- acidburnNSA 5y ago
  Maybe? Sampling on a sphere is computationally trivial in spherical coordinates and done in every undergraduate Monte Carlo radiation transport class as a homework. Knowing temperature PDFs is similarly easy, and so is sampling them. I will have to go read some literature on this cointoss business I think.
- klipt 5y ago
  > I wonder if the tricky part is in choosing random vectors? Sampling vectors from multidimensional random distributions is a well studied problem. For example the open source project https://mc-stan.org https://mc-stan.org implemented several (at the time) state of the art methods like Hamiltonian Monte Carlo with the help of Automatic Differentiation.

sgillen 5y ago

Though I agree we have good solutions to this, I also think it's a more nuanced problem than it seems at first glance. See for example this stack overflow post: https://stackoverflow.com/questions/75677/converting-a-uniform-distribution-to-a-normal-distribution https://stackoverflow.com/questions/75677/converting-a-unifo.... To convert uniform to a Gaussian there are at least four different competing methods, all with subtle tradeoffs. Besides that there are certainly other continuous distributions we might be interested in transforming to, which are useful but not as nice as a Gaussian.

TheDudeMan 5y ago
> there are at least four different competing methods, all with subtle tradeoffs So choose one at random for each sample :)
dwohnitmok 5y ago
> there are at least four different competing methods, all with subtle tradeoffs. As is the case with most implementations of things, even elementary things, that have to do with the real numbers on discrete hardware (see numerical integration, square roots and inverses, trig functions, various approximations of the real numbers themselves, etc.). Real numbers are hard. It's a blessing only a minority of computer programs need to actually deal with them (or their approximations).
dahart 5y ago
Methods to simulate a Normal distribution doesn’t really help you simulate a measured distribution of data, which was the stated problem, wasn’t it? The parent comment’s suggestion to use the tabulated Inverse Transform method is already likely to be the optimal choice for simulating a discrete data distribution. There’s one alternative called the Alias Method that is fast to sample, but uses a discontinuous mapping so it compromises your ability to benefit from stratified or Quasi-Random sampling, which means it loses significant efficiency for Monte Carlo applications and thus doesn’t get used very often. (This is true of Ziggurat as well, and aside from Ziggurat the SO page you linked only has two other decent suggestions and one of them is the Inverse Transform method. Box-Muller is historically interesting, but I think doesn’t really “compete”.) So, anyway, FWIW, it doesn’t really seem super nuanced. I’m guessing the article’s author was just writing for a non-technical audience and isn’t clearly stating the problems being investigated by the COINFLIPS team.

macrolocal 5y ago

For what it's worth, I once struggled to implement random walks on custom hardware because its ISA lacked trig support and I couldn't generate N(0,1)s quickly enough. For that application, tens of fp32 maccs to transform from uniform data was a non-starter.

riskneutral 5y ago

Producing large samples of uniform pseudo-random numbers in high dimensions is very tricky. If COINFLIPS can solve that problem then that would be very useful. That said, I don't know if there are many computational workloads where the basic random number generation step is the performance bottleneck.

xscott 5y ago

Yes, you can use an inverse CDF to implement a fairly efficient generator for pretty much any probability distribution. (I'm sure there's some pathological, and uncommon, counterexample.) It's just a small/quick lookup table, and you can interpolate if you need extra resolution.

tommiegannert 5y ago
Isn't the problem that the normal distribution doesn't have an (inverse) CDF in closed form? So even the most common non-uniform distribution becomes a pathological example. https://en.wikipedia.org/wiki/Probit https://en.wikipedia.org/wiki/Probit
- klipt 5y ago
  You can approximate it and throw away some samples to get the true distribution. See https://en.wikipedia.org/wiki/Ziggurat_algorithm https://en.wikipedia.org/wiki/Ziggurat_algorithm for one method which I believe statistical languages like R currently use to generate normal random variables.
- xscott 5y ago
  Nope, that's not a problem. You don't need a closed form and simple equation to build the lookup table (inverse CDF). Use whatever expensive and iterative functions you want to build it. For the normal distribution, you can use a bisection on the math.h erf() function to invert it. This is expensive, but you're only going to do it to make your lookup table once. Build that table to reasonably fit in your cache, and then use your uniform pseudo random integers to peak into that table. As I mentioned above, you can interpolate between values in the table if you need more resolution. There are other tricks for specific distributions, but the technique is very general.

jameshart 5y ago

Random scalars definitely don't seem like somethign that needs radical technical solutions, no. I wonder if the tricky part is in choosing random vectors? Just doing simple things like choosing a uniformly distributed random point in a disk or on the surface of a sphere are awkward enough to do efficiently; choosing a bunch of random points drawn from the London temperature/pressure/rainfall distribution for December is much worse. I wonder if that might be part of the complexity that is being elided to bring this article to a popular-science-reader level?

acidburnNSA 5y ago
Maybe? Sampling on a sphere is computationally trivial in spherical coordinates and done in every undergraduate Monte Carlo radiation transport class as a homework. Knowing temperature PDFs is similarly easy, and so is sampling them. I will have to go read some literature on this cointoss business I think.
klipt 5y ago
> I wonder if the tricky part is in choosing random vectors? Sampling vectors from multidimensional random distributions is a well studied problem. For example the open source project https://mc-stan.org https://mc-stan.org implemented several (at the time) state of the art methods like Hamiltonian Monte Carlo with the help of Automatic Differentiation.