模整数 space 中毕达哥拉斯三元组的有效测试

Question

我想知道用于测试三个数字是否为毕达哥拉斯三元组的最有效公式是什么。
提醒一下：毕达哥拉斯三元组是三个整数，其中 a²+b²=c²。

我的意思不是在时间方面最有效的公式，而是在不导致特定整数溢出方面最有效的公式（比方说 32 位无符号整数).

我尝试重新排列 a*a + b*b == c*c:

Let's assume a<=b<c, then the best formula I could get to is:
2b*(c-b) == (a+b-c) * (a-b+c)
with this formula can be proven, that the right side is smaller than a*c and so should be the left side, but a*c doesn't look like a huge improvement of c*c.

所以我的问题是，是否有更好的公式可以处理更大的数字而不会溢出整数 space。公式的执行时间并不重要，除了它应该是 O(1).

PS: 我不知道我是否应该 post 这样的问题还是在 Mathematics SE 上，但对我来说似乎更多的是关于编程。

Answer 1

我认为稍微重新安排会有很大帮助。

a²+b²=c² 

can be written as b²=c²-a²

which is b² = (c-a)(c+a)

and hence we arrive at

b/(c+a) = (c-a)/b

or (c+a)/b = b/(c-a)

现在使用上面的方程，你不需要计算平方。

所以我们必须这样做

  if(((c+a)/(double)b)==((double)(b)/(c-a)))
    printf("Yes it is pythagorean triples");
  else printf("No it is not");

Answer 2

EDIT 如果您一直需要 32 位整数，那么您只需修改数学即可满足您的要求。为了简单起见，我对 16 位数据块进行数学运算（平方和求和），并使用包含 2 个无符号整数的结构作为结果。

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

将您的 32 位整数转换为 64 位长整型甚至浮点双精度将编辑减少溢出的可能性并继续以编程方式， O(1) 因为所有主要体系结构（x86、ARM 等）都在低级别将 int 转换为双转换操作码，并且从 int 转换为 long 也是一个 O(1) 操作。

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

模整数 space 中毕达哥拉斯三元组的有效测试

Efficient test for pythagorean triples in modulo integer space

c

algorithm

conditional

integer-overflow