Fibonacci forever

Question

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?

Answer 1

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.

• vero: Can it really be considered constant space if the numbers are getting bigger (therefore needing more bits to store)?
• BenC: @Rodolvertice Asymptotically constant (O(1) space) and approximately constant anyway because you're just storing two BigIntegers.
• user2357112: 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.