Post by thread:Square root (oh no, not again)

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)

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