# Code-Golf: Lattice Points inside a Circle

The following picture shows the problem: Write a function that, given an integer as the circle radius, calculates the number of lattice points inside the centered circle (including the boundary).

The image shows:

f = 5  (blue points)
f = 13 (blue + red points)


f    = 29
f   = 317
f = 3,141,549
f = 12,566,345


Should have a reasonable performance. Let's say less than a minute for f.

Shortest code wins. Usual Code-Golf rules apply.

Please post the calculation and timing of f as an example.

• oeis.org/A328 May 11, 2016 at 21:58
• May 9, 2018 at 13:57

## J, 2119 18

+/@,@(>:|@j./~@i:)


Builds complexes from -x-xj to x+xj and takes magnitude.

Edit: With >:

Edit 2: With hook and monadic ~. Runs a few times slower for some reason, but still 10-ish seconds for f(1000).

• Oh hey, I didn't know about i:, I am so stealing that, thanks!
– J B
Apr 3, 2011 at 16:33
• @J B: Yeah, well... I'm stealing >:. derp Apr 3, 2011 at 18:30
• I wish I understood caps well enough to steal those too O:-)
– J B
Apr 3, 2011 at 18:38
• This answer is depressingly short (to someone who's never bothered to learn a short and/or golfing lang) >:. But hey, that's a cool answer! :)
– anon
May 19, 2016 at 18:23

## J, 27 21

3 :'+/,y>:%:+/~*:i:y'


Very brutal: computes sqrt(x²+y²) over the [-n,n] range and counts items ≤n. Still very acceptable times for 1000.

Edit: i:y is quite a bit shorter than y-i.>:+:y. Thanks Jesse Millikan!

• Ha! That was the idea behind asking a decent performance! Just curious: What is the timing for 1000? Apr 3, 2011 at 16:11
• @belisarius: 0.86s. On 10-year old hardware. 3.26s for 2000.
– J B
Apr 3, 2011 at 16:28

## Ruby 1.9, 62 58 54 characters

f=->r{1+4*eval((0..r).map{|i|"%d"%(r*r-i*i)**0.5}*?+)}


Example:

f
=> 3147833

t=Time.now;f;Time.now-t
=> 0.003361411


Python 55 Chars

f=lambda n:1+4*sum(int((n*n-i*i)**.5)for i in range(n))

• f=lambda n:1+4*sum(int((n*n-i*i)**.5)for i in range(n)) is 17 characters shorter. Apr 3, 2011 at 14:51

f n=1+4*sum[floor$sqrt$n*n-x*x|x<-[0..n]]


Counts points in the quadrant x>=0, y>0, multiplies by 4, adds 1 for the center point.

f n|w<-[-n..n]=sum[1|x<-w,y<-w,x*x+y*y<=n*n]

• I'm new to Haskell: How can you write w<-[-n..n] where (usually) there is a boolean value? May 12, 2016 at 17:40
• @flawr These are pattern guards, which succeed if a pattern is matched, but can be used in golfing as a shorter let. See this tip.
– xnor
May 13, 2016 at 4:55
• Thanks, I was not aware of this this thread! May 13, 2016 at 7:43

# Uiua, 13 bytes

∧+1×4⌊√×⊃+-⇡.


Try it online!

Uses the formula on A057655 $$\ 1+4\sum_{k=0}^{n}{\left\lfloor\sqrt{n^2-k^2}\right\rfloor} \$$, and uses the fact that k=n part can be removed.

∧+1×4⌊√×⊃+-⇡.    input: integer n
⇡.    keep n and generate the range for k
×⊃+-      (n+k) * (n-k) for each k
⌊√          sqrt, floor
∧+1×4            multiply 4, sum, and add 1


## Python 2, 48 bytes

f=lambda n,i=0:i>n or(n*n-i*i)**.5//1*4+f(n,i+1)


Like fR0DDY's solution, but recursive, and returns a float. Returning an int is 51 bytes:

f=lambda n,i=0:i>n or 4*int((n*n-i*i)**.5)+f(n,i+1)


# C (gcc), 60 bytes

r,a;f(x){for(a=r=x*x;a--;)r-=hypot(a%x+1,a/x)>x;x=4*r+1;}


Try it online!

Loops over the first quadrant, multiplies the result by 4 and adds one. Slightly less golfed

r,a;
f(x){
for(a=r=x*x;a--;)
r-=hypot(a%x+1,a/x)>x;
x=4*r+1;
}


# APL (Dyalog Extended), 14 bytes

{≢⍸⍵≥|⌾⍀⍨⍵…-⍵}


Try it online!

Despite lacking the i: (inclusive range from -n to n) builtin of J, APL Extended has shorter syntax in other areas.

{≢⍸⍵≥|⌾⍀⍨⍵…-⍵}            Monadic function taking an argument n.
⍵…-⍵             n, n-1, ..., -n
⌾⍀                   Make a table of complex numbers
(equivalent to ∘.{⍺+1J×⍵} in Dyalog APL)
⍨                  with both real and imaginary parts from that list.
|                       Take their magnitudes.
⍵≥                        1 where a magnitude are is at most n, and 0 elsewhere.
⍸                           Get all indices of truthy values.
≢                            Find the length of the resulting list.


# Japt-x, 12 bytes

òUn)ï Ëx²§U²


Try it online!

Explanation:

òUn)            #Get the range [-input ... input]
ï           #Get each pair of numbers in that range
Ë         #For each pair:
x        # Get the sum...
²       # Of the squares
§      # Check if that sum is less than or equal to...
U²    # The input squared
#Output the number of pairs that passed the check

• 12 bytes Feb 8, 2019 at 11:13

# PHP, 85 83 bytes

The code:

function f($n){for($x=$n;$x;$c+=$x,$y++)for(;$n*$n<$x*$x+$y*$y;$x--);return$c*4+1;}  Its outcome (check https://3v4l.org/bC0cY for multiple PHP versions): f(1001)=3147833 time=0.000236 seconds.  The ungolfed code: /** * Count all the points having x > 0, y >= 0 (a quarter of the circle) * then multiply by 4 and add the origin. * * Walk the lattice points in zig-zag starting at ($n,0) towards (0,$n), in the * neighbourhood of the circle. While outside the circle, go left. * Go one line up and repeat until$x == 0.
* This way it checks about 2*$n points (i.e. its complexity is linear, O(n)) * * @param int$n
* @return int
*/
function countLatticePoints2($n) {$count = 0;
// Start on the topmost right point of the circle ($n,0), go towards the topmost point (0,$n)
// Stop when reach it (but don't count it)
for ($y = 0,$x = $n;$x > 0; $y ++) { // While outside the circle, go left; for (;$n * $n <$x * $x +$y * $y;$x --) {
// Nothing here
}
// ($x,$y) is the rightmost lattice point on row $y that is inside the circle // There are exactly$x lattice points on the row $y that have x > 0$count += $x; } // Four quarters plus the center return 4 *$count + 1;
}


A naive implementation that checks $n*($n+1) points (and runs 1000 times slower but still computes f(1001) in less than 0.5 seconds) and the test suite (using the sample data provided in the question) can be found on github.

## JavaScript (ES6), 80 bytes

n=>(a=[...Array(n+n+1)].map(_=>i--,i=n)).map(x=>a.map(y=>r+=x*x+y*y<=n*n),r=0)|r


Alternative version, also 80 bytes:

n=>[...Array(n+n+1)].map((_,x,a)=>a.map((_,y)=>r+=x*x+(y-=n)*y<=n*n,x-=n),r=0)|r


ES7 version, also 80 bytes:

n=>[...Array(n+n+1)].map((_,x,a)=>a.map((_,y)=>r+=(x-n)**2+(y-n)**2<=n*n),r=0)|r


# Clojure/ClojureScript, 85 chars

#(apply + 1(for[m[(inc %)]x(range 1 m)y(range m):when(<=(+(* x x)(* y y))(* % %))]4))


Brute forces the first quadrant, including the y axis but not the x axis. Generates a 4 for every point, then adds them together with 1 for the origin. Runs in under 2 seconds for input of 1000.

Abuses the hell out of for to define a variable and save a few characters. Doing the same to create an alias for range doesn't save any characters (and makes it run significantly slower), and it seems unlikely that you're going to save anything by making a square function.

• This is quite an old question, are you sure this answer would have worked at the time?
– Blue
May 11, 2016 at 17:43
• @muddyfish I didn't notice the age, just saw it near the top. Clojure predates the question, but I don't know its history enough to know about language changes. May 11, 2016 at 17:47

## Mathematica, 35 characters

f[n_]:=Sum[SquaresR[2,k],{k,0,n^2}]


Lifted from https://oeis.org/A000328

https://reference.wolfram.com/language/ref/SquaresR.html

SquaresR[2,k] is the number of ways to represent k as the sum of two squares, which is the same as the number of lattice points on a circle of radius k^2. Sum from k=0 to k=n^2 to find all the points on or inside a circle of radius n.

• 2~SquaresR~k~Sum~{k,0,#^2}& to make it shorter Feb 10, 2019 at 6:33

# Tcl, 111 bytes

lassign {1001 0 -1} r R x
while {[incr x]<$r} {set R [expr {$R+floor(sqrt($r*$r-$x*$x))}]}
puts [expr {4*$R+1}]  Simple discrete x loop over quadrant I, counting largest y using the Pythagorean Theorem at each step. Result is 4 times the sum plus one (for the center point). The size of the program depends on the value of r. Replace {1001 0 -1} with "$argv 0 -1" and you can run it with any command-line argument value for r.

Computes f(1001) → 3147833.0 in about 1030 microseconds, AMD Sempron 130 2.6GHz 64-bit processor, Windows 7.

Obviously, the larger the radius, the closer the approximation to PI: f(10000001) runs in about 30 seconds producing a 15-digit value, which is about the precision of a IEEE double.

# Stax, 11 bytes

ä÷²M╨⌐■╝^₧░


Run and debug it

## Pyke, 14 bytes

QFXQX-_,B)s}}h


Try it here!

## Pascal, 128 B

This just walks the lattice grid and checks whether the distance to the origin is less than or equal to the radius.

type Z=integer;function f(r:Z):Z;var x,y,n:Z;begin
n:=0;for x:=-r to r do for y:=-r to r do n:=n+ord(sqrt(x*x+y*y)<=r);f:=n
end;


User time on a busy Linux x86‑64 machine for calculating f(1001) = 3147833: ca. 80 ms. Calculate just the points in one quadrant to cut the time.

# Scala, 55 bytes

Try it online!

n=>(0 until n).map(i=>Math.sqrt(n*n-i*i).toInt).sum*4+1