; sqrt.asm
comment ^

        This sample program uses 486 specific features (but not the
        numeric coprocessor) to calculate the integral portion of a
        square root of a 32-bit positive integer.

        written on Sat  09-16-1995  by Ed Beroset
        and released to the public domain by the author
^
        IDEAL
        MODEL small
        p486

        STACK   400h

        DATASEG
alpha   dd      4145943340       ; a large arbitrary number
result  dw      ?                ; the answer should be about 64389 

        CODESEG
proc  main
        STARTUPCODE                     ;
        mov     edi,[alpha]             ; load 'em up
        call    sqrt                    ; call our sqrt function
        mov     [result],bx             ; demonstrate how to save result
        EXITCODE                        ; bail
endp  main

;/***************************************************************************
;
;   Name:
;       sqrt
;
;   Purpose:
;       Calculate the integral portion of the square root of a
;       positive integer.
;
;   Algorithm:
;
;       The way this is done is rather simple.  First, we use the BSR
;       instruction to scan for the bit number of the most significant
;       bit.  The result of this operation is the log (base 2) of our
;       original.  We use this information to generate a good first
;       guess for our algorithm, since 2**((log[2](X))/2) = sqrt(X).
;       That is, if we halve the log of a number and raise the result to
;       the base of our log, we get the square root of the original.
;
;       Once we have that number, we know that it must be the most
;       significant digit in our answer.  Since this is true, we can
;       successively approximate the answer by "guessing" each of the
;       bits and testing by squaring the guess.
;
;       This is not meant to be an optimal solution, but more of an
;       intellectual curiosity.  If I were actually programming a sqrt
;       function on a 486 class CPU, I'd use FSQRT and be done with it.
;       I haven't actually timed them both yet; totalling execution
;       (e.g. data sheet) timings can lead to incorrect conclusions.
;
;   Entry:
;
;       EDI = the number whose square root we're seeking
;
;   Register usage within the routine:
;
;        AX = scratch register (for multiplications)
;        BX = current guess
;        CX = current bit number
;        DX = scratch register (for multiplications)
;
;   Exit:
;
;        AX = calculated square root
;       EDX = square of number in AX
;       EDI = target value
;
;   Trashed:
;       BX, CX
;
;***************************************************************************/
proc sqrt
        bsr     ecx,edi                 ; get the log (base 2)
        shr     cx,1                    ; log2(alpha)/2
        xor     bx,bx                   ; bx=0
        inc     cx                      ;
top:
        dec     cx                      ;
        bts     ebx,ecx                 ; set bit in our answer
        mov     ax,bx                   ; save copy in ax
        mul     bx                      ; DX:AX = BX*BX
        shl     edx,16                  ; convert DX:AX to EDX
        mov     dx,ax                   ;
        cmp     edx,edi                 ; Q: is test < answer?
        jz      done                    ;   if equal, we're done
        jb      over                    ;   N: yes, so leave bit set
        btc     bx,cx                   ;   Y: too big, clear bit
over:
        inc     cx                      ; to make life a little easier
        loop    top                     ; keep going for more
done:
        ret
endp sqrt

        END