=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
    Date: Tue, 15 Feb 2000  16:02:14
    From: Nikolai Golovchenko 
      To: pic microcontroller discussion list 
 Subject: Re: square root added to Piclist FAQ math routine
--------------------------------------------------------------------------------

Hello Scott,
I love challenges!

This beast is 6 cycles (24%) faster. Square root of 8 bit value has
just 16 possible answers. So "brute force" approach helped. This
routine is just a list of compares and tree-like branches.

By the way, today I read in an elementary math book (Mark Vygodskiy,
1979) that the well known Newton method was actually devised by Heron
approximately 2000 years ago.... He didn't even know about decimal
fractions, but knew how to take sqare roots 

The method sounds like:
1) Take an approximate square root of the number
2) Divide number by approximation
3) Calculate mean of division result and approximation
4) Substitute approximation with mean and repeat from step 2 (repeat
until the needed precision is reached)

Same scheme is applied to cubic root, but division is made twice.

;**********************************************************************
;FAST 8 BIT SQUARE ROOT
;
;Author: Nikolai Golovchenko 
;Date: February 15, 2000
;
;Input and output in w
;ROM - 53
;RAM - 0
;Timing - 15..19 cycles including call and return
;**********************************************************************
Sqrt8f
        addlw -64       ;1
        skpnc
         goto sqrt8_15  ;3
        addlw (64-16)
        skpnc
         goto sqrt4_7   ;6
        addlw (16-4)
        skpnc
         goto sqrt2_3   ;9
        addlw (4-1)
        skpnc
         retlw 1                ;1 (15)
        retlw 0                 ;0 (16)
sqrt2_3
        addlw (4-9)
        skpnc
         retlw 3                ;3 (16)
        retlw 2                 ;2 (17)
sqrt4_7
        addlw (16-36)
        skpnc
         goto sqrt6_7   ;10
        addlw (36-25)
        skpnc
         retlw 5                ;5 (16)
        retlw 4                 ;4 (17)
sqrt6_7
        addlw (36-49)
        skpnc
         retlw 7                ;7 (17)
        retlw 6                 ;6 (18)
sqrt8_15
        addlw (64-144)
        skpnc
         goto sqrt12_15 ;7
        addlw (144-100)
        skpnc
         goto sqrt10_11 ;10
        addlw (100-81)
        skpnc
         retlw 9                ;9 (16)
        retlw 8                 ;8 (17)
sqrt10_11
        addlw (100-121)
        skpnc
         retlw 11               ;11 (17)
        retlw 10                ;10 (18)
sqrt12_15
        addlw (144-196)
        skpnc
         goto sqrt14_15 ;11
        addlw (196-169)
        skpnc
         retlw 13               ;13 (17)
        retlw 12                ;12 (18)
sqrt14_15
        addlw (196-225)
        skpnc
         retlw 15               ;15 (18)
        retlw 14                ;14 (19)
;**********************************************************************


Bye,
 Nikolai

On Tuesday, February 15, 2000 Scott Dattalo wrote:
> On Mon, 14 Feb 2000, James Newton wrote:

>> Nikolai Golovchenko has added Square Root routines to the pic math FAQ at
>> http://www.piclist.com/faq
>> under Routine / code library, Math, Basic Math

> Neeto!


>> 8 bit
>> http://techref.massmind.org/microchip/math/sqrt/sqrt8

> Challenge: I've got a back-of-the-notebook routine that will perform an
> 8-bit square root in a worst case of 25 cycles and a best case 8 cycles.
> I'd scribble it now except for the fear of being ostracized for writing
> obtuse pic code. Besides, we haven't had a challenge lately!

> Scott

> ps: James, why you're in the link-all-math-routines-that-have-ever-been-
> written-for-a-pic mode, you may want to add:

> http://www.dattalo.com/technical/software/pic/picsqrt.html
> and the half-baked explanation:
> http://www.dattalo.com/technical/theory/sqrt.html