@@ -0,0 +1,3176 @@
+/*%0AThis program uses memoization (https://en.wikipedia.org/wiki/Memoization) to optimize the fibonacci sequence's%0Atime complexity. It can handle any int %60n%60 so long as the JVM has a large enough stack.%0A */%0A%0Aimport java.math.BigInteger;%0Aimport java.util.ArrayList;%0Aimport java.util.Scanner;%0A%0Apublic class MemoizationFib %7B%0A    private static ArrayList%3CString%3E computed = new ArrayList%3C%3E();%0A%0A    public static void main(String%5B%5D args) %7B%0A        Scanner scan = new Scanner(System.in);%0A%0A        boolean goodInput = false;%0A        int n = 0;%0A        while (!goodInput) %7B%0A            try %7B%0A                System.out.print(%22Enter n: %22);%0A                n = Integer.parseInt(scan.next());%0A                if(n %3C 0)%0A                    throw new Exception();%0A                goodInput = true;%0A                System.out.println();%0A            %7D catch (Exception e) %7B%0A                System.err.println(%22Invalid input. Please enter a positive integer.%22);%0A            %7D%0A        %7D%0A%0A        long startTime = System.nanoTime(); //time how long it takes%0A        BigInteger result = fib(n);%0A        long endTime = System.nanoTime();%0A        long duration = (endTime - startTime) / 1000000; //get milliseconds%0A%0A        System.out.println(%22Fibonacci(%22 + n + %22) = %22 + result.toString() + %22%5CnExecution took %22 + duration + %22 milliseconds%22);%0A    %7D%0A%0A    public static BigInteger fib(int n) %7B%0A        if(n == 0 %7C%7C n == 1) %7B //base case%0A            return BigInteger.valueOf(n);%0A        %7D else %7B%0A             //do the calculation%0A            String%5B%5D check = checker(n);%0A            if (Boolean.parseBoolean(check%5B0%5D)) %7B%0A                return new BigInteger(computed.get(Integer.parseInt(check%5B1%5D)).split(%22:%22)%5B1%5D);%0A            %7D else%0A            %7B%0A                BigInteger f = (fib(n-1).add(fib(n-2)));%0A                computed.add(n + %22:%22 + f);%0A                return f;%0A            %7D%0A        %7D%0A    %7D%0A%0A    public static String%5B%5D checker(int n) %7B%0A        String%5B%5D result = %7B%22%22, %22%22%7D;%0A        for(String s : computed) %7B%0A            if (Integer.parseInt(s.split(%22:%22)%5B0%5D) == n) %7B //if we've already computed this %60n%60%0A                result%5B0%5D = %22true%22;%0A                result%5B1%5D = computed.indexOf(s) + %22%22;%0A                return result;%0A            %7D else %7B%0A                result%5B0%5D = %22false%22;%0A                result%5B1%5D = %22-1%22;%0A            %7D%0A        %7D%0A        return result; //return whether we've computed it, and if we have, return the index%0A    %7D%0A%7D%0A%0A/*%0ACopyright (C) 2016  Zachary Taylor %7C ztaylor54@gmail.com%0A%0AThis program is free software; you can redistribute it and/or%0Amodify it under the terms of the GNU General Public License%0Aas published by the Free Software Foundation; either version 2%0Aof the License, or (at your option) any later version.%0A%0AThis program is distributed in the hope that it will be useful,%0Abut WITHOUT ANY WARRANTY; without even the implied warranty of%0AMERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the%0AGNU General Public License for more details.%0A%0AYou should have received a copy of the GNU General Public License%0Aalong with this program; if not, write to the Free Software%0AFoundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.%0A */%0A

Create MemoizationFib.java