FibonacciSequence.java

packagecom.jwetherell.algorithms.sequence;

/**
 * In mathematics, the Fibonacci numbers are the numbers in the following integer sequence, called the Fibonacci sequence, and characterized by the fact that every number after the first two is the 
 * sum of the two preceding ones: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...
 * <p>
 * @see <a href="https://en.wikipedia.org/wiki/Fibonacci_number">Fibonacci Sequence (Wikipedia)</a>
 * <br>
 * @author Justin Wetherell <phishman3579@gmail.com>
 */
publicclassFibonacciSequence {

privatestaticfinaldoubleINVERSE_SQUARE_ROOT_OF_5 = 1 / Math.sqrt(5); // Inverse of the square root of 5
privatestaticfinaldoublePHI = (1 + Math.sqrt(5)) / 2; // Golden ratio

privateFibonacciSequence() {} 

publicstaticfinallongfibonacciSequenceUsingLoop(intn) {
finallong[] array = newlong[n + 1];
intcounter = 0;
while (counter <= n) {
longr = 0;
if (counter > 1) {
r = array[counter - 1] + array[counter - 2];
 } elseif (counter == 1) {
r = 1;
 }
// If r goes below zero then we have run out of bits in the long
if (r < 0)
thrownewIllegalArgumentException("Run out of bits in long, n="+n);
array[counter] = r;
counter++;
 }

returnarray[n];
 }

/**
 * Recursion with memoization
 */
publicstaticfinallongfibonacciSequenceUsingRecursion(intn) {
// Using the array to store values already computed
finallong[] array = newlong[n + 1];
returnfibonacciSequenceUsingRecursion(array,n);
 }

privatestaticfinallongfibonacciSequenceUsingRecursion(long[] array, intn) {
if (n == 0 || n == 1) 
returnn;

// If array already has a value then it has previously been computed
if (array[n] != 0)
returnarray[n];

finalStringexception = "Run out of bits in long, n="+n;

finallongr1 = fibonacciSequenceUsingRecursion(array, (n - 1));
array[n-1] = r1; // memoization
// If r1 goes below zero then we have run out of bits in the long
if (r1 < 0)
thrownewIllegalArgumentException(exception);

finallongr2 = fibonacciSequenceUsingRecursion(array, (n - 2));
array[n-2] = r2; // memoization
// If r2 goes below zero then we have run out of bits in the long
if (r2 < 0)
thrownewIllegalArgumentException(exception);

finallongr = r1 + r2;
// If r goes below zero then we have run out of bits in the long
if (r < 0)
thrownewIllegalArgumentException("Run out of bits in long, n="+n);

array[n] = r; // memoization

returnr;
 }

publicstaticfinallongfibonacciSequenceUsingMatrixMultiplication(intn) {
// m = [ 1 , 1 ]
// [ 1 , 0 ]
finallong[][] matrix = newlong[2][2];
matrix[0][0] = 1;
matrix[0][1] = 1;
matrix[1][0] = 1;
matrix[1][1] = 0;

long[][] temp = newlong[2][2];
temp[0][0] = 1;
temp[0][1] = 1;
temp[1][0] = 1;
temp[1][1] = 0;

intcounter = n;
while (counter > 0) {
temp = multiplyMatrices(matrix, temp);
// Subtract an additional 1 the first time in the loop because the
// first multiplication is actually n -= 2 since it multiplying two matrices
counter -= (counter == n) ? 2 : 1;
 }
finallongr = temp[0][1];
// If r goes below zero then we have run out of bits in the long
if (r < 0)
thrownewIllegalArgumentException("Run out of bits in long, n="+n);
returnr;
 }

privatestaticfinallong[][] multiplyMatrices(long[][] A, long[][] B) {
finallonga = A[0][0];
finallongb = A[0][1];
finallongc = A[1][0];
finallongd = A[1][1];

finallonge = B[0][0];
finallongf = B[0][1];
finallongg = B[1][0];
finallongh = B[1][1];

B[0][0] = a * e + b * g;
B[0][1] = a * f + b * h;
B[1][0] = c * e + d * g;
B[1][1] = c * f + d * h;

returnB;
 }

publicstaticfinallongfibonacciSequenceUsingBinetsFormula(intn) {
finallongr = (long) Math.floor(Math.pow(PHI, n) * INVERSE_SQUARE_ROOT_OF_5 + 0.5);
// If r hits max value then we have run out of bits in the long
if (r == Long.MAX_VALUE)
thrownewIllegalArgumentException("Run out of bits in long, n="+n);
returnr;
 }
}