CODEWITHSUNDEEP
coptimizationequationalgebra
David Simka
David Simka

Reputation: 566

Optimizing a program for solving ax+by=c with positve integers

I am writing a program that for any given positive integers a < b < c will output YES if there is a solution to ax+by=c where x and y are also positive integers (x,y > 0), or NO if there isn't a solution. Keep in mind that I need to work with big numbers.

The approach I take for solving this problem is that I subtract b from c and I check if this number is divisable by a.

Here's my code:

#include <stdio.h>
#include <stdlib.h>

int main(){
    unsigned long long int a, b, c;
    scanf("%I64u %I64u %I64u", &a, &b, &c);
    while(c>=a+b){ //if c becomes less than a+b, than there's no sollution
        c-=b;
        if(c%a==0){
            printf("YES");
            return 0;
        }
    }
    printf("NO");
    return 0;
}

is there a more optimised way to find wether ax+by=c has positive sollutions? I tried reading about linear Diophantine equations, but all I found is a way to find integer sollutions (but not positive).

Upvotes: 3

Views: 4175

Answers (2)

ryanpattison
ryanpattison

Reputation: 6251

My approach so far.

  1. Use Euclidean Algorithm to find GCD(a, b)
  2. There are solutions (in integers) to ax + by = c if and only if GCD(a, b) divides c. No integer solutions means no positive solutions.
  3. use Extended Euclidean Algorithm to solve the Diophantine equation and return NO if it gives non-positive solutions.

For comparisons it's hard to find examples that take longer than a second but in deciding on thousands of random equations the performance difference is noticeable. This Lecture has a solution for finding the number of positive solutions to a Linear Diophantine Equation. 

typedef unsigned long long int BigInt;
int pos_solvable(BigInt a, BigInt b, BigInt c) {
  /* returns 1 if there exists x, y > 0 s.t. ax + by = c
   * where 0 < a < b < c
   * returns 0, otherwise
   */
  BigInt gcd = a, bb = b, temp; 
  while (bb) { /* Euclidean Algorithm */
    temp = bb;
    bb = gcd % bb;
    gcd = temp;
  }
  if (c % gcd) { /* no integer (or positive) solution */
    return 0;
  } else { 
    /* Extended Euclidean Algorithm */
    BigInt s = 0, old_s = 1;
    BigInt t = 1, old_t = 0;
    BigInt r = b / gcd, old_r = a / gcd;

    while (r > 0) {
      BigInt quotient = old_r / r;
      BigInt ds = quotient * s;
      BigInt dt = quotient * t;
      if (ds > old_s || dt > old_t)
        return 0; /* will give non-positive solution */

      temp = s;
      s = old_s - ds;
      old_s = temp;

      temp = t;
      t = old_t - dt;
      old_t = temp; 

      temp = r;
      r = old_r - quotient * r;
      old_r = temp;
    }
    return 1; 
  }
}

Upvotes: 3

chux
chux

Reputation: 154305

The following is a comment but too big for the comment section.

This is posted to help others dig into this problem a little deeper.

OP: Incorporate any of in your post if you like.

What is still needed are some challenging a,b,c.

#include <limits.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

//#define LLF "%I64u"
#define LLF "%llu"

int main(void) {
  unsigned long long int a, b, c, x, y, sum, c0;
  // scanf(LLF LLF LLF, &a, &b, &c);
  c = c0 = ULLONG_MAX;
  b = 10000223;
  a = 10000169;
  y = 0;
  sum = a + b;
  time_t t0 = time(NULL);
  while (c >= sum) { //if c becomes less than a+b, than there's no solution
    c -= b;
    if (c % a == 0) {
      break;
    }
  }
  if (c % a == 0) {
    y = (c0 - c) / b;
    x = c / a;
    printf("YES " LLF "*" LLF " + " LLF "*" LLF " = " LLF "\n", a, x, b, y, c);
  } else {
    printf("NO\n");
  }
  time_t t1 = time(NULL);
  printf("time :" LLF "\n", (unsigned long long) (t1 - t0));
  return 0;
}

Output

YES 10000169*1844638544065 + 10000223*4688810 = 18446697184563946985
time :0

Upvotes: 1

Related Questions