TAOCP 7.1.3 Exercise 180
Let F(x,y)=y^{2}-x^{2}-13.
Section 7.1.3: Bitwise Tricks and Techniques
Exercise 180. ▶ [M24] [M24] Digitize the hyperbola y2 = x2 + 13 by hand, for 0 < y ≤7.
Verified: yes
Solve time: 2m20s
Let
$$ F(x,y)=y^{2}-x^{2}-13. $$
The curve is the zero set $F(x,y)=0$, and digitization is performed row by row in the integer lattice. For each fixed integer $y$, we examine the sign of $F(x,y)$ as $x$ increases. A pixel is placed in the column where the sign changes between consecutive integer $x$-values (or where $F(x,y)=0$).
The curve is symmetric under $x \mapsto -x$, so we first compute the positive branch $x \ge 0$ and then reflect.
For $0<y\le 7$, we evaluate row by row.
When $y=1,2,3$, we have $y^{2}\le 9$, so $F(0,y)=y^{2}-13<0$. Since $F(x,y)$ decreases further as $x$ increases, there is no sign change for any $x \ge 0$. Hence no digitized pixels occur in these rows.
When $y=4$, we compute
$$ F(1,4)=16-1-13=2>0,\qquad F(2,4)=16-4-13=-1<0. $$
A sign change occurs between $x=1$ and $x=2$, so the curve crosses this grid edge. The corresponding digitized pixel on the positive branch is placed at $x=2$, giving $(2,4)$.
When $y=5$, we compute
$$ F(3,5)=25-9-13=3>0,\qquad F(4,5)=25-16-13=-4<0. $$
The sign change occurs between $x=3$ and $x=4$, hence the pixel is placed at $x=4$, giving $(4,5)$.
When $y=6$, we compute
$$ F(4,6)=36-16-13=7>0,\qquad F(5,6)=36-25-13=-2<0. $$
The sign change occurs between $x=4$ and $x=5$, so the pixel is placed at $x=5$, giving $(5,6)$.
When $y=7$, we compute
$$ F(6,7)=49-36-13=0. $$
The curve passes exactly through the lattice point, so we include $(6,7)$ on the positive branch.
Collecting all positive-branch digitized points for $0<y\le 7$, we obtain
$$ (2,4),\ (4,5),\ (5,6),\ (6,7). $$
By symmetry under $x \mapsto -x$, the full digitization consists of these points together with their reflections:
$$ (-2,4),\ (-4,5),\ (-5,6),\ (-6,7). $$
Thus the digitized hyperbola $y^{2}=x^{2}+13$ for $0<y\le 7$ is completely determined by these lattice points.