Re: matrix and fibonacci

[newcomer[bob]]

On Friday, 9 March 2012 at 05:50:03 UTC, 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]

I attempted the following but it does not work:

int fib(int n)
     ulong[2][2] M = [[1,0], [0,1]];
     ulong[2][2] C = [[1,1], [1,0]];
     foreach (i; 0 .. n) {
        M[0][0] = M[0][0] * C[0][0] + M[0][0] * C[0][1];
        M[0][1] = M[0][1] * C[0][1] + M[0][1] * C[1][1];
        M[1][0] = M[0][1] * C[0][0] + M[1][1] * C[0][1];
        M[1][1] = M[1][1] * C[0][1] + M[1][1] * C[1][1];
     }
     return M[0][0];
}

any ideas what I'm doing wrong?

Thanks,
Bob