Re: Integer Square Root Algorithm for Processor with MUL, DIV

On Thu, 1 May 2008 13:34:52 -0700 (PDT), Didi <dp@xxxxxxxxxxx> wrote:

Here is it excerpted from a post I have made many years ago,
calculates a 16 bit squre root of a 32 bit number.
The example is in CPU32 (or CF) assembly.

*
* calc. the square root of d1.l; return it in d1.l
* destroys d2,d3,d4
*
sqrtd1
moveq #15,d2 counter
clr.l d3 colect result here
set loop,*
bset d2,d3 try this
move.w d3,d4 extra copy result so far
mulu.w d4,d4 square
cmp.l d1,d4 higher?
bls keepbit branch not
bclr d2,d3 else bit back down
keepbit
dbra d2,loop process all bits
move.l d3,d1 update in d1
rts

I guess this will benefit from the ff1 (Coldfire ISA A+ AFAIK) or
cntlzw (PowerPC) opcodes, which return the position of the first 1
bit, and could be used to setup the loop counter (ff1 / 2).




--
42Bastian
Do not email to bastian42@xxxxxxxxx, it's a spam-only account :-)
Use <same-name>@monlynx.de instead !
.