Algorithm for finding number of squares in a given circle

Question

Here is my drawing: CLICK

I need to write a program, that will find the number of squares(1x1), that we can draw into a circle of given radius.The squares can only by drawn fully and placed like lego blocks- one on another. In some cases, vertexes of squares can lie on the circle.

Examples: for 1- it makes 0, for 2- it gives four, for 3- 16 squares, for 4-32, for 5-52.

I have written something, but it doesn't work fine for 5+ (I mean- radius bigger than 5). Here it goes: CLICK. In my code- r is radius of the circle, sum is the sum of all squares and height is the height of triangles I try to "draw" into the circle (using Pythagorean theorem).

Now- any help? Is my algorithm even correct? Should I change something?

Answer 1

There is Gauss's Circle Problem that gives a formula to count integer points inside the circle of given radius. You may use this logic to count squares that lie in the circle.

N = 4 * Sum[i=1..R] (Floor(Sqrt((R^2-i^2)))

example:

R = 3
i=1   n1 = Floor(Sqrt(9-1))~Floor(2.8)=2
i=2   n2 = Floor(Sqrt(9-4))~Floor(2.2)=2
i=3   n2 = Floor(Sqrt(9-9))=0
N=4*(n1+n2+n3)=16

Answer 2

First off - circle with a radius of 5 fits 60 1x1 squares, not 52. My bet would be someone didn't count the points {[3,4],[3,-4],[4,3],[4,-3],[-4,3],[-4,-3],[-3,4],[-3,-4]} when drawing that on paper and counting by hand, being unsure whether they are right on the circle or just outside of it. They are exactly on the circle.

Second - MBo's answer brought me here - I sometimes search StackOverflow for Gauss Circle Problem to see if someone suggested some new, fun algorithm.

Third - here's the code:

int     allSquares=0,
        squaredRadius=radius*radius,
        sideOfQuarterOfInscribedSquare=(int)(long)(radius/sqrt(2));
for(int x=sideOfQuarterOfInscribedSquare+1;
        x<radius;
        x++){
    allSquares+=(long)sqrt(squaredRadius-x*x);
}
allSquares= allSquares*8+4*sideOfQuarterOfInscribedSquare*sideOfQuarterOfInscribedSquare;
return allSquares;

What it does is just count the squares inside one-eighth of the circle, outside an inscribed square. Sorry for my hipster formatting and overly verbose variable names.