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)

other values for your checking/debugging:

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.

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 '11 at 16:33
• @J B: Yeah, well... I'm stealing >:. derp – Jesse Millikan Apr 3 '11 at 18:30
• I wish I understood caps well enough to steal those too O:-) – J B Apr 3 '11 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! :) – Nic Hartley May 19 '16 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? – Dr. belisarius Apr 3 '11 at 16:11
• @belisarius: 0.86s. On 10-year old hardware. 3.26s for 2000. – J B Apr 3 '11 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. – Ventero Apr 3 '11 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? – flawr May 12 '16 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 '16 at 4:55
• Thanks, I was not aware of this this thread! – flawr May 13 '16 at 7:43

JavaScript (ES6), 80 bytes (non-competing because ES6 is too new)

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

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

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 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.

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 '16 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. – MattPutnam May 11 '16 at 17:47

QFXQX-_,B)s}}h

Try it here!

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 – jaeyong sung Feb 10 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.

ä÷²M╨⌐■╝^₧░

Run and debug it