Java 8 Lambda expressions for solving fibonacci (non recursive way)

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?

Dignify

Stream.iterate(Fibonacci.SEED, Fibonacci::next).limit(MAX_NUMS).forEach(System.out::println) Complete code example that shows how to generate Fibonacci using Java 8. Last one. – Swanherd

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.

By the way, 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];

Whoops

You say get the nth element but don't use n. Can you update please? – Feather

It should be obvious that the example is getting the 91th element from the stream, so n is 91 in the example. – Whoops

Answer 2

To get the 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];

Here is what is going on:

• Stream::iterate - is producing pairs of numbers, each containing two consecutive elements of fibonacci. We have to use pairs, because we can access only the last element via "iterate", not two or more previous elements, so to generate a new pair, we get the last pair, which already contains two previous elements of fibonacci, and produce the next pair. And to get the Nth fibonacci element, we just need to get the left value from the Nth pair.

• .limit(n) - to keep the first N pairs, and exclude the rest.

• .reduce((a, b) -> b) - to get the last pair from the stream of N pairs from previous step.

• .get()[0] - extract fibonacci element from the pair (left value of the pair)

Cecilius

please explain the iterate and reduce – Underbrush

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.

Loria

Answer 4

You can use a variable in your lambda expression to temporarily store the previous element, which is needed to calculate the next element in the fibonacci sequence.

public class FibonacciGenerator {

        private long prev=0; 

        public void printSequence(int elements) {

            LongStream.iterate(1, n -> {n+=prev; prev=n-prev; return n;}).           
            limit(elements).forEach(System.out::println);
        }
    }

Normally the method and the field would rather be declared as static but I wanted to show that instance fields can be used as well.

Please note that you could not use a local variable ( declared in a method or passed to a method ) instead of a field, for such variables need to be final in order to use them in lambdas. For our purpose we needed a mutable variable to store the different values during the iteration.

Maelstrom

Answer 5

I know its a old question, but I feel worth to put some more ways to acheive using Pair<> and I came up with 2 ways to achieve using Stream API.

//calculate Fibonacci at given place
public static long fibonacciAt(int place) {
    Pair<Integer, Integer> seed = new Pair<>(0, 1);
    //return Stream.iterate(seed, feed -> new Pair<>(feed.getValue(), feed.getValue() + feed.getKey())).limit(place).reduce((integerIntegerPair, integerIntegerPair2) -> integerIntegerPair2).orElse(seed).getValue();
    return Stream.iterate(seed, feed -> new Pair<>(feed.getValue(), feed.getValue() + feed.getKey())).limit(place).skip(place-1).findFirst().orElse(seed).getValue();
}

The commented return statement is also works fine which is using reduce.

The later return statement is by skipping the number of pairs up to the place variable.(This is because we don't have findLast() method).

Navigator

Answer 6

You can consider the calculation of the n-th fibonacci number as a reduction with two previous elements instead of one which is typical.
Here is some code:

public static long fibonacciByStream(int n) {
    long[] results = IntStream.rangeClosed(3, n)
            .boxed()
            .reduce(new long[]{0, 1, 1},
                    (fib, i) -> {
                        fib[i % 3] = fib[(i - 2) % 3] + fib[(i - 1) % 3];
                        return fib;
                    },
                    (a, b) -> null);
    return results[n % 3];
}

However, this solution looks simpler without any stream:

public static long fibonacciByLoop(int n) {
    long[] fib = new long[]{0, 1, 1};
    for (int i = 3; i <= n; i++) {
        fib[i % 3] = fib[(i - 2) % 3] + fib[(i - 1) % 3];
    }
    return fib[n % 3];
}

Remarks:

• I consider 0 as the 0th fibonacci number because it makes the code simpler.
• I used an array with three elements instead of two because it is easier to understand.
• I used "(a, b) -> null" as combiner because it is not used in a sequential stream.
• I omitted the check whether n is not negative.

Aloke

Answer 7

Using Stream.generat() we can do as follows:

     int[] fie ={0,1};
     Stream.generate(() -> {
        int r = fie[1];
        int f3 = fie[0] + fie[1];
        fie[0] = fie[1];
        fie[1] = f3;
        System.out.println(r);
        return r;
    }).limit(40)
      .collect((Collectors.toList()));

Disconsider

As it’s currently written, your answer is unclear. Please edit to add additional details that will help others understand how this addresses the question asked. You can find more information on how to write good answers in the help center. – Boatswain

Answer 8

Its very easy solution...

static int prev = 0;

public static void main(String[] args) {

// Fibonacci series // Output : 0 1 1 2 3 5 8 13 21 34

    IntStream.iterate(1, n -> {
        n = n + prev;
        prev = n - prev;
        return n;
    }).limit(10).forEach(System.out::println);

Counterblast