How to implement Spliterator for streaming Fibonacci numbers?

Question

I play with Java 8 Spliterator and created to stream Fibonacci numbers to the 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 

Below is my implementation, which prints a bunch of 1 to the end of the stack memory. Can you help me find a mistake? (I think this is not a promotion of currentIndex , but I'm not sure what value to set it to).

Change 1 . If you decide to answer, please keep it in relation to the question. This question is not related to the efficiency of generating Fibonacci numbers; it's about learning breaks.

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); } } 

Using:

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

Answer 1

Ok, write a separator. Using OfLong is still too boring: let it switch to BigInteger and not limit the user to 92. The difficulty here is to quickly switch to a given Fibonacci number. For this purpose, I will use the matrix multiplication algorithm described here . Here is 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 runs faster in parallel with a very large fence value (for example, 100000 ). Possibly, an even smarter implementation is possible, which will share the uneven reuse of the intermediate results of matrix multiplication.

Answer 2

Besides the fact that your code is incomplete, there are at least two recognition errors in your tryAdvance method. First, you are not really moving forward. You do not change the state of your delimiter. Secondly, you unconditionally call the accept action method, which does not match the fact that you are returning a conditional value, not true .

The purpose of tryAdvance :

• as the name suggests, try to do it in advance, i.e. calculate the following value
• if there is the following value, call action.accept with that value and return true
• otherwise just return false

Please note that your trySplit() does not look very convincing, I don’t even know where to start. You better inherit from AbstractSpliterator and not implement custom trySplit() . In any case, your operation will not benefit from parallel execution. A thread built with this source can only benefit from parallel execution if you tie it to quiet, expensive operations on each element.

Answer 3

In general, you do not need to use a spliterator. If you really need a Spliterator object, you can use a 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); 

Note that storing the Fibonacci numbers in the long variable is questionable: it overflows after the Fibonacci number of 92. Therefore, if you want to create a spliterator that simply iterates over the first 92 Fibonacci numbers, I would suggest using a 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); 

The array separator also breaks well, so you will have real parallel processing.