Difference between revisions of "Sqrt.asm"
(→Notes) 
m (Protected "Sqrt.asm" ([edit=autoconfirmed] (indefinite) [move=autoconfirmed] (indefinite))) 
(No difference)

Latest revision as of 02:26, 4 December 2010
Functions Provided
Entry point  Function provided  Notes 

SQRT  Calculate the square root of a fixedpoint number  Value in register, fractional point (Qpt) in ROM. 
SQRT.1  Calculate the square root of an integer  Value in register, fractional point implied to be 0. 
SQRT.2  Calculate the square root of a fixedpoint number  Value and fractional point both in registers 
See source code below for calling convention.
Examples
(todo... please contribute!)
Notes
Unlike the squareroot code in the EXEC, this code works over the entire range $0000 to $FFFF. It is also an order of magnitude faster: Taking the square root of an integer takes between 600 and 700 cycles, whereas the EXEC's routine has a much wider range, taking nearly 10,000 cycles in some cases. In fact, the worst case performance for a square root is roughly a third faster than the worst case performance of FASTDIVU.
Where the code below refers to "Qpt" or "Qpoint," this means the same as "fractional point" or "binary point."
Source Code
;* ======================================================================== *; ;* These routines are placed into the public domain by their author. All *; ;* copyright rights are hereby relinquished on the routines and data in *; ;* this file.  Joseph Zbiciak, 2008 *; ;* ======================================================================== *; ;; ======================================================================== ;; ;; NAME ;; ;; SQRT Calculate the square root of a fixedpoint number ;; ;; SQRT.1 Calculate the square root of an integer ;; ;; SQRT.2 Calculate the square root of a fixedpoint number ;; ;; ;; ;; AUTHOR ;; ;; Joseph Zbiciak <intvnut AT gmail.com> ;; ;; ;; ;; REVISION HISTORY ;; ;; 12Sep2001 Initial revision . . . . . . . . . . . J. Zbiciak ;; ;; 24Nov2003 Minor tweaks for speed . . . . . . . . J. Zbiciak ;; ;; ;; ;; INPUTS for SQRT ;; ;; R1 Unsigned 16bit argument to SQRT() ;; ;; R5 Pointer to DECLE containing Qpt, followed by return addr. ;; ;; ;; ;; INPUTS for SQRT.1 ;; ;; R1 Unsigned 16bit argument to SQRT() ;; ;; R5 Return address ;; ;; ;; ;; INPUTS for SQRT.2 ;; ;; R0 Qpt for fixedpoint value ;; ;; R1 Unsigned 16bit argument to SQRT() ;; ;; R5 Return address ;; ;; ;; ;; OUTPUTS ;; ;; R0 Zeroed ;; ;; R1 Unmodified ;; ;; R2 SQRT(R1) ;; ;; R3, R4 Unmodified ;; ;; R5 Trashed ;; ;; ;; ;; NOTES ;; ;; The way this code handles odd Qpoints on fixedpoint numbers is ;; ;; by rightshifting the incoming value 1 bit, thus making the ;; ;; Qpoint even. This has the negative effect of losing precision ;; ;; on odd Qpoint numbers. Rectifying this without losing any ;; ;; performance would require significantly larger codesize. ;; ;; ;; ;; CODESIZE ;; ;; 44 words ;; ;; ;; ;; CYCLES ;; ;; cycles = 139 + 71*(8 + Qpt/2) worst case for SQRT ;; ;; cycles = 121 + 61*(8 + Qpt/2) best case for SQRT ;; ;; ;; ;; Subtract 4 cycles if Qpt is even. ;; ;; Subtract 8 cycles if calling SQRT.1. ;; ;; Subtract 14 cycles if calling SQRT.2. ;; ;; ;; ;; SOURCE ;; ;; Loosely based on a C code example (mborg_isqrt2) by Paul Hseih and ;; ;; Mark Borgerding, found on the web here: ;; ;; ;; ;; http://www.azillionmonkeys.com/qed/sqroot.html ;; ;; ;; ;; Includes additional optimizations that eliminate some of the math. ;; ;; ======================================================================== ;; SQRT PROC MVI@ R5, R0 ; 8 Get Qpt from after CALL INCR PC ; 6 (skip CLRR R0) @@1: CLRR R0 ; 6 Set Qpt == 0 @@2: PSHR R5 ; 9 Alt entry point w/ all args in regs. PSHR R1 ; 9 save R1 PSHR R3 ; 9 save R3 ; ; 41 (worst case: SQRT) ; 33 (if SQRT.1) ; 27 (if SQRT.2) CLRR R2 ; 6 R2 == Result word MVII #$4000, R3 ; 8 R3 == 1/2 of square of test bit MOVR R3, R5 ; 6 R5 == bit * (2*guess + bit) INCR R0 ; 6 SARC R0, 1 ; 6 Check to see if Qpt is odd ; BC @@even_q ; 7/9 ADCR PC ; 7 SLR R1, 1 ; 6 Note: We lose LSB if odd Q @@even_q: ADDI #8, R0 ; 8 B @@first ; 9 ; ; 60 (worst case, q is ODD) ; 54 (q is EVEN) ;==== ; 83 (worst case: SQRT, q is ODD) @@loop: SLLC R1, 1 ; 6 Shift the value left by 1 BC @@b1 ; 7/9 MSB was 1, force guessed bit to 1. @@first: CMPR R5, R1 ; 6 Is (guess+bit)**2 <= val? BNC @@b0 ; 7/9 C==0 means the bit should be 0 @@b1: RLC R2, 1 ; 6 Yes: Set bit in result and SUBR R5, R1 ; 6 subtract guess from value ADDR R3, R5 ; 6 \ SLR R3, 1 ; 6  Calculate next guess value ADDR R3, R5 ; 6 / DECR R0 ; 6 BNEQ @@loop ; 9/7 Guess next bit PULR R3 ; 11 Restore R3 PULR R1 ; 11 Restore R1 PULR PC ; 11 Return ; ; 71*k + 31 worst case @@b0: SLL R2, 1 ; 6 No: Clear bit in guessed result SLR R3, 1 ; 6 \__ Calculate next guess SUBR R3, R5 ; 6 / DECR R0 ; 6 BNEQ @@loop ; 9/7 Guess next bit ; ; 61*k  2 best case @@done: PULR R3 ; 11 Restore R3 PULR R1 ; 11 Restore R1 PULR PC ; 11 Return ENDP ;; ======================================================================== ;; ;; End of file: sqrt.asm ;; ;; ======================================================================== ;;