0
그래서 나는 GNU MP 라이브러리로 Binet의 수식을 사용하여 피보나치 수를 계산하고 있습니다. 나는 알고리즘의 점근 적 런타임을 해결하려고 노력하고있다.Binet 's 공식 런타임
Fib (n)의 경우 변수를 n 비트 정밀도로 설정합니다. 따라서 두 숫자를 곱하는 것이 n Log (n)라고 생각합니다. 지수화는 Log (n) 곱셈을 믿습니다. 그래서 나는 Log (n) Log (n Log (n))을 가지고 있다고 믿는다. 이것은 가정에서 (부동 소수점 수와 정수 지수로 지수화 된 곱셈의 수를 곱하는) 가정과 결론적으로 맞습니까?
내 정밀도가 높고 정밀도 g (n)을 사용하는 경우; 나는 이것이 g (n) Log (g (n))로 감소한다고 생각한다; 그러나 나는 g (n) = n Log (phi) +1이어야한다고 생각한다. 이것은 점근선에 실제 영향을주지 않아야한다.
계산에는 단지 곱셈과 지수화가 필요합니까? exp (x * log (\ phi)) (사전 계산 된 로그 유지 (\ phi)). – ElKamina
숫자와 그 비트 수를 나타 내기 위해'n'을 사용하고 있습니다 : | –