Check that triangle is right?

Question

I'm trying to check if a triangle is a right triangle in C language. a, b and c are lengths of sides of some triangle.

int is_right_triangle(int a, int b, int c)
{
    return (a * a + b * b == c * c || a * a + c * c == b * b || b * b + c * c == a * a);
}

How I can avoid an integer overflow in sum and multiplication? Assume that we don't have a long long type.

Answer 1

Improved(optimized) version

1. Find the largest side and smallest side. (Without loss of generality, let's call them C and A). And B is the third side
2. Now C² - A² = B² for right angled triangle. i.e. (C+A)*(C-A)=B², calculate unsigned_sum=C+A and unsigned_diff=C-A (unsigned int is guaranteed to not overflow for sum of int)
3. Divide sum, diff and B with the gcd of sum and diff. If it doesn't divide B, it is not a right angled triangle. If it does, sum and diff would be perfect square if triangle is right.
4. Find integer square root of sum and diff. If the product of roots is equal to B, triangle is right.

int is_right_triangle(int a, int b, int c)
{
  unsigned int sum, diff;
  int f = 2;  /* factor */
  unsigned int hcf, irts, irtd;

  /* sort */
  if(b > c) swap(&b, &c);
  if(a > b) swap(&a, &b);
  if(b > c) swap(&b, &c);

  sum = c;
  diff = c;
  sum += a;
  diff -= a;

  hcf = gcd(sum, diff);
  if(b % hcf != 0) return 0;
  sum /= hcf;
  diff /= hcf;
  b /= hcf;

  irts = isqrt(sum);
  if(irts * irts != sum || b % irts != 0) return 0;
  b /= irts;
  irtd = isqrt(diff);
  if(irtd * irtd != diff || b % irtd != 0) return 0;
  b /= irtd;

  return b == 1;
}

You can find the algorithm for isqrt @ Methods_of_computing_square_roots or use binary search method.

#define NEXT(n, i)  (((n) + (i)/(n)) >> 1)  

unsigned int isqrt(int number) {  
  unsigned int n  = 1;  
  unsigned int n1 = NEXT(n, number);  

  while(abs(n1 - n) > 1) {  
    n  = n1;  
    n1 = NEXT(n, number);  
  }  
  while(n1*n1 > number)  
    n1--;  
  return n1;  
}

^{isqrt copied without change from codecodex}

---

Old Answer

1. Find the largest side and smallest side. (Without loss of generality, let's call them C and A). And B is the third side
2. Now C² - A² = B² for right angled triangle. i.e. (C+A)*(C-A)=B², calculate unsigned_sum=C+A and unsigned_diff=C-A (unsigned int is guaranteed to not overflow for sum of int)
3. Gather the prime factors of unsigned_sum and unsigned_diff. If they are not multiple of 2, it is not right angled. If factors are multiple of 2, keep dividing copy_of_B = B, once with pair of prime factors seen. (Check up to fac*fac < max(unsigned_sum, unsigned_dif), if fac divides either, try dividing with other also)
4. If B = 1 at end, the triangle was right angled, else it is not.

int is_right_triangle(int a, int b, int c)
{
  unsigned int sum, diff;
  int f = 2;  /* factor */

  /* sort */
  if(b > c) swap(&b, &c);
  if(a > b) swap(&a, &b);
  if(b > c) swap(&b, &c);

  sum = c;
  diff = c;
  sum += a;
  diff -= a;

  while(f * f <= sum || f * f <= diff) {
    int count = 0;
    while(sum % f == 0) { sum /= f; ++count; }
    while(diff % f == 0) { diff /= f; ++count; }
    if(count % 2 == 1) return 0;
    while(count != 0) {
      b /= f;
      count -= 2;
    }
    ++f;  /* f = (f == 2 ? 3 : f + 2); */
  }
  return b == 1;
}

Optimizations
1. As mentioned in this comment, you can divide unsigned_sum, unsigned_diff and b with gcd(unsigned_sum, unsigned_diff) and can handle unsigned_sum and unsigned_diff separately.
2. In the loop if you can check at any point that product of sum and diff (and square of b) is guaranteed to not overflow you can check for sum * diff == (unsigned)b * b and break accordingly.

Answer 2

For all right triangles with integer sides a, b & c, there is always a pair of integers (m, n), such that;

g = gcd(a, gcd(b, c)); // greatest common divisor of a, b, c

baseA = a / g;
baseB = b / g;
baseC = c / g;

baseA = m * m - n * n;
baseB = 2 * m * n;
baseC = m * m + n * n;

Keeping this in mind (see primitive Pythagorean triples on this page), you can decompose (baseB / 2) (baseB being the even integer) to its factors and then check the factor pairs (m, n) (I'm afraid, this must be brute force) whether they satisfy the above conditions for baseA and baseC as well.

I think, this procedure will take care of overflow issue and assert that any intermediate step of computation will never exceed the longest side of the triangle; "c" in this case.

edit: @anatolyg is right. a, b & c are to be divided into their greatest common divisor, g; however, this correction still does not violate the acceptance of the solution, for down scaling all three integers will indeed help to assert the non-overflow constraint.

Last edit: I think the code below works (tested to the 32 bits integer limit & compiled with gcc).

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

//  linked list definition for the set of divisors
struct divisorSet {
    int divisor;
    struct divisorSet *next;
};

//  swaps two integers
void swap(int *a, int *b) {
    int t;

    t = *a;
    *a = *b;
    *b = t;

    return;
}

//  computes the greatest common divisor
int gcd(int a, int b) {
    int t;

    if (a < b) {
        swap(&a, &b);
    }

    while (b) {
        t = a % b;
        a = b;
        b = t;
    }

    return (a);
}

//  sorts a, b & c as follows:
//  a < c
//  b is the even integer regardless of its magnitude
int sort(int *a, int *b, int *c) {
    int oneEven;

    oneEven = 0;

    if (*b % 2) {
        if (*a % 2) {
            if (*c % 2) {
                oneEven = 1;
            }
            else {
                swap(b, c);
            }
        }
        else {
            swap(a, b);
        }
    }

    if (*a > *c) {
        swap(a, c);
    }

    return (oneEven);
}

//  creates the divisor set as linked list
struct divisorSet *createDivisorSet(int b) {
    struct divisorSet *dSet, *dTmp, *dBase;
    int l, i, k;

    k = sizeof(struct divisorSet);
    l = b / 2;
    dBase = malloc(k);
    dSet = dBase;
    i = 1;
    dSet->divisor = i;

    while (i++ < l) {
        if (!(b % i)) {
            dTmp = dSet;
            dSet = malloc(k);
            dSet->divisor = i;
            dTmp->next = dSet;
        }
    }

    dSet->next = 0;

    return (dBase);
}

//  frees allocated memory
void releaseMem(struct divisorSet *dSet) {
    struct divisorSet *dTmp;

    while (dSet->next) {
        dTmp = dSet->next;
        free(dSet);
        dSet = dTmp;
    }

    free(dSet);
    return;
}

//  test if pythagorean triangle or not
int isRightTriangle(int a, int b, int c) {
    struct divisorSet *dSet, *dTmp, *dBase;
    int g, baseA, baseB, baseC, m, n;

    g = gcd(a, gcd(b, c));
    baseA = a / g;
    baseB = b / g;
    baseC = c / g;

    if (sort(&baseA, &baseB, &baseC)) return (0);

    dSet = createDivisorSet(baseB / 2);
    dBase = dSet;

    while (dSet->next) {
        n = dSet->divisor * dSet->divisor;
        dTmp = dSet;

        while (dTmp->next) {
            dTmp = dTmp->next;
            m = dTmp->divisor * dTmp->divisor;

            if (m - n == baseA && m + n == baseC) {
                releaseMem(dBase);
                return (1);
            }
        }

        dSet = dSet->next;
    }

    releaseMem(dBase);
    return (0);
}

void scaleSides(int *a, int *b, int *c, int s) {
    *a *= s;
    *b *= s;
    *c *= s;
    return;
}

int main(void) {
    int a, b, c, s;

    s = 7040900;

    a = 160;
    b = 231;
    c = 281; // (right triangle)
    printf("a = %10d   b = %10d   c = %10d   rightTriangle = %d\n", a, b, c, isRightTriangle(a, b, c));

    scaleSides(&a, &b, &c, s); // testing for overflow (right triangle)
    printf("a = %10d   b = %10d   c = %10d   rightTriangle = %d\n", a, b, c, isRightTriangle(a, b, c));

    b += 2; // testing for overflow (not right triangle)
    printf("a = %10d   b = %10d   c = %10d   rightTriangle = %d\n", a, b, c, isRightTriangle(a, b, c));

    a = 207;
    b = 224;
    c = 305; // (right triangle)
    printf("a = %10d   b = %10d   c = %10d   rightTriangle = %d\n", a, b, c, isRightTriangle(a, b, c));

    scaleSides(&a, &b, &c, s); // testing for overflow (right triangle)
    printf("a = %10d   b = %10d   c = %10d   rightTriangle = %d\n", a, b, c, isRightTriangle(a, b, c));

    b += 2; // testing for overflow (not right triangle)
    printf("a = %10d   b = %10d   c = %10d   rightTriangle = %d\n", a, b, c, isRightTriangle(a, b, c));

    printf("press <enter> to exit...\n");
    getchar();
    return (0);
}