Re: matrix and fibonacci

[newcomer[bob]]

On Friday, 9 March 2012 at 14:07:10 UTC, Timon Gehr wrote:

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);

}

Thanks very much for the assist. All three of these methods
though, seem to have a bug. fib(), fi() and f() all produce the
same incorrect result which for lack of better word I'll call an
"off by one" bug. A call to any of these functions with any
integer value between 2 and 44 yields the return value of the
next higher integer, while 45 overflows.  For example, 2 => 2, 10
=> 89, and 15 => 987 which are the actual values for 3, 11 and 16.

Thanks,
Bob