Fibonacci sequence is defined as a sequence of integers starting with 1 and 1, where each subsequent value is the sum of the preceding two I.e.

f(0) = 1
f(1) = 1
f(n) = f(n-1)   f(n-2) where n>=2

My goal is to calculate the sum of the first 100 even-values Fibonacci numbers.

So far I've found this code which works perfectly to calculate the sum of even numbers to 4million , however I'm unable to find edit the code so that it stops at the sum of the 100th value, rather than reaching 4million.

public class Improvement {
  public static int Fibonacci(int j) {
      
      /**
       * 
       * Recursive took a long time so continued with iterative 
       * 
       * Complexity is n squared.. try to improve to just n
       * 
       */
            int tmp;
            int a = 2;
            int b = 1;
            int total = 0;

            do {
              if(isEven(a)) total  =a;
              tmp = a   b;
              b = a;
              a = tmp;      
            } while (a < j);

            return total;

          }

          private static boolean isEven(int a) {
            return (a & 1) == 0;
          }

          public static void main(String[] args) {
            // Notice there is no more loop here
            System.out.println(Fibonacci(4_000_000));
          }
        }

Just to show the console from @mr1554 code answer, the first 100 even values are shown and then the sum of all is 4850741640 as can be seen below:

Any help is appreciated, thanks!

CodePudding user response：

You need to use BigInteger because long easily overflows as Fibonacci's scales quite easily. BigInteger is also tricky to check whether is an odd or even number, but you can use BigInteger::testBit returning boolean as explained in this answer.

Here is some complete code:

BigInteger fibonacciSum(int count, boolean isOdd) {
    int i = 0;
    BigInteger sum = BigInteger.ZERO;
    BigInteger current = BigInteger.ONE;
    BigInteger next = BigInteger.ONE;
    BigInteger temp;

    while (i < count) {
        temp = current;
        current = current.add(next);
        next = temp;

        if ((current.testBit(0) && isOdd) || ((!current.testBit(0) && !isOdd))) {
            sum = sum.add(current);
            i  ;
        }
    }

    return sum;
}

Or you can have some fun with Stream API:

BigInteger fibonacciSum(int count, boolean isOdd) {
    final BigInteger[] firstSecond = new BigInteger[] {BigInteger.ONE, BigInteger.ONE};
    return Stream.iterate(
            firstSecond, 
            num -> new BigInteger[] { num[1], num[0].add(num[1]) })
        .filter(pair -> 
            (pair[1].testBit(0) && isOdd) || 
            (!pair[1].testBit(0) && !isOdd))
        .limit(count)
        .map(pair -> pair[1])
        .reduce(BigInteger.ZERO, BigInteger::add);
}

In any way, don't forget to test it out:

@Test
void test() {
    assertThat(
        fibonacciSum(100, false),
        is(new BigInteger("290905784918002003245752779317049533129517076702883498623284700")));
}

CodePudding user response：

as I figured, you want a program to sum 100 first even values of the Fibonacci series.

here is a sample code, when you run the program it will ask you to determine the number of the even values, you want 100 value e.g, type 100 in consul:

public static void main(String[] args) {
    int firstNumber = 0;
    int secondNumber = 2;
    System.out.print("Enter the number of odd elements of the Fibonacci Series to sum : ");
    Scanner scan = new Scanner(System.in);
    int elementCount = scan.nextInt(); // number of even values you want
    System.out.print(firstNumber   ", ");
    System.out.print(secondNumber   ", ");


    long sum = 2;
    for (int i = 2; i < elementCount; i  ) {
        int nextNumber = firstNumber   secondNumber;
        System.out.print(nextNumber   ", ");

        sum  = (nextNumber);

        firstNumber = secondNumber;
        secondNumber = nextNumber;

    }
    System.out.print("...");

    System.out.println("\n"   "the sum of "   elementCount   " values of fibonacci series is: "   sum);
}

CodePudding user response：

You said.

My goal is to calculate the sum of the first 100 even-values Fibonacci numbers.

That number gets very large very quickly. You need to:

• use BigInteger
• use the mod function to determine if even

For this I could have started from (1,1) but it's only one term so ...

BigInteger m = BigInteger.ZERO;
BigInteger n = BigInteger.ONE;

BigInteger sumOfEven= BigInteger.ZERO;
int count = 0;
BigInteger t;
while( count < 100) {
    t = n.add(m);
    // check if even
    if (t.mod(BigInteger.TWO).equals(BigInteger.ZERO)) {
        sumOfEven = sumOfEven.add(t);
        count  ;
    }
    n = m;
    m = t;
}
System.out.println(sumOfEven);

Prints

290905784918002003245752779317049533129517076702883498623284700

If, on the other hand, from your comment.

My aim is to calculate the sum of the first 100 even numbers

Then you can do that like so

sumFirstNeven = (((2N   2)N)/2 = (N 1)N

so (101)100 = 10100 and the complexity is O(1)