matrix and fibonacci

[Timon Gehr]

On 03/09/2012 06:50 AM, newcomer[bob] wrote:
> The following is a matrix implementation of the fibonacci algorithm:
>
> int fib(int n) { int M[2][2] = {{1,0},{0,1}} for (int i = 1; i < n;
> i++) M = M * {{1,1},{1,0}} return M[0][0]; }
>
> problem is I don't really understand how matrix multiplication works
> so i cannot translate it to an equivalent solution in D. Thank for
> you assistance in advance.
>
> newcomer[bob]

// simple 2x2 matrix type
alias int[2][2] Mat;
// 2x2 matrix multiplication
Mat matmul(Mat a, Mat b){
	return [[a[0][0]*b[0][0]+a[0][1]*b[1][0], a[0][0]*b[0][1]+a[0][1]*b[1][1]],
	        [a[1][0]*b[0][0]+a[1][1]*b[1][0], 
a[0][1]*b[0][1]+a[1][1]*b[1][1]]];
}
// implementation of your algorithm
int fib(int n)in{assert(n>=0 && n<46);}body{
	int M[2][2] = [[1,0],[0,1]];
	int F[2][2] = [[1,1],[1,0]];
	foreach (i; 0..n) M = matmul(F,M);
	return M[0][0];
}
// faster way of computing matrix power
int fi(int n)in{assert(n>=0 && n<46);}body{
	Mat M = [[1,0],[0,1]];
	Mat F = [[1,1],[1,0]];
	for(;n;n>>=1){
		if(n&1) M = matmul(F,M);
		F = matmul(F,F);
	}
	return M[0][0];
}
// closed form derived from basis transform to eigenbasis
int f(int n)in{assert(n>=0 && n<46);}body{
	enum sqrt5=sqrt(5.0);
	return cast(int)((((1+sqrt5)/2)^^(n+1)-((1-sqrt5)/2)^^(n+1))/sqrt5);
}