summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorHaidong Ji2018-08-24 13:39:04 -0500
committerHaidong Ji2018-08-24 13:39:04 -0500
commit5d2720031431f05a382482681cd0bbafc8727828 (patch)
tree8bd649af001bba678648718b949d3346006dfa97
parent35812b1161b5855d3b733fa6d499345dd14794fd (diff)
Improved fib by getting rid of array
Huge improvement in terms of both time and memory consumption.
-rw-r--r--AlgoDesignAndTechniqueEdxJava/sources/FibAgain.java19
1 files changed, 17 insertions, 2 deletions
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();
}