[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