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:

  1. Start with a low bound ($L=0$) and a high bound ($H=N$).
  2. Guess the root $R$ by finding the midpoint: $R = (L+H) / 2$.
  3. Calculate $R^2$.
  4. If $R^2$ is too high, set $H = R - 1$. If $R^2$ is too low, set $L = R + 1$.
  5. 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′).