<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<HTML><HEAD><TITLE></TITLE>
<META http-equiv=Content-Type content="text/html; charset=iso-8859-1">
<META content="MSHTML 6.00.2800.1528" name=GENERATOR></HEAD>
<BODY text=#000000 bgColor=#ffffff>
<DIV><FONT face=Arial color=#0000ff size=2><SPAN
class=989055008-27032006> Hello Nick,</SPAN></FONT></DIV>
<DIV><FONT face=Arial color=#0000ff size=2><SPAN
class=989055008-27032006></SPAN></FONT> </DIV>
<DIV><FONT face=Arial color=#0000ff size=2><SPAN
class=989055008-27032006> 1) - can I
compute fib(N) efficiently, and,</SPAN></FONT></DIV>
<DIV><FONT face=Arial color=#0000ff size=2><SPAN
class=989055008-27032006> 2) - how many (decimal)
digits are there in fib(N) </SPAN></FONT></DIV>
<DIV><FONT face=Arial color=#0000ff size=2><SPAN
class=989055008-27032006></SPAN></FONT> </DIV>
<DIV><FONT face=Arial color=#0000ff size=2><SPAN class=989055008-27032006>The
answer to 1) is yes</SPAN></FONT></DIV>
<DIV><FONT face=Arial color=#0000ff size=2><SPAN
class=989055008-27032006></SPAN></FONT> </DIV>
<DIV><FONT face=Arial><FONT size=2><FONT color=#0000ff><FONT><SPAN
class=989055008-27032006> Your original version runs in O (2
^0.69 N) time </SPAN></FONT>-</FONT></FONT></FONT></DIV>
<DIV><FONT face=Arial color=#0000ff size=2><SPAN
class=989055008-27032006> The improved version is O(N) but you
can do better than this and do this in O(ln N) </SPAN></FONT></DIV>
<DIV><FONT face=Arial color=#0000ff size=2><SPAN
class=989055008-27032006> (see the section marked double
iteration in <A
href="http://en.wikipedia.org/wiki/Fibonacci_number_program">http://en.wikipedia.org/wiki/Fibonacci_number_program</A>)</SPAN></FONT></DIV>
<DIV><FONT><FONT><FONT face=Arial><FONT color=#0000ff><FONT size=2> <SPAN
class=989055008-27032006>
</SPAN></FONT></FONT></FONT></FONT></FONT></DIV>
<DIV><FONT><FONT><FONT face=Arial><FONT color=#0000ff><FONT size=2><SPAN
class=989055008-27032006> 2) is much more difficult - you could or
course just compute fib(N) then take the log
-</SPAN></FONT></FONT></FONT></FONT></FONT></DIV>
<DIV><FONT><FONT><FONT face=Arial><FONT color=#0000ff><FONT size=2><SPAN
class=989055008-27032006>but this is cheating - so can you compute
the number of </SPAN></FONT></FONT></FONT></FONT></FONT><FONT face=Arial
color=#0000ff size=2><SPAN class=989055008-27032006>decomal digits in
fib(N) without</SPAN></FONT></DIV>
<DIV><FONT face=Arial color=#0000ff size=2><SPAN
class=989055008-27032006>actually going to the trouble of computing fib(N) - now
this might be easy but it certainly is not</SPAN></FONT></DIV>
<DIV><FONT face=Arial color=#0000ff size=2><SPAN
class=989055008-27032006>obvious... </SPAN></FONT></DIV>
<DIV><FONT face=Arial color=#0000ff size=2><SPAN
class=989055008-27032006></SPAN></FONT> </DIV>
<DIV><FONT face=Arial color=#0000ff size=2><SPAN
class=989055008-27032006>/Joe</SPAN></FONT></DIV>
<DIV><FONT face=Arial color=#0000ff size=2><SPAN
class=989055008-27032006></SPAN></FONT> </DIV>
<DIV><FONT face=Arial color=#0000ff size=2><SPAN
class=989055008-27032006></SPAN></FONT> </DIV>
<DIV><FONT face=Arial color=#0000ff size=2><SPAN
class=989055008-27032006></SPAN></FONT> </DIV>
<DIV><FONT face=Arial color=#0000ff size=2></FONT> </DIV><BR>
<BLOCKQUOTE
style="PADDING-LEFT: 5px; MARGIN-LEFT: 5px; BORDER-LEFT: #0000ff 2px solid; MARGIN-RIGHT: 0px">
<DIV class=OutlookMessageHeader lang=en-us dir=ltr align=left>
<HR tabIndex=-1>
<FONT face=Tahoma size=2><B>From:</B> owner-erlang-questions@erlang.org
[mailto:owner-erlang-questions@erlang.org] <B>On Behalf Of </B>Nick
Linker<BR><B>Sent:</B> den 27 mars 2006 05:27<BR><B>To:</B>
paris@dc.fi.udc.es<BR><B>Cc:</B> Erlang Questions<BR><B>Subject:</B> Re:
Newbie questions<BR></FONT><BR></DIV>
<DIV></DIV>Javier París Fernández wrote:<BR><BR>I made my version, but after
posting the question :-)<BR>
<BLOCKQUOTE><TT>fib(0) -> 0; </TT><BR><TT>fib(1) -> 1;
</TT><BR><TT>fib(N) -> </TT><BR><TT> fib(N, 0, 1).
</TT><BR><TT> </TT><BR><TT>fib(I, Pr, Cu) when I =< 1 ->
</TT><BR><TT> Cu; </TT><BR><TT>fib(I, Pr, Cu) ->
</TT><BR><TT> fib(I-1, Cu, Pr + Cu).
</TT><BR></BLOCKQUOTE>Thank you for your answer nonetheless.<BR><BR>
<BLOCKQUOTE cite=mid200603251127.58459.paris@dc.fi.udc.es type="cite"><PRE wrap="">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.</PRE></BLOCKQUOTE>Best regards,<BR>Linker
Nick.<BR></BLOCKQUOTE></BODY></HTML>