Newbie questions
Nick Linker
xlcr@REDACTED
Thu Mar 30 13:22:26 CEST 2006
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.
More information about the erlang-questions
mailing list