16
\$\begingroup\$

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.

\$\endgroup\$
2

25 Answers 25

9
\$\begingroup\$

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

\$\endgroup\$
4
  • \$\begingroup\$ Oh hey, I didn't know about i:, I am so stealing that, thanks! \$\endgroup\$
    – J B
    Apr 3, 2011 at 16:33
  • \$\begingroup\$ @J B: Yeah, well... I'm stealing >:. derp \$\endgroup\$ Apr 3, 2011 at 18:30
  • \$\begingroup\$ I wish I understood caps well enough to steal those too O:-) \$\endgroup\$
    – J B
    Apr 3, 2011 at 18:38
  • 1
    \$\begingroup\$ 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! :) \$\endgroup\$
    – anon
    May 19, 2016 at 18:23
5
\$\begingroup\$

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!

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

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
\$\endgroup\$
4
\$\begingroup\$

Python 55 Chars

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

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.

\$\endgroup\$
0
3
\$\begingroup\$

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
\$\endgroup\$
2
\$\begingroup\$

Haskell, 44 bytes

f n|w<-[-n..n]=sum[1|x<-w,y<-w,x*x+y*y<=n*n]
\$\endgroup\$
3
  • \$\begingroup\$ I'm new to Haskell: How can you write w<-[-n..n] where (usually) there is a boolean value? \$\endgroup\$
    – flawr
    May 12, 2016 at 17:40
  • 1
    \$\begingroup\$ @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. \$\endgroup\$
    – xnor
    May 13, 2016 at 4:55
  • \$\begingroup\$ Thanks, I was not aware of this this thread! \$\endgroup\$
    – flawr
    May 13, 2016 at 7:43
2
\$\begingroup\$

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
\$\endgroup\$
1
  • 1
    \$\begingroup\$ 12 bytes \$\endgroup\$
    – Shaggy
    Feb 8, 2019 at 11:13
1
\$\begingroup\$

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)
\$\endgroup\$
1
\$\begingroup\$

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;
}
\$\endgroup\$
1
+100
\$\begingroup\$

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.
\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

Scala, 55 bytes

Try it online!

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

JavaScript (ES7), 42 bytes

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

Try it online!

\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$
2
  • \$\begingroup\$ This is quite an old question, are you sure this answer would have worked at the time? \$\endgroup\$
    – Blue
    May 11, 2016 at 17:43
  • \$\begingroup\$ @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. \$\endgroup\$
    – MattPutnam
    May 11, 2016 at 17:47
0
\$\begingroup\$

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.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ 2~SquaresR~k~Sum~{k,0,#^2}& to make it shorter \$\endgroup\$
    – buttercrab
    Feb 10, 2019 at 6:33
0
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

Stax, 11 bytes

ä÷²M╨⌐■╝^₧░

Run and debug it

\$\endgroup\$
0
\$\begingroup\$

Pyke, 14 bytes

QFXQX-_,B)s}}h

Try it here!

\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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!

\$\endgroup\$
5
  • \$\begingroup\$ 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. \$\endgroup\$
    – vengy
    Jan 12 at 20:13
  • \$\begingroup\$ 111 bytes \$\endgroup\$
    – ceilingcat
    Jan 13 at 11:07
  • \$\begingroup\$ @ceilngcat Is there a way to make it even shorter? I've asked the question here. Thanks. \$\endgroup\$
    – vengy
    Jan 13 at 14:07
  • 1
    \$\begingroup\$ 73 bytes \$\endgroup\$
    – ceilingcat
    Jan 13 at 21:02
  • \$\begingroup\$ @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. \$\endgroup\$
    – vengy
    Jan 13 at 21:07
0
\$\begingroup\$

APL (Dyalog Unicode) (SBCS), 28 bytes

{1+4×⍵++/,(×⍨⍵)≥+/¨×⍨∘.,⍨⍳⍵}
{                          } 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
 1+4×⍵+                      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!

\$\endgroup\$
0
\$\begingroup\$

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

\$\endgroup\$
0
\$\begingroup\$

APL(NARS), 25 chars

{1+4×+/⌊√(⍵*2)-¨2*⍨¯1+⍳⍵}

test:

  f←{1+4×+/⌊√(⍵*2)-¨2*⍨¯1+⍳⍵}
  f 0
1
  f 1
5
  f 3
29
  f 10
317
  f 1000
3141549
  f 2000
12566345
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.