Created
September 8, 2015 01:08
-
-
Save alastairparagas/89fc3bab5ecfa89b5c0c to your computer and use it in GitHub Desktop.
Fibonacci calculator - O(logN)
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| /******************************************************* | |
| 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