Truncated match.
PICList
Thread
'Square root (oh no, not again)'
1997\08\07@235034
by
ame
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

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 socalled "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 16bits 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 32bit input)
380 to 450 cycles
2) Binary square roots using the "nonrestoring method":
~45 instructions
9 Ram locations (including 4 for the 32bit input)
~410 cycles (for all inputs)
3) Hodgepodge. 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 32bit 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 stepbystep behavior of the
algorithms. If anybody wishes to see these godforsaken 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...