Нахождение ближайших чисел Фибоначчи
Я пытаюсь решить более серьезную проблему, и я думаю, что важная часть программы тратится на неэффективные вычисления.
Мне нужно вычислить для данного числа N интервал [P, Q], где P - наибольшее число Фибоначчи, которое <= N, а Q - наименьшее число Фибоначчи, которое> = до N.
В настоящее время я использую карту для записи значений чисел Фибоначчи. Запрос обычно включает поиск по всем числам Фибоначчи вплоть до N, и это не очень эффективно по времени, поскольку включает большое число сравнений.
Этот тип запросов будет довольно часто встречаться в моей программе, и меня интересуют способы, которыми я мог бы улучшить поиск, предпочтительно с сублинейной сложностью.
1 ответ
На Scala находят, что приватный номер Fibonaci выглядит также очень простым:
val phi = (1 + sqrt(5))/2
def fib(n: Long): Long = round( ( pow(phi,n) - pow((1-phi),n) ) / sqrt(5) )
def fibinv(f: Long): Long = if (f < 2) f else round( log(f * sqrt(5) ) /log(phi))