Searching \ for '[EE] 8051 Coding challenge' in subject line. ()
Help us get a faster server
FAQ page: piclist.com/techref/index.htm?key=8051+coding+challenge
Search entire site for: '8051 Coding challenge'.

Exact match. Not showing close matches.
'[EE] 8051 Coding challenge'
2005\08\22@091421 by

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}

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
;**********************************************************************

More... (looser matching)
- Last day of these posts
- In 2005 , 2006 only
- Today
- New search...