This solution uses the Iterator
interface. When run it calculates all fibonacci numbers in the long range. The accepted answer is doubly exponential time since it's O(n^2)
for each call. On my computer changing n
to 93 to do the same as my program it will use several hours to compute the same list this code does in 0.09 seconds.
import java.util.Iterator;
import java.util.NoSuchElementException;
import java.lang.IllegalArgumentException;
public class Fibonacci implements Iterable<Long>
{
final int FIB_MAX_LONG_INDEX = 92; // highest index producing correct long
int fromIndex = 0;
int toIndex = FIB_MAX_LONG_INDEX;
public Fibonacci(int fromIndex, int toIndex)
{
if( fromIndex > toIndex )
throw new IllegalArgumentException("toIndex must be same or greater than fromIndex");
if( toIndex > FIB_MAX_LONG_INDEX )
throw new IllegalArgumentException("toIndex must be lowe or equal to 92 to not overflow long");
this.fromIndex = fromIndex;
this.toIndex = toIndex;
}
public Fibonacci(){}
private class FibonacciIterator implements Iterator<Long>
{
private long cur = 0, next = 1;
private int index=0;
public boolean hasNext()
{
return index <= toIndex;
}
public Long next()
{
if ( index > toIndex )
throw new NoSuchElementException();
long tmpCur;
do {
tmpCur = cur;
cur = next;
next +=tmpCur;
index++;
} while ( index <= fromIndex );
return tmpCur;
}
public void remove()
{
throw new UnsupportedOperationException();
}
}
public Iterator<Long> iterator()
{
return new FibonacciIterator();
}
public static void main (String[] args)
{
Fibonacci fib = new Fibonacci();
for (long i : fib)
{
System.out.print( i + " ");
}
System.out.println();
}
}
The output when run (I've added some linefeeds):
0 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 2971215073 4807526976 7778742049
12586269025 20365011074 32951280099 53316291173
86267571272 139583862445 225851433717 365435296162
591286729879 956722026041 1548008755920 2504730781961
4052739537881 6557470319842 10610209857723
17167680177565 27777890035288 44945570212853
72723460248141 117669030460994 190392490709135
308061521170129 498454011879264 806515533049393
1304969544928657 2111485077978050 3416454622906707
5527939700884757 8944394323791464 14472334024676221
23416728348467685 37889062373143906 61305790721611591
99194853094755497 160500643816367088
259695496911122585 420196140727489673
679891637638612258 1100087778366101931
1779979416004714189 2880067194370816120
4660046610375530309 7540113804746346429
But as you see you can make just about any index range. the following loops over 30 to 39 and ends up printing 832040 1346269 2178309 3524578 5702887 9227465 14930352 24157817 39088169 63245986
Fibonacci fib = new Fibonacci(30, 39);
for( long i : fib) {
System.out.print(i + " ");
}