=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
Date: Wed, 16 Feb 2000 09:13:08
From: Nikolai Golovchenko
To: piclist
Subject: Re: square root added to Piclist FAQ math routine
--------------------------------------------------------------------------------
May be you miscounted instructions again? I squeezed one instruction
(10%) out. I wonder how did you find this method, intuition or what?
;**********************************************************************
;SMALL 8 BIT SQUARE ROOT
;
;Author: Nikolai Golovchenko
;Idea: Scott Dattalo
;"Hint: n^2 = sum of the first n odd integers.(e.g 9 = 3*3 = 1 + 3 + 5)"
;Date: February 16, 2000
;
;Input and output in ACCB0
;ROM - 9
;RAM - 1
;Timing - 12..87 cycles including call and return
;**********************************************************************
Sqrt8s
movlw -1
Sqrt8s1
addlw 2
subwf ACCB0, f
skpnc
goto Sqrt8s1
movwf ACCB0
decf ACCB0, f
rrf ACCB0, f
return
;**********************************************************************
Bye,
Nikolai
On Tuesday, February 15, 2000 Scott Dattalo wrote:
> 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
>>
>> 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)
>> ;**********************************************************************
> 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
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
Date: Wed, 16 Feb 2000 22:32:20
From: Dmitry Kiryashov
To: PICLIST@MITVMA.MIT.EDU
Subject: Re: square root added to Piclist FAQ math routine
--------------------------------------------------------------------------------
Hi Scott and Nikolai. Nice done challenge ;-)
Actually Nikolai's code can be reduced.
WBR Dmitry.
PS. Think it was Babbage's spirit Scott ;-)
> > Sqrt8s
> > movwf temp
> > movlw -1
> > Sqrt8s1
> > addlw 2
> > subwf temp,F
> > skpnc
> > goto Sqrt8s1
> > movwf temp
> > decf temp,F
Since W is always holding odd value
this decf isn't required I guess.
> > rrf temp,F ;or ,W
> > return