How to implement a Spliterator for streaming Fibonacci numbers?

Question

I'm playing with Java 8 Spliterator and created one to stream Fibonacci numbers up to a given n. So for the Fibonacci series 0, 1, 1, 2, 3, 5, 8, ...

n fib(n)
-----------
-1 0
1 0
2 1
3 1
4 2

Following is my implementation which prints a bunch of 1 before running out of stack memory. Can you help me find the bug? (I think it's not advancing the currentIndex but I'm not sure what value to set it to).

Edit 1: If you decide to answer, please keep it relevant to the question. This question is not about efficient fibonacci number generation; it's about learning spliterators.

FibonacciSpliterator:

@RequiredArgsConstructor
public class FibonacciSpliterator implements Spliterator<FibonacciPair> {
 private int currentIndex = 3;
 private FibonacciPair pair = new FibonacciPair(0, 1);
 private final int n;
 @Override
 public boolean tryAdvance(Consumer<? super FibonacciPair> action) {
// System.out.println("tryAdvance called.");
// System.out.printf("tryAdvance: currentIndex = %d, n = %d, pair = %s.\n", currentIndex, n, pair);
 action.accept(pair);
 return n - currentIndex >= 2;
 }
 @Override
 public Spliterator<FibonacciPair> trySplit() {
// System.out.println("trySplit called.");
 FibonacciSpliterator fibonacciSpliterator = null;
 if (n - currentIndex >= 2) {
// System.out.printf("trySplit Begin: currentIndex = %d, n = %d, pair = %s.\n", currentIndex, n, pair);
 fibonacciSpliterator = new FibonacciSpliterator(n);
 long currentFib = pair.getMinusTwo() + pair.getMinusOne();
 long nextFib = pair.getMinusOne() + currentFib;
 fibonacciSpliterator.pair = new FibonacciPair(currentFib, nextFib);
 fibonacciSpliterator.currentIndex = currentIndex + 3;
// System.out.printf("trySplit End: currentIndex = %d, n = %d, pair = %s.\n", currentIndex, n, pair);
 }
 return fibonacciSpliterator;
 }
 @Override
 public long estimateSize() {
 return n - currentIndex;
 }
 @Override
 public int characteristics() {
 return ORDERED | IMMUTABLE | NONNULL;
 }
}

FibonacciPair:

@RequiredArgsConstructor
@Value
public class FibonacciPair {
 private final long minusOne;
 private final long minusTwo;
 @Override
 public String toString() {
 return String.format("%d %d ", minusOne, minusTwo);
 }
}

Usage:

Spliterator<FibonacciPair> spliterator = new FibonacciSpliterator(5);
StreamSupport.stream(spliterator, true)
 .forEachOrdered(System.out::print);

• OldCurmudgeon: This code does not compile - please post the correct code.
• Abhijit Sarkar: @OldCurmudgeon, what's the compilation error you're having? The code uses Lombok so you'll need that to make sense of the annotations.

Answer 1

Besides the fact that your code is incomplete, there are at least two errors in your tryAdvance method recognizable. First, you are not actually making any advance. You are not modifying any state of your spliterator. Second, you are unconditionally invoking the action’s accept method which is not matching the fact that you are returning a conditional value rather than true.

The purpose of tryAdvance is:

• as the name suggests, try to make an advance, i.e. calculate a next value
• if there is a next value, invoke action.accept with that value and return true
• otherwise just return false

Note further that your trySplit() does not look very convincing, I don’t even know where to start. You are better off, inheriting from AbstractSpliterator and not implementing a custom trySplit(). Your operation doesn’t benefit from parallel execution anyway. A stream constructed with that source could only gain an advantage from parallel execution if you chain it with quiet expensive per-element operations.

Answer 2

In general you don't need implementing the spliterator. If you really need a Spliterator object, you may use stream for this purpose:

Spliterator.OfLong spliterator = Stream
 .iterate(new long[] { 0, 1 },
 prev -> new long[] { prev[1], prev[0] + prev[1] })
 .mapToLong(pair -> pair[1]).spliterator();

Testing:

for(int i=0; i<20; i++)
 spliterator.tryAdvance((LongConsumer)System.out::println);

Please note that holding Fibonacci numbers in long variable is questionable: it overflows after Fibonacci number 92. So if you want to create spliterator which just iterates over first 92 Fibonacci numbers, I'd suggest to use predefined array for this purpose:

Spliterator.OfLong spliterator = Spliterators.spliterator(new long[] {
 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765,
 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309,
 3524578, 5702887, 9227465, 14930352, 24157817, 39088169, 63245986, 102334155, 165580141,
 267914296, 433494437, 701408733, 1134903170, 1836311903, 2971215073L, 4807526976L,
 7778742049L, 12586269025L, 20365011074L, 32951280099L, 53316291173L, 86267571272L, 139583862445L,
 225851433717L, 365435296162L, 591286729879L, 956722026041L, 1548008755920L, 2504730781961L,
 4052739537881L, 6557470319842L, 10610209857723L, 17167680177565L, 27777890035288L,
 44945570212853L, 72723460248141L, 117669030460994L, 190392490709135L, 308061521170129L,
 498454011879264L, 806515533049393L, 1304969544928657L, 2111485077978050L, 3416454622906707L,
 5527939700884757L, 8944394323791464L, 14472334024676221L, 23416728348467685L, 37889062373143906L,
 61305790721611591L, 99194853094755497L, 160500643816367088L, 259695496911122585L, 420196140727489673L,
 679891637638612258L, 1100087778366101931L, 1779979416004714189L, 2880067194370816120L,
 4660046610375530309L, 7540113804746346429L
}, Spliterator.ORDERED);

Array spliterator also splits well, so you will have real parallel processing.

Answer 3

Ok, let's write the spliterator. Using OfLong is still too boring: let's switch to BigInteger and don't limit user by 92. The tricky thing here is to quickly jump to the given Fibonacci number. I'll use matrix multiplication algorithm described here for this purpose. Here's my code:

static class FiboSpliterator implements Spliterator<BigInteger> {
 private final static BigInteger[] STARTING_MATRIX = {
 BigInteger.ONE, BigInteger.ONE, 
 BigInteger.ONE, BigInteger.ZERO};
 private BigInteger[] state; // previous and current numbers
 private int cur; // position
 private final int fence; // max number to cover by this spliterator
 public FiboSpliterator(int max) {
 this(0, max);
 }
 // State is not initialized until traversal
 private FiboSpliterator(int cur, int fence) {
 assert fence >= 0;
 this.cur = cur;
 this.fence = fence;
 }
 // Multiplication of 2x2 matrix, by definition 
 static BigInteger[] multiply(BigInteger[] m1, BigInteger[] m2) {
 return new BigInteger[] {
 m1[0].multiply(m2[0]).add(m1[1].multiply(m2[2])),
 m1[0].multiply(m2[1]).add(m1[1].multiply(m2[3])),
 m1[2].multiply(m2[0]).add(m1[3].multiply(m2[2])),
 m1[2].multiply(m2[1]).add(m1[3].multiply(m2[3]))};
 }
 // Log(n) algorithm to raise 2x2 matrix to n-th power 
 static BigInteger[] power(BigInteger[] m, int n) {
 assert n > 0;
 if(n == 1) {
 return m;
 }
 if(n % 2 == 0) {
 BigInteger[] root = power(m, n/2);
 return multiply(root, root);
 } else {
 return multiply(power(m, n-1), m);
 }
 }
 @Override
 public boolean tryAdvance(Consumer<? super BigInteger> action) {
 if(cur == fence)
 return false; // traversal finished
 if(state == null) {
 // initialize state: done only once
 if(cur == 0) {
 state = new BigInteger[] {BigInteger.ZERO, BigInteger.ONE};
 } else {
 BigInteger[] res = power(STARTING_MATRIX, cur);
 state = new BigInteger[] {res[1], res[0]};
 }
 }
 action.accept(state[1]);
 // update state
 if(++cur < fence) {
 BigInteger next = state[0].add(state[1]);
 state[0] = state[1];
 state[1] = next;
 }
 return true;
 }
 @Override
 public Spliterator<BigInteger> trySplit() {
 if(fence - cur < 2)
 return null;
 int mid = (fence+cur) >>> 1;
 if(mid - cur < 100) {
 // resulting interval is too small:
 // instead of jumping we just store prefix into array
 // and return ArraySpliterator
 BigInteger[] array = new BigInteger[mid-cur];
 for(int i=0; i<array.length; i++) {
 tryAdvance(f -> {});
 array[i] = state[0];
 }
 return Spliterators.spliterator(array, ORDERED | NONNULL | SORTED);
 }
 // Jump to another position
 return new FiboSpliterator(cur, cur = mid);
 }
 @Override
 public long estimateSize() {
 return fence - cur;
 }
 @Override
 public int characteristics() {
 return ORDERED | IMMUTABLE | SIZED| SUBSIZED | NONNULL | SORTED;
 }
 @Override
 public Comparator<? super BigInteger> getComparator() {
 return null; // natural order
 }
}

This implementation actually faster in parallel for very big fence value (like 100000). Probably even wiser implementation is also possible which would split unevenly reusing the intermediate results of matrix multiplication.

• Holger: Why do you update the state after action.accept instead of before it (in an else clause)? Doing it afterwards implies potentially doing unnecessary work, i.e. when tryAdvance is not called again...
• Abhijit Sarkar: Interesting you used the 2x2 matrix multiplication. I'd used the same logic a year ago with Arrays.parallelPrefix to solve the same problem. I'll study your code later and either accept your answer or ask questions, as applicable. My old code - just search for the word 'fibonacci'.
• Abhijit Sarkar: @tagir-valeev, I'll accept your answer. I made my solution based on your code, with some modifications. I've a question: when do the methods trySplit and tryAdvance get called in the lifecycle of a Spliterator?
• Tagir Valeev: @AbhijitSarkar, in general it's not specified, so you should expect that trySplit and tryAdvance are called in any sequence. However current Stream API implementation never calls trySplit after tryAdvance: first spliterator splits, then its parts are traversed.