Java 8 Lambda expressions for solving fibonacci (n

Question

I am a beginner in using Lambda expression feature in Java 8. Lambda expressions are pretty well useful in solving programs like Prime number check, factorial etc.

However can they be utilized effectively in solving problems like Fibonacci where the current value depends on sum of previous two values. I have pretty well solved prime number check problem effectively using Lambda expressions. The code for the same is given below.

boolean checkPrime=n>1 && LongStream.range(2, (long) Math.sqrt(n)).parallel().noneMatch(e->(n)%e==0);

In the above code in the noneMatch method we are evaluating with the current value(e) in the range. But for the Fibonacci problem, we requires previous two values.

How can we make it happen?

Answer 1

The simplest solution is to use a stream of Pairs:

Stream.iterate(new long[]{ 1, 1 }, p->new long[]{ p[1], p[0]+p[1] })
      .limit(92).forEach(p->System.out.println(p[0]));

Due to the lack of a standard pair type, it uses a two-element array. Further, I use .limit(92) as we can’t evaluate more elements using long values. But it’s easy to adapt to BigInteger:

Stream.iterate(new BigInteger[]{ BigInteger.ONE, BigInteger.ONE },
               p->new BigInteger[]{ p[1], p[0].add(p[1]) })
      .forEach(p->System.out.println(p[0]));

That’ll run until you haven’t enough memory to represent the next value.

BTW, to get the nth element from the stream:

Stream.iterate(new long[]{1, 1}, p -> new long[]{p[1], p[0] + p[1]})
    .limit(91).skip(90).findFirst().get()[1];

Answer 2

To get Nth fibonacci element (using reduction):

Stream.iterate(new long[] {1, 1}, f -> new long[] {f[1], f[0] + f[1]})
    .limit(n)
    .reduce((a, b) -> b)
    .get()[0];

Answer 3

solving fibonacci (non recursive way)

This is not going to happen with your approach

The generation of Fibonacci numbers based on the previous two numbers is based on the previous two numbers, i.e. it's a recursive algorithm, even if you implement it without recursion but in a loop.

There's other ways based on the matrix exponential so you can calculate the n'th fibonacci number without calculating the n-1 previous numbers, but for your problem (calculating the series), this doesn't make sense.

So, to answer your question in the end, namely how can I use Lambda expressions on the two previous elements?: have a list of tuples, each containing two consecutive numbers, and iterate over that, adding a new tuple every step.

Answer 4

If you want a non recursive implementation to find the n-th number of Fibonacci sequence you can use the formula:

Un = ( (1+sqrt(5))^n - (1-sqrt(5))^n ) / (2^n * sqrt(5))

long fibonacci(int n) {
    return (long) ((Math.pow(1 + Math.sqrt(5), n) - Math.pow(1 - Math.sqrt(5), n)) /
        (Math.pow(2, n) * Math.sqrt(5)));
}