Java 큰 수의 피보나치 수열의 값은?

 

• 피보나치(Fibonacci) 수열이란?
  • 1, 1, 2, 3, 5, 8, .. 와 같이 f(x) = f(x - 2) + f(x - 1); 을 만족하는 수열을 말한다.  (첫 항: f(0) = 0 또는 f(1) = 1)
• 아주 큰 자연수 n에 대하여 피보나치 수열의 n 번째 값은 어떻게 구할 수 있을까?

 

---

첫 번째 시도 [Long]

• static 으로 선언한 List<Long> 안에  하나씩 값을 넣어준다. list = [1, 1, 2,3, 5, ...]
• 해당 리스트에 메모이제이션을 적용했다. 

<hide/>
static List<Long> list = new ArrayList<>();
private static void fiboFunc(int idx) {
    if (idx == 1 || idx == 2) {
        list.add(idx, 1L);
        return;
    }
    list.add(idx, list.get(idx - 2) + list.get(idx - 1));
}

 

 

결과 

• cf) Java에서 Long으로 표현할 수 있는 최댓값: 922 3372 0368 5477 5807(19자리) 
• 따라서, 93 번째 부터는 stack overflow로 인한 음수가 나온다.
• static으로 변수를 선언했는데 반드시 필요한 상황은 아니어서 다음 시도에는 제거했다. 

 

---

 

두 번째 시도 [List에 모두 담는 방식]

• 한계가 있는 Integer, Long 을 넘어서 더더욱 큰 정수를 활용할 수 있도록  BigInteger를 적용한다. 
• 그러나 이 방식은 List에 값을 모두 담기 때문에 n번째 피보나치 값을 구하고자 할 때에는 비효율적이다. 

<hide/>
private static void fiboFunc(int n) {
    long start = System.currentTimeMillis();
    list.add(0, BigInteger.ZERO);
    list.add(1, BigInteger.ONE);
    BigInteger result = BigInteger.ZERO;
    for (int i = 2; i <= n; ++i) {
        result = list.get(i - 2).add(list.get(i - 1));
        list.add(i, result);
        if (i == n) {
            long end = System.currentTimeMillis();
            System.out.println("duration " + (end - start));
            System.out.println(result);
        }
    }
}

 

 

결과

• 100000번째의 피보나치 수를 구하는데 걸린 시간: 223

 

---

 

세 번째 시도 [List 없이 두 개의 변수 돌려써서 결과만 반환]

• 위에서는 List에 하나씩 담아서 매번 읽어오는 방식으로 구현했다. 
• 이번에는 두 개의 BigInteger 인스턴스 a, b 두 개를 만들어서 더해서 result에 저장하는 방식으로 구현했다. 
• n번째 값을 구하기 이전 값들을 굳이 저장하지 않기 때문에 시간이 짧다. 

<hide/>
private static void fiboFunc(int n) {
    long start = System.currentTimeMillis();
    BigInteger a = BigInteger.ZERO;
    BigInteger b = BigInteger.ONE;
    BigInteger result = BigInteger.ZERO;
    for (int i = 2; i <= n; i++) {
        result = a.add(b);
        if (i == n) {
            long end = System.currentTimeMillis();
            System.out.println("duration " + (end - start));
            System.out.println(result);
            return;
        }
        a = b;
        b = result;
    }
}

 

 

결과

• 100000번째의 피보나치 수를 구하는데 걸린 시간: 166
• 배열이나 목록으로 수열 전체가 필요하지 않은 이상 이 방법이 가장 효율적이고 시간이 단축된다.