<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN"> <HTML><HEAD> <META http-equiv=Content-Type content="text/html; charset=iso-8859-1"> <META content="MSHTML 6.00.6000.16788" name=GENERATOR> <STYLE></STYLE> </HEAD> <BODY> <DIV>Fib cannot realy run in time O(n), because (+ n m) does not run in time O(1) for large values of n and m. With the function I posted yesterday (: very much like yours :) I find: (#lang scheme no debugging) (all time in milliseconds)</DIV> <DIV> </DIV> <DIV>(void (time (fib 100))) cpu time: 0 real time: 0 gc time: 0 (void (time (fib 1000))) cpu time: 0 real time: 0 gc time: 0 (void (time (fib 10000))) cpu time: 0 real time: 0 gc time: 0 (void (time (fib 100000))) cpu time: 1360 real time: 1391 gc time: 265 (void (time (fib 500000))) cpu time: 35641 real time: 36110 gc time: 7338</DIV> <DIV> </DIV> <DIV>The last call takes about 26 times the time of the last but one call. If fib would run in time O(n), you would expect a factor 5. </DIV> <DIV> </DIV> <DIV>Jos</DIV> <DIV> </DIV> <DIV>----- Original Message ----- <DIV>From: "Stephen Bloch" <<A href="mailto:sbloch@adelphi.edu">sbloch@adelphi.edu</A>></DIV> <DIV>To: <<A href="mailto:laalaalovesu@yahoo.com">laalaalovesu@yahoo.com</A>></DIV> <DIV>Cc: <<A href="mailto:plt-scheme@list.cs.brown.edu">plt-scheme@list.cs.brown.edu</A>></DIV> <DIV>Sent: Thursday, January 08, 2009 3:50 PM</DIV> <DIV>Subject: Re:[plt-scheme] Dr.Scheme freezes on (fib 100) recursion</DIV></DIV> <DIV> </DIV>> > On Jan 8, 2009, at 1:45 AM, laa laa wrote: > >> my son and i coded a program to compute fibonacci sequences. it  >> works fine for low numbers, but when you try to do something higher  >> like (fib 100) Dr.Scheme freaks out and freezes up. we're wondering  >> what's going on? is there a reason for this. . . . >> >> (define (fib n) >>   (if (< n 3) >>       1 >>   (+ (fib (- n 1)) (fib (- n 2))))) > > This is one of my favorite (for classroom use) examples of algorithm  > (in)efficiency.  It is obviously a "correct" definition, but think  > about how long it takes.  The only number it actually knows is 1, and  > the only operation it does is +, and it never uses a computed result  > more than once, so if the right answer is (say) 350 quintillion, it  > has to do around 350 quintillion "+" operations to add up to that  > answer.  At a billion operations per second, that's eleven thousand  > years.  (Interestingly enough, it only requires a stack depth of 100,  > so stack overflow isn't a problem: if you can keep the computer  > running DrScheme for eleven thousand years without anybody tripping  > over the power cord or cosmic rays disrupting the RAM, it WILL  > produce the right answer.) > > John posted an alternative definition, using the technique of "memo- > ization": in a nutshell, every time the function computes the answer  > to a question, it stores the answer in a table (indexed by the  > function input) so the next time it is asked the same question, it  > just re-uses the answer from the table rather than re-computing it.   > All of that is happening behind the scenes in the "memoize" package,  > although you could easily write your own memoized version of the  > function.  With this simple transformation, the algorithm becomes  > linear-time in n, so it takes approximately 100 "+" operations rather  > than 350 quintillion. > > Here's another approach which doesn't require a look-up table.  When  > you say "Fibonacci sequences", you're more right than you may  > realize: there is not ONE Fibonacci sequence but infinitely many,  > each sequence determined by a different first two elements.  If you  > start with F(1)=1, F(2)=1, you get "the usual" Fibonacci sequence,  > but you can also start from F(1)=17, F(2)=-4 or any other starting  > place you wish.  So we define > > ; fib : nat-num -> nat-num > > (check-expect (fib 1) 1) > (check-expect (fib 2) 1) > (check-expect (fib 3) 2) > (check-expect (fib 4) 3) > (check-expect (fib 5) 5) > (check-expect (fib 6) 8) > > (define (fib n) >   (general-fib 1 1 n)) > > ; general-fib : num (prev2) num (prev1) nat-num(n) > ; computes the n-th Fibonacci number in the sequence whose 1st and  > 2nd elements are prev2 and prev1 > > (check-expect (general-fib 17 -4 1) 17) > (check-expect (general-fib 17 -4 2) -4) > (check-expect (general-fib 17 -4 3) 13) > (check-expect (general-fib 17 -4 4) 9) > (check-expect (general-fib 17 -4 5) 22) > > Now, how to define this?  Consider the sequence starting with the  > numbers x and y, then chop off the first number.  You still have a  > Fibonacci sequence, but now it starts with y and x+y, and the nth  > element of the old sequence is the n-1-th element of the new  > sequence.  This gives us a natural recursive definition: > > (define (general-fib prev2 prev1 n) >   (cond [(<= n 1) prev2] >         [(= n 2) prev1] >         [else (general-fib prev1 (+ prev2 prev1) (- n 1))])) > > This version turns out to be much more efficient (all times are in  > milliseconds): > > (time (fib 10)) > cpu time: 3 real time: 4 gc time: 0 > 55 > > (time (fib 100)) > cpu time: 4 real time: 5 gc time: 0 > 354224848179261915075 > > (time (fib 1000)) > cpu time: 34 real time: 49 gc time: 0 > 434665576869374564356885276750406258025646605173717804024817290895365554 > 179490518904038798400792551692959225930803226347752096896232398733224711 > 61642996440906533187938298969649928516003704476137795166849228875 > > > Moral of the story: sometimes generalizing the problem makes it  > easier to solve. > > Stephen Bloch > <A href="mailto:sbloch@adelphi.edu">sbloch@adelphi.edu</A> > > > > _________________________________________________ >  For list-related administrative tasks: >  <A href="http://list.cs.brown.edu/mailman/listinfo/plt-scheme">http://list.cs.brown.edu/mailman/listinfo/plt-scheme</A></BODY></HTML>