2. 팩토리얼, 피보나치 + 계산에 소요된 시간

팩토리얼이나 피보나치 수열을 자바로 표현한다. +계산에 소요된 시간도 같이 구한다.

for문을 돌리면 간단하긴 하겠지만, for이 아닌 재귀함수를 이용하여 만들 것이다.

| 팩토리얼

public static int recursiveFactorial(int n)
{
   if(n==0) return 1;
   else return n*recursiveFactorial(n-1);
}

n! = n * (n-1)! = n * (n-1) * ··· 2 * 1         을 이용한 식이다.

| 피보나치

1. 1. 2. 3. 5. 8....  n번째 피보나치 수열의 수 Fn을 구하는 메소드를 작성해보자.

F(n)= F(n-1) + F(n-2)    (if n>=1)

F(0)=0, F(1)=1

public static int BinaryFib(int n)
{
   if(n<=1) return n;
   else return BinaryFib(n-1)+ BinaryFib(n-2);
}

| 계산에 소요된 시간

계산에 소요된 시간을 알아보자.

1. System.currentTimeMillis();
1970년 1월 1일 자정부터 현재까지 카운트된 시간을 ms(milliseconds) 단위로 표시한다. 실제 시간을 나타낼때 유용하다.

long start = System.currentTimeMillis();
long end = System.currentTimeMillis() - start;

long start = System.currentTimeMillis();   //계산 시작시간
System.out.println(n+"! = "+recursiveFactorial(n));
System.out.println(n+" 피보나치 = "+BinaryFib(n));
double end = (System.currentTimeMillis()-start)/1000.0;    //계산에 걸린 시간. 소수까지 나타내기 위해 double

를 했더니 실행결과로 0.0초가 나왔다.. 계산결과를 ms단위로 나타내서 그런 듯 하다.
그래서 이 문제를 해결하기 위해 다음 방법을 이용했다.


2. System.nanoTime();
nanoTime 메소드는 현재 Java 가상머신의 high-resolution 시간값을 ns(nano sec.) 단위로 반환한다. 단순히 소요된 시간을 나타낼 때 유용하다.

long start = System.nanoTime();
long end = System.nanoTime();

1ns는 1s/10억이다. 따라서 ms일때는 1000으로 나눴지만 이번에는 10억으로 나눠 주었다.

long start = System.nanoTime(); //계산 시작시간
System.out.println(n+"! = "+recursiveFactorial(n));
System.out.println(n+" 피보나치 = "+BinaryFib(n));
double end = (System.nanoTime()-start)/1000000000.0;   //계산에 걸린 시간. 소수까지 나타내기 위해 double

그랬더니 계산결과로

요런 이상한 결과가 나왔다..
여기서 E는 지수를 표현한다. 즉, 1.0543 x 10^-4 라는 뜻이다.

import java.math.*;

좀 더 쉽게 나타내기 위해 BigDemical 메소드를 이용했다.
java.math클래스 안에 있어, 먼저 java.math클래스를 import해줬다.

그 후 원래의 식에 BigDemical을 추가해주었다. (위에선 double을 10억으로 나누면 지수가 떴는데, 이번에는 안 뜨길래, 비교를 위해 임의로 0을 하나 더 추가하였다.).

long start = System.nanoTime();    //계산 시작시간
BigDecimal startTime = new BigDecimal(System.nanoTime());  //BigDecimal 이용

System.out.println(n+"! = "+recursiveFactorial(n));
System.out.println(n+" 피보나치 = "+BinaryFib(n));

double end = (System.nanoTime()-start)/10000000000.0;  //계산에 걸린 시간. 소수까지 나타내기 위해 double

BigDecimal endTime = new BigDecimal(System.nanoTime());    //BigDecimal: 끝나는 시간
BigDecimal total = endTime.subtract(startTime);    //BigDecimal: 계산에 걸린 시간
BigDecimal div = new BigDecimal(1000000000);   //BigDecimal: 10억
BigDecimal TOTAL = total.divide(div);  // 계산에 걸린 ns을 s로 나타내기 위해 나눴다.

BigDecimal convert = new BigDecimal(end);  //지수로 표현되던 수를 BigDecimal로 바꿔 표현

이 식에 대한 실행결과는 다음과 같다.

처음부터 BigDecimal을 이용해 계산한 것보다, double을 후에 BigDecimal로 저장한 값이 더 길다.

BigDecimal로 변환한 값이 너무 길다면, new Bigdecimal대신 BigDecimal.valueOf를 사용하면 된다.

double endFib = (System.nanoTime()-startFib)/1000000000.0; //계산에 걸린 시간. 소수까지 나타내기 위해 double

BigDecimal newFib = new BigDecimal(endFib);
BigDecimal valueFib = BigDecimal.valueOf(endFib);  // 지수를 풀어쓴다

결과: