# Newbie questions

Joe Armstrong (AL/EAB) joe.armstrong@REDACTED
Mon Mar 27 11:08:27 CEST 2006

```   Hello Nick,

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
obvious...

/Joe

________________________________

From: owner-erlang-questions@REDACTED [mailto:owner-erlang-questions@REDACTED] On Behalf Of Nick Linker
Sent: den 27 mars 2006 05:27
To: paris@REDACTED
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) ->
fib(N, 0, 1).

fib(I, Pr, Cu) when I =< 1 ->
Cu;
fib(I, Pr, Cu) ->
fib(I-1, Cu, Pr + Cu).

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.

Regards.

Best regards,