matrix and fibonacci

[Matthias Walter]

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
> 

The idea is not that bad but it contains a bug:

Once you modify M[0][1] in the second step of your loop, its changed
content is plugged into the third step. You might simply save the
contents of M in 4 additional variables and then use these to fill M
again (with the result of M*C).

In fact it suffices to store three values as all matrices M (and C) are
symmetric, that is, M[0][1] == M[1][0]. But I recommend to do this
*after* you made the current version work.

Matthias