From 5d2720031431f05a382482681cd0bbafc8727828 Mon Sep 17 00:00:00 2001
From: Haidong Ji
Date: Fri, 24 Aug 2018 13:39:04 -0500
Subject: Improved fib by getting rid of array

Huge improvement in terms of both time and memory consumption.---
 AlgoDesignAndTechniqueEdxJava/sources/FibAgain.java | 19 +++++++++++++++++--
 1 file changed, 17 insertions(+), 2 deletions(-)

(limited to 'AlgoDesignAndTechniqueEdxJava')

diff --git a/AlgoDesignAndTechniqueEdxJava/sources/FibAgain.java b/AlgoDesignAndTechniqueEdxJava/sources/FibAgain.java
index fbf907e..cef27a5 100644
--- a/AlgoDesignAndTechniqueEdxJava/sources/FibAgain.java
+++ b/AlgoDesignAndTechniqueEdxJava/sources/FibAgain.java
@@ -15,6 +15,21 @@ public class FibAgain {
 		return fibArray[n];
 	}
 
+	public static BigInteger getFibOptimized(int n) {
+		if (n <= 1)
+			return BigInteger.valueOf(n);
+		final BigInteger[] fibArray = new BigInteger[n + 1];
+		BigInteger firstFib = BigInteger.valueOf(0);
+		BigInteger secondFib = BigInteger.valueOf(1);
+		BigInteger tempHolder = BigInteger.valueOf(0);
+		for (int i = 2; i < n + 1; i++) {
+			tempHolder = firstFib.add(secondFib);
+			firstFib = secondFib;
+			secondFib = tempHolder;
+		}
+		return secondFib;
+	}
+
 	public static int getPisanoPeriodOptimized(int m) {
 		// this optimized algorithm is obtained through the
 		// discussion starting around 7:30 mark of the following
@@ -47,8 +62,8 @@ public class FibAgain {
 
 	public static int getFibNModM(long n, int m) {
 		int p = getPisanoPeriodOptimized(m);
-		long i =  n % p;
-		BigInteger fib = getFib((int) i);
+		long i = n % p;
+		BigInteger fib = getFibOptimized((int) i);
 		return fib.mod(BigInteger.valueOf(m)).intValue();
 	}
 
-- 
cgit v1.2.3