ASM Community

lovelypp,

Check this site out. Ratch

http://www.bmath.net/bmath/index.html

You may also want to look at the following procedure which is part of a fixed point math library available at the very bottom of the following site page (mixlib09.zip):

http://www.movsd.com/source.htm

sqrt32 proc public uInt:DWORD

	

    ; -------------------------------------------------------------

    ; Returns the square root of a 32-bit unsigned integer

    ; The result is rounded to the closest integer.

    ;

    ; eax, ebx, ecx, edx used

    ;

    ; EXAMPLE: invoke sqrt32, 32_bit_value

    ; 

    ; Returns result in eax

    ;

    ; -------------------------------------------------------------



    mov edx,uInt

    xor eax,eax

    mov ebx,40000000h

    mov ecx,16

sqr10:

    add eax,ebx

    cmp eax,edx

    ja  sqr40

sqr20:

    sub edx,eax

    add eax,ebx

    jnz sqr50

sqr40:

    sub eax,ebx

sqr50:

    shr eax,1

    shr ebx,2

    dec ecx

    jnz sqr10



    cmp eax,edx

    jae @F

    inc eax



  @@:    

    ret

    

sqrt32 endp

Another similar procedure is also available to extract the square root of 64-bit integers (albeit slower).

Raymond

Greetings,

This is an alternative approach based on an article which appeared
in Dr. Dobbs some time ago:

sqroot PROC USES edi N:DWORD

         mov    edi, N

         mov    eax, 1 

         cmp    edi, 2 

         jle    short @F



         mov    ecx, 4 

         mov    edx, 5 

@1:

         cmp    edi, ecx

         jle    short @F

         

         add    ecx, edx    ;edx = 2*N-1 ecx = N^2 eax = N-1

         add    edx, 2      

         inc    eax 

         jmp	 short @1

@@:	

         jl     short @2

         inc    eax 

@2:   

         ret

sqroot ENDP

Greetings >Matrix<,

The code isn't optimal and is suitable for relatively "small" integer inputs.
However it can be used as the basis for a more optimal version.

Well, my previous code submission is as slow as molasses even after
souping it up alittle. I'm not exactly an optimization expert. As an
alternative I developed a mod of Raymond's sqrt32 routine. The resulting
code varies from about 0% to 50% faster over the entire 32bit input range
depending on the input.

;------------------------------------------------

; Modified version of Raymond's nearest integer square root

; routine 'sqrt32'.

;

; Basic idea: Enhance computation by using the highest bit set in 

; the operand to compute a suitable upper bound.

;

; Destroys ecx and edx 

; Result returned in eax 

;------------------------------------------------

sqrt32b proc public USES ebx uInt:DWORD 

       xor   eax, eax 

       mov   edx, uInt



       bsr   ecx, edx 

       and   ecx, 0FFFFFFFEh 

       mov   ebx, 1

       shl   ebx, cl

       shr   ecx, 1  

       inc   ecx 

@@:

       add   eax, ebx     

       cmp   eax, edx      

       ja    short @@1

       sub   edx, eax       

       add   eax, ebx

       jnz   short @@2

@@1:

       sub   eax, ebx

@@2:

       shr   eax, 1

       shr   ebx, 2

       dec   ecx

       jnz   short @B



       cmp   eax, edx

       jae   short @F

       inc   eax

@@:   

       ret

sqrt32b endp

To make our initial guess at the sqrt, we could use the BSR (bit scan reverse) opcode, which is a sort of crude base-2 logarithm. Say the input is in EAX.

bsr ecx,eax   ;If eax<>0, this puts a value of 0 to 31 in ecx, namely

           ;the index of the most significant set bit in eax.

jnz eax_was_zero  

shr ecx,1  ;For the square root, divide the "logarithm" in half.

jz eax_was_one

xor ebx,ebx

stc

rcl ebx,cl  ;Now ebx is our initial guess.

If you don't mind some inaccuracy, Andre LaMothe in one of his huge game programming books used this short routine to extract a square root of a 32bit floating point number. It can easily be converted from and to an integer with the fild and fst instructions which might round off some of the error. According to this the square root of 144 is 12.5 instead of 12 so use with caution.

.data ?

                float_variable real4 ?

.code	

                mov eax, float_variable

                sub eax, 3f800000h

                sar eax,1

                add eax, 3f800000h

                mov float_variable, eax  

I just whipped it up...

Sqrt PROC uint32:DWORD

	xor ecx, ecx

	xor eax, eax

	bsr edx, uint32

	and edx, -2	; even

	bts ecx, edx



s0:	add eax, ecx

	sub uint32, eax

	jnc s1

	add uint32, eax

	sub eax, ecx

	jmp s2



s1:	add eax, ecx

s2:	shr eax, 1

	shr ecx, 2

	jne s0

	ret

Sqrt ENDP

This in the itterative method that one might use by hand with pencil and paper; but in binary and optimized. The algorithm is undefined at zero.

I don't know much about IC design, but I think this algorithm could have a space saving over the implementation defined in the following document:
http://venus.elfak.ni.ac.yu/projects/IMPEG/DigitalSystem.pdf