Java 更有效的解决方案：Project Euler #2：偶数斐波那契数
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/24483199/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
More efficient solution: Project Euler #2: Even Fibonacci Numbers
提问by user262945
Problem:
问题：
Each new term in the Fibonacci sequence is generated by adding the previous two terms.
By starting with 1 and 2, the first 10 terms will be:
1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.
斐波那契数列中的每个新项都是通过将前两项相加而生成的。
从 1 和 2 开始，前 10 项将是：
1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...通过考虑 Fibonacci 数列中值不超过 400 万的项，找出偶数项的总和。
My code: (which works fine)
我的代码：（工作正常）
public static void main(String[] agrs){
int prevFirst=0;
int prevSecond=1;
int bound=4_000_000;
int evenSum=0;
boolean exceed=false; //when fib numbers > bound
while(!exceed){
int newFib=prevFirst + prevSecond;
prevFirst = prevSecond;
prevSecond = newFib;
if(newFib > bound){
exceed=true;
break;
}
if(newFib % 2 == 0){
evenSum += newFib;
}
}
System.out.println(evenSum);
}
I'm looking for a more efficient algorithm to do this question. Any hints?
我正在寻找一种更有效的算法来解决这个问题。任何提示？
采纳答案by Willem Van Onsem
When taking the following rules into account:
在考虑以下规则时：
even + even = even
even + odd = odd
odd + even = odd
odd + odd = even
偶数 + 偶数 = 偶数
偶数 + 奇数 = 奇数
奇数 + 偶数 = 奇数
奇数 + 奇数 = 偶数
The parity of the first Fibonacci numbers is:
第一个斐波那契数的奇偶性是：
o o e o o e o o e ...
呜呜呜……
Thus basically, you simply need to do steps of three. Which is:
因此，基本上，您只需要执行三个步骤。这是：
(1,1,2)
(3,5,8)
(13,21,34)
Given (a,b,c)this is (b+c,b+2*c,2*b+3*c).
鉴于(a,b,c)这是(b+c,b+2*c,2*b+3*c).
This means we only need to store the two last numbers, and calculate given (a,b), (a+2*b,2*a+3*b).
这意味着我们只需要存储最后两个数字，并计算给定的(a,b), (a+2*b,2*a+3*b)。
Thus (1,2) -> (5,8) -> (21,34) -> ...and always return the last one.
因此(1,2) -> (5,8) -> (21,34) -> ...并且总是返回最后一个。
This will work faster than a "filter"-approach because that uses the if-statement which reduces pipelining.
这将比“过滤器”方法更快地工作，因为它使用了减少流水线操作的 if 语句。
The resulting code is:
结果代码是：
int b = 1;
int c = 2, d;
long sum = 0;
while(c < 4000000) {
sum += c;
d = b+(c<<0x01);
c = d+b+c;
b = d;
}
System.out.println(sum);
Or the jdoodle(with benchmarking, takes 5 microseconds with cold start, and on average 50 nanoseconds, based on the average of 1M times). Of course the number of instructions in the loop is larger. But the loop is repeated one third of the times.
或者jdoodle（基于基准测试，冷启动需要 5 微秒，平均 50 纳秒，基于 1M 次的平均值）。当然，循环中的指令数量更大。但是循环重复了三分之一。
回答by alfasin
You can't improve it much more, any improvement that you'll do will be negligible as well as depended on the OS you're running on.
您无法对其进行更多改进，您所做的任何改进都可以忽略不计，并且取决于您正在运行的操作系统。
Example:
Running your code in a loop 1M timeson my Mac too 73-75ms (ran it a few times).
Changing the condition:
示例：在我的 Mac 上
循环运行代码 100 万次也需要 73-75 毫秒（运行几次）。
改变条件：
if(newFib % 2 == 0){
to:
到：
if((newFib & 1) == 0){
and running it again a few times I got 51-54ms.
再运行几次，我得到了 51-54 毫秒。
- If you'll run the same thing on a different OS you might (and probably will) get different results.
- even if we'll consider the above as an improvement, divide ~20ms in 1M and the "improvement" that you'll get for a single run is meaningless (~20 nanos).
- 如果您将在不同的操作系统上运行相同的东西，您可能（并且可能会）得到不同的结果。
- 即使我们将上述视为改进，在 1M 中划分约 20 毫秒，单次运行获得的“改进”也毫无意义（约 20 纳秒）。
回答by Spektre
as I mentioned in my comment there is really no need to further improvement. I did some measurements
正如我在评论中提到的，真的没有必要进一步改进。我做了一些测量
- looped 1000000 times the whole thing
- measure time in [ms]
- ms / 1000000 = ns
so single pass times [ns] are these:
- [176 ns] - exploit that even numbers are every third
- [179 ns] - &1 instead of %2
- [169 ns] - &1 instead of %2 and eliminated if by -,^,&
[edit1] new code - [105 ns] - exploit that even numbers are every third + derived double iteration of fibonaci [edit2] new code
- [76 ns] - decreased operand count to lower overhead and heap trashing
the last one clearly wins on mine machine (although I would expect that the first one will be best)
- all was tested on Win7 x64 AMD A8-5500 3.2GHz
App with no threads 32-bit compiler BDS2006 Trubo C++
1,2 are nicely mentioned in Answers here already so I comment just 3:
s+=a&(-((a^1)&1));(a^1) negates lovest bit
- ((a^1)&1) is 1 for even and 0 for odd a
- -((a^1)&1)) is -1 for even and 0 for odd a
- -1 is 0xFFFFFFFF so anding number by it will not change it
- 0 is 0x00000000 so anding number by it will be 0
- hence no need for if
- also instead of xor(^) you can use negation(!) but that is much sloweron mine machine
- 整个事情循环了 1000000 次
- 以 [ms] 为单位测量时间
- 毫秒 / 1000000 = 纳秒
所以单次通过时间 [ns] 是这些：
- [176 ns] - 利用偶数是三分之一
- [179 ns] - &1 而不是 %2
- [169 ns] - &1 而不是 %2 并消除 -,^,&
[edit1] 新代码 - [105 ns] - 利用偶数是斐波那契数的三分之一 + 派生双迭代 [edit2] 新代码
- [76 ns] - 减少操作数以降低开销和堆垃圾
最后一个显然在我的机器上获胜（尽管我希望第一个是最好的）
- 全部在 Win7 x64 AMD A8-5500 3.2GHz 上测试
无线程应用程序 32 位编译器 BDS2006 Trubo C++
1,2 在这里的答案中已经很好地提到了，所以我只评论 3：
s+=a&(-((a^1)&1));(a^1) 否定最喜欢的位
- ((a^1)&1) 为偶数为 1，为奇数为0
- -((a^1)&1)) 偶数为 -1，奇数为0
- -1 是 0xFFFFFFFF 所以它的数字不会改变它
- 0 是 0x00000000 所以它的数字将是 0
- 因此不需要如果
- 也可以使用否定（！）代替异或（^），但这在我的机器上要慢得多
OK here is the code (do not read further if you want to code it your self):
好的，这是代码（如果您想自己编写代码，请不要进一步阅读）：
//---------------------------------------------------------------------------
int euler002()
{
// Each new term in the Fibonacci sequence is generated by adding the previous two terms.
// By starting with 1 and 2, the first 10 terms will be: 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
// By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.
int a,a0=0,a1=1,s=0,N=4000000;
/*
//1. [176 ns]
a=a0+a1; a0=a1; a1=a; // odd
a=a0+a1; a0=a1; a1=a; // even
for (;a<N;)
{
s+=a;
a=a0+a1; a0=a1; a1=a; // odd
a=a0+a1; a0=a1; a1=a; // odd
a=a0+a1; a0=a1; a1=a; // even
}
//2. [179 ns]
for (;;)
{
a=a0+a1; a0=a1; a1=a;
if (a>=N) break;
if ((a&1)==0) s+=a;
}
//3. [169 ns]
for (;;)
{
a=a0+a1; a0=a1; a1=a;
if (a>=N) break;
s+=a&(-((a^1)&1));
}
//4. [105 ns] // [edit1]
a0+=a1; a1+=a0; a=a1; // 2x
for (;a<N;)
{
s+=a; a0+=a1; a1+=a0; // 2x
a=a0+a1; a0=a1; a1=a; // 1x
}
*/
//5. [76 ns] //[ edit2]
a0+=a1; a1+=a0; // 2x
for (;a1<N;)
{
s+=a1; a0+=a1; a1+=a0; // 2x
a=a0; a0=a1; a1+=a; // 1x
}
return s;
}
//---------------------------------------------------------------------------
[edit1] faster code add
[edit1] 更快的代码添加
- CommuSoft suggested to iterate more then 1 number per iteration of fibonaci to minimize operations.
- nice idea but code in his comment does not give correct answers
- I tweaked a little mine so here is the result:
- [105 ns] - exploit that even numbers are every third + derived double iteration of fibonaci
- this is almost twice the speedup of 1. from which it is derived
- look for [edit1] in code or look for //4.
- CommuSoft 建议每次斐波那契迭代迭代超过 1 个数字以最小化操作。
- 好主意，但他评论中的代码没有给出正确答案
- 我调整了一点我的，所以这是结果：
- [105 ns] - 利用偶数是斐波那契数的三分之一 + 衍生的双迭代
- 这几乎是 1 的两倍。从中得出它
- 在代码中查找 [edit1] 或查找 //4。
[edit2] even faster code add- just reorder of some variable and operation use for more speed - [76 ns] decreased operand count to lower overhead and heap trashing
[edit2] 甚至更快的代码添加- 只需重新排序一些变量和操作使用以提高速度 - [76 ns] 减少操作数以降低开销和堆垃圾
回答by greybeard
assuming consecutive Fibonacci numbers
假设连续的斐波那契数
a, b,
c = a + b,
d = a + 2b,
e = 2a + 3b,
f = 3a + 5b,
g = 5a + 8b = a + 4(a + 2b) = a + 4d,
it would seem more efficient to use
ef0= 0, ef1= 2, efn= efn-2+ 4 efn-1
使用
ef 0= 0, ef 1= 2, ef n= ef n-2+ 4 ef n-1似乎更有效
回答by M. Paranhos
The answer for project Euler problem 2 is(in Java):
项目欧拉问题 2 的答案是（在 Java 中）：
int x = 0;
int y = 1;
int z = x + y;
int sumeven = 0;
while(z < 4000000){
x = y;
y = z;
z = x + y;
if(z % 2 == 0){
sumeven += z; /// OR sumeven = sumeven + z
}
}
System.out.printf("sum of the even-valued terms: %d \n", sumeven);
This is the easiest answer.
这是最简单的答案。
回答by FReeze FRancis
F(n) be the nth Fibonnaci number i.e F(n)=F(n-1)+F(n-2)
Lets say that F(n) is even, then
F(n) = F(n-1) + F(n-2) = F(n-2) + F(n-3) + F(n-2)
F(n) = 2F(n-2) + F(n-3)
--This proves the point that every third term is even (if F(n-3) is even, then F(n) must be even too)
F(n) = 2[F(n-3) + F(n-4)] + F(n-3)
= 3F(n-3) + 2F(n-4)
= 3F(n-3) + 2F(n-5) + 2F(n-6)
F(n) 是第 n 个斐波那契数，即 F(n)=F(n-1)+F(n-2)
假设 F(n) 是偶数，那么
F(n) = F(n-1) + F(n-2) = F(n-2) + F(n-3) + F(n-2)
F(n) = 2F(n-2) + F(n-3) --这
证明每第三项是偶数的点（如果 F(n-3) 是偶数，那么 F(n) 也必须是偶数）
F(n) = 2[F(n-3) + F(n-4)] + F(n-3)
= 3F(n-3) + 2F(n-4)
= 3F(n-3) + 2F(n-5) + 2F(n-6)
From eq.1:
F(n-3) = 2F(n-5) + F(n-6)
2F(n-5) = F(n-3) - F(n-6)
F(n) = 3F(n-3) + [F(n-3) - F(n-6)] + 2F(n-6)
= 4F(n-3) + F(n-6)
If the sequence of even numbers consists of every third number (n, n-3, n-6, ...)
Even Fibonacci sequence:
从方程 1：
F(n-3) = 2F(n-5) + F(n-6)
2F(n-5) = F(n-3) - F(n-6)
F(n) = 3F(n-3) + [F(n-3) - F(n-6)] + 2F(n-6)
= 4F(n-3) + F(n-6)
如果偶数序列由每三个数字 (n, n-3, n-6, ...)
甚至斐波那契数列：
E(k) = 4E(k-1) + E(k-2)
E(k) = 4E(k-1) + E(k-2)
Fib 序列 F= {0,1,1,2,3,5,8.....}
偶数 Fib 序列 E={0,2,8,....}
代码：
public static long findEvenFibSum(long n){
long term1=0;
long term2=2;
long curr=0;
long sum=term1+term2;
while((curr=(4*term2+term1))<=n){
sum+=curr;
term1=term2;
term2=curr;
}
return sum;
}
回答by Shree Prakash
if you check Fibonacci series, for even numbers 2 8 34 144 610 you can see that there is a fantastic relation between even numbers, for example:
如果您查看斐波那契数列，对于偶数 2 8 34 144 610，您会发现偶数之间存在奇妙的关系，例如：
34 = 4*8 + 2,
144 = 34*4 + 8,
610 = 144*4 + 34;
this means that next even in Fibonacci can be expressed like below
这意味着即使在斐波那契中也可以如下表示
Even(n)=4*Even(n-1)+E(n-2);
in Java
在 Java 中
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int t = in.nextInt();
for(int a0 = 0; a0 < t; a0++){
long n = in.nextLong();
long a=2;
long b=8;
long c=0;
long sum=10;
while(b<n)
{
sum +=c;
c=b*4+a;
a=b;
b=c;
}
System.out.println(sum);
}
}
