Z80 Routines:Math:Square root - Revision history

Zeda: Reorganized and added a few routines including 32-bit integer square root

2019-09-30T23:00:48Z

Reorganized and added a few routines including 32-bit integer square root

Show changes

Zeda: removed redundant code

2019-09-30T22:33:44Z

removed redundant code

Zeda: removed this redundant section

2019-09-30T22:32:34Z

removed this redundant section

John metcalf: Add code for square root in max 379 t-states

2019-08-02T11:31:03Z

Add code for square root in max 379 t-states

Zeda: /* Speed Optimization */ The old speed version was slower than the 29-byte one. Here is a smaller, faster routine.

2013-10-23T03:22:36Z

‎Speed Optimization: The old speed version was slower than the 29-byte one. Here is a smaller, faster routine.

Show changes

Galandros: xor a destroys a, or a doesn't and it indeed clears the carry

2011-01-29T09:22:20Z

xor a destroys a, or a doesn't and it indeed clears the carry

Erfan K at 21:13, 28 January 2011

2011-01-28T21:13:08Z

Fullmetalcoder at 17:14, 5 November 2009

2009-11-05T17:14:53Z

Galandros: Routines:Math:Square root moved to Z80 Routines:Math:Square root: unite z80 routines

2009-10-25T19:49:16Z

Routines:Math:Square root moved to Z80 Routines:Math:Square root: unite z80 routines

Jim e: Added square root routines, been a while hope I did this right

2006-07-20T21:13:53Z

Added square root routines, been a while hope I did this right

New page

[[Category:Z80 Routines:Math|Square root]]
[[Category:Z80 Routines|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.
<nowiki>;-------------------------------
;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 </nowiki>

==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.
<nowiki>;-------------------------------
;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</nowiki>

==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.
<nowiki>;-------------------------------
;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</nowiki>

==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'''

@@ Line 128: / Line 128: @@
    cpl           ; 4
 </nowiki>
 == Presumably the best ==

← Older revision		Revision as of 22:32, 30 September 2019
Line 22:		Line 22:
	ret </nowiki>		ret </nowiki>

−
−	~~==Speed Optimization==~~
−	This version is an unrolled version of a square root algorithm taking at most 555 t-states. The downside is that it takes 111 bytes, but if speed is a priority, this is probably the best option. Most of the unrolled iterations are specially optimised for their location in the algorithm.
−	~~<nowiki>;-------------------------------~~
−	~~;Square Root~~
−	~~;Inputs:~~
−	~~;HL = number to be square rooted~~
−	~~;Outputs:~~
−	~~;A = square root~~
−	~~;111 bytes~~
−	~~;555 t-states worst case~~
−	~~SqrtHL:~~
−	~~;zero some registers~~
−	~~xor a~~
−	~~ld c,a~~
−	~~ld d,a~~
−
−	~~;move the LSB of the input into E for later use, then shift the LSB into L and load H with 0.~~
−	~~;H will be a carry register, where the bits in L are rotated in~~
−	~~ld e,l~~
−	~~ld l,h~~
−	~~ld h,c~~
−
−	~~;Iteration 1 is optimised~~
−	~~; C is treated as the accumulator~~
−	~~add hl,hl~~
−	~~add hl,hl~~
−	~~sub h~~
−	~~jr nc,$+5~~
−	~~inc c~~
−	~~cpl~~
−	~~ld h,a~~
−
−	~~;Iteration 2~~
−	~~; rotate in 2 more bits from the MSB of the input into H~~
−	~~add hl,hl~~
−	~~add hl,hl~~
−	~~; shift the accumulator~~
−	~~rl c~~
−	~~ld a,c~~
−	~~rla~~
−	~~; A is now double the shifted accumulator~~
−	~~sub h~~
−	~~; doubles as a comparison of the carry register (H) to double the accumulator~~
−	~~jr nc,$+5~~
−	~~; If the carry is > 2*accumulator, the bit in the accumulator needs to be 1:~~
−	~~inc c~~
−	~~; We need to perform H-(2C+1), but A=2C-H.~~
−	~~; We could do NEG to get A=H-2C, then DEC A, but NEG = CPL \ INC A~~
−	~~; NEG \ DEC A = CPL \ INC A \ DEC A~~
−	~~; So just use CPL, saving 8 t-states, 1 byte~~
−	~~cpl~~
−	~~ld h,a~~
−
−	~~;Iteration 3~~
−	~~add hl,hl~~
−	~~add hl,hl~~
−	~~rl c~~
−	~~ld a,c~~
−	~~rla~~
−	~~sub h~~
−	~~jr nc,$+5~~
−	~~inc c~~
−	~~cpl~~
−	~~ld h,a~~
−
−	~~;Iteration 4~~
−	~~add hl,hl~~
−	~~add hl,hl~~
−	~~rl c~~
−	~~ld a,c~~
−	~~rla~~
−	~~sub h~~
−	~~jr nc,$+5~~
−	~~inc c~~
−	~~cpl~~
−	~~ld h,a~~
−
−	~~;L is 0, H is the current carry~~
−	~~;E is the lower 8 bits~~
−	~~; Load the next set of bits (LSB of input) into L so that they can be rotated into H~~
−	~~ld l,e~~
−
−	~~;Iteration 5~~
−	~~add hl,hl~~
−	~~add hl,hl~~
−	~~rl c~~
−	~~ld a,c~~
−	~~rla~~
−	~~sub h~~
−	~~jr nc,$+5~~
−	~~inc c~~
−	~~cpl~~
−	~~ld h,a~~
−
−	~~;Iteration 6~~
−	~~add hl,hl~~
−	~~add hl,hl~~
−	~~rl c~~
−	~~ld a,c~~
−	~~rla~~
−	~~sub h~~
−	~~jr nc,$+5~~
−	~~inc c~~
−	~~cpl~~
−	~~ld h,a~~
−
−	~~;Iteration 7~~
−	~~; Now we need to start worrying about 8 bit overflow.~~
−	~~; In particular, the carry register, H should be ideally 9 bits for this iteration, 10 for the last.~~
−	~~; The accumulator, C, is 8 bits, but we need to compare H to 2C, and 2C is up to 9 bits on the last iteration.~~
−	~~;l has 4 more bits to rotate into h~~
−
−	~~sla c \ ld a,c \ add a,a~~
−	~~add hl,hl~~
−	~~add hl,hl~~
−	~~jr nc,$+6~~
−	~~sub h \ jp $+6~~
−	~~sub h~~
−	~~jr nc,$+5~~
−	~~inc c~~
−	~~cpl~~
−	~~ld h,a~~
−
−	~~;Iteration 8~~
−	~~; A lot of fancy stuff here~~
−	~~; D is 0, from way back at the beginning~~
−	~~; now I put H->E so that DE can hold the potentially 10-bit number~~
−	~~; Now C->A, L->H~~
−	~~; H thus has the last two bits of the input that need to be rotated into DE~~
−	~~; L has the value of the accumualtor which needs to be multiplied by 4 for a comparison to DE~~
−	~~; So 2 shifts of HL into DE results in DE holding the carry, HL holding 4*accumulated result!~~
−	~~ld e,h~~
−	~~ld h,l~~
−	~~ld l,c~~
−	~~ld a,l~~
−	~~add hl,hl \ rl e \ rl d~~
−	~~add hl,hl \ rl e \ rl d~~
−	~~sbc hl,de~~
−	~~;the c flag now has the state of the last bit of the result, HL does not need to be restored.~~
−	~~rla~~
−	~~ret~~
−	~~</nowiki>~~

	==Speed Optimization 2==		==Speed Optimization 2==

@@ Line 164: / Line 164: @@
 	rla
 	ret
 </nowiki>
@@ Line 244: / Line 350: @@
 * '''James Montelongo'''
 * '''Milos "baze" Bazelides''' (or possibly one of the contributor of [http://baze.au.com/misc/z80bits.html z80bits])

@@ Line 191: / Line 191: @@
 	; need to clear the carry beforehand
-	xor	a
+	or	a
 _loop:

@@ Line 191: / Line 191: @@
 	; need to clear the carry beforehand
-	or	a
+	xor	a
 _loop:

@@ Line 179: / Line 179: @@
      rra
      ret</nowiki>
@@ Line 186: / Line 219: @@
 == Credits and Contributions ==
 * '''James Montelongo'''

← Older revision	Revision as of 19:49, 25 October 2009
(No difference)