Un algoritmo di Fibonacci inverso?

Ci sono dozzine di modi per calcolare F (n) per un arbitrario n, molti dei quali hanno un ottimo runtime e utilizzo della memoria.

Tuttavia, supponiamo di voler porre la domanda opposta:

Dato F (n) per n> 2, cos’è n?

(La restrizione n> 2 è lì poiché F (1) = F (2) = 1 e non c’è inversione univoca).

Quale sarebbe il modo più efficace per risolvere questo problema? È facile farlo in un tempo lineare enumerando i numeri di Fibonacci e fermandosi quando si preme il numero di destinazione, ma c’è un modo per farlo più veloce di così?

EDIT: attualmente, la migliore soluzione qui pubblicata gira in O (log n) tempo usando O (log n) memoria, assumendo che le operazioni matematiche siano eseguite in O (1) e che una parola macchina possa contenere qualsiasi numero in O (1) spazio . Sono curioso di sapere se è ansible eliminare i requisiti di memoria, dal momento che è ansible calcolare i numeri di Fibonacci usando lo spazio O (1).

Poiché OP ha chiesto informazioni sulla soluzione matrix che non comportano calcoli a virgola mobile, eccola qui. Possiamo ottenere la complessità O(logn) questo modo, assumendo che le operazioni numeriche abbiano una complessità O(1) .

Prendiamo la matrice 2×2 A con la seguente struttura

 1 1 1 0 

Ora considera il vettore (8, 5) , memorizzando due numeri di Fibonacci consecutivi. Se lo si moltiplica per questa matrice, si otterrà (8*1 + 5*1, 8*1 + 5*0) = (13, 8) – il prossimo numero di fibonacci.
Se generalizziamo, A^n * (1, 0) = (f(n), f(n - 1)) .

L’algoritmo attuale richiede due passaggi.

  1. Calcola A^2 , A^4 , A^8 , ecc. Fino a passare il numero desiderato.
  2. Fai una ricerca binaria per n , usando i poteri calcolati di A

Su una nota a margine, qualsiasi sequenza della forma f(n) = k1*f(n-1) + k2*f(n-2) + k3*f(n-3) + .. + kt*f(nt) può essere presentato in questo modo.

Wikipedia dà il risultato come

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

dove Phi è la sezione aurea.

Se puoi facilmente interpretare F (n) in binario,

formula

Potresti essere sospettoso delle costanti 1.7 e 1.1. Questi funzionano perché d * 1.44042009041 + C non si avvicina mai molto a un numero intero.

Posso postare una derivazione domani se c’è interesse.

Ecco una tabella con n = 2 fino a 91, che mostra il risultato della formula prima della pavimentazione:

  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 

Misurare l’utilizzo della memoria contando le parole illimitate è un po ‘sciocco, ma fintanto che questo è il modello, c’è una O (log n) time, O (1) parola soluzione simile a Nikita Rybak che essenzialmente calcola n tramite la sua rappresentazione Zeckendorf , che è basato sui numeri di Fibonacci (YO DAWG).

Definire la matrice

  1 1 A = , 1 0 

che soddisfa

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

Invece della sequenza A^(2^k) , useremo la sequenza A^F(k) . L’ultima sequenza ha la proprietà che possiamo andare avanti con una matrice moltiplicata

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

e indietro con una matrice inversa e moltiplicazione

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

così possiamo build un iteratore bidirezionale con solo otto sei dodici parole supponendo di archiviare tutto come razionali (per evitare di ipotizzare l’esistenza di una divisione di costo unitario). Il resto sta semplicemente adattando questo algoritmo di spazio O (1) per trovare una rappresentazione 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] 

È stato dimostrato che la formula per un fib n è fib(n) = ( (phi)^n - (-phi)^(-n) ) / sqrt(5) dove phi = (1+sqrt(5)) / 2 , il numero della sezione aurea. (vedi questo link ).

Potresti provare a trovare un inverso matematico alla funzione fib di cui sopra, o altrimenti fare una ricerca binaria in 32/64 operazioni (a seconda di quanto grande è il tuo massimo ricercabile) per trovare il n che corrisponde al numero (prova ogni n per via informatica (n) e dividendo lo spazio campionario in due in base a come fib (n) si confronta con il dato numero di fibonacci).

Modifica: la soluzione di @ rcollyer è più veloce, poiché la mia è in O (lg n) e quella che ha trovato è in O (1) = tempo costante.

Quindi stavo pensando a questo problema e penso che sia ansible farlo in O (lg n) ora con O (lg n) utilizzo della memoria. Questo è basato sul fatto che

F (n) = (1 / √5) (Φ n – φ n )

Dove Φ = (1 + √5) / 2 e φ = 1 – Φ.

La prima osservazione è che φ n <1 per ogni n> 1. Ciò significa che per ogni n> 2, abbiamo quello

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

Ora prendi e scrivi in ​​binario come b k-1 b k-2 … b 1 b 0 . Ciò significa che

n = 2 k-1 b k-1 + 2 k-2 b k-2 + … + 2 1 b 1 + 2 0 b 0 .

Ciò significa che

F (n) = ⌊ Φ 2 k-1 b k-1 + 2 k-2 b k-2 + … + 2 1 b 1 + 2 0 b 0 / √5 ⌋

O, più leggibile, quello

F (n) = ⌊ Φ 2 k-1 b k-1 Φ 2 k-2 b k-2 … Φ 2 1 b 1 Φ 2 0 b 0 / √5 ⌋

Questo suggerisce il seguente algoritmo. Per prima cosa, inizia a calcolare Φ 2 k per tutti i k fino a calcolare un numero Φ z tale che ⌊ Φ z / √5 ⌋ sia maggiore del tuo numero F (n). Ora, da lì, scorrere all’indietro attraverso tutti i poteri di Φ hai generato in questo modo. Se il numero corrente è maggiore della potenza indicata di Φ, dividerlo per quel potere di Φ e registrare che il numero è stato diviso per questo valore. Questo processo recupera essenzialmente un bit di n alla volta sottraendo la massima potenza di 2 che è ansible alla volta. Di conseguenza, una volta che hai finito, avrai trovato n.

Il tempo di esecuzione di questo algoritmo è O (lg n), dal momento che è ansible generare Φ 2 i per quadratura ripetuta e generiamo solo termini O (lg n). L’utilizzo della memoria è O (lg n), poiché memorizziamo tutti questi valori.

Puoi trovare n per qualsiasi Fib (n) in O (1) tempo e O (1) spazio.

È ansible utilizzare un algoritmo CORDIC a virgola fissa per calcolare ln () usando solo i tipi di dati di tipo shift e add-on.

Se x = Fib (n), allora n può essere determinato da

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

Il tempo di esecuzione CORDIC è determinato dal livello di precisione desiderato. I due valori a virgola mobile sarebbero codificati come valori a virgola fissa.

L’unico problema con questa proposta è che restituisce un valore per i numeri che non sono nella sequenza di Fibonacci, ma il problema originale specificava specificatamente che l’input della funzione sarebbe Fib (n), il che implica che solo i numeri di Fibonacci validi sarebbero Usato.

EDIT: Non importa. Il richiedente ha dichiarato nei commenti che l’esponenziazione non è sicuramente un tempo costante.


L’esponenziazione è una delle operazioni matematiche consentite in un tempo costante? Se è così, possiamo calcolare F (n) in tempo costante tramite la formula in forma chiusa . Quindi, data una certa F, possiamo fare quanto segue:

  1. Calcola F (1), F (2), F (4), F (16), F (256), … fino a F (2 ^ k) <= F
  2. Esegui una ricerca binaria per i tra 2 ^ k e 2 ^ {k + 1} fino a F (i) <= F

Se F = F (n), la prima parte accetta i passi k = O (log (n)). La seconda parte è una ricerca binaria su un intervallo di dimensione O (2 ^ k), quindi accetta anche k = O (log (n)). Quindi, in totale, abbiamo O (log (n)) tempo nello spazio O (1) se (ed è un grande se) abbiamo l’esponenziazione nel tempo O (1).

Una forma chiusa della formula del numero di Fibonacci è:

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

Dove φ è la sezione aurea.

Se ignoriamo il fattore di arrotondamento, questo è invertibile e la funzione inversa è:

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

Poiché abbiamo ignorato il fattore di arrotondamento, c’è un errore nella formula che potrebbe essere calcolato. Tuttavia se consideriamo che un numero n è un numero di Fibonacci se l’intervallo [n * φ – 1 / n, n * φ + 1 / n] contiene un numero naturale allora:

Un numero è un numero di Fibonacci se l’intervallo [n * φ – 1 / n, n * φ + 1 / n] contiene un numero naturale e l’indice di quel numero nella sequenza di Fibonacci è dato dal log di arrotondamento (n * Sqrt (5) ) / logφ

Ciò dovrebbe essere fattibile in un tempo (pseudo) costante a seconda degli algoritmi utilizzati per calcolare il log e le radici quadrate ecc.

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

Potrebbe essere simile alla risposta di user635541. Non capisco del tutto il suo approccio.

Usando la rappresentazione a matrice per i numeri di Fibonacci, discussi in altre risposte, otteniamo un modo per passare da F_n e F_m a F_{n+m} e F_{nm} in tempo costante, usando solo più, moltiplicazione, meno e divisione (in realtà non vedere l’aggiornamento ). Abbiamo anche uno zero (la matrice di identity framework), quindi è un gruppo matematico!

Normalmente quando eseguiamo la ricerca binaria vogliamo anche un operatore di divisione per il calcolo delle medie. O almeno la divisione per 2. Tuttavia se vogliamo passare da F_{2n} a F_n richiede una radice quadrata. Fortunatamente si scopre che più e meno sono tutto ciò di cui abbiamo bisogno per una ricerca binaria di tempo quasi logaritmico!

Wikipedia scrive dell’approccio, ironicamente chiamato Fibonacci_search , ma l’articolo non è scritto molto chiaramente, quindi non so se è esattamente lo stesso approccio del mio. È molto importante capire che i numeri di Fibonacci usati per la ricerca di Fibonacci non hanno nulla a che fare con i numeri che stiamo cercando. È un po ‘confuso. Per dimostrare l’approccio, ecco in primo luogo un’implementazione della “ricerca binaria” standard usando solo il più e il meno:

 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 

Qui il test è una funzione booleana; a e b sono numeri fibonacci consecutivi f_k e f_{k-1} tali che la differenza tra il limite superiore superiore e lo inferiore inferiore è sempre f_k . Abbiamo bisogno sia di b che di aumentare e diminuire la variabile implicita k efficiente.

Bene, quindi come usiamo questo per risolvere il problema? Ho trovato utile creare un wrapper attorno alla nostra rappresentazione di Fibonacci, che nasconde i dettagli della matrice. In pratica (c'è una cosa del genere per un ricercatore di Fibonacci?) Vorresti mettere tutto in linea manualmente . Ciò ti risparmierebbe la ridondanza nelle matrici e migliorerebbe l'ottimizzazione dell'inversione della matrice.

 import numpy as np class Fib: def __init__(self, k, M): """ `k` is the 'name' of the fib, eg 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] 

Tuttavia, il codice funziona, quindi possiamo testarlo come segue. Notate quanto è diversa la funzione di ricerca da quando i nostri oggetti erano interi e non 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+ab, ba else: hi = mi a, b = ba, a return lo.k >>> search(lambda n: n <= 144) 12 >>> search(lambda n: n <= 0) 0 

La restante domanda aperta è se esiste un algoritmo di ricerca efficiente per i monoidi. Quello è uno che non ha bisogno di un negativo / additivo inverso. La mia ipotesi è no: senza il minimo è necessario il ricordo extra di Nikita Rybak.

Aggiornare

Ho appena realizzato che non abbiamo bisogno di divisione. Il determinante della matrice F_n è solo (-1)^n , quindi possiamo effettivamente fare tutto senza divisione. Nel seguito ho rimosso tutto il codice matrix, ma ho mantenuto la class Fib , solo perché tutto è diventato estremamente disordinato altrimenti.

 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 <= ) 20000 

Tutto funziona come un fascino. La mia unica preoccupazione è che la complessità del bit domina il calcolo, tanto che potremmo aver appena fatto una ricerca sequenziale. O in realtà, solo il numero di cifre potrebbe probabilmente dirti che cosa stavi guardando. Non è così divertente però.