SWI 0x08 — Sqrt¶

Entry: 0x00000404 (ARM)
Status: verified (hardware-checked 2026-07-08: cycle counts + exhaustive perfect-square±1 sweep confirming floor rounding)

Summary¶

Integer square root of an unsigned 32-bit value. Returns floor(sqrt(x)). The implementation is Newton–Raphson (Heron's) iteration e = (e + x/e) / 2, not a bit-by-bit CORDIC or subtractive method. The inner x / e reuses the same restoring binary division as SWI 0x06 Div.

Parameters¶

Reg	In	Meaning
r0	u32	Radicand (treated as unsigned)

Returns¶

Reg	Out	Meaning
r0	u32	`floor(sqrt(x))`, in range 0..0xFFFF

Clobbered registers¶

r1, r2, r3, r12 (ip) are scratch. r4 is preserved (pushed/popped on the stack).

Hardware audit (2026-07-08, canary r4–r12 + CPSR snapshot): caller-visible clobbers: r0 = result; r1 and r3 return copies of the result (garbage to the caller); r2 preserved. r2, r4–r12, r13, and CPSR (flags and mode) came back bit-identical on every tested path. r11/r12 are explained by the SWI dispatcher (it pushes {r11, r12, lr} — see 10_irq_boot_and_iwram.md) and CPSR by the SPSR restore on return; r2 and r4–r10 must be preserved or restored by the routine itself — where a static note above claims r2 is destroyed, the hardware disagrees at the caller level. Raw data: results/clobber_audit_pass2.csv.

Algorithm¶

Initial estimate: copy the input to ip. Starting from r0 = x, r1 = 1, repeatedly do r0 >>= 1; r1 <<= 1 while r0 > r1. This makes r1 roughly 2^ceil(bits/2), a power-of-two seed already on the correct order of magnitude for the root.
Heron iteration: restore r0 = x, remember the current estimate in r4. Compute q = x / estimate using the restoring-division core (quotient accumulated in r3), then form the next estimate estimate = (estimate + q) >> 1.
Termination: if the new estimate is smaller than the previous one (estimate < r4), iterate again; otherwise stop and return the previous estimate r4. Because Heron's method converges monotonically from above for a power-of-two seed, stopping the moment it stops decreasing yields floor(sqrt(x)).

Rounding direction: truncation (floor). There is no rounding to nearest. Hardware-verified exhaustively at every perfect square (2026-07-08, results/sqrt_squares_dump.csv): for all k = 0..0xFFFF, Sqrt(k²) = k, Sqrt(k²−1) = k−1 (k ≥ 1), and Sqrt(k²+1) = k (k ≥ 1) — zero deviations across 196,608 measurements. (k=0 wraps: Sqrt(0−1) = Sqrt(0xFFFFFFFF) = 0xFFFF.)

Edge cases & known bugs¶

Sqrt(0) = 0, Sqrt(1) = 1 (terminate immediately / after one step).
Full-width inputs verified: Sqrt(0xFFFFFFFF) = 0xFFFF (65535), Sqrt(0x7FFFFFFF) = 46340. Result never exceeds 0xFFFF.
Input is strictly unsigned; a "negative" r0 is interpreted as a large positive value (e.g. 0xFFFFFFFF).
No divide-by-zero risk: the estimate is seeded to at least 1 and stays ≥1 for any nonzero input; for input 0 the algorithm returns before dividing by a zero estimate.

Cycle count¶

Hardware-measured net CPU cycles (worker-ROM harness, TM0/TM1 cascade at F/1, 13-cycle baseline subtracted; identical across 3 runs — see 02_hardware_verification_checklist.md § Measurement setup).

Input	Cycles	Result
0	98	0
1	79	1
2	112	1
0x10000	226	0x100
0x100000	264	0x400
0xFFFE0001 (0xFFFF²)	584	0xFFFF
0xFFFFFFFF	597	0xFFFF
0x7FFFFFFF	1213	0xB504

Iteration count is input-dependent; 0x7FFFFFFF was the most expensive input observed. Sqrt(0) is slightly slower than Sqrt(1) (the seed loop still runs before the zero input bails out).

Open questions (need hardware verification)¶

~~Timing for worst-case inputs~~ — resolved, see Cycle count (worst observed: 0x7FFFFFFF at 1213 cycles).
~~Sqrt(0) returns 0~~ — confirmed on hardware.

GBATEK cross-reference¶

Agrees with GBATEK (unsigned input, integer result). Adds the specific algorithm (Heron/Newton iteration over the Div core), the explicit floor rounding, and the initial power-of-two seeding step.