피보나치 수열 생성기

수열은 0, 1로 시작하고 그 뒤의 모든 항은 앞의 두 항을 더한 값입니다. 몇 개까지 원하는지 입력하면 전부 나열해 주고, 마지막 항과 누적 합, 그리고 마지막 두 항의 비를 함께 보여 줍니다. 그 비가 바로 황금비 φ ≈ 1.618034로 수렴하는 수입니다. 모든 계산은 임의 정밀도 정수로 이뤄지므로 백 번째든 천 번째든 반올림이 아니라 정확한 값입니다.

그 정확함이야말로 스프레드시트 대신 도구를 쓸 이유 전부입니다. 피보나치 수는 배정도 연산의 범위를 금방 넘어섭니다. F(78)은 8,944,394,323,791,464로 배정도가 정확히 담을 수 있는 53비트 안에 아직 들어오지만, F(79)는 14,472,334,024,676,221로 들어오지 못합니다. 그 지점부터 부동소수점으로 계산하는 계산기는 그럴듯해 보이면서 끝자리가 틀린 수를, 아무 경고 없이 돌려줍니다. F(100)은 354,224,848,179,261,915,075로 스물한 자리이고, F(1000)은 209자리입니다.

φ로의 수렴은 빠르고, 출력에서 지켜볼 만합니다. 오차는 부호를 번갈아 가며 매 단계 φ² ≈ 2.618배씩 줄어듭니다. 열 번째 항에서 약 1.5 × 10⁻⁴, 스무 번째에서 10⁻⁸, 서른 번째에서 10⁻¹² 어긋납니다. 서른 번째쯤이면 배정도가 표현할 수 있는 자릿수보다 더 많은 자리에서 φ와 일치하므로, 수열이 계속 이어지는 동안에도 비율 열은 한참 전에 변화를 멈춥니다.

단순한 호기심 이상인 성질이 둘 있습니다. 피보나치 수를 어떤 수로 나눈 나머지는 주기를 이룹니다. 마지막 한 자리의 주기는 정확히 60이라서 F(n)과 F(n+60)은 언제나 같은 숫자로 끝나는데, 긴 목록을 빠르게 검산하는 방법이 됩니다. 그리고 φ가 1마일에 해당하는 킬로미터 수와 가깝기 때문에, 이웃한 두 항이 둘 사이의 환산이 됩니다. 5마일은 약 8 km, 8마일은 약 13 km, 13마일은 약 21 km입니다. 비 1.6, 1.625, 1.615가 실제 값 1.609를 양쪽에서 감싸므로, 이 요령은 다섯 번째 항부터 대략 1퍼센트 이내로 정확합니다.