Z80 Routines:Math:Square root
Contents
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
This version uses the high school method of finding a square root and so it is much faster, running at about ~850 tstates. Unfortunately it requires 180 bytes and is quite obfuscated.
;------------------------------- ;Square Root ;Inputs: ;DE = number to be square rooted ;Outputs: ;A = square root sqrt: xor a ld h,a ld l,a ld b,a rl d rl l rl d rl l ld c,1 sbc hl,bc jp c,$+3+2+1 sbc hl,bc inc a add hl,bc add a,a rl d rl l rl d rl l ld c,a scf rl c sbc hl,bc jp c,$+3+2+1 sbc hl,bc inc a add hl,bc add a,a rl d rl l rl d rl l ld c,a scf rl c sbc hl,bc jp c,$+3+2+1 sbc hl,bc inc a add hl,bc add a,a rl d rl l rl d rl l ld c,a scf rl c sbc hl,bc jp c,$+3+2+1 sbc hl,bc inc a add hl,bc add a,a rl e adc hl,hl rl e adc hl,hl ld c,a scf rl c sbc hl,bc jp c,$+3+2+1 sbc hl,bc inc a add hl,bc add a,a rl e adc hl,hl rl e adc hl,hl ld c,a scf rl c sbc hl,bc jp c,$+3+2+1 sbc hl,bc inc a add hl,bc add a,a rl e adc hl,hl rl e adc hl,hl ld c,a scf rl c sbc hl,bc jp c,$+3+2+1 sbc hl,bc inc a add hl,bc add a,a rl e adc hl,hl rl e adc hl,hl ld c,a scf rl c rl b sbc hl,bc jp c,$+3+2+1 sbc hl,bc inc a add hl,bc ret
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 xor 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)