DOES IT MAKE SENSE TO SOLVE DIOPHANTINE LINEAR EQUATION?  
We consider the problem solution of diophantine linear equation  Diophantine problem: Given an array of positive integers A[1], ..., A[N] and an positive integer C find a subset of A[1], ..., A[N] that sums to C. This problem is NPcomplete. An special case for even C, where C = (A[1] + A[2] + ... + A[N]) div 2, is the partition problem. I present very simple exponentialtime algorithm for finding their solutions.
... it can't be solved by WORLD'S FASTEST COMPUTERFollowing citations have been selected from various sources): The only known solution is brute force: test all possible subsets until the sum is found or you run out of subsets. For example for N = 300 the number of subsets is 2^{300}, which is greater than the estimated total number of electrons, protons, and neutrons, in the entire universe. Even a computer counting at a speed of over a million or billion each second, would not reach the result until long after our sun had burned out. When you have partition items from an office, i.e. for N (approximately) equals 100, into 2 disjoint subsets so that the sum of their values in each of the two subsets is equal it doesn't make sense to solve by WORLD'S FASTEST COMPUTER.
Algorithm DIOPHANTI introduce a very simple algorithm for finding of a solution of this problem. The DIOPHANT Algorithm Sort the elements of an aray into ascending order. Compute Ls[1] = A[1], Ls[2] = Ls[1] + A[2], ..., Ls[J] = Ls[J  1] + A[J], ... for J = 3, ..., N.
If A[1] <= C & C <= Ls[N] then
N = L  1 and C = C  A[L]
In this article I present a nonrecursive version of this algorithm in the Rexx language:
An solution is stored into the V variable as an string of numbers separated by blanks. Into the stack are stored by the push operation S = S + 1; Stack.S = (L  1) (C  A.L) D following data for the solution of a subproblem: size of an array, a current value of C, a current part of the solution. When a solution exists the EXIST procedure is called. My simple example of this procedure writes a solution on a screen and ends the computation:
When we replace the exit instruction with S = S  1; return instructions then the DIOPHANT will find all solutions.
Worst Case  Complexity O(2^{N})DIOPHANT is an exponentialtime algorithm. The column entitled P(N) includes number of push operations for given N.
We can spare about half of the number of push operations when we will find only one subset S, A[N] is contained in S. I.e. the Diofantine problem of size N  1: Given an array of positive integers A[1], ..., A[N  1] and an positive integer C  A[N] find a subset of A[1], ..., A[N  1] that sums to C  A[N], where C = (A[1] + ... + A[N]) div 2. In this article I will solve the partition problem, as the "usual" Diophantine problem, also if (A[1] + ... + A[N]) div 2 is an odd number.
Average? Case  Examples of Polynomial ComplexityWhat is average case for the Diophantine problem? That is the Question! Test #1For given N = 10, 20, 30, 40, 50, 100, 200, 300, 400, 500 I generated an array A by the following fragment of program. Note that in the Rexx language the call of the RANDOM(Min, Max) builtin function returns a pseudorandom number from the interval <Min, Max>, where Max <= 100000.
For the partition problem I computed the C number by integer divide (operator % in Rexx)
For the general Diophantine problem I computed C by expression
where the FORMAT builtin function returns integer  rounded values Sum * RANDI(). The RANDI function returns random numbers between 0 and 1. I used "the minimal standard generator" from Park S.K., Miler K.W.: Random Number Generators: Good ones are hard to find. CACM 1988, Vol. 31, No. 10, p. 11921201. Seed is a global variable used to hold the current value in the integer sequence. This generator must be initialized by assigning Seed a value between 1 and 2147483646. Random numbers uniformly distributed between 0 and 1 then can be generated as required via repeated calls to RANDI. Note: // is operator of operation Remainder  divide and return only the remainder.
I repeated 100 times (for given N) the generation of A, C and execution of the DIOPHANT algorithm for finding an solution of the Diophantine problem and then 100 times for finding an solution of the partition problem. The following table sumarizes the results.
The following example shows one solution of the partition problem:
Test #2In the second test I generated the elements of A array by the following fragment (the first instruction of the main program was: numeric digits 16):
I solved the partition problem for maximum value of item more than 21 millions. I initialized Seed by assigning the value 214748364 and then I executed the DIOPHANT algorithm 20 times for N = 100, 200, 300, 400, 500. Then I initialized Seed by assigning the value 19685089 and I continued for N = 30, 40, 50, 20, 10:

last modified 19th July 2001
Copyright © 19982001 Vladimir Zabrodsky
Czech Republic