Program for Fibonacci numbers

Code:

	///https://www.geeksforgeeks.org/program-for-nth-fibonacci-number/
	#include <bits/stdc++.h>
	using namespace std;
	#define INF 1<<30
	#define endl '\n'
	#define maxn 100005
	#define tc printf("Case %d: ", cs)
	#define tcn printf("Case %d:\n", cs);
	#define FASTIO ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	typedef long long ll;
	const double PI = acos(-1.0);
	#define dbg(x) cerr << #x << " = " << x << endl;
	#define dbg2(x, y) cerr << #x << " = " << x << ", " << #y << " = " << y << endl;
	#define dbg3(x, y, z) cerr << #x << " = " << x << ", " << #y << " = " << y << ", " << #z << " = " << z << endl;
	#define dbg4(w,x, y, z) cerr << #w << " = " << w << ", " <<#x << " = " << x << ", " << #y << " = " << y << ", " << #z << " = " << z << endl;
	int fib0(int n)
	{
	if (n <= 1) return n;
	return fib0(n - 1) + fib0(n - 2);
	}
	int fib1(int n)
	{
	int f[n + 2];
	f[0] = 0;
	f[1] = 1;
	for (int i = 2; i <= n; i++) {
	f[i] = f[i - 1] + f[i - 2];
	}
	return f[n];
	}
	// O(n)
	int fib2(int n)
	{
	int a = 0, b = 1;
	if (n == 0) return a;
	for (int i = 2; i <= n; i++) {
	int c = a + b;
	a = b;
	b = c;
	}
	return b;
	}
	void multiply(int F[2][2], int M[2][2])
	{
	int x = F[0][0] * M[0][0] + F[0][1] * M[1][0];
	int y = F[0][0] * M[0][1] + F[0][1] * M[1][1];
	int z = F[1][0] * M[0][0] + F[1][1] * M[1][0];
	int w = F[1][0] * M[0][1] + F[1][1] * M[1][1];
	F[0][0] = x;
	F[0][1] = y;
	F[1][0] = z;
	F[1][1] = w;
	}
	void power(int F[2][2], int n)
	{
	int M[2][2] = {{1, 1}, {1, 0}};
	// n - 1 times multiply the matrix
	for (int i = 2; i <= n; i++) {
	multiply(F, M);
	}
	}
	void powerOptimize(int F[2][2], int n)
	{
	if (n == 0 || n == 1) return;
	int M[2][2] = {{1, 1}, {1, 0}};
	powerOptimize(F, n / 2);
	multiply(F, F);
	if (n & 1) multiply(F, M);
	}
	/// O(n)
	int fib3(int n)
	{
	int F[2][2] = {{1, 1}, {1, 0}};
	if (n == 0) return 0;
	power(F, n - 1);
	return F[0][0];
	}
	/// O(logn)
	int fib4(int n)
	{
	int F[2][2] = {{1, 1}, {1, 0}};
	if (n == 0) return 0;
	power(F, n - 1);
	return F[0][0];
	}
	int f[1000];
	/// O(logn)
	int fib5(int n)
	{
	if (n == 0) return 0;
	if (n == 1 || n == 2)
	return (f[n] = 1);
	// if fib(n) is already computed
	if (f[n]) return f[n];
	int k = (n & 1) ? (n + 1) / 2 : n / 2;
	f[n] = (n & 1) ? (fib5(k) * fib5(k) + fib5(k - 1) * fib5(k - 1))
	: (2 * fib5(k - 1) + fib5(k)) * fib5(k);
	return f[n];
	}
	/// O(1)
	int fib6(int n)
	{
	double phi = (1 + sqrt(5)) / 2;
	return round(pow(phi, n) / sqrt(5));
	}
	int main()
	{
	FASTIO
	///*
	//double start_time = clock();
	#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
	freopen("error.txt", "w", stderr);
	#endif
	//*/
	int n = 16;
	cout << fib0(n) << endl;
	cout << fib1(n) << endl;
	cout << fib2(n) << endl;
	cout << fib3(n) << endl;
	cout << fib4(n) << endl;
	cout << fib5(n) << endl;
	cout << fib6(n) << endl;
	//double end_time = clock();
	//printf( "Time = %lf ms\n", ( (end_time - start_time) / CLOCKS_PER_SEC)*1000);
	return 0;
	}

view raw fibonacci.cpp hosted with ❤ by GitHub

Share: