[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>