Fibonacci

[•Cosmin]

Comentarii la postul http://infoarena.ro/blog/fibonacci

[•dbaluta]

O(logn), dat fiind faptul că știm formula pentru al n-lea Fibonacci number și a n-a puterea a lui x se poate calcula în O(logn).

[•scipianus]

Da,de aceeasi parere sunt si eu. Avand formula pentru al n-lea termen trebuie facuta doar ridicarea la putere in timp logaritmic,deci complexitate O(log n) , doar ca precizia nu stiu cat de mare va fi la radicalii aia  .

[•Vman]

se poate si fara golden ratio, cu exponentiere de matrice si nu mai ai probleme cu precizia

o alta alternativa ar fi plecand de la formulele
F(2k) = F(k)[2F(k+1)−F(k)]
F(2k+1) = F(k+1)^2+F(k)^2
iar inmultirile se pot face ceva mai repede cu http://en.wikipedia.org/wiki/Karatsuba_algorithm

[•bent_larsen]

Parca e si in arhiva educationala Cosmin problema asta daca nu ma insel.

[•Cosmin]

Rezultatul Fn are O(n/log n) cifre. Deci algoritmul trebuie sa aiba cel putin timp de rulare O(n/log n).

Formula cu ratia de aur nu e prea utila pt ca faci calcule cu numere irationale si ai nevoie de precizie buna.

[•yonatan]

Nu se poate face cu ridicare la putere in timp logaritmic de matrice?
Ca la problema iepuri http://infoarena.ro/problema/iepuri


L.E.: Nu citisem comentariul lui Vlad.

[•Cosmin]

Ma interesa complexitatea algoritmului cel mai bun.

[•tudalex]

Se mai poate si preprocesa folosind templateuri in C++ [ 0 ], avand apoi O(1) per query. Daca ai in mod ipotetic timp constant pe adunari si inmultiri cea mai rapida metode sa folosesti ridicare la putere in timp logaritmic [ 1 ] folosind o matrice de ordin 2, complexitatea fiind de O(log N). Lucru mentionat si de ceilalti care au postat mai sus.

[ 0 ] - http://blog.emptycrate.com/node/271 (primul link gasit pe google, sigur sunt numeroase metode de a face asta)
[ 1 ] - http://infoarena.ro/problema/lgput

[•Cosmin]

Preprocesarea e o idee, nu conteaza daca o faci folosind templateuri sau altfel.
Folosirea acestei idei triseaza scopul problemei, pentru ca tot platesti timpul undeva.

Asa cum am zis si mai sus, raspunsul O(log N) e gresit, pentru ca rezultatul va avea multe cifre.
Destul de repede vei avea nevoie sa implementezi numere mari pentru care operatiile de adunare, inmultire ... nu ruleaza in timp constant.

Vlad e mai aproape de raspuns, dar nici el nu mi-a zis complexitatea algoritmului lui. Oricum exista algoritm mai bun.

[•proflaurian]

Complexitatea la care te gandesti e ceva de forma O( n^a )  unde a e prin apropiere de 1,7 ?

[•proflaurian]

Scuze. Am aruncat o vorba fara nicio explicatie. Eu ma gandeam la ceva recursiv pe metoda urmatoare:

(F_m+n,F_m+n-1)=( F_mF_n+F_m-1F_n+F_mF_n-1 , F_mF_n+F_m-1F_n-1)

De aici

(F_2k,F_2k-1)=( F_k²+2F_kF_k-1 , F_k²+F_k-1²)

 si

(F_2k+1,F_2k)=( F_2k+F_2k-1,F_2k)

Astfel se obtine ceva similar cu ce spunea Vlad. La fiecare pas, n se injumatateste si se aplica operatii de inmultire si adunare care duc la complexitate L²  ( unde L este numarul de cifre n/log n ). Sumand aceste complexitati mie imi da ceva de genul  O ( n^1,7 ) .

[•Vman]

sa incerc o estimare...
rezultatul va tinde catre 2^n, deci va avea n biti, deci n/logn cifre. Din cate am citit ar exista un algoritm de inmultire in O(c log c), deci o inmultire ar dura n / log n * log (n / log n) = n / log n * (log n - log log n) = n - n log log n / log n, rezulta o complexitate finala de n^2 log n 

[•Cosmin]

Algoritmul naiv in care folosesti numere mari si le aduni unu cate unu ia O(n^2/log^2 n) timp.

@Adrian ai gresit pe la calcule. La ultimul pas inmultesti numere de O(n/log n) cifre in L^2 deci algoritmul ia cel putin O(n^2/log^2 n) care e mai mare decat O(n^1.7). Acuma vezi ca algoritmul ce nu foloseste o inmultire eficienta ca pas intermediar nu bate algoritmul naiv.

@Vlad ai bushit ceva. Algoritmul tau ar trebui sa fie mai rapid decat cel naiv.

[•Vman]

asa e, am un n in plus acolo la final, de fapt complexitatea la mine e O(N log N)

[•Cosmin]

@Vlad tot iti lipseste o observatie.

La pasul i avem numere de 2^i / log n cifre. Daca sumezi costul inmultirilor vezi ca ajungi la O(n) ca si complexitate finala.

Complexitatea e putin mai mare de O(n)  pentru ca algoritmul cel mai bun de inmultire pe numere mari cunoscut are complexitatea Θ(n log(n) 2^Θ(log*(n)) (http://en.wikipedia.org/wiki/Multiplication_algorithm).

[•proflaurian]

Eu am facut afirmatia cu n^1,7 plecand de la un calcul aproximativ al sumei din (2^k/k)² pentru k < log n folosind n cu 10-20 de cifre. Am refacut cu n avand mult mai multe cifre ( pana la 200) si dupa socotelile mele se ajunge cam la n². Nu afirm ca asta e raspunsul corect, e doar o parere bazata pe calcule destul de aproximative  

Am folosit urmatoru cod:

Cod:

#include <iostream>
#include<cmath>
using namespace std;

int main()
{
    int i;
    long double n=1,N,C,S=0,EXP;
    for(i=1;i<200;i++)n*=10;
    for(N=n/2;N>=2;N/=2)
    {
        C=N/log(N);
        C*=C;
        S+=C;
    }
    EXP=log(S)/log(n);
    cout << EXP;
    return 0;
}