Scott Dattalo <PICLIST@MITVMA.MIT.EDU> wrote:

> A week or so ago Andy W. made the claim:
>
> > I have in front of me a 16-bit square-root routine that takes only
> > 126 cycles to execute on a PIC16C5x.
>
> and it requires:
>
> >    RAM:  4 registers, including the two that hold the 16-bit
> >    input. ROM:  24 words.
>
> and finally
>
> > Anyway, [the author] hasn't given me permission to publish it, so
> > I can't post the routine here.  However, the knowledge that such a
> > solution exists should be enough to prod someone into trying to
> > duplicate it.
>
> Well, I've been prodded. However, I've come up a little short. My
> solution requires:
>
>    RAM:  4 registers, including the two that hold the 16-bit input.
>    ROM:  28 words.  (4 words too big)

    Wow, Scott... You've been busy.  Actually, I miscounted both the
    execution time and the ROM required.  The routine actually takes
    27 words (so your 28-word solution isn't so bad), but it runs
    FASTER than I originally said... 113 cycles worst-case, 95
    cycles best-case, and 103 cycles average over the entire range
    [0-65535].

> The way this routine works is based on the following square root
> algorithm:
>
> [pseudo-code deleted]
>
> In other words, x is built up one bit at a time, starting with the
> most significant bit. Then it is squared and compared to N.

    The routine I was referring to uses the same algorithm.

    -Andy

Andrew Warren - fastfwd@ix.netcom.com
Fast Forward Engineering, Vista, California
http://www.geocities.com/SiliconValley/2499