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

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

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.