On Tue, 15 Feb 2000, Nikolai Golovchenko wrote:

> 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 <G>
>
> 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 <golovchenko@mail.ru>
> ;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)
> ;**********************************************************************

Yep! In fact, compare to:

sqrt8:

        addlw   -(8*8)
        skpnc
         goto   sqrt_gt8
        addlw   (8*8)-(4*4)
        skpnc
         goto   sqrt_gt4
        addlw   (4*4)-(2*2)
        skpnc
         goto   sqrt_gt2
        addlw   (2*2)-(1*1)
        skpnc
         retlw  1
        retlw   0

sqrt_gt2:
        addlw   (2*2)-(3*3)
        skpnc
         retlw  3
        retlw   2

sqrt_gt4
        addlw   (4*4)-(6*6)
        skpnc
         goto   sqrt_6_7
        addlw   (6*6)-(5*5)
        skpnc
         retlw  5
        retlw   4

sqrt_6_7
        addlw   (6*6)-(7*7)
        skpnc
         retlw  7
        retlw   6
sqrt_gt8
        addlw   (8*8)-(0xc*0xc)
        skpnc
         goto   sqrt_gtc

        addlw   (0xc*0xc)-(0xa*0xa)
        skpnc
         goto   sqrt_a_b

        addlw   (0xa*0xa)-(9*9)
        skpnc
         retlw  9
        retlw   8

sqrt_a_b
        addlw   (0xa*0xa)-(0xb*0xb)
        skpnc
         retlw  0x0b
        retlw   0x0a

sqrt_gtc
        addlw   (0xc*0xc)-(0xe*0xe)
        skpnc
         goto   sqrt_gte

        addlw   (0xe*0xe)-(0xd*0xd)
        skpnc
         retlw  0x0d
        retlw   0x0c

sqrt_gte
        addlw   (0xe*0xe)-(0xf*0xf)
        skpnc
         retlw  0x0f
        retlw   0x0e

I believe they're identical!!! (I miscounted the instructions yesterday)

Okay, now I've got another one. This is the smallest: 10 instructions, 81
cycles.

Hint: n^2 = sum of the first n odd integers. (e.g 9 = 3*3 = 1 + 3 + 5)

Scott