Difference between revisions of "Programming:Fast Square Root"

From CPCWiki - THE Amstrad CPC encyclopedia!
Jump to: navigation, search
(Added optimised version (much much faster!))
m (Faster Again: - Optimised using SBC A:ADD n)
Line 77: Line 77:
 
RET
 
RET
 
ge2: CP 3 * 3
 
ge2: CP 3 * 3
LD A, 3
+
SBC A
SBC 0
+
ADD 3
 
RET
 
RET
 
ge4: CP 6 * 6
 
ge4: CP 6 * 6
 
JR NC,ge6
 
JR NC,ge6
 
CP 5 * 5
 
CP 5 * 5
LD A, 5
+
SBC A
SBC 0
+
ADD 5
 
RET
 
RET
 
ge6: CP 7 * 7
 
ge6: CP 7 * 7
LD A, 7
+
SBC A
SBC 0
+
ADD 7
 
RET
 
RET
 
ge8: CP 12 * 12
 
ge8: CP 12 * 12
Line 95: Line 95:
 
JR NC,ge10
 
JR NC,ge10
 
CP 9 * 9
 
CP 9 * 9
LD A,9
+
SBC A
SBC 0
+
ADD 9
 
RET
 
RET
 
ge10: CP 11 * 11
 
ge10: CP 11 * 11
LD A,11
+
SBC A
SBC 0
+
ADD 11
 
RET
 
RET
 
ge12: CP 14 * 14
 
ge12: CP 14 * 14
 
JR NC,ge14
 
JR NC,ge14
 
CP 13 * 13
 
CP 13 * 13
LD A,13
+
SBC A
SBC 0
+
ADD 13
 
RET
 
RET
 
ge14: CP 15 * 15
 
ge14: CP 15 * 15
LD A,15
+
SBC A
SBC 0
+
ADD 15
 
RET
 
RET
 
</pre>
 
</pre>
 
[[Category:Programming]]
 
[[Category:Programming]]

Revision as of 20:46, 18 September 2007

Input: A = The number you want to find the square root of

Output: A = Square root of the number supplied in A

Destroys: A,B,DE

Call: CALL SqrtA

;this routine written 10 - 28 - 2003
;ported from the 68k version (by Frank Yaul) by konrad meyer
;this routine is not as memory efficient as it could be; this is
;done to save cycles

;note: this routine is using the fastest available method
;and will come within 1 below the #
;note: this routine is inaccurate in #s below 4

SqrtA:
	LD	(Asqr),A
	SRL	A
	JR	DataOver
Asqr:
	.DB	0
Bsqr:
	.DB	0
Csqr:
	.DB	0
DataOver:
	LD	(Bsqr),A
	LD	B,A
	LD	(Csqr),A
iterate:
	LD	A,(Asqr)
	LD	B,(Bsqr)
	LD	D,A
	LD	E,B
divideDbyEreturnA:
	RL	D
	RLA
	SUB	E
	JR	nc,$+3
	ADD	A,E
	LD	E,A
	LD	A,D
	CPL
	LD	B,(Bsqr)
	ADD	A,B
	SRL	A
	LD	(Bsqr),A
	LD	A,(Csqr)
	DEC	A
	LD	B,(Bsqr)
	CP	B
	JR	z,done
	LD	(Csqr),B
	JR	iterate
done:
	LD	A,(Bsqr)
	RET

Faster Again

Since there are only 15 possible results for the square root of an 8 bit number, it's really just a series of comparisons, optimised to use a binary comparison. This routine also leaves all other registers intact:

	CP 8 * 8
	JR NC,ge8
	CP 4 * 4
	JR NC,ge4
	CP 2 * 2
	JR NC,ge2
	OR A
	RET Z
	INC A
	RET
ge2:	CP 3 * 3
	SBC A
	ADD 3
	RET
ge4:	CP 6 * 6
	JR NC,ge6
	CP 5 * 5
	SBC A
	ADD 5
	RET
ge6:	CP 7 * 7
	SBC A
	ADD 7
	RET
ge8:	CP 12 * 12
	JR NC,ge12
	CP 10 * 10
	JR NC,ge10
	CP 9 * 9
	SBC A
	ADD 9
	RET
ge10:	CP 11 * 11
	SBC A
	ADD 11
	RET
ge12:	CP 14 * 14
	JR NC,ge14
	CP 13 * 13
	SBC A
	ADD 13
	RET
ge14:	CP 15 * 15
	SBC A
	ADD 15
	RET