Check the correctness of the triangle?

Question

I am trying to check if a triangle is a regular triangle in C. a , b and c are the lengths of the 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 can I avoid integer sum overflow and multiplication? Suppose we do not have a long long type.

Answer 1

Improved (optimized) version

• Find the largest side and the smallest side. (Without loss of generality, we call them C and A). And B is the third party.
• Now C ² - A ² = B ² for a right triangle. (C + A) * (CA) = B ² calculate unsigned_sum = C + A and unsigned_diff = CA (unsigned int will not overflow for the sum int )
• Separate the sum, diff and B with gcd sum and diff. If he does not divide B, it is not a right triangle. If so, the sum and diff will be perfect squares if the triangle is right.
• Find the integer square root of the sum and diff. If the product of the roots is B, the 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 an algorithm for isqrt @ Methods_of_computing_square_roots or use the 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 unchanged from codecodex}

---

Old answer

• Find the largest side and the smallest side. (Without loss of generality, we call them C and A). And B is the third party.
• Now C ² - A ² = B ² for a right triangle. (C + A) * (CA) = B ² calculate unsigned_sum = C + A and unsigned_diff = CA (unsigned int will not overflow for the sum int )
• Collect the main factors unsigned_sum and unsigned_diff. If they are not a multiple of 2, this is not correct at an angle. If the odds are a multiple of 2, continue to divide copy_of_B = B, once per couple of key factors. (Check that fac * fac <max (unsigned_sum, unsigned_dif), if the delimiter is also divisible, try splitting with another as well)
• If B = 1 at the end, the triangle was at right angles, otherwise 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; } 

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

Answer 2

For all right triangles with integer sides a, b, and c, there always exists 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; 

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

I think this procedure will take care of the overflow problem and state that any intermediate calculation step will never exceed the longest side of the triangle; "c" in this case.

edit: @anatolyg is right. a, b and c should be divided by their largest common divisor g; however, this correction still does not violate the decision, since scaling all three integers will really help to approve the overflow constraint.

Last edit: I think the code below works (checked for 32 bit integer limit and 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 3

You can increase the range of values ​​that can be processed using advanced arithmetic.

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

If you decompose products in parts of bit b , 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 caution, keeping a few guard bits and controlling hyphenation, you can get the result located in a nutshell.

Advanced add-ons are simple.

Answer 4

First of all, let it be assumed that all legs are integer positive. They should check the elementary relationships of the triangle:

• 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 clarifies the solution suggested by @ mohit-jain:

• Let the legs a > b > c . Pythagorean theorem says that if a * a = b * b + c * c , then a , b and c are the legs of the right triangle ( a being hypotenuse). The equation can be rewritten as a * a - c * c = b * b , or (a + c) * (a - c) = b * b ;
• Assign sum = a + c , diff = a - c . Here the algorithm may overflow ( a + c ) .
• Now b * b = sum * diff . If sum and diff not coprime integers , then their GCD must also divide b . Calculate the GCD(sum, diff) and check if it divides b . If he does not divide b , then this is not a square triangle.
• Divide sum , diff and b by GCD(sum, diff) . If the original triangle is a right triangle, then the equation b * b = sum * diff remains (and vice versa).
• Now sum and diff have no common factors. If the equation is verified, then sum and b (as well as diff and b ) must have common factors. Let b1 = b2 = b . The equation b1 * b2 = sum * diff .
• Divide b1 and sum their GCD; split b1 and diff into their GCD.
• Divide b2 and sum their GCD; split b2 and diff into their GCD.
• Now the values ​​of b1 , b2 , sum and diff smaller, but it is possible that they are still too large. However, due to the divisions in the previous steps, b1 and b2 do not share the coefficients with sum and diff . The only time they check the equation is when b1 == b2 == sum == diff == 1 .

The code is quite long. You can find it in this essence . It does not check the basic conditions for numbers that are the legs of the triangle (shown above), but implements the algorithm and uses note No. 2 (below) to avoid overflow.

---

Note No. 1

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

Note 2

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

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

Given that the hypotenuse a in the above algorithm, another odd number can be chosen as c (instead of the smallest number). This approach ensures that sum and diff are even numbers, and that sum can be divided by 2 without actually calculating a + c .

When a and c are odd, sum / 2 can be calculated as a / 2 + c / 2 + 1 . This completely eliminates the risk of overflow, and the rest of the algorithm, all the numbers involved are less and less at each step.

Answer 5

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 choosing primes so that the subtotals do not overflow, you can check an arbitrary range.

Here is the code that works for c ^ 2 to 1e22, which means that it is valid for a, b, c of all 32-bit ints. If this is not enough, you can use more bases (or large primes, making sure that intermediate calculations do not overwhelm 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; }