c - Efficient test for pythagorean triples in modulo integer space -

i wondering effective formula, testing if 3 numbers pythagorean triple is.
reminder: pythagorean triple 3 integers a²+b²=c².

i mean not effective formula in terms of time, formula efficient in terms of not causing overflow on specific integer(lets 32-bit unsigned int).

i trying bit rearrangements of a*a + b*b == c*c:

let's assume a<=b<c, best formula is:
2b*(c-b) == (a+b-c) * (a-b+c)
formula can proven, right side smaller a*c , should left side, a*c doesn't huge improvement of c*c.

so question is, if there better formula conditional works bigger numbers without overflowing integer space. execution time of formula doesn't matter much, besides should o(1).

ps: don't know if should post such question here or on mathematics se, me seems more programming.

edit if need have 32bit integers way down can modify math fit requirement. keep simple math (squaring , summing) on 16bit chunks of data , use struct contains 2 unsigned ints result.

http://ideone.com/er2tas

#include <iostream> using namespace std; struct u64 {     unsigned int lo;     unsigned int hi;     bool of; }; u64 square(unsigned int a) {     u64 result;     unsigned int alo = (a & 0xffff);     unsigned int ahi = (a >> 16);     unsigned int aalo = alo * alo;     unsigned int aami = alo * ahi;     unsigned int aahi = ahi * ahi;     unsigned int aa1 = aalo & 0xffff;     unsigned int aa2 = (aalo >> 16) + (aami & 0xffff) + (aami & 0xffff);     unsigned int aa3 = (aa2 >> 16) + (aami >> 16) + (aami >> 16) + (aahi & 0xffff);     unsigned int aa4 = (aa3 >> 16) + (aahi >> 16);     result.lo = (aa1 & 0xffff) | ((aa2 & 0xffff) << 16);     result.hi = (aa3 & 0xffff) | (aa4 << 16);     result.of = false; // 0xffffffff^2 can't overflow     return result; } u64 sum(u64 a, u64 b) {     u64 result;     unsigned int a1 = a.lo & 0xffff;     unsigned int a2 = a.lo >> 16;     unsigned int a3 = a.hi & 0xffff;     unsigned int a4 = a.hi >> 16;     unsigned int b1 = b.lo & 0xffff;     unsigned int b2 = b.lo >> 16;     unsigned int b3 = b.hi & 0xffff;     unsigned int b4 = b.hi >> 16;     unsigned int s1 = a1 + b1;     unsigned int s2 = a2 + b2 + (s1 >> 16);     unsigned int s3 = a3 + b3 + (s2 >> 16);     unsigned int s4 = a4 + b4 + (s3 >> 16);     result.lo = (s1 & 0xffff) | ((s2 & 0xffff) << 16);     result.hi = (s3 & 0xffff) | ((s4 & 0xffff) << 16);     result.of = (s4 > 0xffff ? true : false);     return result; } bool istriple(unsigned int a, unsigned int b, unsigned int c) {     u64 aa = square(a);     u64 bb = square(b);     u64 cc = square(c);     u64 aabb = sum(aa, bb);     return aabb.lo == cc.lo && aabb.hi == cc.hi && aabb.of == false; } int main() {     cout << istriple(3,4,5) << endl;     cout << istriple(2800,9600,10000) << endl;      return 0; } 

conerting 32bit integers 64bit longs or floating point doubles edit reduce chance of overflow , continue being, programmatically, o(1) since major architectures (x86, arm, etc) have int double conversion op codes @ low level , casting long int o(1) operation.

bool istriple(int a, int b, int c) { long long biga = a; long long bigb = b; long long bigc = c; return biga * biga + bigb * bigb == bigc * bigc; }