From c6c5c65f881e9bf67a1bfd62022dbf756b489e8a Mon Sep 17 00:00:00 2001
From: Haidong Ji
Date: Sun, 26 Aug 2018 22:33:30 -0500
Subject: Improved the code by getting rid of fib calculation!

Following the same change I made to Python earlier.---
 .../sources/FibAgain.java                          | 68 ++++++++++++----------
 .../tests/FibAgainTest.java                        | 10 ++--
 2 files changed, 43 insertions(+), 35 deletions(-)

diff --git a/AlgoDesignAndTechniqueEdxJava/sources/FibAgain.java b/AlgoDesignAndTechniqueEdxJava/sources/FibAgain.java
index cef27a5..b38f44a 100644
--- a/AlgoDesignAndTechniqueEdxJava/sources/FibAgain.java
+++ b/AlgoDesignAndTechniqueEdxJava/sources/FibAgain.java
@@ -1,34 +1,33 @@
-import java.math.BigInteger;
 import java.util.Scanner;
 
 public class FibAgain {
 
-	public static BigInteger getFib(int n) {
-		if (n <= 1)
-			return BigInteger.valueOf(n);
-		final BigInteger[] fibArray = new BigInteger[n + 1];
-		fibArray[0] = BigInteger.valueOf(0);
-		fibArray[1] = BigInteger.valueOf(1);
-		for (int i = 2; i < n + 1; i++) {
-			fibArray[i] = fibArray[i - 1].add(fibArray[i - 2]);
-		}
-		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 BigInteger getFib(int n) {
+//		if (n <= 1)
+//			return BigInteger.valueOf(n);
+//		final BigInteger[] fibArray = new BigInteger[n + 1];
+//		fibArray[0] = BigInteger.valueOf(0);
+//		fibArray[1] = BigInteger.valueOf(1);
+//		for (int i = 2; i < n + 1; i++) {
+//			fibArray[i] = fibArray[i - 1].add(fibArray[i - 2]);
+//		}
+//		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
@@ -62,9 +61,18 @@ public class FibAgain {
 
 	public static int getFibNModM(long n, int m) {
 		int p = getPisanoPeriodOptimized(m);
-		long i = n % p;
-		BigInteger fib = getFibOptimized((int) i);
-		return fib.mod(BigInteger.valueOf(m)).intValue();
+		long r =  n % p;
+		if (r == 0)
+			return 0;
+		int firstN = 0;
+		int secondN = 1;
+		int tempHolder = 1;
+		for (int i = 1; i < r; i++) {
+			tempHolder = (firstN+secondN)%m;
+			firstN = secondN;
+			secondN=tempHolder;
+		}
+		return secondN;
 	}
 
 	public static void main(String args[]) {
diff --git a/AlgoDesignAndTechniqueEdxJava/tests/FibAgainTest.java b/AlgoDesignAndTechniqueEdxJava/tests/FibAgainTest.java
index de32b49..11ab098 100644
--- a/AlgoDesignAndTechniqueEdxJava/tests/FibAgainTest.java
+++ b/AlgoDesignAndTechniqueEdxJava/tests/FibAgainTest.java
@@ -5,11 +5,11 @@ import java.math.BigInteger;
 import org.junit.jupiter.api.Test;
 
 public class FibAgainTest {
-	@Test
-	void testGetFib40() {
-		BigInteger f = new BigInteger("102334155");
-		assertEquals(f, FibAgain.getFib(40));
-	}
+//	@Test
+//	void testGetFib40() {
+//		BigInteger f = new BigInteger("102334155");
+//		assertEquals(f, FibAgain.getFib(40));
+//	}
 
 	@Test
 	void testFibonacciPisanoPeriodOptimized2() {
-- 
cgit v1.2.3