1억 번째 피보나치 수를 구하면 4754 페이지 분량이다.
10억 번째 피보나치 수를 구하는 건...
쉽지 않다.
---------------------------------------------------------------------------------------------------------------------------------------------------------------------
울프람알파는 10억 번째 피보나치 수 구하기를 거부하였다.
---------------------------------------------------------------------------------------------------------------------------------------------------------------------
파이썬은 대형 정수 곱셈을 할 때 카라츠바 알고리즘을 사용한다.
그러나 초대형 정수 곱셈에서 단점을 보인다.
피보나치 수를 빠르게 구하기 위해 필요한 공식은 F(m+n-1) = F(m)F(n) + F(m-1)F(n-1) 이다.
이를 이용해 F(2n)과 F(2n+1)을 구할 수 있고 2진법을 이용해 계산 단계를 줄일 수 있다.
gmpy2 라이브러리를 사용한 파이썬 계산기는
초대형 정수 곱셈을 FFT(Fast Fourier Transform) 기반 계산을 빠르게 하며
10억 번째 피보나치 수의 계산 결과는 다음과 같다.
이렇게 시작해서...
이렇게 끝난다.
사용된 파이썬 코드는 다음과 같다.
---------------------------------------------------------------------------------------------------------------------------------------------------------------------
Claude AI에 의하면 계산 차이점은 다음과 같다.
F(10억) 계산 전 과정
부라보!! - dc App