11
\$\begingroup\$

I recently wrote a Fibonacci program in Python, and one of the answers mentioned an Infinite Sequence. I decided to implement an infinite sequence in Java, as I am not that experienced in Python.

import java.math.BigInteger;
import java.util.LinkedList;
import java.util.List;

public class InfiniteFibonacci {

    /**
     * The default starting amount of numbers in the sequence to be generated.
     */
    public static final int DEFAULT_STARTING_CAP = 64;

    private List<SequencePart> parts;

    private int currentSize = 2;

    private BigInteger current = BigInteger.ONE;
    private BigInteger previous = BigInteger.ONE;

    /**
     * Creates a new <code>InfiniteFibonacci</code> object, with the default amount of numbers.
     */
    public InfiniteFibonacci() {
        this(DEFAULT_STARTING_CAP);
    }

    /**
     * Creates a new <code>InfiniteFibonacci</code> object, with the specified amount of numbers.
     * 
     * @param startCap The amount of numbers to generate. It will be rounded up to the nearest 16.
     */
    public InfiniteFibonacci(int startCap) {
        parts = new LinkedList<>();
        initFirst();
        initTo(startCap);
    }

    private void initFirst() {
        SequencePart part = new SequencePart();
        part.values[0] = previous;
        part.values[1] = current;
        for (int i = 2; i < SequencePart.SIZE; i++) {
            part.values[i] = previous.add(current);
            previous = current;
            current = part.values[i];
        }
        parts.add(part);
    }

    private void initTo(int index) {
        for (; currentSize <= index; currentSize += SequencePart.SIZE) {
            SequencePart part = new SequencePart();
            for (int i = 0; i < SequencePart.SIZE; i++) {
                part.values[i] = previous.add(current);
                previous = current;
                current = part.values[i];
            }
            parts.add(part);
        }
    }

    /**
     * Gets the <code>n</code>th number in the sequence, zero-based.
     * 
     * @param index the <code>n</code> as described
     * 
     * @return the specified in the sequence, zero-based.
     */
    public BigInteger getNumberAt(int index) {
        if (index > currentSize) {
            initTo(index);
        }
        return parts.get(index / SequencePart.SIZE).values[index % SequencePart.SIZE];
    }

    private class SequencePart {

        private static final int SIZE = 16;

        private BigInteger[] values = new BigInteger[SIZE];

        private SequencePart() {

        }

    }

}

Concerns:

  1. I don't like the initFirst() method, as it is very WET. Is there a way to avoid it?
  2. Is my JavaDoc and OOP good?
\$\endgroup\$
7
\$\begingroup\$

I'm not sure if SequencePart is necessary.

It would be much simpler to just keep a List<BigInteger> of numbers in InfiniteFibonacci, unless you've already done the testing to see if your chunked LinkedList is faster than a plain ArrayList<BigInteger>.

You would end up with something like this:

public BigInteger getNth(int index) {
    if (index >= nums.size()) {
        initTo(index);
    }
    return nums[index];
}

with no initFirst and with a much simpler initTo(index) method that just appends to this.nums until index.

Edit: OK, sorry, I realize why you're doing this chunking strategy (cheap insertion at the end of a LinkedList). I think it depends on your intended use case, and how often users will request arbitrary Fibs. I would still suggest testing tweaking the size of your SequenceParts to see if 16 is the optimum size for your intended usage.

Iterator

Since this is an infinite sequence, I would also suggest exposing an iterator interface that doesn't maintain a cache. If a caller only needs the numbers once, then you can let them iterate through Fibonacci numbers infinitely using constant space, as opposed to building up your internal list of calculated numbers.

\$\endgroup\$
  • 2
    \$\begingroup\$ Can it really be considered constant space if the numbers are getting bigger (therefore needing more bits to store)? \$\endgroup\$ – rodolphito Dec 20 '15 at 6:28
  • \$\begingroup\$ @Rodolvertice Asymptotically constant (O(1) space) and approximately constant anyway because you're just storing two BigIntegers. \$\endgroup\$ – BenC Dec 20 '15 at 6:30
  • 1
    \$\begingroup\$ Considering that the Nth Fibonacci number takes O(N) space to store, it really can't be considered constant space. Storing a list of all of them up to the Nth takes O(N^2) space, though. \$\endgroup\$ – user2357112 supports Monica Dec 20 '15 at 7:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.