Results 1 to 3 of 3

Math Help - O(Log(n)) Algorithm for Computing Fibonacci Numbers, SICP Ex. 1.19

  1. #1
    Newbie
    Joined
    May 2011
    From
    Los Angeles
    Posts
    23

    O(Log(n)) Algorithm for Computing Fibonacci Numbers, SICP Ex. 1.19

    Hello! I'm so glad this Math Forum exists. Hopefully the people here can help me out. First off, I'm not sure if I'm posting in the right section. I didn't see anything specifically on algorithms and computing but I saw someone else post a Fibonacci question here.

    Also, even though I am referencing an exercise of a book (SICP), this is not for any type of school assignment, I am studying this stuff on my own.

    MIT offers the book free, and the section this problem is in is here:

    Structure and Interpretation of Computer Programs

    Earlier in the text it was demonstrated that the recursively defined Fibonacci sequence can be computed with a "linear iterative" process (so only O(n) steps and O(1) space is required to complete the process). The exercise (1.19) is to complete an algorithm that computes Fib(n) in O(Log(n)) time. This is achieved by essentially "squaring" the Fibonacci function. Here is the text of the exercise:

    Recall the transformation of the state variables a and b in the fib-iter process of section 1.2.2: a a + b and b a. Call this transformation T, and observe that applying T over and over again n times, starting with 1 and 0, produces the pair Fib(n + 1) and Fib(n). In other words, the Fibonacci numbers are produced by applying Tn, the nth power of the transformation T, starting with the pair (1,0). Now consider T to be the special case of p = 0 and q = 1 in a family of transformations Tpq where Tpq transforms the pair (a,b) according to a bq + aq + ap and b bp + aq. Show that if we apply such a transformation Tpq twice, the effect is the same as using a single transformation Tp'q' of the same form, and compute p' and q' in terms of p and q. This gives us an explicit way to square these transformations, and thus we can compute Tn using successive squaring, as in the fast-expt procedure. Put this all together to complete the following procedure, which runs in a logarithmic number of steps:
    Code:
    (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
                       <??>      ; compute p'
                       <??>      ; compute q'
                       (/ count 2)))
            (else (fib-iter (+ (* b q) (* a q) (* a p))
                            (+ (* b p) (* a q))
                            p
                            q
                            (- count 1)))))
    So what I'm looking for is basically some hints on where to start and how to think about solving this type of problem (in this case, how to find p' and q'). I'm looking more for general problem-solving methods than specifics. Here is some of the work I've done on the problem so far:

    I started out trying to do some kind of algebra on the problem :/ Here is an image of my scratch work:

    http://www.chrisdavaz.com/files/19.png (I gave a link rather than uploaded because no matter what I seem to do the website says that this is not a valid image file.)

    And later on as text:

    a <- bq + aq + ap
    b <- bp + aq

    a <- (bp + aq) q + (bq + aq + ap) q + (bq + aq + ap) p
    b <- (bp + aq) p + (ba + aq + ap) q

    bpq + aq^2 + bq^2 + aq^2 + apq + bqp + aqp + ap ^2
    pq(b + a + b + a) + q^2(a + b + a) + p^2(a)

    2 pq (b + a) + q^2 (2 a + b) + p^2 (a)

    Later on I tried looking at the problem as a ratio between a and b (i.e., "the golden ratio"), since that ratio must be maintained from iteration to iteration:

    a(p + q) + bq
    ----------------
    bp + aq

    Again, I feel like I am on to something but wind up just staring at this and getting nowhere.

    Do any of the thoughts here make sense or is it just aimless wandering?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Opalg's Avatar
    Joined
    Aug 2007
    From
    Leeds, UK
    Posts
    4,041
    Thanks
    7
    The calculation that you need to find p' and q' goes like this.

    If T_{pq} is the transformation given by \begin{cases}a&\leftarrow\ bq+a(p+q), \\ b&\leftarrow\ bp+aq, \end{cases} then (T_{pq})^2 is given by

    \begin{cases}a&\leftarrow\ (bp+aq)q+(bq+a(p+q))(p+q) = b(2pq+q^2) + a(p^2+q^2+2pq+q^2), \\ b&\leftarrow\ (bp+aq)p+(bq+a(p+q))q = b(p^2+q^2) + a(2pq+q^2). \end{cases}

    This is of the form T_{p'q'}, where p' = p^2+q^2 and q' = 2pq+q^2.

    That deals with the first part of the exercise. I think that for the second part, you need to use the fact that T = T_{01}. Then by successively squaring that operation n times, you can compute T^{2^n}(1,0) = F_{2^n}, the (2^n)'th Fibonacci number.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    May 2011
    From
    Los Angeles
    Posts
    23
    Thanks Opalg! I'll study this and see where I went astray.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Fibonacci Numbers
    Posted in the Algebra Forum
    Replies: 8
    Last Post: June 10th 2010, 08:57 AM
  2. Fibonacci Numbers
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: March 30th 2010, 05:51 AM
  3. Fibonacci numbers
    Posted in the Math Challenge Problems Forum
    Replies: 3
    Last Post: September 1st 2009, 01:03 AM
  4. Proving Lucas Numbers and Fibonacci Numbers
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: March 19th 2008, 12:33 AM
  5. Algorithm for computing power sets
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 18th 2007, 06:59 AM

/mathhelpforum @mathhelpforum