On 03/09/2012 10:51 AM, newcomer[bob] wrote:
On Friday, 9 March 2012 at 09:22:47 UTC, newcomer[bob] wrote:
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)
long[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
Turns out that this this is an algorithm for calculating the
powers of two up to 2^63. I still cannot find how to modify it to
produce the fibonacci sequence though. Any advice would be
appreciated.
Thanks,
Bob
http://en.wikipedia.org/wiki/Matrix_multiplication#Non-technical_example
http://en.wikipedia.org/wiki/Fibonacci_number#Matrix_form
I don't understand what you are trying to do above.
