Searching \ for 'Square root (oh no, not again)' in subject line. ()
Make payments with PayPal - it's fast, free and secure! Help us get a faster server
FAQ page: www.piclist.com/techref/index.htm?key=square+root+not
Search entire site for: 'Square root (oh no, not again)'.

Truncated match.
PICList Thread
'Square root (oh no, not again)'
1997\08\07@235034 by ame

flavicon
face
    Hi all,

    last year there was a long thread about square roots.  I have
    resurrected Scott's (Dattalo?) routine from way back and modified it
    (parrot fashion) to find the 12bit root of a 24bit number.  I feel it
    is a little profligate in its use of resources, and in fact one could
    write a 32bit routine with probably no more effort.

    Anyway, it uses 61 instructions and takes of the order of 450 cycles
    to execute (my completely random selection of test numbers yielded
    from 409 to 482 cycles).

    It uses 7 registers (and trashes W) and returns the root shifted left
    by 4 bits (a necessary evil).

    Anyone prepared to enter the fray?

    Andy (#2)

1997\08\11@123127 by sdattalo

face
flavicon
face
ame@SYNAPTICS.COM wrote:

>      last year there was a long thread about square roots.  I have
>      resurrected Scott's (Dattalo?) routine from way back and modified it
>      (parrot fashion) to find the 12bit root of a 24bit number.  I feel it
>      is a little profligate in its use of resources, and in fact one could
>      write a 32bit routine with probably no more effort.
>
>      Anyway, it uses 61 instructions and takes of the order of 450 cycles
>      to execute (my completely random selection of test numbers yielded
>      from 409 to 482 cycles).
>
>      It uses 7 registers (and trashes W) and returns the root shifted left
>      by 4 bits (a necessary evil).
>
>      Anyone prepared to enter the fray?

Why knot?

The specifications you quote for the so-called "parrot modification"
of the original routine are reasonable (read: I didn't try it in detail,
but I did see what it would take to extend the 16-bits to 24 or 32).

I made three other attempts. Two I coded, but didn't test and the
third I didn't even bother to code.

1) Binary square roots using the "restoring method":
 ~45 instructions
   9 Ram locations (including 4 for the 32-bit input)
  380 to 450 cycles

2) Binary square roots using the "non-restoring method":
 ~45 instructions
   9 Ram locations (including 4 for the 32-bit input)
 ~410 cycles (for all inputs)

3) Hodge-podge. For the first 16 bits, use the original sqrt
 routine. For the next 16 use a variation of the previous
 algorithm.

 ~75 instructions
   7 Ram locations (including 4 for the 32-bit input)
 ~320 cycles

All three of these algorithms will trash the original input
and the W register.

In testing the concept behind the implementation of the first
two algorithms, I wrote BASIC programs. While grossly inefficient
they do accurately mimic the step-by-step behavior of the
algorithms. If anybody wishes to see these god-forsaken hacks,
then drop me a line. If you want to see some sqrt theory then
check out:

http://www.interstice.com/~sdattalo/technical/theory/sqrt.html

or the original square root algorithm:

http://www.interstice.com/~sdattalo/technical/software/pic/picsqrt.html

Scott
--
    __o     Hey Mike, did you run out of gas?
    \<
 (*)/(*)

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