Newbie questions

[Joe Armstrong (AL/EAB)]

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

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

	Best regards,
	Linker Nick.
	

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://erlang.org/pipermail/erlang-questions/attachments/20060327/18fec42f/attachment.htm>