From: fredh@ix.netcom.com (Fred W. Helenius ) Newsgroups: sci.math Subject: Re: Counting points in a circle Date: 11 Nov 1995 19:38:31 GMT In <47pu8r\$5bf@news.nznet.gen.nz> packrat@nznet.gen.nz (Packrat) writes: >I'm trying to use a square grid of points to measure the area of a >circle (we all have our little hobbies...) by laying the circle on the >grid and counting the points that lie inside the circle. >To make things easier I use a cartesian plane, placing the circle at the >origin and using a grid parallel to both axes. I only count points that >fall _inside_ the circle, ignoring points that lie on the boundary of >the circle (so that, for example, if my radius were 0, my "area" (number >of counted points) would also be 0, not one). A circle of radius 1, for >example, would have only one point within it (the origin), and so have >an "area" of 1, even though there are four points on the edge. >My question is, how fine do I have to make my grid for this method to be >accurate to, say, n decimal places? This is a problem with a lot of history; it's often called "Gauss's lattice point problem". There's a nice description of the problem in Richard Guy's "Unsolved Problems in Number Theory" (2nd ed.); for more information, see the references there. A summary: The number of lattice points within a circle of radius r centered at the origin is approximately pi*r^2. If we call the difference between this ideal value and the actual value h(r), it is conjectured that h(r) is O(r^(1/2 + eps)), for any eps > 0. The best result so far is that h(r) is O(r^(46/73 + eps)), due to Martin Huxley. Hardy and Landau showed that h(r) is _not_ o(r^(1/2) (ln r)^(1/4)). [If the notations are unfamiliar: f(x) is O(g(x)) means that |f(x)| < c g(x) for some constant c, for all x sufficiently large. Loosely speaking, f(x) has the same (or smaller) order of growth as g(x), apart from a constant factor. f(x) is o(g(x)) means lim f(x)/g(x) = 0 as x goes to infinity; so f(x) is, eventually, arbitrarily much smaller than g(x).] -- Fred W. Helenius