How far off is "about half a pixel"?
An experiment and a formal proof in Lean

Preface

When I found my circle algorithm in 1985/86, I was a 16-year-old pupil with a Commodore 64. It ran at 985 kHz, had no multiply instruction, and every operation I could save made a slow computer look fast. That was all that mattered to me. I never proved the method. I built it, looked at the screen and saw that it was round.

One thing I did notice back then: my circles seemed to be off by about half a pixel, at the diagonal. For 40 years I simply accepted that, because for most circles on a raster display half a pixel makes no difference at all.

In November 2026 I finally checked it, together with Claude, an AI assistant by Anthropic: first with an experiment over all radii from 1 to 1000, then with a formal proof in the proof assistant Lean. This page shows what came out. The history of the algorithm and the comparison with other methods are on the main page Algorithms.

The algorithm

This is the version from Wikipedia (Midpoint circle algorithm, section Jesko’s method), identical to the C program on the Algorithms page. It draws one octant, the other seven are mirrored.

Five operations per step, no multiplication. The start value r/16 is just a shift (r >> 4).

t1 = r / 16          // r >> 4
x  = r
y  = 0
Repeat Until x < y
    Pixel (x, y) and all symmetric pixels
    y  = y + 1
    t1 = t1 + y
    t2 = t1 - x
    If t2 >= 0
        t1 = t2
        x  = x - 1

1. The experiment

First question: what does correct mean for a rasterized circle? I used the most common definition. In every row y, the ideal pixel is the integer x closest to √(r² − y²). This is exactly what the classic midpoint algorithm draws, and its pixels are never more than 0.5 px away from the true circle.

All radii from 1 to 1000 went through Jesko’s Method, row by row in the octant (354,715 rows), and every pixel was compared with the ideal one.

  • In 26.4 % of the rows the pixel lies exactly one position further out than the ideal pixel.
  • Never further in, and never more than one pixel.
  • The largest radial error is 0.91 px (ideal circle: 0.50 px). My circles are a touch too large.
  • Only r = 1, 2, 3, 5 and 10 are identical to the ideal circle. The first differences: r = 4 at (4, 2) and r = 6 at (5, 4).
Jesko's Methodideal pixel- - - exact circle
0011223344556677(0, 6): both(1, 6): both(2, 6): both(3, 5): both(4, 4): ideal circle only(4, 5): Jesko's Method only(5, 3): both(5, 4): Jesko's Method only(6, 0): both(6, 1): both(6, 2): both45°
r = 6, first quadrant. Near the diagonal the method sets (5, 4) and (4, 5) instead of (4, 4). All other pixels are identical.

Where the error sits

The deviation depends on the angle. It is largest right next to the axes and smallest at the diagonal:

anglerows one pixel further outmean radial errormax radial error
0–9° (next to the axis)31.6 %+0.34 px0.91 px
9–18°33.3 %+0.32 px0.85 px
18–27°27.2 %+0.25 px0.76 px
27–36°20.5 %+0.18 px0.66 px
36–45° (diagonal)16.5 %+0.11 px0.53 px

For comparison: the ideal circle is never more than 0.50 px off, and on average it is not off at all. My circles are slightly bulged next to the axes, a tiny step towards a rounded square.

That surprised me at first, because on the axis the radius is hit exactly. And it is: the pixel (r, 0) is always correct. But right after it the circle is almost vertical. For r = 1000 the true x falls by only y²/2000 per row, so it takes 32 rows until it drops below 999.5 and the ideal circle steps inward. Jesko’s Method steps inward only in row 43. In rows 32 to 42 its pixel stays at x = 1000, up to 0.88 px outside. Near the axis a shift of the decision threshold turns almost completely into radial error. Towards the diagonal the y + ½ in the test cancels part of it (see the closed form below).

Jesko's Methodideal circle- - - 7/16 − ½·sin θ (closed form, see below)
-0.10+0.1+0.2+0.3+0.4+0.50°5°10°15°20°25°30°35°40°45°angle from the x axismean radial error (px)Jesko's Methodideal circle
Mean signed distance between pixel centre and true circle in 3° steps, radii 1–1000. The first 3° next to the axis are left out: there the ideal pixel stays at x = r for several rows, so its average says little.

Why I saw it at the diagonal

With small radii, as on a screen in 1986, the few deviations show up as a visible step near 45°. r = 6 above is the typical case. The systematic bulge next to the axes only becomes measurable with large radii, and there it disappears in the picture. So about half a pixel was right in magnitude (the systematic shift is at most 0.44 px), only the place was mixed up.

2. The closed form

Why does it behave like this? The loop can be solved. t1 adds up y and subtracts the old x at every step inward, so before every pass through the loop:

2·t1 = 2⌊r/16⌋ + y(y+1) + x(x+1) − r(r+1)

From this the decision follows directly. With y as the new row:

x is decremented  ⇔  x(x−1) + y(y+1) ≥ r(r+1) − 2⌊r/16⌋
                  ⇔  (x − ½)² + (y + ½)² ≥ r² + r − 2⌊r/16⌋ + ½  ≈  (r + 7/16)²

So Jesko’s Method is a midpoint test with two small shifts:

  1. It tests the point (x − ½, y + ½) instead of (x − ½, y). The reason: t1 += y adds the new y, that is yold + 1 instead of yold + ½.
  2. It tests against the radius r + 7/16 instead of r. That comes from the start value r/16.

Together this moves the drawn circle outward by about 7/16 − ½·sin θ pixels on average: 0.44 px at the axis, 0.08 px at the diagonal. The dashed line in the chart above is exactly this formula, and it matches the measurement.

Getting rid of the error completely would need the half step in y, and that costs the very operation the method saves. It is a trade, not a bug.

3. A better start value

In 1986 r/16 was a gut feeling. It looked good, so I kept it. The closed form shows what a start value t1 = k·r really does: the drawn circle moves outward by about

½ − k − ½·sin θ   pixels

With k = 1/16 that is the 7/16 − ½·sin θ from above. The part ½·sin θ comes from the y + ½ in the test, and no constant can remove it. But the start value can centre it: with k ≈ 0.32 the shift runs from +0.18 px next to the axis to −0.18 px at the diagonal. The start value is computed once per circle, not per pixel, so it costs nothing in the loop. Two shifts and one addition give 5r/16 = 0.3125·r:

start valueshift axis → diagonalrows further outrows further inmax radial error
t1 = 0+0.50 → +0.15 px32.4 %0.0 %0.98 px
t1 = r>>4 = r/16 (1986)+0.44 → +0.08 px26.4 %0.0 %0.91 px
t1 = r>>3 = r/8+0.38 → +0.02 px20.0 %0.0 %0.85 px
t1 = r>>2 = r/4+0.25 → −0.10 px8.2 %1.8 %0.73 px
t1 = (r>>2) + (r>>4) = 5r/16+0.19 → −0.17 px4.5 %4.4 %0.67 px

With t1 = (r>>2) + (r>>4) only 9 % of the rows differ from the ideal circle instead of 26 %, and the largest error drops from 0.91 to 0.67 px. The remaining deviations are split evenly between outside and inside. About 9 % is the floor; no start value I tried gets below it, because of the angle-dependent part.

If the circle should never lie inside the ideal one, t1 = r>>3 is the best simple choice: 20 % instead of 26 %, and still never inside (checked up to r = 3000).

All other results and the proof below refer to the published version with r/16.

4. The proof in Lean

An experiment up to r = 1000 is not a proof. Lean is a proof assistant: you write definitions and theorems, and Lean checks every single step of every proof. With the library Mathlib it knows integers and inequalities, and tactics like ring, linear_combination and nlinarith do the algebra on their own.

The file models the loop exactly as in the pseudocode and proves four theorems, for every integer radius r, not just up to 1000:

inv_start, inv_stepThe closed form above holds at the start and survives every step. So t1 has an exact meaning before every pass, by induction.
decides_iffThe decision “x − 1 or not” is exactly the shifted midpoint test (x − ½)² + (y + ½)² ≥ r² + r − 2⌊r/16⌋ + ½.
never_insideWhenever Jesko’s Method steps one pixel inward, the ideal circle (midpoint test) steps inward at the same place as well. The side condition y ≤ r − 2⌊r/16⌋ holds in the whole octant.

#print axioms never_inside answers with [propext, Classical.choice, Quot.sound]. These are Lean’s three standard axioms. No sorry, so no step was skipped. The two #eval lines run the algorithm inside Lean and give the same pixels as the C program.

To check it yourself, paste the file into live.lean-lang.org and wait until Mathlib has loaded. Nothing may be underlined in red.

import Mathlib

/-!
# Jesko's Method (1986)

Circle rasterization in one octant with 5 operations per step, as in the
Wikipedia article "Midpoint circle algorithm":

    t1 = r / 16;  x = r;  y = 0
    Repeat Until x < y
        Pixel (x, y)
        y  = y + 1
        t1 = t1 + y
        t2 = t1 - x
        If t2 >= 0:  t1 = t2;  x = x - 1

Source: https://schwarzers.com/?page_id=209
Checked with Lean 4 + Mathlib on live.lean-lang.org, November 2026.
-/

structure State where
  x  : Int
  y  : Int
  t1 : Int
deriving Repr

/-- One pass through the loop. `s.t1 + (s.y + 1) - s.x` is the t2 of the pseudocode. -/
def step (s : State) : State :=
  if s.t1 + (s.y + 1) - s.x ≥ 0 then
    { x := s.x - 1, y := s.y + 1, t1 := s.t1 + (s.y + 1) - s.x }
  else
    { x := s.x,     y := s.y + 1, t1 := s.t1 + (s.y + 1) }

def start (r : Int) : State := { x := r, y := 0, t1 := r / 16 }

/-- The pixels in the octant. `fuel` only bounds the loop, so that Lean can
    see that it terminates. -/
def pixels (r : Int) : List (Int × Int) :=
  go (start r) (r.toNat + 1)
where
  go (s : State) : Nat → List (Int × Int)
    | 0     => []
    | n + 1 => if s.x < s.y then [] else (s.x, s.y) :: go (step s) n

/-- The ideal circle: in each row, the x closest to √(r² − y²). -/
def idealX (r y : Int) : Int :=
  let s := r * r - y * y
  let x : Int := (Nat.sqrt s.toNat : Int)
  if 4 * x * x + 4 * x + 1 < 4 * s then x + 1 else x

/-! ## Part 1: Trying it out (this is not a proof yet) -/

#eval pixels 10
-- [(10, 0), (10, 1), (10, 2), (10, 3), (9, 4), (9, 5), (8, 6), (7, 7)]

#eval (pixels 6).map fun (x, y) => (x, y, idealX 6 y)
-- [(6, 0, 6), (6, 1, 6), (6, 2, 6), (5, 3, 5), (5, 4, 4)]   ← (5,4) instead of (4,4)

/-! ## Part 2: Proving (holds for *all* radii) -/

/-- What t1 means after every step: the closed form.
    (German "Invariante" = invariant.) -/
def Invariante (r : Int) (s : State) : Prop :=
  2 * s.t1 = 2 * (r / 16) + s.y * (s.y + 1) + s.x * (s.x + 1) - r * (r + 1)

/-- The closed form holds at the start. -/
theorem inv_start (r : Int) : Invariante r (start r) := by
  show 2 * (r / 16) = 2 * (r / 16) + 0 * (0 + 1) + r * (r + 1) - r * (r + 1)
  ring

/-- Every step preserves it (induction step). -/
theorem inv_step (r : Int) (s : State) (h : Invariante r s) : Invariante r (step s) := by
  unfold Invariante at *
  by_cases hc : s.t1 + (s.y + 1) - s.x ≥ 0
  · rw [step, ite_eq_left hc]
    dsimp only
    linear_combination h
  · rw [step, ite_eq_right hc]
    dsimp only
    linear_combination h

/-- The decision "x−1 or not" can be written without t1:
    (x−½)² + (y'+½)² ≥ r² + r − 2⌊r/16⌋ + ½  with  y' = y + 1. -/
theorem decides_iff (r : Int) (s : State) (h : Invariante r s) :
    (s.t1 + (s.y + 1) - s.x ≥ 0) ↔
      s.x * (s.x - 1) + (s.y + 1) * (s.y + 2) ≥ r * (r + 1) - 2 * (r / 16) := by
  unfold Invariante at h
  constructor <;> intro hc <;> nlinarith

/-- Never inside: whenever Jesko's method steps one pixel inward in row y,
    the ideal circle (midpoint test (x−½)² + y² > r²) does so as well.
    The condition `hy` holds in the whole octant, since there y ≤ 0.71·r. -/
theorem never_inside (r x y : Int) (hy : y ≤ r - 2 * (r / 16))
    (hj : x * (x - 1) + y * (y + 1) ≥ r * (r + 1) - 2 * (r / 16)) :
    x * (x - 1) + y * y ≥ r * r := by
  nlinarith

#print axioms never_inside
-- 'never_inside' depends on axioms: [propext, Classical.choice, Quot.sound]

How it went

The mathematics, meaning the invariant and the three proof ideas, went through on the first attempt. The errors were small and of a predictable kind:

  • When I pasted the file into the browser, the first line import Mathlib got lost. Without it Lean knows none of the tactics, and the result was a page full of unknown tactic.
  • Claude had named the invariant Inv. That name already exists in Lean, as the type class for inverses (1/x). Lean reported the collision at once, and the definition was renamed to Invariante (German for invariant).
  • Lean warned that if_pos and if_neg are deprecated and suggested ite_eq_left and ite_eq_right. The file above uses the new names.

That is the whole point of a proof assistant: I do not have to trust the author of a proof, neither myself nor an AI. Lean checks it.

5. What is still open

Lean has proven what the theorems say, and nothing more. The statement I would really like is global: in no row of any circle does Jesko’s Method lie inside the ideal circle. never_inside is the local step for it. The full theorem needs an induction over the whole run that follows both algorithms side by side.

Until then, “never inside” and “never more than one pixel” are experimental results for r ≤ 1000, not theorems.

Downloads and links

/Jesko Schwarzer
2026-Nov-16