On Tue, 18 Jul 2006, Mike Speciner wrote:
Am I missing something? Why do you need square root at all? sqrt(x*x+y*y) < n is the same as x*x+y*y < n*n.
Yes, but don't tell the younger brother. :) Square roots were the limit of his skills, plus sticking with ordinary pythagoras made things easier on the older brother.
Also, you don't need to check every point (an O(n^2) process). If you just follow around the edge of the circle (an O(n) process), you can easily infer the interior points.
Indeed. I was ready to guide him toward my integration solution, where you just calculate the height of the quarter circle at each x, but he came up with a very simple alternative on his own. a. Start at (0,y+1) b. move down until (0,y) is interior (y--) c. move right (x++) d. goto b unless x>=r It was great to watch his expression when he saw how much faster it was than the n^2 solution. -J