Thanks to Eric Brewer and Martin Nilsson for finding a way to shave one more
byte from the sqrt routine. This brings the total word count down to 27, which
is the same as the other one Andy Warren says exists.

Another thanks to Eric for finding a way to save 6 execution cycles at the end
of the routine. Here's the latest version with a few more comments:


s1      equ     0x20
s2      equ     0x21
N_hi    equ     0x22
N_lo    equ     0x23

;---------------------------------------------------------------
;sqrt
;
; The purpose of this routine is take the square root of a 16 bit
;unsigned integer.
;Inputs:  N_hi - High byte of the 16 bit number to be square rooted
;         N_lo - Low byte     "                  "             "
;Outputs: s1   - Temporary variable
;         s2   - 8 bit result returned in here
;
sqrt
        MOVLW   0x40
        MOVWF   s1
        CLRF    s2

L2      ADDWF   s2,W
        SUBWF   N_hi,W          ;W = N_hi-s1-s2

        SKPNC                   ;if N_hi > (s1+s2)
          goto  L3              ;  then replace N_hi with N_hi-s1-s2

        BTFSS   s1,6            ;If this is the first time through the loop
          BTFSS   N_lo,0        ;or If MS bit is zero, then N < s1+s2
            goto  L1

L3
    ;N is greater than s1+s2, so replace N_hi with N_hi-s1-s2
        MOVWF   N_hi

        RLF     s1,W
        RLF     s1,W
        ADDWF   s2,F            ;s2 = s2 | (s1<<1)
L1
        BTFSC   s1,7            ;If s1 has rolled all the way around, we're
 done.
          return

    ;Next, roll N left one bit position. I.e. N = (N<<1) | (N>>15). This puts
 the
    ;MS bit into the LS bit position.
        RLF     N_hi,W          ;C = MS bit of N
        RLF     N_lo,F
        RLF     N_hi,F

        CLRC
        RRF     s1,W            ;Roll s1 right one bit: s1 = ((s1>>1) | (s1<<7))
 & 0xff
        RRF     s1,F            ;

        BTFSS   s1,7            ;If this is the last time through the loop, we
 need to
          goto  L2              ;make a tiny exception.

    ;We only get here if this is the last time through the loop. This special
 exception
    ;needs to handle a 10 bit addition. Right now, the value of s1 that got
 shifted into
    ;W is zero. It should be 1 >> 1, ie a fraction of 1/2. Or, another way to
 look at it
    ;is the value of s1 to be subtracted from N is 0x0080. Now, if N_lo is less
 than 0x80,
    ;then the subtraction will cause a borrow that must be propagated to N_hi,
 i.e. N_hi
    ;must be decremented. Rather than subtracting 1 from N_hi now, we'll instead
 add 1 to
    ;s2 and do the subtraction above.

        BTFSS   N_lo,7
          MOVLW 1

        goto    L2



Eric Brewer wrote:

>
> PS. If I get a chance, I'll do the timing analisys (if no one else does!)

I haven't done a full blown timing analysis. However, by adding up cycles I
estimate the worst case condition to be about 175 cycles. This is about 50%
slower than Andy's ghost programmer. But, Andy has assured me that the
original solution is no hoax. (If you think about, it wouldn't be a bad idea
to claim some hoax just to see if someone can meet your claim!)

So this _new_ wheel may not be perfectly round, but it is free.


Scott