G-факт 18 | Нахождение n-го числа Фибоначчи с использованием золотого сечения
Мы обсудили различные методы нахождения n-го числа Фибоначчи.
Ниже приводится еще один математически правильный способ найти то же самое.
n-е число Фибоначчи:
Здесь φ - золотое сечение со значением как
Вышеупомянутая формула кажется хорошей для нахождения n-го числа Фибоначчи за время O (Logn), поскольку целая степень числа может быть вычислена за время O (Logn). Но это решение практически не работает, потому что φ хранится как число с плавающей запятой, и когда мы вычисляем степени φ, важные биты могут быть потеряны в процессе, и мы можем получить неправильный ответ.
Использованная литература:
https://www.youtube.com/watch?v=-EQTVuAhSFY
http://en.wikipedia.org/wiki/Fibonacci_number
Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по теме, обсужденной выше.