Newtons Raphson Iteration issues

Question

I am writing a 8bit integer newton raphson function in MASM X8086-32bit assembly and I think I am stuck in an infinite loop. The editor I have to use for class does not send an error for infinite loops.

Anyways I am not sure where my problem is. I just started MASM a few weeks ago and am kind of lost any help with the infinite loop would be appreciated. My initial x value is defined as 1.

The function is y = 1/2(x+n/x) ===> x/2+ n/2x where n is the number in question. and x is the intitialized value and then the previous iterations y value.

    mov ah, 09h
    lea dx, prompt  ;Prompt User
    int 21h

    mov ah, 01h
    int 21h         ;User input
    sub al, 30h

    mov bh, al
    mov bl, x       ;Loading for loop
    mov al, x

    iteration:
                mul bl; al*bl = al

                mov dl, al ; storing x^2

                add al, 01h ; (x+1)^2
                mul al

                cmp bh, dl
                jge doneCheck ; bh - dl ====> n- x^2 => 0
                doneCheck:
                cmp bh, al; bh-al = ? ====>n - (x+1)^2 == -int
                jl done

                mov al, 02h; loading 2 in ah
                mul bl  ; bl*al = 2(bl) = 2x = al

                shr bl, 1 ; x/2 = bl

                mov cl, al ; storing 2x in cl
                mov ah, 0 ; clearing ah
                mov ch, 0; clearing ch
                mov al, bh ; moving n into ax for division prep
                div cx ; ax/cl ====> n/2x ===> p =ah and q = al

                add bl, ah ;so this is finally 1/2(x+(n/x)) === (x/2+n/2x) y the new value y is now stored in bl for next loop
                mov al, bl ; for next loop
                jmp iteration

    done:

    mov dl, bl; print square root
    mov ah, 02h
    int 21h

Answer 1

This:

shl bl, 1 ; x/2 = bl

shouldn't be?:

shr bl,1

-- Updated:

And about your question:

BH = Number to find sqrt. When x^2 == BH then x is the sqrt(n)
AL and BL = y value of the last iteration

and you do:

mul bl     ; AL*BH => AX
cmp bh, al ; BH == AL? or with names: n == x^2 ?

Why the infinite loop?:

As you take the input with AH=01h+int 21h, you only read one char and you get the ascii code in AL.

Let's assume the user input number is "A", which is translated into the number 65. By no means, any integer will give you x^2 = 65, so that loop will loop forever.

I suggest you to use this condition as the loop break. The result will be an approximation (rounded to the lower number):

(n >= x^2) && (n < (x+1)^2)

Bear in mind that you are working all with 8 bits, so the highest solution would be: y = 15. Look at this:

1^2 = 1
2^2 = 4
3^2 = 9
4^2 = 16
5^2 = 25
6^2 = 36
7^2 = 49
8^2 = 64
...
15^2 = 225

Those are the only numbers you can calculate sqrt with your code (without my proposal).

So you can only press the following keys as input:

$ = number 36
1 = number 49
@ = number 64
Q = number 81
d = number 100
y = number 121

Any keypress between those will make your code get into an infinite loop.

And a tip for output: add 48 to BL before printing it so it goes to an ASCII number :)

-- Update 2 :

From your code I found this errors:

add al, 01h ; (x+1)^2 ; AL = x^2, therefore you are doing (x^2)+1
mul al

and here the execution flow will execute all lines always:

cmp bh, dl
jge doneCheck ; bh >= dl? ====> n >= x^2 ?
doneCheck:
cmp bh, al; bh-al = ? ====>n - (x+1)^2 == -int
jl done

I guess it should be something like:

  cmp bh, dl     ; n vs x^2
  jb notSolution ; BH < DL? ====> if n < x^2 continue with next NR step
  cmp bh, al     ; here, n >= x^2
  jb done        ; BH < AL ? ====> if n < (x+1)^2 we found a solution

notSolution:     ; n is not in [ x^2 , (x+1)^2 )

I used jb instead of jl because I assume only possitive numbers. jl will treat 129 as a negative number and maybe we will be in trouble.

-- Update 3:

From Peter Cordes' answer, a detail I didn't notice (I read div cl):

div cx ; ax/cl ====> n/2x ===> p =ah and q = al. That would be correct if you'd used div cl

Answer 2

I'm not sure you've correctly understood that MUL and DIV have one operand each that's double the width of the other two.

Your comments on those lines are wrong:

• mul bl; al*bl = al: no, AX = AL*BL.
• div cx ; ax/cl ====> n/2x ===> p =ah and q = al. That would be correct if you'd used div cl, but DIV r/m16 takes DX:AX as a 32-bit dividend, and produces results in AX=quotient, DX=remainder.

Look up MUL and DIV in the manual.

---

I highly recommend single-stepping through your code in a debugger. And/or stopping it in a debugger after it gets into an infinite loop, and single step from there while watching registers.

The bottom of the x86 tag wiki has some tips on using GDB to debug asm. (e.g. use layout reg). Since you're using MASM, you might be using Visual Studio, which has a debugger built in.

It doesn't matter what debugger you use, but it's an essential tool for developing asm.