Re: [問題] 費氏數列快速計算的 scheme 程式

[jimfan (jimfan)]

: >     *Exercise 1.19:* There is a clever algorithm for computing the
: >     Fibonacci numbers in a logarithmic number of steps.  Recall the
: >     transformation of the state variables a and b in the 'fib-iter'
: >     process of section *note 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 T^n, 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 T_(pq), where T_(pq)
: >     transforms the pair (a,b) according to a <- bq + aq + ap and b <-
: >     bp + aq.  Show that if we apply such a transformation T_(pq) twice,
: >     the effect is the same as using a single transformation T_(p'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 T^n 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:(5)


就係不明白他說的"transformation"是啥......我數學太爛了

不過算法確實精彩，假設要找fib(17)，以下列舉每項 fib-iter 的輸入：

   a    b    p    q  count
==========================
   1    0    0    1     17
   1    1    0    1     16
   1    1    1    1      8
   1    1    2    3      4
   1    1   13   21      2
   1    1  610  987      1
2584 1597  610  987      0

count 為零時，b = 1597，所以 f(17) = 1597

神奇的是，count 為 1 時，f(15) 與 f(16) 分別出現為 p、q

count 為 2 時，f(7) 與 f(8) 分別出現為 p、q

往上推如是

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 14.199.97.157
※ 文章網址: https://www.ptt.cc/bbs/Programming/M.1504951623.A.4D0.html
推 moebear: 我是沒看 不過應該是用矩陣快速冪算的
→ jimfan: 用“矩陣快速冪”找到國力清華大學一個站
→ jimfan: https://goo.gl/ScDuT6
→ jimfan: 手殘，國立清華大學才是
推 hijkxyzuw: transformation 就是線性變換，
→ hijkxyzuw: 而線性變換可以用乘上一個矩陣表示
推 hijkxyzuw: 原本的寫法應該是把矩陣相乘展開的結果