Newbie questions
Tony Rogvall
<>
Mon Mar 27 08:44:09 CEST 2006
> 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
More information about the erlang-questions
mailing list