Usm*_*ail 6 language-agnostic algorithm
A^2+B^2+C^2+D^2 = N给定一个整数N,打印出ABCD解决方程的整数值的所有可能组合.
我猜我们可以比蛮力更好.
天真的蛮力将是这样的:
n = 3200724;
lim = sqrt (n) + 1;
for (a = 0; a <= lim; a++)
for (b = 0; b <= lim; b++)
for (c = 0; c <= lim; c++)
for (d = 0; d <= lim; d++)
if (a * a + b * b + c * c + d * d == n)
printf ("%d %d %d %d\n", a, b, c, d);
不幸的是,这将导致超过一万亿次循环,而不是过度有效.
实际上,你可以通过在每个级别折扣大量的不可能性来做得比这更好,例如:
#include <stdio.h>
int main(int argc, char *argv[]) {
int n = atoi (argv[1]);
int a, b, c, d, na, nb, nc, nd;
int count = 0;
for (a = 0, na = n; a * a <= na; a++) {
for (b = 0, nb = na - a * a; b * b <= nb; b++) {
for (c = 0, nc = nb - b * b; c * c <= nc; c++) {
for (d = 0, nd = nc - c * c; d * d <= nd; d++) {
if (d * d == nd) {
printf ("%d %d %d %d\n", a, b, c, d);
count++;
}
tot++;
}
}
}
}
printf ("Found %d solutions\n", count);
return 0;
}
它仍然是蛮力,但不是那么野蛮,因为它知道什么时候尽早停止每个级别的循环.
在我的(相对)适度的盒子上,需要不到一秒钟(a)来获得最多50,000个数字的所有解决方案.除此之外,它开始花费更多时间:
n time taken
---------- ----------
100,000 3.7s
1,000,000 6m, 18.7s
因为n = ten million,在我杀了之前它已经持续了大约一个半小时.
所以,我想说蛮力在某种程度上是完全可以接受的.除此之外,还需要更多的数学解决方案.
为了提高效率,您只能检查那些解决方案d >= c >= b >= a.这是因为,你可以再建立从这些组合的所有解决方案集成到排列(与潜在的重复去除其中的两个或两个以上的值a,b,c,或者d是相同的).
此外,d循环体不需要检查每个值d,只是最后一个值.
1,000,000在这种情况下获得结果需要不到十秒而不是六分钟:
0 0 0 1000
0 0 280 960
0 0 352 936
0 0 600 800
0 24 640 768
: : : :
424 512 512 544
428 460 500 596
432 440 480 624
436 476 532 548
444 468 468 604
448 464 520 560
452 452 476 604
452 484 484 572
500 500 500 500
Found 1302 solutions
real 0m9.517s
user 0m9.505s
sys 0m0.012s
该代码如下:
#include <stdio.h>
int main(int argc, char *argv[]) {
int n = atoi (argv[1]);
int a, b, c, d, na, nb, nc, nd;
int count = 0;
for (a = 0, na = n; a * a <= na; a++) {
for (b = a, nb = na - a * a; b * b <= nb; b++) {
for (c = b, nc = nb - b * b; c * c <= nc; c++) {
for (d = c, nd = nc - c * c; d * d < nd; d++);
if (d * d == nd) {
printf ("%4d %4d %4d %4d\n", a, b, c, d);
count++;
}
}
}
}
printf ("Found %d solutions\n", count);
return 0;
}
并且,根据DSM的建议,d循环可以完全消失(因为只有一个可能的值d(折扣负数)并且可以计算),这使我的100万个案例减少到两秒,而十个百万箱,更容易管理68秒.
该版本如下:
#include <stdio.h>
#include <math.h>
int main(int argc, char *argv[]) {
int n = atoi (argv[1]);
int a, b, c, d, na, nb, nc, nd;
int count = 0;
for (a = 0, na = n; a * a <= na; a++) {
for (b = a, nb = na - a * a; b * b <= nb; b++) {
for (c = b, nc = nb - b * b; c * c <= nc; c++) {
nd = nc - c * c;
d = sqrt (nd);
if (d * d == nd) {
printf ("%d %d %d %d\n", a, b, c, d);
count++;
}
}
}
}
printf ("Found %d solutions\n", count);
return 0;
}
(a):所有时间都在内部printf注释完成,以便I/O不会扭曲数字.
维基百科页面有一些有趣的背景信息，但拉格朗日的四平方定理（或更准确地说，巴切特定理 - 拉格朗日仅证明了它）并没有真正详细介绍如何找到所述平方。
正如我在评论中所说，解决方案将非常重要。本文讨论四平方和的可解性。该论文声称：
没有方便的算法（除了本文第二段中提到的简单算法之外）来查找表示计算所指示的其他解决方案，但这也许可以通过了解哪些类型的解决方案的作用和用途来简化搜索不存在。
还有一些与该主题相关的其他有趣的事实。还存在其他定理，指出每个整数都可以写成四个特定平方倍数的和。例如，每个整数都可以写为 N = a^2 + 2b^2 + 4c^2 + 14d^2。对于所有整数来说，有 54 个这样的情况，拉马努金在 1917 年提供了完整的列表。
有关详细信息，请参阅模块化表单。除非您有一些数论背景，否则这并不容易理解。如果您可以概括拉马努金的 54 种形式，那么您可能会更容易做到这一点。话虽如此，在我引用的第一篇论文中，有一个小片段讨论了可能找到每个解决方案的算法（尽管我发现它有点难以理解）：
例如，据报道，1911 年，计算器 Gottfried Ruckle 被要求将 N = 15663 化简为四个平方和。他在 8 秒内得出了 125^2 + 6^2 + 1^2 + 1^2 的解，紧接着是 125^2 + 5^2 + 3^2 + 2^2。一个更困难的问题（反映为第一项距原始数字较远，后面的项相应较大）花费了 56 秒：11399 = 105^2 + 15^2 + 8^2 + 5^2。一般来说，策略是首先将第一项设置为 N 以下的最大平方，并尝试将较小的余数表示为三个平方和。然后第一项设置为 N 下面的下一个最大的方格，依此类推。随着时间的推移，闪电计算器将熟悉将小数字表示为平方和，这将加快该过程。
（强调我的。）
该算法被描述为递归的，但它可以很容易地迭代实现。