025. 1000-digit Fibonacci Number (1000자리 피보나치 수 구하기)

 

 

​문제 (English)

The Fibonacci sequence is defined by the recurrence relation:

$F_n = F_{n-1} + F_{n-2}$, where $F_1=1$ and $F_2=1$.

 

Hence the first terms will be:

 

$F_{1}=1, F_{2}=1, F_{3}=2, F_{4}=3, F_{5}=5, F_{6}=8,F_{7}=13, F_{8}=21, F_{9}=34, F_{10}=55, F_{11}=89, F_{12}=144 $

 

The 12th term, $F_{12}$, is the first term to contain three digits.

What is the index of the first term in the Fibonacci sequence to contain digits?

 

문제 분석

---

1000자리가 되는 피보나치 수를 구하는 문제.

 

1000자리이기 때문에 일반적인 변수를 가지고는 계산이 안된다.

 

두가지 풀이 방법이 있다. 

하나는, 큰 수에 대해서 피보나치 수를 구하기 위해, 큰 수를 배열로 표현하고 그 배열에 대한 덧셈을 구현해서 피보나치 수를 구하는 것.

 

두 번째는, 피보나치수의 규칙을 이용해서 수학적으로 자릿수를 구하는 공식을 만들어서 푸는 방법.

 

풀이 1은 큰 수에 대한 덧셈 이용해서 풀이.

풀이 2는 수학공식을 만들어서 풀어보겠다.

 

풀이 1 

---

가장 간단히 생각해 볼 수 있는 풀이 방법이다.

- 3에서부터 시

 

 

풀이 2 

---

어떤 십진수 k의 자릿수 $L(k)$은,

 

$$L(k) = 1 + \log_{10}{k} \tag {1}$$ 

 

n번째의 피보나치 수 $F(n)$은,

$$F(n) = F(n-1) + F(n-2) \tag {2}$$

 

피보나치 수 $F(n)$에 대한 자릿수를 구하는 것이기에, $F(n)$에 대한 자릿수 $L(F(n)$은,

$L(F(n)) = 1 + \log_{10}{F(n-1)+F(n-2)} \tag {3}$ 

 

식(3)을 보면, 오른편 식을 $L$에 대한 식으로 바꾸면, 유용한 풀이 식이 나올 수 있을 거 같은데, $L$에 대한 식으로 바꿀 방법이 안 보인다. $F$를 표현하는 다른 식을 찾아서 사용해 보자.

 

피보나치 수 $F(n)$을 황금비(Golden rate, 1.618...)를 이용해서 나타내는 식이 있다. 

 

황금비 $\varphi$는 $F(n+1)$과 $F(n)$과의 비이다. 

$$\varphi = \lim _ {n \to \infty} {\frac {F(n+1)}{F(n)}} = \frac {(1+\sqrt{5})}{2} = 1.618$$

 

n번째 피보나치 수를 황금비를 이용해서 나타낼 수 있다. 

 

$$ F(n) = \frac{1}{\sqrt{5}} \left\{ \left( \frac{1+\sqrt{5}}{2} \right)^{n} - \left( \frac{1-\sqrt{5}}{2} \right)^{n} \right\} = \frac{1}{\sqrt{5}} \left(\varphi^{n}-(1-\varphi)^n \right) \tag {4} $$

 

식(4)에서 $(1-\varphi)^n$은 생략하고, 계산된 결과를 반올림해도 결과는 똑같다.

아래와 같이 실제 수식을 넣어 엑셀로 값을 구해보면, 실제 생략할 수 있음을 알 수 있다.

 

위 엑셀의 수식은,

 

따라서,  $F(n)$을 다시 쓰면,

$$ F(n) = \frac{\varphi^{n}}{\sqrt{5}} \tag {5}$$

 

이제 식(5)에 대해서 몇 자리 수가 되는지 식(1)을 적용해 본다. 자릿수 d보다 F(n) 값이 커야 되기에 $d=L(F(n)) \le ...$ 형태가 된다.

$$  d = L(F(n)) \le 1 + \log_{10}{\frac{\varphi^{n}}{\sqrt{5}}} = 1 + \log_{10}{\varphi^{n}} - \log_{10}{\sqrt{5}} \tag {6}$$ 

 

이제 d=1000 자리가 되려면 피보나치의 $n$이 얼마인지를 구하는 게 문제이기에, 식(6)을 $n$에 대해서 정리하면,

 

$$ n \ge (d-1+\log_{10}{\sqrt{5}}) / \log_{10}{\varphi} \tag {7}$$ 

 

위 식(7) 에서 n이 오른편 식보다 같거나 커야 하고 n이 정수이기에, 오른편식은 올림(ceiling)해야 한다. 오른편 식을 올림으로 표현하고, 내부의 상수값들에 실제 값을 적용하면, 

 

$n = \lceil (d-0.650515) / 0.20898764 \rceil \tag {8}$

 

이 식을 코드로 구현하면 된다.

 

fn answer2(d:usize) -> usize {
    let phi:f64 = (1.0 + 5f64.sqrt()) / 2f64 ;
    let sqrt5 = 5f64.sqrt();
    let n = (d as f64-1.0+sqrt5.log10()) / phi.log10();
    return n.ceil() as usize;
}

 

총평

---

큰 수에 대한 피보나치 수를 구하려면, 일반 변수에 의한 덧셈이 아니라, 큰 수를 처리할 수 있게 배열로 수를 표현한 후 배열에 대한 덧셈 연산을 해야한다. 

이 문제는, 큰 수에 대한 덧셈을 할 수 있느냐를 물어보는 문제이다.

 

파이썬에서는 큰 수에 대해서 자동으로 Bigint로 전환하여, 큰 수에 대해서도 일반변수처럼 연산이 가능하기에, 피보나치 수의 계산도 그냥 일반변수처럼 하면 된다. 

Java에서는 BigInteger 클래스를 사용하면 된다.

 

큰 수에 대한 처리를 배열 등을 이용해서 직접 구현할 수 있어야 하느냐, 아니면 그냥 프로그램 언어에서 제공하는 라이브러리를 이용하면 족하냐는, 아직 잘 모르겠다.

그러나, 알고리즘을 공부하는 입장이라면, 직접 구현할 수도 있어야 하지 않을까 싶다.

 

전체 소스코드

---

p25.rs 

#[test]
fn test(){
    // assert_eq!(vec![2,6,8], big_add(&Vec::from([1,8,9]), &Vec::from([7,9])));
    
    assert_eq!(4782, answer(1000));
    assert_eq!(7, answer(2));
    assert_eq!(23922, answer(5000));
}

#[cfg(test)]
fn answer(n:usize) -> usize{
    let mut i = 3;
    let mut f:Vec<Vec<usize>> = vec![vec![0],vec![1], vec![1]];
    loop {
        fibo(i, &mut f);
        if f[i].len() >= n {break;}
        i += 1;
        if i > 23923 {break;} //Len(f(23922)) = 5000
    }
    return i;
}

#[cfg(test)]
fn fibo(n:usize, f:&mut Vec<Vec<usize>>) {
    let t = big_add(&f[n-1], &f[n-2]);
    f.push(t);
}

#[cfg(test)]
fn big_add(a:&Vec<usize>, b:&Vec<usize>) -> Vec<usize> {
    let (&large, &small) = if a.len() >= b.len() {(&a, &b)} else {(&b,&a)};
    
    let mut c:Vec<usize> = Vec::new();
    let mut carry = 0;
    let mut i:i32 = small.len() as i32 -1; 
    let mut j:i32 = large.len() as i32 -1;
    while i >= 0 {
        let t = small[i as usize] + large[j as usize] + carry;
        c.push(t % 10);
        carry = t / 10;
        i -= 1; j -= 1;
    }
    while j >= 0 {
        let t = large[j as usize] + carry;
        c.push(t % 10);
        carry = t / 10;
        j -= 1;
    }
    if carry > 0 {c.push(carry);}
    c.reverse();

    return c;
}

//-------------
//n-1, n-2 값만 저장하는 버전
#[test]
fn test1(){
    assert_eq!(4782, answer1(1000));
    assert_eq!(7, answer1(2));
    assert_eq!(23922, answer1(5000));
}

#[cfg(test)]
fn answer1(n:usize) -> usize{
    let mut i = 3;
    let mut f1 = vec![1];
    let mut f2 = vec![1];    
    loop {
        let f3 = big_add(&f1, &f2);
        if f3.len() >= n {break;}
        i += 1;
        f1 = f2;  f2 = f3;        

        if i > 23923 {break;} //Len(f(23922)) = 5000
    }
    return i;
}


//-------------------------
// 수학공식 이용

#[test]
fn test2(){
    assert_eq!(4782, answer2(1000));
    assert_eq!(7, answer2(2));
    assert_eq!(23922, answer2(5000));
}

#[cfg(test)]
fn answer2(d:usize) -> usize {
    let phi:f64 = (1.0 + 5f64.sqrt()) / 2f64 ;
    let sqrt5 = 5f64.sqrt();
    let n = (d as f64-1.0+sqrt5.log10()) / phi.log10();
    return n.ceil() as usize;
}

 

끝