def fibo(n):
sqrt_5 = pow(5, 1/2)
ans = 1 / sqrt_5 * ( ((1 + sqrt_5) / 2) ** n - ((1 - sqrt_5) / 2) ** n )
return int(ans)
sqrt(5) 자체가 이미 무리수인데다가, 1/sqrt(5) 부터 시작해서, 저 일반항 방식으로는 'Fn-1 + Fn-2' 방식의 순차 더하기로 딱딱 정수로 떨어지는 해를 도출할 수 없다는 것이 기본적인 숙명이다. 변수 크기를 아무리 늘려도 무리수는 그 끝이 없으므로 뒤에가서 반드시 오차가 나올 수 밖에 없다.
n=100000으로 하고 bc 로 위 식을 풀었을 때, 25974069347221716802868... 로 시작하는 20899자리수의 정수+소수점이하 20자리수의 소수 조합의 실수가 출력된다.
근데 이 결과값은 실제 피보나치 10만번째 수와 차이가 나는데, 예를 들어 20899자리 중 처음 15자리만 동일하고, 그 이하는 달라지는 것이다.
오차가 무려 m*e+20883 이나 된다!!
정밀한 계산에는 전혀 써먹을 수가 없는 지경이다.
굳이 오차를 보정하고자 변수의 크기를 20899자리수로 늘린다 쳐도, 캐리 처리 시간을 감안하면 일반항의 속도 장점은 완전히 사라지는 것이 되는 것이다. 캐리 때문에 오히려 일반항 방식이 더 느려진다.
즉, 이미지에 점찍는 수준의 설렁설렁 계산이 목적이라면 일반항이 유용할 수 있으나, 정밀계산에는 무용지물.
행렬식 이용하면 O(log N)으로 빠르고 정확하게 구할 수 있는 방법이 있음 내용은 영문 위키피디아에 있음
O(log N)이라면 순차 덧셈방식이랑 차이가 없음.. 행렬식도 CPU 한계로 인해 일정 자리수 이상 넘어가면 캐리문제로 더 복잡해짐?
순차 덧셈방식은 O(n)임 ㅎㅎ 위키피디아 찾아보고..ㅎㅎ
그리고 원래 수학 쪽 프로그래밍하는 놈들은 빅인트 무조건 해결함 ㅎㅎ
너 말대로라면 원주율 파이 수억 자리까지 어떻게 계산할래 고수들은 다 함 ㅎㅎ
오, 그래? 빅인트랑 행렬 조합 한 번 체크해 봐야겠네~ 빅인트나 캐리 방식이나 속도 느리다는 것과 정확한 값 계산이 가능하다는 건 공통점이지. 원주율 수억 아니라 수백억 자리도 당연히 계산 가능하지. 문제는 속도일 뿐.
위 일반항도, 소수자리수만 무한대로 늘려주면 (속도 무한대로 느려지면) 정확한 값 계산 얼마든지 가능하다.