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

Thanks, that is a clear explanation of the code Arthur showed. It has been 
proven that there are limits to the power of programming languages (or 
formal systems in general), but again and again I am amazed how far we :(me 
not included): can move the limit further away, not only by faster hardware, 
but more importantly by more clever algorithms.
Jos

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


>
> On Jan 9, 2009, at 10:47 AM, 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.
>
> Quite true.  I would assume that (+ n m) takes at most linear time in  the 
> lengths of n and m.  Since the "right answer" to fib(n) is  exponential in 
> n, the lengths of the numbers being added are linear  in n, which means 
> the cost of addition should make (at most) the  difference between O(n) 
> and O(n^2) time.
>
> On a related subject that somebody mentioned off-list, Scheme's 
> optimization of tail-recursion makes a multiplicative difference of 
> approximately the depth of the recursion, i.e. the difference between 
> O(n) and O(n^2) time -- about the same effect as the cost of addition.
>
> And, of course, replacing the double recursion of the naive algorithm 
> with a single recursion makes the difference between O(n) or O(n^2)  or 
> O(n^3) and O(phi^n) time, a MUCH more noticeable difference.
>
> Arthur adds:
>> 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)))))
>
>
> I hadn't seen this expressed in Scheme before; cute.
>
> For those who haven't seen the algorithm at all, it relies on the 
> observation that the transformation from <fib(r), fib(r+1)> to <fib(r +1), 
> fib(r+2)> is simply multiplication by the matrix
> +-      -+
> |  0   1 |
> |  1   1 |
> +-      -+
> Call this matrix F.  Then multiplying by the matrix F^n effects a 
> transformation from <fib(r),fib(r+1)> to
> <fib(r+n), fib(r+n+1)>; in particular, it gets you from <fib(0),fib(1)
> > to <fib(n),fib(n+1)>.  So if you can figure out how to
> exponentiate that remarkably simple matrix quickly, it allows you to 
> compute fib(n) quickly.  (In fact, you can compute F^n once, and then  get 
> the nth-number in ANY Fibonacci sequence, no matter what the  starting 
> numbers are, in constant time!)  Raising something to the n- th power, of 
> course, can be done in time O(logn) by repeated squaring  (again ignoring 
> the non-constant cost of primitive arithmetic  operations when the numbers 
> no longer fit into a machine word).
>
> So where the naive algorithm takes time O(phi^n) and the algorithm in  my 
> previous post takes time O(n) or O(n^2) (depending on whether you  count 
> the cost of primitive arithmetic operations), this one takes  time O(logn) 
> or O(n*logn) (ditto).
>
> However, nobody would come up with this algorithm who hadn't taken  linear 
> algebra.
>
> Stephen Bloch
> sbloch at adelphi.edu