A few days ago, I mentioned in passing that I'd just thought of
a fast way to calculate square roots, but that it would require
512 bytes of lookup tables.  Since then, I've received a number
of e-mail requests for a program that implements the algorithm,
so I thought I'd better actually write one.

Here it is.  As usual, you get what you pay for; I've assembled
the program, but haven't tested it.  The algorithm has been
completely tested in QuickBASIC, so if this program doesn't
work, it's just because there's a bug in the implementation.

        ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
        ;                                                      ;
        ; "Big Mojo" Square-Root Calculator                    ;
        ; Written by Andy Warren, 26 October 1995              ;
        ;                                                      ;
        ; (C) 1995 Fast Forward Engineering                    ;
        ; All Rights Reserved                                  ;
        ;                                                      ;
        ; Permission is hereby granted for any non-commercial  ;
        ; use (as though anyone would actually CHOOSE to find  ;
        ; square roots this way) so long as this copyright     ;
        ; notice remains intact.                               ;
        ;                                                      ;
        ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

                LIST FIXED,R=DEC,P=16C74

                ERRORLEVEL -305, -205   ;TURN OFF "USING DEFAULT
                                        ;DESTINATION OF 1
                                        ;(FILE)" AND "DIRECTIVE
                                        ;FOUND IN COLUMN 1"
                                        ;MESSAGES.

        PCL     EQU     002H

        XHI     EQU     020H            ;THESE COULD BE ANY
        XLO     EQU     021H            ;GENERAL-PURPOSE FILE
        ROOT    EQU     022H            ;REGISTERS.


                ORG     0000H
                GOTO    START

                ORG     0008

        START:
                ;Load XHI with the hi-byte of the number whose
                ;square root you wish to find, and XLO with the
                ;lo-byte.

                CALL    SQRT

                GOTO    START

        ;
        ; Square-Root Finder.  Enter with the radicand in
        ; XHI:XLO.  Exits with the square root, rounded to the
        ; nearest integer, in ROOT.
        ;
        ; For non-zero radicands, this routine executes in an
        ; average of 127 cycles (minimum of 121, maximum of
        ; 158), including CALL and RETURN overhead.  When the
        ; radicand is 0, the routine executes in 10 cycles,
        ; including CALL and RETURN.
        ;

        SQRT:

                CLRF    ROOT

                MOVF    XHI,W
                IORWF   XLO,W
                BZ      DONE

        bit = 7
        while (bit >= 0)

                BSF     ROOT,bit

                DECF    ROOT,W
                CALL    GETHI

                SUBWF   XHI,W
                SKPZ
                GOTO    $+4

                DECF    ROOT,W
                CALL    GETLO
                SUBWF   XLO,W

                SKPC
                BCF     ROOT,bit

        bit = bit - 1
        endw

        DONE:

                ;ROOT contains the square root of XHI:XLO,
                ;rounded to the nearest integer.

                RETURN

        ;
        ; Hi-Byte Lookup Table.  Must be ORG'ed at a page
        ; boundary.
        ;

                ORG     0100H

        GETHI:

                ADDWF   PCL

        x = 0
        while (x < 255)

                RETLW   HIGH (((2*x+1)*(2*x+1))/4)

        x = x + 1
        endw

        ;
        ; Lo-Byte Lookup Table.  Must be ORG'ed at a page
        ; boundary.
        ;

                ORG     0200H

        GETLO:

                ADDWF   PCL

        x = 0
        while (x < 255)

                RETLW   LOW (((2*x+1)*(2*x+1))/4) + 1

        x = x + 1
        endw

                END

Of course, the code above is written for Microchip's MPASM
assembler.  It's written for the 16C74, but will work without
modification on any 16Cxx part with at least 1K of code space;
translation to the 16C57/58 is a little more involved.

Oh... The comments say that the routine rounds ROOT to the
nearest integer.  This is true except for those cases where the
nearest integer is 256.  In those cases (where the radicand is
greater than 65280), the routine sets ROOT to 255, since 256
won't fit in 8 bits.

-Andy

--
Andrew Warren - fastfwd@ix.netcom.com
Fast Forward Engineering, Vista, California