Skip to content

Instantly share code, notes, and snippets.

@alastairparagas
Created September 8, 2015 01:08
Show Gist options
  • Select an option

  • Save alastairparagas/89fc3bab5ecfa89b5c0c to your computer and use it in GitHub Desktop.

Select an option

Save alastairparagas/89fc3bab5ecfa89b5c0c to your computer and use it in GitHub Desktop.
Fibonacci calculator - O(logN)
/*******************************************************
Program Number: A1_1
Purpose/Description: <a brief description of the program>
Author: Alastair Paragas
Due date: 09/09/2015
Certification:
I hereby certify that this work is my own and none of it is the work of
any other person.
Alastair Paragas
*******************************************************/
package assignment1.problem1;
public class Calculator {
/**
* Helper for calculating the nth Fibonacci number
* @param n - Term # in the Fibonacci sequence.
* @return Array where element 0 is the nth Fibonacci number and element 1
* is the nth - 1 Fibonacci number
*/
private int[] fibHelper(int n) {
if (n == 0) {
return new int[]{0,0};
} else if (n == 1) {
return new int[]{1,0};
}
// Odd Term (at least, Term #3) - use old strategy of adding 2
// previous terms
if (n % 2 == 1) {
int[] fibNthTuple = fibHelper(n - 1);
int fibNthTerm = fibNthTuple[0];
int fibNthMinus1Term = fibNthTuple[1];
return new int[]{fibNthTerm + fibNthMinus1Term, fibNthTerm};
}
// Even Term (at least, Term #2): F(2n) = (F(n))^2 + 2(F(n) * F(n-1))
int[] fibNthTuple = fibHelper(n/2);
int fibNthTerm = fibNthTuple[0];
int fibNthMinus1Term = fibNthTuple[1];
return new int[]{fibNthTerm * fibNthTerm + 2 * fibNthTerm *
fibNthMinus1Term, fibNthTerm * fibNthTerm + fibNthMinus1Term *
fibNthMinus1Term};
}
/**
* Calculates the nth Fibonacci number
* @param n - Term # in the Fibonacci sequence
* @return Fibonacci number
*/
public int fib(int n) {
// 0th Term is 0, 1st Term is 1
if (n < 2) {
return n;
}
return fibHelper(n)[0];
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment