=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- 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