# Fibonacci forever

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.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) {
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++) {
previous = current;
current = part.values[i];
}
}

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

/**
* 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?

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.

• Can it really be considered constant space if the numbers are getting bigger (therefore needing more bits to store)? – rodolphito Dec 20 '15 at 6:28
• @Rodolvertice Asymptotically constant (O(1) space) and approximately constant anyway because you're just storing two BigIntegers. – BenC Dec 20 '15 at 6:30
• 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. – user2357112 supports Monica Dec 20 '15 at 7:07