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

I assume you did use some more mathematical knowledge about fibs than I 
have. Nevertheless your posting confirms that choosing the right algorithm 
is very important.
Your solution seems about time O(n), I admit that, even for very large n. 
When I said fib could not be realy O(n) for its time, I ment to refer to the 
simple layman solotion. Lesson learned: always keep looking further!
Thanks for your correction, Jos.

----- Original Message ----- 
From: "Arthur Nunes-Harwit" <anh at cs.rit.edu>
To: "Jos Koot" <jos.koot at telefonica.net>
Cc: "Stephen Bloch" <sbloch at adelphi.edu>; <laalaalovesu at yahoo.com>; 
<plt-scheme at list.cs.brown.edu>
Sent: Friday, January 09, 2009 6:03 PM
Subject: Re: Re:[plt-scheme] Dr.Scheme freezes on (fib 100) recursion


> The following algorithm from SICP is better.
>
> (define (square x) (* x x))
>
> (define (fib n)
>   (fib-iter 1 0 0 1 n))
>
> (define (fib-iter a b p q count)
>   (cond ((= count 0) b)
>         ((even? count)
>          (fib-iter a
>                    b
>                    (+ (square p) (square q))
>                    (+ (* 2 p q) (square q))
>                    (/ count 2)))
>         (else (fib-iter (+ (* b q) (* a q) (* a p))
>                         (+ (* b p) (* a q))
>                         p
>                         q
>                         (- count 1)))))
>
> Here are the timings.
>
>> (void (time (fib 1000000)))
> cpu time: 539 real time: 548 gc time: 0
>> (void (time (fib 2000000)))
> cpu time: 1518 real time: 1541 gc time: 13
>> (void (time (fib 3000000)))
> cpu time: 2741 real time: 2791 gc time: 0
>> (void (time (fib 4000000)))
> cpu time: 4214 real time: 4292 gc time: 12
>> (void (time (fib 5000000)))
> cpu time: 5250 real time: 5341 gc time: 11
>
> -Arthur
>
> On Fri, 9 Jan 2009, Jos Koot wrote:
>
>> 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