summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--AlgoDesignAndTechniqueEdxJava/sources/FibAgain.java68
-rw-r--r--AlgoDesignAndTechniqueEdxJava/tests/FibAgainTest.java10
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() {