diff options
| -rw-r--r-- | AlgoDesignAndTechniqueEdxJava/sources/FibAgain.java | 68 | ||||
| -rw-r--r-- | AlgoDesignAndTechniqueEdxJava/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() { |