CODEWITHSUNDEEP
c#algorithmmathequation
Jonathan Applebaum
Jonathan Applebaum

Reputation: 5986

Improving equation algorithm ax+by=c with the smallest difference between |x-y|

I am struggling for quite a while to improve my algorithm but with no progress.

I need a reusable function to calculate x*3+y*5=n.

Constrains:

that is a console app draft i have written, it compiles and work but, as you can see, very not efficient when dealing with large numbers.

i think i have a lack of knowledge in math in order to improve that code:

static void Main(string[] args)
{
    GetWarAfterMath(5000000);
    Console.ReadLine();
}

const int FIRST = 3;
const int SECOND = 5;

static void GetWarAfterMath(int n)
{
    int x = 0;
    int y = 0;
    int delta = 0;

    int i = 0;
    int j = 0;

    for (i = 0; i < n; i++)
    {
        for (j = 0; j < n; j++)
        {
            if ((i * FIRST) + (j * SECOND) == n)
            {
                // Console.WriteLine(i + "*" + FIRST + "+" + j + "*" + SECOND + "=" + n);
                if (Math.Abs(i - j) < delta)
                {
                    x = i;
                    y = j;
                    delta = Math.Abs(x - y);
                }
                break;
            }

            else if ((j * FIRST) + (i * SECOND) == n)
            {
                // Console.WriteLine(j + "*" + FIRST + "+" + i + "*" + SECOND + "=" + n);
                if (j - i < delta)
                {
                    x = j;
                    y = i;
                    delta = Math.Abs(x - y);
                }
                break;
            }
        }
    }

    Console.WriteLine("THE WINNERS ARE:" + x + "*" + FIRST + "+" + y + "*" + SECOND + "=" + n);
}

EDIT:

finally after combining @Yves Daoust, @user3386109 and @Hasson answers.
time complexity decreased dramatically,
Execution time with the number 8000000: 127 miliseconds!
this is the final algorithm:

static void Main(string[] args)
{
    GetMatch(34);
    Console.ReadLine();
}

const double FIRST = 3;
const double SECOND = 5;

static void GetMatch(double n)
{
    int x = 0;
    int y = 0;
    int finalX = 0;
    int finalY = int.MaxValue;
    for (int i = 0; i < n / FIRST; i++)
    {
        if (((n - FIRST * i) / SECOND) % 1 == 0)
        {
            y = Convert.ToInt32(((n - FIRST * i) / SECOND));
            x = i;
            if(Math.Abs(x-y) < Math.Abs(finalX-finalY))
            {
                finalX = x;
                finalY = y;
            }
        }
    }

    Console.WriteLine("THE WINNERS ARE:" + finalX + "*" + FIRST + "+" + finalY + "*" + SECOND + "=" + n + "    Calc: " +  (finalX * FIRST + finalY * SECOND));
}

Note that as @Yves Daoust wrote in his first answer its also possible to solve this with inear diophantine equation using the Euclidian Algorithm but you need to reverse the Euclidian Algorithm, I preferred to keep it simple. here is a nice video about that topic with a solution, if somebody intrested: Number Theory: Diophantine Equation: ax+by=gcd(a,b)
thank you very much for the help.

Upvotes: 3

Views: 854

Answers (5)

user1196549
user1196549

Reputation:

Though my other solution has been accepted, there is an even simpler approach.

If rationals are allowed, you always achieve the minimum 0 with x = y = n / 8. With the restriction on integers, x = y = floor(n / 8) yields |x - y| = n mod 8, which is one of 0..7. You can adjust by adding/subtracting 5 from x while subtracting/adding 3 to y, and you only have to solve the problem for n in 0..7.

Upvotes: 0

user3386109
user3386109

Reputation: 34839

The goal is to minimize |x-y|. So start with y=x and solve the equation

3x + 5x = n
   8x = n

If n is a multiple of 8, then you've found an integer solution.

Otherwise, try y=x+1

3x + 5(x+1) = n
  8x + 5 = n

If n-5 is a multiple of 8, then you've found an integer solution.

Otherwise, try it the other way around

3(y+1) + 5y = n
  8y + 3 = n

If n-3 is a multiple of 8, then you've found integer solution.

Rinse and repeat to get the following results

|x-y|==0 works if n is a multiple of 8
|x-y|==1 works if (n-3) or (n-5) is a multiple of 8
|x-y|==2 works if (n-2) or (n-6) is a multiple of 8
|x-y|==3 works if (n-1) or (n-7) is a multiple of 8
|x-y|==4 works if (n-4) is a multiple of 8

At least one of those conditions must be true, so |x-y| will always be less than or equal to 4.

Upvotes: 5

user1196549
user1196549

Reputation:

The problem ax+by = c is very well-known in number theory (it is a linear diophantine equation).

It can only have a solution if gcd(3,5)|n, which is of course always true.

Then, if you know some solution to 3x°+5y°=n, all solutions are of the form x=x°-5k, y=y°+3k.

It is very easy to find a solution, as one of n, n-5, n-10 is certainly a multiple of 3.

All that remains is to minimize |x°-5k-y°-3k| under the constraints x°-5k>0, y°+3k>0. The minimum will be achieved by the value of 8k the closest to x°-y°, or the value that saturates one of the constraints.

For instance, for n=173000, x°=57665 and y°=1 is a solution. Then k=(57665-1)/8=7208 yields |x-y|=0. This solution is acceptable because the constraints are fulfilled.

I am not providing full details of the case study, but the main lesson is: no loop required !

Upvotes: 7

Hasson
Hasson

Reputation: 1914

You don't have to loop for both x and y, this is a simple equation where you know n, so if you consider x = 1..n , then you can calculate y = (n-3*x)/5 and test if it is integer or not (even better you can test if n-3*x ends with 5 or 0 or not, if it is then this is a valid combination otherwise it is not. So over all it is one loop, and I think we can add more optimization.

And by the way delta has to be initialized with very large number, or n for example.

Upvotes: 3

Olaf
Olaf

Reputation: 101

If you need an efficient algorithm, then start with the solution in real values (e.g. double or float) for x == y. Then round x to the next integer and take that as starting point. Test for the next few pairs (x,y) of integers only. Break when your delta becomes worse.

Upvotes: 0

Related Questions