Проект Эйлера 2: сумма четных чисел Фибоначчи

Question

Я пытаюсь решить Project Euler проблема 2 в Java:

public class Euler2 {

public static long GenerateFibonacci(int term) {

    long sum = 0;
    long fib = 0;
    long f1 = 0;
    long f2 = 1;
    if (term <=1) return term;
    for (int i = 1; i <= term; i++) {
        fib = f1 + f2;
        f1 = f2;
        f2 = fib;
        if(fib %2 ==0)
            sum += fib;         
    }
    return sum;

}

    /**
     * @param args
     */
    public static void main(String[] args) {

        int n = 100;
        long result = GenerateFibonacci(n);
        System.out.println("The sum of the even Fibonacci numbers is: "+result);
    }
}

Когда n мало, я получаю правильный ответ, но для больших значений яполучить неправильный результат.В чем здесь проблема?

Answer 1

int ограничен 32-битной точностью, long - 64-битной.

Когда вы превышаете ограничение, добавляя числа, результат которых больше, чем битовый предел, они "переворачиваются"и вы потеряете наиболее значимые биты в результате сложения - по сути, они «округлены» до 32/64 бит.

Вот пример пролонгации:

int i = Integer.MAX_VALUE; // 2147483647
i++; // -2147483648

Примерноговоря, каждое число Фибоначчи в два раза превосходит предыдущее, поэтому, грубо говоря, вы можете обработать его только в порядке 64 итераций, используя long как общее значение.

Answer 2

Самое большое длинное значение в Java - 9223372036854775807. При добавлении 1 к этому значению получается -9223372036854775807, поскольку целочисленные значения в большинстве языков программирования берутся из конечного набора значений, а когда вы достигаете наибольшего значения и добавляете одно, последовательность «оборачивает» вокруг "к началу.

Если вам нужно выйти за пределы этого диапазона, в котором вы хотите получить сотое число Фибоначчи, используйте BigInteger.

Answer 3

Вы можете улучшить эффективность 'GenerateFibonacci' с помощью следующего кода. Это должен быть комментарий, но я не могу отформатировать код в комментарии, я делаю это в ответе

public class FibUtil {

//Constants used in equation to calculate nth fib term
private static final double fibA=1/Math.sqrt(5);
private static final double fibB=(1+Math.sqrt(5))/2;
private static final double fibC=(1-Math.sqrt(5))/2;

public static double getNthFibTerm(long n){
    return fibA*(Math.pow(fibB, n)-Math.pow(fibC, n));
}

}

Далее, основываясь на постановке задачи euler 2, вы можете просто добавить только n-е слагаемые, кратные 3. Я оставляю вам «почему».

Answer 4

Вам нужно использовать BigInteger, вы также можете использовать тот факт, что каждое третье число Фибоначчи является четным.

public static BigInteger sumOfEvenFibonacci(int term) {
    BigInteger sum = BigInteger.ZERO;
    BigInteger f1 = BigInteger.ONE;
    BigInteger f2 = BigInteger.ONE;
    for (int i = 1; i <= term; i+=3) {
        BigInteger fib = f1.add(f2);
        sum = sum.add(fib);
        f1 = f2.add(fib);
        f2 = fib.add(f1);
    }
    return sum;
}

System.out.println(sumOfEvenFibonacci(100));

печать

1213946614199987541226

Answer 5

Сумма больше Long.MAX_VALUE.Вы правы (в своем комментарии к @Bohemian), что n меньше этого предела, но довольно удивительно, как быстро эта простая серия может расти.Например, 100-е число Фибоначчи - 354224848179261915075. Сумма первых 100 - это 20-значное число, просто чтобы дать вам представление о шкале, с которой вы имеете дело.

Answer 6

/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */

package evenfibonaccisum;

import java.math.BigInteger;

/**
 *
 * @author blades of Aragon
 */
public class EvenFibonacciSum {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        // TODO code application logic here

        long a=0;
      long b=1;
       long fib=1;
        int i=10;
        long sum=0;
        while(fib<=4000000){
        fib=a+b;
        a=b;
        b=fib;
           if(fib>=4000000){
           break ;
           }
           else{

               if(fib%2==0){

               sum=sum+fib;

               }


           }

        }
         System.out.println("sum of even Fibonacci "+sum);  






        }



    }