Solving linear Diophantine equation systems {Project
In this project, you are going to implement an algorithm that I presented
in class to solve a linear Diophantine equation system in three variables
and with 2 equations. Being Diophantine, the variables are of nonnegative
integers. You may use C, C++, or Java to do the implementation.
I do not ask you to design the algorithm, instead, I present the algorithm’s
design, and you need only implement the algorithm.
You need turn-in working code and prepare for a demo. You have two
weeks to do the project.
Preparation 1.
Herein, an equation is in the form. of
C1x1 + C2x2 + C3x3 + C = 0 (1)
where constants C1;C2;C3 are integers (positive,negative, zero), and constant
C is nonnegative. Hence, for instance, 3x1 + 0x2 4x3 17 = 0 is not an
equation in the above form. However, equivalently, 3x1 0x2+4x3+17 = 0
is in the above form.
For the equation in (1), we de ne
Cmax = max
d;d1;d2;d32f0;1g
jC1d1 + C2d2 + C3d3 + dj: (2)
(Excercise: For the aforementioned equation 3x1 0x2 +4x3 +17 = 0, what
is the value of Cmax?)
Implement a function that returns Cmax from the description of an equation
in (1), and use the above Excercise to test your function.
Preparation 2.
For a constant C 0, we use binary representation for C. For instance,
if C = 34, then in binary, C = 100010. In this case, we use
b6b5b4b3b2b1
for it, with b6 = 1;b5 = b4 = b3 = 0;b2 = 1;b1 = 0. Herein, we de ne KC = 6
(the number of bits needed to represent C). In particular when C = 0, we
let KC = 0.
1
Hence, for 1 i KC, the bi is de ned as above. However, for i = KC+1,
the bi is now de ned as 0. (Excercise: Let C = 18. What is the value of KC?
what is the value of b6? what is the value of b4?)
Implement a function that returns the value KC from a given constant
C 0.
Implement a function that returns the value bi from a given constant C 0
and i, noticing that the i shall be in the range of 1 i KC + 1.
Algorithm 1. Equation to automaton
We now construct a nite automaton M from the description of the equa-
tion in (1).
The input alphabet of M contains exactly eight input symbols, where
each symbol is in the form. of (a1;a2;a3) with a1;a2;a3 2f0;1g. (Hence, an
input symbol is a triple of three Boolean values.)
A state in M is a pair of values: [carry;i], where
Cmax carry Cmax;
recalling that Cmax is de ned in (2), and 1 i KC + 1.
The initial state in M is [carry = 0;i = 1]. The accepting state is
[carry = 0;i = KC + 1].
For all states [carry;i] and [carry0;i0] and all input symbols (a1;a2;a3),
the following is true:
[carry;i](a1;a2;a3) ! [carry0;i0] is a transition in M (i.e., M moves from state
[carry;i] to state [carry0;i0] on reading input symbol (a1;a2;a3)) i the fol-
lowing is true:
Let R = C1a1 +C2a2 +C3a3 +bi +carry. Then, R is divisible by
2, and carry0 = R2 . Furthermore, if 1 i KC, then i0 = i + 1,
else i0 = i. (You shall use the functions implemented above to
implement this step; e.g., to compute the bi.)
Implement a function that returns the nite automaton M from the de-
scription of an equation in (1). Notice that you shall use a graph as the
data structure of the automaton M. (The automata we constructed are all
deterministic by de nition.)
Algorithm 2. Cartesian product of automata
Now we are given a system of 2 equations over three variables x1;x2;x3,
where we use E1(x1;x2;x3) and E2(x1;x2;x3) to indicate the two equations
and recall that the equations are in the form. of (1). Suppose that, using the
Algorithm 1 presented earlier, we obtain nite automata M1 and M2 from the
two equations respectively. Then, we need construct a nite automaton M
to accept the intersection of the language accepted by M1 and the language
by M2. This is a standard algorithm in cpts317. In case that you dont know
it, you can watch https://www.youtube.com/watch?v=QSpErcGyXPM
Implement a function that returns theMfrom the M1 and the M2 (which
are computed using the function implemented in Algorithm 1 from descrip-
tions of the two equations). Again, the resulting automatonMuses a graph
as its data structure.
Final step.
If the language accepted by M is empty, then the equation system does
not have solutions;
If the language accepted byMis not empty, then we can nd a solution by
using DFS on the graph of theM(from initial to accepting while collecting
the sequence of input symbols on the path). Notice that you shall reverse the
sequence and then convert it into digit before you output the solution. I will
sketch a little more detail of this step. Suppose that the following sequence
of input symbols is collected on a path from the initial to the accepting:
(1;0;1);(0;1;1);(1;0;0);(1;1;0)
then, what is the solution to the equation system? it is 1011, 0101,
1100 (how did I do it? I got 1011 by picking the rst bit from each input
symbol in the sequence!). After reversing them, I have 1101, 1010, 0011.
Then I convert them into digits: 13, 10, 3. Hence, the solution is actually
x1 = 13;x2 = 10;x3 = 3.
Emptiness testing for the language accepted byMcan be done by running
DFS on the graph of theM(from initial to accepting) { this is also a standard
algorithm in cpts317. DFS is covered in one of cpts121, 122, 223.
Please also implement this nal step and use the following two to test
your code:
1. The following equation system does not have nonnegative integer solutions:
3x1 2x2 + x3 + 5 = 0
6x1 4x2 + 2x3 + 9 = 0
3
2. The following equation system does have solutions:
3x1 2x2 x3 + 3 = 0
6x1 4x2 + x3 + 3 = 0
=============================
Summary: we can generalize the algorithms to any linear Diophantine
equation (and inequalities) system with any number of equations and any
number of variables. However, this small project is intended for training
purposes and hence we only deal with two equations and three variables |-
but the algorithm is general.
The entire project should be implemented within 600 lines of code (may
be even less). To be successful in this project, you shall be really uent in
playing with pointers, graphs and algorithms on graphs (cpts350).