144 lines
4.7 KiB
Plaintext
144 lines
4.7 KiB
Plaintext
|
$set ans85 noosvs mf
|
||
|
|
|
||
|
|
PROGRAM-ID. DIOPHANT.
|
||
|
|
******************************************************************
|
||
|
|
*
|
||
|
|
* (C) Micro Focus Ltd. 1989
|
||
|
|
*
|
||
|
|
* DIOPHANT.CBL
|
||
|
|
*
|
||
|
|
* DIOPHANTINE - solve linear equation Ax + By = C
|
||
|
|
* for integers x and y.
|
||
|
|
*
|
||
|
|
* Method:
|
||
|
|
* if A > B
|
||
|
|
* swap A and B
|
||
|
|
* fi
|
||
|
|
*
|
||
|
|
* when A = 0
|
||
|
|
* set x = 0, y = C/B as solution, and fail if non-integer
|
||
|
|
* when A = 1
|
||
|
|
* set x = C, y = 0 as solution
|
||
|
|
* otherwise
|
||
|
|
* let D = largest integer < (B/A)
|
||
|
|
* let E = largets integer < (C/A)
|
||
|
|
* let F = B - A*D
|
||
|
|
* let G = C - A*E
|
||
|
|
* then Ax + By = C becomes
|
||
|
|
* Ax + (F + A*D)y = (G + A*E)
|
||
|
|
* so x + (F/A + D)y = (G/A + E)
|
||
|
|
* and (F/A)y + v = G/A (since everything else is integral)
|
||
|
|
* so solve
|
||
|
|
* Fy + Av = G for integers y and v
|
||
|
|
*
|
||
|
|
* in COBOL terms:
|
||
|
|
*
|
||
|
|
* divide B by A giving D remainder F
|
||
|
|
* divide C by A giving E remainder G
|
||
|
|
* solve Av + Fw = G for integers v and w
|
||
|
|
* set x = E - Dw + v, y = w as solution
|
||
|
|
*
|
||
|
|
* if swapped
|
||
|
|
* swap x and y
|
||
|
|
* fi
|
||
|
|
*
|
||
|
|
*
|
||
|
|
******************************************************************
|
||
|
|
WORKING-STORAGE SECTION.
|
||
|
|
01 InitA PIC s9(9) comp-5.
|
||
|
|
01 InitB PIC s9(9) comp-5.
|
||
|
|
01 InitC PIC s9(9) comp-5.
|
||
|
|
01 SolvX PIC s9(9) comp-5.
|
||
|
|
01 SolvY PIC s9(9) comp-5.
|
||
|
|
01 FailFg PIC X.
|
||
|
|
88 OK VALUE 'Y'.
|
||
|
|
88 BAD VALUE 'N'.
|
||
|
|
88 TRY VALUE '?'.
|
||
|
|
LOCAL-STORAGE SECTION.
|
||
|
|
01 D PIC s9(9) comp-5.
|
||
|
|
01 E PIC s9(9) comp-5.
|
||
|
|
01 F PIC s9(9) comp-5.
|
||
|
|
01 G PIC s9(9) comp-5.
|
||
|
|
01 V PIC s9(9) comp-5.
|
||
|
|
01 TEMP PIC s9(9) comp-5.
|
||
|
|
LINKAGE SECTION.
|
||
|
|
01 A PIC s9(9) comp-5.
|
||
|
|
01 B PIC s9(9) comp-5.
|
||
|
|
01 C PIC s9(9) comp-5.
|
||
|
|
01 X PIC s9(9) comp-5.
|
||
|
|
01 Y PIC s9(9) comp-5.
|
||
|
|
PROCEDURE DIVISION.
|
||
|
|
MAIN SECTION.
|
||
|
|
DISPLAY "Solve Ax + By = C for integers x and y"
|
||
|
|
DISPLAY "Enter value for A: " with no advancing
|
||
|
|
ACCEPT InitA
|
||
|
|
DISPLAY "Enter value for B: " with no advancing
|
||
|
|
ACCEPT InitB
|
||
|
|
DISPLAY "Enter value for C: " with no advancing
|
||
|
|
ACCEPT InitC
|
||
|
|
SET TRY TO TRUE
|
||
|
|
CALL 'SOLVE' USING BY VALUE InitA InitB InitC
|
||
|
|
BY REFERENCE SolvX SolvY
|
||
|
|
|
||
|
|
IF OK
|
||
|
|
DISPLAY "Solution is: x = " SolvX ", y = " SolvY
|
||
|
|
ELSE
|
||
|
|
DISPLAY "No Solution exists."
|
||
|
|
END-IF
|
||
|
|
STOP RUN.
|
||
|
|
|
||
|
|
SOLVE-DIOPHANTINE SECTION.
|
||
|
|
ENTRY 'SOLVE' USING BY VALUE A B C BY REFERENCE X Y.
|
||
|
|
|
||
|
|
IF A > B
|
||
|
|
* Use TEMP as a flag to indicate swapped or not.
|
||
|
|
MOVE 1 TO TEMP
|
||
|
|
CALL 'SWAP2' USING A B
|
||
|
|
ELSE
|
||
|
|
MOVE 0 TO TEMP
|
||
|
|
END-IF
|
||
|
|
|
||
|
|
EVALUATE A
|
||
|
|
WHEN 0
|
||
|
|
DIVIDE C BY B GIVING D REMAINDER E
|
||
|
|
IF E = 0
|
||
|
|
MOVE 0 TO X
|
||
|
|
MOVE D TO Y
|
||
|
|
SET OK TO TRUE
|
||
|
|
ELSE
|
||
|
|
* No solution exists.
|
||
|
|
SET BAD TO TRUE
|
||
|
|
MOVE 0 TO X, Y
|
||
|
|
END-IF
|
||
|
|
|
||
|
|
WHEN 1
|
||
|
|
MOVE C TO X
|
||
|
|
MOVE 0 TO Y
|
||
|
|
SET OK TO TRUE
|
||
|
|
|
||
|
|
WHEN OTHER
|
||
|
|
* We must delve deeper to find a solution.
|
||
|
|
DIVIDE B BY A GIVING D REMAINDER F
|
||
|
|
DIVIDE C BY A GIVING E REMAINDER G
|
||
|
|
|
||
|
|
CALL 'SOLVE' USING BY VALUE A F G BY REFERENCE v Y
|
||
|
|
|
||
|
|
COMPUTE X = E - ( D * Y ) + v
|
||
|
|
|
||
|
|
END-EVALUATE
|
||
|
|
|
||
|
|
IF TEMP = 1
|
||
|
|
CALL 'SWAP2' USING X Y
|
||
|
|
END-IF
|
||
|
|
|
||
|
|
EXIT PROGRAM.
|
||
|
|
|
||
|
|
|
||
|
|
* Second level program to swap 2 variables using local temp variable.
|
||
|
|
SWAPPER SECTION.
|
||
|
|
ENTRY 'SWAP2' USING X Y.
|
||
|
|
MOVE X TO TEMP
|
||
|
|
MOVE Y TO X
|
||
|
|
MOVE TEMP TO Y
|
||
|
|
EXIT PROGRAM.
|