A^2+B^2+C^2+D^2 = N Given an integer N, print out all possible combinations of integer values of ABCD which solve the equation.
^ 2 + B ^ 2 + C ^ 2 + D ^ 2 = N给定的整数N,打印出所有可能的组合的整数值解方程的ABCD。
I am guessing we can do better than brute force.
我想我们可以比武力强。
4 个解决方案
#1
4
The Wikipedia page has some interesting background information, but Lagrange's four-square theorem (or, more correctly, Bachet's Theorem - Lagrange only proved it) doesn't really go into detail on how to find said squares.
*页面上有一些有趣的背景信息，但拉格朗日的四平方定理(或者更准确地说，是巴赫定理——拉格朗日只是证明了这一点)并没有详细说明如何找到这些平方。
As I said in my comment, the solution is going to be nontrivial. This paper discusses the solvability of four-square sums. The paper alleges that:
正如我在我的评论中所说，解决方案将是非平凡的。本文讨论了四平方和的可解性。该报宣称:
There is no convenient algorithm (beyond the simple one mentioned in the second paragraph of this paper) for finding additional solutions that are indicated by the calculation of representations, but perhaps this will streamline the search by giving an idea of what kinds of solutions do and do not exist.
除了本文第二段中提到的简单算法之外，没有任何方便的算法可以找到通过计算表示来指示的其他解决方案，但这可能会简化搜索，因为它提供了一种关于哪些解决方案可以存在，哪些解决方案不存在的想法。
There are a few other interesting facts related to this topic. There exist other theorems that state that every integer can be written as a sum of four particular multiples of squares. For example, every integer can be written as N = a^2 + 2b^2 + 4c^2 + 14d^2. There are 54 cases like this that are true for all integers, and Ramanujan provided the complete list in the year 1917.
关于这个话题还有一些其他有趣的事实。还有其他的定理，说每个整数都可以写成四个特定的平方倍数的和。例如,每个整数可以写成N = a ^ 2 + 2 ^ 2 + 4 c ^ 2 + 14 d ^ 2。有54个这样的例子对所有整数都成立，Ramanujan在1917年提供了完整的列表。
For more information, see Modular Forms. This is not easy to understand unless you have some background in number theory. If you could generalize Ramanujan's 54 forms, you may have an easier time with this. With that said, in the first paper I cite, there is a small snippet which discusses an algorithm that may find every solution (even though I find it a bit hard to follow):
有关更多信息，请参见模块化表单。这并不容易理解，除非你有一些数字理论的背景。如果你能概括拉马努扬的54种形式，你可能会有更轻松的时间。话虽如此，在我引用的第一篇论文中，有一个小片段讨论了一种算法，它可以找到所有的解决方案(尽管我发现它有点难以理解):
For example, it was reported in 1911 that the calculator Gottfried Ruckle was asked to reduce N = 15663 as a sum of four squares. He produced a solution of 125^2 + 6^2 + 1^2 + 1^2 in 8 seconds, followed immediately by 125^2 + 5^2 + 3^2 + 2^2. A more difficult problem (reflected by a first term that is farther from the original number, with correspondingly larger later terms) took 56 seconds: 11399 = 105^2 + 15^2 + 8^2 + 5^2. In general, the strategy is to begin by setting the first term to be the largest square below N and try to represent the smaller remainder as a sum of three squares. Then the first term is set to the next largest square below N, and so forth. Over time a lightning calculator would become familiar with expressing small numbers as sums of squares, which would speed up the process.
例如，1911年有报道称，哥德弗莱德·鲁克尔(Gottfried Ruckle)计算器被要求将N = 15663减去4个平方之和。他拿出一个解决方案125 ^ 2 + 6 ^ 2 + 1 ^ 2 + 1 ^ 2 8秒,跟随125 ^ 2 + 5 ^ 2 + 3 ^ 2 + 2 ^ 2。更困难的问题(反映在第一个任期内,远离原来的数量,与相应的大后计算)花了56秒:11399 = 105 ^ 2 + 15 8 ^ ^ 2 + 2 + 5 ^ 2。一般来说，策略是首先将第一项设为N以下最大的平方，然后将较小的余数表示为三个平方之和。然后第一项被设为下一个最大的平方，在N下面，等等。随着时间的推移，闪电计算器会逐渐熟悉如何将小数字表示为平方和，这将加快这一过程。
(Emphasis mine.)
(强调我的。)
The algorithm is described as being recursive, but it could easily be implemented iteratively.
该算法被描述为递归，但它可以很容易地迭代地实现。
#2
6
Naive brute force would be something like:
天真的暴力会是:
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);
Unfortunately, this will result in over a trillion loops, not overly efficient.
不幸的是，这将导致超过一万亿次的循环，而不是过于高效。
You can actually do substantially better than that by discounting huge numbers of impossibilities at each level, with something like:
实际上，你可以通过在每一层上折现大量的不可能性来做得更好，比如:
#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;
}
It's still brute force, but not quite as brutish inasmuch as it understands when to stop each level of looping as early as possible.
它仍然是蛮力，但并不像它所理解的那样野蛮，因为它尽可能早地停止每一层循环。
On my (relatively) modest box, that takes under a second (a) to get all solutions for numbers up to 50,000. Beyond that, it starts taking more time:
在我的(相对)温和的盒子上，需要不到一秒钟(a)就能得到5万个数字的所有解。除此之外，它开始需要更多的时间:
n time taken
---------- ----------
100,000 3.7s
1,000,000 6m, 18.7s
For n = ten million, it had been going about an hour and a half before I killed it.
n = 1000万的时候，我花了一个半小时才把它弄死。
So, I would say brute force is perfectly acceptable up to a point. Beyond that, more mathematical solutions would be needed.
我认为蛮力在某种程度上是完全可以接受的。除此之外，还需要更多的数学解。
For even more efficiency, you could only check those solutions where d >= c >= b >= a. That's because you could then build up all the solutions from those combinations into permutations (with potential duplicate removal where the values of two or more of a, b, c, or d are identical).
更效率,你只能检查这些解决方案在d > = c > b = > =一个。那是因为你可以建立所有的解决方案组合成排列(与潜在重复删除的两个或两个以上的值,b,c,d是相同的)。
In addition, the body of the d loop doesn't need to check every value of d, just the last possible one.
此外，d循环的主体不需要检查d的每个值，只需要检查最后一个可能的值。
Getting the results for 1,000,000 in that case takes under ten seconds rather than over six minutes:
在这种情况下，得到100万的结果需要不到10秒，而不是超过6分钟:
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
That code follows:
这段代码:
#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;
}
And, as per a suggestion by DSM, the d loop can disappear altogether (since there's only one possible value of d (discounting negative numbers) and it can be calculated), which brings the one million case down to two seconds for me, and the ten million case to a far more manageable 68 seconds.
DSM,正如每一个建议的d环可以完全消失(因为只有一个可能值的d(打折负数),它可以计算),将一百万例下降到两秒钟对我来说,和一千万年更可控的68秒。
That version is as follows:
该版本如下:
#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): All timings are done with the inner printf commented out so that I/O doesn't skew the figures.
(a):所有的计时都是用内printf注释掉的，这样I/O就不会扭曲数字。
#3
2
It seems as though all integers can be made by such a combination:
似乎所有的整数都可以由这样的组合组成:
0 = 0^2 + 0^2 + 0^2 + 0^2
1 = 1^2 + 0^2 + 0^2 + 0^2
2 = 1^2 + 1^2 + 0^2 + 0^2
3 = 1^2 + 1^2 + 1^2 + 0^2
4 = 2^2 + 0^2 + 0^2 + 0^2, 1^2 + 1^2 + 1^2 + 1^2 + 1^2
5 = 2^2 + 1^2 + 0^2 + 0^2
6 = 2^2 + 1^2 + 1^2 + 0^2
7 = 2^2 + 1^2 + 1^2 + 1^2
8 = 2^2 + 2^2 + 0^2 + 0^2
9 = 3^2 + 0^2 + 0^2 + 0^2, 2^2 + 2^2 + 1^2 + 0^2
10 = 3^2 + 1^2 + 0^2 + 0^2, 2^2 + 2^2 + 1^2 + 1^2
11 = 3^2 + 1^2 + 1^2 + 0^2
12 = 3^2 + 1^2 + 1^2 + 1^2, 2^2 + 2^2 + 2^2 + 0^2
.
.
.
and so forth
等等
As I did some initial working in my head, I thought that it would be only the perfect squares that had more than 1 possible solution. However after listing them out it seems to me there is no obvious order to them. However, I thought of an algorithm I think is most appropriate for this situation:
当我在头脑中做了一些初步的工作时，我认为这只是一个完美的正方形，有超过1个可能的解决方案。然而，在列出它们之后，在我看来它们并没有明显的顺序。然而，我想到了一种最适合这种情况的算法:
The important thing is to use a 4-tuple (a, b, c, d). In any given 4-tuple which is a solution to a^2 + b^2 + c^2 + d^2 = n, we will set ourselves a constraint that a is always the largest of the 4, b is next, and so on and so forth like:
最重要的是使用一个4-tuple(a,b,c,d)。在任何给定4-tuple ^ 2 +的解决方案b d ^ ^ 2 + c ^ 2 + 2 = n,我们将一个约束,总是最大的4 b是接下来,等等等等:
a >= b >= c >= d
Also note that a^2 cannot be less than n/4, otherwise the sum of the squares will have to be less than n.
还要注意,^ 2不能小于n / 4,否则的平方和小于n。
Then the algorithm is:
的算法是:
1a. Obtain floor(square_root(n)) # this is the maximum value of a - call it max_a
1b. Obtain the first value of a such that a^2 >= n/4 - call it min_a
2. For a in a range (min_a, max_a)
At this point we have selected a particular a, and are now looking at bridging the gap from a^2 to n - i.e. (n - a^2)
在这一点上我们选择了一个特定的,现在看着弥合差距从^ 2到n——即(n - ^ 2)
3. Repeat steps 1a through 2 to select a value of b. This time instead of finding
floor(square_root(n)) we find floor(square_root(n - a^2))
and so on and so forth. So the entire algorithm would look something like:
诸如此类。整个算法看起来是这样的
1a. Obtain floor(square_root(n)) # this is the maximum value of a - call it max_a
1b. Obtain the first value of a such that a^2 >= n/4 - call it min_a
2. For a in a range (min_a, max_a)
3a. Obtain floor(square_root(n - a^2))
3b. Obtain the first value of b such that b^2 >= (n - a^2)/3
4. For b in a range (min_b, max_b)
5a. Obtain floor(square_root(n - a^2 - b^2))
5b. Obtain the first value of b such that b^2 >= (n - a^2 - b^2)/2
6. For c in a range (min_c, max_c)
7. We now look at (n - a^2 - b^2 - c^2). If its square root is an integer, this is d.
Otherwise, this tuple will not form a solution
At steps 3b and 5b I use (n - a^2)/3, (n - a^2 - b^2)/2. We divide by 3 or 2, respectively, because of the number of values in the tuple not yet 'fixed'.
在步骤3 b和5 b我使用(n - ^ 2)/ 3 b(n - 2 ^ - ^ 2)/ 2。我们分别除以3或2，因为元组中值的个数还没有“固定”。
An example:
一个例子:
doing this on n = 12:
在n = 12时这样做:
1a. max_a = 3
1b. min_a = 2
2. for a in range(2, 3):
use a = 2
3a. we now look at (12 - 2^2) = 8
max_b = 2
3b. min_b = 2
4. b must be 2
5a. we now look at (12 - 2^2 - 2^2) = 4
max_c = 2
5b. min_c = 2
6. c must be 2
7. (n - a^2 - b^2 - c^2) = 0, hence d = 0
so a possible tuple is (2, 2, 2, 0)
2. use a = 3
3a. we now look at (12 - 3^2) = 3
max_b = 1
3b. min_b = 1
4. b must be 1
5a. we now look at (12 - 3^2 - 1^2) = 2
max_c = 1
5b. min_c = 1
6. c must be 1
7. (n - a^2 - b^2 - c^2) = 1, hence d = 1
so a possible tuple is (3, 1, 1, 1)
These are the only two possible tuples - hey presto!
这是两个可能的元组——嘿，马上!
#4
0
nebffa has a great answer. one suggestion:
nebffa有一个很好的答案。一个建议:
step 3a: max_b = min(a, floor(square_root(n - a^2))) // since b <= a
max_c and max_d can be improved in the same way too.
max_c和max_d也可以通过同样的方式进行改进。
Here is another try:
这是另一个尝试:
1. generate array S: {0, 1, 2^2, 3^2,.... nr^2} where nr = floor(square_root(N)).
now the problem is to find 4 numbers from the array that sum(a, b,c,d) = N;
现在的问题是从数组中找出4个数字(a, b,c,d) = N;
2. according to neffa's post (step 1a & 1b), a (which is the largest among all 4 numbers) is between [nr/2 .. nr].
We can loop a from nr down to nr/2 and calculate r = N - S[a]; now the question is to find 3 numbers from S the sum(b,c,d) = r = N -S[a];
我们可以从nr循环到nr/2，计算r = N - S[a];现在问题是要从S中找出3个数字(b,c,d) = r = N -S[a];
here is code:
下面是代码:
nr = square_root(N);
S = {0, 1, 2^2, 3^2, 4^2,.... nr^2};
for (a = nr; a >= nr/2; a--)
{
r = N - S[a];
// it is now a 3SUM problem
for(b = a; b >= 0; b--)
{
r1 = r - S[b];
if (r1 < 0)
continue;
if (r1 > N/2) // because (a^2 + b^2) >= (c^2 + d^2)
break;
for (c = 0, d = b; c <= d;)
{
sum = S[c] + S[d];
if (sum == r1)
{
print a, b, c, d;
c++; d--;
}
else if (sum < r1)
c++;
else
d--;
}
}
}
runtime is O(sqare_root(N)^3).
运行时是O(sqare_root(N)^ 3)。
Here is the test result running java on my VM (time in milliseconds, result# is total num of valid combination, time 1 with printout, time2 without printout):
这是在我的VM上运行java的测试结果(时间以毫秒为单位，结果#是有效组合的总num，时间1有printout，时间2没有printout):
N result# time1 time2
----------- -------- -------- -----------
1,000,000 1302 859 281
10,000,000 6262 16109 7938
100,000,000 30912 442469 344359
#1
4
The Wikipedia page has some interesting background information, but Lagrange's four-square theorem (or, more correctly, Bachet's Theorem - Lagrange only proved it) doesn't really go into detail on how to find said squares.
*页面上有一些有趣的背景信息，但拉格朗日的四平方定理(或者更准确地说，是巴赫定理——拉格朗日只是证明了这一点)并没有详细说明如何找到这些平方。
As I said in my comment, the solution is going to be nontrivial. This paper discusses the solvability of four-square sums. The paper alleges that:
正如我在我的评论中所说，解决方案将是非平凡的。本文讨论了四平方和的可解性。该报宣称:
There is no convenient algorithm (beyond the simple one mentioned in the second paragraph of this paper) for finding additional solutions that are indicated by the calculation of representations, but perhaps this will streamline the search by giving an idea of what kinds of solutions do and do not exist.
除了本文第二段中提到的简单算法之外，没有任何方便的算法可以找到通过计算表示来指示的其他解决方案，但这可能会简化搜索，因为它提供了一种关于哪些解决方案可以存在，哪些解决方案不存在的想法。
There are a few other interesting facts related to this topic. There exist other theorems that state that every integer can be written as a sum of four particular multiples of squares. For example, every integer can be written as N = a^2 + 2b^2 + 4c^2 + 14d^2. There are 54 cases like this that are true for all integers, and Ramanujan provided the complete list in the year 1917.
关于这个话题还有一些其他有趣的事实。还有其他的定理，说每个整数都可以写成四个特定的平方倍数的和。例如,每个整数可以写成N = a ^ 2 + 2 ^ 2 + 4 c ^ 2 + 14 d ^ 2。有54个这样的例子对所有整数都成立，Ramanujan在1917年提供了完整的列表。
For more information, see Modular Forms. This is not easy to understand unless you have some background in number theory. If you could generalize Ramanujan's 54 forms, you may have an easier time with this. With that said, in the first paper I cite, there is a small snippet which discusses an algorithm that may find every solution (even though I find it a bit hard to follow):
有关更多信息，请参见模块化表单。这并不容易理解，除非你有一些数字理论的背景。如果你能概括拉马努扬的54种形式，你可能会有更轻松的时间。话虽如此，在我引用的第一篇论文中，有一个小片段讨论了一种算法，它可以找到所有的解决方案(尽管我发现它有点难以理解):
For example, it was reported in 1911 that the calculator Gottfried Ruckle was asked to reduce N = 15663 as a sum of four squares. He produced a solution of 125^2 + 6^2 + 1^2 + 1^2 in 8 seconds, followed immediately by 125^2 + 5^2 + 3^2 + 2^2. A more difficult problem (reflected by a first term that is farther from the original number, with correspondingly larger later terms) took 56 seconds: 11399 = 105^2 + 15^2 + 8^2 + 5^2. In general, the strategy is to begin by setting the first term to be the largest square below N and try to represent the smaller remainder as a sum of three squares. Then the first term is set to the next largest square below N, and so forth. Over time a lightning calculator would become familiar with expressing small numbers as sums of squares, which would speed up the process.
例如，1911年有报道称，哥德弗莱德·鲁克尔(Gottfried Ruckle)计算器被要求将N = 15663减去4个平方之和。他拿出一个解决方案125 ^ 2 + 6 ^ 2 + 1 ^ 2 + 1 ^ 2 8秒,跟随125 ^ 2 + 5 ^ 2 + 3 ^ 2 + 2 ^ 2。更困难的问题(反映在第一个任期内,远离原来的数量,与相应的大后计算)花了56秒:11399 = 105 ^ 2 + 15 8 ^ ^ 2 + 2 + 5 ^ 2。一般来说，策略是首先将第一项设为N以下最大的平方，然后将较小的余数表示为三个平方之和。然后第一项被设为下一个最大的平方，在N下面，等等。随着时间的推移，闪电计算器会逐渐熟悉如何将小数字表示为平方和，这将加快这一过程。
(Emphasis mine.)
(强调我的。)
The algorithm is described as being recursive, but it could easily be implemented iteratively.
该算法被描述为递归，但它可以很容易地迭代地实现。
#2
6
Naive brute force would be something like:
天真的暴力会是:
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);
Unfortunately, this will result in over a trillion loops, not overly efficient.
不幸的是，这将导致超过一万亿次的循环，而不是过于高效。
You can actually do substantially better than that by discounting huge numbers of impossibilities at each level, with something like:
实际上，你可以通过在每一层上折现大量的不可能性来做得更好，比如:
#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;
}
It's still brute force, but not quite as brutish inasmuch as it understands when to stop each level of looping as early as possible.
它仍然是蛮力，但并不像它所理解的那样野蛮，因为它尽可能早地停止每一层循环。
On my (relatively) modest box, that takes under a second (a) to get all solutions for numbers up to 50,000. Beyond that, it starts taking more time:
在我的(相对)温和的盒子上，需要不到一秒钟(a)就能得到5万个数字的所有解。除此之外，它开始需要更多的时间:
n time taken
---------- ----------
100,000 3.7s
1,000,000 6m, 18.7s
For n = ten million, it had been going about an hour and a half before I killed it.
n = 1000万的时候，我花了一个半小时才把它弄死。
So, I would say brute force is perfectly acceptable up to a point. Beyond that, more mathematical solutions would be needed.
我认为蛮力在某种程度上是完全可以接受的。除此之外，还需要更多的数学解。
For even more efficiency, you could only check those solutions where d >= c >= b >= a. That's because you could then build up all the solutions from those combinations into permutations (with potential duplicate removal where the values of two or more of a, b, c, or d are identical).
更效率,你只能检查这些解决方案在d > = c > b = > =一个。那是因为你可以建立所有的解决方案组合成排列(与潜在重复删除的两个或两个以上的值,b,c,d是相同的)。
In addition, the body of the d loop doesn't need to check every value of d, just the last possible one.
此外，d循环的主体不需要检查d的每个值，只需要检查最后一个可能的值。
Getting the results for 1,000,000 in that case takes under ten seconds rather than over six minutes:
在这种情况下，得到100万的结果需要不到10秒，而不是超过6分钟:
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
That code follows:
这段代码:
#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;
}
And, as per a suggestion by DSM, the d loop can disappear altogether (since there's only one possible value of d (discounting negative numbers) and it can be calculated), which brings the one million case down to two seconds for me, and the ten million case to a far more manageable 68 seconds.
DSM,正如每一个建议的d环可以完全消失(因为只有一个可能值的d(打折负数),它可以计算),将一百万例下降到两秒钟对我来说,和一千万年更可控的68秒。
That version is as follows:
该版本如下:
#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): All timings are done with the inner printf commented out so that I/O doesn't skew the figures.
(a):所有的计时都是用内printf注释掉的，这样I/O就不会扭曲数字。
#3
2
It seems as though all integers can be made by such a combination:
似乎所有的整数都可以由这样的组合组成:
0 = 0^2 + 0^2 + 0^2 + 0^2
1 = 1^2 + 0^2 + 0^2 + 0^2
2 = 1^2 + 1^2 + 0^2 + 0^2
3 = 1^2 + 1^2 + 1^2 + 0^2
4 = 2^2 + 0^2 + 0^2 + 0^2, 1^2 + 1^2 + 1^2 + 1^2 + 1^2
5 = 2^2 + 1^2 + 0^2 + 0^2
6 = 2^2 + 1^2 + 1^2 + 0^2
7 = 2^2 + 1^2 + 1^2 + 1^2
8 = 2^2 + 2^2 + 0^2 + 0^2
9 = 3^2 + 0^2 + 0^2 + 0^2, 2^2 + 2^2 + 1^2 + 0^2
10 = 3^2 + 1^2 + 0^2 + 0^2, 2^2 + 2^2 + 1^2 + 1^2
11 = 3^2 + 1^2 + 1^2 + 0^2
12 = 3^2 + 1^2 + 1^2 + 1^2, 2^2 + 2^2 + 2^2 + 0^2
.
.
.
and so forth
等等
As I did some initial working in my head, I thought that it would be only the perfect squares that had more than 1 possible solution. However after listing them out it seems to me there is no obvious order to them. However, I thought of an algorithm I think is most appropriate for this situation:
当我在头脑中做了一些初步的工作时，我认为这只是一个完美的正方形，有超过1个可能的解决方案。然而，在列出它们之后，在我看来它们并没有明显的顺序。然而，我想到了一种最适合这种情况的算法:
The important thing is to use a 4-tuple (a, b, c, d). In any given 4-tuple which is a solution to a^2 + b^2 + c^2 + d^2 = n, we will set ourselves a constraint that a is always the largest of the 4, b is next, and so on and so forth like:
最重要的是使用一个4-tuple(a,b,c,d)。在任何给定4-tuple ^ 2 +的解决方案b d ^ ^ 2 + c ^ 2 + 2 = n,我们将一个约束,总是最大的4 b是接下来,等等等等:
a >= b >= c >= d
Also note that a^2 cannot be less than n/4, otherwise the sum of the squares will have to be less than n.
还要注意,^ 2不能小于n / 4,否则的平方和小于n。
Then the algorithm is:
的算法是:
1a. Obtain floor(square_root(n)) # this is the maximum value of a - call it max_a
1b. Obtain the first value of a such that a^2 >= n/4 - call it min_a
2. For a in a range (min_a, max_a)
At this point we have selected a particular a, and are now looking at bridging the gap from a^2 to n - i.e. (n - a^2)
在这一点上我们选择了一个特定的,现在看着弥合差距从^ 2到n——即(n - ^ 2)
3. Repeat steps 1a through 2 to select a value of b. This time instead of finding
floor(square_root(n)) we find floor(square_root(n - a^2))
and so on and so forth. So the entire algorithm would look something like:
诸如此类。整个算法看起来是这样的
1a. Obtain floor(square_root(n)) # this is the maximum value of a - call it max_a
1b. Obtain the first value of a such that a^2 >= n/4 - call it min_a
2. For a in a range (min_a, max_a)
3a. Obtain floor(square_root(n - a^2))
3b. Obtain the first value of b such that b^2 >= (n - a^2)/3
4. For b in a range (min_b, max_b)
5a. Obtain floor(square_root(n - a^2 - b^2))
5b. Obtain the first value of b such that b^2 >= (n - a^2 - b^2)/2
6. For c in a range (min_c, max_c)
7. We now look at (n - a^2 - b^2 - c^2). If its square root is an integer, this is d.
Otherwise, this tuple will not form a solution
At steps 3b and 5b I use (n - a^2)/3, (n - a^2 - b^2)/2. We divide by 3 or 2, respectively, because of the number of values in the tuple not yet 'fixed'.
在步骤3 b和5 b我使用(n - ^ 2)/ 3 b(n - 2 ^ - ^ 2)/ 2。我们分别除以3或2，因为元组中值的个数还没有“固定”。
An example:
一个例子:
doing this on n = 12:
在n = 12时这样做:
1a. max_a = 3
1b. min_a = 2
2. for a in range(2, 3):
use a = 2
3a. we now look at (12 - 2^2) = 8
max_b = 2
3b. min_b = 2
4. b must be 2
5a. we now look at (12 - 2^2 - 2^2) = 4
max_c = 2
5b. min_c = 2
6. c must be 2
7. (n - a^2 - b^2 - c^2) = 0, hence d = 0
so a possible tuple is (2, 2, 2, 0)
2. use a = 3
3a. we now look at (12 - 3^2) = 3
max_b = 1
3b. min_b = 1
4. b must be 1
5a. we now look at (12 - 3^2 - 1^2) = 2
max_c = 1
5b. min_c = 1
6. c must be 1
7. (n - a^2 - b^2 - c^2) = 1, hence d = 1
so a possible tuple is (3, 1, 1, 1)
These are the only two possible tuples - hey presto!
这是两个可能的元组——嘿，马上!
#4
0
nebffa has a great answer. one suggestion:
nebffa有一个很好的答案。一个建议:
step 3a: max_b = min(a, floor(square_root(n - a^2))) // since b <= a
max_c and max_d can be improved in the same way too.
max_c和max_d也可以通过同样的方式进行改进。
Here is another try:
这是另一个尝试:
1. generate array S: {0, 1, 2^2, 3^2,.... nr^2} where nr = floor(square_root(N)).
now the problem is to find 4 numbers from the array that sum(a, b,c,d) = N;
现在的问题是从数组中找出4个数字(a, b,c,d) = N;
2. according to neffa's post (step 1a & 1b), a (which is the largest among all 4 numbers) is between [nr/2 .. nr].
We can loop a from nr down to nr/2 and calculate r = N - S[a]; now the question is to find 3 numbers from S the sum(b,c,d) = r = N -S[a];
我们可以从nr循环到nr/2，计算r = N - S[a];现在问题是要从S中找出3个数字(b,c,d) = r = N -S[a];
here is code:
下面是代码:
nr = square_root(N);
S = {0, 1, 2^2, 3^2, 4^2,.... nr^2};
for (a = nr; a >= nr/2; a--)
{
r = N - S[a];
// it is now a 3SUM problem
for(b = a; b >= 0; b--)
{
r1 = r - S[b];
if (r1 < 0)
continue;
if (r1 > N/2) // because (a^2 + b^2) >= (c^2 + d^2)
break;
for (c = 0, d = b; c <= d;)
{
sum = S[c] + S[d];
if (sum == r1)
{
print a, b, c, d;
c++; d--;
}
else if (sum < r1)
c++;
else
d--;
}
}
}
runtime is O(sqare_root(N)^3).
运行时是O(sqare_root(N)^ 3)。
Here is the test result running java on my VM (time in milliseconds, result# is total num of valid combination, time 1 with printout, time2 without printout):
这是在我的VM上运行java的测试结果(时间以毫秒为单位，结果#是有效组合的总num，时间1有printout，时间2没有printout):
N result# time1 time2
----------- -------- -------- -----------
1,000,000 1302 859 281
10,000,000 6262 16109 7938
100,000,000 30912 442469 344359