이 강연은 면접 질문 형식으로 피보나치 수열 계산 알고리즘의 발전 과정을 단계별로 제시하며 루비의 강력한 기능을 시연합니다.
1. 기본 재귀 알고리즘
fib(n) = fib(n-1) + fib(n-2)형태는 중복 계산으로O(2^n)의 지수적 성능 저하를 보입니다.
2. 베넷 공식 및 정밀도 문제
- 수학적 공식은 이론상
O(1)이지만, 루비의 기본 부동 소수점(Float)으로는 큰 수에서FloatDomainError나 정밀도 오차가 발생합니다. BigDecimal은 임의 정밀도로 오차를 줄이지만 성능이 저하되며,Rational은 연분수 근사를 통해 더 큰 수까지 정확도를 유지하나 결국 한계에 도달합니다.
3. 꼬리 재귀 최적화 (Tail Call Optimization)
- 누적자를 사용하는 재귀 함수는 중복 계산을 줄이지만
SystemStackError를 유발합니다. - 루비의 꼬리 재귀 최적화(TCO)를 활성화하면 스택 깊이를 일정하게 유지하여 N이 50만까지도 빠르게 계산할 수 있습니다.
4. 행렬 거듭제곱 및 반복 제곱법
- 피보나치 수열의 행렬 항등식
[[1, 1], [1, 0]]^n을 활용합니다. - 반복 제곱법(Repeated Squares)은 비트 연산을 통해 행렬 거듭제곱을
O(log n)시간에 수행하여 N이 수천만까지 가능하게 합니다.
5. 빠른 배가 (Fast Doubling)
F_{2m}과F_{2m+1}을F_m과F_{m+1}으로 표현하는 최적화된 공식을 사용합니다.Hash의default_proc를 활용한 동적 프로그래밍(memoization)으로 구현됩니다.- N이 10억에 달하는 피보나치 수를 약 10초 만에 계산할 수 있으며, 이는 루비의 뛰어난 계산 성능을 입증합니다.