Home > Mobile >  Calculating Fibonacci numbers with Streams and BigInteger
Calculating Fibonacci numbers with Streams and BigInteger

Time:03-28

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.

CodePudding user response:

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 isn't performance-wise, it'll be better to create a list only ones 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 it.

public static BigInteger getFibb(int num) {
    if (num <= 0) {
        return BigInteger.ZERO;
    }
    if (num == 1 || num == 2) {
        return BigInteger.ONE;
    }

    return Stream.iterate(new BigInteger[]{BigInteger.ONE, BigInteger.ONE}, // the only array created by 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])
            .orElseThrow();
}

main()

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

    System.out.println(result);
}

Output

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

CodePudding user response:

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.

  • Related