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

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
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
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
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
XOR EAX,EAX
MOV Y,0
MOV J,0
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
CMP EAX,2002 ;Check if X and Y made their 1001 loop separately (sum of both is 2002)
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
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
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
DIV Ten
ADD DL,'0' ;Convert from numeral value to Ascii value
DEC SI
XOR EDX,EDX
XOR CX,CX
MOV CX,4
XOR SI,SI
MOV SI,21
MOV EAX,X
DIV Ten
DEC SI
XOR EDX,EDX
XOR CX,CX
MOV CX,6
XOR SI,SI
MOV SI,11
MOV EAX,Z
DIV Ten
DEC SI
XOR EDX,EDX
CMP NumSign,-1
JE ChangeSignString
MOV AH,9
INT 21h
JMP CodeEnd
ChangeSignString:
MOV AL,45
MOV AH,9
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
DIV Ten
DEC SI
XOR EDX,EDX
MOV AH,9
INT 21h
CodeEnd:
MOV AH,4Ch
INT 21h
END

• Out of curiosity: why assembly? If it's for learning or a school project, fine. But these days, for any kind of serious application development, it's rare to see assembly - and even then, only in "critical sections" or while debugging. – Reinderien Dec 22 '18 at 17:57
• True but as you assumed, it's for a course I'm taking in college – S.Arkab Dec 22 '18 at 19:08

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:
...

• Kind of feel bad none of these methods came to my mind while trying to solve it.. Thank you, great info!! – S.Arkab Dec 23 '18 at 16:46
• The absolute value is now unnecessary with this algorithm . The x,y values will track by themselves to x>y if z>0 and x<y if z<0. Eliminate the absolute value and there is no longer a need to swap the values at the end. – AJNeufeld Dec 23 '18 at 18:18

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.

• As for the restriction of Z, I couldn't really figure out how to do that with the whole number.. +1 for the info about the SUB and it's flag, as for the removing JB, there are chars below 0, won't that make them possible to enter? Thank you for the XOR and DIV tip as well! Didn't understand what you meant to do in Initialize section... in IncX, I do that since the value of X will be by degree of 2, so it needed a reboot to the value of I everytime. Thank you for the JNE tip. The comment about the offset lines, didn't understand this.. @1201ProgramAlarm – S.Arkab Dec 22 '18 at 20:28
• There is the ja (Jump above, unsigned comparison) and jg (Jump greater, signed comparison). ja will jump if the unsigned byte in AL is greater than 9. In initiialze: XOR EAX,EAX/MOV X,EAX/MOV I,EAX/MOV J,EAX. You don't need to define a complete string in one line. You can split it across multiple db lines and add labels wherever you need to reference the string. – 1201ProgramAlarm Dec 22 '18 at 20:58

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.

• Thank you!! Question, I'm having real trouble restricting the input number, any tips on how I should do it? – S.Arkab Dec 23 '18 at 16:47
• One simple way to do that is to note that the absolute value of the allowable input numbers is 0 - 65535. That is exactly what fits in a 16-bit register (0000h to FFFFh), so as you add and multiply using 16-bit registers, just check the carry flag. If it's ever set after a mul or add instruction, the number is out of range. – Edward Dec 23 '18 at 16:51

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.

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.

• Sorry didn;t quite understand, but if I did then isn't it the same as I'm doing only need to change the inner loop for compare with X? Thank you. – S.Arkab Dec 22 '18 at 20:16
• Couldn't edit my previous comment, but same question goes for the CMP AL,45/'-', aren't they the same just different way of typing? Thank you! @AJNeufeld – S.Arkab Dec 22 '18 at 20:32
• The first two comments are aimed at improving your algorithm. As it stands, if no answer can be found, it will have taken 1,000,000 iterations. The first comment could reduce it to 500,000 and the second can reduce it to 8000. – AJNeufeld Dec 22 '18 at 20:42
• Yes, 45 and '-' are the same, I think, I haven’t checked. But why should I check when you could just write '-'. Why did you write SUB AL,'0' when you could write SUB AL,48? One is much, much clearer to the reader. Comments can help explain the code, but here you can let the assembler turn '-' into 45, and let the comment explain the why, instead of wasting the comment explaining that ASCII 45 is the minus sign. – AJNeufeld Dec 22 '18 at 20:51
• Yes, your original implementation takes the Z entered, saves the sign, solves the problem, and reverses the X/Y if the saved sign was negative. So, you are solving the sub-problem where Z >= 0. Now consider the inner loop when the outer loop has reached X=100. 100^2 = Z + Y^2. Y=0 through Y=100 are all possible solutions. But once Y is incremented to larger the X, 100^2 = Z + 101^2 has no solution since Z is not negative. – AJNeufeld Dec 23 '18 at 10:59