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

last modified 8th August 2001
Copyright 2000-2001 Vladimir Zabrodsky
Czech Republic.

mail