Code-Golf: Lattice Points inside a Circle

Question

The following picture shows the problem:

enter image description here

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[1] = 5 (blue points)
f[2] = 13 (blue + red points) 

other values for your checking/debugging:

f[3] = 29
f[10] = 317
f[1000] = 3,141,549
f[2000] = 12,566,345 

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

Shortest code wins. Usual Code-Golf rules apply.

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

• msh210: oeis.org/A328
• user202729: Triangular version.

Answer 1

J, (削除) 21 (削除ここまで) (削除) 19 (削除ここまで) 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).

• J B: Oh hey, I didn't know about i:, I am so stealing that, thanks!
• Jesse Millikan: @J B: Yeah, well... I'm stealing >:. derp
• J B: I wish I understood caps well enough to steal those too O:-)
• anon: 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! :)

Answer 2

J, (削除) 27 (削除ここまで) 21

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

Very brutal: computes sqrt(x2+y2) 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!

• Dr. belisarius: Ha! That was the idea behind asking a decent performance! Just curious: What is the timing for 1000?
• J B: @belisarius: 0.86s. On 10-year old hardware. 3.26s for 2000.

Answer 3

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[1001]
=> 3147833
t=Time.now;f[1001];Time.now-t
=> 0.003361411

Answer 4

Python 55 Chars

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

• Ventero: f=lambda n:1+4*sum(int((n*n-i*i)**.5)for i in range(n)) is 17 characters shorter.

Answer 5

Haskell, 41 bytes

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.

Answer 6

Uiua, 13 bytes

×ばつ⊃+-⇡.

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.

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

Answer 7

Haskell, 44 bytes

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

• flawr: I'm new to Haskell: How can you write w<-[-n..n] where (usually) there is a boolean value?
• xnor: @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.
• flawr: Thanks, I was not aware of this this thread!

Answer 8

Japt -x, 12 bytes

òUn)ï Ëx2§U2

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...
 2 # Of the squares
 § # Check if that sum is less than or equal to...
 U2 # The input squared
 #Output the number of pairs that passed the check

• Shaggy: 12 bytes

Answer 9

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)

Answer 10

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

Answer 11

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;
}

Answer 12

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 ×ばつ⍵} 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.

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

Answer 14

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

Answer 15

Scala, 55 bytes

Try it online!

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

Answer 16

JavaScript (ES7), 42 bytes

f=(n,k=n)=>k--?((n*n-k*k)**.5<<2)+f(n,k):1

Try it online!

Answer 17

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.

• Blue: This is quite an old question, are you sure this answer would have worked at the time?
• MattPutnam: @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.

Answer 18

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.

• buttercrab: 2~SquaresR~k~Sum~{k,0,#^2}& to make it shorter

Answer 19

Stax, 11 bytes

ä÷2M╨⌐■しかく╝^₧░

Run and debug it

Answer 20

Pyke, 14 bytes

QFXQX-_,B)s}}h

Try it here!

Answer 21

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.

Answer 22

C (gcc), 116 bytes

a,x,y;c(r){for(x=-r;x<=r;x++)for(y=-r;y<=r;a+=x*x+y*y<=r*r,y++);return a;}main(r){scanf("%u",&r);printf("%d",c(r));}

How it works

This inefficient method draws a square around the circle then iterates through all lattice points \$(x,y)\$ within it and checking if \$x^2+y^2 \le r^2 \$.

Try it online!

• vengy: Hello, I'd like to shorten my answer above by using this tio.run technique from this C example. Any tips to make it work so it results in fewer bytes? Thanks.
• ceilingcat: 111 bytes
• vengy: @ceilngcat Is there a way to make it even shorter? I've asked the question here. Thanks.
• ceilingcat: 73 bytes
• vengy: @ceilingcat Thanks for those saved bytes and the TIO example. Is there a way to remove that return statement? I think there's a way to resolve that using a code golf that returns the value such as x=a.

Answer 23

APL (Dyalog Unicode) (SBCS), 28 bytes

×ばつ⍵++/,(×ばつ⍨⍵)≥+/ ×ばつ⍨∘.,⍨⍳⍵}
{ } dfn
 ∘.,⍨⍳⍵ get cartesian square of 1..n
 ×ばつ⍨ square each half of each pair
 +/ ̈ add each half of each pair
 +/, ≥ count sums greater than
 (×ばつ⍨⍵) the input squared
 ×ばつ⍵+ add the input, multiply by 4, and add 1

Finds the lattice points in one quadrant, then multiplies it by 4 and adds the points on the axes.

Try it online!

Answer 24

05AB1E, 9 bytes

(Ÿn¬sãO@O

Port of @KamilDrakari's Japt answer, so make sure to upvote that answer as well!

Try it online or verify all test cases. (Runs 1001 in about 3.5 seconds on TIO.)

Explanation:

( # Negate the (implicit) input-integer
 Ÿ # Push a list in the range [(implicit) input,-input]
 n # Square each inner value
 ¬ # Push the first item (without popping the list), which is input2
 s # Swap so the list is at the top again
 ã # Cartesian power of 2 to get all possible pairs
 O # Sum all those inner pairs together
 @ # Check for each whether the input2 is >= this value
 O # Sum to get the amount of truthy values
 # (which is output implicitly as result)

Try it online with a step-by-step output.

Answer 25

APL(NARS), 25 chars

×ばつ+/⌊√(⍵*2)- ̈2*⍨ ̄1+⍳⍵}

test:

 ×ばつ+/⌊√(⍵*2)- ̈2*⍨ ̄1+⍳⍵}
 f 0
1
 f 1
5
 f 3
29
 f 10
317
 f 1000
3141549
 f 2000
12566345