Обратный алгоритм Фибоначчи?

Существует множество способов вычисления F (n) для любого n, многие из которых имеют отличную среду исполнения и использования памяти.

Однако предположим, что я хотел задать противоположный вопрос:

Для F (n) при n > 2, что n?

(Существует ограничение n > 2, так как F (1) = F (2) = 1 и нет однозначного обратного).

Каким будет наиболее эффективный способ решения этой проблемы? Это легко сделать в линейном времени, перечислив числа Фибоначчи и остановившись, когда вы нажмете на целевой номер, но есть ли способ сделать это быстрее, чем это?

EDIT:, лучшее решение, размещенное здесь, выполняется в O (log n) времени с использованием O (log n) памяти, предполагая, что математические операции выполняются в O (1) и что машинное слово может содержать любое число в O (1) пространстве. Мне интересно, если можно отказаться от требований к памяти, так как вы можете вычислить числа Фибоначчи, используя O (1) пространство.

Ответ 1

Поскольку OP задал вопрос о матричном решении, не включающем вычисления с плавающей запятой, вот оно. Таким образом, мы можем достичь сложности O(logn), предполагая, что числовые операции имеют сложность O(1).

Пусть возьмем матрицу 2x2 A, имеющую следующую структуру

1 1
1 0

Теперь рассмотрим вектор (8, 5), сохранив два последовательных числа фибоначчи. Если вы умножите его на эту матрицу, вы получите (8*1 + 5*1, 8*1 + 5*0) = (13, 8) - следующее число фибоначчи.
Если обобщить, A^n * (1, 0) = (f(n), f(n - 1)).

Фактический алгоритм выполняет два шага.

Рассчитайте A^2, A^4, A^8 и т.д. до тех пор, пока мы не получим требуемое число.
Сделайте двоичный поиск n, используя рассчитанные значения A.

На стороне примечания любая последовательность вида f(n) = k1*f(n-1) + k2*f(n-2) + k3*f(n-3) + .. + kt*f(n-t) может быть представлена следующим образом.

Ответ 2

Википедия дает результат как

n(F) = Floor[ Log(F Sqrt(5) + 1/2)/Log(Phi)]

где Phi - золотое соотношение.

Ответ 3

Если вы можете легко интерпретировать F (n) в двоичном формате,

Вы можете быть подозрительными к константам 1.7 и 1.1. Они работают, потому что d * 1.44042009041 + C никогда не приближается к целому числу.

Я могу опубликовать вывод завтра, если есть интерес.

Вот таблица с n = от 2 до 91, которая показывает результат формулы перед полом:

 n  formula w/o floor     F(n) F(n) in binary

 2  2.540                    1 1
 3  3.981                    2 10
 4  4.581                    3 11
 5  5.421                    5 101
 6  6.862                    8 1000
 7  7.462                   13 1101
 8  8.302                   21 10101
 9  9.743                   34 100010
10 10.343                   55 110111
11 11.183                   89 1011001
12 12.623                  144 10010000
13 13.223                  233 11101001
14 14.064                  377 101111001
15 15.504                  610 1001100010
16 16.104                  987 1111011011
17 17.545                 1597 11000111101
18 18.385                 2584 101000011000
19 19.825                 4181 1000001010101
20 20.425                 6765 1101001101101
21 21.266                10946 10101011000010
22 22.706                17711 100010100101111
23 23.306                28657 110111111110001
24 24.147                46368 1011010100100000
25 25.587                75025 10010010100010001
26 26.187               121393 11101101000110001
27 27.028               196418 101111111101000010
28 28.468               317811 1001101100101110011
29 29.068               514229 1111101100010110101
30 30.508               832040 11001011001000101000
31 31.349              1346269 101001000101011011101
32 32.789              2178309 1000010011110100000101
33 33.389              3524578 1101011100011111100010
34 34.230              5702887 10101110000010011100111
35 35.670              9227465 100011001100110011001001
36 36.270             14930352 111000111101000110110000
37 37.111             24157817 1011100001001111001111001
38 38.551             39088169 10010101000111000000101001
39 39.151             63245986 11110001010000111010100010
40 40.591            102334155 110000110010111111011001011
41 41.432            165580141 1001110111101000110101101101
42 42.032            267914296 1111111110000000110000111000
43 43.472            433494437 11001110101101001100110100101
44 44.313            701408733 101001110011101010010111011101
45 45.753           1134903170 1000011101001010011111110000010
46 46.353           1836311903 1101101011100111110010101011111
47 47.193           2971215073 10110001000110010010010011100001
48 48.634           4807526976 100011110100011010000101001000000
49 49.234           7778742049 111001111101001100010111100100001
50 50.074          12586269025 1011101110001100110011100101100001
51 51.515          20365011074 10010111101110110010110100010000010
52 52.115          32951280099 11110101100000011001010000111100011
53 53.555          53316291173 110001101001111001100000101001100101
54 54.396          86267571272 1010000010101111100101010110001001000
55 55.836         139583862445 10000001111111110110001011011010101101
56 56.436         225851433717 11010010010101110010110110001011110101
57 57.276         365435296162 101010100010101101001000001100110100010
58 58.717         591286729879 1000100110101011011011110111110010010111
59 59.317         956722026041 1101111011000001000100111001011000111001
60 60.157        1548008755920 10110100001101100100000110001001011010000
61 61.598        2504730781961 100100011100101101100101101010100100001001
62 62.198        4052739537881 111010111110011010000110011011101111011001
63 63.038        6557470319842 1011111011011000111101100000110010011100010
64 64.478       10610209857723 10011010011001100001110010100010000010111011
65 65.078       17167680177565 11111001110100101001011110101000010110011101
66 66.519       27777890035288 110010100001110001011010001001010011001011000
67 67.359       44945570212853 1010001110000010110100101111110010101111110101
68 68.800       72723460248141 10000100010010001000000000000111101001001001101
69 69.400      117669030460994 11010110000010011110100110000101111111001000010
70 70.240      190392490709135 101011010010100100110100110001101101000010001111
71 71.681      308061521170129 1000110000010111000101001100010011100111011010001
72 72.281      498454011879264 1110001010101011101011110010100001001111101100000
73 73.121      806515533049393 10110111011000010110000111110110100110111000110001
74 74.561     1304969544928657 100101000101101110011100110001010110000110110010001
75 75.161     2111485077978050 111100000000110001001101110000001010111101111000010
76 76.602     3416454622906707 1100001000110011111101010100001100001000100101010011
77 77.442     5527939700884757 10011101000111010000111000010001101100000010100010101
78 78.042     8944394323791464 11111110001101110000100010110011001101000111001101000
79 79.483    14472334024676221 110011011010101000001011011000100111001001001101111101
80 80.323    23416728348467685 1010011001100010110001111101111000000110010000111100101
81 81.764    37889062373143906 10000110100110111110011011000111100111111011010101100010
82 82.364    61305790721611591 11011001110011010100101010110110101000101101011101000111
83 83.204    99194853094755497 101100000011010010011000101111110010000101000110010101001
84 84.644   160500643816367088 1000111010001101100111110000110100111001010110001111110000
85 85.244   259695496911122585 1110011010100111111010110110110011001001111111000010011001
86 86.085   420196140727489673 10111010100110101100010100111101000000011010101010010001001
87 87.525   679891637638612258 100101101111011101011101011110011011001101010100010100100010
88 88.125  1100087778366101931 111101000100010011000000000110000011010000101001100110101011
89 89.566  1779979416004714189 1100010110011110000011101100100011110011101111101111011001101
90 90.406  2880067194370816120 10011111111000000011011101101010100001101110100111100001111000
91 91.846  4660046610375530309 100000010101011110011111011001111000000001100100101011101000101

Ответ 4

Измерение использования памяти путем подсчета неограниченных слов является своего рода глупым, но до тех пор, пока эта модель, существует решение O (log n), O (1) слово, подобное Никите Рыбаку, что по существу вычисляет n через представление Zeckendorf, основанное на числах Фибоначчи (YO DAWG).

Определим матрицу

      1  1
A  =       ,
      1  0

которая удовлетворяет

        F(m + 1)    F(m)
A^m  =                      .
          F(m)    F(m - 1)

Вместо последовательности A^(2^k) мы будем использовать последовательность A^F(k). Последняя последовательность обладает тем свойством, что мы можем двигаться вперед с умножением матрицы на

A^F(k + 1) = A^F(k - 1) * A^F(k)

и обратно с матрицей обратного и умножения

A^F(k - 1) = A^F(k + 1) (A^F(k))^-1,

так что мы можем построить двунаправленный итератор, используя только ~~eight~~ ~~шесть~~ двенадцать слов, предполагая, что мы храним все как рациональные (чтобы избежать предположения о существовании деления на единицу стоимости). Остальное просто адаптирует этот O (1) -пространственный алгоритм для нахождения представления Зеекендорфа.

def zeck(n):
    a, b = (0, 1)
    while b < n:
        a, b = (b, a + b)
    yield a
    n1 = a
    while n1 < n:
        a, b = (b - a, a)
        if n1 + a <= n:
            yield a
            n1 += a
            a, b = (b - a, a)

>>> list(zeck(0))
[0]
>>> list(zeck(2))
[1, 1]
>>> list(zeck(12))
[8, 3, 1]
>>> list(zeck(750))
[610, 89, 34, 13, 3, 1]

Ответ 5

Было доказано, что формула для a nn fib(n) = ( (phi)^n - (-phi)^(-n) ) / sqrt(5) где phi = (1+sqrt(5)) / 2 - номер золотого сечения. (см. эта ссылка).

Вы можете попытаться найти математический обратный к функции фина выше или иначе выполнить бинарный поиск в операциях 32/64 (в зависимости от того, насколько велика ваша максимальная величина для поиска), чтобы найти n, которое соответствует числу (попробуйте каждый n вычисляя fib (n) и разбивая пространство выборки на два в соответствии с тем, как fib (n) сравнивается с данным числом фибоначчи).

Изменить: решение @rcollyer выполняется быстрее, так как мой находится в O (lg n), и тот, который он нашел, находится в O (1) = постоянное время.

Ответ 6

Итак, я думал об этой проблеме, и я думаю, что это возможно сделать в O (lg n) времени с использованием памяти O (lg n). Это основано на том, что

F (n) = (1/& radic; 5) (& Phi; ⁿ - & phi; ⁿ)

Где & Phi; = (1 + & radic; 5)/2 и & phis; = 1 - & Phi;.

Первое наблюдение состоит в том, что & phis; ⁿ 1 для любого n > 1. Это означает, что для любого n > 2 мы имеем, что

F (n) = & llo; & Phi; ⁿ/& radic; 5 & rfloor;

Теперь возьмите n и запишите его в двоичном формате, как b _k-1 b _k-2... b ₁ b _{0суб > . Это означает, что}

n = 2 ^k-1 b _k-1 + 2 ^k-2 b _k-2 +... + 2 ¹ b ₁ + 2 ⁰ b ₀.

Это означает, что

F (n) = & llo; & Phi; ^{2 ^k-1 b _k-1 + 2 ^k-2 b _k-2 +... + 2 ¹ b ₁ + 2 ⁰ b ₀}/& radic; 5 & rfloor;

Или, что более понятно, что

F (n) = & llo; & Phi; ^{2 ^k-1 b _k-1} & Phi; ^{2 ^k-2 b _k-2}... & Phi; ^{2 ¹ b ₁} & Phi; ^{2 ⁰ b ₀}/& radic; 5 & rfloor;

Это говорит о следующем алгоритме. Во-первых, начните вычислять & Phi; ^{2 ^k} для всех k, пока вы не вычислите число & Phi; ^z такое, что & lloor; & Phi; ^z/& radic; 5 & rfloor; что больше вашего числа F (n). Теперь, оттуда, итерация назад по всем силам & Phi; вы создали этот путь. Если текущее число больше указанной мощности & Phi;, затем разделите его на эту мощность & Phi; и записать, что число было разделено на это значение. Этот процесс по существу восстанавливает один бит n за раз, вычитая наибольшую мощность 2, которую вы можете за один раз. Следовательно, как только вы закончите, вы найдете n.

Время выполнения этого алгоритма равно O (lg n), так как вы можете генерировать & Phi; ^{2 ⁱ} путем повторного квадратирования, и мы генерируем только O (lg n) сроки. Использование памяти - O (lg n), так как мы сохраняем все эти значения.

Ответ 7

Вы можете найти n для любого Fib (n) в O (1) и O (1) пространстве.

Вы можете использовать алгоритм CORDIC с фиксированной точкой для вычисления ln(), используя только сдвиг и добавление целочисленных типов данных.

Если x = Fib (n), то n можно определить через

     n = int(2.0801 * ln(x) + 2.1408)

Время работы CORDIC определяется желаемым уровнем точности. Два значения с плавающей запятой будут закодированы как значения фиксированной точки.

Единственная проблема с этим предложением состоит в том, что он возвращает значение для чисел, которые не входят в последовательность Фибоначчи, но исходная проблема специально указывала, что входной сигнал функции будет Fib (n), что означает, что только действительный Fibonacci числа будут использоваться.

Ответ 8

ИЗМЕНИТЬ: Ничего. Заявитель заявил в комментариях, что возведение в степень, безусловно, не постоянное время.

Является ли возведение в степень одной из математических операций, которые вы разрешите в постоянное время? Если это так, мы можем вычислить F (n) в постоянное время с помощью формулы закрытой формы. Тогда, учитывая некоторое F, мы можем сделать следующее:

Вычислить F (1), F (2), F (4), F (16), F (256),... до тех пор, пока F (2 ^ k) <= F < Р (2 ^ {к + 1})
Сделайте двоичный поиск я между 2 ^ k и 2 ^ {k + 1} до тех пор, пока F (i) <= F < Р (г + 1)

Если F = F (n), то первая часть принимает шаги k = O (log (n)). Вторая часть представляет собой двоичный поиск по диапазону размеров O (2 ^ k), поэтому он также принимает k = O (log (n)). Итак, в общем случае мы имеем O (log (n)) время в O (1) пространстве , если (и это большое if), мы имеем возведение в степень в O (1) времени.

Ответ 9

Замкнутая форма формулы числа Фибоначчи:

Fn = Round(φ^n / Sqrt(5))

Где φ - золотой коэффициент.

Если мы игнорируем фактор округления, это обратимо, и обратная функция:

F(-1)n= log(n*Sqrt(5))/logφ

Поскольку мы проигнорировали фактор округления, в формуле, которую можно было бы вычислить, есть ошибка. Однако если учесть, что число n является числом Фибоначчи, если интервал [n * φ - 1/n, n * φ + 1/n] содержит натуральное число, то:

Число является числом Фибоначчи, если интервал [n * φ - 1/n, n * φ + 1/n] содержит натуральное число и этот индекс числа в последовательности Фибоначчи задается округлением log (n * Sqrt (5))/logφ

Это должно выполняться в (псевдо) -константном времени в зависимости от алгоритмов, используемых для вычисления логарифма и квадратных корней и т.д.

Изменить: φ = (1 + Sqrt (5))/2

Ответ 10

Это может быть похоже на user635541 ответ. Я не совсем понимаю его подход.

Используя матричное представление чисел Фибоначчи, обсуждаемое в других ответах, мы получаем способ перехода от F_n и F_m к F_{n+m} и F_{n-m} в постоянное время, используя только плюсы, умножения, минус и (на самом деле нет! см. обновление). У нас также есть нуль (единичная матрица), поэтому это математическая группа!

Обычно при выполнении двоичного поиска нам также нужен оператор деления для усреднения. Или, по крайней мере, деление на 2. Однако, если мы хотим перейти от F_{2n} до F_n, для этого требуется квадратный корень. К счастью, оказывается, что плюсы и минусы - все, что нам нужно для логарифмического "почти" бинарного поиска!

Wikipedia пишет об этом подходе, по иронии судьбы, называемом Fibonacci_search, но статья написана не очень четко, поэтому я не знаю, это точно такой же подход, как и мой. Очень важно понимать, что числа Фибоначчи, используемые для поиска Фибоначчи, не имеют ничего общего с числами, которые мы ищем. Это немного запутанно. Чтобы продемонстрировать подход, вначале реализация стандартного "бинарного поиска" используется только с использованием плюс и минус:

def search0(test):
    # Standard binary search invariants:
    #   i <= lo then test(i)
    #   i >= hi then not test(i)
    # Extra invariants:
    #   hi - lo = b
    #   a, b = F_{k-1}, F_k
    a, b = 0, 1
    lo, hi = 0, 1
    while test(hi):
        a, b = b, a + b
        hi = b
    while b != 1:
        mi = lo + a
        if test(mi):
            lo = mi
            a, b = 2*a - b, b - a
        else:
            hi = mi
            a, b = b - a, a
    return lo

>>> search0(lambda n: n**2 <= 25)
5
>>> search0(lambda n: 2**n <= 256)
8

Здесь test - некоторая булева функция; a и b являются последовательными числами фибоначчи f_k и f_{k-1} такими, что разница между верхней границей hi и нижней границей lo всегда f_k. Нам нужны как a, так и b, чтобы мы могли эффективно и неявно изменять неявную переменную k.

Хорошо, так как мы используем это для решения проблемы? Мне было полезно создать оболочку вокруг нашего представления Фибоначчи, которое скрывает детали матрицы. На практике (есть ли такая вещь для искателя Фибоначчи?) вы хотели бы встроить все вручную. Это избавит вас от избыточности в матрицах и сделает некоторую оптимизацию вокруг инверсии матрицы.

import numpy as np
class Fib:
    def __init__(self, k, M):
        """ `k` is the 'name' of the fib, e.g. k=6 for F_6=8.
             We need this to report our result in the very end.
            `M` is the matrix representation, that is
             [[F_{k+1}, F_k], [F_k, F_{k-1}]] """
        self.k = k
        self.M = M
    def __add__(self, other):
        return Fib(self.k + other.k, self.M.dot(other.M))
    def __sub__(self, other):
        return self + (-other)
    def __neg__(self):
        return Fib(-self.k, np.round(np.linalg.inv(self.M)).astype(int))
    def __eq__(self, other):
        return self.k == other.k
    def value(self):
        return self.M[0,1]

Однако код работает, поэтому мы можем протестировать его следующим образом. Обратите внимание, насколько мало отличается функция поиска, когда наши объекты были целыми, а не Фибоначчи.

def search(test):
    Z = Fib(0, np.array([[1,0],[0,1]])) # Our 0 element
    A = Fib(1, np.array([[1,1],[1,0]])) # Our 1 element
    a, b = Z, A
    lo, hi = Z, A
    while test(hi.value()):
        a, b = b, a + b
        hi = b
    while b != A:
        mi = lo + a
        if test(mi.value()):
            lo = mi
            a, b = a+a-b, b-a
        else:
            hi = mi
            a, b = b-a, a
    return lo.k

>>> search(lambda n: n <= 144)
12
>>> search(lambda n: n <= 0)
0

оставшийся открытый вопрос - есть ли эффективный алгоритм поиска для моноидов. Это тот, который не нуждается в обратном минусе/добавке. Мое предположение - нет: что без минуса вам нужна дополнительная память о Никите Рыбаке.

Update

Я просто понял, что нам вообще не нужно разделение. Детерминантом матрицы F_n является только (-1)^n, поэтому мы можем делать все без разделения. В нижнем я удалил весь код матрицы, но я сохранил класс Fib, потому что все получилось так крайне беспорядочно.

class Fib2:
    def __init__(self, k, fp, f):
        """ `fp` and `f` are F_{k-1} and F_{k} """
        self.k, self.fp, self.f = k, fp, f
    def __add__(self, other):
        fnp, fn, fmp, fm = self.fp, self.f, other.fp, other.f
        return Fib2(self.k + other.k, fn*fm+fnp*fmp, (fn+fnp)*fm+fn*fmp)
    def __sub__(self, other):
        return self + (-other)
    def __neg__(self):
        fp, f = self.f + self.fp, -self.f
        return Fib2(-self.k, (-1)**self.k*fp, (-1)**self.k*f)
    def __eq__(self, other):
        return self.k == other.k
    def value(self):
        return self.f

def search2(test):
    Z = Fib2(0, 1, 0)
    A = Fib2(1, 0, 1)
    ...

>>> search2(lambda n: n <= 280571172992510140037611932413038677189525)
200
>>> search2(lambda n: n <= 4224696333392304878706725602341482782579852840250681098010280137314308584370130707224123599639141511088446087538909603607640194711643596029271983312598737326253555802606991585915229492453904998722256795316982874482472992263901833716778060607011615497886719879858311468870876264597369086722884023654422295243347964480139515349562972087652656069529806499841977448720155612802665404554171717881930324025204312082516817125)
2000
>>> search2(lambda n: n <= 2531162323732361242240155003520607291766356485802485278951929841991312781760541315230153423463758831637443488219211037689033673531462742885329724071555187618026931630449193158922771331642302030331971098689235780843478258502779200293635651897483309686042860996364443514558772156043691404155819572984971754278513112487985892718229593329483578531419148805380281624260900362993556916638613939977074685016188258584312329139526393558096840812970422952418558991855772306882442574855589237165219912238201311184749075137322987656049866305366913734924425822681338966507463855180236283582409861199212323835947891143765414913345008456022009455704210891637791911265475167769704477334859109822590053774932978465651023851447920601310106288957894301592502061560528131203072778677491443420921822590709910448617329156135355464620891788459566081572824889514296350670950824208245170667601726417091127999999941149913010424532046881958285409468463211897582215075436515584016297874572183907949257286261608612401379639484713101138120404671732190451327881433201025184027541696124114463488665359385870910331476156665889459832092710304159637019707297988417848767011085425271875588008671422491434005115288334343837778792282383576736341414410248994081564830202363820504190074504566612515965134665683289356188727549463732830075811851574961558669278847363279870595320099844676879457196432535973357128305390290471349480258751812890314779723508104229525161740643984423978659638233074463100366500571977234508464710078102581304823235436518145074482824812996511614161933313389889630935320139507075992100561077534028207257574257706278201308302642634678112591091843082665721697117838726431766741158743554298864560993255547608496686850185804659790217122426535133253371422250684486113457341827911625517128815447325958547912113242367201990672230681308819195941016156001961954700241576553750737681552256845421159386858399433450045903975167084252876848848085910156941603293424067793097271128806817514906531652407763118308162377033463203514657531210413149191213595455280387631030665594589183601575340027172997222489081631144728873621805528648768511368948639522975539046995395707688938978847084621586473529546678958226255042389998718141303055036060772003887773038422366913820397748550793178167220193346017430024134496141145991896227741842515718997898627269918236920453493946658273870473264523119133765447653295022886429174942653014656521909469613184983671431465934965489425515981067546087342348350724207583544436107294087637975025147846254526938442435644928231027868701394819091132912397475713787593612758364812687556725146456646878912169274219209708166678668152184941578590201953144030519381922273252666652671717526318606676754556170379350956342095455612780202199922615392785572481747913435560866995432578680971243966868110016581395696310922519803685837460795358384618017215468122880442252343684547233668502313239328352671318130604247460452134121833305284398726438573787798499612760939462427922917659263046333084007208056631996856315539698234022953452211505675629153637867252695056925345220084020071611220575700841268302638995272842160994219632684575364180160991884885091858259996299627148614456696661412745040519981575543804847463997422326563897043803732970397488471644906183310144691243649149542394691524972023935190633672827306116525712882959108434211652465621144702015336657459532134026915214509960877430595844287585350290234547564574848753110281101545931547225811763441710217452979668178025286460158324658852904105792472468108996135476637212057508192176910900422826969523438985332067597093454021924077101784215936539638808624420121459718286059401823614213214326004270471752802725625810953787713898846144256909835116371235019527013180204030167601567064268573820697948868982630904164685161783088076506964317303709708574052747204405282785965604677674192569851918643651835755242670293612851920696732320545562286110332140065912751551110134916256237884844001366366654055079721985816714803952429301558096968202261698837096090377863017797020488044826628817462866854321356787305635653577619877987998113667928954840972022833505708587561902023411398915823487627297968947621416912816367516125096563705174220460639857683971213093125)
20000

Все это работает как шарм. Мое единственное беспокойство заключается в том, что сложность бит такая доминирует в расчете, что мы могли бы просто сделать последовательный поиск. Или на самом деле, просто глядя на количество цифр, возможно, вы могли бы рассказать вам в значительной степени, на что вы смотрели. Это не так весело.