'x86 assembly language integer "cube root" with Newton's algorithm
I'm writing a program that calculates the cube root of an unsigned 8-bit integer. I'm using Newton's iteration algorithm to determine the cube root of perfect cube numbers like 1, 8, 27, 64, 125, 216, 343, 512, 729 and 1000. Starting with x0 = 1, the recurrence is:
Desired execution:
Enter a perfect cube: 512
The cube root of 512 is 8
i have tried to write some code and im looking for some help!~ im stuck on the last 5 parts of Newton's algorithm after i get divided by 3.
data segment ;data segment. Keyword db means define byte. You can also define word (dw)
iNum db 225 ;Define input number
tStr db 'Enter a perfect (unsigned 8-bit) cube:',10,'$' ;Prompt for user
oStr db 'The result is:',10,'$' ;Output prompt
iBuff db 4, 5 dup(?) ;Define input buffer
ten db 10
data ends
;stack segment
stack1 segment stack
db 100 dup(?) ;This is the stack of 100 bytes
stack1 ends
code segment
assume cs:code, ds:data, ss:stack1
start:
;Perform initialization
mov ax, data ;Put the starting address of the data segment into the ax register (must do this first)
mov ds, ax ;Put the starting address of the data segment into the ds register (where it belongs)
mov ax, stack1 ;Put the starting address of the stack into the ax register (must do this first)
mov ss, ax ;Put the starting address of the stack segment into the ss register (where it belongs)
;****************** Perform Newton's Algorithm ******************
call get_int ;Call procedure to get user input
mov dl, iNum ;dl contains input number
mov bx, 1 ;x_0 = 1
mov ah, 0 ;Clear ah
mov al, bl ;Move x_k into al
mul bl ;al = x_{k}^{2}
mov cx, ax ;cx = x_{k}^{2}
mov al, dl ;Move input into al (for division)
div cl ;Divide by x_{k}^{2}
mov ah, 0 ;Clear ah (for addition)
add al, bl ;Add x_k
add al, bl ;because it's 2x
mov cl, 3
div cl ;Divide by 3
cmp dl, bl ;Check to see if they are the same
jne gL1S ;Exit loop if they are equal
mov al, 1 ;Set x_k = x_{k+1}
jmp get_int ;Start again
jmp print_int ;Output result
;-------------------------------------------------------------------------------------------------------------------------------------------------------
mov ah, 4ch ;Set up code to specify return to dos
int 21h ;Interpt number 21 (Return control to dos prompt)
;--------------------------------------------------------------------------------------------------------------------------------------------------
;procedure to read an integer
;Input None:
get_int proc
mov ah, 9 ;Specify print string DOS service routine
lea dx, tStr ;Load pointer to string
int 21h ;Call DOS service routine
mov ah, 0ah ;Prepare to call buffered keyboard input
lea dx, iBuff ;Load the address of the buffer into iBuff
int 21h ;Request service from OS
mov ah, 2 ;Specify print string DOS service routine
mov dl, 10 ;Load new line feed into dl
int 21h ;Call DOS service routine
lea si, iBuff ;Point to start of buffer
inc si ;Point to # of chars
mov ch, 0 ;Clear ch for loop
mov cl, [si] ;Get the number of characters read
add si, cx ;Point si to end of buffer
mov dl, 0 ;Clear al to create number
mov bl, 1 ;Stores power of 10
gL1S: ;get_int loop1 start
mov al, [si] ;Get digit
sub al, 30h ;Convert to number
mul bl ;Multiply by power of 10
add dl, al ;Add to total
mov al, bl ;Initialize X10 multiplication
mul ten ;Multiply by 10
mov bl, al ;Store power of 10 back in bl
dec si ;Decrement si
loop gL1S ;Loop until cx == 0
mov iNum, dl ;Store result in memory
ret
get_int endp
;--------------------------------------------------------------------------------------------------------------------------------------------------
;procedure that prints out an integer passed
;Input (al): unsigned 8-bit number for output
print_int proc
mov ah, 9 ;Specify print string DOS service routine
lea dx, oStr ;Load pointer to string
int 21h ;Call DOS service routine
mov dx, '$' ;Set up end of string
push dx ;Put on stack to indicate finished
PLS1:
mov ah, 0 ;Clear ah for division
div ten ;Divide by 10
mov dl, ah ;Store remainder in dl (putting in dl makes output easier below)
push dx ;Store digit for output
cmp al, 0 ;Check to see if we are done looping
jne PLS1
mov ah, 2h ;Setup character output routine
PLS2:
pop dx ;Get last character
cmp dl, '$' ;Check to see if we are finished
je pDone ;Exit loop if equal to $
add dl, 30h ;Convert integer to character
int 21h ;Call character output routine
jmp PLS2 ;Continue looping
pDone:
ret
print_int endp
;--------------------------------------------------------------------------------------------------------------------------------------------------
code ends
end start
Solution 1:[1]
div cl ;Divide by 3 cmp dl, bl ;Check to see if they are the same (1) jne gL1S ;Exit loop if they are equal (2) mov al, 1 ;Set x_k = x_{k+1} (3) jmp get_int ;Start again (4) jmp print_int ;Output result (5)
This is the part of your program that you are asking about.
- (1) What you need is to check if x_{k+1} (in
AL) is equal to x_{k} (inBL). So comparing withDLis not going to work! - (2) The comment says to exit the loop when they are equal but then the
jneinstruction branches on the opposite condition. Moreover, the branch jumps to the middle of the get_int procedure (something that you should never do). This is also a reason for why your program becomes an infinite loop. - (3) Loading 1 into the
ALregister is not equivalent to what the comment states. - (4) This
jmp get_intis another reason why the program loops forever. You need to loop to where you started the calculation. - (5) After having displayed the result, you need to return to DOS. Therefore you should use a
callinstruction here followed by invoking function 4Ch.
The calculation that you have programmed is Y = ((N / (X * X)) + X + X) / 3. This is correct and will work for very small perfect cube numbers like 1, 8, and 27.
Next is the amended version:
mov al, 1 ; X = 1
Again:
mov bl, al ; BL = X
mul bl ; AL = (X * X) MUL modifies AH
mov cl, al
mov al, iNum ; N
mov ah, 0 ; Setup for DIV
div cl ; AL = (N / (X * X)) DIV modifies AH
add al, bl ; AL = (N / (X * X)) + X
add al, bl ; AL = (N / (X * X)) + X + X
mov cl, 3
mov ah, 0 ; Setup for DIV
div cl ; AL = ((N / (X * X)) + X + X) / 3 DIV modifies AH
cmp al, bl
jne Again
call print_int ; Output result
mov ax, 4C00h ; DOS.Terminate
int 21h
The program might encounter an additional problem
;Input (al): unsigned 8-bit number for output print_int proc mov ah, 9 ;Specify print string DOS service routine lea dx, oStr ;Load pointer to string int 21h ;Call DOS service routine
In many implementations of DOS, this function 09h will return with AL=36. That will mess with your AL argument! You need to preserve it:
push ax
lea dx, oStr
mov ah, 09h
int 21h
pop ax
The full range
To make the calculation work for every perfect cube number in your list {1, 8, 27, 64, 125, 216, 343, 512, 729, 1000}, you need to widen from 8 bits to 16 bits. The X * X can safely ignore the high word in DX that you can get non-zero from using N=1000.
mov ax, 1 ; X = 1
Again:
mov bx, ax ; BX = X
mul bx ; AX = (X * X) MUL modifies DX
mov cx, ax
mov ax, iNum ; N
xor dx, dx ; Setup for DIV
div cx ; AX = (N / (X * X)) DIV modifies DX
add ax, bx ; AX = (N / (X * X)) + X
add ax, bx ; AX = (N / (X * X)) + X + X
mov cx, 3
xor dx, dx ; Setup for DIV
div cx ; AX = ((N / (X * X)) + X + X) / 3 DIV modifies DX
cmp ax, bx
jne Again
call print_int ; Output result
mov ax, 4C00h ; DOS.Terminate
int 21h
Sources
This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.
Source: Stack Overflow
| Solution | Source |
|---|---|
| Solution 1 | Sep Roland |