# Sqrt.asm

Jump to: navigation, search

# Functions Provided

Entry pointFunction providedNotes
SQRTCalculate the square root of a fixed-point numberValue in register, fractional point (Qpt) in ROM.
SQRT.1Calculate the square root of an integerValue in register, fractional point implied to be 0.
SQRT.2Calculate the square root of a fixed-point numberValue and fractional point both in registers

See source code below for calling convention.

# Examples

(todo... please contribute!)

# Notes

Unlike the square-root 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 "Q-point," 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 fixed-point number       ;;
;;      SQRT.1      Calculate the square root of an integer                 ;;
;;      SQRT.2      Calculate the square root of a fixed-point number       ;;
;;                                                                          ;;
;;  AUTHOR                                                                  ;;
;;      Joseph Zbiciak <intvnut AT gmail.com>                               ;;
;;                                                                          ;;
;;  REVISION HISTORY                                                        ;;
;;      12-Sep-2001 Initial revision . . . . . . . . . . .  J. Zbiciak      ;;
;;      24-Nov-2003 Minor tweaks for speed . . . . . . . .  J. Zbiciak      ;;
;;                                                                          ;;
;;  INPUTS for SQRT                                                         ;;
;;      R1      Unsigned 16-bit argument to SQRT()                          ;;
;;      R5      Pointer to DECLE containing Qpt, followed by return addr.   ;;
;;                                                                          ;;
;;  INPUTS for SQRT.1                                                       ;;
;;      R1      Unsigned 16-bit argument to SQRT()                          ;;
;;      R5      Return address                                              ;;
;;                                                                          ;;
;;  INPUTS for SQRT.2                                                       ;;
;;      R0      Qpt for fixed-point value                                   ;;
;;      R1      Unsigned 16-bit 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 Q-points on fixed-point numbers is    ;;
;;      by right-shifting the incoming value 1 bit, thus making the         ;;
;;      Q-point even.  This has the negative effect of losing precision     ;;
;;      on odd Q-point 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                                                  ;;
;; ======================================================================== ;;
```