피보나치 수 계산기

피보나치 수 계산기 쉽게 이해하기 — 개념과 원리

피보나치수열은 0, 1, 1, 2, 3, 5, 8, 13, …으로 이어지며, 각 항은 바로 앞 두 항의 합입니다. 이 계산기는 0부터 2,000까지의 n에 대해 F(n)의 정확한 값을 반올림 없이 정수 연산으로 구하고, 황금비에 가까워지는 비 F(n) ÷ F(n − 1)도 보여 줍니다. 피보나치 수는 프로그래밍, 알고리즘 분석, 경우의 수 문제에 자주 등장합니다.

계산 방법

• 정의: F(0) = 0, F(1) = 1이고, n ≥ 2일 때 F(n) = F(n − 1) + F(n − 2)입니다.
• 처음 두 항에서 출발해 마지막 두 값만 기억하며 n번 앞으로 나아가므로 덧셈 n번이면 됩니다.
• 비: F(n) ÷ F(n − 1)이며, n ≥ 2일 때 표시됩니다.

n은 0 이상 2,000 이하의 정수여야 합니다.

원리

이 수열은 피사의 레오나르도가 쓴 『산반서(Liber Abaci)』(1202)의 토끼 번식 문제로 서양 수학에 처음 소개되었습니다. 이번 달 토끼 쌍의 수는 지난달의 쌍에 새로 태어난 쌍을 더한 것이고, 새로 태어난 쌍은 두 달 전의 쌍 수와 같기 때문입니다. 일반항은 비네 공식 F(n) = (φⁿ − ψⁿ) ÷ √5로 나타낼 수 있으며, φ = (1 + √5) ÷ 2 ≈ 1.618034, ψ = (1 − √5) ÷ 2 ≈ −0.618034입니다. |ψ| < 1이어서 ψⁿ은 금방 작아지므로 F(n)은 φⁿ ÷ √5에 가장 가까운 정수가 되고, 이웃한 항의 비는 φ에 수렴합니다.

예제 풀이

1. 입력값: n = 50입니다.
2. F(0) = 0, F(1) = 1부터 차례로 더하면 F(48) = 4,807,526,976, F(49) = 7,778,742,049입니다.
3. F(50) = 4,807,526,976 + 7,778,742,049 = 12586269025입니다.
4. 비네 공식으로 확인하면 φ⁵⁰ ÷ √5 ≈ 12,586,269,025.0으로 같은 값이 됩니다.
5. 비: 12,586,269,025 ÷ 7,778,742,049 ≈ 1.618033989로, 표시된 자리까지 φ와 같습니다.

결과 해석

피보나치 수는 한 단계마다 약 1.618배씩 커지므로 F(n)의 자릿수는 대략 0.209 × n입니다. F(50)은 11자리, F(100)은 21자리입니다. 비 F(n) ÷ F(n − 1)은 φ보다 조금 컸다 작았다를 반복하며, n = 25 무렵이면 소수 아홉째 자리 정도까지 일치합니다. 정의로부터 세 번째마다 짝수가 나온다는 등의 성질도 따라 나옵니다.

흔한 실수

• F(0)의 번호 매기기를 헷갈려 모든 항의 순번이 하나씩 밀리는 경우입니다.
• 코드에서 단순 재귀를 써서 같은 값을 반복 계산하는 경우입니다. 매우 느려지며, 이 계산기처럼 반복문을 쓰면 n에 비례하는 시간이면 됩니다.
• 큰 n에서 비네 공식을 부동소수점으로 계산하는 경우입니다. n이 약 70을 넘으면 반올림 오차로 틀린 값이 나옵니다.
• 모든 나선이나 예술 작품에 황금비가 있다고 단정하는 경우입니다. 근삿값이거나 근거가 약한 주장이 많습니다.

자주 묻는 질문

F(100)은 얼마인가요?

F(100) = 354,224,848,179,261,915,075로 21자리 수입니다.

0도 피보나치 수인가요?

여기서 쓰는 현대적인 정의에서는 F(0) = 0입니다. 오래된 책 중에는 1, 1로 시작하는 경우도 있습니다.

파스칼의 삼각형과는 어떤 관계가 있나요?

파스칼의 삼각형에서 비스듬한 대각선 방향의 수를 더하면 1, 1, 2, 3, 5, 8, …의 피보나치 수가 나옵니다.

출처: Leonardo of Pisa (Fibonacci), Liber Abaci (1202) · Donald E. Knuth, The Art of Computer Programming, Vol. 1, §1.2.8 (Fibonacci Numbers) · OEIS Foundation, The On-Line Encyclopedia of Integer Sequences, A000045