Saturday, February 18, 2017

How To Find Integer Solutions (If Any) Of A Nonlinear System Of Equations, Improved Edition

 
Jsun Yui Wong

The computer program listed below seeks to find integer solutions (if any) of the first problem on page 177 of Conley [4], which is to solve 

         X(1)^2 + 3 * X(2) + 5 * X(4) + 6 * X(3) + 7 * X(6)) =5492,

         2 * X(1) * X(2) * X(3) + X(4) +  X(5)  + X(6)= 1114 X(5) = 638213,

         X(1) + X(2) + X(3) + 9 * X(4) + 11 * X(5) + X(6)=2787,

         3 * X(1) + 4 * X(2) + X(3) + X(4) + 6 * X(5) + 7 * X(6)=1768,

        13 * X(1) + X(2) * X(3) * X(4) + X(5) * X(6)=844252,

where 0<=X(i)>=200 and X(i)'s are whole numbers.


0 DEFDBL A-Z

3 DEFINT J, K, X


4 DIM X(342), A(342), L(333), K(333)


12 FOR JJJJ = -32000 TO 32000


    14 RANDOMIZE JJJJ

    16 M = -1D+317

    77 IF JJJJ > -32000 THEN GOTO 88 ELSE GOTO 91


    88 IF RND < .05 THEN GOTO 91 ELSE GOTO 128


    91 FOR KK = 1 TO 6

        94 A(KK) = 100


    95 NEXT KK


    128 FOR I = 1 TO 1250000


        129 FOR K = 1 TO 6


            131 X(K) = A(K)
        132 NEXT K
        155 FOR IPP = 1 TO FIX(1 + RND * 3)

            181 B = 1 + FIX(RND * 6)


            182 REM IF RND < -.1 THEN 183 ELSE GOTO 189

            183 R = (1 - RND * 2) * A(B)
            186 X(B) = A(B) + (RND ^ 3) * R

            188 GOTO 191
            189 IF RND < .5 THEN X(B) = A(B) - FIX(1 + RND * 1.99) ELSE X(B) = A(B) + FIX(1 + RND * 1.99)



        191 NEXT IPP


        1005 N88 = 5492 - 3 * X(2) - 5 * X(4) - 6 * X(3) - 7 * X(6) - X(1) ^ 2

        1006 N89 = 638213 - 2 * X(1) * X(2) * X(3) - X(4) - X(6) - X(5)


        1009 N91 = -1768 + 3 * X(1) + 4 * X(2) + X(3) + X(4) + 6 * X(5) + 7 * X(6)


        1113 REM


        1117 N93 = -2787 + X(1) + X(2) + X(3) + 9 * X(4) + 11 * X(5) + X(6)

        1119 N94 = -844252 + 13 * X(1) + X(2) * X(3) * X(4) + X(5) * X(6)



        1335 P = -ABS(N91) - ABS(N93) - ABS(N94) - ABS(N88) - ABS(N89)


        1499 IF P <= M THEN 1670
        1657 FOR KEW = 1 TO 6


            1658 A(KEW) = X(KEW)
        1659 NEXT KEW
        1661 M = P
        1664 NN88 = N88: NN89 = N89: NN91 = N91: NN93 = N93: NN94 = N94


    1670 NEXT I
    1888 IF M < 0 THEN 1999


    1917 PRINT A(1), A(2), A(3), A(4), A(5), A(6), M, JJJJ, NN88, NN89, NN91, NN93, NN94

1999 NEXT JJJJ


This computer program was run with qb64v1000-win [10]. Copied by hand from the screen, the computer program’s complete output through JJJJ=-27462 is shown below:

58      47      117      152     102
750      0      -31268      0      0
0      0      0    

58      47      117      152     102
750      0      -31267      0      0
0      0      0    

58      47      117      152     102
750      0      -31266      0      0
0      0      0    

58      47      117      152     102
750      0      -30638      0      0
0      0      0    

58      47      117      152     102
750      0      -30441      0      0
0      0      0    

58      47      117      152     102
750      0      -30440      0      0
0      0      0    

58      47      117      152     102
750      0      -27462      0      0
0      0      0    

Above there is no rounding by hand; it is just straight copying by hand from the screen.

On a personal computer with a Pentium Dual-Core CPU E5200 @2.50GHz, 2.50 GHz, 960 MB of RAM and with qb64v1000-win [10], the wall-clock time through
JJJJ=-27462 was one hour and forty minutes.

Acknowledgment

I would like to acknowledge the encouragement of Roberta Clark and Tom Clark.

References
[1] R. Burden, J. Faires, A. Burden, Numerical Analysis, Tenth Edition. Cengage Learning, 2016.
[2] R. Burden, J. Faires, Numerical Analysis, Sixth Edition. Brooks/Cole Publishing Company, 1996.
[3] R. Burden, J. Faires, Numerical Analysis, Third Edition. PWS Publishers, 1985.
[4] W. Conley, Computer Optimization Techniques, Revised Edition.  Petrocelli Books, Inc., NY/Princeton, 1984.
[5] D. Greenspan, V. Casulli, Numerical Analysis for Applied Mathematics, Science, and Engineering. Addison-Wesley Publishing Company, 1988
[6] L. W. Johnson, R. D. Riess, Numerical Analysis, Second Edition. Addison-Wesley Publishing Company, 1982
[7] Microsoft Corp. BASIC, second edition (May 1982), Version 1.10. Boca Raton, Florida: IBM Corp., Personal Computer, P. O. Box 1328-C, Boca Raton, Florida 33432, 1981.
[8] William H. Mills, A System of Quadratic Diophantine Equations, Pacific Journal of Mathematics, 3 (1953), pp. 209-220.
[9] Terry E. Shoup, Applied Numerical Methods for the Microcomputer, Prentice-Hall, 1984.
[10] Wikipedia, QB64, https://en.wikipedia.org/wiki/QB64.

No comments:

Post a Comment