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, ..., A[N] and an positive integer C find a subset of A, ..., A[N] that sums to C. This problem is NP-complete. An special case for even C, where C = (A + A + ... + A[N]) div 2, is the partition problem. I present very simple exponential-time algorithm for finding their solutions.
... it can't be solved by WORLD'S FASTEST COMPUTER
Following 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 2300, 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.
I 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 = A, Ls = Ls + A, ..., Ls[J] = Ls[J - 1] + A[J], ... for J = 3, ..., N.
If A <= C & C <= Ls[N] then
N = L - 1 and C = C - A[L]
In this article I present a non-recursive 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) Dfollowing 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(2N)
DIOPHANT is an exponential-time 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, ..., A[N - 1] and an positive integer C - A[N] find a subset of A, ..., A[N - 1] that sums to C - A[N], where C = (A + ... + A[N]) div 2.
In this article I will solve the partition problem, as the "usual" Diophantine problem, also if (A + ... + A[N]) div 2 is an odd number.
Average? Case - Examples of Polynomial Complexity
What is average case for the Diophantine problem? That is the Question!
For 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) built-in 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 built-in 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. 1192-1201. 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:
In 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 © 1998-2001 Vladimir Zabrodsky