행렬 거듭제곱으로 피보나치수 계산기

행렬 M=[[1,1],[1,0]]을 n제곱하면 그 결과 행렬의 우상단 원소가 정확히 F(n)이 됩니다. 예를 들어 M¹=[[1,1],[1,0]]의 우상단이 1=F(1)이고, M²=[[2,1],[1,1]]의 우상단이 1=F(2), M³의 우상단이 2=F(3)인 식입니다.

지수를 분할정복으로 처리하기 때문입니다. n제곱을 구할 때 지수가 짝수면 절반을 제곱해 구하고, 홀수면 한 번 더 곱하는 식으로 반복하면, 곱셈 횟수가 n이 아니라 log₂n에 비례해서만 늘어납니다. n이 100만이면 단순 반복은 100만 번의 연산이 필요하지만 이 방법은 약 20번의 행렬 곱셈이면 충분합니다.

메모이제이션 없는 순수 재귀(F(n)=F(n-1)+F(n-2))는 같은 값을 지수적으로 중복 계산해 n이 조금만 커져도 실행이 끝나지 않습니다. 메모이제이션을 쓰거나 반복문을 쓰면 O(n)까지는 줄일 수 있지만, 행렬 거듭제곱의 O(log n)에는 미치지 못합니다.

피보나치수는 황금비(약 1.618)의 거듭제곱에 가깝게 자라는 지수적 수열이기 때문입니다. n이 몇백만 되어도 자릿수가 수십, 수백 자리까지 늘어나 자바스크립트의 일반 숫자로는 정밀도를 잃습니다. 그래서 이 계산기는 임의 정밀도 정수(BigInt)로 계산합니다.