CODEWITHSUNDEEP
c#polynomial-mathfactorization
user2290809
user2290809

Reputation: 21

How to solve polynomial with 4 or 7 variables in Fastest possible way

Given equation :

K = Ap + Bq + Cr + Ds.

Solution I tried :

Terms we already know : A, B, C, D, K

Finding term s given p, q, r;

p=0, q=0, r=1;
compute() => s = (K - Ap - Bq - Cr)/D;

continue until s becomes < 0; for all terms p=0, q=0, r=1...n;

like wise continue until s becomes < 0; for all terms where p=0, q=1..n, r=1...n;

and,

finally, continue until s becomes < 0; for all terms where p=1..n, q=1..n, and r=1..n;

coded 3 loops for updating p, q and r.

It takes more time to compute if K becomes larger for example 1000..., 8145, 45000 etc..;

Please do not suggest external library... I am looking for a coding solution.

Example Snippet

for (int i = 0; i < preSpecifiedIterations; i++)
{
 p = i;

 if (A * p > K)  //Exit condition ; if Ap > K
  break;

  for (int j = 0; j < preSpecifiedIterations; j++)
  {
   q = j;

   if (B * q > K) //Exit condition ; if Bq > K
    break;

   for (int k = 1; k < preSpecifiedIterations; k++)
   {
    r = k;
    // compute s given p, q, and r;
    s = (K - (A * p) - (B * q) - (C * r)) / D;

    if (s < 0) //Exit condition ; don't process if s < 0 i.e negative values
     break;
    else
     ...
   }
  }
}

Also, if one has noted : preSpecifiedIterations -> Is it possible to determine how many iterations would be required ahead of computation?

And is there any better Algorithm to solve above problem?

Thanks a lot of reading.

Upvotes: 0

Views: 1476

Answers (1)

Eric Lippert
Eric Lippert

Reputation: 660377

This is not a very good question for StackOverflow; it's better for one of the math sites. But I'll answer it here anyways.

You certainly can do better than brute force, as you are doing here. You should be able to compute the answer in a few microseconds.

There exists a solution if and only if the greatest common divisor of (A, B, C, D) divides K evenly. That's the extended form of Bézout's identity.

In order to determine (1) what the gcd is and (2) what the values for p, q, r, s are, you use the Extended Euclidean Algorithm, which you can read about here:

http://en.wikipedia.org/wiki/Extended_Euclidean_algorithm

My advice is to first write a program that solves simple linear Diophantine equations of the form ax + by = c. Once you've done that, then read the section of that Wikipedia article called "The case of more than two numbers", which describes how to extend the algorithm to handle your case.

Upvotes: 4

Related Questions