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?
     \<
  (*)/(*)