Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.io.BufferedWriter;
- import java.io.FileWriter;
- import java.io.IOException;
- import java.io.PrintStream;
- import java.math.BigInteger;
- import java.util.ArrayList;
- import java.util.concurrent.TimeUnit;
- /**
- * FibLoop
- * FibRecursive
- * FibRecursiveWithCache
- * FibMatrix
- *
- * F(0)=1,
- * F(1)=1,
- *
- * F(2)=2,
- * F(3)=3,
- * F(4)=5,
- * F(5)=8
- *
- * Arry 0 1 2 3 4 5 6 7 8 9 10 11
- * Seq 1 2 3 4 5 6 7 8 9 10 11 12
- * Fib 1 1 2 3 5 8 13 21 34 55 89 144
- */
- public class FibBigNum {
- ArrayList<BigInteger> fibCache;
- public static void main(String[] args) throws IOException {
- new FibBigNum(args);
- }
- public FibBigNum(String... args) throws IOException {
- boolean infiniteFib = true;
- long startTime, elpasedTime;
- int inputNumber = 0;
- BigInteger fibResult = BigInteger.ZERO;
- if(args.length > 1) {
- inputNumber = Integer.parseInt(args[1]);
- infiniteFib = false;
- }
- // System.out.println(args[0].substring(1).concat(" BigInteger"));
- // System.out.println("n MiliSec");
- // PrintStream writer = new PrintStream(args[0].substring(1));
- do{
- startTime = System.nanoTime();
- switch (args[0])
- {
- case "-FibLoop":
- case "-1":
- fibResult = FibLoop(inputNumber);
- break;
- case "-FibRecursive":
- case "-2":
- fibResult = FibRecursive(inputNumber);
- break;
- case "-FibRecursiveWithCache":
- case "-3":
- fibCache = new ArrayList<>(inputNumber);
- for(int i = 0; i<inputNumber+1; i++)
- fibCache.add(i, null);
- fibResult = FibRecursiveWithCache(inputNumber);
- break;
- case "-FibMatrix":
- case "-4":
- fibResult = FibMatrix(inputNumber);
- break;
- }
- elpasedTime = System.nanoTime() - startTime;
- // System.out.println(inputNumber + " " + fibResult.toString() + " " + TimeUnit.MILLISECONDS.convert(elpasedTime, TimeUnit.NANOSECONDS));
- // System.out.println(inputNumber + " " + TimeUnit.NANOSECONDS.convert(elpasedTime, TimeUnit.NANOSECONDS));
- // System.out.println(inputNumber + " " + fibResult);
- // System.out.println(inputNumber + " " + count);
- // writer.println(inputNumber + " " + TimeUnit.NANOSECONDS.convert(elpasedTime, TimeUnit.NANOSECONDS));
- inputNumber = inputNumber + 1;
- fibResult = BigInteger.ZERO;
- } while (inputNumber <= 50000 && infiniteFib); // run until inputNumber reaches the limit of long variable type
- // writer.close();
- }
- BigInteger first, second, result;
- private BigInteger FibLoop(int n)
- {
- if(n == 0 || n == 1) return BigInteger.ONE;
- first = BigInteger.ONE;
- second = BigInteger.ONE;
- result = BigInteger.ZERO;
- for(int loop = 1 ; loop < n; loop++)
- {
- result = first.add(second);
- first = new BigInteger(second.toString());
- second = new BigInteger(result.toString());
- }
- return result;
- }
- private BigInteger FibRecursive(int n)
- {
- if(n == 0 || n == 1) return BigInteger.ONE;
- return FibRecursive(n-1).add(FibRecursive(n-2));
- }
- /**
- * Array[4] holds Fib(5)
- * @param n-th Fibonacci number
- * @return value of Fib(n)
- */
- static String test;
- private BigInteger FibRecursiveWithCache(int n)
- {
- if(n == 0) {
- fibCache.set(0, BigInteger.ONE);
- return BigInteger.ONE;
- }
- if(n == 1) {
- fibCache.set(1, BigInteger.ONE);
- return BigInteger.ONE;
- }
- if(fibCache.get(n) == null){
- fibCache.set(n, new BigInteger(FibRecursiveWithCache(n-1).add(FibRecursiveWithCache(n-2)).toString()));
- }
- return fibCache.get(n);
- }
- private BigInteger FibMatrix(int n)
- {
- if(n == 0 || n == 1) return BigInteger.ONE;
- BigInteger[][] matrix = {
- {BigInteger.ZERO, BigInteger.ONE},
- {BigInteger.ONE, BigInteger.ONE}
- };
- matrix = matrixPower(matrix, n);
- return matrix[0][0].add(matrix[1][0]);
- }
- private BigInteger[][] matrixPower(BigInteger[][] matrix, int power)
- {
- BigInteger[][] result = {
- {BigInteger.ONE, BigInteger.ZERO},
- {BigInteger.ZERO, BigInteger.ONE}
- };
- while(power > 0 )
- {
- if(power % 2 == 1)
- result = matrix2x2Multi(result, matrix);
- power = power / 2;
- matrix = matrix2x2Multi(matrix, matrix);
- }
- return result;
- }
- private BigInteger[][] matrix2x2Multi(BigInteger[][] a, BigInteger[][] b)
- {
- BigInteger[][] result = {
- {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]))},
- {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]))}
- };
- return result;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement