SX Microcontroller Math Method

24 bit Square Root binary restoring method

Andy David says:

Here's my 24-bit routine as written for the 17c43 [ed: and converted to Scenix SX] taken from a mail I sent Scott just after I wrote them, hence the comments about the implementations I used.

I did a few pencil-and-paper runs through the algorithm to be sure I understood the steps involved. This 24-bit resembles these 'manual' steps of shifting along the input string 2 bits at a time and subtracting - as the result is 12-bit, the final subtraction isn't awkward as in the 32-bit sqrt. I can't remember the performance figures for this routine, but I've just counted 348 min, 406 max (inc. call & return). A downside of this method is that the loop counter has to be a seperate variable, so it uses the same amount of ram as the 32-bit sqrt. This one is easier to follow and compare to an example on paper than the method I've used for the 32-bit sqrt.

I've added a 16-bit square root routine (again for the 17c43) that uses successive approximation to find the square root, the binary restoring method I'm fairly sure would be quicker. This is the only 16-bit sqrt routine I have specifically for the 17cxx PICs, I've only included it as the original poster requested a 16-bit routine. If you really want speed speed speed, I'd rewrite the 32-bit routine to be 16-bit.

Standard disclaimer applies

;==========================================================================
; brSQRT24
;
; Calculates the square root of a twentyfour bit number using the
; binary restoring method.
;
; Result in ACCaHI:ACCaLO
; Input in ACCcLO:ACCdHI:ACCdLO
; Test ACCbLO:ACCcHI
; Counter in ACCbHI
;
; 44 words long, uses 8 bytes RAM (inc. 3 holding 24-bit input).
;
;--------------------------------------------------------------------------
brSQRT24:
        clr     ACCaHI          ; clear result
        clr     ACCaLO          ;

        clr     ACCcHI          ; clear test bytes
        clr     ACCbLO          ;

        mov     W, #12          ; initialize counter
        mov     ACCbHI, W       ; (6 cycle intro, 9 incl. call)

ShftUp: rl      ACCdLO          ; Shift input up 2 places.
        rl      ACCdHI          ; (39 cycles per loop if bit is 0)
        rl      ACCcLO          ; (33 cycles per loop if bit is 1)
        rl      ACCcHI          ;
        rl      ACCbLO          ;
        rl      ACCdLO          ;
        rl      ACCdHI          ;
        rl      ACCcLO          ;
        rl      ACCcHI          ;
        rl      ACCbLO          ;

        rl      ACCaLO          ; Shift root-so-far up by two and append
        rl      ACCaHI          ; ... '01'.
        rl      ACCaLO          ;
        rl      ACCaHI          ;
        clrb    ACCaLO.1        ;
        setb    ACCaLO.0        ;

SubTest:
        mov     W, ACCaLO       ;
        sub     ACCcHI, W       ;
        mov     W, ACCaHI       ;
        sb      C               ;
        movsz   W, ++ACCaHI     ;
        sub     ACCbLO, W       ;

        snb     C               ;
        jmp     Set1            ;

        mov     W, ACCaLO       ; Restore the remainder.
        add     ACCcHI, W       ; ... (the current bit is 0).
        mov     W, ACCaHI       ;
        snb     C               ;
        movsz   W, ++ACCaHI     ;
        add     ACCbLO, W       ;
        jmp     Set0            ;

Set1:   setb    ACCaLO.1        ;
Set0:   rr      ACCaHI          ;
        rr      ACCaLO          ;
        clrb    ACCaHI.7        ;

BitLoop:
        decsz   ACCbHI          ;
        jmp     ShftUp

        ret