DIOPHANTINE LINEAR EQUATION

PROBLEM
The solution of diophantine linear equation asks whether there exists a subset of {A.1,...,A.N} of positive integers that adds up exactly to the target a positive integer T

ALGORITHM
My Diophant algorithm solves almost always diophantine equation for N<=500 and A.I<=2*10**9

IMPLEMENTATION
Unit: internal subroutine

Global variables: array A.1,...,A.N of positive integers

Parameters: a positive integer N, a positive integer T

Result: displays in the screen the solution of the problem - i. e. a subset A. whose sum is equal T. The execution is halted (via the exit statement) as soon as a solution is found

Interface: internal procedure QUICKSORT

 DIOPHANT: procedure expose A. parse arg N, T call QUICKSORT N Ls.1 = A.1 do I = 2 to N   Im1 = I - 1; Ls.I = A.I + Ls.Im1 end if A.1 <= T & T <= Ls.N then do   S = 1; Stack.1 = N T   do while S > 0     parse var Stack.S R T V; S = S - 1     do K = 1 while Ls.K < T; end     if Ls.K = T then call EXIST V, K, 1     do while A.R > T; R = R - 1; end     if A.R = T then call EXIST V, R, R     do L = K to R while A.1 <= T - A.L       D = V A.L; S = S + 1       Stack.S = (L - 1) (T - A.L) D     end   end end say "Solution not exist" exit   EXIST: procedure expose A. parse arg V, B, E do J = B to E by -1; V = V A.J; end say "Solution:" V exit

COMPARISON
For N=100;T=25557 and the array A. created by statements:

 Seed = RANDOM(1, 1, 481989) do J = 1 to N   A.J = RANDOM(1, 1000) end

I compared the algorithms for solution of the Subset-sum problem and my algorithm DIOPHANT for solution of the diophantine equations.

Notes:
I halted the EXACT_SUBSET_SUM after 30 minutes of computations. For APPROX_SUBSET_SUM I used the value Epsilon = 0.5

Subset-sum problem - Comparison of Algorithms
Algorithm Subset sum Time
GS 25554      0.05
DPS 25557   240.24
APPROX_SUBSET_SUM 25436    12.31
DIOPHANT 25557      0.82

CONNECTIONS
Subset-sum problem
Exponential-time exact algorithm
Exact algorithm - dynamic programming
Greedy algorithm
Polynomial-time approximation algorithm

Literature
Zabrodsky V., Problem dvou loupezniku
BAJT (former Czech computer journal), October 1993 (36), pp. 134-136

 cover contents index main page