Verifies if three integer numbers can be the legs of a right-angle triangle, while trying to avoid overflowing on large input values.

pythagorean-triples.c

/**
 * A short program that verifies if three integer numbers can be the legs of a right-angle triangle.
 * The program's purpose is to avoid overflowing when the legs are large numbers.
 *
 * It accompanies an answer to this StackOverflow question: http://stackoverflow.com/q/36623053/4265352
 * @link http://stackoverflow.com/a/36626811/4265352
 */
#include <stdio.h>
#include <stdlib.h>

#define min(a,b) ((a) < (b) ? (a) : (b))
#define max(a,b) ((a) > (b) ? (a) : (b))


int isRightTriangle(unsigned int, unsigned int, unsigned int);
unsigned int GCD(unsigned int, unsigned int);


int main(int argc, char *argv[])
{
  if (argc < 4) {
    printf("Usage: %s leg1 leg2 leg3\n", argv[0]);
    return 1;
  }

  unsigned int 
    leg1 = atoi(argv[1]),
    leg2 = atoi(argv[2]),
    leg3 = atoi(argv[3]);

  printf("Legs: %d, %d, %d. Is right triangle: %s\n", leg1, leg2, leg3, isRightTriangle(leg1, leg2, leg3) ? "yes" : "no");
  return 0;
}


int isRightTriangle(unsigned int leg1, unsigned int leg2, unsigned int leg3)
{
  // Step 1. let the legs be a > b > c
  unsigned int a = max(max(leg1, leg2), leg3);
  unsigned int b = min(max(leg1, leg2), leg3);
  unsigned int c = min(min(leg1, leg2), leg3);

  // While all the values are even numbers, divide them by 2
  // See Remark #2 on the StackOverflow answer: http://stackoverflow.com/a/36626811/4265352
  while (a % 2 == 0 && b % 2 == 0 && c % 2 == 0) {
      a /= 2;
      b /= 2;
      c /= 2;
  }

  // If 'a' is still even then the numbers cannot be the legs of a right-angle triangle
  if (a % 2 == 0) {
    return 0;
  }


  // Let 'c' be the odd value (see Remark #2)
  if (b % 2 == 1) {
    unsigned int tmp = b;
    b = c;
    c = tmp;
  }

/**
  // Step 2. compute sum and diff
  // a*a = b*b + c*c
  // b*b = (a+b)*(a-c)
  unsigned int sum  = a + c;
  unsigned int diff = a - c;
*/
  // Step 2. modified to avoid overflow
  // b is even, a and c are odd; a + c and a - c are also even
  // divide b, a + c and a - c by 2 without actually computing a + c
  unsigned int sum = a / 2 + c / 2 + 1;
  unsigned int diff = (a - c) / 2;          // This doesn't overflow or underflow (c < a)
  b = b / 2;


  // Step 3. GCD(sum, diff) must divide b
  unsigned int gcd = GCD(sum, diff);
  if (b % gcd != 0) {
    return 0;
  }

  // Step 4. divide sum and diff by their GCD
  sum  /= gcd;
  diff /= gcd;
  // Step 5. divided b by GCD(sum, diff), assign b1 and b2
  unsigned int b1 = b / gcd;
  unsigned int b2 = b / gcd;

  // Step 6.
  // b1 and sum
  gcd = GCD(b1, sum);
  b1  /= gcd;
  sum /= gcd;
  // b1 and diff
  gcd = GCD(b1, diff);
  b1   /= gcd;
  diff /= gcd;

  // Step 7.
  // b2 and sum
  gcd = GCD(b2, sum);
  b2  /= gcd;
  sum /= gcd;
  // b2 and diff
  gcd = GCD(b2, diff);
  b2   /= gcd;
  diff /= gcd;

  // Step 8.
  // No further reduction can be done
  // Here, if b1 * b2 == sum * diff then it is a right triangle

  // However, because b1 doesn't have any common factors with sum and diff, the only 
  // situation when b1 * b2 == sum * diff (in integer numbers) is when b1 == b2 == sum == diff == 1

  return (b1 == 1) && (b2 == 1) && (sum == 1) && (diff == 1);
}


unsigned int GCD(unsigned int a, unsigned int b)
{
   unsigned int gcd = a;
   unsigned int rem = b;
   unsigned int tmp = 0;

   while (rem > 0) {
      tmp = rem;
      rem = gcd % rem;
      gcd = tmp;
  }

  return gcd;
}


// This is the end of file