The Challenge of Square Roots
The Z80 cannot natively calculate a square root. This complex operation must be achieved using an iterative algorithm that repeatedly guesses the answer and refines the guess until it is accurate enough.
Goal: To find the largest integer $R$ such that $R^2 \le N$, where $N$ is the input number.
Method 1: Integer Binary Search (The Reliable Method)
The Binary Search method is the safest and most reliable way to find the integer square root on an 8-bit processor. It works by checking the midpoint of a search range.
The Principle:
- Start with a low bound ($L=0$) and a high bound ($H=N$).
- Guess the root $R$ by finding the midpoint: $R = (L+H) / 2$.
- Calculate $R^2$.
- If $R^2$ is too high, set $H = R - 1$. If $R^2$ is too low, set $L = R + 1$.
- Repeat the process until the range ($L$ to $H$) converges.
Z80 Implementation Focus: This method requires 16-bit multiplication (Part 16) to calculate $R^2$ and careful 16-bit addition/subtraction (Part 8) to manage the $L$ and $H$ bounds.
The Core Logic: Iteration
The routine requires a main loop that repeats until $L$ is no longer less than or equal to $H$.
Outer Loop (Simplified):
SQRT_LOOP:
; 1. Calculate Midpoint: R = (L + H) / 2. This requires 16-bit addition and a fast right shift.
CALL CALCULATE_MIDPOINT ; DE ← R (The guess)
; 2. Square the Guess: Calculate R × R. (32-bit result)
CALL MULTIPLY_16_BY_16
; 3. Compare R*R to N (The input number)
CALL COMPARE_32_BIT_TO_N ; Sets Carry flag if R*R < N
JP C, TOO_LOW ; Jump if the guess was too low
; Too High: H = R - 1 (Need to reduce the high bound)
CALL SET_HIGH_BOUND
JP CONTINUE_LOOP
TOO_LOW:
; Too Low: L = R + 1 (Need to increase the low bound)
CALL SET_LOW_BOUND
CONTINUE_LOOP:
; ... (Check for convergence and JP SQRT_LOOP)
RET
Method 2: Newton’s Method (Faster but More Complex)
Newton’s method is mathematically much faster (quadratic convergence) but requires more complex fixed-point division, making it generally more difficult to implement robustly in Z80 assembly than the simple Binary Search.
Final Output: The function exits when the search converges, and the final value of $R$ (the integer square root) is returned in a 16-bit register pair (e.g., `HL′).