# PICMicrocontollerMathMethod for square root

## 16 bit integer square root

From: Scott Dattalo

I know at least a few people are interested in this. I finally got around to applying the 18cxxx instruction set to the sqrt algorithm (see: http://www.dattalo.com/technical/software/pic/picsqrt.html and http://www.dattalo.com/technical/theory/sqrt.html ).

It takes only 25 instructions and executes between 68 and 108 (excluding the call). I have no idea what the average is. Although, if I made the test code isochronous, it'd be easy to find that out. I still think there's room for optimization too (but after spending 4 hours fixing an elusive bug in gpsim, I'm not up to it [but I see two places that can be tweaked]). BTW, gpsim runs through all 2^16 test cases in just 2 seconds!

Scott

```
list    p=18c242,t=ON,c=132,n=80

include "p18c242.inc"

cblock  0
N_hi,N_lo
x,y
s_hi,s_lo
endc

ORG     0               ;Reset Vector

Main

CLRF    status
CLRF    x
CLRF    s_hi
CLRF    s_lo
INCF    x,f

; Here's some test code that goes through all 2^16 cases
;
; psuedo code:
:
;  int  s=0;
;  int  x=0;
;
;  do {
;
;    if(x*x == s)
;      x++;
;
;    n = s;
;    w = sqrt(n);
;    if(w+1 != x)
;      failed();
;
;    s++;
;
;  } while (x<256);

;  for(i=0; i< 256; i++)
xxx
MOVF    x,W             ;W = x*x
MULWF   x

movf    prodh,w,0       ;if x*x is equal to the current
cpfseq  s_hi            ;test case, s, then we need to advance
bra    L1              ;x. Note that x will always be 1 greater
movf    prodl,w,0       ;than the sqrt(s)
cpfseq  s_lo
bra    L1

infsnz  x,f
here     bra    here

L1:
; N = s
movf    s_hi,w
movwf   N_hi
movf    s_lo,w
movwf   N_lo

; find the sqrt of N (N_hi:N_lo)
RCALL    sqrt

infsnz  s_lo,f          ;s++ advance for the next test case
incf   s_hi,f

addlw   1               ;if w (sqrt(N)) is one less than x
cpfseq  x               ; then we've passed
bra    failed

bra     xxx

failed:
bra     xxx             ;Set a break point here to catch failures

;----------------------------------------------------------
;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: W register returned with the 8 bit result
;
;Memory used:
;
;Minimum 68 cycles
;Maximum 108 cycles

sqrt
MOVLW   0xc0            ;Initialize value for mask
MOVLW   0x40            ;Initial value for the root

sq1     CPFSLT   N_hi
BRA     sq6
;Subtract the root developed so far

sq3     RLCF    N_lo,F          ;Shift N left one position
RLCF    N_hi,F
BC      sq4

XORWF   mask,W          ;clear the last and set the next bit

BNC     sq1

;We are almost done. In the last iteration, we have 7 bits of the root. When
;"01" is appended to it, we will have a 9-bit number that must be subtracted
;from N.

SUBWF   N_hi,F          ;
SKPC                    ;If the upper 7 bits cause a borrow, then
RETURN                ;the appended "01" will as well: We're done.

SKPNZ                   ;If the result of the subtraction is zero
BTFSC N_lo,7          ;AND the msb of N_lo is set then the LSB of the
;root is zero.
XORLW  1             ;Otherwise, it is one.

RETURN                  ;

sq4     BTFSC   mask,0          ;Need to unconditionally set the current bit of
the root.
RETURN                ;However, if we're through iterating, then
leave.

XORWF   mask,W          ;Append "01" to the root developed so far.
sq6     SUBWF   N_hi,F
IORWF   mask,W          ;Set the current bit
bra     sq3             ;Go unconditionally set the current bit.

END

```

(gpsim is a full-featured software simulator for Microchip PIC microcontrollers distributed under the GNU General Public License. http://dattalo.com/gnupic/gpsim.html )

Archive:

 file: /Techref/microchip/math/sqrt/16bint-18c-sd.htm, 5KB, , updated: 2003/12/10 17:05, local time: 2024/8/3 13:35, owner: DAV-MP-E62a, TOP NEW HELP FIND:  3.238.244.234:LOG IN

 ©2024 These pages are served without commercial sponsorship. (No popup ads, etc...).Bandwidth abuse increases hosting cost forcing sponsorship or shutdown. This server aggressively defends against automated copying for any reason including offline viewing, duplication, etc... Please respect this requirement and DO NOT RIP THIS SITE. Questions?Please DO link to this page! Digg it! / MAKE! 16 bit integer square root (16bint-18c-sd.htm)

After you find an appropriate page, you are invited to your to this massmind site! (posts will be visible only to you before review) Just type a nice message (short messages are blocked as spam) in the box and press the Post button. (HTML welcomed, but not the <A tag: Instead, use the link box to link to another page. A tutorial is available Members can login to post directly, become page editors, and be credited for their posts.

Attn spammers: All posts are reviewed before being made visible to anyone other than the poster.
 Did you find what you needed? "No. I'm looking for: " "No. Take me to the search page." "No. Take me to the top so I can drill down by catagory" "No. I'm willing to pay for help, please refer me to a qualified consultant"

 PICList 2024 contributors: o List host: MIT, Site host massmind.org, Top posters @none found - Page Editors: James Newton, David Cary, and YOU! * Roman Black of Black Robotics donates from sales of Linistep stepper controller kits. * Ashley Roll of Digital Nemesis donates from sales of RCL-1 RS232 to TTL converters. * Monthly Subscribers: Gregg Rew. on-going support is MOST appreciated! * Contributors: Richard Seriani, Sr.

.