Population

SQUAREROOT--A APPROACH BY BINARY SEARCH

1¡£How to calculate squareroot?

It seems an meaningless question, but how? I can only imagine a binary search method, that is continuingly test if its square is equal to the questioned number.

2. Main function

It is painful to code in assembly only because there is no basic calculation tools, like multiply and divide! I spent my 80% of time in switching between 16bit multiply or dividing and 8 bit multiply and dividing. It is ugly painful.

A. INPUTNUMBER PROC

input: none;

output: ax output the number of what the user key in which should be ended with return key after number.

Is it naive to write this kind of stupid function? There is simply nothing built in to use. You have to do everything by yourself. And I hate to check number consistency. If user key in char other than number, then let it down.

B. DISPLAYNUMBER PROC

input: ax input the number you want to display

output: none

It is another example of nasty assembly code. I have to switch between 16bit and 8bit dividing all the time. and I hate it this to death! I divide the number continually by 10 and find the remainder to be saved in stack. Then, after add 30h to change it into ASCII, I display them one by one from stack.

C. SQUAREROOT PROC

input: ax input the number to find the squareroot.

output: ax output the approximate square root. Excuse me, I destroy your input data deliberately!!!

I hate to debug it for a half night and half morning which made me furious. It is a bad experience as I have to switch all the way between the 16bit and 8bit dividing and multiply.

It is as simple as a basic binary search, got it? Try to set up a low bound and high bound of searching scope, pick the mid point to test the square of the mid to see if it is equal to the questioned number. If less, try to move high bound to one lower than mid, if greater, move low bound one higher than mid. if equal, congratualtions, you got it. If after moving the bound, you find that your new bound is exceeding the opposite bound(I.E. low bound moved, and higher than high bound, or vise vosa), Congratulations, you find an approximate number which is the current mid.

I limit the input number to be less than 65535 of which the root is 255.

¡¡

2. ÎÒµÄ³ÌÐò

    .DOSSEG
    .MODEL SMALL
    .STACK 100H
    .DATA

    MSG DB "THIS IS TRUE", "$"

    .CODE
    START:

    	MOV AX, @DATA
    	MOV DS, AX

    	CALL INPUTNUMBER
    	CALL SQUAREROOT
    	CALL CHANGELINE
    	CALL DISPLAYNUMBER

    	MOV AX, 4C00H
    	INT 21H

    CHANGELINE   PROC
    	PUSH AX
    	PUSH DX
    	MOV AH, 02
    	MOV DL, 0DH
    	INT 21H
    	MOV DL, 0AH
    	INT 21H
    	POP DX
    	POP AX
    	RET
    CHANGELINE  ENDP

    DISPLAYNUMBER	PROC
    	PUSH BX
    	PUSH CX
    	PUSH DX
    	MOV BX, 10
    	MOV CX, 0
    BEGINDIVIDE:
    	CMP AH, 0
    	JE  SMALLDIVIDE
    BIGDIVIDE:
    	DIV BL
    	ADD DX, 30H
    	PUSH DX
    	INC CX
    	JMP BEGINDIVIDE

    SMALLDIVIDE:
    	CMP AL, 0
    	JE  SHOWRESULT
    	DIV BL
    	MOV DX, 0
    	MOV DL, AH
    	MOV AH, 0H
    SAVERESULT:
    	ADD DX, 30H
    	PUSH DX
    	INC CX
    	JMP SMALLDIVIDE
    SHOWRESULT:
    	CMP CX, 0
    	JE  ENDDISPLAY
    DISPLAYLOOP:
    	MOV AH, 02H
    	POP DX
    	INT 21H
    	LOOP DISPLAYLOOP
    ENDDISPLAY:
    	POP DX
    	POP CX
    	POP BX
    	RET
    DISPLAYNUMBER	ENDP

    SQUAREROOT  PROC
    	PUSH BX
    	PUSH CX
    	PUSH DX
    	PUSH SI
    	PUSH DI
    	MOV CX, 00H
    	MOV BX, AX; BX SAVE THE NUMBER
    	CMP BX, 255; THE BIGGEST ROOT OF 16BIT
    	JG  LOCAL1
    	MOV DI, BX
    	JMP LOCAL2
    LOCAL1:
    	MOV DI, 255; THIS IS UPPER BOUND OF 16BIT ROOT
    LOCAL2:

    	MOV SI, 1; LOWBOUND

    CHECKRESULT:
    	MOV AX, SI
    	ADD AX, DI ; AX IS THE SUM OF LOW AND HIGH BOUND
    	MOV DL, 02H
    	CMP AX, 255
    	JLE LOCALSMALL
    	DIV DL
    	MOV CX, AX; ROOTS SAVED BY 16BIT DIV
    	MUL AX
    	JMP COMPARE
    LOCALSMALL:

    	DIV DL
    	MOV CL, AL; SAVE ROOT IN CX
    	CMP AL, 15
    	JLE LOCAL3 ; THE MUL IS 8BIT
    	MUL AX; 16BIT MUL
    	JMP COMPARE

    LOCAL3:
    	MOV AH, 00H ; IT IS 8BIT MUL
    	MUL AL; SQUARE

    COMPARE:
    	CMP AX, BX
    	JE  FINDRESULT
    	CMP AX, BX
    	JL  SMALLER

    BIGGERR:
    	DEC CX
    	CMP CX, SI; COMPARE LOWBOUND
    	JL  FINDRESULT; EXCEED LOW BOUND
    	MOV DI, CX;NEW HIGH BOUND
    	JMP NEXT

    SMALLER:
    	INC CX
    	CMP CX, DI; COMPARE HIGHBOUND
    	JG FINDRESULT  ; EXCEED LOW BOUND
    	MOV SI, CX; NEW LOW BOUND
    	JMP NEXT
    NEXT:

    	JMP CHECKRESULT
    FINDRESULT:
    	MOV AX, CX; RESULT IS RETURN IN AX
    	POP DI
    	POP SI
    	POP DX
    	POP CX
    	POP BX
    	RET
    SQUAREROOT  ENDP

    INPUTNUMBER PROC
    	PUSH BX
    	PUSH CX
    	MOV AX, 00H
    	MOV BX, 00H
    	MOV CX, 00H

    CHECK:
    	MOV AH, 01H
    	INT 21H
    	CMP AL, 0DH
    	JE ENDINPUT
    	MOV CL, AL; SAVE INPUT IN CX
    	MOV AX, 10; PREPARE MUL
    	MUL BX	  ; OLD DATA IN BX
    	SUB CX, 30H; CX TO BE NUBMERS
    	ADD AX, CX
    	MOV BX, AX; SAVE DATA IN BX
    	JMP CHECK

    ENDINPUT:
    	MOV AX, BX; RETURN VALUE IN AX
    	POP CX
    	POP BX
    	RET
    INPUTNUMBER ENDP

    END START
    END

¡¡

Click here to download the execute file to have a try. Just run and key in a number smaller than 65535 ended by return and you get the approximate answer or exact answer, depending if the number has an integer root or not.