Joe Armstrong (AL/EAB)
Mon Mar 27 11:08:27 CEST 2006
1) - can I compute fib(N) efficiently, and,
2) - how many (decimal) digits are there in fib(N)
The answer to 1) is yes
Your original version runs in O (2 ^0.69 N) time -
The improved version is O(N) but you can do better than this and do this in O(ln N)
(see the section marked double iteration in http://en.wikipedia.org/wiki/Fibonacci_number_program)
2) is much more difficult - you could or course just compute fib(N) then take the log -
but this is cheating - so can you compute the number of decomal digits in fib(N) without
actually going to the trouble of computing fib(N) - now this might be easy but it certainly is not
From: [mailto:] On Behalf Of Nick Linker
Sent: den 27 mars 2006 05:27
Cc: Erlang Questions
Subject: Re: Newbie questions
Javier París Fernández wrote:
I made my version, but after posting the question :-)
fib(0) -> 0;
fib(1) -> 1;
fib(N, 0, 1).
fib(I, Pr, Cu) when I =< 1 ->
fib(I, Pr, Cu) ->
fib(I-1, Cu, Pr + Cu).
Thank you for your answer nonetheless.
However, as Kostis said, this has more to do with having two recursive calls
each time than with it being tail recursion or not. If you try to see how it
evaluated, the number of recursive calls expands exponentially.
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the erlang-questions