Comment by tzs

I had a go at the circle one. What I tried was starting with something very straightforward (pseudocode):

  for each x from -r to r
    find y that minimizes abs(x^2 + y^2 - r^2)
    plot(x,y)

Finding y could be done by taking sqrt(r^2 - x^2) and then taking whichever for floor or ceil of that gives less error. But I assume they probably don't want sqrt. We could find y without using sqrt by doing some kind of search--say start with 0 and increment checked x^2 + y^2 - r^2 until we find where that crosses 0 and then take whichever y made it closes to 0. But that will be even slower than sqrt.

But what if we take advantage when we are trying to find the y for x+1 that we already have found the y that minimizes the error at x? Say we wrote a next_y(y, e) function that takes the y that was used for x and the error e that would be the error if we also used y for x+1 and that function returns the y that would minimize the error at x+1.

That's pretty easy (Python):

  def next_y(y, e):
      if e < 0:       # need to increase y
          delta = 1 + 2*y
          while e < 0:
              if e + delta >= 0:
                  if abs(e+delta) < abs(e):
                      return y+1, e+delta
                  else:
                      return y, e
              else:
                  e += delta
                  y += 1
                  delta += 2
      elif e > 0:     # need to decrease y
          delta = 1 - 2*y
          while e > 0:
              if e + delta <= 0:
                  if abs(e+delta) < abs(e):
                      return y-1, e+delta
                  else:
                      return y, e
              else:
                  e += delta
                  y -= 1
                  delta += 2
      else:
          return y, e

Here's how it is used:

def circle(r): x = -r y = 0 e = 0 print(f'{x},{y}') for i in range(2r): e += 2x + 1 x += 1 y, e = next_y(y, e) print(f'{x},{y}')

Here are some half circles drawn with it: https://imgur.com/a/5aYzPqS

The basic idea is that when you increase x by 1 you increase x^2 by 2x+1, and so (x+1, y) would have error 2x+1 more than (x, y). You then need to change y to compensate.

Changing y by k changes y^2 by 2yk + k^2. Changing k by 1 changes the amount that y^2 changes by 2y + 2k + 1. Note that 2y + 2k + 1 goes up by 2 every time k goes up. In other words if you look at the sequence y^2, (y+1)^2, (y+2)^2, ... the third order diffs are 2. So to see how consecutive changes to y affect y, we can just keep track of the adjusted e and the current second order diff. Then for each consecutive y we can add the second order diff in to update the adjusted e to for the next y, and add the third order diff (the constant 2) into the second order diff.

I split next_y into two cases depending on whether we need to increase y or decrease y. There is probably some way to combine them but it is late and I'm half asleep. Oh, and I realize half of the abs() calls can be removed. I thought it looked clearer with them.

For a radius 50 half circle here is how times it took N tries to find the right y:

   3 0
  68 1
  18 2
   6 3
   2 4
   1 5
   2 10

i.e., for 68 values of x, the first y it looked at was the right one. Here are the numbers for a radios 300 half circle:

   3 0
 410 1
 121 2
  35 3
  13 4
   7 5
   2 6
   3 7
   2 8
   2 11
   1 24
   1 25

That was a fun little exercise. It has two multiplies, but they are both by 2 so could easily be replaced by add or shift.

An improvement would be to make more use of symmetry. The curve looks best when x is between -r/2 and r/2. It would be better to draw just those parts and then use symmetry to fill the rest.