Newbie questions

[Tony Rogvall]

>  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