Z80 Routines:Math:Square root

Size Optimization

This version is size optimized, it compares every perfect square against HL until a square that is larger is found. Obviously slower, but does get the job done in only 12 bytes.

;-------------------------------
;Square Root
;Inputs:
;HL = number to be square rooted
;Outputs:
;A  = square root

sqrt:
   ld a,$ff
   ld de,1
sqrtloop:
   inc a
   dec e
   dec de
   add hl,de
   jr c,sqrtloop
   ret 

Speed Optimization 2

This 92 byte version is an optimized unrolled loop taking at most 379 t-states. Each iteration is optimized for its location in the algorithm.

; fast 16 bit isqrt by John Metcalf
; 92 bytes, 344-379 cycles (average 362)
; v2 - saved 3 cycles with a tweak suggested by Russ McNulty

; call with hl = number to square root
; returns    a = square root
; corrupts hl, de

; ----------

  ld a,h        ; 4
  ld de,0B0C0h  ; 10
  add a,e       ; 4
  jr c,sq7      ; 12 / 7
  ld a,h        ; 4
  ld d,0F0h     ; 7
sq7:

; ----------

  add a,d       ; 4
  jr nc,sq6     ; 12 / 7
  res 5,d       ; 8
  db 254        ; 7
sq6:
  sub d         ; 4
  sra d         ; 8

; ----------

  set 2,d       ; 8
  add a,d       ; 4
  jr nc,sq5     ; 12 / 7
  res 3,d       ; 8
  db 254        ; 7
sq5:
  sub d         ; 4
  sra d         ; 8

; ----------

  inc d         ; 4
  add a,d       ; 4
  jr nc,sq4     ; 12 / 7
  res 1,d       ; 8
  db 254        ; 7
sq4:
  sub d         ; 4
  sra d         ; 8
  ld h,a        ; 4

; ----------

  add hl,de     ; 11
  jr nc,sq3     ; 12 / 7
  ld e,040h     ; 7
  db 210        ; 10
sq3:
  sbc hl,de     ; 15
  sra d         ; 8
  ld a,e        ; 4
  rra           ; 4

; ----------

  or 010h       ; 7
  ld e,a        ; 4
  add hl,de     ; 11
  jr nc,sq2     ; 12 / 7
  and 0DFh      ; 7
  db 218        ; 10
sq2:
  sbc hl,de     ; 15
  sra d         ; 8
  rra           ; 4

; ----------

  or 04h        ; 7
  ld e,a        ; 4
  add hl,de     ; 11
  jr nc,sq1     ; 12 / 7
  and 0F7h      ; 7
  db 218        ; 10
sq1:
  sbc hl,de     ; 15
  sra d         ; 8
  rra           ; 4

; ----------

  inc a         ; 4
  ld e,a        ; 4
  add hl,de     ; 11
  jr nc,sq0     ; 12 / 7
  and 0FDh      ; 7
sq0:
  sra d         ; 8
  rra           ; 4
  cpl           ; 4

Balanced Optimization

This version is a balance between speed and size. It also uses the high school method and runs under 1200 tstates. It only costs 41 bytes.

;-------------------------------
;Square Root
;Inputs:
;DE = number to be square rooted
;Outputs:
;A  = square root

Sqrt:
    ld hl,0
    ld c,l
    ld b,h
    ld a,8
Sqrtloop:
    sla e
    rl d
    adc hl,hl
    sla e
    rl d
    adc hl,hl
    scf               ;Can be optimised
    rl c              ;with SL1 instruction
    rl b
    sbc hl,bc
    jr nc,Sqrtaddbit
    add hl,bc
    dec c
Sqrtaddbit:
    inc c
    res 0,c
    dec a
    jr nz,Sqrtloop
    ld a,c
    rr b
    rra
    ret

Presumably the best

This code was found on z80 bits and has the advantage of being both faster than all three versions above and smaller than the last two (it runs in under 720 T-states (under 640 if fully unrolled) and takes a mere 29 bytes). On the other hand it takes a somewhat unconventionnal input... It computes the square root of the 16bit number formed by la and places the result in d.

sqrt_la:
	ld	de, 0040h	; 40h appends "01" to D
	ld	h, d
	
	ld	b, 7
	
	; need to clear the carry beforehand
	or	a
	
_loop:
	sbc	hl, de
	jr	nc, $+3
	add	hl, de
	ccf
	rl	d
	rla
	adc	hl, hl
	rla
	adc	hl, hl
	
	djnz	_loop
	
	sbc	hl, de		; optimised last iteration
	ccf
	rl	d
	
	ret
 

Other Options

A binary search of a square table would yield much better best case scenarios and the worst case scenarios would be similar to the high school method. However this would also require 512 byte table making it significantly larger than the other routines. Of course the table could also serve as a rapid squaring method.

Credits and Contributions

• James Montelongo
• Milos "baze" Bazelides (or possibly one of the contributor of z80bits)
• John Metcalf (Speed Optimization 2 from z80snippets)