Advertisement
iamcreasy

4 Algorithms to calculate Fibonacci number

Oct 6th, 2017
89
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 5.42 KB | None | 0 0
  1. import java.io.BufferedWriter;
  2. import java.io.FileWriter;
  3. import java.io.IOException;
  4. import java.io.PrintStream;
  5. import java.math.BigInteger;
  6. import java.util.ArrayList;
  7. import java.util.concurrent.TimeUnit;
  8.  
  9. /**
  10.  * FibLoop
  11.  * FibRecursive
  12.  * FibRecursiveWithCache
  13.  * FibMatrix
  14.  *
  15.  * F(0)=1,
  16.  * F(1)=1,
  17.  *
  18.  * F(2)=2,
  19.  * F(3)=3,
  20.  * F(4)=5,
  21.  * F(5)=8
  22.  *
  23.  * Arry 0 1 2 3 4 5 6  7  8  9  10 11
  24.  * Seq  1 2 3 4 5 6 7  8  9  10 11 12
  25.  * Fib  1 1 2 3 5 8 13 21 34 55 89 144
  26.  */
  27.  
  28. public class FibBigNum {
  29.     ArrayList<BigInteger> fibCache;
  30.  
  31.     public static void main(String[] args) throws IOException {
  32.         new FibBigNum(args);
  33.     }
  34.  
  35.     public FibBigNum(String... args) throws IOException {
  36.         boolean infiniteFib = true;
  37.         long startTime, elpasedTime;
  38.  
  39.         int inputNumber = 0;
  40.         BigInteger fibResult = BigInteger.ZERO;
  41.  
  42.         if(args.length > 1) {
  43.             inputNumber = Integer.parseInt(args[1]);
  44.             infiniteFib = false;
  45.         }
  46.  
  47. //        System.out.println(args[0].substring(1).concat(" BigInteger"));
  48. //        System.out.println("n  MiliSec");
  49.  
  50. //        PrintStream writer = new PrintStream(args[0].substring(1));
  51.         do{
  52.             startTime = System.nanoTime();
  53.             switch (args[0])
  54.             {
  55.                 case "-FibLoop":
  56.                 case "-1":
  57.                     fibResult = FibLoop(inputNumber);
  58.                     break;
  59.                 case "-FibRecursive":
  60.                 case "-2":
  61.                     fibResult = FibRecursive(inputNumber);
  62.                     break;
  63.                 case "-FibRecursiveWithCache":
  64.                 case "-3":
  65.                     fibCache = new ArrayList<>(inputNumber);
  66.                     for(int i = 0; i<inputNumber+1; i++)
  67.                         fibCache.add(i, null);
  68.  
  69.                     fibResult = FibRecursiveWithCache(inputNumber);
  70.                     break;
  71.                 case "-FibMatrix":
  72.                 case "-4":
  73.                     fibResult = FibMatrix(inputNumber);
  74.                     break;
  75.             }
  76.  
  77.             elpasedTime = System.nanoTime() - startTime;
  78. //            System.out.println(inputNumber + " " + fibResult.toString() + " " + TimeUnit.MILLISECONDS.convert(elpasedTime, TimeUnit.NANOSECONDS));
  79. //            System.out.println(inputNumber + " " + TimeUnit.NANOSECONDS.convert(elpasedTime, TimeUnit.NANOSECONDS));
  80. //            System.out.println(inputNumber + " " + fibResult);
  81. //            System.out.println(inputNumber + " " + count);
  82.  
  83. //            writer.println(inputNumber + " " + TimeUnit.NANOSECONDS.convert(elpasedTime, TimeUnit.NANOSECONDS));
  84.             inputNumber = inputNumber + 1;
  85.             fibResult = BigInteger.ZERO;
  86.  
  87.         } while (inputNumber <= 50000 && infiniteFib); // run until inputNumber reaches the limit of long variable type
  88.  
  89. //        writer.close();
  90.     }
  91.  
  92.     BigInteger first, second, result;
  93.     private BigInteger FibLoop(int n)
  94.     {
  95.         if(n == 0 || n == 1) return BigInteger.ONE;
  96.  
  97.         first = BigInteger.ONE;
  98.         second = BigInteger.ONE;
  99.         result = BigInteger.ZERO;
  100.  
  101.         for(int loop = 1 ; loop < n; loop++)
  102.         {
  103.             result = first.add(second);
  104.  
  105.             first = new BigInteger(second.toString());
  106.             second = new BigInteger(result.toString());
  107.         }
  108.  
  109.         return result;
  110.     }
  111.  
  112.     private BigInteger FibRecursive(int n)
  113.     {
  114.         if(n == 0 || n == 1) return BigInteger.ONE;
  115.         return FibRecursive(n-1).add(FibRecursive(n-2));
  116.     }
  117.  
  118.     /**
  119.      * Array[4] holds Fib(5)
  120.      * @param n-th Fibonacci number
  121.      * @return value of Fib(n)
  122.      */
  123.     static String test;
  124.     private BigInteger FibRecursiveWithCache(int n)
  125.     {
  126.         if(n == 0) {
  127.             fibCache.set(0, BigInteger.ONE);
  128.             return BigInteger.ONE;
  129.         }
  130.         if(n == 1) {
  131.             fibCache.set(1, BigInteger.ONE);
  132.             return BigInteger.ONE;
  133.         }
  134.  
  135.         if(fibCache.get(n) == null){
  136.             fibCache.set(n, new BigInteger(FibRecursiveWithCache(n-1).add(FibRecursiveWithCache(n-2)).toString()));
  137.         }
  138.  
  139.         return fibCache.get(n);
  140.  
  141.     }
  142.  
  143.     private BigInteger FibMatrix(int n)
  144.     {
  145.         if(n == 0 || n == 1) return BigInteger.ONE;
  146.  
  147.         BigInteger[][] matrix = {
  148.                 {BigInteger.ZERO, BigInteger.ONE},
  149.                 {BigInteger.ONE, BigInteger.ONE}
  150.         };
  151.  
  152.         matrix = matrixPower(matrix, n);
  153.         return matrix[0][0].add(matrix[1][0]);
  154.     }
  155.  
  156.     private BigInteger[][] matrixPower(BigInteger[][] matrix, int power)
  157.     {
  158.         BigInteger[][] result = {
  159.                 {BigInteger.ONE, BigInteger.ZERO},
  160.                 {BigInteger.ZERO, BigInteger.ONE}
  161.         };
  162.  
  163.         while(power > 0 )
  164.         {
  165.             if(power % 2 == 1)
  166.                 result = matrix2x2Multi(result, matrix);
  167.  
  168.             power = power / 2;
  169.             matrix = matrix2x2Multi(matrix, matrix);
  170.         }
  171.  
  172.         return result;
  173.     }
  174.  
  175.     private BigInteger[][] matrix2x2Multi(BigInteger[][] a, BigInteger[][] b)
  176.     {
  177.         BigInteger[][] result = {
  178.                 {a[0][0].multiply(b[0][0]).add(a[0][1].multiply(b[1][0])) ,  a[0][0].multiply(b[0][1]).add(a[0][1].multiply(b[1][1]))},
  179.                 {a[1][0].multiply(b[0][0]).add(a[1][1].multiply(b[1][0]))  ,  a[1][0].multiply(b[0][1]).add(a[1][1].multiply(b[1][1]))}
  180.         };
  181.  
  182.         return result;
  183.     }
  184. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement