Post by thread:[EE] 8051 Coding challenge

A friend has produced what he considers is the most code efficient possible 8051 square root routine. Those interested in such devices may be interested and/or wish to attempt to improve on it. He says: > I have coded another even simpler 8-bit square root algorithm for > the > 051 - 17 bytes as a callable routine (including fetching the > argument from > RAM and returning the result to RAM). > I'll look at optimising it further tomorrow. & later > The optimised version is 13 bytes as a callable routine (including > fetching > the argument from RAM and returning the result to RAM). Executes in > 18..183 > cycles (average of 71 cycles for all 256 possible input values). I haven't got his code yet. Can anyone improve on 13 bytes ;-) ? I don't believe he is using lookup. Russell McMahon

{Quote hidden}> A friend has produced what he considers is the most code efficient > possible 8051 square root routine. Those interested in such devices > may be interested and/or wish to attempt to improve on it. He says: > >> I have coded another even simpler 8-bit square root algorithm for >> the >> 051 - 17 bytes as a callable routine (including fetching the >> argument from >> RAM and returning the result to RAM). >> I'll look at optimising it further tomorrow. > > & later > >> The optimised version is 13 bytes as a callable routine (including >> fetching >> the argument from RAM and returning the result to RAM). Executes in >> 18..183 >> cycles (average of 71 cycles for all 256 possible input values). > > I haven't got his code yet. Can anyone improve on 13 bytes ;-) ? > I don't believe he is using lookup. Maybe, but I'm not too familiar with the 8051 any more (thank goodness). But here's a hint: N^2 = sum of the first N-odd integers E.g. 1^2 = 1 2^2 = 1+3 3^2 = 1+3+5 4^2 = 1+3+5+7 ... In C an algorithm would look something like: // Looped square root -- untested. int sqrt(int x) { int odd_int=1; int square_root = 0; while (x>0) { x -= odd_int; square_root++; odd_int += 2; } return square_root; } I believe Nikolai may have code this up for a PIC back in 2000. Scott

I translated your code to Rexx and it worked the first time. /* Rexx */ sqr = 443556 say "the square root of" sqr "is" dosqrt(sqr) return dosqrt: arg x odd_int=1 square_root = 0 do while (x > 0) x = x - odd_int square_root = square_root + 1 odd_int = odd_int + 2 end return square_root Gives: the square root of 443556 is 666 -Lindy {Original Message removed}

On Aug 22, 2005, at 8:57 AM, Lindy Mayfield wrote: >> N^2 = sum of the first N-odd integers > > I believe Nikolai may have code this up for a PIC back in 2000. > Yep. Nicely summarized here: http://www.piclist.com/techref/microchip/math/sqrt/index.htm ;********************************************************************** ;SMALL 8 BIT SQUARE ROOT ; ;Author: Nikolai Golovchenko <golovchenko at mail.ru> ;Idea: Scott Dattalo <http://www.dattalo.com> ;"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 ;**********************************************************************