drawing circle without floating point calculation

Question

This is a common interview question (according to some interview sites) but I can find no normal answers on the Internet - some are wrong and some point to complex theory I expect not to be required in an interview (like the Bresenham algorithm).

The question is simple:

The circle equation is: x² + y² = R². Given R, draw 0,0-centered circle as best as possible without using any floating point (no trig, square roots, and so on, only integers)

Answer 1

Bresenham-like algorithms are probably the expected answer, and can be derived without "complex theory". Start from a point (x,y) on the circle: (R,0) and maintain the value d=x^2+y^2-R^2, initially 0. D is the squared distance from the current point to the circle. We increment Y, and decrement X as needed to keep D minimal:

// Discretize 1/8 circle:
x = R ; y = 0 ; d = 0
while x >= y
  print (x,y)
  // increment Y, D must be updated by (Y+1)^2 - Y^2 = 2*Y+1
  d += (2*y+1) ; y++
  // now if we decrement X, D will be updated by -2*X+1
  // do it only if it keeps D closer to 0
  if d >= 0
    d += (-2*x+1) ; x--