Integer Square Roots in Z80 machine code
========================================
A simple, but inefficient way of calculating integer square roots is to
count how many times increasing odd numbers can be subtracted from the
starting value. For example:
32-1=31 -> 31-3=28 -> 28-5=23 -> 23-7=16 -> 16-9=7 -> 7-11<0
1 2 3 4 5
-> SQR(30)=5, remainder 7
This can be done in Z80 machine code as follows. To calculate roots of
numbers larger than 16 bits different code is needed, as the square root
of &10000 (a 17-bit number) is &100 (a 9-bit number).
; Calculate 16-bit square root
; ----------------------------
; On entry HL=input value
; On exit DE=corrupted
; A=root
; HL=remainder
; Size 14 bytes
;
.sqr
LD DE,1 ; Initialise to first subtrand
LD A,D ; Initial root=0
.sqr_loop ; Repeatedly subtract increasing
AND A ; odd numbers until HL<0
SBC HL,DE ; HL=HL-subtrand
JR C,sqr_done ; HL<0, all done
INC A ; Increase root
INC DE
INC DE ; step subtrand +2 to next odd number
JR sqr_loop ; Loop to subtract next odd number
.sqr_done
ADD HL,DE ; A=root, HL=remainder
You can test this in BBC BASIC by terminating the code with:
LD H,L:LD L,A:EXX ; HL'=remainder*256+root
RET
and running:
FOR L%=1 TO 65535:H%=L%DIV256:R%=USR sqr:PRINT L%,~R%:NEXT
The following code calculates roots of 8-bit numbers by using an 8-bit
counter and root. As it calculates roots of 8-bit numbers the maximum it
will calculate is the integer square root of 255 which is 15.
; Calculate 8-bit square root
; ---------------------------
; On entry A=input value
; On exit A=corrupted
; C=corrupted
; B=root
; Size 11 bytes
;
.sqr8
LD BC,1 ; Initialise C=first subtrand, B=SQR(0)
.sqr8_loop ; Repeatedly subtract increasing
SUB A,C ; Subtract current odd number
JR C,sqr8_done ; A<0, all done
INC B ; Increase root
INC C
INC C ; Step to next odd number
JR sqr8_loop ; Loop to subtract next odd number
.sqr8_done
; B=root