Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!zaphod.mps.ohio-state.edu!think.com!mintaka!bloom-beacon!eru!hagbard!sunic!ugle.unit.no!ugle.unit.no!haltraet
From: haltraet@gondle.idt.unit.no (Hallvard Traetteberg)
Newsgroups: comp.lang.scheme
Subject: Re: fibonacci Numbers
Message-ID: <HALTRAET.91Apr14151210@gondle.idt.unit.no>
Date: 14 Apr 91 13:12:10 GMT
References: <1991Apr12.051844.15063@milton.u.washington.edu>
	<1991Apr14.030812.887@ariel.unm.edu>
Sender: news@ugle.unit.no
Followup-To: comp.lang.scheme
Organization: Norwegian Inst. of Tech., Div. of Computer Syst. and Telematics
Lines: 90
In-Reply-To: scavo@cie.uoregon.edu's message of 14 Apr 91 03:08:12 GMT

In a class on Knowledge Based Software Design we had an assignment on
fibonacci-numbers. We were supposed to demonstrate how one could logically
deduce the standard linear algorithm from the exponential one. When trying to
solve the problem I found the following formula:

    fib(n) = fib(m) * fib(n-m) + fib(m-1) * fib (n-m-1)

It's easy to prove correct by induction and equally easy to "prove"
intuitively by expanding the standard formula fib(n) = fib(n-1) + fib(n-2) a
couple of times.

By choosing m = (n+ n mod 2)/2 one is able to divide the problem into two
approximately equal problems. Writing the equations for n mod 2 = 0 and
n mod 2 = 1 gives:

fib(n) = (fib(n/2))^2 + (fib(n/2 - 1))^2             ; n mod 2 = 0
fib(n) = fib((n-1)/2)(fib((n-1)/2) + 2*fib((n-3)/2)) ; n mod 2 = 1

Each of the equations gives two fib-calculations around n/2, so the complexity
is linear. Since the n's are divided by two and thus reach 1 after log(n)
steps, the computation tree is bound to calculate som fib-numbers more than
once. The same kind of reasoning tells us that the standard fib-formula makes
redundant calculations since the complexity is exponential and n decreases by
at least 1 in each call.

By expanding the formulas I was able to find where the redundant calculations
were made. It wasn't difficult to reformulate the algorithm so to calculate
each fib-number only once. Since we still reach 1 after log(n) steps the
algorithm is O(log(n)). Unfortunately it is written in Common Lisp and uses
multiple values, but it shouldn't be hard to translate to Scheme:

;;; Auxillary function

(defun fib2-aux (n f1 f2)
  (cond ((< n 2) (values 1))
        ((evenp n) (+ (* f1 f1) (* f2 f2)))
	(t (* f1 (+ f1 (* 2 f2))))
))

;;; The fib-function itself (fib1 was the linear version, hence the name).

(defun fib2 (n)
  (case n
    ((0 1) (values 1 n 0))
    (2     (values 2 1 1))
    (t (multiple-value-bind (f1 f2 f3) (fib2 (truncate n 2))
	 (values (fib2-aux n f1 f2)
		 (if (evenp n)
		     (fib2-aux (1- n) f2 f3)
		     (fib2-aux (1- n) f1 f2))
		 (fib2-aux (- n 2) f2 f3))
	 ))
))

It's a bit hard to explain, but it works!  It actually calculates fib(n),
fib(n-1) and fib(n-2) at the same time, so it returns three numbers:

>(trace fib2)
>(fib2 100)
  1> (FIB2 100)
    2> (FIB2 50)
      3> (FIB2 25)
        4> (FIB2 12)
          5> (FIB2 6)
            6> (FIB2 3)
              7> (FIB2 1)
              <7 (FIB2 1 1 0)
            <6 (FIB2 3 2 1)
          <5 (FIB2 13 8 5)
        <4 (FIB2 233 144 89)
      <3 (FIB2 121393 75025 46368)
    <2 (FIB2 20365011074 12586269025 7778742049)
  <1 (FIB2 573147844013817084101 354224848179261915075 218922995834555169026)

573147844013817084101
354224848179261915075
218922995834555169026

The trace shows that it is logarithmic, it calculates the three fib-numbers
fib(n), fib(n-1) and fib(n-2) for each n. These are the only fib-numbers that
are calculated and additionally they are calculated only once. 

The use of multiple values make the code rather nice. I guess an equivalent
scheme implementation will have to return a list and destructure it with car
and cdr. Common Lisp isn't that bad is it? :-)

            - hal (Student at the Norwegian Institute of Technology)
--

                                       - haltraet (@idt.unit.no)