; 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