Hacker News Reader

Comment by nh23423fefe | Hacker News Reader

why would anyone think you could do that? if someone thought, "i want to uniformly sample a subset of x-y space, i guess i'll instead ill sample in r-theta space and then use the nonlinear transformation x = r cos theta and y = r sin theta to sample uniformly."

i would assume someone didnt even know what uniform meant if they did that.

and graphics people are so insane about perf, they arent going to just start doing sqrt over and over. they are going to rejection sample anyway because it just 2 fmas

View on HN

Rejection sampling is not a good choice here.

First, the cost is 2 FMAs * the cost of generating 2 random numbers * the number of rejection sampling iterations. On average, you reject (4-pi)/4 ~= 0.25 of the time. However, if you're running on a GPU in a warp (or the equivalent) of 32 threads, then you pay the cost of the maximum number of rejections over all the threads.

The bigger issue is that a direct mapping from [0,1]^2 to the disk, as is described in this tweet, if you have well-distributed uniform samples in [0,1]^2, you get well-distributed samples on the disk. Thus, stratified or low discrepancy samples in [0,1]^2 end up being well distributed on the disk. In turn, this generally gives benefits in terms of error with Monte Carlo integration of functions over the disk.

You can have the threads cooperate, distributing from those that got extra to those that were unlucky.

It's not clear that rejection sampling would be faster.

Assmuning this is a graphics operation running on a GPU. Taking the sqrt is pretty optimized, and having a branch for every point to be sampled is not fun.

Spot on. A lot of graphics people in the thread point this out. (I am not a graphics person — I occasionally tinker, but mostly just appreciate it from a distance.)

Rejection sampling doesn’t need sin/cos.

What costs more, generating a random number and maybe a second or a random number and a sin/cos? This sounds very platform dependent.

Note that when generating random points in the 4-ball (i.e. a quaternion)? The ball takes up a much smaller percentage of the space in the hypercube compared to the disk in a square, so rejections sampling can take many iterations.

> What costs more, generating a random number and maybe a second or a random number and a sin/cos

You’re adding a very unpredictable loop branch and a bunch of data dependencies doing that. For GPUs (and maybe even CPUs), the sqrt way is almost certainly faster.

If you have ALUs to spare, you can generate multiple points in parallel, say 4, and it is likely that at least one is inside the disk and you can select it branchlessly. Then you only need to loop in the very very rare case.

Just saying it's not clear and one would have to benchmark to find out.

The thinking goes more like this:

I want to get a random point in a circle.

What parameters make up a point in a circle?

Radius and angle can be one, so let's randomise those.

This is something that's done a lot in game development.

And it _is_ a random point in a circle. Just not a uniformly distributed one.

Btw, here's a way to sample a uniform random point on the edge of a circle without trigonometric functions:

Sample x and y coordinates from a standard normal distribution. Then project the result on the circle, by normalising the distance.

(You can approximate normal distributions fairly easily. Or your favourite computing environment might have specialised optimized machinery built-in.)

> Sample x and y coordinates from a standard normal distribution. Then project the result on the circle, by normalising the distance.

I wonder if that's uniform...

I expect that you would have more points mapped to the corners.

It appears to be uniform. I tested empirically in Python: https://pastebin.com/raw/ca03uywJ

https://codepen.io/toxicfork/pen/OJQzLba

This says otherwise

Normal distribution is not the same as uniform distribution. I edited in a normal distribution sampler in your codepen example.

https://pastebin.com/raw/CP4yNRE9

I see, thanks!

Btw, the following two are equivalent (in JavaScript syntax):

    var a = Math.max(Math.random(), Math.random());
    var b = Math.sqrt(Math.random());

Curious, how come? Does it become a statistical thing?

Well, not sure whether you'd call it statistics. It's a mathematical fact from probability theory. And it doesn't matter how often you sample: the distributions themselves are the same.

I came across that one in the other direction, when trying to work out how to make weighted rendezvous hashing work. See https://en.wikipedia.org/wiki/Rendezvous_hashing

I meant to show the output of my code, but Pasteboard was down at the time: https://gcdnb.pbrd.co/images/f8bgGZMW3deq.png?o=1

It's a well-known method to uniformly sample the surface of an n-dimensional sphere.

I guess/think you misread the “standard normal” part in that sentence as “uniform”.

The logic is that independent standard normals on each axis make up the multivariate standard normal, and the multivariate standard normal is rotationally invariant and therefore has the same density at any angle.

>why would anyone think you could do that?

They don't realize/they lack intuition about the nonlinearity of going from rectangular to polar coordinates.

Things like this aren't necessarily immediately obvious, depending on one's academic background.

> and graphics people are so insane about perf, they arent going to just start doing sqrt over and over. they are going to rejection sample anyway because it just 2 fmas

If you can re-jig the rest of your algorithm to consume the square of the radius (instead of the radius itself), you don't need to take a square-root here.

Sqrt is actually one of the faster operations, though obviously avoiding the need for any operation is clearly preferable :)

Here's a much simpler way to get the same distribution (in JavaScript syntax):

    var radius1 = Math.max(Math.random(), Math.random());
    var radius2 = Math.sqrt(Math.random());

Basically taking the maximum of two uniformly distributed random variables is the same as taking the square root of one of them in terms of their distributions.

Whether taking the max of two variables is cheaper than the square-root of one depends on implementation details, I guess?

You can also re-use the random variable that the max 'tossed' away by scaling it.

and for those looking for a demonstration of an O(n) approach, Jason Davies' demo of Poisson Disk sampling is a good start and links to Bridson's algorithm: https://www.jasondavies.com/poisson-disc/

Haven't you ever forgotten the determinant of the jacobian?

this cuts deep

Reply on news.ycombinator.com