Обратный алгоритм Фибоначчи?
существуют десятки способов вычисления F (n) для произвольного n, многие из которых имеют большое время выполнения и использование памяти.
однако, предположим, я хотел бы задать противоположный вопрос:
учитывая F (n) для n > 2, Что такое n?
(ограничение n > 2 находится там, так как F(1) = F(2) = 1 и нет однозначного обратного).
каков был бы наиболее эффективный способ решения этой проблемы? Это легко сделать в линейном времени с помощью перечисляя числа Фибоначчи и останавливаясь, когда вы попадаете в целевой номер, но есть ли какой-то способ сделать это быстрее, чем это?
EDIT: в настоящее время, лучшим решением здесь выложил, работает в o(зарегистрируйте N) времени, используя o(зарегистрируйте N) памяти, предполагая, что математические операции выполняются за O(1) и что машинное слово может содержать любое число за O(1) пространство. Мне любопытно, можно ли отказаться от требований к памяти, так как вы можете вычислить числа Фибоначчи с помощью O(1) пространство.
10 ответов:
поскольку OP спросил о матричном решении, не включающем никаких вычислений с плавающей запятой, вот оно. Мы можем достичь
O(logn)сложность таким образом, предполагая, что числовые операцииO(1)сложности.возьмем матрицу 2х2
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)можно представить так.
Википедия дает результат как
n(F) = Floor[ Log(F Sqrt(5) + 1/2)/Log(Phi)]где Phi-золотое сечение.
Если вы можете легко интерпретировать 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'
измерение использования памяти путем подсчета неограниченных слов-это глупо, но пока это модель, есть O (log n) время, O (1) слово решение аналогично Никите рыбаку, что по сути вычисляет
nчерез представления Цекендорфа, который основан на числах Фибоначчи (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,таким образом, мы можем построить двунаправленный итератор только с
восемьшестьдвенадцать слов, предполагая, что мы храним все как рациональные (чтобы избежать предположения о существовании деления на единицу стоимости). Остальное просто адаптирует этот алгоритм O (1)-пространства для нахождения a Представление цекендорфа.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]
было доказано, что формула для fib n является
fib(n) = ( (phi)^n - (-phi)^(-n) ) / sqrt(5)здесьphi = (1+sqrt(5)) / 2число золотого сечения. (см. этой ссылке).вы можете попытаться найти математическую обратную функцию fib выше, или иначе выполнить двоичный поиск в 32/64 операциях (в зависимости от того, насколько велик ваш поисковый максимум), чтобы найти n, который соответствует числу (попробуйте каждый n, вычисляя fib (n) и разделяя ваше пространство выборки на два в соответствии с тем, как fib(n) сравнивается с заданным число Фибоначчи.)
Edit: решение @rcollyer быстрее, так как мое находится в O(lg n), а тот, который он нашел, находится в O(1) = постоянное время.
Так что я думал об этой проблеме, и я думаю, что это можно сделать в O(lg n) время с использованием o(lg n) памяти. Это основано на том, что
F (n) = (1 / √5) (Φn - φn)
где Φ = (1 + √5)/2 и φ = 1 - Φ.
первое наблюдение заключается в том, что φn 1. Это означает, что для любого N > 2, мы имеем, что
F (n) = ⌊ Φn / √5 ⌋
теперь, возьмите n и запишите его в двоичном виде как bk-1bк-2...b1b0. Это значит, что
n = 2k-1 bk-1 + 2к-2 bк-2 + ... + 21 b1 + 20 b0.
Это означает, что
F (n) = ⌊ Φ2k-1 bk-1 + 2к-2 bк-2 + ... + 21 b1 + 20 b0 / √5 ⌋
или, что более понятно, что
F (n) = ⌊ Φ2k-1 bk-1Φ2к-2 bк-2 ... Φ21 b1Φ20 b0 / √5 ⌋
Это предполагает следующий алгоритм. Во-первых, начать вычисления Φ2k для всех k, пока вы не вычислите число Φz такой, что ⌊ Φz / √5 ⌋ это больше, чем ваше число F(n). Теперь, оттуда, повторите назад по всем степеням Φ, которые вы создали таким образом. Если текущее число больше указанной степени Φ, то разделите его на эту степень Φ и запишите, что число было разделено на это значение. Этот процесс по существу восстанавливает один бит n за один раз, вычитая самый большой мощность 2, что вы можете одновременно. Следовательно, как только вы закончите, вы найдете n.
время выполнения этого алгоритма равно O (lg n), так как вы можете генерировать Φ2Я путем повторного возведения в квадрат, и мы генерируем только o (lg n) членов. Использование памяти-O (lg n), так как мы храним все эти значения.
вы можете найти n для любого Fib(n) в O(1) времени и O (1) пространстве.
вы можете использовать алгоритм с фиксированной точкой CORDIC для вычисления в (), используя только сдвиг и добавить на целочисленные типы данных.
Если x = Fib( n), то n можно определить по
n = int(2.0801 * ln(x) + 2.1408)время выполнения CORDIC определяется желаемым уровнем точности. Два значения с плавающей запятой будут кодироваться как значения с фиксированной точкой.
единственная проблема с этим предложением заключается в том, что он возвращает значение для числа, которые не находятся в последовательности Фибоначчи, но исходная задача конкретно заявила, что вход в функцию будет Fib(n), что означает, что будут использоваться только действительные числа Фибоначчи.
правка: не бери в голову. Аскер заявил в комментариях, что возведение в степень определенно не является постоянным временем.
является ли возведение в степень одной из математических операций, которые вы позволите в постоянное время? Если это так, мы можем вычислить F( n) в постоянное время через формула закрытой формы. Затем, учитывая некоторые F, мы можем сделать следующее:
- Вычислить F(1), F(2), F(4), F(16), F(256), ... пока F (2^k)
- бинарного ищите меня между 2^K и 2^{к+1}, пока ф(Я)
Если F = F(n), то первая часть принимает шаги k = O(log (n)). Вторая часть представляет собой двоичный поиск в диапазоне размера O(2^k), поэтому он также принимает k = O(log (n)). Итак, в общей сложности мы имеем o(log(n)) время в O (1) пространстве если (и это большое "если") у нас есть возведение в степень за O(1) времени.
замкнутая форма формулы числа Фибоначчи:
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φ
Это должно быть выполнимо в (псевдо) - постоянное время в зависимости от алгоритмов, используемых для вычисления логарифма и квадратных корней и т. д.
Edit: φ = (1+Sqrt (5)) / 2
это может быть похоже на ответ user635541. Я не совсем понимаю его подход.
используя матричное представление для чисел Фибоначчи, обсуждаемых в других ответах, мы получаем способ перейти от
F_nиF_mдоF_{n+m}иF_{n-m}в постоянное время, используя только плюс, умножение, минус и деление (на самом деле нет! смотрите обновление). У нас также есть ноль (матрица идентичности), поэтому это математическая группа!обычно при выполнении двоичного поиска мы также хотим оператор деления для взятия средних. Или хотя бы деление на 2. Однако, если мы хотим пойти от
F_{2n}доF_nдля этого требуется квадратный корень. К счастью, оказывается, что плюс и минус-это все, что нам нужно для логарифмического времени "почти" двоичного поиска!Википедия пишет о подходе, иронически называемом 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]однако код работает, так что мы можем проверить его следующим образом. Обратите внимание, как мало отличается функция поиска от того, когда наши объекты были целыми числами, а не Fibonaccis.
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) 0The остается открытым вопрос есть ли эффективный алгоритм поиска для моноидов. Это тот, который не нуждается в минусе / аддитивная инверсия. Я думаю, нет: что без минуса вам нужна дополнительная память о Никите рыбаке.
обновление
я только что понял, что нам вообще не нужно разделение. Определитель
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все это работает как шарм. Мой единственное беспокойство заключается в том, что такая битовая сложность доминирует над вычислением, что мы могли бы также просто выполнить последовательный поиск. Или на самом деле, просто глядя на количество цифр, вероятно, можно сказать вам, на что вы смотрели. Это не так весело.