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, what's the compilation error you're having? The code uses Lombok so you'll need that to make sense of the annotations. — Abhijit Sarkar, Jan 14 '16 at 17:15

score 4 · Answer 1 · answered Jan 14 '16 at 11:15

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.

score 4 · Answer 2 · answered Jan 14 '16 at 11:40

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.

score 3 · Accepted Answer · edited May 23 '17 at 12:34

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.

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… — Holger, Jan 15 '16 at 10:23
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](https://github.com/abhijitsarkar/java8-impatient/blob/master/src/main/java/name/abhijitsarkar/java/java8impatient/concurrency/PracticeQuestionsCh6.java) - just search for the word 'fibonacci'. — Abhijit Sarkar, Jan 15 '16 at 10:45
@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`? — Abhijit Sarkar, Jan 16 '16 at 05:27
@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. — Tagir Valeev, Jan 16 '16 at 07:22

How to implement a Spliterator for streaming Fibonacci numbers?

3 Answers3