Wednesday, November 6, 2013

Gauss's circle problem calculation without using the floor function

Gauss's circle problem is the one that asks given a circle of a certain radius centered at the origin, how many grid points are on the circle or inside of it. For example:
The graphic shows the answers for radius = 1, 2, 3 are 5, 13, 29 respectively.
One way to calculate how many there would be is to add 1 for every  point on the grid where the distance to the center is greater than the radius, and count how many times that happens checking every grid point. But that's really more of an algorithm...

I found this other way:
For example, this sum totals 113 for r=6 which is the correct value. 

 My reasoning was, if you look at the bottom right quadrant of the circle in question (disregarding the points on the axis) and and imagine all the vectors from those points to the point on the circle along the line to the origin,  you see vectors like this:
It ends up you can always tell from the sign of the y component of this vector whether the point in question is inside or outside of the circle. The  X above is the expression for the y component of this vector, derived by calculating the angle to a point from the origin and then finding the polar coordinates of a point that is that same angle from the origin but with a distance to the origin r, of the radius of the circle, and then converting back to cartesian coordinates and looking at the y component. I divide whatever this y value is by the absolute value to get either 1 if the point is inside the circle, 0 if it is on the circle, or -1 if it is outside.
The final expression is totalling these values up and solving for how many must be inside the whole circle from that sum.

Unfortunately it's harder to get rid of the absolute value and it didn't happen that there was a closed form sum for the double sum over the grid, but I still think it's an interesting approach.

No comments:

Post a Comment