Nty wyraz fibonacci

Witam,
Męczę się z tym zadaniem już trochę czasu liczę na jakieś rady:

Napisz algorytm obliczania n-ty wyraz ciągu Fibonacciego. Wejście: liczba naturalna n Wyjście: n-ty wyraz ciągu Fibonacciego.
Należy napisać algorytm, który działa w czasie O(logn). Dodatkowe wymaganie to: Program powinien wczytywać wartość n z konsoli.

Zrobiłem coś takiego, no ale są błędy w kompilacji. Liczę na pomoc.

edit: kod jest niepoprawny

To jest Fibonacci? Nie wygląda:) Żeby mieć ~logn Musisz użyć algebry, mnożenie macierzy.
https://en.wikipedia.org/wiki/Fibonacci_number
Pseudokod (Python):
https://github.com/lion137/blog/blob/master/Matrix_Exponetiation_Fibo.ipynb

When google for solution, then: Showing results for fibonacci Log N

OT
rozumiem, na rozgrzewkę albo interview zamiast fizz-buzz fibonacci O(n) albo dynamicznie z użyciem 'cache'
ale O(log n) albo zrzynasz gotowca z sieci abo co? Masz sam dojść do rozwiązania? chyba, że to akurat zadanie domowe z algebry a temat był omawiany na ćwiczeniach, ty go tylko implementujesz.

ja prosty inżynier jestem, rekurencje wypasałem ;)

Myślę że warto spojrzeć tu:

https://www.geeksforgeeks.org/program-for-nth-fibonacci-number/

Nie wiem Panowie co jest nie tak z tym kodem. Użyłem tego algorytmu z metody 6 co wysłał Sarrus ale chyba robię coś nie tak. Mogłby ktoś mi to ładnie wyjaśnić ;/
Plus jeszcze chciałbym dodać funkcję setprecision żeby można było sobie sprawdzać nieograniczone wyrazy ciągów.

#include <bits/stdc++.h>
#include <iostream>
#include <iomanip>

using namespace std;

int main()
{
const int MAX = 1000;
int f[MAX] = {0};
int fib(int n)
{
    cout << "Podaj nr wyrazu ciagu: ";
    cin>>n;
    if (n == 0)
        return 0;
    if (n == 1 || n == 2)
        return (f[n] = 1);
    if (f[n])
        return f[n];
    int k = (n & 1)? (n+1)/2 : n/2;
    f[n] = (n & 1)? (fib(k)*fib(k) + fib(k-1)*fib(k-1))
           : (2*fib(k-1) + fib(k))*fib(k);
    return f[n];
}
    cout<<setprecision(10000);
    cout<<endl<<"wyraz nr "<<n<<": "<<fib(n);
    return 0;
}

Co Ty funkcję w mainie Umieszczasz? Jakie "nieograniczone wyrazy ciągów" w trzydziestu jeden bitach (int)?

const int MAX = 1000; 
 
int f[MAX] = {0}; 

int fib(int n) { 
    
    if (n == 0) 
        return 0; 
    if (n == 1 || n == 2) 
        return (f[n] = 1); 

    if (f[n]) 
        return f[n]; 
  
    int k = (n & 1)? (n+1)/2 : n/2; 
 
    f[n] = (n & 1)? (fib(k)*fib(k) + fib(k-1)*fib(k-1)) 
           : (2*fib(k-1) + fib(k))*fib(k); 
  
    return f[n]; 
} 


int main(int argc, char **argv){	
	
	int n;
	cin >> n;
	cout << "\n";
	cout << fib(n);
	cout << "\n";
	return 0;
}

Umieściłeś ciało funkcji fib w ciele funkcji main. To się w ogóle kompiluje? Na tej stronie jest możliwość skopiowania przykładu przyciskiem. Użyj go.

Jesteś pewny że po prostu masz policzyć Fibonacciego?
A nie przypadkiem Fibonacciego modulo jakaś liczba? Albo Fibonacciego dla n tak małego, że by wynik mieścił się w typie wbudowanym?
Wygląda na to, że arytmetyka wielkich liczb jest tuż za twoim zasięgiem, a to jest potrzebne by policzyć dowolnego Fibonacciego.

Po:

• poprawieniu: typów, zakresów, inicjalizacji;
• Usunięciu zbędnych warunków, załączeniu pozostałych;
• Oraz innych niezbędnych ruchach ...

#include <iostream>
using namespace std;

unsigned long long fib(unsigned n)
{ 
	static const unsigned MAX=94;
	static unsigned long long f[MAX]={0,1,1};
	if(n>=MAX) return (unsigned long long)-1;
	if((!n)||(f[n])) return f[n];
	int k=(n+1)>>1; 
	return f[n]=(n&1)?(fib(k)*fib(k)+fib(k-1)*fib(k-1)):(2*fib(k-1)+fib(k))*fib(k);
}

int main()
{
	for(unsigned i=0;i<200;++i) cout<<i<<": "<<fib(i)<<endl;
	return 0;
}