我想知道测试三个数字是否是毕达哥拉斯三重奏最有效的公式是什么。
提醒一下：勾股三元组是三个整数，其中a²+b²=c²。
我的意思不是就时间而言最有效的公式，而是就不引起特定整数（让我们说32位unsigned int）溢出而言最有效的公式。
我正在尝试对以下内容进行重新排列a*a + b*b == c*c：
假设
a<=b<c，那么我能得到的最佳公式是：
2b*(c-b) == (a+b-c) * (a-b+c)
通过该公式可以证明，右侧小于a*c，左侧应该也是如此，但是a*c看起来并没有很大的改进c*c。
所以我的问题是，是否有一个更好的公式可以处理更大的数字而又不会溢出整数空间。公式的执行时间无关紧要，除了应为O（1）。
PS：我不知道该在这里还是在Mathematics SE上发布这样的问题，但是对我来说，它似乎更多地与编程有关。
编辑如果您需要一直使用32位整数，则可以修改数学以适合您的要求。为简单起见，我对16位数据块进行了数学（平方和求和），并使用包含2个无符号整数的结构作为结果。
#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您的32位整数64位多头甚至浮点双打将编辑 降低溢出的机会，并继续因为所有之中，编程，O（1）主要的架构（X86，ARM等）有一个整型到双转换操作码的低级别并从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;
}
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句