Number of integer lattice points within a circle

Question

I am trying to solve a problem on codeforces, to be precised, this problem. I was able to figure out that the solution is $N(n) - N(n-1)$ where $N(n)$ is the number of lattice points withing a circle centered at the origin. I wrote a solution using the formula from MathWorld.WolframAlpha

$$N(r) = 1 + 4\lfloor r\rfloor + \sum^{\lfloor r\rfloor}_{i = 1} \lfloor \sqrt{r^2 - i^2}\rfloor$$

Since $r$ is an integer in this case, I didn't bother much about the precision.

Here is the code I wrote.

long long N(int r){
    long long s = 0;
    for(int i = 1; i<=r; i++) s+=(int)sqrt(r*r-i*i);
    s*=4;
    s+=1+4*r;
    return s;
}

This function worked well for small integers but failed for larger ones. I can't figure out why.

I inspected accepted submissions from other coders and I found out some of them used a simplified version of $N(n) - N(n-1)$, more precisely

$$N(n) - N(n-1) = 4\lfloor n\sqrt 2\rfloor$$

which I tried to derive and couldn't.

I am more interested in knowing how to simplify to get the expression but if anyone understands why the code fails, I'd really appreciate that as well. Thanks.

Answer 1

If your integers are stored as $B$ bits long, then you need r to be only $B/2$ bits or less, i.e. $r \leq 2^{B/2 - 1}$. (The minus one is because you are using signed integers.) Otherwise you will get integer overflow when you compute $r * r$ and the answer won't be correct. Using doubles (long floats) instead of integers won't really help either, because you won't have enough precision to get $r*r - i*i$ when $r$ and $i$ are both large, e.g. when you try to set $i = r-1$ and $r$ is large you will actually get $i*i = r*r$ so the expression will evaluate to zero.

The other possibilities are that when you convert r*r - i*i to a floating point to compute the square root, the squared value might not fit precisely into the bits of mantissa precision. So actually you might need $r$ to be a few orders of magnitude less than $2^{B/2}$. Also, when you convert to a floating point, it's possible that when you compute the square root you will get a floating point answer slightly smaller than the true integer answer when the expression under the square root is a perfect integer square. Then when you cast to integer, your answer will be 1 less than it should be. To test for this and fix it, if the integer under the square-root is $A$ and you compute the floored square-root to be $B$, then you should have $A - B^2 \leq 2B$, or equivalently $(B+1)^2 > A$ (all integer arihmetic). If not, then add one to $B$.