algorithm - algoritmo - fibonacci java

¿Un algoritmo de Fibonacci inverso?

Question

Hay docenas de formas de calcular F (n) para un n arbitrario, muchas de las cuales tienen un gran tiempo de ejecución y uso de memoria.

Sin embargo, supongamos que quisiera hacer la pregunta opuesta:

Dado F (n) para n> 2, ¿qué es n?

(La restricción n> 2 está ahí desde F (1) = F (2) = 1 y no hay inversa inequívoca).

¿Cuál sería la forma más eficiente de resolver este problema? Es fácil hacer esto en tiempo lineal al enumerar los números de Fibonacci y detenerse cuando alcanzas el número objetivo, pero ¿hay alguna forma de hacerlo más rápido que eso?

EDITAR: actualmente, la mejor solución publicada aquí se ejecuta en tiempo O (log n) usando la memoria O (log n), suponiendo que las operaciones matemáticas se ejecutan en O (1) y que una palabra máquina puede contener cualquier número en O (1) espacio . Tengo curiosidad si es posible eliminar los requisitos de memoria, ya que puede calcular los números de Fibonacci usando O (1) espacio.

Answer 1

Así que estaba pensando en este problema y creo que es posible hacerlo en O (lg n) vez con el uso de memoria O (lg n). Esto se basa en el hecho de que

F (n) = (1 / √5) (Φ ⁿ - φ ⁿ )

Donde Φ = (1 + √5) / 2 y φ = 1 - Φ.

La primera observación es que φ ⁿ <1 para cualquier n> 1. Esto significa que para cualquier n> 2, tenemos que

F (n) = ⌊ Φ ⁿ / √5 ⌋

Ahora, tome ny escríbalo en binario como b _k-1 b _k-2 ... b ₁ b ₀ . Esto significa que

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

Esto significa que

F (n) = ⌊ Φ ^{2 k-1 b _k-1 + 2 k-2 b _k-2 + ... + 2 1 b ₁ + 2 0 b ₀} / √5 ⌋

O, más legible, eso

F (n) = ⌊ Φ ^{2 k-1 b _k-1} Φ ^{2 k-2 b _k-2} ... Φ ^{2 1 b ₁} Φ ^{2 0 b ₀} / √5 ⌋

Esto sugiere el siguiente algoritmo. Primero, comience a calcular Φ ^{2 k} para todo k hasta que calcule un número Φ ^z tal que ⌊ / ^z / √5 ⌋ sea mayor que su número F (n). Ahora, desde allí, itera hacia atrás a través de todos los poderes de Φ generados de esta manera. Si el número actual es mayor que la potencia indicada de Φ, entonces divídalo por esa potencia de Φ y anote que el número fue dividido por este valor. Este proceso esencialmente recupera un bit de n a la vez al restar la mayor potencia de 2 que puede a la vez. En consecuencia, una vez que haya terminado, habrá encontrado n.

El tiempo de ejecución de este algoritmo es O (lg n), ya que puede generar Φ ^{2 i} mediante cuadratura repetida, y solo generamos términos O (lg n). El uso de memoria es O (lg n), ya que almacenamos todos estos valores.

Answer 2

EDITAR: No importa. El autor de la pregunta ha declarado en comentarios que la exponenciación definitivamente no es un tiempo constante.

¿La exponenciación es una de las operaciones matemáticas que permitirás en tiempo constante? Si es así, podemos calcular F (n) en tiempo constante a través de la Wikipedia . Entonces, dado algo de F, podemos hacer lo siguiente:

1. Calcule F (1), F (2), F (4), F (16), F (256), ... hasta F (2 ^ k) <= F <F (2 ^ {k + 1})
2. Haga una búsqueda binaria para i entre 2 ^ k y 2 ^ {k + 1} hasta que F (i) <= F <F (i + 1)

Si F = F (n), entonces la primera parte toma k = O (log (n)) pasos. La segunda parte es una búsqueda binaria en un rango de tamaño O (2 ^ k), por lo que también toma k = O (log (n)). Entonces, en total, tenemos O (log (n)) tiempo en O (1) espacio si (y es un gran si) tenemos exponenciación en O (1) tiempo.

Answer 3

Esto podría ser similar a la respuesta del usuario635541. No entiendo completamente su enfoque.

Usando la representación matricial para números de Fibonacci, discutida en otras respuestas, obtenemos un camino para ir de F_n y F_m a F_{n+m} y F_{nm} en tiempo constante, usando solo más, multiplicación, menos y división (en realidad no! vea la actualización ). También tenemos un cero (la matriz de identidad), ¡así que es un grupo matemático!

Normalmente, al hacer una búsqueda binaria, también queremos que un operador de división tome promedios. O al menos división por 2. Sin embargo, si queremos pasar de F_{2n} a F_n se requiere una raíz cuadrada. Afortunadamente resulta que más y menos son todo lo que necesitamos para una búsqueda binaria "casi" binaria de tiempo logarítmico.

Wikipedia escribe sobre el enfoque, irónicamente llamado Fibonacci_search , pero el artículo no está muy claramente escrito, así que no sé si es exactamente el mismo enfoque que el mío. Es muy importante comprender que los números de Fibonacci utilizados para la búsqueda de Fibonacci no tienen nada que ver con los números que estamos buscando. Es un poco confuso Para demostrar el enfoque, primero se trata de una implementación de la ''búsqueda binaria'' estándar que usa más y menos:

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

Aquí la test es alguna función booleana; b son números consecutivos de Fibonacci f_k y f_{k-1} tales que la diferencia entre el límite superior hi y el límite inferior lo es siempre f_k . Necesitamos tanto a como b para poder aumentar y disminuir la variable implícita k eficiente.

Bien, entonces, ¿cómo usamos esto para resolver el problema? Me pareció útil crear un envoltorio alrededor de nuestra representación de Fibonacci, que oculta los detalles de la matriz. En la práctica (¿existe tal cosa para un buscador de Fibonacci?) , Querrá alinear todo manualmente . Eso le ahorraría la redundancia en las matrices y haría una optimización alrededor de la inversión de la matriz.

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]

Sin embargo, el código funciona, por lo que podemos probarlo de la siguiente manera. Observe cuán poco diferente es la función de búsqueda cuando nuestros objetos eran enteros y no 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)
0

La pregunta abierta restante es si hay un algoritmo de búsqueda eficiente para monoides. Eso es uno que no necesita un inverso negativo / aditivo. Mi conjetura es no: que sin menos necesitas la memoria extra de Nikita Rybak.

Actualizar

Me di cuenta de que no necesitamos división en absoluto. El determinante de la matriz F_n es (-1)^n , por lo que podemos hacer todo sin división. En el siguiente eliminé todo el código de la matriz, pero mantuve la clase Fib , simplemente porque todo se volvió tan extremadamente desordenado de lo contrario.

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

Todo esto funciona como un encanto. Mi única preocupación es que la complejidad de bits domine el cálculo, que bien podríamos haber hecho una búsqueda secuencial. O, de hecho, solo mirando la cantidad de dígitos probablemente podría decirle más o menos lo que estaba mirando. Aunque eso no es tan divertido.

Answer 4

Medir el uso de memoria contando palabras ilimitadas es algo tonto, pero mientras ese sea el modelo, hay una solución de palabra O (log n), O (1) similar a la de Nikita Rybak que en esencia computa n través de su representación Zeckendorf , que se basa en los números de Fibonacci (YO DAWG).

Definir la matriz

 1 1
A = ,
1 0

que satisface

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

En lugar de la secuencia A^(2^k) , vamos a usar la secuencia A^F(k) . La última secuencia tiene la propiedad de que podemos avanzar con una matriz multiplicada

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

y hacia atrás con una matriz inversa y multiplicación

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

así que podemos construir un iterador bidireccional con solo ocho seis y doce palabras suponiendo que almacenamos todo como racionales (para evitar asumir la existencia de una división del costo unitario). El resto simplemente está adaptando este algoritmo de espacio O (1) para encontrar una representación de Zeckendorf.

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]

Answer 5

Puede encontrar n para cualquier Fib (n) en O (1) tiempo y O (1) espacio.

Puede usar un algoritmo CORDIC de punto fijo para calcular ln () usando solo cambios y agregar tipos de datos enteros.

Si x = Fib (n), entonces n puede determinarse por

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

CORDIC run-time está determinado por el nivel de precisión deseado. Los dos valores de coma flotante se codificarían como valores de punto fijo.

El único problema con esta propuesta es que devuelve un valor para los números que no están en la secuencia de Fibonacci, pero el problema original estableció específicamente que la entrada a la función sería Fib (n), lo que implica que solo serían válidos los números de Fibonacci. usado.

Answer 6

Se ha demostrado que la fórmula para un fib n es fib(n) = ( (phi)^n - (-phi)^(-n) ) / sqrt(5) donde phi = (1+sqrt(5)) / 2 , el número de la sección dorada. (ver este enlace ).

Podría intentar encontrar un inverso matemático a la función fib anterior, o realizar una búsqueda binaria en 32/64 operaciones (dependiendo de qué tan grande sea el máximo de búsqueda) para encontrar la n que coincida con el número (pruebe cada n calculando fib (n) y dividir el espacio de muestra en dos según cómo se compara fib (n) con el número de fibonacci dado).

Editar: la solución de @rcollyer es más rápida, ya que la mía está en O (lg n) y la que encontró está en O (1) = tiempo constante.

Answer 7

Si puede interpretar fácilmente F (n) en binario,

Puede sospechar de las constantes 1.7 y 1.1. Estos funcionan porque d * 1.44042009041 + C nunca se acerca mucho a un número entero.

Puedo publicar una derivación mañana si hay interés.

Aquí hay una tabla con n = 2 a 91, que muestra el resultado de la fórmula antes del piso:

 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

''

Answer 8

Una forma cerrada de la fórmula del número de Fibonacci es:

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

Donde φ es la proporción áurea.

Si ignoramos el factor de redondeo, esto es invertible y la función inversa es:

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

Debido a que ignoramos el factor de redondeo, hay un error en la fórmula que podría calcularse. Sin embargo, si consideramos que un número n es un número de Fibonacci, si el intervalo [n * φ - 1 / n, n * φ + 1 / n] contiene un número natural, entonces:

Un número es un número de Fibonacci si el intervalo [n * φ - 1 / n, n * φ + 1 / n] contiene un número natural y el índice de ese número en la secuencia de Fibonacci viene dado por el registro de redondeo (n * Sqrt (5) ) / logφ

Esto debería ser factible en tiempo (pseudo) constante según los algoritmos utilizados para calcular el registro y las raíces cuadradas, etc.

Editar: φ = (1 + Sqrt (5)) / 2

Answer 9

Wikipedia da el resultado como

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

donde Phi es la proporción áurea.

Answer 10

Dado que OP ha preguntado acerca de la solución de matriz que no involucra ningún cálculo de punto flotante, aquí está. Podemos lograr la complejidad O(logn) esta manera, suponiendo que las operaciones numéricas tienen O(1) complejidad.

Tomemos la matriz A 2x2 que tiene la siguiente estructura

1 1
1 0

Ahora considere el vector (8, 5) , almacenando dos números consecutivos de Fibonacci. Si lo multiplicas por esta matriz, obtendrás (8*1 + 5*1, 8*1 + 5*0) = (13, 8) - el próximo número de Fibonacci.
Si generalizamos, A^n * (1, 0) = (f(n), f(n - 1)) .

El algoritmo real toma dos pasos.

1. Calcule A^2 , A^4 , A^8 , etc. hasta que pasemos el número deseado.
2. Haga una búsqueda binaria por n , usando potencias calculadas de A

En una nota lateral, cualquier secuencia de la forma f(n) = k1*f(n-1) + k2*f(n-2) + k3*f(n-3) + .. + kt*f(nt) se puede presentar así.