Find some X^2 - Y^2 equal to a given Z

Question

Request input (Z) from user, \$-65535 \leq Z \leq 65535\$.
Check if \$(X^2)-(Y^2)=Z\$ (while \$0 \leq X,Y \leq 1000\$).

I wrote a code which will receive Z from user, if it's negative, store the negative value and continue as if Z is positive. Two loops, one which will check Y from \$0 \mapsto 1000\$, after that add \$1\$ to X and continue, until both X and Y are 1000 (meaning no answer) or until an answer is found.

If Z contained a negative value, exchange X and Y after answer is found. Would love to see some reviews.

    .MODEL SMALL
    .STACK 100h
    .DATA
    EnterNum     DB 13,10,'Please enter a number between (and including) -65535 and 65535: ',13,10,'$'
    AnswerSTR    DB 13,10,'Z =       , X =     , Y =     ',13,10,'$'
    WrongSTR     DB 13,10,'Wrong input, please type a number again (-65535 <= X <= 65535): ',13,10,'$'
    NoAnswerSTR  DB 13,10,'       has no solution below 1000',13,10,'$'
    Z            DD ?
    X            DD ?
    Y            DD ?
    I            DD ?
    J            DD ?
    NumSign      DD 1
    Ten          DD 10
.CODE
.386
    MOV AX,@DATA
    MOV DS,AX
    XOR EAX,EAX
    MOV CX,6 ;Initialize CX for the loop of receiving num
    MOV AH,9
    MOV DX,OFFSET EnterNum
    INT 21h ;Print request num from user
TypeAgain:
    XOR DX,DX
ReceiveNum:
    MOV AH,1
    INT 21h
    CMP AL,45 ;Ascii for minus
    JE SignSave
    CMP AL,13 ;Ascii for enter key
    JE EnterKey
    SUB AL,'0' ;Convert from Ascii value to numeral value (if reached this point then it's SUPPOSED to be a number)
    CMP AL,0
    JB WrongInput
    CMP AL,9
    JA WrongInput ;Check if input is correct (0-9)
    XOR AH,AH
    ADD Z,EAX ;Save digit in Z
    MOV EAX,Z
    MUL Ten
    MOV Z,EAX ;Save digit multiplied by 10 in order to make place for the new digit (if enter, will go to EnterKey label)
    XOR EAX,EAX
    LOOP ReceiveNum
    MOV AH,1
    INT 21h
    SUB AL,'0'
    CMP AL,0
    JB WrongInput
    CMP AL,9
    JA WrongInput
    XOR AH,AH
    ADD Z,EAX ;Receive last digit in number
    JMP Initialize
WrongInput:
    MOV AH,9
    MOV DX,OFFSET WrongSTR
    INT 21h
    JMP TypeAgain
SignSave:
    MOV NumSign,-1
    JMP ReceiveNum
EnterKey:
    XOR EAX,EAX
    MOV EAX,Z
    DIV Ten
    MOV Z,EAX ;Z has number entered by user
Initialize:
    MOV X,0
    MOV I,0
    MOV J,0
    JMP CheckAnswerX ;Z will have number from user, NumSign will have -1 if number is negative (remain 1 if positive)
IncX:
    XOR EAX,EAX
    INC I ;To help with count of X
    MOV EAX,I
    MOV X,EAX
    MUL X
    MOV X,EAX ;X contains the value of X^2
CheckAnswerX:
    XOR EAX,EAX
    MOV Y,0
    MOV J,0
CheckAnswerY:
    XOR EAX,EAX
    MOV EAX,J
    MOV Y,EAX
    MUL Y
    MOV Y,EAX ;Y contains value of Y^2
    XOR EAX,EAX
    MOV EAX,X
    SUB EAX,Y ;EAX - Y, keep value in EAX
    CMP EAX,Z
    JNE ContinueCheck
    JMP Answer ;Meaning they're equal and we have the answer
ContinueCheck:
    XOR EAX,EAX
    MOV EAX,I
    ADD EAX,J
    CMP EAX,2002 ;Check if X and Y made their 1001 loop separately (sum of both is 2002)
    JE NoAnswerStop
    XOR EAX,EAX
    MOV EAX,J
    CMP EAX,1001 ;Check if Y made it's 0-1000 run
    JE IncX ;Meaning Y needs to start from 0 again and add 1 to X
    INC J ;To help with count of Y
    JMP CheckAnswerY
Answer:
    XOR EAX,EAX
    MOV EAX,I
    MOV X,EAX ;X contains it's original value of the answer (before the degree)
    XOR EAX,EAX
    MOV EAX,J
    MOV Y,EAX ;Y contains it's original value of the answer (before the degree)
    CMP NumSign,-1 ;If Z has a negative value
    JE ExchangeXY
    JMP Answer2 ;Else jump to Answer2 label
ExchangeXY: ;Exchange Y and X values so we receive correct negative Z
    XOR EAX,EAX
    MOV EAX,X
    XCHG EAX,Y
    MOV X,EAX
Answer2: ;Start inserting the values of Y, X and Z into the string
    XOR CX,CX
    MOV CX,4
    XOR SI,SI
    MOV SI,31
    MOV EAX,Y
ReplaceAnswerY:
    DIV Ten
    ADD DL,'0' ;Convert from numeral value to Ascii value
    MOV AnswerSTR[SI],DL
    DEC SI
    XOR EDX,EDX
    LOOP ReplaceAnswerY
    XOR CX,CX
    MOV CX,4
    XOR SI,SI
    MOV SI,21
    MOV EAX,X
ReplaceAnswerX:
    DIV Ten
    ADD DL,'0'
    MOV AnswerSTR[SI],DL
    DEC SI
    XOR EDX,EDX
    LOOP ReplaceAnswerX
    JMP ReplaceAnswerContinueX
NoAnswerStop:
    JMP NoAnswer
ReplaceAnswerContinueX:
    XOR CX,CX
    MOV CX,6
    XOR SI,SI
    MOV SI,11
    MOV EAX,Z
ReplaceAnswerZ:
    DIV Ten
    ADD DL,'0'
    MOV AnswerSTR[SI],DL
    DEC SI
    XOR EDX,EDX
    LOOP ReplaceAnswerZ
    CMP NumSign,-1
    JE ChangeSignString
    MOV AH,9
    MOV DX,OFFSET AnswerSTR
    INT 21h
    JMP CodeEnd
ChangeSignString:
    MOV AL,45
    MOV AnswerSTR[5],AL
    MOV AH,9
    MOV DX,OFFSET AnswerSTR
    INT 21h
    JMP CodeEnd
NoAnswer: ;Insert value of Z into the string
    XOR CX,CX
    MOV CX,6
    XOR SI,SI
    MOV SI,7
    MOV EAX,Z
ReplaceNoAnswerZ:
    DIV Ten
    ADD DL,'0' 
    MOV NoAnswerSTR[SI],DL
    DEC SI
    XOR EDX,EDX
    LOOP ReplaceNoAnswerZ
    MOV AH,9
    MOV DX,OFFSET NoAnswerSTR
    INT 21h
CodeEnd:
    MOV AH,4Ch
    INT 21h
    END

Answer 1

Ooooh... MS-DOS Assembly programming! That was a long time ago for me, but here goes.

There's a lack of error handling with the number entered, since a user can enter 99999 for Z and your program does not complain. The SUB, CMP, JB sequence can lose the CMP instruction since the flags will already be set by the subtraction. You can also get rid of the JB in this case, since the next check (CMP AL,9/JA) will detect all the wrong inputs.

There are many places where you zero out a register with XOR when you don't need to zero it out at all. The sequence

XOR EAX,EAX
MOV EAX,Z

The XOR is unnecessary since you immediately replace the register content with a new value.

You need to zero out the EDX register before the DIV Ten instruction after the EnterKey label (or any of the other places you use DIV). You can also rewrite the code so that this isn't required: Multiply by ten before adding in the new digit, rather than before getting the next digit from input.

In the Initialize section, you can zero out a register then store that value (which uses shorter instructions than storing a constant to memory).

In IncX, the first MOV X,EAX is unnecessary since you replace it two instructions later. The same applies for MOV Y,EAX under CheckAnswerY.

The JNE ContinueCheck/JMP Answer/ContinueCheck: sequence can be replaced with a simple JE Answer.

You've hardcoded the offset to store the answer in (MOV SI,31). Your data declaration can be updated to include a label for this spot so you can store the address directly into SI. Similarly, you can get rid of the constant used in ReplaceAnswerX, and where the sign is stored in ChangeSignString, and the offset used in NoAnswer.

Answer 2

In pseudocode, your program looks roughly like this:

z = |z|
for x = 0..1000
  for y = 0..1000
    if x² - y² = z -> return true
return false

It can be made faster by several orders of magnitude if you got rid of the nested loops:

x = y = 0
z = |z|
while x <= 1000:
  r = x² - y² - z
  if r = 0: return true
  if r < 0: x += 1
  if r > 0: y += 1
return false

Alternatively, we can iterate down to zero, which better suits an assembly implementation.

x = y = 1000
z = |z|
while y >= 0:
  r = x² - y² - z
  if r = 0: return true
  if r < 0: y -= 1
  if r > 0: x -= 1
return false

We still face the problem that intermediate results in r = x² - y² - z can be rather large, which is probably the reason you restricted x and y to values below 1000. Incremental updates to the residual are not only numerically superior, they are also faster and allow us to get away without a single multiplication:

x = y = 1000
r = -|z|
while y >= 0:
  if r = 0: return true
  if r < 0: y -= 1, r += 2y + 1
  if r > 0: x -= 1, r -= 2x + 1
return false

In x86 assembly, this results in a fairly tight loop.

x = y = 1000
r = -|z|

  cmp r, 0
  jl negative
  jmp success

positive:
  dec x
  lea r [r - 2*x]
  dec r              ; implicitly sets status flags
  jl negative        ; most taken branch
  jg positive
  jmp success

negative:
  dec y              ; implicitly sets status flags
  jl fail            ; continue while y >= 0
  lea r [r + 2*y]
  inc r              ; implicitly sets status flags
  jl negative        ; most taken branch
  jg positive
  jmp success

fail:
  ...
success:
  ...

As was suggested in the comments, a slightly modified implementation can handle both negative and positive values of z naturally:

x = y = 1000

  cmp z, 0
  jl negative
  jg positive
  jmp success

positive:
  dec y              ; implicitly sets status flags
  jl fail            ; continue while y >= 0
  lea z [z - 2*y]
  dec z              ; implicitly sets status flags
  jg positive
  jl negative
  jmp success

negative:
  dec x              ; implicitly sets status flags
  jl fail            ; continue while x >= 0
  lea z [z + 2*x]
  inc z              ; implicitly sets status flags
  jl negative
  jg positive
  jmp success

fail:
  ...
success:
  ...

Answer 3

I see a number of things that may help you improve your program.

Factor out common code into subroutines

Several places use largely identical code which could be factored out into a routine instead. For example, you could use a subroutine for converting each number into its ASCII equivalent. Here's one way to do that:

;----------------------
; StoreDec
;
; ENTRY: 
;   es:di ==> *end* of target string
;   ax = number to convert to decimal string
;
; EXIT: 
;   es:di ==> one before last written digit
;
; TRASHED: 
;   ax, bx, dx, flags
; 
StoreDec proc
    std         ; move backward
    mov bx, 10  ; use base 10
nextDigit:
    xor dx, dx  ; zero top part
    div bx      ; remainder:quotient in dx:ax
    xchg ax, dx ; 
    add al, '0' ; convert quotient to ASCII digit
    stosb
    mov ax, dx  ; recover remainder
    or ax, ax   ; is it zero?
    jne nextDigit
    ret
StoreDec endp

Study the intruction set

A few cases in the current code have sequences like this one:

SUB AL,'0'
CMP AL,0
JB WrongInput

Because the sub instruction already sets the flags, the cmp instruction can simply be deleted.

Minimize register usage

With assembly language programming, minimizing the use of resources is often vital. One of the most precious resources is the processor's registers. Write comments to help you keep track of which registers are used for which purposes. It is possible to refactor this code so that none of the numeric variables are used and everything needed is stored in registers, given appropriate care.

Think of the user

I'd probably prefer to at least have the option of specifying the number \$Z\$ on the command line. When the program begins, the command line argument(s), if any, are located in the DOS PSP. I'd suggest looking there first and then only issuing prompts if a command line argument is missing or invalid.

Fix the bug(s)

The stated input parameters are not enforced very well. For example, if the user enters 9000000 as the input value, the program falsely claims that:

000000 has no solution below 1000

First, the program should validate that the input is within the stated range and second, the program should inform the user of the faulty input rather than wasting many CPU cycles creating an incorrect answer.

Rethink the algorithm

The algorithm used in this code is extremely inefficient and can easily be improved to much much faster. First, let's look at the mathematics:

The difference of two squares \$x^2 - y^2 = (x+y)(x-y)\$. So instead of doing two multiplication operations and a subtraction, we can do two addition/subtractions and one multiply. This is usually beneficial because adding and subtracting is very often faster than multiplication or division.

Next, notice that we can keep the sum and difference and don't really need to recover the actual X and Y values until the end. For simplicity, in the alternative implementation I wrote, I keep \$x, sum\$ and \$diff\$.

You've already correctly observed that the only difference between, say -5 and +5 for \$z\$ is that the values of the corresponding \$x, y\$ pair are reversed. We can further exploit this fact by noting that if we only look for the absolute value of \$z\$, we can observe that if the value of \$x^2 - y^2 > |z|\$, there's no point in further incrementing the \$x\$ value because that will only make the number even larger. We can then test for this and increment \$y\$ if we observe this condition.

Lastly, it is obvious that if \$x = y, x^2 - y^2 = 0\$ and also that if we're only looking for a positive value, then \$x > y\$.

Putting all of these observations together, the algorithm is:

1. store \$|z|\$ and sign separately. Hereafter we use \$z\$ to mean \$|z|\$.
2. set \$x = y = sum = diff = 0\$
3. compare \$(x+y)(x-y) , z\$
4. if \$(x+y)(x-y) = z\$, we're done
5. if \$(x+y)(x-y) > z\$, go to step 9
6. increment \$x, sum, diff\$
7. if \$x > 1000\$, there is no answer
8. go to step 3
9. increment \$y\$
10. if \$y > 1000\$, there is no answer
11. set \$x = y+1\$ and recalculate \$sum, diff\$
12. go to step 3

When we print the result, the only difference is that if the original sign of \$z\$ was negative, then swap \$x, y\$

Be aware of real machines

It's unlikely you'll encounter anything less than a .386 machine these days, but be aware that your use of 32-bit registers EAX, etc. means that this code will not run correctly on a real 8088 or 8086 machine.

Return an error code

When the program returns, it has the option of returning an error code. I'd suggest that a value of 0 would mean that suitable \$x, y\$ values have been found, an error code of 1 would mean not found, and an error code of 2 could mean "bad input." The return value goes into the al register when executing int 21h, function 4ch.

Answer 4

You can rearrange your equation:

$$X^2 = Z + Y^2$$

Since you are solving where \$Z \ge 0\$, then \$ |X| \ge |Y|\$, so you can stop your inner loop when Y reaches X, instead of continuing up to 1000.

Alternately, loop for Y over the range 0..1000, calculate \$X^2\$, and do a binary search on the range Y..1000, looking for the X with the desired square.

---

Instead of:

CMP AL,45 ;Ascii for minus

You should probably write:

CMP AL,'-' ;Is the number negative?

---

It looks like the user can type -123 as 123- or 1-23 or even -1-2--3-. You don’t restrict the minus sign to only being the first character.

---

Since NumSign is initialized to 1 by loading the code image, the code is only guaranteed to run correctly once. Once a negative number has been entered, NumSign will be changed to -1, and will not be set back to 1 without reloading the program image.

You should use NumSign DD ? and explicitly set NumSign to 1 at the beginning of you code MOV NumSign,1, to allow the code to be executed move than once.