code to solve a linear equity - Need help

leon Galushko — Sat, 12 Jan 2008 21:49:02 -0500

Hi,
i have had previosly adressed this question titled with "Lingo..." Now there are more MatLab experts which have good experience in MaTLab, so i rephrase the problem once more. The task is simply to solve the equity where
could be n amount of variables, like:
a1 * x1 + a2 * x2 + a3 * x3 = Y;
a1, a2 and a3 are given, the Y too; now is to find all
possible values which x1, x2 and x3 could take on to solve the equity; one constraint is, that x1,2, 3 have to be only integer, that is whole numbers. I will let the programm run till it had worked out all possible solving ways that could be for the given equation. I need all solving possibilities be outputed.

I tried in MatLab this code:
target_result = .....
% Iterations boundaries:
x1_start = 1;
x1_stop = 10000;
x2_start = 1;
x2_stop = 10000;
result = []; % initialize empy Array
for i = x1_start:x1_stop
> for j = x2_start:x2_stop
> result = a * i + b * j;
> if result == target_result
> number_1 = i
> number_1 = j
Resutls store in a matrix
> result = [result; number_1 number_1];

This do indeed, BUT the really problem is one cannot more than 2 or 3 variables, in case equation is longer, like that:
x1 * a1 + x2 * a2 + ..........x15 * a15 = Y;

There are then more than 15 loops, which MatLab not up to run in a time.
Is there another way to make a better code for this model or this task?
Thanks
Leon

Re: code to solve a linear equity - Need help

Roger Stafford — Sun, 13 Jan 2008 01:00:19 -0500

leon Galushko <leonid.galushko@rwth-aachen.de> wrote in message
<16745921.1200174572444.JavaMail.jakarta@nitrogen.mathforum.org>...
> Hi,
> i have had previosly adressed this question titled with "Lingo..." Now there
are more MatLab experts which have good experience in MaTLab, so i
rephrase the problem once more. The task is simply to solve the equity where
> could be n amount of variables, like:
> a1 * x1 + a2 * x2 + a3 * x3 = Y;
> a1, a2 and a3 are given, the Y too; now is to find all
> possible values which x1, x2 and x3 could take on to solve the equity; one
constraint is, that x1,2, 3 have to be only integer, that is whole numbers. I
will let the programm run till it had worked out all possible solving ways that
could be for the given equation. I need all solving possibilities be outputed.
>
> I tried in MatLab this code:
> target_result = .....
> % Iterations boundaries:
> x1_start = 1;
> x1_stop = 10000;
> x2_start = 1;
> x2_stop = 10000;
> result = []; % initialize empy Array
> for i = x1_start:x1_stop
> > for j = x2_start:x2_stop
> > result = a * i + b * j;
> > if result == target_result
> > number_1 = i
> > number_1 = j
> Resutls store in a matrix
> > result = [result; number_1 number_1];
>
> This do indeed, BUT the really problem is one cannot more than 2 or 3
variables, in case equation is longer, like that:
> x1 * a1 + x2 * a2 + ..........x15 * a15 = Y;
>
> There are then more than 15 loops, which MatLab not up to run in a time.
> Is there another way to make a better code for this model or this task?
> Thanks
> Leon
--------
  Quite aside from excessive execution time, I foresee accuracy difficulties for
you in your procedure. You are requiring exact equality when you say:

if result == target_result,

but unless Y and the coefficients a1, a2, etc. are all fractions with
denominators only powers of two, there will occur inevitable roundoff errors
as the 'result' is computed and you may not achieve exact equality, even
though you may have a valid solution. In this case you need to determine the
largest roundoff errors that could possibly develop and tolerate enough
divergence from exact equality to allow such near solutions to be listed. That
is, you should say

if abs(result-target_result) < tolerance

for some appropriately small value of 'tolerance'.

  As to the time of execution, you should be aware that with 15 variables,
each ranging from 1 to 10000, you have a total of 10^60 combinations to
check, which is far too many for your computer to ever finish computing.
Optimistically assume one nanosecond for each summation. Then 10^60 of
them would require some 3e+43 years to complete! The universe will have
long since suffered the heat death predicted for it by astronomers and
physicists.

  If the a-coefficients and Y are restricted to fractions with only comparatively
small denominators, there are some shortcuts I can conceive of, but I fear the
execution time for 15 terms would still be far out of reach for practical
computation, even if you had all the earth's computers devoted in parallel to
the project. And even if you succeeded in this, what would you do with the
prodigious quantities of result listings?

Roger Stafford

MATLAB Central Newsreader - code to solve a linear equity - Need help

code to solve a linear equity - Need help

Re: code to solve a linear equity - Need help