Calculating Fibonacci numbers with Streams and BigInteger

Question

I have the following is code for calculating the Fibonacci number at position 10:

IntStream.range(1,10)
         .mapToObj(ignore ->     List.Of(BigInteger.One, BigInteger.One)
         .reduce(List.Of(BigInteger.One, BigInteger.One), (values,ignore) -> ???)
         .get(1)

How do I replace the question marks in the code?

I have to achieve it by using only functional programming.

Answer 1

The lambda you need is:

(values, ignore) -> List.of(values.get(1), values.get(0).add(values.get(1)))

which converts the list [a, b] to [b, a+b].

However, There are some compile errors in your code:

• It's List.of() not List.Of()
• It's BigInteger.ONE not BigInteger.One

And a logic error: The first fibonacci number is 0, not 1, so to return the nth fibonacci number by starting with IntStream.range(1, n), the accumulator must be List.of(BigInteger.ZERO, BigInteger.ONE), not List.of(BigInteger.ONE, BigInteger.ONE).

The full working code is then:

BigInteger fibonacci = IntStream.range(1, 10)
  .mapToObj(ignore -> List.of(BigInteger.ZERO))
  .reduce(
    List.of(BigInteger.ZERO, BigInteger.ONE),
    (values, ignore) -> List.of(values.get(1), values.get(0).add(values.get(1)))
  ).get(0);

which returns 34, which is the 10th fibonacci number.

---

Rather than use IntStream#range(), a simpler way is to use Stream#generate() to generate the starting list and apply limit(n), using the same lambda from above:

BigInteger fibonacci = Stream.generate(() -> List.of(BigInteger.ZERO, BigInteger.ONE))
  .limit(10)
  .reduce((values, ignore) -> List.of(values.get(1), values.get(0).add(values.get(1))))
  .get().get(0);

Also returning 34.

Answer 2

If you are going to utilize this code for relatively small input numbers like 10, usage of BigInteger doesn't seem to be justifiable.

Otherwise, creating a new list for every member of the sequence is harmful performance-wise. It'll be better to create a list just once and then reuse it.

Unfortunately List.of() returns an immutable list, and in order to make it mutable you have wrap it with an ArrayList and clumsy code becomes more clumsy...

Instead, I advise to make use of an array as shown below, it'll make the code both more performant and easier to reason about.

public static BigInteger getFib(int num) {

    return Stream.iterate(new BigInteger[]{BigInteger.ZERO, BigInteger.ONE}, // the only array created in the stream
                          arr -> {arr[1] = arr[0].add(arr[1]);      // calculating the next member of the sequence
                                  arr[0] = arr[1].subtract(arr[0]); // calculating the previous member of the sequence
                                  return arr;})                     // returning the same array
            .limit(num - 1)
            .reduce((left, right) -> right)
            .map(arr -> arr[1])
            .orElse(BigInteger.ZERO);
}

main()

public static void main(String[] args) {
    List<BigInteger> result = // generating a list Fibonacci numbers for demo purposes
            IntStream.rangeClosed(1, 10)
                    .mapToObj(num -> getFib(num))
                    .collect(Collectors.toList());

    System.out.println(result);
}

Output

[0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

Answer 3

To calculate the Nth term of a fibonacci sequence you can do it like this. No list is involved as they are calculated on the fly and only the Nth one is printed or returned. This works by initializing an array a to [ 0, 1 ] and generating subsequent arrays of [ a[1], a[0] + a[1] ] such that a[0] is the used as the term in the series. Positions start at 1 which can be changed if insufficient.

• define the position (must be >= 1) or (i.e >= first position)
• using arrays iterate the series.
• skip the first position - 1 terms in the stream.
• then print the next one (or assign it)

int position = 10;
Stream.iterate(new BigInteger[] { BigInteger.ZERO, BigInteger.ONE },
        (a) -> new BigInteger[] { a[1], a[0].add(a[1]) })
        .skip(position-1).limit(1)
        .map(a->a[0]).forEach(System.out::println);
}

prints

34

to assign it change forEach to findFirst().get(). and assign to a BigInteger.

Here I've included that in a method.

public static BigInteger getFibTerm(int position) {
    if (position < 1) {
        throw new IllegalArgumentException("position must be >= 1");
    }
    return Stream.iterate(
            new BigInteger[] { BigInteger.ZERO, BigInteger.ONE },
            (a) -> new BigInteger[] { a[1], a[0].add(a[1]) })
            .skip(position - 1).limit(1).map(a -> a[0])
            .findFirst().get();
}