피보나치 수열 계산기

앞의 두 수를 더해 다음 수를 만드는 수열

피보나치 수열은 1, 1, 2, 3, 5, 8, 13, 21처럼 앞의 두 항을 더해 다음 항을 만드는 수열입니다. 13세기 이탈리아 수학자 피보나치가 『산반서』에서 토끼 한 쌍이 매달 새끼를 낳으면 쌍의 수가 어떻게 늘어나는지를 묻는 문제로 소개해 이 이름이 붙었습니다. 여기서는 첫째 항과 둘째 항을 1로 두는 일반적인 방식을 씁니다.

F(1) = F(2) = 1, F(n) = F(n−1) + F(n−2)

수가 빠르게 커지는 이유

피보나치 수는 한 항씩 갈 때마다 약 1.618배씩 커지기 때문에 50번째 항은 125억이 넘고, 100번째 항은 21자리가 됩니다. 이웃한 두 항의 비 F(n+1)/F(n)은 n이 커질수록 황금비 φ에 한없이 가까워집니다. 이 계산기는 큰 정수 연산을 써서 2,000번째 항(418자리)까지 정확한 값을 보여 줍니다.