//ciag fibonacciego O( log n )
//Metodą szybkiego potęgowania macierzy
//www.algorytm.org

/*
 * Macierze wyglądają tak:
 *
 * A = {a , b
 * 	    c , d}
 *
 * W = {w1 , w2
 *      w3 , w4}
 * */
#include <cstdio>

int main()
{
	//Nasza macierz początkowa
	unsigned n, A[2][2] = { {1,1},//Macierz pomocnicza do sybkiego potęgowania
					        {1,0}};
	unsigned W	[2][2] = { {1,1},//Macierz wynikowa
	                       {1,0}};

	printf("Podaj jaki wyraz ciągu Fibonacciego chcesz policzyc: ");
	scanf("%u",&n);
	for(unsigned i = 1;i <= n;i<<=1)
	{
		//Zmienne pomocnicze do wymnażania
		unsigned a = A[0][0],b = A[0][1],c = A[1][0],d = A[1][1];

		if((i&n) != 0)
		{
			//Zmienne pomocnicze do wymnożenia macierzy wynikowej * macierz A
			unsigned w1 = W[0][0],w2 = W[0][1],w3 = W[1][0],w4 = W[1][1];

			W[0][0] = w1 * a + w2 * c;
			W[1][0] = w3 * a + w4 * c;
			W[0][1] = w1 * b + w2 * d;
			W[1][1] = w3 * b + w4 * d;
		}

		//Potęgujemy macierz A
		A[0][0] = a * a + b * c;
		A[1][0] = c * a + d * c;
		A[0][1] = a * b + b * d;
		A[1][1] = c * b + d * d;
	}
	printf("%u wyraz ciagu Fibonacciego to: %u\n\n",n,W[1][1]);
	printf("Macierz wynikowa wyglada tak:\n");
	printf("%u %u\n",W[0][0],W[0][1]);
	printf("%u %u\n",W[1][0],W[1][1]);
	return 0;
}