CODEWITHSUNDEEP
python
user131983
user131983

Reputation: 3927

Number of lattice points in a circle

I am trying to determine the number of lattice points in a Circle i.e. Basically I am trying to find the number of pairs (m,n) such that m^2+n^2 <= r^2, where m and n are both integers. I used the code below to do this, but I get the wrong answer for r = 12, which is supposed to be 441 according to this and I get 121 and I was wondering where I might be wrong:

def latticepoints(N):
    num = 0
    for m in range(0, int(N), 1):
        for n in range(0, int(N), 1):
            if (m**2 + n**2) <= N**2:
                num = num + 1

    return number

print(latticepoints(12))

Edit:

Just solved it. Just needed to change the loops to:

for m in range(-int(N), int(N)+1, 1):
    for n in range(-int(N), int(N)+1, 1):

Thanks

Upvotes: 4

Views: 2512

Answers (1)

alexwlchan
alexwlchan

Reputation: 6098

As you've already noted, the problem is that you're counting lattice points in a single quadrant of the circle. Expanding the range to fix this is one approach; an alternative fix is to take

lattice points = 4 * (lattice points in a single quadrant) - 3

We have to subtract 3 because the first term counts the origin four times.

Since you've already found the bug, here are a few quick comments on other ways to improve your code:

  • range() can take up to three arguments: start, end and step:

    • If supplied with only two arguments, it defaults step to 1
    • If supplied with just one argument, it defaults start to 0 and step to 1

    In general, you should supply as few arguments as you can get away with (letting the defaults do the rest) – this cuts down on visual noise.

    So in the original function, you'd write

    for m in range(int(N)):

    and in the fixed version, you'd write:

    for m in range(-int(N), int(N)):

  • Since your example supplies N as an integer, I'm not sure why you're continuously casting to int(). It would be better to do a single cast to int() at the start of the function, and then remove the rest of the casts. That will cut down on visual noise.

  • The function as supplied throws a NameError. It's counting lattice points in the variable num, but returns number, which hasn't been defined yet. Quick fix is to tidy up the return statement; better would be to use a more descriptive variable name such as lattice_count.

    Note also that you can replace num = num + 1 by num += 1.

  • If m > sqrt(N) or n > sqrt(N), clearly the lattice point (m, n) will fall outside the circle of radius N. As such, you could speed up your loops by only looking at -sqrt(N) <= m <= sqrt(N), and likewise for n.

Upvotes: 2

Related Questions