CORDIC

Remarks

Each step multiplies the vector $(x_i, y_i)$ by the matrix with rows $(1, -\sigma_i t)$ and $(\sigma_i t, 1)$, $t = 2^{-i}$, which is $\sqrt{1 + t^2}$ times the rotation by the angle $\sigma_i \arctan t$. After $n$ steps the scale factors multiply to $1/K_n$, which cancels $x_0 = K_n$, and the total angle is $\sum_i \sigma_i a_i = \theta - z_n$; this is clause 1. For clause 2, concavity of $\arctan$ on $[0, \infty)$ gives $a_i \le 2 a_{i+1}$, hence $a_i \le a_{i+1} + \cdots + a_{n-1} + a_{n-1}$ by induction. With this, the bound $\abs{z_i} \le a_i + \cdots + a_{n-1} + a_{n-1}$ passes from $z_i$ to $z_{i+1} = z_i - \sigma_i a_i$, and at $i = n$ it gives $\abs{z_n} \le a_{n-1}$. Clause 3 follows because $\cos$ and $\sin$ are $1$-Lipschitz. Since $a_0 + a_1 + a_2 + a_3 \approx 1.618 > \pi/2$, for $n \ge 4$ the method covers all $\theta \in [-\pi/2, \pi/2]$; other angles are first reduced by symmetries. Multiplication by $2^{-i}$ is a shift in binary, so each step needs only shifts, additions and a table lookup of $a_i$.

Going deeper

For a student

The same iteration in vectoring mode drives $y$ to $0$ instead of $z$, and then computes $\arctan(y_0/x_0)$ and, up to the known constant factor, the length $\sqrt{x_0^2 + y_0^2}$. Replacing $\arctan 2^{-i}$ by $\operatorname{artanh} 2^{-i}$ and rotations by hyperbolic rotations gives the hyperbolic functions, the exponential and the logarithm; in that case some steps must be repeated to ensure convergence. The constant $K_n$ tends to about $0.6073$ and is applied once at the start, not at each step.