Intersecting a circle with the integer lattice Looking for a method to find all the integer coordinates on the edge of a circle using a known radius.
The assumption is that we have a known radius $R$ (e.g. $R=254$). How would you calculate all the available integer points on the circle between $0$ and $90$ degrees?
Is there a Java Package that uses Big Decimal that can be used with the above methodology?
 A: Assuming the center of the circle is the origin (or at least a lattice point), you want integer solutions to $x^2+y^2=N(=R^2=254^2)$, or a Gauß lattice point $x+iy\in\Bbb Z[i]$ of norm $R^2$.
The existence of such solutions depends on the prime factorization of $N$, that corresponds to possible factorizations of $x+iy$.
We can always multiply a solution by $i$ or $-1$ or $-i$ (i.e., swap the $x$ and $y$ and change signs).


*

*Every factor of $2$ in $N$ gives us $1+i$ as a factor of $x+iy$.

*Every prime factor $p$ with $p\equiv 1\pmod 4$ allows an essentially unique solution of $u^2+v^2=p$ and thereby a factor of $u\pm iv$ of $x+iy$.

*Every prime factor $p$ with $p\equiv -1\pmod 4$ does not have such a decomposition. We can only hope that it appears twice or any even number of times (which it does because $N=R^2$ is a prefect square) and then multiply $x+iy$ by $p$ for each $p^2$.


We find the prime factorization of $N$ as $N=254^2=2^2\cdot127^2$.
Following the above, we find exactly the following:
$$x+iy = u\cdot (1+i)^2\cdot 127 \qquad \text{with }u\in\{1,i,-1,-i\} $$
i.e., 
$$ x+iy\in\{254i,-254,-254i,254\}.$$
In other words, one of $x,y$ must be $=0$, the other $=\pm 254$,
there are no non-trivial lattice points.
As you want to restrict to the range from $0°$ to $90°$, we are left wuth $(254,0)$ and $(0,254)$.
A: You only need Big Decimal if $R$ is big. For $R$ not too large, not only can you use ordinary integers, you can brute-force the solution. 
For example, with $R=254,$ just try each integer value of $x$ from $x=0$ to $x=254,$ and set $s = R^2 - x^2.$ Apply the floating-point square root function to that result, that is, take q = sqrt(s), round the return value q to an integer, set $y$ to the rounded value, and then check whether 
$y^2 = R^2 - x^2.$ If it is equal, that value of $(x,y)$ is a point on the circle, otherwise there is no such lattice point with that $x$-coordinate.
You can even avoid floating-point calculations entirely if you just "guess" the value of $y$ each time. When $R=254,$ for $x=0$ you know $y=254,$
and you know that $y$ for the next lattice point will be less, so for
$x=1$ you guess $y=254- 1 = 253$ and see if $(x,y)$ is a lattice point.
Each time you make such a guess, if it turns out $x^2 + y^2 > R^2$
then you decrease $y$ by $1$ and try again with the same $x$;
if $x^2 + y^2 < R^2$ then you keep the same $y$ but increase $x$ by $1$;
and if $x^2 + y^2 = R^2$ then you remember the fact that $(x,y)$
is a lattice point on the circle, and for your next guess you
add $1$ to $x$ and subtract $1$ from $y.$
If you use $64$-bit integers these "brute force" approaches work up to
$R \approx 2{,}000{,}000{,}000,$
although somewhere between $R=254$ and $R = 2{,}000{,}000{,}000$
you might find that the brute-force approach takes so much computing time
that you want to implement the cleverer solution already explained
in another answer (involving the factorization of $R$).
