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

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);
}

Answer 2

If a^2+b^2=c^2 (modulo p_i) for some primes p1, p2, ..., then you know that a^2+b^2=c^2 (modulo p1*p2*...). By picking primes so that the intermediate sums don't overflow, you can check an arbitrary range.

Here's code that works for c^2 up to 1e22, which means it's valid for a, b, c all 32 bit ints. If that's not sufficient, you can use more bases (or larger primes, being careful to make sure that the intermediate calculations don't overflow your ints).

void swap(int *a, int *b) {
    int t = *a;
    *a = *b;
    *b = t;
}

int bases[] = {5051, 5059, 5077, 5081, 5087, 5099};

int is_rightangled(int a, int b, int c) {
  if (a > c) swap(&a, &c);
  if (b > c) swap(&b, &c);
  for (int i = 0; i < sizeof(bases)/sizeof(bases[0]); i++) {
    int p = bases[i];
    int ap = a % p, bp = b % p, cp = c % p;
    if (((ap * ap) + (bp * bp)) % p != (cp * cp) % p) return 0;
  }
  return 1;
}

Answer 3

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 4

Before anything else, let's assume the value of all the legs are positive integers. They must verify the elementary triangle relationships:

• 0 < a, 0 < b, 0 < c;
• a < b + c, b < c + a, c < a + b;
• abs(a - b) < c, abs(b - c) < a, abs(c - a) < b.

Otherwise they cannot be the legs of a triangle.

A solution that refines the solution proposed by @mohit-jain:

1. Let the legs be a > b > c. The Pythagorean theorem says that if a * a = b * b + c * c then a, b and c are the legs of a right triangle (a being the hypotenuse). The equation can be rewritten as a * a - c * c = b * b, or (a + c) * (a - c) = b * b;
2. Assign sum = a + c, diff = a - c. This is where the algorithm can overflow (a + c).
3. Now b * b = sum * diff. If sum and diff are not mutually prime integers then their GCD must also divide b. Compute GCD(sum, diff) and check if it divides b. If it doesn't divide b then it is not a square triangle.
4. Divide sum, diff and b by GCD(sum, diff). If the original triangle is a right triangle, the equation b * b = sum * diff still stands (and vice-versa).
5. Now sum and diff don't have any common factors. If the equation is verified then sum and b (and also diff and b) must have common factors. Let b1 = b2 = b. The equation is b1 * b2 = sum * diff.
6. Divide b1 and sum by their GCD; divide b1 and diff by their GCD.
7. Divide b2 and sum by their GCD; divide b2 and diff by their GCD.
8. Now the values of b1, b2, sum and diff are smaller but it's possible that they are still too large. However, because of the divisions in the previous steps, b1 and b2 doesn't share factors with sum and diff. The only case they verify the equation is when b1 == b2 == sum == diff == 1.

The code is pretty lengthy. You can find it in this gist. It doesn't verify the basic conditions for the numbers to be the legs of a triangle (exposed above) but implements the algorithm and uses the remark #2 (below) to avoid overflows.

---

Remark #1

Another possibility is to check if the legs verify some elementary properties of Pythagorean triangles. Most of these checks use only simple mathematical operations and can reject many leg combinations. For the ones that pass, use the algorithm above.

Remark #2

The mathematical properties in the Wikipedia page listed above can also be used to find common factors for the legs or convenient ways to combine them in order to find their common factors and reduce them.

For example, if all the legs are even numbers then they can be divided by 2 before anything else. The operation can be repeated while all of them are still even. After that, if the hypotenuse is still an even number then they cannot be the legs of a right triangle (see the properties in the list)

Given the hypotenuse is a in the algorithm above, the other odd number can be chosen to be c (instead of the smallest number). This approach guarantees that sum and diff are even numbers and sum can be divided by 2 without actually computing a + c.

When a and c are odd, sum / 2 can be computed as a / 2 + c / 2 + 1. This completely removes the risk of overflow and the rest of the algorithm turns all the involved numbers smaller and smaller on each step.

Answer 5

You can increase the range of values that can be handled by means of extended arithmetic.

If you split the number X in two parts of at most b bits, you get X = B X' + X", where X' and X" have at most b bits (B is the b'th power of 2). Then squaring, X² = B²X'² + 2BX'X" + X"², where the three parts have at most b+1 significand bits.

If you decompose the products in parts of b bits, you rewrite as

B²(B [X'²]' + [X'²]") + 2B(B [X'X"]' + [X'X"]") + B[X"²]' + [X"²]"

and get

B³ [X'²]' + B² ([X'²]" + 2[X'X"]') + B (2[X'X"]" + [X"²]') + [X"²]"

With some care, keeping a few guard bits and handling the carries, you can obtain the result arranged in two words.

Extended addition is straightforward.