[plt-scheme] Dr.Scheme freezes on (fib 100) recursion

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)

(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

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. 

Jos


----- Original Message ----- 
From: "Stephen Bloch" <sbloch at adelphi.edu>
To: <laalaalovesu at yahoo.com>
Cc: <plt-scheme at list.cs.brown.edu>
Sent: Thursday, January 08, 2009 3:50 PM
Subject: Re:[plt-scheme] Dr.Scheme freezes on (fib 100) recursion


> 
> 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
> sbloch at adelphi.edu
> 
> 
> 
> _________________________________________________
>  For list-related administrative tasks:
>  http://list.cs.brown.edu/mailman/listinfo/plt-scheme
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.racket-lang.org/users/archive/attachments/20090109/205c4562/attachment.html>