Newbie questions

[Nick Linker]

Tony Rogvall wrote:

>>  Good solution :-)
>> Now I also have different idea without using recursion. It is based  
>> on the following equation
>> [F_n  ]   [1  1]   [F_n-1]
>> [     ] = [    ] * [     ]
>> [F_n-1]   [1  0]   [F_n-2]
>> And we just have to calculate k-th power of the matrix [[1,1], 
>> [1,0]]. It is possible to do within O(log(k)).
>>
>
> Here is my contrib (written many years ago, it may work :-)
>
> ffib(N) ->
>     {UN1,_,_,_} = lucas_numbers(1,-1,N-1),
>     UN1.
>
> lucas_numbers(P, Q, M) ->
>     m_mult(exp({P,-Q,1,0}, M), {1,P,0,2}).
>
> exp(A, N) when tuple(A), size(A)==4, is_integer(N), N > 0 ->
>     m_exp(A, N, {1,0,0,1}).
>
> m_exp(A, 1, P) ->
>     m_mult(A,P);
> m_exp(A, N, P) when ?even(N) ->
>     m_exp(m_sqr(A), N div 2, P);
> m_exp(A, N, P) ->
>     m_exp(m_sqr(A), N div 2, m_mult(A, P)).
>
> m_mult({A11,A12,A21,A22}, {B11,B12,B21,B22}) ->
>     { A11*B11 + A12*B21, A11*B12 + A12*B22,
>       A21*B11 + A22*B21, A21*B12 + A22*B22 }.
>
> m_sqr({A,B,C,D}) ->
>     BC = B*C,
>     A_D = A + D,
>     { A*A+BC, B*A_D, C*A_D, D*D + BC }.
>
>
> /Tony

Cool. I guess the problem of computing Fibonacci is finally closed. Thanks.

Best regards,
Linker Nick.