package fibonaccisequence;

/**
 * Fibonacci Sequence
 * @author Winston   Prakash
 */
public class FibonacciSequence {
    
    /*
     * Based on iteration O(n**2)
     * This is very innefficient
     */ 
    public long iterativeFindAt(int index){
        if (index == 0) return 0;
        if (index == 1) return 1;
        return iterativeFindAt(index - 1) + iterativeFindAt(index - 2);
    }
    
    /*
     * Find FB based on simple polynomial equation  O(n)
     */
    public long FindAt(int index){
        if (index == 0) return 0;
        long[] fibSeq = new long[index + 1];
        fibSeq[0] = 0;
        fibSeq[1] = 1;
        for (int i = 2; i <= index; i++){
           fibSeq[i] =  fibSeq[i - 1] + fibSeq[i - 2];
        }
        return fibSeq[index];
    }
    
    
    /*
     * Based on Formula but may be inaccurate at higher index values O(1)
     */
    public long FindAtUsingFormula(int index){
        double sqrtFive = Math.sqrt(5D);
        double mult1 = 1/sqrtFive;

        double mult2  = Math.pow(((1. + sqrtFive)/2.0), (double)index);
        double mult3  = Math.pow(((1. - sqrtFive)/2.0), (double)index);
        
        return (long)(mult1 * mult2 - mult1 * mult3);
    }
}